Prep@s.org

Le site de l'UPS pour les Classes Préparatoires aux Grandes Écoles

Télécom Bretagne Stage 3 : Théorie et application des graphes avec Python du Mercredi 27 avril 2016 au Jeudi 28 avril 2016

4 stages sont proposés du 25 au 29 avril, où l’on peut s’inscrire à tout ou seulement à une partie des stages.

La page d’accueil est ici
Le descriptif des stages est

Stage 1 : lundi 25 avril 2016 : Probabilités : analyse et simulation des phénomènes aléatoires avec Python. Plus d'informations ici

Stage 2 : mardi 26 avril 2016 : Initiation aux bases de données, présentation du langage de requête SQL, exemples de programme Python pour interagir avec la BD. Plus d'informations ici

Stage 3 : mercredi 27 et jeudi 28 avril 2016 : Théorie et application des graphes. Plus d'informations ci-dessous

Stage 4 : vendredi 29 avril 2016 : Introduction au machine learning sous Python. Plus d'informations ici

Date : du 25 au 29 avril 2016

Pour toute question, merci de prendre contact par mail avec Chantal Leblond en cliquant sur ce lien : contact-cpge

Lieu : campus de Télécom Bretagne, Brest

Adresse : Le campus est situé à l'ouest de Brest, sur le Technopôle de Brest-Iroise. On y accède facilement avec le fléchage « Technopôle » en suivant la direction « Le Conquet, Plouzané ». L'École est située 655, avenue du Technopôle, en face de l'avenue La Pérouse. En savoir plus

Nombres min/MAX de participants : min=8, MAX=32

Prise en charge partielle par Télécom Bretagne des frais de restauration et d'hébergement pendant la durée du stage (voir formulaire d'inscription).

Intervenants : Thierry Chonavel, Issam Rebaï, Yannis Haralambous, enseignants-chercheurs à Télécom Bretagne

INSCRIPTIONS

Pour toute inscription, suivez ce LIEN

Stage 3 : mercredi 27 et jeudi 28 avril 2016 : Théorie et application des graphes


Intervenant : Yannis Haralambous

Pré-requis : 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 le 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


1ère journée (27 avril 2016)

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)

2ème journée (28 avril 2016)

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