Cours d’algorithmique et structures de données

Notion d’algorithme

Définition

On peut définir un algorithme comme suit :
Résultat d’une démarche logique de résolution d’un problème. C’est le résultat de l’analyse.
Ou encore :
Une séquence de pas de calcul qui prend un ensemble de valeurs comme entrée (input) et produit un ensemble de valeurs comme sortie (output).

Propriétés

On peut énoncer les cinq propriétés suivantes que doit satisfaire un algorithme :
1. Généralité : un algorithme doit toujours être conçu de manière à envisager toutes les éventualités d’un traitement.
2. Finitude : Un algorithme doit s’arrêter au bout d’un temps fini.
3. Définitude : toutes les opérations d’un algorithme doivent être définies sans ambiguïté
4. Répétitivité : généralement, un algorithme contient plusieurs itérations, c’est à dire des actions qui se répètent plusieurs fois.
5. Efficacité : Idéalement, un algorithme doit être conçu de telle sorte qu’il se déroule en un temps minimal et qu’il consomme un minimum de ressources.

Exemples

– PGCD (Plus Grand Commun Diviseur) de deux nombres u et v.
– Algorithme naïf : on teste successivement si chaque nombre entier est diviseur commun.
– Décomposition en nombres premiers.
– Algorithmes de tri
– Algorithmes de recherche
– Recherche d’une chaîne de caractère dans un texte (Logiciels de traitement de texte).
– Recherche dans un dictionnaire.
– … etc.

Remarque

Attention, certains problèmes n’admettent pas de solution algorithmique exacte et utilisable. On utilise dans ce cas des algorithmes heuristiques qui fournissent des solutions approchées.

Langage algorithmique utilisé

Durant ce cours, on va utiliser un langage algorithmique pour la description des différentes solutions apportées aux problèmes abordés. L’algorithme suivant résume la forme générale d’un algorithme et la plupart des déclarations et instructions utilisées.