[ Aymeric Vincent's home page ]
Algorithmes et structures de données
Cours d'introduction à l'algorithmique dispensé en filière électronique (IF109).
Cours
| Séance 1 |
15 septembre 2010, 13h50-15h10 |
-
Présentation
-
8 séances de cours, 5 séances de travaux dirigés
-
Rappel : architecture très simplifiée d'un ordinateur (CPU,
Mémoire)
-
Notion d'algorithme
-
Notion de problème
-
Exemple d'algorithme : calcul du PGCD par l'algorithme d'Euclide
-
Syntaxe du langage algorithmique utilisé
-
Lien entre problème, algorithme, et programme
-
Syntaxe d'utilisation des tableaux
-
Exemple : chercher le max dans un tableau d'entiers
| Séance 2 |
17 septembre 2010, 13h50-15h10 |
-
Algorithme de tri par sélection
-
Notions de complexité (constante, linéaire, quadratique,
exponentielle)
-
Récursivité
-
Calcul récursif de la mise à la puissance
| Séance 3 |
20 septembre 2010, 15h20-16h40 |
-
Version itérative du calcul de la mise à la puissance
-
Version optimisée du calcul de la mise à la puissance
-
Tri par fusion avec copies
| Séance 4 |
28 septembre 2010, 8h-9h20 |
-
Deuxième version du tri fusion
-
Notion d'arbre des appels
-
Utilisation de moins de mémoire
| Séance 5 |
30 septembre 2010, 15h20-16h40 |
-
Structures de données
-
Exemples : tableau, liste chainée
-
Notion d'allocation mémoire
-
Listes chainées
-
Notion de type abstrait de données
| Séance 6 |
8 octobre 2010, 13h50-15h10 |
-
Style impératif, style fonctionnel
-
Piles
-
Utilisation d'une pile pour évaluer des expressions préfixes
| Séance 7 |
15 octobre 2010, 13h50-15h10 |
-
Files
-
Type abstrait de données
-
Implémentation par listes, buffer circulaire
-
Notion d'arbre
-
Arbres binaires de recherche
-
Insertion, suppression
-
Equilibrage
| Séance 8 |
21 octobre 2010, 11h-12h20 |
Travaux dirigés
Liens
Bibliographie
- Introduction à l'algorithmique, Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest, Dunod, 1994, ou
- Introduction à l'algorithmique, 2ème édition, Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Dunod, 2002