UE Algorithmique et Modélisation – L3 INFO – UE GINF 363 – Année 2023/2024
Table of Contents
- 1. Équipe pédagogique et organisation
- 2. Consignes
- 3. Objectif
- 4. Planning (provisoire, les liens pointent sur les ressources de 2023)
- 4.1. Semaine 15/01 Énumération
- 4.2. Semaine 22/01 Programmation dynamique
- 4.3. Semaine 29/01 Tables de hachage
- 4.4. Semaine 05/02 Analyse en moyenne
- 4.5. Semaine 12/02 Randomisation
- 4.6. Semaine 19/02 Diviser pour régner
- 4.7. Semaine 04/03 Chemins et graphes
- 4.8. Semaine 11/03 Plus court chemin d'origine donnée
- 4.9. Semaine 18/03 Représentation algébrique des graphes
- 4.10. Semaine 25/03 Graphes et optimalité
- 4.11. Semaine 1/04
- 5. Anciens sujets
- 6. Évaluation
- 7. Bibliographie commentée
1 Équipe pédagogique et organisation
- Cours : Jean-Marc Vincent
- TD1 : Fanny Dufossé (coordination des TD1), Maxime Lesourd et Jean-Marc Vincent
- TD2 : Florent Bouchez-Tichadou, Cyril Labbé (coordination des TD2 et des Apnees) et Jolahn Vaudey
Réunion pédagogique hebdomadaire de l'équipe à définir)
Les salles sont à vérifier sur ADE (qui fait foi)
- Cours : Mercredi 8h00 - 9h30 Jean-Marc Vincent
- Groupe 1
- TD1 Lundi 13h30-15h Jean-Marc Vincent
- TD2 Jeudi 8h-9h30 Florent Bouchez-Tichadou
- Groupe 2
- TD1 Lundi 13h30-15h Fanny Dufossé
- TD2 Jeudi 8h-9h30 Cyril Labbé
- Groupe 3
- TD1 Mardi 13h30-15h Maxime Lesourd
- TD2 Mercredi 9h45-11h15 Jolahn Vaudey
- Apnees : Mercredi et/ou vendredi après-midi (voir ADE)
2 Consignes
Les mails concernant
- cours/examens…: Jean-Marc Vincent
- les TD1 : Fanny Dufossé ou Maxime Lesourd ou Jean-Marc Vincent
- les TD2 et les Apnées : Florent Bouchez-Tichadou, Cyril Labbé ou Jolahn Vaudey
Le sujet du mail doit être explicite avec
- SUJET : [L3INFO:ALGO6] Cours/TD1/TD2/Apnée sujet du mail
- Vous devez envoyer votre mail avec votre adresse officielle e.univ-grenoble-alpes.fr
- toute adresse de provenance différente risque d'être "grey/black-listée" et d'atterrir dans une poubelle
- le mail officiel de la L3-INFO est la liste etu-2022-im2ag-gbl3ig211@univ-grenoble-alpes.fr toute annonce officielle (quicks, apnées, déplacements de créneaux horaires,…) passera par ce mail (que vous devez lire quotidiennement)
APNEES les sujets et rendus sont sur le moodle de l'Ufr. Pour chaque APNEE, un lien vers le sujet est mis sur cette page à titre indicatif. En cas de difficulté vous devez contacter tous les trois chargés de TD2 au plus vite, toute réclamation doit être faite dans le quart d'heure après le démarrage de l'apnee pour être recevable
3 Objectif
Savoir rattacher un problème à une classe de problèmes, en déduire une approche adaptée pour sa résolution, valider la correction de la solution proposée, et en analyser sa complexité.
Cet objectif est atteint par une approche selon trois plans (ou points de vue) :
- raisonnement informel mais rigoureux, liant la réalisation d'un algorithme à ses spécifications, raffinement d'un schéma d'algorithme vers une réalisation particulière ;
- méthodes classiques de résolution dont le critère principal est la complexité (algorithmes gloutons, diviser pour régner, programmation dynamique…) ;
- types de problèmes classiques (parcours de graphe, énumération d'un ensemble de candidats…), et comment l'expression d'une solution (itérative, récursive) est liée à la structure sous-jacente.
4 Planning (provisoire, les liens pointent sur les ressources de 2023)
4.1 Semaine 15/01 Énumération
4.2 Semaine 22/01 Programmation dynamique
4.3 Semaine 29/01 Tables de hachage
4.4 Semaine 05/02 Analyse en moyenne
4.5 Semaine 12/02 Randomisation
4.6 Semaine 19/02 Diviser pour régner
4.7 Semaine 04/03 Chemins et graphes
- TD1 : Le facteur TD1-7
- Cours : Cruches, graphes et chemins Chemins Notations lexique
- TD2 : Au pays des amphipodes
- APNEE : Vendredi
4.8 Semaine 11/03 Plus court chemin d'origine donnée
- TD1 : Composantes connexes TD
- Cours : Plus courts chemins algorithme de Dijkstra Arbre des chemins Algorithme de Pledge sur le site Interstice Labyrinthes
- TD2 : Présentation APP Sokoban (Livret)
- APNEE : Vendredi (page Moodle APP Sokoban)
4.9 Semaine 18/03 Représentation algébrique des graphes
- TD1 : Chemins et programmation dynamique TD
- Cours : Approche algébrique de calcul des plus courts chemins transparents
- TD2 : Travail APP Sokoban
- APNEE : Mercredi
- Quick : Vendredi
4.10 Semaine 25/03 Graphes et optimalité
- TD1 : Algorithme A-star TD
- Cours : Point fixes, chemins et circuits transparents rappel A-star
- TD2 : Travail APP Sokoban
4.11 Semaine 1/04
- TD1 : lundi de Pâques report au 08/04 : révisions
- Cours : Configurations, jeux et stratégies, arbres and/or
- Td2 : Travail APP Sokoban préparation de la démo
- APNEEs : Mercredi (APP Sokoban) et Vendredi : démonstration Sokoban
5 Anciens sujets
Attention, le programme ayant changé, tous les exercices des quick 1 et quick2 ne sont pas faisables et certains exercices du quick 2 ou des examens sont accessibles
Année | Quick 1 | Quick 2 | Examen |
---|---|---|---|
2024 | Q1-24 | Q2-24 | |
Q1-hint-24 | |||
2023 | Q1-23 | Q2-23 | E-23 |
2022 | Q1-22 | Q2-22 | E-22 |
Q1-hint-22 | Q2-hint-22 | ||
2021 | Q1-21 | E-21 | |
Q1-hint-21 | |||
2020 | Q1-2020 | E-20 | |
Q1-hint-20 | |||
2019 | Q1-19 | E-19 | |
Q1-hint-19 | |||
2018 | Q1-18 | E-18 | |
Q1-hint-18 | |||
2017 | Q1-17 | E-17 | |
Q1-hint-17 | |||
2016 | Q1-16 | E-16 | |
Q1-hint-16 | |||
2015 | Q2-15 | E-15 | |
Q2-hint-15 |
6 Évaluation
Conformément au règlement d'examen (qui fait foi)
7 Bibliographie commentée
7.1 Ouvrage à lire, travailler impérativement
Algorithmique Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Dunod, 2010.
Ouvrage de référence internationale en algorithmique. Très pédagogique il peut être utilisé en autoformation, lorsque les bases sont acquises. Couvre l’ensemble du cours. L'ouvrage est cité comme [CLRS] dans la page
Algorithms (en anglais) Robert Sedgewick and Kevin Wayne. Addison Wesley, 2011.
Une approche thématique permettant de reprendre les différents et paradigmes de l’algorithmique. La présentation est soignée, les détails des implémentations en Java sont très utiles. Des versions précédentes en français : Robert Sedgewick Algorithmes en C ou Algorithmes en Java chez Dunod
7.2 Ouvrages plus avancés
The Design and Analysis of Algorithms Dexter C. Kozen Springer, 1991.
Excellent ouvrage pour de l’algorithmique avancée. Présenté sous forme de séquence de lectures "indépendantes" il va directement à l’essentiel. Les principes algorithmiques sont ainsi mis en valeur.
Algorithmics : The Spirit of Computing David Harel and Yishai Feldman Addison Wesley, 2004.
Orienté méthodologie, cet ouvrage propose une vue transversale en abordant successivement, méthode et analyse, limitations et robustesse, extensibilité… intéressant pour le recul pris.
Introduction à l’analyse des algorithmes Robert Sedgewick and Philippe Flajolet Addison Wesley 1995
Ouvrage théorique sur l’analyse de la complexité des algorithmes. Assez difficile d'accès, mais les fondements sont clairs et les méthodes efficaces
Randomized Algorithms, R. Motwani and P. Raghavan, Cambridge University Press, 1995.
Ouvrage de référence sur le sujet, on ne fait qu'aborder la thématique dans le cours.
7.3 Ouvrages historiques (et toujours de référence)
The Art of Computer Programming, Vol 1-4 Donald E. Knuth, Addison-Wesley, 1998.
Ouvrage historique et encore d’actualité pour la conception et l’analyse d’algorithmes
Data Structures and Algorithms Alfred V. Aho, J.E. Hopcroft, et Jeffrey D. Ullman Addison Wesley 1983
Ouvrage de référence proche de l'implantation sur machine
Histoires d’algorithmes Jean-Luc Chabert et al. Belin 2010
Une histoire des algorithmes avec un point de vue calcul et calcul numérique