IN-202-Cours

IN202 - AlgorithmiqueNotes de CoursLaurent CanetLe 8 juin 2002Table des mati`eres1 Syst`eme formel de preuve de programme de O’Hare 31.1 R`egles et axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Construction de programmes sur invariant . . . . . . . . . . . . . . . 41.2.1 Exemple : somme des ´el´ements d’un tableau . . . . . . . . . . 52 Probl`emes de recherches 62.1 Remarques sur l’´evaluation de complexit´e d’un programme . . . . . . 62.2 Recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.1 Code Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2.2 Complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Recherche s´equentielle . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3.1 Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3.2 Complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.4 Recherche arri`ere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4.1 Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4.2 Complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Tris 113.1 Slowsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.1.1 Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.1.2 Complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . ...