Algorithme¶
Je me suis en partie inspiré sur ce cours : https://pixees.fr/informatiquelycee/n_site/nsi_prem_intro_algo.html
La notion d'algorithme est souvent associée à l'informatique, pourtant le terme algorithme vient du nom du mathématicien perse du 8ème - 9ème siècle Al-Khuwārizmī. La notion d'algorithme est donc très antérieure à la création du premier ordinateur.
Les algorithmes sont omniprésents, notamment à travers l'intelligence artificielle. Les médias utilisent ce terme en permanence sans jamais l'expliciter. Nous allons les étudier de manière plus rigoureuse.
Définition¶
La première définition dont vous avez peut être entendu parlé en SNT est celle qui consiste à définir un algorithme comme une suite finie d'étapes permettant d'obtenir un résultat à partir d'éléments fournis en entrée.
Exemples :
- Recette de cuisine
- Algorithme d’Euclide pour obtenir le pgcd de deux entiers
- Algorithme de conversion décimal/binaire
- Algorithmes de tris
- Algorithme de recherche d’un fichier dans une arborescence sur un ordinateur
- Algorithme de compression de fichiers (MP3, langage sms)
- Algorithme de plus court chemin (planification de parcours sur un GPS)
Nous allons partir ce cette définition et la préciser pour qu'elle soit adaptée à ce que nous ferons en informatique.
Algorithme
Un algorithme est la spécification d'un schéma de calcul sous forme d'une suite finie d'opérations élémentaires obéissant à un enchainement déterminé.
On peut résumer cette définition par ce schéma :
Les mots importants dans cette définition sont en particulier calcul et élémentaires.
Ordinateur
Comment dit-on "ordinateur" en anglais ?
Nous ferons des calculs, mais non pas uniquement au sens d'opérations arithmétiques, mais au sens défini par Turing et Church dans les fondements théorique de l'informatique.
Nous étudierons les machines de Turing en Terminale, mais voici une vidéo qui explique cela plus en détail :
Cette vidéo est assez complexe donc n'hésitez pas à revenir vers moi si vous avez des questions à ce sujet.
Les opérations (au sens large) doivent être suffisamment atomiques.
Pseudo-code¶
Pour retranscrire notre algorithme nous pouvons utiliser ce qu'on appelle du pseudo-code
, cette description sera à la fois proche du français et suffisamment proche d'un langage de programmation.
Question
Quel peut être l'avantage d'utiliser du pseudo-code plutôt que directement du Python ?
Il n'y a pas de standard pour le pseudo-code, mais nous allons nous appuyer sur ce document de l'école Polytechnique de Lausanne (sans le suivre à la lettre) : télécharger
Exemple de pseudo-code :
Question
A quoi correspond la flêche ← ?
Voici un autre pseudo-code
Mystere
_________________________
entrée : un entier n
sortie : à vous de dire
_________________________
r ← 1
Pour i allant de 1 à n
r ← r * i
Sortir : r
Question
Que fait la fonction Mystere ?
Exercice
Ecrire le code Python correspondant à ce pseudo-code
Exercice
Que fait ce pseudo-code ?