IP4563 - Complexité des Algorithmes

IP4563 - Complexité des Algorithmes

Objectifs

Objectif général :

Savoir calculer les complexités temporelle et spatiale d'algorithmes séquentiels.
Être capable d'appliquer la technique de programmation dynamique pour optimiser les formulations
récursives.
Savoir comparer des algorithmes et choisir le plus adapté en fonction du problème.

Objectifs détaillés :

Maîtriser les notions de complexités temporelle et spatiale en pire cas d’un algorithme séquentiel.
Savoir calculer et comparer les expressions asymptotiques d'algorithmes itératifs et récursifs.
Savoir transformer certains algorithmes récursifs en algorithme itératif à l’aide de la programmation dynamique.
Comprendre la notion d’algorithme optimal.
Connaître les classes de complexité de problèmes NP, P, NPC et NP-difficile.
Savoir comparer des algorithmes et choisir le plus adapté pour résoudre un problème donné en fonction du contexte.

Place dans le cursus

plutôt au début du semestre 7

Volume horaire (h)

  • Cours magistraux : 10

Examens

Nombre total d'heures d’évaluation : 1

Ce cours fait partie de la formation

En bref

Crédits ECTS : Cf UE

Nombre d'heures 11

Contact(s)

Nicolas BARNIER

Tél : +33 5 62 25 95 06

Email : nicolas.barnier @ enac.fr

Jean-Baptiste GOTTELAND

Tél : +33 5 62 25 95 84

Email : jean-baptiste.gotteland @ enac.fr