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

> Formation > Cursus ingénieur

Algorithmique et optimisation discrète - 4MMAOD6

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 : 7.5
    • TD : 9.0
    • TP : -
    • Projet : -
    • Stage : -
    • DS : -
    Crédits ECTS : 1.5
  • Responsables : Jean-Louis ROCH

Objectifs

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

Objectifs:

  • analyser la performance d'un programme en terme de nombre d'opérations et de localité (nombre de défauts de localité)
  • concevoir un algorithme en prenant en compte les problématiques de hiérarchie mémoire (internet, disque dur, RAM, cache)
  • maîtriser les schémas de programmation itératifs et récursifs, et leur combinaison en cascade
  • concevoir et programmer des méthodes d’optimisation discrète: programmation dynamique et branch&Bound; exemples d’applications
  • pratiquer : TP
  • apprendre à modéliser par l'abstraction: temps et nombre d'opérations; cache et modèle de cache CO; optimisation et modélisation récursive

Contenu

Descriptif des 5 séances de cours et 6 de TDs:

  • Chap 1. Anlyse de la performance mémoire. Modèle CO. Technique par bloc cache-aware. Applications à des algorithmes sur des tableaux (tris et produits matrice-vecteur(s) [TP 0: produit matrice-matrice)
    TD1: produit matrice veteur; tri fusion.
    => TP0 Produit de matrice.
  • Chap 2. De cache aware à cache oblivious. Applications à la transposition et au produit matrice-vecteur.
    TP: patch optimal
    TD2 : trasposition et produit de matrices; tri par insertion
  • Chap 3. Programmation des formules récursives: élimination de la redondance par tabulation (mémoisation); programmation itérative; programmation récursive cache oblivious.
    TD 3: Formules récurisve et cache : Cnp
  • Chap 4. Application à la programmation d'un algorithme de programmation dynamique: distance de Fréchet
    TD4: Cageots de fraises.
  • Chap 5. Gestion des contraintes mémoire dans une exploration récrusive: application au Branch&Bound.
    TD5: Compromis mémoire file et pile
  • 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

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Filière ISI - Semestre 7
  • Cursus ingénieur - Filière IF - Semestre 7
cf. l'emploi du temps 2020/2021

Informations complémentaires

Code de l'enseignement : 4MMAOD6
Langue(s) d'enseignement : FR

Le cours est rattaché aux structures d'enseignement suivantes :

Vous pouvez retrouver ce cours dans la liste de tous les cours.

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 15 janvier 2017

Université Grenoble Alpes