Ensimag Rubrique Formation 2022

Algorithmique et Optimisation Discrète - 4MMAOD

  • Volumes horaires

    • CM 8.25
    • TD 8.25

    Crédits ECTS

    Crédits ECTS 2.0

Objectif(s)

Titre complet: Algorithmique de l’optimisation discrète. Introduction à l'analyse de dépendances: parallélisme et localité mémoire

Objectifs:
- conception et programmation de méthodes d’optimisation discrete: programmation dynamique (et branch&Bound); exemples d’applications
- analyser un algorithme (graphe de dépendances ou de flots de données): programmation itérative et récursive, de l’un à l’autre
- analyse de la localité mémoire et du parallélisme; performance des schémas itératifs et récursifs
- initiation au parallélisme multicoeur (boucles OpenMP simples)
- pratiquer : TP

Contact Jean-Louis ROCH

Contenu(s)

Descriptif des 11 séances:

  • Chap 1 Programmation des formules récursives : élimination de la redondance par tabulation
  • Chap 2. Programmation dynamique (2 séances)
    => Démarrage TP : tex-display: justification optimale d’un texte (par paragraphe mais avec plusieurs paragraphes)
  • Chap. 3 Analyse de dépendances (2 séances): de récursif à itératif et d'itératif à récursif.
  • Chap 4. Exemple de synthèse: Processus de décision (MDP): algorithme EM (expectation–maximization)
  • Chap 5. Analyse des défauts de localité des accès mémoire: algorithmes cache-aware et cache-oblivious (2 séances)
  • Chap 6. Branch&Bound (2 séances)
  • Exemple de révision (dernière séance)


Prérequis

En terme de modules : Algorithmique et structures de données 1 et 2.
En terme de compétences : programmation impérative (itération, récursion, programmation procédurale, généricité ; mise en pratique). Structures de données

Contrôle des connaissances

CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) : TP individuel avec correction automatique

SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) : examen écrit
Salle spécifique : non
Durée : 2 h
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : tous documents manuscrits et photocopiés
Documents interdits (ex : livres, tous documents) : livres
Matériel (ex : calculatrices):

  • matériel autorisé, préciser :
  • matériel interdit, préciser : tout type de calculateur électronique
    Commentaires :

SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) : oral si < 5 étudiants, écrit 2h si > 6 étudiants
Salle spécifique :
Durée :
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) :
Documents interdits (ex : livres, tous documents) :
Matériel (ex : calculatrices):

  • matériel autorisé, préciser :
  • matériel interdit, préciser :
    Commentaires :


N1 = (3*E + TP) / 4
N2 = (3*E2 + TP) / 4

Informations complémentaires

Cursus ingénieur->Filière MMIS->Semestre 3
Cursus ingénieur->Filière ISI->Semestre 3
Cursus ingénieur->Filière ISSC->Semestre 3
Cursus ingénieur->Filière SLE->Semestre 3
Cursus ingénieur->Filière IF->Semestre 3

Bibliographie

Introduction to Algorithms (chap 1-4, 17, 14, 15, 22, 24, 25), Cormen Leiserson Rivest Stein, MIT PRESS
Thinking in Java, B. Eckel, Prentice Hall