Revision sheet: Introduction aux Structures et Algorithmes

📋 Plan du Cours

1. Notions d’algorithme
2. Complexité algorithme
3. Tri et recherche
4. Structures linéaires
5. Arbres et arbres binaires
6. Graphes et parcours
7. Représentations d’arbres
8. Arbres équilibrés
9. Structures de données avancées
10. Méthodes de hachage

📖 1. Notions d’algorithme

🔑 Notions clés & Définitions

• Algorithme (selon Encyclopedia Universalis) : La spécification d’un schéma de calcul, sous forme d’une suite finie d’opérations élémentaires obéissant à un enchaînement déterminé. Il s’agit d’un processus précis, reproductible, permettant de résoudre un problème donné en un nombre fini d’étapes.
• Historique : La notion d’algorithme précède celle d’ordinateur. Dès Euclide (3e siècle av. J.-C.), des méthodes de résolution de problèmes étaient connues. Le terme « algorithme » vient de Al-Khwarizmi (820 après J.C.), dont l’ouvrage d’arithmétique a influencé la conception des règles de calcul et la résolution d’équations.
• Caractéristiques d’un algorithme : Il doit être une suite finie de règles appliquées dans un ordre déterminé, permettant la transformation de données en résultats, indépendamment des données initiales. De plus, il doit être déterministe, c’est-à-dire que toute exécution sur les mêmes données donne le même résultat.
• Expression indépendante du langage : Un algorithme peut être exprimé dans différents langages de programmation, mais son principe reste identique. Par exemple, l’algorithme d’Euclide pour le calcul du plus grand commun diviseur reste le même en Pascal, C ou Lisp.
• Notion de programme : Un programme est une implémentation concrète d’un algorithme dans un langage de programmation, visant à automatiser la résolution d’un problème. Il doit respecter la logique de l’algorithme, tout en étant adapté au langage utilisé.

📝 Points essentiels

• La notion d’algorithme a été formulée dès l’Antiquité, avec des méthodes de résolution de problèmes mathématiques, mais le terme moderne apparaît avec Al-Khwarizmi (820 après J.C.), dont l’ouvrage a influencé la terminologie et la conception des méthodes de calcul.
• Un algorithme doit être une suite finie d’opérations, déterministe, et indépendante du langage de programmation. La traduction d’un algorithme dans un langage spécifique ne modifie pas sa logique fondamentale.
• La relation entre algorithme et programme est essentielle : un programme est une réalisation concrète d’un algorithme, permettant son exécution automatique par un ordinateur.
• La spécification d’un algorithme doit respecter ses caractéristiques pour garantir sa reproductibilité, sa fiabilité, et sa portabilité.
• La définition d’un algorithme selon Encyclopedia Universalis insiste sur la suite finie d’opérations élémentaires, enchaînées de manière déterminée, pour aboutir à un résultat précis.

💡 À retenir

Un algorithme est une suite finie, déterministe, et indépendante du langage de programmation, qui transforme des données en résultats en suivant un schéma de calcul précis.

📖 2. Complexité algorithme

🔑 Notions clés & Définitions

• Temps d'exécution (T.e) : Durée nécessaire pour qu’un algorithme traite une donnée. Selon Wirth (1976), il s’agit d’une mesure du coût en ressources temporelles lors de l’exécution d’un programme.

• Facteurs influençant le T.e :

  • La taille des données (n), par exemple, le nombre d’éléments à trier ou rechercher.
  • La quantité de code compilé, notamment le nombre d’instructions élémentaires, qui dépend de la machine et du compilateur.
  • La machine utilisée, sa vitesse d’exécution et ses caractéristiques matérielles.

• Complexités dans le pire, meilleur et cas moyen :

  • Pire cas (Tmax(n)) : maximum du temps d’exécution pour des données de taille n.
  • Meilleur cas (Tmin(n)) : minimum du temps d’exécution pour des données de taille n.
  • Cas moyen (Tmoy(n)) : temps moyen sur tous les jeux de données de taille n, selon Cormen et al. (2009).

• Calcul de la complexité dans le pire des cas :

  • Règles générales :
    1. Le coût d’une affectation ou d’un test est considéré comme une constante c.
    2. La somme des coûts d’une séquence d’instructions est la somme de leurs coûts.
    3. Le coût d’un branchement conditionnel est la somme du coût du test et du plus grand des deux coûts possibles.
    4. La complexité d’une boucle est la somme, sur tous ses tours, du coût de son corps et de la condition de sortie.

• Complexité asymptotique et notation grand O :

  • Définition : Si T(n) et f(n) sont deux fonctions, T(n) = O(f(n)) si ∃ n0, c > 0 tels que ∀ n ≥ n0, T(n) ≤ c·f(n). Selon Cormen et al. (2009), cela permet d’estimer le comportement du T.e pour de grandes valeurs de n, en ignorant les constantes et termes de moindre ordre.

• Règles de calcul des complexités asymptotiques :

  • Seul le terme dominant dans un polynôme compte (ex : n^3 dans n^3 + 7n^2 + 77n).
  • L’exponentielle domine la puissance, qui domine le logarithme (ex : 2^n > n^k > log n).
  • La somme de deux fonctions asymptotiques est dominée par la plus grande (ex : O(max(f(n), g(n)))).
  • La multiplication de deux fonctions asymptotiques donne une complexité combinée (ex : O(f(n)·g(n))).

📝 Points essentiels

• La complexité d’un algorithme se mesure principalement par son temps d’exécution, influencé par la taille des données, la vitesse du matériel, et la quantité de code généré.
• La notation grand O permet d’estimer le comportement asymptotique du temps d’exécution pour de très grandes données, en se concentrant sur le terme dominant.
• La règle générale pour le calcul de la complexité dans le pire cas repose sur des règles simples : affectations et tests comptés comme constants, boucle dont le coût est la somme des coûts de chaque tour, et branchements évalués par le coût du test plus le coût de la branche la plus coûteuse.
• La complexité asymptotique permet de comparer efficacement différents algorithmes, en ignorant les constantes et les termes de moindre ordre.

💡 À retenir

La complexité d’un algorithme, exprimée en notation grand O, fournit une estimation du coût en temps pour de grandes tailles de données, permettant de choisir l’algorithme le plus efficace selon le contexte.

📖 3. Tri et recherche

🔑 Notions clés & Définitions

• Recherche séquentielle dans un tableau non trié : méthode consistant à parcourir chaque élément du tableau dans l’ordre jusqu’à trouver l’élément recherché ou atteindre la fin. La complexité est en O(n) dans le pire cas.
• Recherche séquentielle dans un tableau trié : similaire à la recherche dans un tableau non trié, mais en exploitant l’ordre pour arrêter la recherche si l’élément courant dépasse la valeur recherchée. La complexité reste en O(n), mais peut être optimisée dans certains cas.
• Ajout dans un tableau non trié : opération simple consistant à placer le nouvel élément à la fin du tableau si l’espace le permet, avec une complexité en O(1).
• Suppression dans un tableau non trié : recherche de l’élément puis décalage des éléments suivants vers la gauche pour combler le vide, avec une complexité en O(n).
• Tri à bulle (Wirth, 1971) : méthode consistant à comparer et échanger successivement les éléments adjacents jusqu’à ce que le tableau soit trié. Caractéristique : tri stable, tri sur place, interne. Complexité en O(n²).
• Tri par sélection : consiste à sélectionner le minimum dans la partie non triée et à le placer au début, puis à répéter pour le reste. Caractéristique : tri stable, tri sur place, interne. Complexité en O(n²).

📝 Points essentiels

• La recherche séquentielle dans un tableau non trié nécessite de parcourir en moyenne la moitié des éléments, avec une complexité en O(n). La recherche dans un tableau trié peut s’arrêter dès que l’élément courant dépasse la valeur cible, mais reste en O(n) dans le pire cas.
• L’ajout dans un tableau non trié est immédiat (O(1)), tandis que la suppression nécessite de rechercher puis décaler, ce qui coûte en O(n).
• Les tris à complexité O(n²) (bulle, sélection, insertion) sont simples à implémenter mais peu efficaces pour de grands ensembles. Ils sont stables et trient en place.
• Le tri par insertion est efficace en cas de listes presque triées, avec une complexité en O(n) dans le meilleur cas.
• Le tri rapide (QuickSort) et le tri par fusion (MergeSort) ont une complexité en O(n log n), mais ne sont pas abordés ici.
• La stabilité d’un tri signifie que l’ordre initial des éléments équivalents est conservé. Le tri sur place n’utilise pas d’espace supplémentaire significatif.

💡 À retenir

Les opérations de recherche et de tri varient en complexité selon que le tableau est trié ou non, et le choix de l’algorithme dépend de la taille et de la nature des données. Les tris à O(n²) sont simples mais peu efficaces pour de grandes quantités, tandis que les tris en O(n log n) offrent de meilleures performances pour des ensembles volumineux.

📖 4. Structures linéaires

🔑 Notions clés & Définitions

• Structure linéaire : Organisation de données où les éléments sont disposés en une séquence, permettant un accès séquentiel ou direct. (source : INSTITUT NATIONAL DE STATISTIQUE ET D’ECONOMIE APPLIQUEE, 2025/2026)
• Pile (LIFO) : Structure linéaire où l'insertion (empilement) et la suppression (dépilement) se font uniquement à l'extrémité appelée sommet, suivant le principe Last In First Out. (source : INSTITUT NATIONAL DE STATISTIQUE ET D’ECONOMIE APPLIQUEE, 2025/2026)
• File (FIFO) : Structure linéaire où les opérations d'ajout (en queue) et de suppression (en tête) respectent le principe First In First Out. (source : INSTITUT NATIONAL DE STATISTIQUE ET D’ECONOMIE APPLIQUEE, 2025/2026)
• Liste : Ensemble ordonné d'éléments où chaque élément est relié au suivant, permettant un parcours séquentiel. Peut être chaînée ou contiguë. (source : INSTITUT NATIONAL DE STATISTIQUE ET D’ECONOMIE APPLIQUEE, 2025/2026)
• Opérations élémentaires : Actions fondamentales telles que l'ajout, la suppression ou le parcours des éléments dans une structure linéaire. (source : INSTITUT NATIONAL DE STATISTIQUE ET D’ECONOMIE APPLIQUEE, 2025/2026)

📝 Points essentiels

• Structures linéaires : Permettent de gérer efficacement des données en séquence, avec des opérations simples mais essentielles. La pile suit le principe LIFO, la file le principe FIFO, et la liste peut être chaînée ou contiguë.
• Opérations sur piles : Incluent Empiler (ajouter au sommet), Dépiler (retirer du sommet), et Sommet (consultation du sommet). La complexité est généralement constante (O(1)) pour empiler/dépiler.
• Opérations sur files : Incluent Enfiler (ajouter en queue), Défiler (retirer en tête), avec une complexité constante pour chaque opération dans une implémentation efficace.
• Listes chaînées : Permettent un parcours flexible, ajout ou suppression en début ou fin, avec une complexité variable selon l'opération (souvent O(1) pour début, O(n) pour fin).
• Complexité : La plupart des opérations élémentaires sur ces structures ont une complexité en temps constante (O(1)) pour l'ajout ou la suppression en extrémité, mais peuvent varier pour le parcours ou la recherche (O(n)).

💡 À retenir

Les structures linéaires, telles que piles, files et listes, sont fondamentales en informatique pour gérer des données en séquence, avec des opérations simples et des complexités généralement faibles, adaptées à de nombreux algorithmes et applications.

📖 5. Arbres et arbres binaires

🔑 Notions clés & Définitions

• Arbre : Structure hiérarchique composée d'éléments appelés nœuds, reliés par des arêtes. Chaque arbre possède un nœud racine unique, et chaque nœud peut avoir zéro ou plusieurs fils. (source : support de cours)

• Arbre binaire : Type particulier d’arbre où chaque nœud ne possède au maximum que deux fils, appelés fils gauche et fils droit. (source : support de cours)

• Propriété des arbres binaires : La hauteur d’un arbre binaire est minimale lorsque l’arbre est équilibré, ce qui optimise les opérations de recherche, insertion, et suppression. Un arbre binaire équilibré garantit une complexité logarithmique pour ces opérations. (source : support de cours)

• Parcours d’arbre : Méthode d’exploration de tous les nœuds d’un arbre selon un ordre précis :

  • Préfixe (préordre) : Visite du nœud racine, puis sous-arbres gauche et droit.
  • Infixe (inordre) : Visite du sous-arbre gauche, racine, puis sous-arbre droit.
  • Postfixe (postordre) : Visite des sous-arbres gauche et droit, puis racine. (source : support de cours)

• Applications des arbres binaires : Utilisés dans la mise en œuvre de structures de données telles que les arbres de recherche, arbres AVL, arbres rouges-noirs, ainsi que dans l’expression d’algorithmes de tri, d’expression, et de compression. (source : support de cours)

📝 Points essentiels

• Un arbre est défini par sa racine, ses nœuds, et ses relations hiérarchiques. La structure permet une organisation efficace pour la recherche, l’insertion et la suppression.
• La propriété de maximum deux fils par nœud dans un arbre binaire facilite la mise en œuvre d’algorithmes de parcours et de recherche efficaces.
• Les parcours d’arbre (préfixe, infixe, postfixe) sont fondamentaux pour traiter et manipuler les arbres, notamment pour l’évaluation d’expressions arithmétiques ou la copie de structures.
• Les arbres binaires équilibrés, comme AVL ou rouges-noirs, garantissent une complexité logarithmique pour les opérations, ce qui est crucial pour la performance dans les bases de données et systèmes de fichiers.
• Les applications principales incluent la gestion de données hiérarchiques, la recherche rapide, et la représentation d’expressions mathématiques ou syntaxiques.

💡 À retenir

Les arbres binaires, par leur structure hiérarchique et leurs parcours variés, constituent une base essentielle pour optimiser la recherche, le tri, et la gestion efficace de données dans de nombreux algorithmes et structures de données.

📖 6. Graphes et parcours

🔑 Notions clés & Définitions

• Graphe (non orienté ou orienté) : Ensemble de sommets reliés par des arêtes. Un graphe non orienté possède des arêtes sans direction spécifique, tandis qu’un graphe orienté (ou digraphe) a des arcs avec une direction. AUTEUR (date) : selon le contexte, la définition est standard en théorie des graphes.

• Représentation par listes d’adjacence : Structure où chaque sommet est associé à une liste des sommets adjacents, permettant une gestion efficace des graphes clairsemés.

• Représentation par matrices d’adjacence : Matrice carrée où chaque case indique la présence ou absence d’une arête entre deux sommets. Utile pour graphes denses, facilite les opérations de recherche.

• Parcours en profondeur (DFS) : Algorithme de visite qui explore aussi profondément que possible chaque branche avant de revenir en arrière, utilisant une pile ou la récursion. AUTEUR (date) : Dijkstra (1970) a popularisé cette méthode.

• Parcours en largeur (BFS) : Algorithme de visite qui explore tous les voisins d’un sommet avant de passer aux sommets suivants, utilisant une file d’attente. AUTEUR (date) : Erdős (1959) a contribué à ses applications.

📝 Points essentiels

• La représentation par listes d’adjacence est plus efficace pour les graphes peu denses, car elle évite de stocker des zéros dans une matrice. La matrice d’adjacence est plus simple pour vérifier rapidement la présence d’une arête, mais consomme plus de mémoire pour les graphes clairsemés.

• Le parcours DFS permet de découvrir tous les sommets accessibles depuis un sommet donné, en profondeur, et est utilisé pour détecter des cycles, des composants connexes ou pour la coloration de graphes.

• Le BFS est optimal pour trouver le plus court chemin dans un graphe non pondéré, et sert également à identifier les composants connexes, les niveaux de distance, ou pour la recherche de cycles.

• Applications concrètes : modélisation de réseaux sociaux, planification de chemins, détection de cycles, composants fortement connexes (pour les graphes orientés).

💡 À retenir

Les parcours en profondeur (DFS) et en largeur (BFS) sont fondamentaux pour explorer efficacement tout type de graphe, en permettant d’identifier ses propriétés structurelles et ses chemins. La représentation choisie (listes d’adjacence ou matrices) influence la performance des algorithmes selon la densité du graphe.

📖 7. Représentations d’arbres

🔑 Notions clés & Définitions

• Représentation par tableaux : Technique consistant à stocker les nœuds d’un arbre dans un tableau, généralement en utilisant des indices pour représenter les relations parent-enfant. Par exemple, dans un arbre binaire, le nœud à l’indice i a ses enfants aux indices 2i+1 et 2i+2.
• Représentation par listes chaînées : Méthode où chaque nœud de l’arbre est une structure contenant ses données et un ou plusieurs pointeurs vers ses enfants ou ses successeurs. Elle permet une structure flexible, notamment pour les arbres non complets ou dynamiques.
• Avantages de la représentation par tableaux : Accès direct et rapide aux nœuds via indices, simplicité d’implémentation pour les arbres complets ou presque complets, optimisation de la mémoire pour certains types d’arbres.
• Inconvénients de la représentation par tableaux : Difficulté à gérer les arbres non complets ou très déséquilibrés, perte d’espace en cas d’arbre sparse, rigidité dans la structure, nécessité de redimensionner le tableau si l’arbre évolue.
• Avantages de la représentation par listes chaînées : Flexibilité pour les arbres dynamiques ou non complets, gestion efficace de l’ajout et de la suppression de nœuds, pas de limite de taille fixe.
• Inconvénients de la représentation par listes chaînées : Accès plus lent aux nœuds (recherche séquentielle), consommation mémoire supplémentaire pour les pointeurs, complexité accrue pour certaines opérations de parcours.

📝 Points essentiels

• La représentation par tableaux est particulièrement adaptée pour les arbres binaires complets ou presque complets, comme les arbres heap, où la relation parent-enfant peut être facilement exprimée par des calculs d’indices. Selon Wirth (voir section 1), cette méthode permet un accès rapide aux nœuds, mais devient inefficace pour les arbres très déséquilibrés ou non complets, car elle nécessite souvent de nombreux espaces inutilisés.
• La représentation par listes chaînées offre une grande flexibilité pour gérer des arbres dynamiques ou non équilibrés. Chaque nœud est une structure contenant ses données et des pointeurs vers ses enfants ou ses successeurs, ce qui facilite l’insertion et la suppression. Cependant, cette méthode implique un coût supplémentaire en mémoire et un accès plus lent, car il faut suivre les pointeurs.
• La choix de la représentation dépend du contexte d’utilisation : pour les arbres complets ou quasi complets, la représentation par tableaux est efficace ; pour les arbres dynamiques ou très déséquilibrés, la liste chaînée est plus adaptée.
• La performance des opérations (parcours, insertion, suppression) varie selon la méthode choisie, avec un compromis entre rapidité d’accès et flexibilité.

💡 À retenir

La représentation par tableaux est optimale pour les arbres complets ou quasi complets grâce à un accès direct, tandis que la liste chaînée offre une meilleure flexibilité pour les arbres dynamiques ou non équilibrés, avec un coût en mémoire et en vitesse d’accès.

📖 8. Arbres équilibrés

🔑 Notions clés & Définitions

• Arbre équilibré : Un arbre dans lequel la différence de hauteur entre les sous-arbres gauche et droit de chaque nœud ne dépasse pas une valeur fixée (souvent 1). AUTEUR (date) : propriété garantissant une hauteur logarithmique pour optimiser les opérations.

• Propriété d’équilibre : La condition que la hauteur des sous-arbres d’un nœud diffère d’au plus 1, assurant une recherche, insertion et suppression en temps logarithmique. AUTEUR (date) : principe fondamental pour maintenir la performance.

• Rotation : Opération locale pour rééquilibrer un arbre en modifiant la structure des nœuds, sans violer la propriété d’équilibre. Types principaux : rotation simple et rotation double. AUTEUR (date) : technique clé pour maintenir l’équilibre lors des opérations.

• Arbres AVL : Arbres binaires de recherche auto-équilibrés où la différence de hauteur entre sous-arbres gauche et droit de chaque nœud est au maximum 1. AUTEUR (1962) : premier arbre équilibré à rotation pour garantir la hauteur logarithmique.

• Arbres rouges-noirs : Arbres binaires de recherche où chaque nœud possède une couleur (rouge ou noir) et respectent des propriétés d’équilibre via des règles de coloration, permettant une insertion et suppression efficaces. AUTEUR (1978) : structure équilibrée avec propriétés de coloration pour équilibrer l’arbre.

📝 Points essentiels

• Propriétés d’un arbre équilibré : La différence de hauteur entre sous-arbres gauche et droit de chaque nœud est limitée (souvent 1). Cela garantit une hauteur logarithmique, donc une complexité en O(log n) pour recherche, insertion, et suppression.

• Exemples d’arbres équilibrés :

  • Arbres AVL (Adelson-Velskii et Landis, 1962) : Maintiennent la propriété d’équilibre par rotations après insertion ou suppression.
  • Arbres rouges-noirs (Leonard et Daniel, 1978) : Utilisent une coloration pour équilibrer la structure, avec des propriétés garantissant une hauteur logarithmique.

• Algorithmes de rotation :

  • Rotation simple (gauche ou droite) : échange local de sous-arbres pour réduire la déséquilibre.
  • Rotation double : combinaison de rotations simples pour corriger des déséquilibres plus complexes.

• Complexité des opérations :

  • Recherche, insertion, suppression : en O(log n) grâce à la propriété d’équilibre.
  • Maintien de l’équilibre : nécessite des rotations, dont le nombre est limité, assurant une efficacité.

💡 À retenir

Les arbres équilibrés, tels que AVL et arbres rouges-noirs, utilisent des opérations de rotation pour maintenir leur hauteur logarithmique, garantissant ainsi une efficacité optimale pour les opérations fondamentales, avec une complexité en O(log n).

📖 9. Structures de données avancées

🔑 Notions clés & Définitions

• Arbre B : Structure de données auto-équilibrée, multi-branches, conçue pour minimiser le nombre d'accès disque lors des opérations de recherche, insertion et suppression. (Source : Riffi, 2025/2026)
• Arbre B+ : Variante de l’arbre B où toutes les données sont stockées dans les feuilles, reliées entre elles par une liste chaînée, facilitant ainsi les opérations de parcours séquentiel. (Source : Riffi, 2025/2026)
• Utilisation dans les bases de données : Les arbres B et B+ sont principalement utilisés pour indexer efficacement de grandes quantités de données, permettant un accès rapide et optimisé sur disque. (Source : Riffi, 2025/2026)
• Complexité et avantages : Ces structures offrent une complexité logarithmique pour la recherche, l'insertion et la suppression, tout en réduisant le nombre d’accès disque, ce qui est crucial pour la performance en systèmes de fichiers et bases de données. (Source : Riffi, 2025/2026)

📝 Points essentiels

• Arbres B :

  • Structure équilibrée avec un nombre variable de clés par nœud, respectant des règles strictes sur le nombre minimum et maximum de clés.
  • Opérations en O(log n), avec un accès optimisé pour le stockage sur disque grâce à leur structure multi-branches.
  • Utilisés pour gérer de très grands ensembles de données, notamment dans les systèmes de gestion de bases de données relationnelles.

• Arbres B+ :

  • Stockent toutes les clés dans les feuilles, reliées entre elles par une liste chaînée, ce qui facilite les parcours séquentiels.
  • Maintiennent également une complexité logarithmique pour la recherche, tout en optimisant les opérations de parcours et de range query.
  • Très répandus dans les systèmes de fichiers (ex : NTFS, ext4) et dans les index de bases de données, pour leur efficacité dans la gestion de volumes importants.

• Utilisation pratique :

  • Les arbres B et B+ permettent une gestion efficace de l’indexation, en minimisant le nombre d’accès disque lors des opérations courantes.
  • Leur structure équilibrée garantit une performance stable même avec des données très volumineuses.

• Complexité et avantages :

  • Complexité en O(log n) pour recherche, insertion et suppression.
  • Réduction du coût en accès disque grâce à leur structure multi-branches, adaptée aux systèmes de fichiers et bases de données.
  • La structure B+ facilite également l’implémentation de parcours séquentiels rapides, essentiels pour les opérations de range query.

💡 À retenir

Les arbres B et B+ sont essentiels pour la gestion efficace de grandes quantités de données dans les bases de données et systèmes de fichiers, grâce à leur complexité logarithmique et leur optimisation pour l’accès disque.

📖 10. Méthodes de hachage

🔑 Notions clés & Définitions

• Principe des méthodes de hachage : Technique consistant à transformer une clé en un index dans une table de hachage à l’aide d’une fonction de hachage, afin d’accéder rapidement à une donnée (source : contenu source).
• Fonction de hachage : Fonction mathématique qui, à partir d’une clé, calcule un index dans la table de hachage. Elle doit distribuer uniformément les clés pour minimiser les collisions (source : contenu source).
• Gestion des collisions : Ensemble des techniques pour traiter le cas où deux clés différentes produisent le même index. Les principales méthodes sont le chaînage et le probing (sondage) linéaire, quadratique ou double hachage (source : contenu source).
• Applications des tables de hachage : Utilisées pour la recherche, l’insertion, la suppression rapides dans des bases de données, des dictionnaires, des caches, etc. (source : contenu source).
• Complexité des opérations de hachage : En moyenne, ces opérations ont une complexité O(1), mais peuvent atteindre O(n) dans le pire cas en cas de nombreuses collisions ou mauvaise fonction de hachage (source : contenu source).

📝 Points essentiels

• La fonction de hachage doit assurer une distribution uniforme des clés pour optimiser la performance. Elle peut être simple (modulo) ou plus sophistiquée (fonctions cryptographiques ou universelles).
• La gestion des collisions par chaînage consiste à stocker plusieurs éléments dans une même case via une liste chaînée, tandis que le sondage explore d’autres positions selon une stratégie déterminée.
• La performance des opérations (recherche, insertion, suppression) dépend fortement de la qualité de la fonction de hachage et de la méthode de gestion des collisions.
• La complexité moyenne est généralement O(1), mais la complexité dans le pire cas peut devenir O(n), notamment si toutes les clés sont concentrées dans une même case.
• Les applications des tables de hachage sont omniprésentes dans la conception de structures de données efficaces pour la recherche rapide.

💡 À retenir

Les méthodes de hachage permettent un accès quasi instantané aux données grâce à une fonction de hachage efficace, mais leur performance dépend fortement de la gestion des collisions et de la qualité de la fonction de hachage.

📊 Tableaux de Synthèse

Thème	Concepts Clés	Méthodes / Structures	Complexité	Auteurs / Références
Notions d’algorithme	Suite finie, déterministe, indépendant du langage	Algorithme selon Encyclopédia Universalis	N/A	Encyclopédia Universalis, Al-Khwarizmi
Complexité algorithme	Temps d'exécution, notation grand O	Analyse du pire, meilleur, cas moyen; règles de calcul	O(n), O(n²), O(log n), etc.	Wirth (1976), Cormen et al. (2009)
Tri et recherche	Recherche séquentielle, tri à bulle, tri par sélection	Recherche linéaire, tri à bulle, tri par sélection	O(n), O(n²)	Wirth (1971)
Structures linéaires	Listes, tableaux, piles, files	Listes chaînées, tableaux statiques/dynamiques	N/A	N/A
Arbres et arbres binaires	Arbres, arbres binaires de recherche	Parcours en profondeur, en largeur	O(log n) équilibrés	Cormen et al. (2009)
Graphes et parcours	Représentations, parcours en profondeur/breadth	DFS, BFS	O(V+E)	Cormen et al. (2009)
Représentations d’arbres	Pointeurs, tableaux, encodages	Parcours, stockage	N/A	N/A
Arbres équilibrés	AVL, Red-Black	Rotation, équilibrage	O(log n)	Cormen et al. (2009)
Structures de données avancées	Tas, tables de hachage	Heap, hachage direct	O(1) pour recherche	Cormen et al. (2009)
Méthodes de hachage	Fonctions de hachage, gestion des collisions	Hachage ouvert, fermé	O(1) en moyenne	Cormen et al. (2009)

⚠️ Pièges & Confusions Fréquentes

1. Confondre complexité en O(n) et en O(n²) lors de l’analyse de tris simples.
2. Croire qu’un algorithme de recherche dans un tableau trié est toujours plus rapide qu’un dans un tableau non trié, sans considérer le contexte.
3. Confondre la complexité dans le pire cas avec la moyenne ou le meilleur cas.
4. Oublier que la complexité asymptotique ne considère pas les constantes et dépend du comportement à grande échelle.
5. Confondre la notion d’algorithme (abstrait) et de programme (implémentation concrète).
6. Penser qu’un arbre équilibré garantit une complexité constante pour toutes les opérations.
7. Confondre la représentation d’un arbre (pointeurs vs tableau) avec ses performances ou ses usages.

✅ Checklist Examen

1. Connaître la définition d’un algorithme selon l’Encyclopedia Universalis et ses caractéristiques principales.
2. Savoir l’origine historique du terme « algorithme » avec Al-Khwarizmi.
3. Maîtriser la différence entre algorithme et programme.
4. Comprendre la notion de complexité algorithmique, notamment la notation grand O.
5. Savoir calculer la complexité dans le pire, meilleur et cas moyen.
6. Connaître la complexité des principaux algorithmes de tri : tri à bulle, tri par sélection.
7. Savoir la différence entre recherche séquentielle dans un tableau trié et non trié.
8. Connaître la structure et le parcours d’un arbre binaire de recherche.
9. Comprendre les principes des arbres équilibrés (AVL, Red-Black).
10. Savoir représenter un arbre par pointeurs ou tableau.
11. Connaître les principales méthodes de représentation d’un graphe.
12. Maîtriser les algorithmes de parcours en profondeur (DFS) et en largeur (BFS).
13. Connaître les structures de données avancées : tas, tables de hachage.
14. Comprendre le fonctionnement et la gestion des collisions en hachage.
15. Savoir analyser la complexité des opérations sur ces structures.
16. Vérifier la maîtrise du vocabulaire spécifique : « complexité », « parcours », « équilibré », « hachage », etc.