^{PDFprof.com Search Engine}

L3 Info Cours 3 : preuve d'algorithmes

Comment prouver un algorithme ?
Pour prouver la validité d'un algorithme, il faut chercher un invariant de boucle, c'est-à-dire un prédicat de certaines variables de l'algorithme qui en font une proposition vraie à chaque entrée dans la boucle.
Quelles sont les 3 grandes phases d'un algorithme ?
Définition : Un algorithme comprend ensuite trois phases : Une phase d'initialisation ou d'entrée qui permet de donner une valeur initiale aux variables.
Une phase de traitement du problème.
Une phase de sortie des résultats. 2.
0) Instructions d'entrées et de sortie.
Comment savoir le coût d'un algorithme ?
Le calcul du coût d'un algorithme s'obtient donc en composant les coûts des différentes opérations composant l'algorithme.
On écrit f = O(g) pour f ∈ O(g).
On dit que g est une borne supérieure asymptotique pour f .
Un programme exprime un algorithme dans un langage de programmation particulier, ce programme peut être exécuté par un ordinateur.
Un algorithme se compose de trois parties : le nom de l'algorithme, la partie déclaration et la partie traitement.

Comment prouver un algorithme ?