Schema della sezione

    1. Graphes orientés
    2. Plus courts chemins
    3. DAG : l'algorithme de Bellman
    4. Poids positifs : l'algorithme de Dijkstra


    		Spyked math cheminement

    • Compétences

      1. Problèmes
        • Décrire les trois problèmes de plus courts chemins 
        • Expliquer le principe de sous-optimalité
      2. Algorithmes et preuves
        • Décrire les ingrédients d'un algorithme de plus court chemin
        • Écrire l'algorithme BFS
        • Pour les graphes non pondérés, décrire le certificat et la preuve que BFS renvoie bien les distances
      3. DAG et algorithme de Bellman
        • Démontrer qu'un DAG a toujours une source
        • Décrire un algorithme pour trouver un ordre topologique
        • Décrire l'algorithme de Bellman pour les plus courts chemins dans un DAG
        • Appliquer l'algorithme de Bellman sur un exemple
      4. Poids positifs, algorithme de Dijkstra et tas binaire
        • Décrire l'algorithme de Dijkstra pour les plus courts chemins lorsque les poids sont positifs
        • Implémenter l'algorithme de Dijkstra
        • Démontrer la validité de  l'algorithme de Dijkstra 
        • Connaitre et Implémenter la structure de données tas binaire
        • Calculer la complexité de l'algorithme de Dijkstra

      Vocabulaire : Graphe orienté, arc, degré entrant, degré sortant, source, puits, chemin, longueur d'un chemin, circuit, graphe orienté pondéré, distance, DAG, ordre topologique, tas binaires

      Notations : d^-(u), d^+(u), d(u, v)   
    • Transparents plus courts chemins File
      Gli studenti devono
      Visualizzare
    • Feuille d'exercices plus courts chemins File
      Gli studenti devono
      Spunta come completato
    • One idea, one story: the physics of shortest paths to detect useless streets ! Pagina
      Gli studenti devono
      Visualizzare
    • Test plus court chemin Quiz
      Gli studenti devono
      Visualizzare
      Ricevere una valutazione
      Ottenere la sufficienza
    • Trouver un plus court chemin lorsque les poids sont positifs Quiz
      Gli studenti devono
      Ricevere una valutazione
      Ottenere la sufficienza
    • Trouver un plus court chemin dans un DAG Quiz
      Gli studenti devono
      Visualizzare
      Ricevere una valutazione
      Ottenere la sufficienza
    • Vidéo (6min): Ordre topologique Pagina
    • Exécuter l'algorithme de Bellman Ford Quiz
      Gli studenti devono
      Spunta come completato
    • Gli studenti devono
      Spunta come completato

      "L'humour est le plus court chemin d'un homme à un autre."
      Georges Wolinski

    • Implémentation de la structure de tas binaire et de l'algorithme de Dijkstra - Java Virtual programming lab
      Gli studenti devono
      Ricevere una valutazione
    • Javadoc de Element.java File
      Gli studenti devono
      Visualizzare
    • Javadoc de Arc.java File
      Gli studenti devono
      Visualizzare
    • Javadoc de GrapheOriente.java File
      Gli studenti devono
      Visualizzare
    • Javadoc de TasBinaire.java File
      Gli studenti devono
      Visualizzare