Catalogue des formations

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

• Licence Informatique

Descriptif

Calcul de la complexité d'un algorithme
Preuve d'algorithme
Structures de données élémentaires : pile, file, tas, arbres
Méthodes algorithmiques : diviser pour régner, algos gloutons
Algorithmes classiques : tri rapide, arbres binaires de recherche, tri par tas, algorithme de Prim

Pré-requis recommandés

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

- Algorithmes en Java, par Sedgewick, Pearson Education

Informations complémentaires

Lieu(x) : Grenoble
Langue(s) : Français