Algorithmes

Inhoudsopgave

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 :

Fais bouillir de l'eau.
Mets du café dans la tasse.
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 :

Fais bouillir de l'eau :
1. Remplis la bouilloire.
2. Allume la bouilloire.
3. Attends que l'eau soit bouillante.
4. Éteins la bouilloire.
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.

Inhoudsopgave Haut

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.

Inhoudsopgave Haut

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)

Inhoudsopgave Haut

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.

Inhoudsopgave Haut

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) | omplexité linéaire | recherche simple du plus grand élément d'un tableau |

(n log(n)) | complexité quasi-linéaire | tri par fusion |

(n²) | complexité quadratique | tri par sélection |

(n³) | complexité cubique | multiplication de matrices |

(n^log(n)) | complexité quasi-polynomiale | |

(n^k) | complexité polynomiale | |

(2^√n) | complexité superpolynomiale | |

(2ⁿ) | complexité exponentielle | borne supérieure d'un calcul inéfficace d'une suite de Fibonacci |

(nⁿ) | complexité superexponentielle | |

((2²ⁿ) | complexité superexponentielle | |

(n!) | complexité factorielle | |

Inhoudsopgave Haut

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 | |

(n^l) ≤

(kⁿ) | si k > 1 | Les fonctions exponentielles croissent plus rapidement que les fonctions polynomes |

(lⁿ) ≤

(kⁿ) | 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)) | |

Inhoudsopgave Haut

Quelques liens relatifs aux algorithmes

Paradigmes :
- diviser pour régner (diviser la complexité ou le nombre de données à traiter)
- programmation dynamique (mémoïsation : éviter de recalculer les mêmes valeurs en mémorisant le résultat)
- algorithmes gloutons (résolution locale de petits problèmes de manière optimale)
- Générer et tester
- Branch and bound (utilisation de bornes, élaguage d'une partie de l'arbre)
- analyse amortie (mesure de la robustesse dans le pire des cas)
Complexité :
- Tri par échanges (exchange sort ou bubble sort)
- Tri par sélection (selection sort)
- Tri par insertion (insertion sort)
- Tri Shell (shell sort), amélioration du tri par insertions
- Tri par tas (heap sort)
- Tri par fusion (merge sort)
- Tri rapide (quick sort)
Divers
- Suite de Fibonacci
Cryptologie
- DES
- RSA
- MD5
Axiomes
Matrices
Graphes
- Parcourir un graphe
  - Parcours en profondeur d'abord : Algorithme DFS (Depth First Search), complexité de (m), et de (n²) dans le pire des cas.
    - Algorithme DFS de Tarjan
    - Algorithme de Malgrange basé sur DFS
  - Parcours en largeur d'abord : Algorithme BFS (Breadth First Search), complexité de (m).
    - Implémentation de BFS par Linden
  - Parcours en largeur lexicographique : Algorithme Lex-BFS (Lexicographic Breadth First Search
- Chemins et circuits
  - Détecter la simple présence d'un chemin entre 2 sommets
  - Détecter un chemin de longueur déterminée entre 2 sommets
  - Calculer le nombre de longueur déterminée (>1) entre 2 sommets
  - Calculer la matrice M ou M' : Algorithme de Warshall, complexité de (n³).
  - Détecter un circuit dans un graphe
  - Détecter un circuit passant par un sommet donné
  - Détecter un circuit passant par un arc donné
- Rechercher un ou plusieurs chemins extrémaux des graphes pondérés (les plus courts ou les plus longs)
  - Algorithme de Bellman-Kalaba (pas de circuits), complexité de (n²).
  - Algorithme de Moore-Dijkstra (circuits nécessaires, poids positifs ou nuls), complexité de (n²).
  - Algorithme de Ford-Bellman (avec ou sans circuits, détection de circuits absorbants, poids quelconques), complexité de (n³).
  - Heusistique A* (avec ou sans circuits, bornes, et sommet destination pré-déterminé)
  - Algorithme de Floyd-Warshall (accepte les poids négatifs, mais pas de cycle strictement négatif)
  - Algorithme de Ford-Dantzig (graphe orienté, avec ou sans circuit, poids positifs et négatifs)
- Arbres couvrant (ARPM¹, ou ACM²)
  - Algorithme de Kruskal (graphe connexe, valué, non orienté)
  - Algorithme de Prim (graphe connexe, valué, non orienté)
- Flux extémaux (minimum ou maximum)
  - Algorithme de Ford-Fulkerson
  - Algorithme de Edmonds-Karp
  - Algorithme de flux bloquant de Dinitz
- Divers
  - Construire la fermeture transitive d'un graphe orienté ou non orienté
    - Algorithme de Warshall, complexité de (n³).
    - Algorithme de Minoux (sans circuit), complexité entre (n³) et (∑d^int_j . d^ext_j) (Minoux et Bartnik).
  - Construire les composantes simplement connexes d'un graphe (via DFS), complexité de (m+n).
  - Construire les composantes fortement connexes d'un graphe
    - Algorithme de Foulkes, complexité de (n³).
    - Algorithme de Malgrange, complexité de (m * nombre d'exécutions), de (n³) dans le pire des cas.
  - Décomposer en niveaux. (sans circuit), complexité de (n²).
  - Aide à la décision multicritère : ELECTRE

Nederlandse vertaling

U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.

Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.

Bij voorbaat dank.

Document heeft de 03/02/2004 gemaakt, de laatste keer de 07/03/2020 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/algorithmes.html

De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de auteur.

Notes

↑ ARPM : Arbre Recouvrant de Poids Minimum
↑ ACM : Arbre Couvrant Minimum

Inhoudsopgave Haut

Referenties

INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (September 2008)
Computer Science : ECIS, Algorithms, programs and programming languages (2005)
Initiation into Computer Science : ECIS, Processing Algorithms (2005)

Deze verwijzingen en links verwijzen naar documenten die geraadpleegd zijn tijdens het schrijven van deze pagina, of die aanvullende informatie kunnen geven, maar de auteurs van deze bronnen kunnen niet verantwoordelijk worden gehouden voor de inhoud van deze pagina.
De auteur Deze site is als enige verantwoordelijk voor de manier waarop de verschillende concepten, en de vrijheden die met de referentiewerken worden genomen, hier worden gepresenteerd. Vergeet niet dat u meerdere broninformatie moet doorgeven om het risico op fouten te verkleinen.

Inhoudsopgave Haut