Apprenez le développement informatique à votre rythme.
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.
Chemin Un chemin est une chaîne sans répétition de sommets. Chemin élémentaire : Aucun sommet n'est répété (implique qu'aucune arête n'est répétée).
De nombreux problèmes rencontrés en mathématiques, en informatique et en ingénierie ont une caractéristique commune : ils mettent en jeu des objets entre lesquels existent des relations. Un graphe ne cherche pas à modéliser la nature des objets, mais la manière dont ils sont reliés.
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.