Algorithmique en licence Mathématiques-Informatique en 2007/2008
- 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 : listes, piles, files et arbres
- Listes
- listes simplement chaînées et doublement chaînées
- implémentation des opérations de base : ajout et suppression
d'un élément
- Piles et files
- opérations élémentaires : interface Java
- implémentation par tableaux et par listes
- Une implémentation
simpliste des listes, piles et files.
- 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
- Cours n° 5 : Parcours
d'arbres
- 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° 6 :
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° 7 : 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° 8 : parcours en profondeur dans un graphe
- Parcours en profondeur
- Détection des cycles
- Tri topologique d'un graphe acyclique
- Cours n° 9 : 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° 10 : transformée de Fourier rapide
- algorithme récursif
- algorithme intératif
- mutiplication de polynômes
- mutiplication de grands entiers
- Cours n° 10 et 11 annulés en raison des blocages de l'université