UE Algorithmique et Modélisation – L3 INFO – UE GINF 363 – Année 2019/2020

Table of Contents

1 Équipe pédagogique et organisation

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

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

  • Cours : Mercredi 8h00 - 9h30 Jean-Marc Vincent
  • TD Groupe 1
    • TD1 : Lundi 13h30 - 15h00
    • TD2 : Jeudi 09h45 - 11h15
  • Groupe 2
    • TD1 : Lundi 13h30 - 15h00
    • TD2 : Jeudi 08h00 - 09h30
  • Groupe 3
    • TD1 : Mardi 08h00 - 09h30
    • TD2 : Mardi 13h30 - 15h00

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 [[mailto:etu-2019-im2ag-gbl3in160@univ-grenoble-alpes.fr%5D%5Betu-2019-im2ag-gbl3in160@univ-grenoble-alpes.fr], toute annonce officielle (quicks, apnées, déplacements de créneaux horaires,…) passera par ce mail (que vous devez lire quotidiennement)

APNEES les sujets et rendus sont sur le moodle de l'Ufr. Pour chaque APNEE, un lien vers le sujet est mis sur cette page à titre indicatif. En cas de difficulté vous devez contacter les deux chargés de TD2 au plus vite, toute réclamation doit être faite dans le quart d'heure après le démarrage de l'apnee pour être recevable.

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 (attention ce sont les documents de 2019, ils seront mis à jour durant le semestre)

  1. Thème : Algorithmique et complexité
    • Semaine 1 du 13/01
    • Semaine 2 du 20/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 1 (vendredi 24/01) : Algorithme de recherche de motif
    • Semaine 3 du 27/01
    • Semaine 4 du 03/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 3 (vendredi 07/02) : Génération aléatoires de textes
      • FUN : Killer Quicksort
  2. Thème : Diviser pour régner et récursivité

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

  • Semaine 7 du 02/03
    • TD1 : Algorithme de Karatsuba
    • Cours : Diviser pour régner et enveloppes convexes
    • TD2 : Algorithmes naïf de calcul de l'enveloppe convexe d'un ensemble de points
  1. Thème : Graphes et cheminements
    • Semaine 8 du 09/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 4 (vendredi 13/03) : Enveloppe convexe (implémentation d'un algorithme itératif et d'un algorithme de type diviser pour régner)
    • Semaine 9 du 16/03
      • TD1 : Des présentations de l'algorithme Dijkstra
      • Cours : Plus courts chemins, circuits, algorithme de Bellman
      • TD2 : Implémentation de l'algorithme de Dijkstra
  2. Thème : Exploration intelligente
    • Semaine 10 du 23/03
      • TD1 : Algorithme A*
      • Cours :Approche algébrique pour explorer l'ensemble des chemins
      • TD2 : Modélisation du problème de Sokoban
      • APNEE 5 (Vendredi 27/03) : Sokoban 1
      • Quick 2 : 23 ou 24 9h45-10h45
    • Semaine 11 du 30/03
      • TD1 : Algorithme de Floyd-Warshall
      • Cours : Approche algébrique pour explorer l'ensemble des chemins
      • Cours : Algorithme Alpha/Beta, préparation du projet
      • TD2 : Résolution automatique
      • APNEE 6 : Sokoban 2 (mercredi 01/04), APNEE 7 : Sokoban démonstration (vendredi 3/04)
    • Semaine 12 du 08/04

      Pour réviser

5 Évaluation

Conformément au règlement d'examen (qui fait foi) rappel : CC = 1/2 note de quicks + 1/2 note d'apnées

6 Bibliographie commentée

6.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

6.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.

6.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: root

Created: 2020-02-18 Tue 08:47

Validate