Nicolas Méloni
Maître de conférences en informatique, Université de Toulon

I21 - Algorithmique et programmation 1

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

Livret d'exercices: Algo-exercices.pdf

  1. Introduction (pdf)

    • Problème et instance
    • Pseudo langage
    • Justesse et terminaison
    • Récurrence
    • Invalider un algorithme

  2. Analyse d'algorithme (pdf)

    • Modèle RAM
    • Analyse asymptotique
    • Familles de complexité
    • Analyse de boucle

  3. Bases de l'algorithmiques (pdf)

    • Parcours de tableau de dimension 1
    • Addition multiprécision
    • Parcours de tableau de dimension 2
    • Multiplication multiprécision

  4. Algorithmes de tris (pdf)

    • Le problème du tri
    • Tri sélection
    • Tri à bulles
    • tris par insertion
    • Tris optimaux

  5. Algorithmes de rangement (pdf)

    • Rangement pair/impair
    • Rangement bleu/blanc/rouge

  6. Algorithmes de recherche (pdf)

    • Recherche séquentielle
    • Recherche par dichotomie
    • Application à la recherche de pic

  7. Pile et de file (pdf)

    • Structure de pile
    • Structure de file

  8. Parcours de grille 2D (pdf)

    • Coloriage du zone
    • Recherche de chemin en largeur
    • Recherche de chemin en profondeur

Travaux pratiques

  1. Parcours de Tableaux

  2. Complexité des opérateurs

  3. Analyse en meilleur, pire et cas moyen

  4. Algorithmes de tris

  5. Algorithmes de rangements

  6. Algorithmes de recherche

  7. Piles et Files

  8. Plus cours chemin

  9. Démineur