Intervenants

Cours : David Pichardie

Travaux dirigés : David Cachera et Yannick Zakowski

Planning des cours

CoursDateSujetMatériel supplémentaire
1 06/09/2016 Introduction
  • Union-Find
  • preuve par invariants de boucle
    		•  Quelques expériences avec des variantes de l'algorithme Union-Find
  • Quick-Find
  • Quick-Union
  • Union-find sans compression de chemin
  • Union-find avec compression de chemin
    •
    2 13/09/2016 Analyse de l'efficacité des algorithmes Quelques visualisations de tris (à utiliser en plein écran avec Acrobat Reader pour déclencher l'animation)
  • Tris insertion et fusion sur une entrée aléatoire
  • Tris insertion et fusion sur une entrée presque triée
  • Tri Shell
    •
    3 20/09/2013 Recherche :
  • techniques simples
  • arbres de recherche
  • arbres équilibrés (AVL)
    		•
    4 27/09/2016 Recherche (fin):
  • arbres équilibrés (AVL)
  • tables de hachage
    		•  Expériences sur les fonctions de hachage: on hache une fois tous les mots distincts du livre Les misérable (Tome 1) et on observe le nombre de collision.
    5 04/10/2016 Graphes :
  • Premières définitions
  • Représentations
  • Parcours
    		•
  • Quelques illustrations.
  • Un parcours récursif en profondeur animé (sous Acrobat Reader) du labyrinthe. Les sommets déjà vus sont noirs ou bleus. Les sommets bleus représentent des sommets i dont l'appel récursif VISITE(i) n'est pas encore terminé. Pour les sommets noirs, la date de fin a été déjà choisie.
  • Un parcours itératif en profondeur animé (sous Acrobat Reader) du labyrinthe. Les sommets déjà vus sont noirs ou bleus. Les sommets bleus représentent les sommets actuellement sur la pile.
  • Un parcours en largeur animé (sous Acrobat Reader) du labyrinthe. Les sommets déjà vus sont noirs ou bleus. Les sommets bleus représentent les sommets actuellement sur la file d'attente.
    • 6 11/10/2016 Graphes :
  • Etude formelle du parcours en profondeur
  • Détection de cycles
  • Tri topologique
  • Calcul de composantes fortement connexes avec l'algorithme de Kosaraju
    		•
    7 18/10/2016 Graphes :
  • Fin de la preuve de l'algorithme de Kosaraju
  • Algorithme de Tarjan pour la caclul de composantes fortement connexes
  • Propriétés du parcours en largeur
    		•
  • Présentation de l'algorithme de Tarjan
  • Comparaison Tarjan/Kosaraju
    		•
    Bonus 1 23/10/2016 Cours de programmation Python avancé Notes de cours.
    8 08/11/2016 Réseaux de flot Notes de cours.
    9 15/11/2016
    10 22/11/2016
    Bonus 2 29/11/2016