Algorithmique et complexité

Note

Humanités numériques

Le plus souvent, plusieurs algorithmes peuvent résoudre une même tâche. Lequel de ces algorithmes choisir ? Cette question concerne aussi bien l’utilisateur d’un système informatique, que le concepteur/programmeur de ce système.

Pré-requis

Programmation objet

Contenu de la formation

L’objectif du cours est de définir la notion de complexité d’un algorithme, qui est l’outil servant à la comparaison d’algorithmes. Cette notion est appliquée à quelques algorithmes fondamentaux : recherche d’un élément dans une liste, tri d’une liste.

La complexité d’un algorithme dépend de la manière dont les données manipulées sont stockées en mémoire. C’est pourquoi le cours revient aussi sur les structures de données (simples) standards.

Le cours ne se concentre pas sur un langage de programmation en particulier mais sur les concepts et structures récurrents en programmation : structures de contrôle, boucles, fonctions, tableaux, pointeurs, listes...

Connaissances

  • Complexité d’un algorithme
    • Notion
    • Méthode de calcul dans des cas simples
  • Structures de données simples
    • Tableaux
    • Listes
    • Tables de hachage
    • Arbres
  • Diviser pour régner

Compétences

  • Savoir appréhender la complexité d’un algorithme
  • Savoir choisir la structure de données/l’algorithme la/le plus adapté(e) à un besoin

Références

  • Cormen, Leiserson, Rivest, Stein. Introduction aux algorithmes. Seconde édition, Dunod.
  • Types de donnees et algorithmes, C. Froideveaux, M-C. Gaudel, M. Soria, chez Ediscience.
  • Algorithmes en langage C : cours et exercices, R. Sedgewick, chez Dunod.
  • Algorithmique : conception et analyse, G. Brassad, P. Bratley, chez Masson.
  • The Art of Computer Programming, D. Knuth, chez Addison-Wesley.

Table des matières

Sujet précédent

Programmation avancée

Sujet suivant

Modélisation interrogation de documents structurés en XML