Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Algorithmes randomisés : Recherche médiane

Description

Cette séance de cours se concentre sur l'utilisation du hasard combiné à la récursion pour rechercher efficacement la médiane d'une liste. L'instructeur explique le concept de médiane, l'importance de choisir un élément pivot et la complexité de l'algorithme. En sélectionnant au hasard des pivots, l’algorithme peut atteindre une complexité temporelle linéaire, ce qui en fait un outil puissant pour la recherche médiane.

Source officielle

Concepts associés (16)

Algorithme probabiliste

En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j].

Complexité en temps

En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.

Complexité en espace

En algorithmique, la complexité en espace est une mesure de l'espace utilisé par un algorithme, en fonction de propriétés de ses entrées. L'espace compte le nombre maximum de cases mémoire utilisées simultanément pendant un calcul. Par exemple le nombre de symboles qu'il faut conserver pour pouvoir continuer le calcul. Usuellement l'espace que l'on prend en compte lorsque l'on parle de l'espace nécessaire pour des entrées ayant des propriétés données est l'espace nécessaire le plus grand parmi ces entrées ; on parle de complexité en espace dans le pire cas.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Afficher plus

Séances de cours associées (39)

Résoudre les jeux de parité dans la pratique

Explore les aspects pratiques de la résolution des jeux de parité, y compris les stratégies gagnantes, les algorithmes, la complexité, le déterminisme et les approches heuristiques.

Factorisation des polynômes : complexité et algorithmes

Plonge dans la complexité de l'affacturage des polynômes et ses implications pour la sécurité.

Complexité algorithmique : analyse du temps de déplacement

Couvre la complexité algorithmique et l'analyse du temps de trajet, en se concentrant sur la mesure du temps pris par les algorithmes et l'évaluation de leurs performances.

Complexité algorithmique: Notation Theta

Explore la complexité algorithmique, en comparant les taux de croissance en utilisant la notation Theta et en caractérisant différentes classes de complexité.

Récursion dans la programmation

Explore la récursion dans la programmation, en discutant de ses avantages, de ses défis et de son impact sur la complexité des algorithmes.

Afficher plus

Concepts associés (16)

Algorithme probabiliste

Complexité en temps

Algorithme

Complexité en espace

Computational complexity

Afficher plus