Un algorithme est une suite d’instructions élémentaires appliquées dans un ordre déterminé portant sur un nombre fini de données pour arriver, en un nombre fini d'étapes, à un certain résultat.
Il faut savoir que les algorithmes ont été développés bien avant l'arrivée de l'informatique. Et que l'on sent sert tous les jours, par exemple lors ce que l'on cuisine.
Tout commence vers -1800 : ou apparaissent les plus anciens algorithmes connus (il y a presque quatre millénaires). C'étaient les Babyloniens (habitant de Mésopotamie, actuel Irak) qui utilisaient des algorithmes pour résoudre certaines équations (comme celles du second degré). Voici l'image d'une tablette datant de cette période où plusieurs problèmes du second degré sont résolus par une 'sorte' de liste d'instructions proche de nos algorithmes actuels :
Vers -300 : Euclide, un mathématicien grec, propose un algorithme, encore utilisé de nos jours, permettant de trouver le plus grand diviseur commun (le PGCD) entre deux nombres entiers.
Vers 800 : l'appellation Algorithme est nait du nom latinisé du grand mathématicien Al-Khwârizmî. Ce savant, ayant vécu entre 780 et 850, répertoria tous les algorithmes connus à son époque, et écrira deux livres importants : le premier a conduit au mot « algèbre » actuel ; le second a permis la diffusion du système de numération décimal actuel à travers le monde abbasside puis en Europe : ce sont les « chiffres arabes » actuels.
Au XVII siècle, des machines, des calculateurs mécaniques, ont été construits pour réduire les temps et surtout les risques d'erreurs de calcul. Voici l'image de la toute première calculatrice construite par Blaise Pascal en 1645 capable d'effectuer des additions et des soustractions : la Pascaline.
Au XIX siècle, le mathématicien, Charles Babbage, exaspéré par les nombreuses erreurs présentes dans les tables utilisées pour faire des calculs compliqués en sciences (astronomie, physique, ...), conçoit les plans d'une machine capable de calculer et surtout d'éditer les valeurs de fonctions polynomiales. En 1843, Ada Lovelace, qui a travaillé un temps avec Charles Baggage, écrit le premier algorithme exécutable sur une machine : c'est la création du premier programme informatique
En 1936 Alan Turing développe le concept de machine universelle, qui est capable d’exécuter tous les algorithmes. Ce concept permet de regrouper les notions de machine, d'algorithme, de langage et d'information. Ils sont désormais pensés comme un tout cohérent.
En 1943, la première machine électronique est construite, nommé le Colossus, elle a été utilisée pour décrypter les codes secrets allemands fondés sur la machine Enigma.
Suivant l'architecture de Von Neumann, le premier ordinateur a été construit en 1948 aux États-Unis. Ces ordinateurs étaient surtout utilisés par les femmes qui travaillaient dans la programmation. Le problème avec les premiers ordinateurs était que le seul langage utilisable par le processeur des ordinateurs est le langage machine. Pour faciliter la communication d'informations avec un ordinateur, des informaticiens ont créé des langages dits de haut niveau qui sont plus simples à utiliser, car plus proches du langage naturel. Il y en a un très grand nombre (FORTRAN (1955), C (1972), PHP (1994), JAVA (1995), Javascript (1995), ...) Celui que nous utilisons énormément est le langage PYTHON, créé en 1991 par Guido Von Rossum.
Le pseudo-code est un langage qui sert à écrire clairement et formellement un algorithme dans un langage 'universel'. C'est à dire que vu qu'il existe un très grand nombre de langages différentes, il est commode d'utiliser une sorte de lingua franca et donc le pseudo-code. Il exprime des idées formelles dans une langue près du langage naturel de ses usagers (pour nous, le français) en lui imposant une forme rigoureuse. Il n'y a pas de standard normalisé mais seulement des conventions partagées par un plus grand nombre de programmeurs. Ce langage ressemble de près aux langages de programmation comme le Pascal, C# ou C++, sans être identique à l'un ou à l'autre.
Quelques règles :
Les variables servent à stocker une ou plusieurs informations dans un programme informatique. Ces informations sont des valeurs, c'est à dire qu'il peut s'agir de données issues du disque dur, fournies par l’utilisateur (frappées au clavier), ... ou les résultats obtenus par le programme, intermédiaires ou définitifs. Elles peuvent être de plusieurs types : des nombres, du texte, ...
Dans l’ordinateur, il y a un emplacement de mémoire, repéré par une adresse binaire. Si on programmait dans un langage directement
compréhensible par la machine, on devrait designer nos données par l'écriture en héxadécimal (0002).
L'écriture hexadécimal est un langage qui portent le nom d’assembleur.
Les langages informatiques plus évolués (ce sont ceux que presque tout le monde emploie) se chargent précisément,
entre autres rôles, d’épargner au programmeur la gestion fastidieuse des emplacements mémoire et de leurs adresses. Et,
comme vous commencez à le comprendre, il est beaucoup plus facile d’employer les variables de son choix, que de devoir manier
des adresses binaires.
Il existe de nombreux types de variables utilisés, voici une liste de quelques un:
Le fait de déclarer en pseudo-code le type de la variable n'est pas une obligation, mais vous
Le verrez dans de nombreux sites car de nombreux langages de programmation nécessitent un typage strict.
Le langage PYTHON est auto-typé, c'est-à-dire le typage se fait lors de l'affectation (signe: ←).
IF THEN ELSE est une instruction conditionnelle, qui teste une expression booléenne (condition après le if) et exécute soit un bloc d'instruction (ou plusieurs) si la condition est vraie (bloc 1 après le then) soit un éventuel autre bloc d'instruction (ou plusieurs) si la condition est fausse (bloc 2 après le else)
Illustration :
1. If condition then
2. bloc 1
3. else
4. bloc 2
Voici une manière imagée de visualiser cette instruction :
Remarques:
Vous pouvez pratiquer du pseudo-code en français ou utiliser l'anglais (il faut vous habituer à lire du pseudo-code en anglais). Une version francisée avec une identification des blocs différents pourrait être :
1. Si condition alors
2. bloc 1
3. sinon
4. bloc 2
Voici un exemple d'algorithme affichant le signe d'un nombre a saisi par l'utilisateur :
1. LIRE a
2. if a>0 then
3. ECRIRE "a positif"
4. else
5. ECRIRE "a négatif"
L'instruction Pour est utilisée lorsque le nombre d'itérations est connu à l'avance : elle initialise un compteur, l'incrémente(c'est-à-dire l'augmente de 1) après chaque exécution du bloc d'instructions, et vérifie que le
Illustration :
1. For compteur ← entier1 to entier2
2. bloc d'instructions
On peut préciser le pas d'incrémentation du compteur. Par défaut le pas est de 1. Le mot clé en anglais pour le pas est le mot STEP.
Voici une illustration de l'algorithme suivant :
1. For i←1 to 4
2. bloc d'instructions
L'instruction While est utilisée lorsque le nombre d'itérations n'est connu à l'avance : elle répète l'exécution le bloc d'instructions tant que la condition est vraie.
1. while condition vraie
2. bloc d'instructions
Une manière de visualiser cette instruction, sous forme d'algorigramme :
Exemple: Voici un algorithme affichant tous les carrés inférieurs à 50 :
1. i ← 0
2. while i*i < 50
3. ÉCRIRE i*i
4. i ← i+1
Remarques :
Il faut prendre l'habitude de commenter ses algorithmes et ses programmes.
Remarques :
Exemple : Voici l'algorithme sans les commentaires :
1. n ← O
2. p ← 50
3. while p < 100
4. p←p*1.1
5. n←n+1
6. ÉCRIRE n
Il existe différentes façons de noter un commentaire : //, #, <- ->
Voici le même algorithme avec les commentaires :
// Cet algorithme cherche la valeur de n pour que p passe de 50 à 100 avec une augmentation de 10%
1. n←O //Initialisation de n
2. p←50 //Initialisation de p
3. while p<100
4. p←p*1.1 // suivie de 10% d'augmentation
5. n←n+1 //Incrémentation de n
6. ÉCRIRE n
Avec trop de commentaires, le code devient illisible. Sans commentaire, le code est incompréhensible. A vous de trouver le juste milieu.
Il existe différentes manières de réaliser une trace de programme et/ou d'algorithme. Une trace :
Dans la mesure du possible, on peut organiser une trace d'exécution d'un algorithme en constituant un tableau avec toutes les variables de l'algorithme. Il faut numéroter toutes les lignes de votre algorithme. En colonne, il faut indiquer le nom des variables et en ligne les numéros de ligne.
Exemple : Il faut commencer par numéroter toutes les lignes de l'algorithme.
1. r←0
2. while r*r<= n
3. r←r+1
4. r←r-1
Voici une trace de l'algorithme avec n=5. Quelle est la valeur de la variable r ?
À la fin de l'algorithme, la variable r a pour valeur 2.
Mais nous allons favoriser des traces de ce type :
Un autre exemple avec un appel de fonction :
Voici quelque symboles importants :
<> signifie "diffèrent de"
Exercice 7
Exercice 17
Exercice 18
Exercice 19
Exercice 20
Exercice 21
Exercice 22
08/10
Nous sommes évalués sur docshare, ou nous avons dû crée un appel de fonction. Voici mon travail qui a été note 19/20.
