This repository was moved to: https://gitlab.u-psud.fr/M1-ISD/AlgorithmiqueAvancee/Instructors
1ère année - Algorithmique avancée (25h)
L’objectif de ce cours est de fournir des outils et techniques algorithmiques de pointe aux apprentis. Etude de l’algorithmique sur les graphes (plus court chemin, tri topologique, …), les techniques de mémorisation, de programmation dynamique et de backtraching. 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.
MCC:
Session 1 : 1/3 CC + 2/3 ET1
Session 2 : 1/3CC + 2/3 ET2
3h: cours/td intégré
Mardi 29-01 AM F Jeudi 31-01 AM Impossible
Lundi 11-02 PM V Mardi 12-02 AM F Jeudi 14-02 AM V
Mardi 19-02 AM F Jeudi 21-02 AM impossible
Exam: Mardi 26-02 AM Pas Viviane.
Partie 1 (NT): Chemins dans un (di)graphe, structures de données de base, terminologie
Motivation: route la plus courte entre deux stations de métro de Paris
Tri topologique, ordonnancement simple (UET, 1 ou infinté processeurs)
Arbre, labyrithes, arbre couvrant de poids minimal algos Kruskal puis Prim.
Réseaux: Dijkstra, flots, Ford-Fulkerson, ...
Article de Mathieu Gay Paquet
Installation: voir le notebook Theme1-ParcoursDeGraphes/notes/Introduction.ipynb