INF 435 A : 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. Cinq domaines de la théorie de graphes seront étudiés : l'exploration de graphes et la recherche de plus courts chemins, les arbres couvrants, les réseaux de transport et les mesures de position avec une grande part dédiée aux différentes mesures de centralité. Dans chaque cas on verra des exemples d'application, la théorie mathématique sous-jacente et les aspects algorithmiques. 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.

La méthodologie pédagogique de ce module est basée sur la jonction et l'interaction entre théorie et pratique. Au cours des travaux pratiques, l'étudiant sera confronté à la modélisation de problèmes en terme de graphes, aux outils mathématiques appropriés, aux outils algorithmiques appropriés, et à l'implémentation de la solution. 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. En Travaux Pratiques les élèves vont implémenter les algorithmes dans le langage Python.

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.

Il abordera ainsi des problèmes classiques modélisables par des graphes, tels que la création d'un circuit électronique, la distribution de gaz au niveau d'une ville ou encore l'optimisation des performances d'une flotte marchande.

Objectifs pédagogiques :

• 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
• 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
• 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
• Décrire les modèles formels vus en cours et expliquer un ensemble de problèmes de référence associés

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 : 18h

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 :

TP 1-2 : parcours optimisé d'un robot (3h)

Un robot se déplace sur un graphe donné pour distribuer des ressources à chaque noeud. Il s'agit de trouver la meilleure position de stockage des ressources pour minimiser les déplacements du robot. L'algorithme de mesure de la "meilleure position" doit être developpée dans un programme en python.

Les étudiants rendent une argumentation de leur choix de représentation du graphe, des algorithmes proposés et une interprétation de la métrique de position implémentée.

TP 3-4 : le téléphone arabe (3h)

À partir d'un graphe valué «réseau social» dans lequel à chaque arête est associée une durée en minutes, deux questions :
- quel est le temps minimal pour qu'une rumeur partant d'un individu atteigne tout le monde ?
- sachant qu'à chaque passage d'information, 10% du contenu est perdu, quelle est la déviation sémantique minimale ?

Les étudiants rendent une argumentation de leur choix de représentation du graphe et des algorithmes proposés.

TP 5-6 : dans la peau du Community Manager de Telecom Bretagne (3h)

À partir d'un graphe représentant des messages publiés sur Twitter, les étudiants appliqueront les mesures d'analyse de réseaux sociaux vues en cours via l'outil d'analyse dédié Gephi. Ils devront interpréter les différentes mesures d'influence sur un cas concret d'analyse de buzz. Ils seront confrontés à des grands graphes réels et comprendront la nécessité d'évaluer la complexité des algorithmes mis en œuvre.

Les étudiants rendent une argumentation de leur analyse et l'interprétation des mesures employées.

Année 2016/2017
Dernière mise à jour le 08-FEB-16
Validation par le responsable de programme le