Algorithmique et optimisation discrète - 4MMAOD6
A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail
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 en temps libre avec correction automatique
* Devoir individuel à la maison
SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) : pas d'examen, devoir individuel à la maison
SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) : si < 5 étudiants: oral de 30' ; si > 6 étudiants: écrit de 2h
Salle spécifique : non
Durée : 2h si écrit; oral individuel 30' par élève avec 30' préparation
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 :
- MCC en présentiel distanciel **
N1 =1/2 note projet en temps libre + 1/2 devoir à la maison
N2 = examen écrit de 2h (ou oral individuel de 30' si < 5 élèves)
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 2022/2023
Informations complémentaires Code de l'enseignement : 4MMAOD6
Langue(s) d'enseignement : 
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
A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail
mise à jour le 15 janvier 2017
> Formation > Cursus ingénieur
Nos sites
e-Services
