L'unité d'enseignement « Algorithmique générale » est une UE de niveau (300) spécialisation relevant de la licence d'informatique. Elle possède un volume de 6 ECTS et s'étend sur 12 semaines. Elle est placée sous la responsabilité de Kedad-sidhoum, safia.

Description

L'algorithmique générale est la discipline indispensable pour concevoir des programmes corrects et efficaces. Cette UE permet d'étudier et d'analyser les algorithmes et les structures de données les plus fondamentales, de comprendre et de manipuler les concepts de preuves et de complexité d'algorithmes à travers différentes applications : tris, parcours de graphes, gestion d'ensembles dynamiques, problèmes d'optimisation dans les graphes. Outre l'étude d'algorithmes connus, cette UE vise l'apprentissage de la conception d'algorithmes pour la résolution de problèmes nouveaux ou de nouveaux algorithmes pour la résolution de problèmes identifiés.

1- Notions d'algorithmes: Preuve - Mesures de Complexité. Algorithmes de Tri.

2- Structures de données linéaires: Piles, files et listes (rappels) - Tables de hachage.

3- Structures de données arborescentes: Files de priorité - Arbres binaires de recherche équilibrés.

4- Graphes: Propriétés générales - Parcours.

5- Applications des parcours: - Plus court chemin (Algorithme de Dijkstra) - Arbre couvrant de coût minimum (Algorithme de Prim).

Préalables et buts pédagogiques

Bibliographie

• Cormen, Lieserson, Rivest et Stein (2002) Introduction à l'algorithmique (Dunod)

• Beauquier, Berstel et Chrétienne (1992) Eléments d'algorithmique (Masson)

• Aho, Hopcroft et Ullman (1987) Structures de données et algorithmes (InterEditions)

• Baynat, Chrétienne, Hanen, Kedad-Sidhoum, Munier-Kordon et Picouleau (2003) Exercices et problèmes d'algorithmique (Dunod)

Contenu indicatif par semaine

1. Notions d'algorithmes

2. Preuves - Récursivité

3. Mesures de complexité

4. Algorithmes de tris

5. Structures de données linéaires (Piles-Files-Listes) - Hachage

6. Structures de données arborescentes - Arbres binaires de recherche

7. Structures de données arborescentes - Tas

8. Introduction aux graphes

9. Parcours de graphes non-orientés

10. Parcours de graphes orientés

11. Algorithmes de plus courts chemins

12. Arbres couvrants de coût minimum