Algorithmique

1. Définitions

« Un algorithme est une procédure de résolution de problème, s'appliquant à une famille d'instances du problème et produisant, en un nombre fini d'étapes constructives, effectives, non-ambiguës et organisées, la réponse au problème pour toute instance de cette famille. » Simon Modeste.

Une instance (« un exemple ») d’un problème est une entrée (satisfaisant aux contraintes, quelles qu’elles soient, imposées dans l’énoncé du problème) requise par le calcul d’une solution au problème.

Pour un problème donné, il peut exister plusieurs algorithmes possibles... ou aucun. Cependant, ces algorithmes ne se valent pas !
Lequel choisir ?

• le plus efficace

• le plus rapide

• le plus efficient...

2. Complexité d'un algorithme

La complexité permet d'estimer, à priori, l'efficacité intrinsèque de la méthode mobilisée par un algorithme indépendamment de la machine, du langage de programmation, du compilateur et de tous les détails d'implémentation.

Dit en d'autres mots, la complexité permet d'avoir un ordre de grandeur :

• du temps d’exécution d’un algorithme : on parle alors de complexité en temps ;

• et l’espace mémoire mobilisé pour contenir et manipuler le programme et ses données : on parle alors de complexité en espace.

Dans cette partie, nous ne nous préoccupons que de la complexité temporelle des algorithmes.

Réaliser un calcul de complexité en temps revient à décompter le nombre d’opérations élémentaires (affectation, calcul arithmétique ou logique, comparaison…) effectuées par l’algorithme.

Pour rendre ce calcul réalisable, on admet que toutes les opérations élémentaires (chaque ligne du pseudo-code) sont à égalité de coût. En pratique, ce n'est pas tout à fait exact mais cette approximation est cependant raisonnable.

3. Applications des algorithmes

Les applications concrètes des algorithmes sont innombrables (Le classement, l'Internet, le commerce électronique, le séquençage du génome d'un virus, l'intelligence artificielle...).
L'algorithmique est l'étude des algorithmes.

4. Pseudo-code

4.1. Définition :
En programmation, le pseudo-code est une façon de décrire un algorithme en respectant certaines conventions, mais sans référence à un langage de programmation en particulier.
L'écriture en pseudo-code permet de développer une démarche structurée, en « oubliant » temporairement la syntaxe rigide d'un langage de programmation.

4.2. Convention :
Il n'existe pas de convention universelle pour le pseudo-code.
Pour la suite :

• Déclaration des variables :
  Exemples : a est un entier ;
  x est une chaîne de caractères.

• Affectation : x ← \(10\) : on affecte à la variable x la valeur \(10\) ;

  verite ← True : on affecte à la variable verite la valeur True ;

• Bloc Si :
  Si \(expression\) Alors
  affirmation_si_vrai
  ...
  Sinon
  affirmation_si_faux
  FinSI
  

• Bloc Pour
  Pour \(i\) variant de \(début\) à \(fin\) Faire
  affirmation
  FinPour
  

• Bloc Tant que
  Tant que \(expression\_vraie\) Faire
  affirmation
  FinTantque
  

• A[\(i\)] : l'élément de rang \(i\) dans le tableau A, on suppose que les éléments du tableau sont numérotés à partir de \(0\) ;

• A[\(i,j\)] : Élément en ligne \(i\) et en colonne \(j\) du tableau A ;

• A[\(i..j\)] : de l'élément de rang \(i\) à l'élément de rang \(j\) (exclu) du tableau A ;

• Fonction :
  fonction nom_fonction(paramètres)
corps
résultat
  

• Commentaire : # Ceci est un commentaire

• Spécification : """\(Ceci\) \(est\) \(une\) \(spécification\)"""

Notation : \(affirmation\) est soit une instruction soit un bloc d'instructions.