Cours d’algorithmique by Ph. RIS est mis à disposition selon les termes de la licence Creative Commons Paternité – Pas d’Utilisation Commerciale – Pas de Modification 3.0 Unported.
Introduction
Ce cours d’algorithme est issu de cours donnés dans différentes universités (Université de Franche Comté, Institut Gaspard Monge de Marne-La-Vallée, Université de Lille, Université du Littoral).
I) La logique de base des ordinateurs
Les ordinateurs actuels utilisent le courant comme support de l’information. Lorsque le courant passe dans un circuit (i.e. lorsque l’on a une tension de +5 volt par exemple), on dit que ce circuit est à vrai ou 1. A l’opposé, lorsque aucun courant ne passe dans ce même circuit (0 volt), on dit qu’il est à faux ou 0. Il est très facile de faire passer du courant dans un élément et de détecter dans quel état (vrai ou faux) est ce dernier. C’est pourquoi, dès les tous débuts de l’informatique, les créateurs d’ordinateurs ont utilisé la logique VRAI/FAUX dite également binaire, pour concevoir les ordinateurs.
Toutes les opérations effectuées par l’ordinateur sont faites sur des suites de 0 ou de 1 :
– une information stockée en mémoire est une suite de 0 ou de 1,
– les opérations arithmétiques se font sur des nombres codés avec des 0 et des 1,
– les programmes effectués par les ordinateurs sont finalement interprétés comme des suites de 0 et de 1,
– …
I).1. Définition et manipulation des éléments logiques de base
I.1.a. Le bit
Le plus petit élément de base doit donc coder soit un 1 soit un 0. On l’appel bit (pour Binary unIT). Un bit vaut donc 0 ou 1 (faux ou vrai) à l’exclusion de toute autre valeur.
I.1.b Le mot (byte)
Le bit est cependant une information trop élémentaire pour être facilement manipulée lorsque l’on veut travailler. C’est pourquoi, on regroupe ceux-ci en mots de longueur variable. Les ordinateurs modernes manipulent généralement des mots de 32 bits, c’est-à-dire une suite de trente-deux 0 ou 1.
I.1.c. L’octet
On regroupe souvent les bits par 8 pour les compter. Un groupe de 8 bits forme un octet. Il est à noter qu’il est possible d’avoir des mots faisant un octet de long (soit 8 bits).
(Pièce-jointe : « Octet – Regroupement des bits »)
I.2. Unités pour mesurer les capacités des ordinateurs
L’unité de base est le bit.
Les sous-unités sont des multiples de l’octet. Par exemple, on dira qu’un mot fait 4 octet au lieu de dire qu’il fait 32 bits.
Pour mesurer la taille d’un programme par exemple, on utilisera un multiple de l’octet qui est le kilo-octet (Ko). 1 Ko vaut 1024 octet (les informaticiens utilisent des kilos de 1024 au lieu de 1000 classiquement, car ils comptent en multiples de 2 ; 1024 = 2*2*2*2*2*2*2*2*2*2 (10 fois) ).
Pour mesurer la capacité d’une disquette, on utilisera le méga-octet (Mo) qui vaut 1024 Ko ou encore 1024*1024 octet.
Enfin, il existe des unités plus grandes pour mesurer les grandes capacités de stockages par exemple :
– le giga-octet (Go) qui vaut 1000 Mo (et non 1024 !),
– le tera-octet (To) qui vaut 1000 Go,
– …
II. L’algorithmique
Construire un programme revient à décomposer un problème en un certain nombre d’étapes élémentaires qui vont permettre de le résoudre :
– décomposer l’ensemble des informations dont on dispose en données exploitables par le programme,
– déterminer le résultat à obtenir,
– décomposer le problème en étapes élémentaires de traitement (on avance pas à pas dans la résolution de celui-ci) permettant de passer des données au résultat.
Il existe des méthodes permettant de formaliser ces étapes :
– méthode du style Meurise,
– décomposition en organigramme,
– …
Exemple d’organigramme : (pièce-jointe : « Organigramme concernant la construction d’un programme »)
Exemple d’analyse de problème : on souhiate préparer du café, voici comment on pourrait décomposer le problème.
Données du problème :
– des gens qui veulent boire du café
– du café
– de l’eau
– une cafétière électrique
But :
– obtenir un liquide noir et fumant
Etapes de traitement :
– avoir du café moulu,
– mettre le café dans un filtre,
– mettre la bonne quantité d’eau,
– mettre en marche.
Algorithme (programme) :
DEBUT
Indiquer le nombre de tasses désirées
Tant que le nombre de tasses est supérieur à 10
Faire Afficher : « Impossible, trop de tasses »
Indiquer le nombre de tasses désirées
Fait
Mettre l’eau dans la cafetière
Mettre un filtre
Si le café est en grain Alors
Prendre le moulin à café
Mettre du café dans le moulin
Moudre le grain
Sinon
Prendre du café moulu
Fin Si
Remplir une mesure de café
Verser son contenu dans le filtre
Tant que le nombre de mesure est insuffisant
Faire
Remplir une mesure de café
Verser son contenu dans le filtre
Fait
Mettre la cafetière en marche
FIN
III. Les langages de programmation
Un programme est une suite d’instructions à effectuer par les éléments électroniques de l’ordinateur (aller chercher une information en mémoire, additionner deux nombres sur le processeur, …) Cependant, comme nous l’avons dit, l’ordinateur ne comprend que le binaire.
Exemple de programme en binaire :
10100101
01100000
01100101
01100001
10000101
01100010
Ce genre de programme est très difficilement compréhensible pour un humain. Aussi, une étapge peut être franchie en écrivant ces instructions en base 16 (hexadécimale : 0 1 2 3 4 5 6 7 8 9 A B C D E F) au lieu de la base 2 (binaire).
Exemple de programme en hexadécimal :
A5
60
65
61
85
62
NB : on utilise l’hexadécimal au lieu de notre usuelle base dix car la correspondance est beaucoup plus simple (4 bits donnent un chiffre hexadécimal).
Ce codage est plus concis mais pas encore assez clair, aussi a-t-on inventé un langage symbolique, l’assembleur, qui reste très proche du processeur mais est déjà plus simple à comprendre.
Exemple de programme en assembleur :
LDA $60
ADC $61
STA $62
On peut comparer les trois façons d’écrire le même programme :
10100101 A5 LDA $60
01100000 60
01100101 65 ADC $61
01100001 61
10000101 85 STA $62
01100010 62
Enfin, si l’assembleur représente un programme quant à la lisibilité, les programmes écrits dans ce langage sont difficiles à concevoir, à modifier et surtout sont liés définitivement à une machine (chaque processeur à son propre langage assembleur). Aussi, les informaticiens ont-ils inventé des langages de plus haut niveau comme C, PASCAL, ADA, PROLOG…
On fait la distinction entre langage compilé (où le code écrit est traduit une fois pour toutes en binaire qui pourra être directement exécuté par le processeur), et langage interprété (où le code est analysé à chaque fois pour le traduire en binaire). Un langage compilé est donc beaucoup plus rapide.
IV. Codage des caractères : la table ASCII
Tous les caractères (lettres, chiffres…) ont un code standardisé dans une table appelée table ASCII (American Standard Code for Information Interchange). Dans cette table, chaque caractère correspond à un nombre et vice-versa. (Pièce jointe : « Table ASCII »).
