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 :

inutile ← 0
Pour i allant de 0 à  9
    Afficher : i

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 ?

Mystere2
_______________________________________
entrée : liste L (non vide) de nombres
sortie : à vous de dire
_______________________________________

     somme ← 0
     Pour k allant de 1 à taille(L) # choix de commencer la numérotation du tableau à 1
          somme ← somme + L[k]

     Sortir : somme / taille(L)

Exercice

En vous basant sur le pseudo-code ci-dessus et sachant que la condition "si" peut s'écrire :

Si condition
    ...

Ecrivez un pseudo code permettant de retourner le maximum d'une liste.