Algorithmique avancée#
M1 Informatique pour la Science des Données, Université Paris-Saclay, Faculté d’Orsay
«L’objectif de ce cours est de fournir des outils et techniques algorithmiques de pointe aux apprentis. Étude de l’algorithmique sur les graphes (plus courts chemins, tri topologique, …), les techniques de mémorisation, de programmation dynamique et de backtracking. Présentation de la notion de flots et des algorithmes de calcul de flot maximal. Enfin, les thèmes des algorithmes online et approchés seront abordés.»
Enseignants#
Florent Hivert (pas cette année)
Viviane Pons (pas cette année)
Vue d’ensemble#
Les notions du cours seront abordées par la pratique, tout d’abord par l’implantation de structures de données de graphes, puis leur utilisation pour résoudre quatre problèmes.
Structures de données pour les graphes#
#
Problème 1: Le chemin le plus rapide en métro de Montgallet à Billancourt ?
Problème 2: Rush Hour#
La voiture rouge est coincée dans un embouteillage; comment déplacer les véhicules pour la faire sortir? Ci-dessous le défi 1. Saurez-vous faire résoudre par l’ordinateur le défi 40 en un nombre minimum du coups?
Problème 3: Faire passer le maximum de courant#
Problème 4: Fabriquer et résoudre des labyrinthes#
Planning#
7 séances de 3h: Cours + TD + TP intégré
Graphes: structures de données, terminologie, plus courts chemins#
2026-03-19 jeu. 09:00-12:15 B210
2026-03-24 mar. 09:00-12:15 B211
Réseaux et flots#
2026-03-26 jeu. 13:30-16:45 B210
2026-03-31 mar. 08:00-11:15 B211
2026-04-02 jeu. 08:00-11:15 B210
Arbres couvrants#
2026-05-07 jeu. 08:00-10:15 B210
2026-05-11 lun. 09:00-11:15 B210
Examen#
2026-05-22 jeu. 13:30-16:45
Modalités d’évaluation#
L’évaluation se fera sur vos TPs, évalués à l’oral (CC), ainsi que sur un examen (ET1 / ET2)
Session 1 : 1/3 CC + 2/3 ET1
Session 2 : 1/3 CC + 2/3 ET2
Annales#
Du bon usage des aides#
Attention
Vous avez à disposition de multiples aides: enseignant, solutions en ligne, collègues, copains, famille, robots conversationnels, etc.
Vous êtes responsables de votre progression, à vous de les utiliser à bon escient.
Nos conseils
Les exercices de ce cours sont à réaliser par vous-même pour qu’ils soient utiles à votre progression. Copier ou simplement adapter une solution existante ne vous apportera pas grand chose.
Si, après un temps de réflexion personnelle approfondie, vous ne voyez pas comment avancer, alors n’hésitez pas à demander des indications à vos aides.
Si vous vous adressez à un robot conversationnel, soyez précis dans votre invite (prompt): «Vous êtes un enseignant bienveillant d’un cours de master d’algorithmique de graphes. Je dois résoudre l’exercice suivant: … J’ai essayé … Sans me donner la solution, pourriez vous me donner une indication sur comment avancer à partir de là?»Vous pouvez aussi utiliser vos aides pour discuter vos solutions aux exercices.
Privilégiez les conversations avec des humains; elles sont plus fécondes qu’avec un robot.
Vous êtes aussi responsable de votre impact environnemental
Évaluation des TPs
Vous ne serez pas évalués sur vos rendus de TP, mais lors de deux ou trois mini-oraux portant sur le thème des TPs.
Motivation:
Vous inciter à comprendre les TPs plus qu’à les remplir.
Consacrer mon temps de correction des TPs à des dialogues individuel féconds, plutôt qu’à faire le flic et compter des points derrière mon ordi.
Vous faire remémorer vos TPs après la fin de ceux-ci, pour aider à ancrer les apprentissages sur le plus long terme.
Environnement de travail#
Langage de programmation: Python 3
Bibliothèques: networkx + matplotlib + …
Environnement interactif: Jupyter
Environnement virtuel: myDocker (optionnel)
Forge logicielle: GitLab
Robot conversationnel: basé sur LLM llama; souverain et loyal (sur myDocker; optionnel)
Dans cette section, nous expliquons:
Comment accéder aux logiciels requis
Comment télécharger et déposer vos devoirs
Les instructions font l’hypothèse que vous travaillerez sur ce cours dans votre
répertoire ~/M1-ISD/AlgorithmiqueAvancee. Vous pouvez choisir un autre nom.
Accéder aux logiciels requis#
Ce cours utilise Python, Jupyter et quelques bibliothèques classiques (voir le fichier pyproject.toml, ainsi que quelques paquets Python plus ou moins maison.
Utilisation des logiciels en ligne (recommandé)
L’université Paris-Saclay mets à votre disposition un service sur lequel sont installés tous les logiciels requis. Vous pouvez vous identifier avec vos identifiants usuels de l’université (Adonis).
Ouvrez le tableau de bord du cours
Installation en local de l’environnement de travail (optionnel)
Alternativement, vous pouvez installer les logiciels sur votre machine et travailler en local.
Instructions d’installation avec uv
Si vous ne l’avez pas déjà fait, installez le gestionnaire d’environnements uv.
Si vous ne l’avez pas déjà fait, téléchargez la «salle de TP virtuelle» :
git clone https://gitlab.dsi.universite-paris-saclay.fr/M1InfoISDAlgorithmiqueAvancee/ComputerLab.git ~/M1-ISD/AlgorithmiqueAvancee
Allez dans le dossier contenant le matériel pédagogique et lancez JupyterLab. Les logiciels requis seront automatiquement installés dans ce dossier.
cd ~/M1-ISD/AlgorithmiqueAvancee uv run jupyter lab tableau_de_bord.md
La liste des logiciels pourra être mise à jour en en cours de semestre. Dans ce cas:
cd ~/M1-ISD/AlgorithmiqueAvancee/binder
git pull
uv sync
Télécharger et déposer les devoirs#
Le matériel pédagogique de ce cours est réparti sous la forme de devoirs que vous
téléchargerez depuis le tableau de bord. Par exemple, lors de la première séance, vous
téléchargerez le devoir 1-StructuresDeDonnees et suivrez les instructions dans les
feuilles successives README.md, 00-*.md, 01-*.md, … ainsi que Rapport.md.
Depuis le tableau de bord, vous pouvez déposer votre travail aussi souvent que vous le souhaitez. Cela permet d’en avoir une sauvegarde et de le rendre disponible à vos enseignants et éventuellement votre binôme.
Depuis le tableau de bord, vous pouvez aussi accéder au devoir et à votre dépôt, par exemple pour en consulter l’historique.
Pour en savoir plus
Chaque devoir est publié sous la forme d’un dépôt git sur la forge logicielle GitLab de l’université. Télécharger le devoir revient à en faire une copie locale (clone) ou la mettre à jour (pull) si elle existe déjà. Déposer revient à créer une divergence privée (fork) ou de la mettre à jour si elle existe déjà (push)
Consultation des résultats des tests automatiques#
Vous pouvez consulter les résultats des tests automatiques en navigant sur votre dépôt depuis le tableau de bord. Quelques minutes après avoir déposé, un badge apparaîtra avec votre score. Cliquez dessus et suivez les liens pour consulter le résultat de la correction automatique.
Travail en binôme#
Les TP seront à effectuer en binôme. Vous trouverez sur cette page web des suggestions sur comment travailler en binôme, et notamment configurer vos dépôts sur GitLab pour faciliter la collaboration et la correction.