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

Table of Contents

———————— Travail à distance —————————

Chère étudiante, cher étudiant

J'espère que vous allez bien, que vous pouvez prendre toutes les précautions nécessaires et que vous allez rester de bonne humeur.

Cette semaine, les enseignements sont en cours de réorganisation. Nous sommes bien conscients que vous avez probablement des priorités plus importantes. Notre objectif est juste de vous permettre de garder le contact avec nous et de vous proposer des activités pour poursuivre votre formation. En cas de difficultés, n’hésitez pas à contacter des membres de l’équipe enseignante ou la responsable du L3.

Nous visons la simplicité pour le suivi de votre formation, de manière asynchrone de préférence, nous tenterons d’être les plus réactifs possible (l’organisation n’est pas simple pour nous aussi mais nous allons faire au mieux).

Je vous rappelle que la page de l’UE Algorithmique et Modélisation est https://algo.gricad-pages.univ-grenoble-alpes.fr/L3I-S6-algo/

Vous y trouverez les informations ponctuelles sur le déroulé de l’UE à distance Les feuilles de TD1 et de TD2, les informations sur le cours (cf plus bas)

Pour les TD1 et TD2, vous pouvez faire les fiches puis poser les questions lorsque vous êtes bloqués, nous vous encourageons également de partager entre vous et de faire des propositions, l’interactivité est fondamentale.

J’ai ouvert un framateam pour cela, il suffit de vous inscrire, voici le lien d’invitation https://framateam.org/signup_user_complete/?id=6hooxigcxffmdmzy3s87hdru5a

Identifiez-vous de manière explicite, que l’on puisse reconnaitre votre nom et savoir dans quel groupe de TD vous travaillez.

Pour le cours, difficile de faire un cours en visio, les outils classiques ne supportent pas la charge et surtout cela doit être synchrone et je ne suis pas certain que l’ensemble de la promotion puisse y assister.

Je vous propose en échange de faire un cours interactif avec un petit problème tous les jours (j’espère tenir le rythme). Je posterai le problème sur la page du cours, à vous de chercher une/des solutions, vous pouvez utiliser le chat pour échanger, je ferai une synthèse de vos réponses et donnerai les éléments importants ensuite.

Voici la page des petits problèmes lien

Il est clair que ce mode de fonctionnement est très nouveau pour les étudiants comme pour les enseignants, et nous avons besoin d'un peu de temps pour le mettre en place. Soyez patients avec vos profs qui sont soumis à une charge mentale très importante en ce moment.

Nous vous remercions de faire passer cette information aux étudiants qui ne sont pas touché par ce mail.

Prenez bien soin de vous et de vos proches, bon courage pour la mise en place de votre travail, nous attendons de vos nouvelles sur le framateam de préférence ou par mail,

Bien cordialement,

Pour l’équipe pédagogique

Jean-Marc Vincent


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

  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
  • 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
  • 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 Page du cours à distance
      • TD2 : Résolution automatique
      • APNEE 6 : Sokoban 2 (mercredi 01/04), APNEE 7 : Sokoban démonstration (vendredi 3/04)
    • Semaine 12 du 08/04

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-04-07 Tue 07:41

Validate