Algorithmique 1
Objectifs
- Savoir proposer et écrire des algorithmes pour résoudre des problèmes difficiles
- Savoir analyser un algorithme : complexité temporelle, preuve de correction, preuve de terminaison
- Savoir écrire un algorithme récursif et analyser sa complexité
- Maîtriser les algorithmes classiques de tri sur les tableaux d’entiers
- Maîtriser les algorithmes classiques de parcours sur des arbres
Plan du cours
- Intérêt et notations de pseudo-code
- Complexité temporelle
- Preuves d'algorithme : correction, terminaison
- Récursivité
- Structure de données : introduction aux types de données abstraits, pile, file, arbres
- Algorithmes classiques de tri : par insertion, par sélection, rapide, fusion
Description des TP
10,5 h CM et 19,5h TDs, pas de TP
Connaissances requises
- Ecriture d'algorithmes de base en Python (utilisation de variables, de fonctions, de listes, instructions if, for, while, …), vus au Semestre 1
- (hors PEIP) Acquis de l'EC Programmation en C au S2 : Ecriture d'algorithmes classiques sur les tableaux en C (calcul d'une somme, d'un maximum, recherche d'un élément, ….). Notions de structures et de pointeurs.
RSE (Responsabilité Sociale et Environnementale)
Bibliographie
Introduction à l'algorithmique, T. Cormen, C. Leiserson, R. Rivest, 1996