Aller au menu Aller au contenu
Grenoble INP - UGA
Une voie, plusieurs choix
Informatique et Mathématiques appliquées
Une voie, plusieurs choix

> Formation > Cursus ingénieur

Algorithmique et Optimisation Discrète - 4MMAOD

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

  • Volumes horaires

    • CM : 8.25
    • TD : 8.25
    Crédits ECTS : 2.0

Objectifs

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

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ôles 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 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

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

mise à jour le 21 novembre 2014

Université Grenoble Alpes