Algorithmique 2 : Motivation

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est maintenue par les enseignants et utilisée par les élèves de la matière concernée. Vos contributions sont les bienvenues, mais merci d'en discuter avant de faire des modifications non triviales de la page, pour être sûr de ne pas perturber le déroulement du cours.

Laptop.png  Première Année  CDROM.png  Informatique 

Cette page se veut une motivation du cours Algorithmique 2. Elle essaie de répondre à la question: qu'est-ce qu'un algorithme ?

Voilà une première réponse: c'est un processus systématique de résolution d'un problème par le calcul. En général, un algorithme doit terminer (sinon, on parle de semi-algorithme). Un algorithme est généralement écrit en langue naturelle avec des notations mathématiques.

Exemple du Tri Fusion

procedure TriFusion(T: in out Suite) is
 
  si Taille(T) > 1 alors
    
     -- on construit 2 suites T1 et T2 tq 
     -- T est une permutation de la concaténation de T1 et T2
     -- avec |Taille(T1)-Taille(T2)| <= 1
     T1,T2 := Separer(T) ; 
      
     TriFusion(T1) ;
     TriFusion(T2) ;
    
     -- on place dans T la concaténation triée de T1 et T2. 
     T := Fusion(T1,T2) ; 
      
 fin si   

Qu'est-ce que c'est ?

Cet algo est ici décrit dans une pseudo-syntaxe (qui ressemble à du Ada). Ici, on NE VEUT PAS vraiment écrire un programme: en particulier, on ne veut pas définir précisément ce qu'est le type "Suite". Ça pourrait être un type tableau Ada, un type de pointeur sur tableau, une liste simplement chaînée, une liste doublement chaînée, etc...

Ici, on peut raisonner d'une part:
1. sur la correction de l'algo (il réalise effectivement un tri).
2. sur le coût en temps (e.g. nombre d'opérations) de cet algo, en supposant que "Separer" et "Fusion" ont un coût en temps linéraire en fonction de "Taille(T)", on peut montrer que le coût de TriFusion est en "Taille(T).log(Taille(T))".

Cette approche est motivée par le fait qu'on peut programmer cet algo pour les différents types de données mentionnés ci-dessus, de manière à respecter cette analyse de coût en temps. Par contre le coût en espace est sensiblement différent pour les différentes implémentations du type "Suite". En effet, pour réaliser "Fusion" sur les tableaux Ada, le tableau de sortie doit nécessairement être disjoint des tableaux d'entrées (si on veut respecter le coût en temps): le coût en espace va être linéaire en fonction de "Taille(T)". Par contre, dans les listes chaînées on peut implémenter cet algo en place (sans allouer de nouvelles cellules).

A quoi ça sert ?

Typiquement, on va donc pouvoir comparer cet algorithme avec d'autres comme le tri par insertion: ce dernier est meilleur dans le meilleur cas (coût en temps linéaire), alors que ce premier est meilleur dans le pire cas.

Attention, ce type de comparaisons entre algorithmes exige de bien regarder ce qui est compté dans les analyses de coût, pour éviter de comparer des "choux" avec des "chèvres". Par exemple, dans l'analyse du tri fusion, on considère que toutes les comparaisons d'éléments ont un coût en temps constant (qui vaut "1"). Pour un autre algorithme (appelé "Radix sort" ou "tri par base"), spécialisé sur le tri d'une suite T de mots pour l'ordre lexicographique, on va regarder le coût des comparaisons au niveau des lettres de l'alphabet: on a ainsi un coût dans le pire cas en "Taille(T).TailleMotMax(T)" où TailleMotMax(T) donne le nombre maximal de lettres d'un mot de T. Si on veut comparer le coût de TriFusion (algo générique en fonction du type des éléments dans T et de l'ordre utilisé pour les comparaisons) avec cet algorithme spécialisé sur le tri des suites de mots, il faut bien multiplier le coût "Taille(T).log(Taille(T))" de TriFusion par TailleMotMax(T) (coût d'une comparaison de 2 mots dans le pire cas). En théorie, l'algo spécialisé est donc bien meilleur sur le coût en temps.

Conclusion

Quand on écrit un algorithme, on modélise un ensemble d'implémentations possibles dans le but de montrer d'une part la correction de l'algorithme et d'autre part d'effectuer une analyse de complexité (son coût en temps ou son coût en espace). Cette analyse de complexité fait des hypothèses sur les implémentations (et le langage de programmation et son compilateur). Il est important de bien tenir compte de ces hypothèses si on veut comparer des algorithmes sans se tromper.

Tentative de définition de la notion d'algorithme

Voilà quelques qualificatifs pour définir cette notion.

Un modèle de programme(s)

Un algorithme n'est généralement pas un programme exécutable. En effet, on peut considérer un programme source (dans un langage donné) comme un cas particulier d'algorithme. Et, un tel programme source n'est déjà pas lui-même un programme exécutable, mais un modèle de programme. Autrement dit, le comportement exact du programme à l'exécution dépend du compilateur et de l'architecture de la machine: on ne peut donc pas prédire exactement le comportement calculatoire en raisonnant sur le source.

Typiquement, on peut écrire deux variantes d'un même programme Ada telle que la première variante est plus rapide quand on compile sans optimisation (avec option -O0) alors que la deuxième est plus rapide quand on compile avec le niveau maximal d'optimisation du compilateur (avec option -O3). Autrement dit, si on veut départager ces différentes variantes (qui sont donc en fait plutôt quatre, si on regarde le binaire généré) par une analyse algorithmique, il faudra raisonner au niveau des programmes assembleurs générés par le compilateur.

En conclusion, le choix du niveau d'abstraction dans lequel on formule l'algorithme (langage naturel, langage de programmation de haut niveau, assembleur, etc) détermine la granularité avec laquelle on peut parler du comportement à l'exécution. Mais généralement, c'est en raisonnant à des niveaux abstraits (langage naturel) qu'on trouve les optimisations de calcul les plus significatives !

Générique

Un algorithme est généralement adaptable pour différents langages de programmations, pour différentes structures de données, etc. Voir l'exemple du TriFusion ci-dessus.

Généralement informel

Formaliser complètement un algorithme reviendrait en quelque sorte à le programmer. Il faudrait pour cela formaliser aussi le caractère générique de l'algorithme. Cela peut être intéressant à faire car cela donne un programme réutilisable directement dans de nombreux contextes. Mais, une formalisation extrême de cette généricité peut aussi conduire à une programmation trop lourde (instancier le programme dans les différents contextes peut devenir plus laborieux que de reprogrammer l'algorithme) et surtout peu efficace (dans un contexte particulier, on peut souvent optimiser l'algorithme).

Mathématique

Pour un algorithme donné, on essaye de bien préciser les hypothèses importantes pour la correction et l'analyse de coût, en évitant de contraindre inutilement les implémentations. L'algorithme permet de poser des équations de coût qu'on essaye ensuite de résoudre.

Approximatif et empirique

Le caractère informel donne une grande souplesse: essayer de tout formaliser serait trop lourd. Mais attention, on peut facilement faire des erreurs de raisonnement.

Typiquement la plupart du temps: on suppose IMPLICITEMENT que les opérations arithmétiques (addition, multiplications) ont un coût constant (indépendant de la taille des nombres en jeu). Cette hypothèse est vraie en pratique quand on utilise les entiers (bornés) machines: chaque opération correspond grosso-modo à une instruction machine effectuée en un cycle d'horloge. Mais évidemment, cette hypothèse devient fausse si on utilise des entiers non bornés implémentés au niveau logiciel. D'une part, le coût en temps des opérations va dépendre de la taille des entiers. D'autre part, une multiplication sera plus coûteuse qu'une addition. Ça peut remettre en cause complètement l'analyse de coût d'un algorithme.

Plus généralement, la démarche de l'algorithmique elle-même peut sembler pleine de paradoxes pour un mathématicien. Dans les analyses de coût, on suppose que certaines opérations ont un coût constant (ex: les opérations arithmétiques) car on travaille en pratique sur un domaine fini (les entiers machines), mais en même temps, on s'intéresse au comportement asymptotique (c'est-à-dire pour des entiers qui tendent vers l'infini!). Ce comportement asymptotique peut en effet donner une bonne idée de ce qui se passe quand les données sont grandes (mais il ne dit rien du tout de ce qui se passe quand les données sont petites). En fait, les modèles algorithmiques sont en général une approximation grossière de la réalité: mais il est très difficile de faire mieux. Ceci montre que les résultats théoriques doivent être validés par des expérimentations pratiques.

Conclusion

L'algorithmique est donc un domaine assez difficile qui navigue entre deux écueils: l'excès de rigueur qui donne des problèmes mathématiques trop complexes à résoudre et donc n'amène aucun résultat, et l'excès d'approximations qui donne des résultats très loin de la réalité.

Il y a une littérature très abondante en algo: dans la vraie vie, si vous avez un problème à résoudre, il y a de très forte chance qu'il existe déjà des algorithmes pour traiter ce problème (ou un problème similaire). Un objectif du cours est de vous donner une "culture de base" dans le domaine, de manière à pouvoir vous rendre autonome dans cette littérature. Comme on l'a déjà dit, une difficulté du domaine vient du fait que les modèles sont rarement complètement explicités: les hypothèses implicites font partie de la culture justement.

Liens

Algorithmique 2 : Ada

page Algo1 du Kiosk