table des matières
Université Bordeaux 1
Licence Semestre 2   Initiation à l'algorithmique
Dernière mise à jour effectuée le 2 Juillet 2007

Introduction

  1. Notion d'algorithme

    2. Définition 1.1. Un algorithme est une procédure de calcul bien définie qui prend en entrée un ensemble de valeurs et qui délivre en sortie un ensemble de valeurs.
    Exemple 1.1
    Problème : Trier une suite de nombres entiers dans l'ordre croissant.
    Entrée : Suite de n nombres entiers (a1, a2, ...an)
    Sortie : Une permutation de la suite donnée en entrée (a'1, a'2, ...a'n) telle que a'1≤a'2≤, ...≤a'n.
    A partir de la suite (6,9,2,4), un algorithme de tri fournira le résultat (2,4,6,9).
    Définition 1.2.Une valeur particulière de l'ensemble des valeurs données en entrée est appelée instance du problème.
    Exemple 1.1 (suite)
    La valeur (6,9,2,4) est une instance du problème.
    Définition 1.3.Un algorithme est correct si pour toute instance du problème il se termine et produit une sortie correcte.
    Les algorithmes peuvent être spécifiés en langage humain ou tout langage informatique. Dans ce qui suit nous utiliserons un langage proche du langage naturel. Nous donnerons une implémentation en Python (voir cours MISMI MIS 102

    Définition 1.4.Une heuristique est une procédure de calcul correcte pour certaines instances du problème (c'est à dire se termine ou produit une sortie correcte).
    Ce cours n'aborde pas les heuristiques.

    Pour qu'un algorithme puisse être décrit et s'effectue, les données d'entrées doivent être organisées.
    Définition 1.5.Une structure de données est un moyen de stocker et d'organiser des données pour faciliter leur stockage, leur utilisation et leur modification.
    De nombreux problèmes nécessitent des algorithmes :
    • Bio-informatique
    • Moteur de recherche sur Internet
    • Commerce électronique
    • Affectation de tâches

    Définition 1.6. L'efficacité d'un algorithme est mesuré par son coût (complexité)en temps et en mémoire.
    Une problème NP-complet est un problème pour lequel on ne connait pas d'algorithme correct efficace c'est à dire réalisable en temps et en mémoire. Le problème le plus célèbre est le problème du voyageur de commerce. L'ensemble des problèmes NP-complets ont les propriétés suivantes :
    • Si on trouve un algorithme efficace pour un problème NP complet alors il existe des algorithmes efficaces pour tous,
    • Personne n'a jamais trouvé un algorithme efficace pour un problème NP-complet,
    • personne n'a jamais prouvé qu'il ne peut pas exister d'algorithme efficace pour un problème NP-complet particulier.


  2. Notion de complexité

    3. L'efficacité d'un algorithme est fondamentale pour résoudre effectivement des problèmes.
    Exemple1.2.
    Supposons que l'on dispose de deux ordinateurs. L'ordinateur A est capable d'effectuer 109 instructions par seconde. L'ordinateur B est capable d'effectuer 107 instructions par seconde. Considérons un même problème (de tri par exemple) dont la taille des données d'entrées est n. Pour l'ordinateur A, on utilise un algorithme qui réalise 2n2 instructions. Pour l'ordinateur B, on utilise un algorithme qui réalise 50nlog(n) instructions. Pour traiter une entrée de taille 106 : l'ordinateur A prendra 2000s et l'ordinateur B prendra 100s. Ainsi même si la machine B est médiocre, elle résoudra le probème 20 fois plus vite que l'ordinateur A.
    Définition 1.1. La complexité d'un algorithme est
    • en temps, le nombre d'opérations élémentaires effectuées pour traiter une donnée de taille n,
    • en mémoire, l'espace mémoire nécessaire pour traiter une donnée de taille n.
    Dans ce cours, nous considèrerons que la complexité des instructions élémentaires les plus courantes sur un ordinateur ont un temps d'exécution que l'on considèrera dans ce cours comme constant égal à 1. Les instructions élémentaires sont : addition, multiplication, modulo et partie entière, affectation, instruction de contrôle.
    Ce qui intéresse fondamentalement l'algorithmique c'est l'ordre de grandeur (au voisinage de l'infini) de la fonction qui exprime le nombre d'instructions. Les courbes de références sont ici.

  3. Langage de description d'algorithmes

    4. Il est nécessaire de disposer d'un langage qui soit non lié à l'implémentation. Ceci permet une description plus précise des structures de données ainsi qu'une rédaction de l'algorithme plus souple et plus "lisible". Le langage EXALGO est un exemple de ce qui peut être utilisé et qui sera utilisé dans ce cours. Il est composé de chaînes de caractères alphanumériques, de signes opératoires (+,-,*,/,<,<=,>=,>,<>,==,=,ou,non,et), de mot-clés réservés, et de signes de ponctuation : ''=, ;,(,), début, fin, //. Les balises début et fin peuvent être remplacés par { et }.
    Remarque. Python n'utilise pas de marqueurs de fin. Le caractère : est le marqueur de début et quand l'indentation cesse Python considère que c'est un marqueur de fin.