Algorithmique Master 2 GSI
Cours,
Travaux Dirigés, Exam
Cours 1 : Introduction
à la conception et
l'expression d'algorithmes.
Analyse descendante, modularité.
Correction des algorithmes itératifs.
Invariants. Terminaison.
Correction des algorithmes récursifs. Existence et
unicité d'un point fixe.
Cours 2: Complexité
en temps et en espace d'un algorithme. Notion d'asymptotique.
Exemple des Tours de Hanoï et de la suite de Fibonacci.
Cours 3: Notion de type abstrait.
Structures séquentielles. Mise en oeuvre par des tableaux
et par des listes chaînées.
Cours 4: Les piles et les
files.
Application à la version itérative de la fonction
d'Ackerman.
Mise en oeuvre par des tableaux et par listes
chaînées. Introduction aux arbres.
Cours 5: Arbres
binaires. Type abstrait, parcours préfixe, postfixe,
infixe. Parcours
itératifs.
Valeur et bon parenthésage d'une expression
arithmétique.
Cours 6: Arbres
binaires de recherche. Taille, profondeur, longueur de
cheminements.
Arbre Binaires de Recherche aléatoires.
Estimation du coût moyen des recherches,
insertions, suppressions.
Cours 7: Arbres
quelconques. Parcours, recherche et adjonction d'un
élément. Impression.
Mise en oeuvre en Java.
Cours
8: Graphes. Notions fondamentales,
représentations, mise en oeuvre en Java.
Cours
9: Graphes. Parcours en
profondeur. Complexité et preuves de corrections.
Mise en oeuvre en Java.
Cours 10: Parcours en largeur.Tri
topologique.
Travaux
Dirigés
TD1-2-3
Fondements : sur des exemples simples, notions de correction, de
complexité,
de programmation dynamique,
recherche dichotomique. ps, pdf.
TD 4-5 Exemple de programmation dynamique :
Calcul de la plus longue sous-suite commune à deux suites.
ps, pdf.
TD 6-7 Arbres Binaires de Recherche :
Parcours, insertion, suppression. Mise en oeuvre en Java.
TD 8-9 Pratique des listes et des arbres
quelconques: Tri de mots en parties communes. ps, pdf.
TD 10 Recherche de plus courts chemins dans
un graphe valué. L'algorithme de Dijkstra. ps, pdf
Examen
Tri par Tas ps, pdf.