Auris Solutions : Cabinet de Conseil en Stratégie Numérique

Cours d’algorithmique – Introduction

(c) Ph. RISCours 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 »).

Aucun commentaire jusqu'à présent.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *


_____________


Avant d'être uberisé,
apprenez à décoder les

17 règles de l'économie numérique


Catégories

Nous respectons la RGPD