Algo 5 L3 Info

Equipe enseignante

• Cours : Benjamin Wack, mardi 15h30-17h amphi F022
• TD1 :
  • Groupe 1 : Valentin Garnero, mardi 9h45-11h15
  • Groupe 2 : Jean-Marc Vincent, mardi 8h-9h30
  • Groupe 3 : Valentin Garnero, mardi 8h-9h30
  • Groupe 4 : Benjamin Wack, lundi 13h30-15h
• TD2 :
  • Groupe 1 : Vincent Danjean, mardi 8h-9h30
  • Groupe 2 : Alban Reynaud, mercredi 8h-9h30
  • Groupe 3 : Kahina Ouazine, lundi 13h30-15h
  • Groupe 4 : David Monniaux, mardi 9h45-11h15

Adresse Mail enseignant : Prénom.Nom@univ-grenoble-alpes.fr

Annales

• 2023 : Quick 1 et son corrigé, Quick 2 et son corrigé
• 2022 : Quick 1 et son corrigé, Quick 2 et son corrigé, Examen
• 2021 : Quick 1 et son corrigé, Quick 2 et son corrigé, Examen

Liens utiles

• La page de l'UE sur le Moodle de l'UFR

Contenus (prévisionnels)

1. • Cours : Problème, spécification, instances, correction
     Modèle de coût d'un algorithme ; complexités au pire, au mieux
     Ordres de grandeur
     Les courbes projetées en cours (figures dynamiques) :
     • Comparaison de plusieurs fonctions
     • Borne supérieure asymptotique
     Algorithme : trouver la star
   • TD1 : calculs de coût (corrigé)
   • TD2 : mesure expérimentale de complexité (corrigé)
2. • Cours : Schémas récursifs simples
     Analyse en moyenne, modèle probabiliste
     Tri rapide
   • TD1 : le Base-ball multicolore (expérimenter en ligne) (corrigé)
   • TD2 : réalisation du tri rapide (corrigé)
   • Apnée 1 le 20/09 : rendez-vous sur Moodle et inscrivez-vous au cours d'Algorithmique semestre 5 de la Licence Info
3. • Cours : Structures séquentielles
     Algorithme de bon parenthésage
   • TD1 : simulations mutuelles (corrigé)
   • TD2 : tableaux et collections (corrigé)
4. • Cours : Structures arborescentes
     Partition Binaire de l'Espace
   • TD1 : algorithmes de parcours d'arbres
     (corrigé)
   • TD2 : files et files à priorité (corrigé)

Quick (complexité, structures de données) le 6/10

5. • Cours : Spécification, correction, invariant
     Terminaison, variant de boucle
     Drapeau hollandais
   • TD1 : un autre tour de magie, correction et terminaison (corrigé)
   • TD2 : drapeau arc-en-ciel (corrigé)
6. • Cours : Logique de Hoare
     Preuve automatique de programme
     Recherche dichotomique
     
   • TD1 : preuves de correction et de terminaison (corrigé)
   • TD2 : validation expérimentale de programmes (corrigé)
   • Apnée 2 le 20/10
7. • Cours : Structures de données dynamiques
     Arbres binaires de recherche
     Arbres B
   • TD1 : Arbres Binaires de Recherche d'Intervalles (corrigé)
   • TD2 : arbres binaires (corrigé)
8. • Cours : Arbres ordonnés
     Réalisation efficace d'une FAP
     Diviser pour régner
     Structure de tas
     
   • TD1 : Implantation d'un tas dans un tableau et Tri par tas (corrigé)
   • TD2 : Dictionnaire arborescent (corrigé)

Quick (preuve de programmes, ABR, tas) le 10/11

9. • Cours : Arbres et codage
     Entropie
     Algorithme de Huffman
   • TD1 : codage et algorithme de Huffman ; Diviser pour régner (corrigé)
   • TD2 : implantation des arbres n-aires à l'aide d'arbres binaires (corrigé)
   • Apnée (double) 3 les 22/11 et 24/11
10. • Cours : Problèmes d'optimisation
      Algorithmes gloutons
      Coloration de graphes
    • TD1 : Algorithmes gloutons : écriture, preuve (corrigé)
    • TD2 : Représentations de graphes (corrigé)
11. • Cours : Algorithmique de graphes
      Arbre couvrant
      Algorithmes de Prim et Kruskal
    • TD1 : Algorithmes gloutons : preuve, complexité
    • TD2 : Union-Find