UE Algorithmique (analyse des algorithmes, complexité)

Diplômes intégrant cet élément pédagogique :

Descriptif

Savoir proposer une solution algorithmique à un problème, savoir l'implanter et savoir l'analyser.
---------------------
Cet objectif se décline en plusieurs sous-objectifs :
- Savoir reconnaître et mettre en oeuvre des schémas génériques d'algorithmes (séquence, arbre, graphe...),
- Savoir construire une solution selon une démarche allant du plus simple (algorithme naïf) au plus efficace (diviser pour régner, etc...)
- Savoir comment évaluer la complexité d'une solution algorithmique: analyser la complexité au pire, en moyenne avec des hypothèses probabilistes,

Pré-requis

Expression itérative et expression récursive. Structures de données de base : séquences et arbres (représentations tabulées et chaînées) - Algorithmes de parcours de séquences et d'arbres - Interclassement de deux séquences - Algorithmes de tri

Compétences visées

1) Analyse d'algorithmes : coût d'algorithmes, complexité, équations récurrentes,  analyse en moyenne, introduction à la complexité d'un problème
2) Types abstraits : définition formelle, tableaux et tables de hachage, structures séquentielles (piles, files, files à priorité),
3) Structures arborescentes : Arbres, arbres binaires, propriétés, arbres de recherche, arbres partiellement ordonnés (structure de tas)
4) Problèmes classiques : algorithmes "union-find", dictionnaires arborescents, arbres de codage (algorithme de Huffman), arbres B, arbres 2D et quadtree,...

Bibliographie

Introduction à l'algorithmique
par Cormen, Leisserson, Rivest et Stein
Dunod 2002

Informations complémentaires

Lieu(x) : Grenoble - Domaine universitaire
Langue(s) : Français