Algorithmique en licence Mathématiques-Informatique en 2008/2009
- Présentation
- Cours n° 1 : introduction à
l'algorithmique
- Notion d'algorithme
- modélisation mathématique et méthode abstraite de résolution
- structures de données abstraites et algorithme générique
- implémentation dans un langage
- Preuve de programmes
- Complexité d'algorithmes
- en espace et en temps
- dans le cas le pire et en moyenne
- Exemple du tri à bulles
- Cours n° 2 :
recherche d'un motif dans un texte
- Algorithme naïf
- Algorithme de Morris et Pratt
- Cours n° 3 :
recherche d'un motif dans un texte
(suite)
- Algorithme de Knuth, Morris et Pratt
- Algorithme de Boyer et Moore
- Cours n° 4 : Parcours
d'arbres
- arbres
- définition
- terminologie : racine, nœud, nœud interne, feuille,
père, fils, hauteur, branche, sous-arbre
- définition récursive des arbres
- implémentations
- arbres binaires et binarisation d'un arbre quelconque
- définition des parcours en largeur, préfixe, infixe et suffixe
- implémentation avec une file du parcours en largeur
- liens entre le parcours global de l'arbre et les parcours
préfixe, infixe et suffixe
- Programmation
des parcours en profondeur
- de manière récursive
- de manière itérative
- Cours n° 5 :
arbres rouges et noirs
- Rappels sur les arbres binaires de
recherches
- définition d'un arbre binaire de recherche
- recherche d'un élément dans un arbre de binaire de recherche
- insertion d'un élément
- recherche du successeur d'un élément
- suppression d'un élément
- Arbres rouges et noirs
- définition
- hauteur d'un arbre rouge et noir
- rotations
- insertion d'un élément
- suppression d'un élément
- Cours n° 6 : graphes
- Définitions et terminologie
- graphes orientés ou non
- chemin, cycle
- Représentations
- représentation par matrice d'adjacence
- représentation par liste d'adjacence
- Parcours en largeur
- Cours n° 7 : parcours en profondeur dans un graphe
- Parcours en profondeur
- Détection des cycles
- Tri topologique d'un graphe acyclique
- Cours n° 8 : composantes fortement connexes
- Composantes fortement connexes et graphe induit
- Calcul des composantes fortement connexes
- graphes non-orientés
- algorithme de Tarjan pour les graphes orientés
- Cours n° 9 : plus courts chemins à origine unique
- Relâchement
- Algorithme de Bellman-Ford
- Algorithme de Dijkstra
- Cours n° 10 : problème de flots dans un graphe
- Présentation du problème sur un exemple
- Définitions
- capacité
- flot dans un graphe
- capacité résiduelle et graphe résiduel
- chemin d'augmentation
- Algorithme de Ford-Fulkerson
- Théorème flot maximal/coupe minimale
- Algorithme d'Edmonds-Karp
- Cours n° 11 : transformée de Fourier rapide
- algorithme récursif
- algorithme intératif
- mutiplication de polynômes
- mutiplication de grands entiers
- Rattrapage jeudi 25 juin de 9h30 à 12h30 en salle 380F