JDL -Complexité des algorithmes

J. Durand-Lose

Printemps 2012

Le contenu de cette page devrait être progressivement passé sous Célène sur l’intranet de l’université.

Contents

1  Organisation

Nombre de séances: 9 CM (2h, 18h au total) + 11 TD (2h, 22h au total)

1.1  Descriptif de l’enseignement

Contenu
  1. notions de complexité,
  2. coût en temps et en espace, dans le pire des cas et en moyenne, et
  3. problèmes d’optimalité.

De nombreux exemples d’algorithmes illustrent le cours.

Objectifs (savoirs et compétences acquis)

Pouvoir évaluer l’évolution du temps d’exécution d’un algorithme en fonction de l’évolution de la taille des données.

1.2  Évaluation

Examen terminal écrit 2 heures.

2  Plan du cours (prévisionnel)

  1. Introduction (demi séance)
    but (prédire le passage à l’échelle), contexte, exemple et bases mathématiques (comparaison de fonctions et somme géométrique)
    recherche maximum / présence élément dans un tableau
  2. Programmation impérative (sans récursivité, une séance et demi)
    boucles for et while simples (et qq formules mathématiques)
    addition et multiplication de taille arbitraire, produit matriciel (simple), tri à bulles
  3. Diviser pour régner (récursive, deux séances)
    dichotomie, tri fusion, tours d’Hanoï, multiplication rapide d’entiers de taille arbitraire, puissance égyptienne, tri rapide (Quicksort, avec aléa)
    pgcd (à l’examen?)
  4. Algorithmes glouton (greedy) (deux séances)
    rendre la monnaie, sac à dos avec objets sécables, nombre max d’activité, ordonnancement pour minimiser l’attente, ordonnancement avec date butoir
    structure de tas, arbre recouvrant de poids minimal (Prim), Distance entre deux sommets (Dijstra),
  5. Test de performance (expérimentation) sur biblio et algo à programmer
  6. Programmation dynamique
    Coef. bin (ou Fibonacchi), analyse langage algébrique, sac à dos (avec poids max) et plus longue sous-séquence commune (dont TD)
  7. Aléatoire
    autre approximation (?)

Selon l’avancement, pourraient être abordés:

3  Formules mathématiques

Comparaisons (notations Landau et Hardy): http://fr.wikipedia.org/wiki/Notation_de_Hardy

3.1  À connaître

n
∑
i=0
 ai  = 
1−an+1
1−a
 avec  a≠ 1
n
∑
i=0
 i = 
n(n+1)
2
  ∈  Θ(n2)

3.2  Utiles

n
∑
i=0
 i2 = 
n(n+1)(2n+1)
6
  ∈  Θ(n3)
n
∑
i=1
i3 = 
1
4
n2(n+1)2    ∈  Θ(n4)

4  Examens passés

5  Conseils de lecture

Le livre Cormen et al. [2002] est un livre d’algorithmique (et même une bible sur le sujet) qui explique et donne la complexité des algorithmes classiques algorithmes.

Le livre Brassard and Bratley [1996] n’est pas disponible à la bibliothèque, mais il m’a beaucoup servi pour la complexité et les exemples sur les différents types d’algorithmes.

References

Brassard and Bratley [1996]
G. Brassard and P. Bratley. Fundamentals of Algorithmics. Prentice Hall, 1996.
Cormen et al. [2002]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction à l’algorithmique. Dunod, 2002. 2e édition, http://www.dunod.com/pages/ouvrages/ficheouvrage.asp?id=43922.
This document was translated from LATEX by HEVEA.