Stage Liesse 2017-1

Texte

STAGE 1 (24 avril)

THÉORIE ET APPLICATIONS DES GRAPHES SOUS PYTHON

Pré-requis : des notions de base sur la syntaxe du langage Python sont suffisantes pour aborder ce stage. Quelques notions de mathématiques (relations binaires, algèbre linéaire).

Mots-clés : graphes, arbres, algorithme de plus court chemin, arbre couvrant

Présentation :

On cite souvent le problème des sept ponts de Königsberg, résolu par Euler en 1741, comme point de départ de la théorie des graphes, mais en réalité elle s’est surtout développée dans la deuxième moitié du vingtième siècle, en même temps que l’informatique. Les applications des graphes sont innombrables et il est toujours réconfortant pour les élèves de réaliser que les mêmes outils (théoriques et pratiques) peuvent être utiles dans des situations diverses et variées. Ce stage propose une initiation à la théorie des graphes et se base sur un certain nombre d’algorithmes génériques (BFS, DFS, Dijkstra, A*, Kruskal, Prim) et leurs applications. L’objectif pédagogique pour les élèves de classe prépa est double : s’exercer en algorithmique par l’étude des algorithmes, et apprendre à modéliser des problèmes du monde réel en utilisant des outils adaptés. Les exercices vus lors du stage peuvent ensuite servir en tant que base de TP de classe de prépa.

Programme

  • Définitions de base : sommets, arêtes, pondérations, orientation, cliques, stables, graphes bipartis, composantes connexes.
  • Python : le paquet graph-tool.
  • Algorithmes de parcours de graphe (BFS, DFS).
  • Algorithmes de recherche de plus courts chemins avec et sans heuristique (Dijkstra, A*).
  • Algorithmes de recherche d’arbre couvrant (Kruskal, Prim).
  • Mesures de centralité (par le degré, par vecteur propre, de Katz, PageRank, proximité, synexité), applications aux réseaux sociaux.
  • Découverte du logiciel gephi d’étude et de visualisation de graphe

> Retour au sommaire Formations Liesse 2017