Complexité, Tris ...
Une heuristique est une méthode de résolution basée sur des règles empiriques, des approximations ou des connaissances spécifiques du problème, visant à produire rapidement une solution acceptable, sans garantie d'optimalité.
Une entreprise développe un correcteur orthographique intelligent pour une suite bureautique. Le système doit détecter les fautes de frappe, suggérer des corrections, analyser la similarité entre documents et construire un index de recherche approximative. Le cœur du système repose sur la distance d'édition (distance de Levenshtein), qui mesure le nombre minimal d'opérations élémentaires (insertion, suppression, substitution) pour transformer un mot en un autre.
La preuve d'algorithme est une démonstration mathématique qu'un algorithme produit le résultat attendu pour toutes les entrées valides et qu'il se termine effectivement.
L'analyse des fonctions récursives repose sur l'établissement et la résolution de relations de récurrence. Cas de base : condition d'arrêt de la récursion. Relation de récurrence : exprime \(T(n)\) en fonction de \(T\) pour des entrées plus petites.
La méthode de comptage des pas est une technique systématique pour analyser la complexité temporelle d'un algorithme : On identifie les instructions élémentaires et on compte leur nombre d'exécutions.
Lorsqu'on analyse un algorithme, on s'intéresse à deux ressources fondamentales : le temps et l'espace mémoire. Ces deux mesures permettent d'évaluer l'efficacité d'un algorithme et de comparer différentes solutions pour un même problème.
Une variante de boucle (ou fonction de terminaison) est une expression associée à une boucle qui possède les propriétés suivantes : Elle est évaluée à une valeur entière positive ou nulle. Sa valeur décroît strictement à chaque itération de la boucle. Elle fournit une borne inférieure garantissant que la boucle ne peut pas s'exécuter indéfiniment.
La coloration des graphes consiste à attribuer des couleurs à certains éléments d'un graphe (sommets ou arêtes) en respectant des contraintes d'adjacence.
L'algorithme A* ne se contente pas de regarder le chemin parcouru ; il projette également l'effort restant. C'est un algorithme best-first search (recherche du meilleur d'abord).
La recherche linéaire (ou recherche séquentielle) est l'algorithme de recherche le plus simple. Elle consiste à parcourir un tableau élément par élément jusqu'à trouver la valeur recherchée ou atteindre la fin du tableau.
Tri rapide Le tri rapide (Quicksort) est un algorithme de tri basé sur le paradigme Diviser pour régner, proposé par C.A.R. Hoare en 1959. C'est l'un des algorithmes de tri les plus utilisés en pratique grâce à ses excellentes performances en moyenne.
Problème du tri Étant donné un tableau T[0..n-1] de n éléments comparables, trier consiste à réorganiser les éléments de façon à obtenir T[0] ≤ T[1] ≤ … ≤ T[n-1]. Les trois algorithmes présentés ici sont dits élémentaires : simples à comprendre et à implémenter, mais de complexité O(n^2) dans le pire cas — à utiliser sur de petits tableaux ou comme base pédagogique.