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 : 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) ∈ Ordre de grandeur(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) = Ordre de grandeur(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.

 NotationType 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)complexité linéairerecherche simple du plus grand élément d'un tableau
 Ordre de grandeur(n log(n))complexité quasi-linéairetri par fusion
 Ordre de grandeur(n2)complexité quadratiquetri par sélection
 Ordre de grandeur(n3)complexité cubiquemultiplication 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é exponentielleborne supérieure d'un calcul inéfficace d'une suite de Fibonacci
 Ordre de grandeur(nn)complexité superexponentielle 
 Ordre de grandeur(22n)
 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èmeConditionInformations
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 > 1Les fonctions exponentielles croissent plus rapidement que les fonctions polynomes
Ordre de grandeur(ln) ≤ Ordre de grandeur(kn)si k > lDans 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)) 

 

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é :
  • 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

 

Réseaux sociaux

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Nuage de mots clés

13 mots clés dont 0 définis manuellement (plus d'information...).

Avertissement

Cette page ne possède pas encore de mots clés manuels, ceci est donc un exemple automatique (les niveaux de pertinence sont fictifs, mais les liens sont valables). Pour tester le nuage avec une page qui contient des mots définis manuellement, vous pouvez cliquer ici.

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher le nuage de mots clés.

 

Notes

  1.  ARPM : Arbre Recouvrant de Poids Minimum

  2.  ACM : Arbre Couvrant Minimum

 

Références

  1. livre Langue du document: fr IHDCB331 - Méthodes de Programmation : PY Schobbens, Cours de Méthodes de Programmation (Septembre 2009)
  2. livre Langue du document: uk Computer Science : ECIS, Algorithms, programs and programming languages (2004)
  3. livre Langue du document: uk 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.

 

Historique et modifications de la page

  • Dimanche 18 Octobre 2009, 08:31 : Ajout de la notion de complexité et des liens vers les types d'algorithmes.
Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-266
Document créé le 04/02/04 00:17, dernière modification le Vendredi 17 Juin 2011, 12:11
Source du document imprimé : http:///www.gaudry.be/algorithmes.html
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Apparence (afficher)
Stats (afficher)
15838 documents
455 astuces.
550 niouzes.
3107 definitions.
447 membres.
8121 messages.

Document genere en :
0,07 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
La vie a beaucoup plus d’imagination que nous.

François Truffaut [Les 400 coups]
 
l'infobrol
Nous sommes le Dimanche 28 Mai 2017, 05:14, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)