Схема на раздела

    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 Файл
      Обучаваните трябва
      Преглеждане
    • Feuille d'exercices plus courts chemins Файл
      Обучаваните трябва
      Отбелязване като завършено
    • One idea, one story: the physics of shortest paths to detect useless streets ! Страница
      Обучаваните трябва
      Преглеждане
    • Test plus court chemin Тест
      Обучаваните трябва
      Преглеждане
      Получаване на оценка
      Получаване на оценка за преминаване
    • Trouver un plus court chemin lorsque les poids sont positifs Тест
      Обучаваните трябва
      Получаване на оценка
      Получаване на оценка за преминаване
    • Trouver un plus court chemin dans un DAG Тест
      Обучаваните трябва
      Преглеждане
      Получаване на оценка
      Получаване на оценка за преминаване
    • Exécuter l'algorithme de Bellman Ford Тест
      Обучаваните трябва
      Отбелязване като завършено
    • Обучаваните трябва
      Отбелязване като завършено

      "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
      Обучаваните трябва
      Получаване на оценка
    • Javadoc de Element.java Файл
      Обучаваните трябва
      Преглеждане
    • Javadoc de Arc.java Файл
      Обучаваните трябва
      Преглеждане
    • Javadoc de GrapheOriente.java Файл
      Обучаваните трябва
      Преглеждане
    • Javadoc de TasBinaire.java Файл
      Обучаваните трябва
      Преглеждане
    • Plus courts chemins - Python Virtual programming lab
      Обучаваните трябва
      Получаване на оценка
    • Vidéo (6min): Ordre topologique Страница
    • Vidéo (8 min): Application de Bellman-Ford sur un exemple Страница
    • Vidéo (10 min): Les idées clefs de Bellman-Ford Страница
    • Vidéo (1 min): De Bellman-Ford à la programmation dynamique Страница