Graphes et algorithme
  • Découverte et exploration des graphes : partie 1
    • Présentation du problème fil rouge et règles du jeu
      • Fil rouge
      • Organisation du cours
    • Un exemple “jouet”
    • Exo - modéliser des données avec un graphe
    • Cours - Graphe
      • Rappel sur les ensembles
      • Première définition d’un graphe
      • Représentation visuelle d’un graphe
      • Application successeurs (voisinage)
    • Exo - Représentation mémoire d’un graphe
    • Cours - Représentation mémoire d’un graphe
      • Représentation mémoire des sommets du graphe
      • Représentation mémoire d’un sous ensemble de sommets : liste chaînée et tableau de booléen
      • Représentation mémoire d’un graphe par tableau de listes chaînées
      • Représentation mémoire d’un graphe par matrice booléenne
      • Représentation mémoire d’un graphe par tableau d’arcs
    • Exo - Graphe des sens interdits
    • Cours - Symétrique et graphes
    • Exo - Implémentation d’un premier algorithme de graphes
    • Cours - Algorithme SYM : calcul du symétrique d’un graphe
    • Bonus culture générale - Quelques graphes remarquables
  • Découverte et exploration des graphes : partie 2
    • Rappel du problème fil rouge et règles du jeu
      • Fil rouge
      • Organisation du cours
    • Un exemple “jouet” : rappel
    • Exo - Exploration des successeurs : algorithme de dilatation
    • Cours - Exploration des successeurs : dilatation
    • Exo - Chemin
    • Cours - Chemin
    • Exo - Exploration partielle
    • Cours - Exploration partielle d’un graphe
    • Exo - Exploration de graphe
    • Cours - Exploration d’un graphe
    • Exo - Programmer des algorithmes d’exploration de graphes
    • Cours - Algorithmes d’exploration de graphes
      • Cours - Algorithme Exploration Naïf
      • Cours - Algorithme Exploration Largeur
    • Exo - Connexité
    • Cours - Connexité
      • Connexité (et connexité forte)
      • Composante connexe (et fortement connexe)
      • Une propriété remarquable des composantes connexes et fortement connexes
    • Exo - Programmer des algorithmes de composantes connexes
    • Cours - Algorithme Composante Connexe et Composante Fortement Connexe
  • Regroupement de données avec des graphes
    • Présentation du problème fil rouge et règles du jeu
      • Fil rouge
      • Organisation du cours
    • Exercices : cyber-profiler et composantes \(k\)-liées
  • Plus courts chemins
    • Objectif et organisation de l’atelier
    • Notes de cours
    • Exercices (compréhension du cours et recherche arrière)
    • Travaux pratiques
  • Construire et optimiser un réseau d’espions - partie 1 : arborescence
    • Présentation du problème fil rouge et règles du jeu
      • Fil rouge
      • Organisation du cours
    • Un exemple “jouet”
    • Exo - Modéliser les données avec un graphe
    • Cours - Graphes à arêtes pondérées
    • Exo - Transmission sans redondance d’un message secret
    • Cours - Arbres et arborescences
      • Arbres
      • Arborescences
      • Représentation mémoire d’une arborescence
  • Construire et optimiser un réseau d’espions - partie 2 : arbre de poids minimum
    • Présentation du problème fil rouge et règles du jeu
      • Fil rouge
      • Organisation du cours
    • Un exemple “jouet”
    • Exo - Solution optimale pour l’exemple jouet
    • Cours - Arbre de poids minimum
      • Mise en situation
      • Formalisation avec les graphes
      • Arbres de poids maximum
    • Exo - Calculer des arbres de poids minimum
    • Cours - Algorithme de Kruskal
      • Schéma générique pour calculer des arbres de poids minimum
      • Algorithme de Kruskal
      • Choix des structures de données et Analyse de complexité
      • Preuve de correction de l’algorithme de Kruskal
    • Pour aller plus loin…
Graphes et algorithme
  • Docs »
  • Search

© Copyright 2021, Benjamin Perret, Jean Cousty.

Built with Sphinx using a theme provided by Read the Docs.