Scribd
Importer
8 vues4 pages

Cours complet sur les graphes et leurs applications

Le document présente un plan de cours structuré sur les graphes, débutant par la théorie et se poursuivant avec des algorithmes, des applications modernes, et des projets pratiques. Il couvre des sujets allant des bases des graphes aux réseaux de neurones graphiques et aux bases de données orientées graphes, avec des objectifs d'apprentissage clairs et des travaux dirigés associés. Chaque section est conçue pour renforcer les concepts théoriques tout en offrant des applications pratiques et des études de cas.

Transféré par

yangui rania
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd
8 vues4 pages

Cours complet sur les graphes et leurs applications

Le document présente un plan de cours structuré sur les graphes, débutant par la théorie et se poursuivant avec des algorithmes, des applications modernes, et des projets pratiques. Il couvre des sujets allant des bases des graphes aux réseaux de neurones graphiques et aux bases de données orientées graphes, avec des objectifs d'apprentissage clairs et des travaux dirigés associés. Chaque section est conçue pour renforcer les concepts théoriques tout en offrant des applications pratiques et des études de cas.

Transféré par

yangui rania
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd

Je vous propose plan est progressif et cohérent :

 On commence par la théorie,


 on passe aux algorithmes,
 puis aux applications modernes et outils (Neo4j, GNN),
 et enfin à la mise en pratique via projets.

1. Introduction aux graphes (2h cours, 2h TD)


🎯 Objectifs :

 Poser les bases conceptuelles des graphes.


 Relier théorie et premières applications.

📚 Contenu :

 Définitions : sommets, arêtes, graphes orientés / non orientés / pondérés / bipartis /


multigraphes.
 Représentations (matrice d’adjacence, listes d’adjacence, dictionnaires).
 Parcours : BFS, DFS.
 Applications simples : réseau social, chemin dans un labyrinthe.

📝 TD :

 Construire différents graphes et leurs représentations.


 Exercices de parcours BFS/DFS manuels.

2. Théorie avancée des graphes (4h cours, 2h TD)


🎯 Objectifs :

 Approfondir les propriétés théoriques.


 Préparer le terrain pour les algorithmes avancés.

📚 Contenu :

 Connexité et composantes fortement connexes.


 Graphes eulériens (théorème d’Euler), graphes hamiltoniens.
 Coloration de graphes et nombre chromatique.
 Arbres : propriétés, codage de Prüfer.

📝 TD :

 Vérification d’un graphe eulérien/hamiltonien.


 Exercices de coloration de graphes.
3. Algorithmes fondamentaux sur les graphes (4h cours, 4h
TD/TP)
🎯 Objectifs :

 Étudier les grands algorithmes classiques.


 Comprendre leurs applications et complexités.

📚 Contenu :

 Chemins : Dijkstra, Bellman-Ford, Floyd-Warshall.


 Arbres couvrants : Prim, Kruskal.
 Flots : Ford-Fulkerson, Edmonds-Karp.

📝 TD/TP :

 Implémentation en Python avec NetworkX.


 Étude d’un graphe de transport (calcul shortest path, min spanning tree).

4. Graphes et optimisation combinatoire (4h cours, 2h TD)


🎯 Objectifs :

 Relier graphes et complexité algorithmique.


 Introduire heuristiques et optimisation.

📚 Contenu :

 Problèmes NP-complets : Clique, Vertex Cover, TSP.


 Méthodes exactes : programmation dynamique, branch & bound.
 Méthodes heuristiques et métaheuristiques : glouton, recuit simulé, génétiques.
 Applications : planification, logistique, ordonnancement.

📝 TD :

 Étude d’un problème de voyageur de commerce simplifié.


 Comparaison méthode exacte vs heuristique.

5. Applications modernes des graphes (4h cours, 2h TD)


🎯 Objectifs :

 Montrer l’importance des graphes dans les réseaux complexes.


 Étudier des mesures et détection de communautés.
📚 Contenu :

 Réseaux complexes (loi de puissance, petit monde).


 Centralité : degré, proximité, intermédiarité, vecteur propre.
 Détection de communautés : Girvan-Newman, Louvain.
 Applications : réseaux sociaux, biologie, web.

📝 TD/TP :

 Analyse d’un dataset réseau social avec NetworkX.


 Identification de communautés et nœuds influents.

6. Graph Neural Networks (4h cours, 2h TP)


🎯 Objectifs :

 Introduire les modèles d’apprentissage profond appliqués aux graphes.


 Expérimenter avec un framework moderne.

📚 Contenu :

 Représentation de graphes pour le machine learning.


 Idée de convolution sur graphe.
 GCN (Graph Convolutional Networks).
 Applications : classification de nœuds, prédiction de liens, réseaux moléculaires.

📝 TP :

 Exemple avec PyTorch Geometric ou DGL (classification de nœuds sur Cora dataset).

7. Bases de données orientées graphes et Neo4j (4h cours,


4h TP)
🎯 Objectifs :

 Découvrir les graph databases.


 Apprendre Cypher et explorer Neo4j.

📚 Contenu :

 Comparaison SQL vs graph databases.


 Modèle Neo4j : nœuds, relations, propriétés.
 Cypher : CREATE, MATCH, RETURN, WHERE, shortestPath().
 Neo4j Graph Data Science (centralité, communautés).
 Applications : recommandation, analyse de fraude, réseaux sociaux.

📝 TP :

 Installation Neo4j Desktop ou AuraDB.


 Chargement d’un dataset (IMDB, Game of Thrones, réseau social).
 Requêtes Cypher (requêtes simples puis avancées).
 Analyse de communautés avec GDS.

8. Études de cas et projets (4h cours, 2h TP)


🎯 Objectifs :

 Synthétiser les acquis.


 Appliquer la théorie à un mini-projet de recherche.

📚 Contenu :

 Étude de datasets réels :


o Réseaux sociaux (Twitter, Facebook).
o Réseaux de transport/logistique.
o Réseaux biologiques (protéines, gènes).
 Méthodologie de projet de recherche : problématique, méthode, résultats.

📝 Projet final (par groupes) :

 Analyse de graphe réel avec Python/Neo4j.


 Rapport + soutenance courte.

Vous aimerez peut-être aussi