Séance de cours

Analyse algorithmique : croissance, recherche et logarithme

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours couvre l'analyse de la croissance de l'algorithme, y compris l'ordre de croissance du temps de voyage, le comportement asymptotique et les comparaisons polynomiales. Il introduit des algorithmes de recherche dans les listes, en se concentrant sur la recherche binaire et son temps de déplacement. La séance de cours explore également le concept de logarithmes, en discutant de leurs propriétés, de leur croissance exponentielle et de leur comportement à l'infini. Divers algorithmes et leurs complexités sont explorés, tels que la recherche binaire récursive et la génération de sous-chaînes. La session se termine par des exercices pratiques sur l'analyse des algorithmes et la mise en œuvre de la recherche binaire.

Source officielle

Proximité ontologique

Informatique théorique

Algorithmes et structures de données: Analyse de la complexité des algorithmes

Concepts associés (32)

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.

Recherche dichotomique

La recherche dichotomique, ou recherche par dichotomie (), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Le principe est le suivant : comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente. Le nombre d'itérations de la procédure, c'est-à-dire le nombre de comparaisons, est logarithmique en la taille du tableau.

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].

Algorithme de recherche

En informatique, un algorithme de recherche est un type d'algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions répondant au problème. Supposons que l'ensemble de ses entrées soit divisible en sous-ensemble, par rapport à un critère donné, qui peut être, par exemple, une relation d'ordre. De façon générale, un tel algorithme vérifie un certain nombre de ces entrées et retourne en sortie une ou plusieurs des entrées visées.

Arbre binaire de recherche

En informatique, un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.

Afficher plus

Séances de cours associées (64)

Complexité et induction: Algorithmes et preuves

Couvre la complexité, les algorithmes et les preuves du pire cas, y compris l'induction mathématique et la récursion.

Récursion et recherche binaire

Introduit des algorithmes de récursion et de recherche binaire pour résoudre efficacement les problèmes.

Algorithmes en informatique: techniques de recherche et de tri

Fournit un aperçu des algorithmes de recherche et de tri essentiels en informatique.

Algorithmes : Résumé de la semaine

Couvre les algorithmes de recherche, de tri, d'optimisation et le problème d'arrêt.

Analyses de complexité des algorithmes

Couvre les analyses de complexité des algorithmes et leurs complexités de temps dans le pire des cas.

Afficher plus

Concepts associés (32)

Complexité en temps

Recherche dichotomique

Algorithme probabiliste

Algorithme de recherche

Arbre binaire de recherche

Afficher plus