Algorithmes

Sommaire du document

Nous ne ferons pas des algorithmes pour le plaisir : un algorithme doit fournir une solution à un problème.
Il est donc primordial de savoir exactement ce que nous désirons faire (analyse du problème).

Ensuite, nous devons donc savoir ce que peut réaliser le processeur, pour déterminer le type et le niveau d'affinage auquel nous devrons soumettre notre algorithme.
Il faut savoir que le processeur ne peut réaliser que de très simples opérations. Il est de plus totalement dépourvu de tout sens de l'initiative. Comment dès lors lui demander de faire quelque chose?

Nous devons tenter de découper ce que nous désirons faire en une multitude de tâches plus simples, ces tâches étant elles aussi découpées en sous tâches, jusqu'au moment ou nous nous trouvons en possession d'une liste d'instructions que nous pouvons fournir au processeur car il en comprend la signification.

Un algorithme est donc une manière de décrire les différentes actions à entreprendre; il doit pouvoir être compris par une autre personne, exempt de toute ambiguïté, indépendant de tout langage de programmation, concis, et facilement découpé en séquences.

Exemple d'algorithme

Je peux dire à quelqu'un : "sert moi une tasse de café, s'il te plait".
En admettant que la personne comprenne ma langue ( et soit assez aimable ), il est probable que cette phrase suffise.

Il est impossible de demander une tasse de café de la même manière à un processeur.
Je dois donc découper ma demande :

1. Fais bouillir de l'eau.
2. Mets du café dans la tasse.
3. Mets de l'eau dans la tasse.

Nous avons donc notre premier algorithme.
Comme notre processeur ne sait toujours pas ce que signifie "faire bouillir de l'eau", nous devons affiner l'algorithme :

1. Fais bouillir de l'eau :
   1. Remplis la bouilloire.
   2. Allume la bouilloire.
   3. Attends que l'eau soit bouillante.
   4. Éteins la bouilloire.
2. Mets du café dans la tasse.

Nous devons donc affiner notre algorithme jusqu'au moment où chaque instruction peut être réalisée par le processeur.

Logique, syntaxe et sémantique

Avant d'aller plus en avant, il est important de comprendre les notions de syntaxe et de sémantique.
Ces deux notions sont étroitement liées à notre futur algorithme, et en cas d'erreur, nous situerons précisément ce qu'il faut corriger.
Lors de l'utilisation d'un IDE (environnement intégré de développement), les messages d'erreurs retournés par notre compilateur spécifieront par exemple si l'erreur est syntaxique.

La syntaxe est un ensemble de conventions qui régissent l'écriture.
Par exemple, chaque phrase débute par une majuscule et se termine par un point.

La sémantique est le sens, la signification de la phrase ou de l'instruction.
Par exemple, la phrase "Un est plus grand que deux." est syntaxiquement correcte, mais présente une erreur de sémantique.

Exemple : calcul de l'addition de deux nombres a et b.

r = a - b ;
Une erreur de logique ne peut être détectée par le compilateur : les instructions s'effectuent correctement, mais le résultat n'est pas celui attendu.

r = a; + b
Le délimiteur de fin d'instruction (;) est placé au milieu de l'instruction.
Une erreur de syntaxe est détectée à la compilation.

r = a + 'b' ;
Le programme est prévu pour additionner deux nombres, et b est considéré ici comme un caractère et pas comme une variable.
La syntaxe de l'instruction est correcte, mais pas la sémantique.
Une erreur de sémantique est détectée à la compilation.

Structure des algorithmes

Nous verrons dans les pages suivantes que diverses notions nous seront nécessaires dans la conception des algorithmes :

• Séquence.
• Sélection.
• Itération ( boucles ).
• Modularité.
• Récursivité.

La structure de nos algorithmes répondra le plus souvent à trois grands principes :

• Combinaisons : nous n'allons pas réinventer la roue, donc nous utiliserons des fonctions simples, que nous combinerons pour obtenir des fonctions plus élaborées
• Branchements : nous agirons de manière différente selon certains états ou selon les résultats de certains tests (si ceci est vrai alors je fais ceci, sinon je fais celà)
• Itérations : nous utiliserons des boucles ou des récursions afin d'éviter de coder chaque passage dans une opération répétitive (dont nons ne pouvons parfois même pas déterminer le nombre de passages à l'avance)

Avant de conçevoir un algorithme

Avant de travailler sur un algorithme, nous devons nous poser quelques questions :

• réalisabilité : nous devons nous demander si la tâche à exécuter est réalisable par un ordinateur (computability). Par exemple, il est peu réaliste de tenter un algorithme de création d'algorithmes.
• complexité : la tâche à accomplir est réalisable par un ordinateur, mais les ressources que nécessiterait l'exécution d'un tel algorithme ne sont-elles pas trop élevées ?
• robustesse : nous devons aussi penser à une série de tests pour vérifier les résultats de l'algorithme, mais pouvons-nous avoir la certitude de l'exactitude sans faille dans tous les cas de notre algorithme ? La seule certitude que nous pouvons avoir est celle d'un échec, au moment où l'algorithme dévoile ses failles devant une situation hors norme.

Complexité des algorithmes

Nous pouvons considérer la complexité d'un algorithme de différentes manières : dans le temps (temps nécessaire àl'exécution), dans l'espace (quantité de mémoire nécessaire), au niveau des resources (charge du processeur, etc.), mais nous allons nous intéresser ici à la complexité en temps en fonction de la quantité de données à traiter, sans dépendre de facteurs extérieurs tels que la machine sur laquelle l'algorithme est exécuté. Nous parlerons d'ordre de grandeur.

Afin de donner un ordre de gandeur de la complexité d'un algorithme, nous utiliserons la notion d'instruction élémentaire.

Tp(n) correspond au Temps d'exécution de p en fonction de la taille de données n (dans le pire des cas), ce qui correspond au nombre maximal d'instructions élémentaires qui seront exécutées par p sur n'importe quelle entrée de taille n.

Notation de l'ordre de grandeur

Nous pouvons utiliser différentes notations pour spécifier un ordre de grandeur. La notation la plus répendue est Θ, mais nous retrouvons aussi souvent une sorte de O majuscule : (c'est le cas par défaut sur ce site, mais vous pouvez le modifier par le lien en bas de page).

(f(n)) ≤ (g(n()) ∧ (f(n)) ≤ (f(n())

La complexité de l'algorithme (f(n)) s'exprime donc en fonction de la quantité n de données à traiter par une fonction f.

La notation correcte est f(n) ∈ (n), ce qui signifie que la fonction f qui traite une taille de données n appartient à l'ordre de grandeur de n, mais nous utilisons souvent la notation f(n) = (n) par abus de notation.

Tableau d'ordres de grandeur

Le tableau ci-dessous reprend donc les complexités des algorithmes les plus fréquentes.

	Notation	Type de complexité	Exemple
	(1)	complexité constante (indépendante de la taille de la donnée)	fonction head()
	(log(n))	complexité logarithmique (ou sub-linéaires)
	(n)	complexité linéaire	recherche simple du plus grand élément d'un tableau
	(n log(n))	complexité quasi-linéaire	tri par fusion
	(n2)	complexité quadratique	tri par sélection
	(n3)	complexité cubique	multiplication de matrices
	(nlog(n))	complexité quasi-polynomiale
	(nk)	complexité polynomiale
	(2√n)	complexité superpolynomiale
	(2n)	complexité exponentielle	borne supérieure d'un calcul inéfficace d'une suite de Fibonacci
	(nn)	complexité superexponentielle
	(22n)
	(n!)	complexité factorielle

Théorèmes sur la complexité des algorithmes

Situation : variable n ≥ 0, constantes k, l ≥ 0, fonction f(n) ≥ 0

Théorème	Condition	Informations
(k*f(n)) = f(n))		Multiplier une fondtion par une constante ne modifie pas l'ordre de grandeur de la fonction
(f(n) + g(n)) = (f(n))	si (g(n)) ≤ (f(n))	Nous conservons celui qui croît le plus rapidement
(f(n)k) ≤ (f(n)l)	si 0 ≤ k ≤ l
(nl) ≤ (kn)	si k > 1	Les fonctions exponentielles croissent plus rapidement que les fonctions polynomes
(ln) ≤ (kn)	si k > l	Dans le cas de 2 fonctions de même exposant, nous conservons la plus grande base
(f(n)) * (g(n)) = (f(n) * g(n))
(max(f(n),g(n))) = (f(n))	si (g(n)) ≤ (f(n))

Quelques liens relatifs aux algorithmes

Notes

1. ↑ ARPM : Arbre Recouvrant de Poids Minimum
   
   
2. ↑ ACM : Arbre Couvrant Minimum
   
   

Références

1. IHDCB331 - Méthodes de Programmation : PY Schobbens, Cours de Méthodes de Programmation (Septembre 2009)
2. Computer Science : ECIS, Algorithms, programs and programming languages (2004)
3. Initiation into Computer Science : ECIS, Processing Algorithms (2004)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

Structure du document