Dans ce cours, on étudie des algorithmes et des structures de
données, ainsi que les techniques qui permettent de raisonner sur
les algorithmes.
Il s'agit notamment de savoir justifier qu'un algorithme répond
correctement à un problème posé, ou de prédire le temps d'exécution
d'un programme.
Le cours mélange donc des aspects mathématiques et algorithmiques,
et vise à la fois à vous faire découvrir des structures de données
et algorithmes fondamentaux en informatique et à affûter vos
capacités de raisonnement.
Notes de cours
- Première partie : techniques de base [ .pdf ]
- Deuxième partie : graphes [ .pdf ]
- Intermède : jeux [ .pdf ]
- Troisième partie : arbres [ ch. 8 | ch. 9 | ch. 10 | ch. 11 | ch. 12 ]
- Dernier cours : révisions [ Cloture transitive | Fusion d'ABR ]
Archives
- Partiel 2022 [ énoncé corrigé ]
- Examen 2022 [ énoncé corrigé ]
Programme
| Première période. | ||
| Semaine | Cours | TD |
|---|---|---|
| 12/01 | 1. Chercher | |
| 16/01 | 2. Trier | 1. Invariants [ énoncé | correction ] |
| 23/01 | 3. Accélerer | 2. Complexité [ énoncé | correction ] |
| 30/01 | 4. Répartir | 3. Récursion [ énoncé | correction ] |
| 06/02 | 5. Ordonner | 4. Graphes [ énoncé | correction ] |
| 13/02 | 6. Explorer | 5. Parcours [ énoncé | correction ] |
| 20/02 | 7. Gagner | 6. Terminaison [ énoncé | correction ] |
| 27/02 | Vacances | |
| 06/03 | Partiel | |
| Deuxième période. | ||
| Semaine | Cours | TD |
| 13/03 | 8. Recommencer | 7. Listes [ énoncé | correction ] |
| 20/03 | 9. Ranger | TP1. Arbres binaires
[ énoncé Info ] TP1. Variante java [ énoncé MNSI ] [ corrigé caml ] |
| 27/03 | 10. Prioriser | 9. Arbres binaires [ énoncé | correction ] |
| 03/04 | 11. Résoudre | TP2. Arbres de syntaxe
[ énoncé Info ] TP2. Variante java [ énoncé MNSI ] [ corrigé caml ] |
| 10/04 | TP3/DM. Compression de Huffman
[ énoncé Info ] TP3/DM. Variante java [ énoncé MNSI ] [ corrigé caml | corrigé java ] |
|
| 17/04 | 12. Se perdre | TD12. Composantes connexes [ énoncé | corrigé ] |
| 24/04 | Révisions | |