Algorithmes

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 : Ordre de grandeur (c'est le cas par défaut sur ce site, mais vous pouvez le modifier par le lien en bas de page).

Ordre de grandeur(f(n))Ordre de grandeur(g(n())Ordre de grandeur(f(n))Ordre de grandeur(f(n())

La complexité de l'algorithme Ordre de grandeur(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) ∈ '. $brolMeth->addThetaItem(). '(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) = '. $brolMeth->addThetaItem(). '(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 |
  | Ordre de grandeur(1) | complexité constante (indépendante de la taille de la donnée) | fonction head() |
  | Ordre de grandeur(log(n)) | complexité logarithmique (ou sub-linéaires) | |
  | Ordre de grandeur(n) | omplexité linéaire | recherche simple du plus grand élément d'un tableau |
  | Ordre de grandeur(n log(n)) | complexité quasi-linéaire | tri par fusion |
  | Ordre de grandeur(n2) | complexité quadratique | tri par sélection |
  | Ordre de grandeur(n3) | complexité cubique | multiplication de matrices |
  | Ordre de grandeur(nlog(n)) | complexité quasi-polynomiale | |
  | Ordre de grandeur(nk) | complexité polynomiale | |
  | Ordre de grandeur(2√n) | complexité superpolynomiale | |
  | Ordre de grandeur(2n) | complexité exponentielle | borne supérieure d'un calcul inéfficace d'une suite de Fibonacci |
  | Ordre de grandeur(nn) | complexité superexponentielle | |
  | Ordre de grandeur((22n) | complexité superexponentielle | |
  | Ordre de grandeur(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 |
Ordre de grandeur(k*f(n)) = Ordre de grandeurf(n)) | | Multiplier une fondtion par une constante ne modifie pas l'ordre de grandeur de la fonction |
Ordre de grandeur(f(n) + g(n)) = Ordre de grandeur(f(n)) | si Ordre de grandeur(g(n)) ≤ Ordre de grandeur(f(n)) | Nous conservons celui qui croît le plus rapidement |
Ordre de grandeur(f(n)k) ≤ Ordre de grandeur(f(n)l) | si 0 ≤ kl | |
Ordre de grandeur(nl) ≤ Ordre de grandeur(kn) | si k > 1 | Les fonctions exponentielles croissent plus rapidement que les fonctions polynomes |
Ordre de grandeur(ln) ≤ Ordre de grandeur(kn) | si k > l | Dans le cas de 2 fonctions de même exposant, nous conservons la plus grande base |
Ordre de grandeur(f(n)) * Ordre de grandeur(g(n)) = Ordre de grandeur(f(n) * g(n)) | | |
Ordre de grandeur(max(f(n),g(n))) = Ordre de grandeur(f(n)) | si Ordre de grandeur(g(n)) ≤ Ordre de grandeur(f(n)) | |

 

  • 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é :
  • Divers
  • Cryptologie
  • Axiomes
  • Matrices
  • Graphes 
    • Parcourir un graphe
    • 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 Ordre de grandeur(n3).
      • 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 Ordre de grandeur(n2).
      • Algorithme de Moore-Dijkstra (circuits nécessaires, poids positifs ou nuls), complexité de Ordre de grandeur(n2).
      • Algorithme de Ford-Bellman (avec ou sans circuits, détection de circuits absorbants, poids quelconques), complexité de Ordre de grandeur(n3).
      • 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[1], ou ACM[2])
      • 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é
      • Construire les composantes simplement connexes d'un graphe (via DFS), complexité de Ordre de grandeur(m+n).
      • Construire les composantes fortement connexes d'un graphe
      • Décomposer en niveaux. (sans circuit), complexité de Ordre de grandeur(n2).
      • Aide à la décision multicritère : ELECTRE

 

Document créé le 03/02/04 23:17, dernière modification le 22/08/17 12:54
Source du document imprimé : https://www.gaudry.be/algorithmes.html

L'infobrol est un site personnel dont le contenu n'engage que moi. Le texte est mis à disposition sous licence CreativeCommons(BY-NC-SA). Plus d'info sur les conditions d'utilisation et sur l'auteur.

Notes

  1.  ARPM : Arbre Recouvrant de Poids Minimum

  2.  ACM : Arbre Couvrant Minimum

 

Références

  1. livre Langue du document: fr Cours de Théorie des Graphes et réseaux de Petri : JP Leclercq, INFOB321 - Théorie des graphes (Septembre 2008)
  2. livre Langue du document: uk Algorithms, programs and programming languages : ECIS, Computer Science (2004)
  3. livre Langue du document: uk Processing Algorithms : ECIS, Initiation into Computer Science (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.