Analyse de complexité

La complexité  d’un algorithme est :

• en temps, le nombre d’opérations élémentaires effectuées pour traiter une donnée de taille n ;
• en mémoire, l’espace mémoire nécessaire pour traiter une donnée de taille n.

 

Elle permet d’exprimer l’efficacité d’un algorithme dans la résolution d’un problème, et par conséquent de comparer deux algorithmes.

 

Exemple :

Supposons que l’on dispose de deux ordinateurs. L’ordinateur A est capable d’effectuer 10⁹  instructions par seconde. L’ordinateur B est capable d’effectuer 10⁷  instructions par seconde. Considérons un même problème (de tri par exemple) dont la taille des données d’entrées est n. Pour l’ordinateur A, on utilise un algorithme qui réalise 2n²  instructions. Pour l’ordinateur B, on utilise un algorithme qui réalise 50nlog(n) instructions. Pour traiter une entrée de taille 10⁶: l’ordinateur A prendra 2000s et l’ordinateur B prendra 100s. Ainsi même si la machine B est médiocre, elle résoudra le problème 20 fois plus vite que l’ordinateur A.

 

La complexité est exprimée en fonction du nombre de données et de leur taille. A défaut de pouvoir faire mieux :

• On considère que les opérations sont toutes équivalentes
• Seul l’ordre de grandeur nous intéresse.
• On considère uniquement le pire des cas

 

Pour n données on aura comme exemples de complexités : O(n) linéaire, O(n²) quadratique O(n log(n)),…

 

Notions de programmation

On a besoin d’un formalisme minimum pour décrire un algorithme dans un langage présentant moins de contrainte et de spécificités qu’un langage de programmation (Java, C, Pascal, etc.).

 

Dans la littérature, les algorithmes sont décrits dans un pseudo langage qui ressemble à un langage de programmation, tout en étant plus flexible (on reste souple tant qu’il n’y a pas d’ambiguïté). En cas de besoin, les instructions simples sont séquencées par un « ; ».

 

Tous les pseudo langages recouvrent les mêmes concepts.

Les variables

Elles sont déclarées avec l’indication de leur type.

Exemple :

Booléen b, Entier n, Réel x, Caractère c, Chaîne s, etc.

Ou encore

Bool b, Int n, Float x, Char c, String s, etc.

 

Une variable peut être globale (visible dans tout l’algorithme) ou locale (visible uniquement dans le bloc dans lequel elle a été créée)

 

Les affectations

On pourra représenter l’affectation de la valeur 5 à une variable a de plusieurs manières :

• • a = 5
  •  5             a
  •  a             5

 

Les structures de contrôle

Les blocs d’instructions sont entourés par

• • { … }

ou

• • début … fin

 

Exemples

• • SI

SI (condition) {

instruction1;

instruction2 ;

} SINON {

Instruction3;

}

 

• • POUR

POUR i ALLANT DE min A max {

Instruction1 ;

}

 

 

• • TANT QUE

TANT QUE (condition) {

instruction1 ;

}

 

FAIRE {

instruction1 ;

} TANT QUE (condition)

Les fonctions et procédures

Lorsqu’un algorithme a une certaine longueur, il y’a une forte probabilité de devoir procéder aux mêmes traitements, ou à des traitements similaires, à plusieurs endroits de son déroulement.

La manière la plus évidente de gérer cette situation est de répéter le code correspondant autant de fois que nécessaire. Cette solution, bien qu’elle semble plus simple, pose beaucoup de problèmes.

• • Les répétitions rendent l’algorithme touffu et difficilement lisible, ce qui est un problème important lorsque plusieurs personnes doivent pouvoir le comprendre et/ou le modifier
  • Une telle structure pose des problèmes considérables de maintenance. En effet, en cas de besoin de modification d’un code, il faut traquer toutes les apparitions plus ou moins identiques de ce code, avec les risques d’oubli et d’erreur que cela comporte.

Les procédures et les fonctions sont une solution à ce type de problème. Elles permettent un découpage de l’algorithme en « sous-programmes » pour rendre sa compréhension et son développement plus faciles, en regroupant les instructions d’un traitement dans un module séparé qui peut être ensuite appelé chaque fois que l’on en a besoin.

 

Tandis qu’une fonction renvoie une valeur au programme qui l’a appelée, une procédure n’en renvoie pas. Par exemple, on utilisera une procédure pour regrouper des instructions permettant d’effacer l’écran, d’afficher un message, etc.

 

Lorsqu’on appelle la fonction, on doit lui préciser quelle(s) variable(s) (représentant des informations) elle doit prendre en entrée pour pouvoir produire le résultat attendu. Ces informations sont appelées des paramètres ou des arguments. Ces arguments peuvent être passés :

• Par valeur (toute modification de cette valeur n’est valable qu’à l’intérieur de la fonction)
• Par référence (la variable est manipulée en utilisant sa référence et les modifications faites à l’intérieur de la fonction restent valables après la sortie de la fonction).

Par défaut et sauf précision expresse, les arguments sont passés par valeur.

L’ensemble du nom d’une fonction ou d’une procédure et de ses paramètres est appelé son prototype.

 

Exemple :

Fonction periode(Date dateDebut, Date dateFin) renvoie Entier

Procedure afficheMessage(Chaine msg)

 

Structures de données

Les structures de données sont utilisées :

 

Exemple :

• Les tableaux : Si A est un tableau, A[i] est le ième élément du tableau
• Structure personnalisées : Si P est une structure modélisant un point et x un champ de cette structure représentant l’abscisse du point, P.x est l’abscisse de P

 

Récursivité

On dit qu’un programme est récursif si pour parvenir au résultat voulu il se réemploie lui-même.

Ce mode de programmation permet d’implémenter des boucles dites récursives (les boucles POUR et TANT QUE vues précédemment sont des boucles itératives.)

 

Exemple :

La fonction Factorielle

Factorielle(Entier n) {

if n=0 {

Renvoyer 1 ;

}

sinon {

Renvoyer n*factorielle(n-1) ;

} ;

}

 

Quelques exemples d’algorithmes classiques

Il existe de nombreux algorithmes dits classiques, qui répondent à des problèmes connus et susceptibles d’apparaitre dans la « décomposition » de problèmes plus complexes.

 

Le cours ne s’attardera que sur quelques algorithmes de tri. Ces algorithmes auront tous pour objectif de classer (trier) une liste d’éléments. Ces éléments seront stockés dans un tableau.

 

Tri bulles

Principe :

Le but est de faire un tri croissant.

Le tableau est parcouru de la fin vers le début en utilisant deux compteurs. Chaque fois qu’une valeur du tableau est inférieure à celle qui la précède, les deux valeurs sont permutées. A la fin de tous les parcours du tableau, toutes ses valeurs sont triées

 

Algorithme :

tri_à_bulles (Tableau T) {

Entier i

Entier j

Pour i allant de taille de T – 1 à 1

Pour j allant de 0 à i – 1

Si T[j+1] < T[j]

           Alors

permuter(T[j+1], T[j])

Fin si

       Fin Pour

Fin Pour

}

 

Tri jump-down

Principe :

Le code de ce tri ressemble énormément au tri à bulles. Tout comme le tri à bulles, ce tri fait remonter en premier les plus grands éléments. Toutefois, il ne travaille pas sur des éléments adjacents ; il compare chaque élément du tableau avec celui qui est à la place du plus grand, et échange lorsqu’il trouve un nouveau plus grand.

 

Algorithme :

tri_jump_down(Tableau T) {

Pour i allant de taille de T – 1 à 1

Pour j allant de 0 à i – 1

Si T[i] < T[j]

permuter(T[i], T[j])

Fin Si

Fin Pour

Fin Pour

}

 

Tri bulles optimisé

Principe :

Ce tri est une optimisation courante du tri bulles qui consiste à l’interrompre dès qu’un parcours entier est effectué sans échange. En effet, cela signifie que le tableau est trié. Cette optimisation nécessite une variable supplémentaire.

 

Algorithme :

tri_à_bulles_optimisé (Tableau T) {

Entier i

Entier j

Booléen tableau_trie

Pour i allant de taille de T – 1 à 1

tableau_trié := vrai

Pour j allant de 0 à i – 1

Si T[j+1] < T[j]

permuter(T[j+1], T[j])

tableau_trié := faux

Fin Si

         Fin Pour

Si tableau_trié

Sortir du programme

         Fin Si

     Fin Pour

}