BCU

C1-ALGO-05.00 : Algorithmes classiques#

Objectifs pédagogiques#

  • connaître quelques classes d’algorithmes classiques:

    • algorithmes de tri

    • algorithmes de recherche

Introduction#

Être capable de programmer un ordinateur requiert deux éléments importants :

  1. Maîtriser un langage de programmation (par exemple Python)

  2. Avoir une connaissance des algorithmes classiques

Par algorithme classique on entend des classes d’algorithmes qui ont été décrit il y a longtemps (parfois plusieurs siècles) et qui sont reconnus comme étant la meilleure solution pour un problème donné (voir Cours 4)

La meilleure solution peut signifier celle qui prendra le moins de temps ou celle qui utilisera le moins de mémoire de l’ordinateur (ou toute autre métrique). On parle alors de complexité des algorithmes.

Algorithmes classiques : c’est quoi ?#

Un algorithme classique est un algorithme qui peut être écrit dans un langage de programmation et exécuté sur un ordinateur classique. Il possède les caractéristiques suivantes :

  1. il doit toujours se terminer après un nombre fini d’étapes

  2. chaque étape d’un algorithme doit être définie précisément, les actions à mener doivent être spécifiées rigoureusement et sans ambigüité pour chaque cas

  3. un algorithme a des entrées, zéro ou plus, quantités qui lui sont données avant ou pendant son exécution

  4. un algorithme a une ou plusieurs sorties, quantités qui ont une relation spécifiée avec les entrées

  5. les instructions doivent être suffisament basiques pour pouvoir être en principe exécutées de manière exacte, en un temps fini par une personne utilisant un papier et un crayon.

On peut donner une liste d’algorithmes classiques :

  1. Algorithmes de recherche

    • recherche dichotomique

  2. Algorithmes de tri

    • tri par sélection

    • tri à bulle

    • tri rapide

    • etc…

  3. Algorithmes de graphes (sur des structures de graphes)

    • Problème du voyageur de commerce

    • Plus court chemin

  4. Algorithmes mathématiques

    • suite de Fibonacci

    • Euclide

  5. Algorithmes dans le domaine de l’informatique pure

    • cryptographie

    • musique électronique

    • génétiques

    • analyse léxicale, syntaxique, sémantique

Nous allons concentrer notre survol des algorithmes classiques sur les deux premiers : algorithmes de recherche et algorithmes de tri