UE Algorithmique et Modélisation – L3 INFO – UE GINF 363 – Année 2017/2018

• Cours : Jean-Marc Vincent
• TD1 : Nicolas Gast (coordination des TD1), Florence Perronnin et Jean-Marc Vincent
• TD2 : Cyril Labbé (coordination des TD2 et des Apnees), Adrien Faure

Réunion pédagogique hebdomadaire de l'équipe (mardi 12h) : lieu habituel

Les salles sont à vérifier sur ADE (qui fait foi)

• Cours : Mercredi 8h00 - 9h30 Jean-Marc Vincent
• TD Groupe 1
  • TD1 : Lundi 13h30 - 15h00 Jean-Marc Vincent
  • TD2 : Jeudi 09h45 - 11h15 Adrien Faure
• Groupe 2
  • TD1 : Lundi 13h30 - 15h00 Florence Perronnin
  • TD2 : Jeudi 08h00 - 09h30 Adrien Faure
• Groupe 3
  • TD1 : Mardi 08h00 - 09h15 Nicolas Gast
  • TD2 : Mardi 15h15 - 16h45 Cyril Labbé

Les mails concernant

• cours/examens…: Jean-Marc Vincent
• les TD1 : Nicolas Gast
• les TD2 et les Apnées : Cyril Labbé

Le sujet du mail doit être explicite avec

• SUJET : [L3INFO:ALGO6] Cours/TD1/TD2/Apnée sujet du mail
• Vous devez envoyer votre mail avec votre adresse officielle e.ujf-grenoble.fr
• toute adresse de provenance différente risque d'être "grey/black-listée" et d'atterrir dans une poubelle
• le mail officiel de la L3-INFO est la liste etu-2017-im2ag-l3_info@ujf-grenoble.fr , toute annonce officielle (quicks, apnées, déplacements de créneaux horaires,…) passera par ce mail (que vous devez lire quotidiennement)

Savoir rattacher un problème à une classe de problèmes, en déduire une approche adaptée pour sa résolution, valider la correction de la solution proposée, et en analyser sa complexité.

Cet objectif est atteint par une approche selon trois plans (ou points de vue) :

• raisonnement informel mais rigoureux, liant la réalisation d'un algorithme à ses spécifications, raffinement d'un schéma d'algorithme vers une réalisation particulière ;
• méthodes classiques de résolution dont le critère principal est la complexité (algorithmes gloutons, diviser pour régner, programmation dynamique…) ;
• types de problèmes classiques (parcours de graphe, énumération d'un ensemble de candidats…), et comment l'expression d'une solution (itérative, récursive) est liée à la structure sous-jacente.

1. Thème : Algorithmique et complexité
   • Semaine 1 du 15/01
     • Cours : Présentation de l'UE Expression des algorithmes Introduction à la complexité de problème, classes de problèmes, exemple de l'exponentiation Complexité Master-Theorem
     • TD1 : Le tri partition/fusion, analyse et fusion sur place
     • TD2 : déplacé en fin de semestre Lire le dernier cours de recherche de motif d'Algo5 sur la recherche de Maman.
     • Fun : http://panthema.net/2013/sound-of-sorting
   • Semaine 2 du 22/01
     • TD2 : Recherche de motif dans une chaîne de caractères algorithme naïf, automate des préfixes
     • Cours : Tables de hachage outil algorithmique, (chapitre 11 du [CLRS]) Exemple de l'algorithme de Karp-Rabin Algorithme
     • TD1 : Arbres binaires de Recherche : Analyse en moyenne
     • APNEE (vendredi) : Algorithme de recherche de motif
   • Semaine 3 du 29/01
     • TD2 : Structures de mapping et tables de hachage
     • Cours : Construction de fonctions de hachage, (chapitre 11 du CLRS) exemple du tri par paquet (section 8.4 du [CLRS])
     • Td1 : Tables de hachage et analyse en moyenne Corrigé Remplissage
     • APNEE (mercredi): table de hachage hash-join (utilisation de librairies Java standard)
   • Semaine 4 du 05/02
     • TD2 : La fonction random, utilisation de l'aléatoire et de la simulation
     • Cours : Algorithmes randomisés, exemple du test de primalité de Miller-Rabin (voir le [CLRS] section 31.8)
     • TD1 : Algorithme randomisé de calcul de la coupe min d'un graphe
     • APNEE (vendredi) : Génération aléatoires de textes
     • FUN : Killer Quicksort
2. Thème : Diviser pour régner et récursivité
   • Semaine 5 du 12/02
     • TD2 : Plus longue sous-séquence commune
     • Cours : Récursivité et énumération slides
     • TD1 : Karatsuba et Strassen
     • HISTOIRE : Un très bel exposé de la BBC

   ========== Semaine du 19/02 interruption pédagogique =====

   • Semaine 6 du 26/02
     • TD1 : Parties stables de cardinal \(k\) d'un graphe
     • Cours : Programmation dynamique
     • TD2 : Énumération des parties d'un ensemble
     • QUICK (vendredi): 1h pour vous entrainer sujet 2015 et corrigé
   • Quick : énoncé-2017 et éléments de correction-2017
   • Semaine 7 du 05/03
     • TD1 : Algorithme de rendu de monnaie
     • Cours : Diviser pour régner et enveloppes convexes
     • TD2 : Algorithmes naïf de calcul de l'enveloppe convexe d'un ensemble de points
3. Thème : Graphes et cheminements
   • Semaine 8 du 12/03
     • TD1 : Algorithme de calcul de chemins eulériens d'un graphe
     • Cours : Énumération de l'ensemble des chemins d'un graphe, exemple de l'algorithme de Dijkstra
     • TD2 : Enveloppe convexe, structures de données
     • APNEE (mercredi) : Enveloppe convexe (implémentation d'un algorithme itératif et d'un algorithme de type diviser pour régner)
   • Semaine 9 du 19/03
     • TD1 : Des présentations de l'algorithme Dijkstra
     • Cours : Approche algébrique pour explorer l'ensemble des chemins
     • TD2 : Implémentation de l'algorithme de Dijkstra
4. Thème : Exploration intelligente
   • Semaine 10 du 26/03
     • TD1 : Exploration et algorithme A*
     • Cours : Algorithme de Floyd-Warshall
     • TD2 : Modélisation du problème de Sokoban
     • APNEE (mercredi) : Sokoban 1
   • Semaine 11 du 02/04 (le 2 est férié)
     • TD1 : Je divise, tu divises, ils révisent (TD du lundi reporté la semaine du 12)
     • Cours :Algorithme Alpha/Beta, préparation du projet
     • TD2 : Résolution automatique
     • APNEE : Sokoban 2 (mercredi), Sokoban démonstration (vendredi)
   • Semaine 12 du 09/04
     • TD1 : Révisions en commun Anciens sujets

     Pour réviser

     • le sujet du quick 1 et des éléments de correction
     • le sujet du Quick 2 de l'année dernière avec des éléments de correction
     • le sujet de l'année dernière