Complexité, Tris ...
L'optimisation par colonies de fourmis (Ant Colony Optimization, ACO) est une métaheuristique inspirée du comportement des fourmis réelles pour trouver le plus court chemin entre leur nid et une source de nourriture. Développée par Marco Dorigo dans sa thèse en 1992, cette méthode est particulièrement efficace pour les problèmes d'optimisation combinatoire.
Le recuit simulé est une métaheuristique d'optimisation inspirée d'un phénomène physique : le recuit des métaux. Ce processus consiste à chauffer un matériau puis à le refroidir lentement pour réduire ses défauts et améliorer sa structure cristalline.
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.