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

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

Travaux dirigés

Livret d'exercices: Algo-exercices.pdf