UE Algorithmique et Modélisation – L3 INFO – UE GINF 363 – Année 2023/2024

Table of Contents

1 Équipe pédagogique et organisation

Réunion pédagogique hebdomadaire de l'équipe à définir)

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

  • Cours : Mercredi 8h00 - 9h30 Jean-Marc Vincent
  • Groupe 1
    • TD1 Lundi 13h30-15h Jean-Marc Vincent
    • TD2 Jeudi 8h-9h30 Florent Bouchez-Tichadou
  • Groupe 2
    • TD1 Lundi 13h30-15h Fanny Dufossé
    • TD2 Jeudi 8h-9h30 Cyril Labbé
  • Groupe 3
    • TD1 Mardi 13h30-15h Maxime Lesourd
    • TD2 Mercredi 9h45-11h15 Jolahn Vaudey
  • Apnees : Mercredi et/ou vendredi après-midi (voir ADE)

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.univ-grenoble-alpes.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-2022-im2ag-gbl3ig211@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 tous les trois 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 (provisoire, les liens pointent sur les ressources de 2023)

4.1 Semaine 15/01 Énumération

  • TD1 : Pilzegal TD1-1
  • Cours :Présentation de l'UE TC-0 et Introduction à l'énumération TC-1
  • TD2 : Couplage et énumération TD2-1

4.2 Semaine 22/01 Programmation dynamique

  • TD1 : Rendre la monnaie TD1-2
  • Cours :Programmation dynamique TC-2
  • TD2 : Plus longue sous-séquence commune TD2-2
  • APNEE : Vendredi

4.3 Semaine 29/01 Tables de hachage

  • TD1 : Anniversaires, distribution TD1-3
  • Cours : Éléments de probabilité et recherche dans une table et analyse du tri postal TC-3 TC-3b
  • TD2 : Algorithme de Karp-Rabin TD2-3(Tables de hachage)
  • APNEE : Vendredi

4.4 Semaine 05/02 Analyse en moyenne

  • TD1 : Tri par segmentation et randomisation TD1-4
  • Cours : Hachage: structure de table et fonctions de hachage TC-4
  • TD2 : Simulation TD2-4
  • APNEE : Vendredi

4.5 Semaine 12/02 Randomisation

  • TD1 : Calcul d'une coupe minimale d'un graphe TD1-5
  • Cours : Algorithmes randomisés TC-5 Analyse du Quicksort TC-5b
  • TD2 : Implémentation des tables de hachage TD2-5 (Karp-Rabin pour groupes 1 et 2, cf Semaine 5)

4.6 Semaine 19/02 Diviser pour régner

  • TD1 : Tri partition fusion TD1-6
  • Cours : Diviser pour régner et complexité TC-6 TC-6b TC-6c
  • TD2 : Enveloppes convexes TD2-6 et diviser pour régner
  • Quick : Vendredi

4.7 Semaine 04/03 Chemins et graphes

4.8 Semaine 11/03 Plus court chemin d'origine donnée

4.9 Semaine 18/03 Représentation algébrique des graphes

  • TD1 : Chemins et programmation dynamique TD
  • Cours : Approche algébrique de calcul des plus courts chemins transparents
  • TD2 : Travail APP Sokoban
  • APNEE : Mercredi
  • Quick : Vendredi

4.10 Semaine 25/03 Graphes et optimalité

4.11 Semaine 1/04

  • TD1 : lundi de Pâques report au 08/04 : révisions
  • Cours : Configurations, jeux et stratégies, arbres and/or
  • Td2 : Travail APP Sokoban préparation de la démo
  • APNEEs : Mercredi (APP Sokoban) et Vendredi : démonstration Sokoban

5 Anciens sujets

Attention, le programme ayant changé, tous les exercices des quick 1 et quick2 ne sont pas faisables et certains exercices du quick 2 ou des examens sont accessibles

Année Quick 1 Quick 2 Examen
2024 Q1-24 Q2-24  
  Q1-hint-24    
2023 Q1-23 Q2-23 E-23
2022 Q1-22 Q2-22 E-22
  Q1-hint-22 Q2-hint-22  
2021 Q1-21   E-21
  Q1-hint-21    
2020 Q1-2020   E-20
  Q1-hint-20    
2019 Q1-19   E-19
  Q1-hint-19    
2018 Q1-18   E-18
  Q1-hint-18    
2017 Q1-17   E-17
  Q1-hint-17    
2016 Q1-16   E-16
  Q1-hint-16    
2015   Q2-15 E-15
    Q2-hint-15  

6 Évaluation

Conformément au règlement d'examen (qui fait foi)

7 Bibliographie commentée

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

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

7.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: 2024-04-09 Tue 11:40

Validate