| Francesca Fiorenzi
|
Ingénieurs réseaux 1ère
année : Cours d'Algorithmique 1 et 2
-
Programme du cours : Notions fondamentales de l'algorithme. Types
abstraits. Notions de preuve de programme. Récursion et itération
; leur équivalence. Introduction à l'analyse de la complexité des
algorithmes.
Structures de données fondamentales (on décrit les
principaux opérateurs de base associés). Listes : listes en tableaux
et listes chaînées par pointeurs, listes doublement chaînées. Arbres
: parcours d'arbres dans l'ordre préfixe, infixe, suffixe. Piles et
files (ou queues). Ensembles et algorithmes de recherche. Méthodes
élémentaires : recherche dichotomique, listes ordonnées. Hachage :
hachage fermé et hachage ouvert, méthodes de rehachage, évaluation
moyenne. Arbres binaires de recherche : évaluation du coût de
l'insertion.
Algorithmes de tri (on fait un choix parmi les très
nombreux algorithmes de tri pour présenter les idées principales et
comparer l'efficacité des différentes méthodes). Schémas élémentaires
: tri par insertion, sélection, bulle. Tri rapide, évaluation en
moyenne. Tri fusion, évaluation dans le pire des cas.
-
Polycopié de Maxime
Crochemore
Algorithmique 1
Algoritmique 2
|