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

Table of Contents

1 Équipe pédagogique et organisation

Réunion pédagogique hebdomadaire de l'équipe (lundi 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 F116 Nicolas Gast
    • TD2 : Jeudi 08h00 - 09h30 F116 Alexandre Dumont
  • Groupe 2
    • TD1 : Lundi 13h30 - 15h00 F321 Florence Perronnin
    • TD2 : Jeudi 09h45 - 11h15 F319 Cyril Labbé
  • Groupe 3
    • TD1 : Mercredi 09h45 - 11h15 F321 Nicolas Gast
    • TD2 : Mardi 13h30 - 15h00 F319 Alexandre Dumont

2 Consignes

Les mails concernant

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-2016-im2ag-l3info@ujf-grenoble.fr , toute annonce officielle (quicks, apnées, déplacements de créneaux horaires,…) passera par ce mail (que vous devez lire quotidiennement)

3 Objectif

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.

4 Planning prévisionnel

  1. Thème : Algorithmique et complexité
    • Semaine 1 du 16/01
    • Semaine 2 du 23/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 30/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 06/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 13/02
      • TD2 : Plus longue sous-séquence commune
      • Cours : Récursivité et énumération slides
      • TD1 : Parties stables de cardinal \(k\) d'un graphe
      • HISTOIRE : Un très bel exposé de la BBC

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

    • Semaine 6 du 27/02
      • TD2 : Énumeration des parties d'un ensemble
      • Cours : Programmation dynamique
      • TD1 : Algorithme de rendu de monnaie
      • QUICK (mercredi): 1h mercredi pour vous entrainer sujet 2015 et corrigé attention les question 4,5,6 de l'exercice 2 ne sont pas au programme.
    • Semaine 7 du 06/03
      • TD2 : Algorithmes naïf de calcul de l'enveloppe convexe d'un ensemble de points
      • Cours : Diviser pour régner et enveloppes convexes
      • TD1 : Karatsuba et Strassen
      • Activité libre : énumération des parties
  3. Thème : Graphes et cheminements
    • Quick : énoncé et éléments de correction
    • Semaine 8 du 13/03
      • TD2 : Enveloppe convexe, structures de données
      • Cours : Énumération de l'ensemble des chemins d'un graphe, exemple de l'algorithme de Dijkstra
      • TD1 : Algorithme de calcul de chemins eulériens d'un graphe
      • APNEE (mercredi) : Enveloppe convexe (implémentation d'un algorithme itératif et d'un algorithme de type diviser pour régner)
    • Semaine 9 du 20/03
      • TD2 : Implémentation de l'algorithme de Dijkstra
      • Cours : Approche algébrique pour explorer l'ensemble des chemins
      • TD1 : Algorithme de Floyd-Warshall
  4. Thème : Exploration intelligente
    • Semaine 10 du 27/03
      • TD2 : Modélisation du problème de Sokoban
      • Cours : Exploration et algorithme minimax
      • TD1 : Algorithme A*
      • APNEE (mercredi) : Sokoban 1
    • Semaine 11 du 03/04 (le 6 est férié)
      • TD2 : Résolution automatique
      • Cours :Algorithme Alpha/Beta, préparation du projet
      • TD1 : Je divise, tu divises, ils révisent
      • APNEE : Sokoban 2 (mercredi), Sokoban démonstration (vendredi)

    ========== Semaine du 13/04 interruption pédagogique =====

    • Semaine 12 du 10/04 Rattrapages Pour réviser

5 Bibliographie commentée

5.1 Ouvrage à lire, travailler impérativement

  • Algorithmique Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Dunod, 2010.

    Ouvrage de référence internationale en algorithmique. Très pédagogique il peut être utilisé en autoformation, lorsque les bases sont acquises. Couvre l’ensemble du cours. L'ouvrage est cité comme [CLRS] dans la page

  • Algorithms (en anglais) Robert Sedgewick and Kevin Wayne. Addison Wesley, 2011.

    Une approche thématique permettant de reprendre les différents et paradigmes de l’algorithmique. La présentation est soignée, les détails des implémentations en Java sont très utiles. Des versions précédentes en français : Robert Sedgewick Algorithmes en C ou Algorithmes en Java chez Dunod

5.2 Ouvrages plus avancés

  • The Design and Analysis of Algorithms Dexter C. Kozen Springer, 1991.

    Excellent ouvrage pour de l’algorithmique avancée. Présenté sous forme de séquence de lectures "indépendantes" il va directement à l’essentiel. Les principes algorithmiques sont ainsi mis en valeur.

  • Algorithmics : The Spirit of Computing David Harel and Yishai Feldman Addison Wesley, 2004.

    Orienté méthodologie, cet ouvrage propose une vue transversale en abordant successivement, méthode et analyse, limitations et robustesse, extensibilité… intéressant pour le recul pris.

  • Introduction à l’analyse des algorithmes Robert Sedgewick and Philippe Flajolet Addison Wesley 1995

    Ouvrage théorique sur l’analyse de la complexité des algorithmes. Assez difficile d'accès, mais les fondements sont clairs et les méthodes efficaces

  • Randomized Algorithms, R. Motwani and P. Raghavan, Cambridge University Press, 1995.

    Ouvrage de référence sur le sujet, on ne fait qu'aborder la thématique dans le cours.

5.3 Ouvrages historiques (et toujours de référence)

  • The Art of Computer Programming, Vol 1-4 Donald E. Knuth, Addison-Wesley, 1998.

    Ouvrage historique et encore d’actualité pour la conception et l’analyse d’algorithmes

  • Data Structures and Algorithms Alfred V. Aho, J.E. Hopcroft, et Jeffrey D. Ullman Addison Wesley 1983

    Ouvrage de référence proche de l'implantation sur machine

  • Histoires d’algorithmes Jean-Luc Chabert et al. Belin 2010

    Une histoire des algorithmes avec un point de vue calcul et calcul numérique

Author: Jean-Marc Vincent

Created: 2017-03-27 Mon 11:37

Emacs 24.4.1 (Org mode 8.2.6)

Validate