INF 435 P : Graphes

Présentation :

Le but de ce module est d'apporter à l'élève les connaissances fondamentales de la théorie de graphes et la capacité de reconnaître l'apport des graphes dans une multitude de situations et de proposer et de mettre en œuvre une solution en utilisant les algorithmes appropriés. Les domaines classiques de la théorie de graphes seront étudiés : le parcours de graphes, le calcul de plus courts chemins, les arbres couvrants, les réseaux de transport, les métriques permettant d'identifier des positions clés (utiles dans les réseaux sociaux). Dans chaque cas on verra des exemples d'application, la théorie mathématique sous-jacente et les aspects algorithmiques. En Travaux Pratiques les élèves vont implémenter les algorithmes dans le langage Python.

La méthodologie pédagogique de ce module est basée sur la jonction et l'interaction entre théorie et pratique, en suivant le schéma : problème confronté en TP, modélisation de problème en terme de graphes, outils mathématiques appropriés, outils algorithmiques appropriés, implémentation de la solution. Ainsi, on n'écartera pas les démonstrations de propositions mathématiques, quand celles-ci comportent des idées qui permettent de mieux assimiler les concepts. De même, on n'écartera pas l'écriture et le débogage de code, lorsque ceux-ci permettent de suivre concrètement l'application d'un algorithme.

Il est un principe connu que le métier d'ingénieur demande aussi bien la compréhension (théorique) que l'application (pratique). Tour à tour mathématicien et programmeur, l'élève trouvera dans ce module une illustration de ce principe.

Objectifs pédagogiques :

• Comprendre les notions de bases de théorie des graphes, telles que les matrices d'adjacence, les graphes pondérés, orientés, les chemins, la connexité, les arbres couvrants minimum, les flots, les parcours en largeur et profondeur, les mesures de position dans les réseaux sociaux
• Décrire les modèles formels vus en cours et expliquer un ensemble de problèmes de référence associés
• Reconnaître le problème de référence auquel un problème nouveau se ramène et apppliquer le formalisme et les méthodes associés
• Produire un code correspondant à un modèle formel spécifié, justifier les représentations en mémoire adoptées, appliquer les algorithmes de références, et en évaluer les performances

Pré-requis :

Savoir traduire un problème en algorithme, écrire un algorithme en pseudo code, le coder dans un langage de programmation impératif (Java ou C), avoir développé un programme simple concurrent en Java, avoir développé un programme simple en Python.

Volume horaire : 21h

Contenu détaillé :

Cours 1-2 (3h)

Définitions générales et formalisation des notions fondamentales :
- sommets, arêtes, matrices d'adjacence, graphe pondéré, graphe orienté, graphe biparti, matrice d'incidence
- arbre, forêt
- chemins, connexité, connectivité, laplacien de graphe
- représentation du graphe en mémoire


Cours 3-4 (3h)

Les principaux algorithmes :
— parcours du graphe en profondeur d'abord
— parcours du graphe en largeur d'abord
— détermination algorithmique de composantes connexes
— recherche du plus court chemin, algorithme de Dijkstra
— arbres, arbres couvrants minimaux, algorithmes de Kruskal et Prim
— flots et réseaux de transport, algorithme de Ford-Fulkerson


Cours 5-6 (3h)

Mesures :
- centralité de degré, vecteur propre, Katz, proximité
- algorithmes : le PageRank, HITS
- coefficient de clustering
- groupes de sommets, cliques, k-plexes, cohésion

Travaux personnels encadrés :

Un mini-projet servira de fil rouge aux séances de TPs et permettra d'utiliser les outils vus en cours (modèles, algorithmes, métriques) pour résoudre un problème classique et toujours actuel de e-marketing.

Chaque séance de TP est organisée autour d'un problème élémentaire à résoudre. Les étudiants, par groupe, modélisent le problème par un graphe, conçoivent un algorithme basé sur un algorithme classique de la théorie des graphes, en font une implémentation en Python, tout en argumentant les choix de conception et d'implémentation.

Les TPs permettront de travailler certaines des techniques suivantes :
- les parcours de graphes
- le calcul de flot maximal
- la découverte d'arbre couvrant minimal
- le calcul et l'interprétation de métriques de position clés dans un graphe

Les problèmes à résoudre sont variés :
- trouver la position optimale d'un robot
- le téléphone arabe
- la gestion de foule dans le métro
- définir les stratégies marketing d'un community manager sur Twitter
- appréhender la position et les communautés d'intérêt dans Facebook
- définir le nombre optimal d'aquarium de dauphins selon des contraintes de respect d'affinités

Le dernier TP, dont le sujet n'est dévoilé qu'en début de séance, compte pour le contrôle continu (3h). Les étudiants auront un problème à résoudre avec les techniques d'analyse de graphes vues en cours.

Le premier TP est à rendre et est évalué, sans note, selon la grille d'évaluation qui sert au contrôle continu, de façon à sensibiliser les étudiants aux attentes et objectifs à atteindre pour valider le module.

Année 2018/2019
Dernière mise à jour le 10-JAN-18
Validation par le responsable de programme le