I21 - Algorithmique élémentaire

L'objectif de ce cours est d'introduire les concepts essentiels de l'analyse des algorithmes et de permettre l'acquisition et la compréhension par l'étudiant de notions de compléxité, d'efficacité, de comportement asymptotique a travers l'étude de quelques algorithmes fondamentaux ainsi que des structures de données qui leur sont associées.

L'enseignement est constituée de:

Plan du cours

Polycopié de cours: poly-algo.pdf

  1. Introduction 1-intro.pdf
    1. Problème et instance
    2. Pseudo langage
    3. Justesse et terminaison
    4. Récurrence
    5. Invalider un algorithme
  2. Analyse d'algorithme 2-analyse.pdf
    1. Modèle RAM
    2. Analyse asymptotique
    3. Familles de complexité
    4. Analyse de boucle
  3. Bases de l'algorithmiques 3-parcours.pdf
    1. Parcours de tableau de dimension 1
    2. Addition multiprécision
    3. Parcours de tableau de dimension 2
    4. Multiplication multiprécision
  4. Algorithmes de tris 4-tris.pdf
    1. Le problème du tri
    2. Tri sélection
    3. Tri à bulles
    4. tris par insertion
    5. Tris optimaux
  5. Algorithmes de rangement 5-rangement.pdf
    1. Rangement pair/impair
    2. Rangement bleu/blanc/rouge
  6. Algorithmes de recherche 6-recherche.pdf
    1. Recherche séquentielle
    2. Recherche par dichotomie
    3. Application à la recherche de pic
  7. Structures de pile et de file 7-pilefile.pdf
    1. Structure de pile
    2. Structure de file
  8. Parcours de grille 2D 8-grille.pdf
    1. Coloriage du zone
    2. Recherche de chemin en largeur
    3. Recherche de chemin en profondeur

Travaux dirigés

Livret d'exercices: Algo-exercices.pdf