Au terme de ce cours, l'étudiant(e) aura assimilé les notions suivantes :

• différents types d'analyse des performances des algorithmes : en temps, en espace, analyse amortie, etc.;
• classes de complexité : P, NP, NP-complet;
• algorithmes classiques sur les graphes : calcul d'arbres couvrants, tri topologique, identification des composantes fortement connexes, calcul du flot maximal,  coupure minimale, etc.;
• problèmes classiques de la théorie des graphes : partitionnement, clusterisation, clique, coloriage, commis voyageur, etc.;

À la fin du cours, l'étudiant(e) sera capable de :

• modéliser un problème donné en terme de graphes;
• utiliser la théorie des graphes et ses algorithmes afin de résoudre un problème de nature algorithmique;
• modifier les algorithmes classiques afin de les adapter à une situation particulière;
• concevoir une solution algorithmique exacte ou approchée en fonction du contexte.

• 3 heures de cours magistraux par semaine.
• 2 heures de laboratoire et de travaux pratiques par semaine. La répartition du temps entre travaux pratiques et activité de laboratoire est flexible et dépend de la matière vue lors des séances de cours magistraux.

Introduction aux bases de données orientées graphes (2h)

1. Principes fondamentaux
2. Comparaison aux bases de données relationnelles

Problèmes et algorithmes classiques sur les graphes (4h)

1. Parcours, arbres couvrants, composantes fortement connexes
2. Algorithmes de Prim, Kruskal, Tarjan, Kosaraju
3. DAG : tri topologique, chemin critique, chemin minimum en temps linéaire
4. Analyse des performances : en temps et en espace, analyse au pire cas et analyse amortie

Approche matricielle (3h)

1. Dénombrement de chemins
2. Parcours en largeur via l'algèbre matricielle
3. Algorithme de Floyd-Warshall
4. Introduction à l'analyse spectrale

Coupures et flots (3h)

1. Problème du flot maximal
2. Algorithmes de Ford-Fulkerson et Edmonds-Karp
3. Théorème flot-max/coupe-min

Découpage en communautés (6h)

1. Coupures : minimum et maximum
2. Diamètre d'un graphe
3. Algorithme des k-moyennes
4. Problèmes : clique, partition, identification de communautés

NP-Complétude (3h)

1. Classes P et NP
2. Réduction polynomiale
3. Problèmes NP-difficiles
4. Théorème de Cook

Coloriage de graphes (3h)

1. Algorithmes exacts et approchés
2. Preuve de NP-complétude
3. Applications en informatique
4. Introduction au théorème des 4 couleurs

Commis voyageur (3h)

1. Algorithmes exacts
2. Preuve de NP-complétude
3. Heuristique avec garantie : algorithme de Christofides

Systèmes distribués (6h)

1. Modèles synchrone et asynchrone.
2. Algorithmes élémentaires : diffusion, concentration, inondation, arbre couvrant, etc.
3. Algorithme de Bellman-Ford distribué
4. Coloration de graphe distribuée

Visualisation de graphes (3h)

1. Méthodes de base
2. Métriques
3. Méthodes basées sur les forces

L’étudiant(e) utilisera un outil de développement logiciel intégré (IDE) tel que : ECLIPSE, INTELLIJ ou VSCODE afin de développer des logiciels en JAVA.

Pour la réalisation des travaux de laboratoires, les étudiants(es) pourront utiliser un ordinateur MAC ou PC.

Laboratoires 40%

Examen intra 30%

Examen final 30%

Aucune documentation obligatoire.

KLEINBERG et TARDOS, Algorithm Design, Addison Wesley, 2006.
CORMEN, LEISERSON et RIVEST, Introduction à l’algorithmique. 3^e éd., Dunod, 2010.
DEO, Graph Theory with applications to Engineering & Computer Science, Dover, 1974.
ATTIYA et WELCH, Distributed Computing: Fundamentals, Simulations, and Advanced Topics, Wiley, 2004.

Le matériel de cours sera publié sur Moodle.