Algorithmique avancée

Algorithmique avancée#

M1 Informatique pour la Science des Données, Université Paris-Saclay, Faculté d’Orsay

Page web, ENT eCampus

«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#

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 ?

../_images/metro-paris.gif

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?

Un visuel du jeu de plateau RushHour

Problème 3: Faire passer le maximum de courant#

../_images/reseau-electrique.png

Problème 4: Fabriquer et résoudre des labyrinthes#

../_images/labyrinthe.png

Planning#

7 séances de 3h: Cours + TD + TP intégré

Graphes: structures de données, terminologie, plus courts chemins#

  • 2025-01-20 lun. 13:30-16:45

  • 2025-01-24 ven. 13:30-16:45

Réseaux et flots#

  • 2025-02-03 lun. 13:30-16:45

  • 2025-03-18 lun. 13:30-16:45

  • 2025-03-25 lun. 13:30-16:45

Arbres couvrants#

  • 2025-04-01 lun. 13:30-16:45

  • 2025-05-26 lun. 09:00-12:15 (horaire à confirmer)

Examen#

  • 2025-05-30 ven. 09:00-12:15

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

Expérimentation

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. 🚧 Modalités à tester 🚧.

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#

Utilisation des logiciels en ligne (recommandé)

L’université Paris-Saclay mets à votre disposition deux services sur lesquels sont installés tous les logiciels requis. Vous pouvez vous identifier avec vos identifiants usuels de l’université (Adonis).

Installation en local de l’environnement de travail (optionnel)

Alternativement, vous pouvez installer les logiciels sur votre machine et travailler en local.

Ce cours utilise Python, Jupyter et quelques bibliothèques classiques (voir le fichier environment.yml, ainsi que quelques paquets Python plus ou moins maison.

Avec miniconda (ou micromamba, …)

  1. Si vous ne l’avez pas déjà, installez le gestionnaire d’environnements conda. Nous recommandons l’utilisation de l’installateur Miniforge.

  2. Si vous ne l’avez pas déjà, installez mamba (plus rapide que conda; fourni directement par miniforge) :

    conda install -c conda-forge mamba

  3. 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

  4. Installez les logiciels requis :

    cd ~/M1-ISD/AlgorithmiqueAvancee/binder
mamba env create
conda  activate algo-avancee

    La liste des logiciels pourra être mise à jour en en cours de semestre. Dans ce cas:

    cd ~/M1-ISD/AlgorithmiqueAvancee/binder
git pull
mamba env create --force

  5. Activez votre environnement conda et lancez Jupyter :

    conda activate algo-avancee
jupyter lab

    Attention

    Pour accéder aux logiciels fournis, vous devrez réitérer cette activation à chaque fois que vous ouvrirez un nouveau terminal.

Avec Docker

Une image docker du cours est fournie dans le Container Registry du projet Gitlab du cours. Voici son identifiant:

gitlab.dsi.universite-paris-saclay.fr:5005/m1infoisdalgorithmiqueavancee/computerlab/image:latest

Télécharger et déposer les devoirs#

Les sujets sont donnés sous forme de dépôt git sur https://gitlab.dsi.universite-paris-saclay.fr . Vous utiliserez git pour le télécharger et le déposer sous la forme d’une divergence privée (fork). La correction se fera en partie automatiquement par intégration continue. Il y a un script pour automatiser le processus.

Mise en place la première fois#

Activation compte GitLab Paris-Saclay#
Téléchargement de la «salle de TP virtuelle»#

Si vous ne l’avez pas déjà fait :

git clone https://gitlab.dsi.universite-paris-saclay.fr/M1InfoISDAlgorithmiqueAvancee/ComputerLab.git ~/M1-ISD/AlgorithmiqueAvancee

Note : nous supposerons dans la documentation ci-dessous que vous avez utilisé le nom de répertoire ~/M1-ISD/AlgorithmiqueAvancee/. Vous pouvez en utiliser un autre en adaptant les instructions.

Téléchargement et dépôt des TPs avec Travo#

L’environnement de cours fournit un script qui automatise le téléchargement et le dépôt de votre travail. Consultez sa documentation avec:

cd ~/M1-ISD/AlgorithmiqueAvancee
./course.py

Voir ci-dessous sur ce que cela fait, et comment faire pareil à la main, si vous le souhaitez.

Travail sur le TP#

Ouvrez les feuilles Jupyter et suivez les instructions dans les feuilles successives README.md, 00-*.md, 01-*.md, … ainsi que Rapport.md.

Dépôt de votre travail#

Consultez la documentation comme ci-dessus!

Vous pouvez déposer votre travail aussi souvent que vous le souhaitez. Seule la dernière version disponible au moment de la correction sera prise en compte.

Consultation des résultats des tests automatiques#

Vous pouvez consulter les résultats des tests automatiques en navigant sur votre dépôt:

https://gitlab.dsi.universite-paris-saclay.fr/prenom.nom_travo/

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 indications sur comment travailler en binôme, et notamment configurer vos dépôts sur GitLab pour faciliter la collaboration et la correction.