Semestre 5 – Algorithmique 4

Objectifs

Étude des méthodes pour la construction des algorithmes efficaces. Connaissance de structures de données de haut niveau. Capacité à construire des algorithmes efficaces et les analyser

Prérequis

Algorithmique (Listes, arbres ordonnés, programmation récursive, tris).

Contenu pédagogique de l’UE

Notion fondamentales: temps d’exécution d’un algorithme, algorithmes efficaces, structures de données.

Méthode de conception des algorithmes efficaces: diviser pour régner, programmation dynamique, algorithme glouton.

Structures de données: arbre binaire de recherche équilibré, tas binomial, B-arbre.

Algorithmes de graphes: problème d’arbre couvrant minimal (Prim, Kruskal), problème de plus court chemin (Dijkstra).

Exemple de réalisation

Projet « Seam-carving » : développement d’un programme de recadrage « intelligent » d’images. Voir les images ici.

Alexis et Julien

oiseau