Chapitre 3 : Les logiciels et algorithmique

Principe

Fondamental

Le différence entre un algorithme et un programme est souvent une question de niveau de détail. Un algorithme est souvent exprimé avec une notation indépendante de tout langage de programmation alors qu'un programme est écrit dans un langage de programmation particulier.

Fondamental

Donc un algorithme est un concept, tandis qu'un programme est l'implémentation de ce concept. Ainsi, un programme est entièrement dépendant de la machine qui va l'exécuter, contrairement à un algorithme.

Complément

Une autre différence entre algorithme et programme est que l'exécution d'un algorithme doit toujours se terminer avec un résultat, alors que celle d'un programme peut conduire à une boucle infinie (ne jamais s'arrêter).

Remarque

Un algorithme est donc une méthode pour résoudre un problème particulier dont on est sûr qu'elle trouve toujours une réponse en un temps d'exécution fini.

Exemple

Lisez attentivement !

Il y a dans cette définition (informelle) d'algorithme un problème majeur. Prenons l'exemple des nombres premiers. Pourquoi peut-on supposer que l'on sait comment diviser Ln par Li et vérifier que le résultat est un entier ?

Ne faudrait-il pas avoir un algorithme pour ça aussi ?

Et si jamais on trouve un algorithme pour cette division, ne faudrait-il pas trouver un algorithme pour chaque étape de celle-ci ? Et ainsi de suite. Ou, au contraire, pourquoi ne peut-on pas simplement supposer que ``vérifier si un entier est premier'' est une opération élémentaire ?

Pourquoi est-il nécessaire de trouver un algorithme pour cette opération ?

En d'autres termes : comment savoir si une opération est élémentaire (et ne nécessite par conséquent aucun algorithme) ?

La réponse est qu'une opération est élémentaire lorsque un ordinateur peut l'exécuter très rapidement, en réalité en un nombre relativement faible de cycles d'horloge.

PrécédentPrécédentSuivantSuivant
AccueilAccueilImprimerImprimerRéalisé avec Scenari (nouvelle fenêtre)