L'art de programmer, c'est l'art de faire résoudre des problèmes par des machines. Il s’agit bien d’un art, au sens de l’artisan, qui passe par une longue période d’apprentissage et d’imitation. Dans cet exercice certains individus ont des dispositions naturelles ; pour les autres un apprentissage rigoureux fournit les rudiments d’une méthode. Le reste est affaire de travail et d’investissement personnels.
Un ordinateur est dénué d’intelligence ; il ne peut donc résoudre que les problèmes pour lesquels existe une méthode de résolution algorithmique, c’est-à-dire une recette déterministe. De plus, même si la recette existe en théorie pour résoudre tel problème, encore faut-il que l’énoncé du problème — l’espace des paramètres— et l’ensemble des solutions soient de dimension finie, en raison de la limitation en taille de la mémoire des machines. Enfin, condition ultime, la mise en oeuvre d’un algorithme doit avoir une durée finie. Un problème dont la solution nécessite de disposer d’un temps infini n’est pas considéré comme résoluble par ordinateur. Ces trivialités vont donc limiter nos ambitions de programmeur à une classe de problèmes assez restreinte, d’autant que ne nous disposons pas de puissantes machines de calcul.
2.1. Le traitement de l’information
L’informatique est la science du traitement de l’information. Une information est un élément de connaissance susceptible d’être codé, transmis et traité de manière automatique. Le codage numérique en nombres binaires étant adapté à la conception de machines électroniques, une partie essentielle du cours d’informatique porte sur la représentation des nombres et la logique (algèbre de Boole) binaires. Je considèrerai comme acquises les notions d’opération élémentaire (addition, soustraction, multiplication et division réelle et euclidienne) sur les ensembles de nombres naturels, relatifs, rationnels, réels et complexes, qui ne seront pas redéfinies, non plus que les opérations ensemblistes union, intersection, complémentation, ni les notions de relation binaire, relation d’équivalence et relation d’ordre partiel ou total. Concernant les notions de constante numérique, de variable, d’instruction d’affectation, de test, de boucle, qui sont au centre des techniques de programmation, elles seront redéfinies ou précisées selon les besoins.
2.2. Quelques exemples de problèmes
L’ordinateur fonctionne en binaire, mais il peut résoudre des problèmes autres que numériques. Et bien que le calculateur électronique soit l’instrument privilégié de l’ingénieur, ce n’est pas en programmant des problèmes numériques qu’on apprend le plus efficacement à programmer. Pourtant il est de tradition dans les sections techniques et scientifiques de commencer par des exercices numériques :
- Résoudre une équation du second degré à coefficients réels dans le corps de nombrescomplexes.
- Programmer la division euclidienne de deux entiers en n’employant que des soustractions.
- Trouver le plus grand diviseur commun de deux nombres naturels (PGDC).
- Enumérer les n premiers nombres premiers.
- Tester la conjecture polonaise.
- Calculer le nième élément de la suite de Fibonacci.
- Calculer le minimum, le maximum, la moyenne et l’écart-type d’une distribution numérique.- Calculer les zéros d’un polynome, tracer graphiquement le graphe d'une fonction numÉrique - inverser une matrice.
D’autres problèmes qui ne sont pas strictement numériques sont pourtant tout aussi instructifs pour l’art de la programmation. Ils seront soit traités soit évoqués :
- Trouver un mot dans un dictionnaire.
- Construire un arbre hiérarchique- Ordonner une liste de mots.
- Fusionner deux listes de mots déjà ordonnés.
- Enumérer les parcours d’un graphe et trouver le plus court chemin entre deux sommets.
- Filtrer une image, etc.
Partant d’un problème élémentaire nous montrerons comment le reformuler en des termes susceptibles d’être traités par un ordinateur idéal. Puis nous coderons ces algorithmes en langage C. Nous encourageons le lecteur à implanter ses propres solutions, à les modifier, éventuellement les améliorer ou à les réutiliser pour d’autres applications.
Tous les exemples fournis en C ont été testés sur compilateur Turbo C sur PC et Think C sur Macintosh. Je remercie par avance celles et ceux qui voudront bien me transmettre remarques et suggestions.
L'Informatique est la science du traitement automatique de l'information.
La notion d'information est assez générale. Pour l'informatique elle prend un sens particulier : Une information est un élément ou un système de connaissance pouvant être transmis au moyen d'un support et d'un codage approprié et pouvant être compris.
Par exemple des hiéroglyphes (codage) sur un papyrus égyptien (support) constituent une information sur la société égyptienne antique dés qu'on a été en mesure de les lire et d'en comprendre le sens (Champollion au XIXéme siècle).
Une information est une fonction du temps, puisque le contenu d'un message est sujet à changer au cours du temps. L'information "La mer est 'calme' dans le Golfe de Gascogne" est particulièrement périssable Quand le vent se léve et que la houle se forme, la mer devient 'agitée'. L'état de la mer est une information qui peut prendre des valeurs différentes, au cours du temps.
La plupart des informations que les Humains échangent sont supportées par un langage, c'est-àdire des groupes de sons (les mots), qu'il faut assembler "d'une certaine manière" (grammaire) pour que les phrases aient un sens Avec l'invention de l'écriture, ces mots ont eu une transcription (recodage) sous forme de symboles graphiques (des formes) dessinés ou imprimés.
Le concept de mot est fondamental en informatique, de même que celui de langage. Un langage est un ensemble de mots construits avec les lettres choisies dans un alphabet. Les mots sont assemblés en phrases selon des régles de grammaire précises qui définissent la syntaxe du langage. Le sens attaché à ces phrases, c'est-à-dire leur signification, constitue la sémantique.
L'essentiel de ce cours va consister à expliquer comment sont commandées les machines que nous nommons ordinateurs, capables d'exécuter des tâches complexes de traitement de l'information.
Le traitement de l'information consiste en une suite d'opérations transformant une représentation de cette information en une autre représentation plus facile à manipuler ou à interpréter.
Exemples :
"3*2" remplacé par "6"
"Mille neuf cent quatre vingt treize" est remplacé par "1993"
"La somme des carrés des côtés de l'angle droit d'un triangle rectangle est égale au carré de l'hypoténuse" est remplacé par "Théoréme de Pythagore"
"Championne olympique 1992 et 1996 du 400 mètres féminin" est remplacé par "Marie-José Pérec".
Dans une entreprise, traiter l'information peut consister à établir la paye, faire la facturation, gérer le stock, dresser un bilan. Dans un atelier, diriger un robot. En météorologie, reconnaître un cyclone sur une photo satellite
Un ordinateur est une machine qui permet d'effectuer des traitements sur des données à l'aide de programmes. Les données (les paramètres du problème, par exemple les notes des étudiants du cours d'informatique) ainsi que le programme (par exemple le calcul de la moyenne des notes) sont fournis à la machine par l'utilisateur au moyen de dispositifs de saisie (le clavier). Le résultat du traitement est recueilli à la sortie de l'ordinateur (l'écran, l’imprimante) sous forme de texte.
C'est en 1945 que le principe des ordinateurs a été inventé. Mais on peut faire remonter ses origines au boulier et aux premières machines à calculer mécaniques. Blaise Pascal (1623-1662) inventa à l'âge de 18 ans une machine à base de roues dentées et d'engrenages qui réalise d'elle-même les additions et les soustractions. Il suffit d'indiquer les chiffres et l'opération à faire.
Au XIXéme siècle l'anglais Babbage conçoit deux grandes machines dont le principe était correct, mais qui ne purent être réalisées en raison de difficultés techniques et financiéres. Il était sans doute trop tôt. Ce n'est qu'au XXème siècle que sous la pression du développement économique et des besoins militaires (Deuxiéme guerre mondiale) des scientifiques et des ingénieurs s'attelérent à la construction de gigantesques machines à calculer. La plus fameuse de ces machines fut la "Harvard Mark 1" qui mesurait 16 mètres de long, pesait 5 tonnes et comprenait 800 000 éléments, et pourtant n'avait pas plus de puissance qu'une simple calculette de poche actuelle !
La véritable révolution pour les machines à calculer viendra des progrès de l'électronique et de la logique mathématique. Le premier calculateur électronique, l'ENIAC, destiné à calculer la trajectoire de projectiles pour l'armée américaine, fut construit à partir de 1943. Il pesait 30 tonnes, comportait 17 468 tubes à vide et additionnait 5000 nombres en une seconde. Mais on ne peut considèrer cette machine comme un ordinateur, car il n'était pas véritablement automatique et n'utilisait pas de programme interne.
Sur le plan technique les progrès décisifs seront réalisés dans les années 1950 avec l'invention en 1947 du transistor (qui donne son nom aux postes de radio portables). Les transistors sont des composants électroniques qui remplace partout les lampes à vides ; rassemblés par dizaines puis centaines de milliers sur des circuits intégrés ils permettent de réaliser des puces électroniques qui envahissent les automates (lave linge, magnétoscopes, circuits d'allumage de voiture, calculettes ) et les ordinateurs.
Sur le plan conceptuel, c'est aux anglais George Boole (1815-1864), inventeur de l'algèbre binaire, l'algèbre de la logique, et Alan Turing (1912-1954) et aux américains d'origine européenne John Von Neumann (1903-1957) et Norbert Wiener (1894-164) que nous devons l'avancée décisive qui méne des calculateurs aux ordinateurs. Leurs travaux aboutissent à la construction du premier ordinateur en 1948 à Manchester, en Grande-Bretagne, le "Manchester Mark 1".
La machine conçue par John Von Neumann comporte trois innovations majeures :
- elle a une mémoire importante, dans laquelle sont archivées les données et le programme.
- elle a un programme enregistré dans la mémoire, qui décrit l'ensemble des instructions à réaliser.
- elle a une unité centrale de commande interne qui organise le travail en appliquant lesinstructions du programme et dirige les échanges de données avec l'extérieur de la machine.
Un ordinateur est constitué de composants matériels (hardware ) et de composants logiciels (software ). Les composants matériels sont essentiellement des cartes électroniques, des circuits intégrés, des câbles électriques, des supports de mémoires de masse (disques durs) et des dispositifs d'entrée/sortie (périphériques : clavier, écran, imprimante). Les logiciels, qui pilotent le fonctionnement des composant matériels, sont des programmes stockés sous forme codée dans la mémoire de l'ordinateur. Pour être interprétés par l'unité centrale ces programmes doivent être traduits dans le langage des machines, le langage binaire.
Toute l'information qui transite dans un ordinateur est codée avec des mots formés seulement de deux symboles (ou de deux 'états') notés 0 et 1. Cela tient à la nature des composants électriques et magnétiques utilisés pour coder l'information.
Dans les mémoires d'ordinateur, chaque unité élémentaire d'information peut être représentée par un minuscule aimant. Chaque aimant est orienté soit dans un sens (état 0), soit dans le sens opposé (état 1)
C'est le même principe qui est appliqué aux échanges de données. Pour transmettre un 1, il faut appliquer sur un conducteur électrique une différence de potentiel supérieure à quelques volts pendant une période "assez" longue, de l'ordre de la micro seconde (1/1 000 000 éme de seconde). Pour transmettre un 0, il faut maintenir une différence de potentiel inférieure à 1 volt pendant la même durée.
Par exemple pour coder le nombre 13 en binaire, il faut les quatre chiffres binaires 1101. En effet 13 peut être décomposé comme une somme de puissances de 2
13 = 8 + 4 + 1
= 1 * 8 + 1 * 4 + 0 * 2 + 1 * 1 en décimal
= 1 * 23 + 1 * 22 + 0 * 21 + 1 * 20 on ne conserve que les coefficients = 1 1 0 1 en binaire
Pour coder de l'information , que ce soient des nombres, (PI=3,141592 ), du texte (ce cours), des schémas, des images, des sons, des relations ("Pierre est le pére de Jacques et le frêre de Marie"), les circuits électroniques d'un ordinateur ne peuvent utiliser que des mots en binaire.
Montrons d'abord comment il est possible de coder n'importe quel nombre entier naturel IN={0, 1, 2, 3, ,1 000, , 1 000 000, } en binaire.
Puis nous en ferons autant pour les lettres et les mots de la langue française. Enfin il faudra montrer que les images, les sons et les relations aussi peuvent se coder en binaire.
Il suffit de décomposer un nombre décimal en une somme de puissances de 2. On peut par exemple commencer par écrire la table des premières puissances de 2 :
|
20 = 1 |
21 = 2 |
22 = 2x2 = 4 |
23 = 2x2x2 = 8 |
|
24 = |
25 = 2x x2 = |
26 = |
27 = |
|
28 = |
29 = |
210 = |
211 = |
Exercice 1 : Montrer que le nombre 256 est une puissance de 2.
Exercice 2 : Montrer que le nombre 131 est une somme de puissances de 2
Exercice 3 : Donner la représentation binaire des 10 premiers nombres entiers :
0 = 0x20 -> 0; 1=1x20 -> 1 ; 2=1x21 -> 10
3 = 1x2 + 1x1 = 1x21 + 1x20 -> 11
4 = 1x4+ 0x2 + 0x1 = 1x22 + 0x21 + 0x20-> 100
5 = 1x4 + 0x2 + 1x1 =
6 = 7 = 8 =
9 =
10 =
Le codage binaire a un inconvénient majeur pour l'être humain, son manque de lisibilité
Quelle est la représentation décimale du nombre dont la représentation binaire est : 1001 1110 ?
Réponse : 1x27+ 0x26 + 0x25 +1x24 + 1x23 + 1x22 + 1x21 + 0x20 = 1x128 + 0x64 + 0x32+1x16 + 1x8 + 1x4+ 1x2 + 0x1 = 158
Exercice 4 : Même question pour 1111 1111
Exercice 5 : Combien de chiffres binaires faut-il pour représenter le nombre décimal 10000 ?
Les deux opérations binaires de base sont
- l'addition
- la multiplication
Table d'addition binaire
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 avec une retenue de 1
Table de multiplication binaire
0 x 0 = 0
0 x 1 = 0 1 x 0 = 0
1 x 1 = 1 Exercice 6 :
En utilisant la table d'addition binaire calculez en binaire les nombres suivants :
1001 + 10100
1111 + 1
1010 + 111
1111 1111 + 1111 1111
Exercice 7 : En utilisant la table de multiplication et d'addition binaires calculez en binaire les nombres suivants :
1001 x 1
1111 x 10
100 x 101
1111 x 1111
En logique binaire une variable logique (booléenne) est VRAI (TRUE = 1) ou FAUSSE (FALSE = 0). Une expression logique est constituée de plusieurs variables logiques combinées par des connecteurs (opérateurs) logiques :
Les opérateurs logiques élémentaires sont :
- NON [NOT]
- ET [AND]
- OU [OR]
- OU EXCLUSIF [XOR]
Table de vérité du NONTable de vérité du ET
NON 0 = 10 ET 0 = 0
NON 1 = 00 ET 1 = 0
1 ET 0 = 0
Table de vérité du OU1 ET 1 = 1
0 OU 0 = 0Table de vérité du OU EXCLUSIF [XOR]
0 OU 1 = 10 XOR 0 = 0
1 OU 0 = 10 XOR 1 = 1
1 OU 1 = 11 XOR 0 = 1
1 XOR 1 = 0
Exercice 8 : Donner la valeur de vérité {VRAI ou FAUX} des assertions suivantes :
A : « 102 est un nombre pair »
B : « 11 est un multiple de 3 »
C : « 102 est un nombre pair » ET « 102 est divisible par 3 »
D : « 11 est multiple de 3 » ET « 102 est divisible par 3 »
E : « 108 est multiple de 9 » OU « 11 est divisible par 3 »
L'ensemble des entiers naturels : IN = {0,1,2..,100,101, 1000, }
- IN est ordonné ; il a un plus petit élément 0 ;
- Il n'y a pas de plus grand élément : tout élément a un successeur
L'ensemble des entiers relatifs : Z = Z+ U Z-
Z = { ,-1000, ,-100, , -3,-2,-1, 0, 1,2..,100,101, 1000, }
- Z est ordonné
- il n'y a ni plus grand ni plus petit élément : tout élément de Z a un prédécesseur et un successeur.
Opérateurs unaires : - (moins) : opposé
succ : successeur renvoie le nombre suivant dans l'ordre des entiers pred : prédécesseur renvoie le nombre précédent maxint : renvoie le plus grand entier représenté sur la machine
Opérateurs binaires :
+ - * DIV MOD /
Opérateurs de comparaison :
= < <=> >=
Axiomes :
associativité de + et *; distributivité de * sur +; relation d'ordre
En raison des limitations d'espace mémoire, on ne peut représenter que des intervalles de nombres.
Deux difficultés à résoudre : choix des intervalles et représentation des nombres négatifs
Implantation courante sur 2 octets: l'intervalle sélectionné est [0..65535]
Il s'agit de générer une représentation de ce nombre en base 2 occupant au plus deux octets, soit 16 bits.
Exemple pour n = 54710
On décompose 547 en puissances successives de 2 :
54710= 512 + 32 + 2 + 1 = 1*29 +1*25 +1*21 +1*20 et on ne code que les coefficients de la décomposition, la représentation binaire de n est Bin(n) = 0000 0010 0010 0011
Le plus grand nombre entier non signé représentable est donc :
1111 1111 1111 1111
= 1*215 +1*214 +1*213 +1*211 +1*210 +1*29 +1*28
+ 1*27 +1*26 +1*25 +1*24 +1*23 +1*22 +1*21 +1*20
= 1*216 - 1
La représentation décimale de ce nombre est donc Dec(n) = 65 536 - 1 = 65 53510
L'intervalle sélectionné est [-32768.. +32767]
Soit un nombre n de Z. Il s'agit de générer une représentation de ce nombre en base 2 occupant au plus deux octets, soit 16 bits. Si le nombre est positif et inférieur à 215(32 768) on le représente comme un entier non signé. Si le nombre est négatif et supérieur à -32768, le problème est de représenter le signe et de pouvoir passer d'un nombre à son opposé de façon simple.
Une méthode très répandue est la méthode du complément à 2. On travaille MODULO 216
On représente Bin(216+ n) = 65 536 - 547 = 64 989
= 1111 1101 1101 1101
Une vérification de l'expression calculée consiste à effectuer une somme bit à bit de 547 et de -547 Si la représentation est correcte on doit trouver 0 :
0000 0010 0010 0011
+ 1111 1101 1101 1101
_____________________________
Report 0000 0000 0000 0000
Le report (ou retenue) n'est bien sûr pas représenté.
Donc un nombre entier signé représenté sur 16 bits dont le bit de poids fort est à 1 doit être considéré comme un nombre NEGATIF : sa valeur est -(216- Dec(n2))
Algorithme de conversion d'un nombre en binaire complément à 2 sur un octet :
Trouver l'opposé d'un nombre en complément à 2 : Soit n = 0000 0101 = 510
Son opposé est -5 obtenu en inversant tous les 1 en 0 et tous les 0 en 1 et en ajoutant 1:
0000 0101 --> 1111 1010 + 1 = 1111 1011 = -5
Vérification :
5 + (-5) = 0
0000 0101
+1111 1011 ----------
0000 0000 report ignoré
Exercice :
Trouver les représentations binaires en complément à deux sur deux octets des nombres suivants :
-1; -2; 31000; -31000
-33000 est-il représentable ?
Les nombres réels.
L'ensemble IR ne peut pas être représenté de façon compléte en machine.
On retrouve les mêmes difficultés pour représenter les réels que pour représenter les entiers : l'ordinateur n'a pas une mémoire infinie. On représente donc un sous-ensemble fini de IR. Tout traitement (opération, représentation) peut être entachée d’erreur. Un calcul mathématique permet d’estimer l’importance de cette erreur.
Opérations sur les réels :
Opération unaire : - (opposé)
Opérations binaires :+ - * /
Comparaisons = < > <= >=
Fonctions réelles : cos sin log puiss sqrt Axiomes Corps ordonné
x * (y + z) = x * y + x * z: distributivité
On retrouve certains axiomes des entiers plus ceux des rationnels (inverse) plus quelques caractéristiques intéressantes (densité)
On appelle notation normalisée d'un réel celle où le premier chiffre significatif est placé immédiatement après la virgule (ou le point décimal).
Exemple : 1989 = 0.1989 E4
Pour stocker ce nombre en mémoire, il suffit de stocker l'exposant 4 et la partie décimale appelée mantisse 1989
Exemple : écrire PI en notation normalisée ? = 3.1415926535 = 0.31415926535 E1
Tout nombre réel peut être représenté dans une base quelconque : a = M * B e
avec B : base ; e : exposant ; M : mantisse (qui peut être une suite infinie de chiffres ) En notation normalisée on a les conditions :
(1/B) <= | M | < 1 ou bien M=0
Les réels sont représentés en machine selon un standard défini par l' IEEE Un réel est décomposé en
|
signe |
+ - |
s |
|
exposant |
caractéristique |
E |
|
partie décimale |
mantisse |
F |
x = (-1) s. 2E-127 . 1, F
En général on représente un réel sur 4 octets (32 bits) le bit 0 de poids fort (le plus à gauche) est le signe s, soit 0 (positif) ou 1 (négatif)
les bits 1 à 8 sont la caractéristique E qui est représentée par un entier binaire sur 8 bits décalé de
la valeur 127 les bits 9 à 31 sont pour exprimer la mantisse F en binaire, Exemple : 0.8 sera codé : s=0 E=126 F
. .. ..
0 01111110 10011001100110011001100 codage binaire . .. ..
0 1 8 9 31 n° de bit
Soit le nombre 0.8 à convertir en binaire. On constate d’abord que son signe est positif, donc S=0. On cherche ensuite à le décomposer en une somme de puissances de 2.
0.8 = 20 x 0.8
0.8 x 2 = 1.6 donc 0.8 = 1.6 / 2 = 2-1 x 1.6 = 2-1 x 1 + 2-1 x 0.6
0.6 x 2 = 1.2 donc 0.8 = 2-1 x 1 + 2-2 x 1.2
0.2 x 2 = 0.4 donc 0.8 = 2-1 x 1 + 2-2 x 1 + 2-3 x 0.4
0.4 x 2 = 0.8 donc 0.8 = 2-1 x 1 + 2-2 x 1 + 2-3 x 0 + 2-4 x 0.8
0.8 x 2 = 1.6 donc on retrouve une expression déjà rencontrée qui va se répéter infiniment
0.8 = (-1)0x 1. 10011001100110011 . x 2-1
Finalement on ne code que les chiffres binaires de la décomposition :
signe = 0 car 0.8 est positif
E = 126 car 126-127 = -1 F = 10011001100110011 .
Exemple 2 : 0.75 en base 2 donnera
0.75 x 2 = 1.5 donc 0.75 = 2-1 x 1.5
0.5 x 2 = 1.0 donc 0.75 = 2-1 x 1 + 2-2 x 1.0
0.75 = (-1)° x 2 126-127 x 1.10000000000000000000000
Exercice : Montrer que le nombre décimal 0.1 n’a pas de représentation finie en binaire.
En augmentant le nombre d'octets attribués à la représentation des réels, on améliore la précision en consacrant plus de bits à la mantisse, mais on n'augmente pas l'intervalle des réels représentés car on conserve le même nombre de bits pour la caractéristique.
La représentation des réels a de gros défauts dés qu'il s'agit par exemple de comparer des nombres manifestement égaux mais dont on ignore si l'ordinateur les identifiera.
x = 0.000 020 et y = 0.000 019 999 ; u = 20 ; v = 19 999
Comment est représenté z = (x/y) et r = (u/v) ? Sont-ils perçus comme égaux ?
Il peut être avantageux de définir directement un type de données NOMBRE RATIONNEL qui représentera de façon exacte tous les nombres équivalents à une fraction entiére
Les textes peuvent être représentés en binaire à condition d'associer à chaque lettre de l'alphabet une représentation numérique, par exemple son rang dans l'ordre alphabétique : A serait codé1 ; B, de rang 2 serait codé 10 en binaire; C codé 11, etc. Mais ce codage est insuffisant car il faut aussi pouvoir coder les signes de ponctuation . , ; ? ! , distinguer les minuscules des MAJUSCULES, les caractères accentués, etc.
La table ASCII (American Standard Code for Interexchange Information) propose un codage de 128 caractères différents sur 7 bits. Dans la table ASCII la lettre A est codé 65 B est codé 66 C est codé 67 Z est codé 90 a est codé 97 b est codé 98 0 est codé 48 1 est codé 49 9 est codé 57
Les caractères accentués des langues européennes ont nécessité l'ajout d'un huitiéme bit de codage, d'où la table ASCII étendue avec 256 caractères. Mais ce n'était pas suffisant pour certaines langues comme le japonais ; un codage sur 16 bits est en cours de normalisation sous le nom d'UNICODE. Il supplantera dans l'avenir le code ASCII.
Image 12 lignes de 8 colonnes Recodage binaire Le codage des images en noir et blanc ne présente pas0001 1100 de difficulté. Il suffit d'observer à la loupe une0011 11100110 1011photographie de journal pour en comprendre le principe. Si0011 1110
0011 1110
à une image est superposée une grille très fine, chaque0001 1100
0000 1000 carré de la grille coloré en NOIR par l'image est codé 1,0001 1100 chaque carré BLANC est codé 0. Il suffit donc de coder0111 11101111 1111toute l'image sous forme d’un tableau à deux dimensions de1111 1101
1111 1111 0 et de 1.
Le codage des sons est plus compliqué. Il faut d'abord transformer chaque son en un signal électrique continu (c'est le rôle du microphone), puis échantillonner ce signal électrique (discrétiser) et le numériser. On dispose alors d'un série de nombres qui représentent le signal sonore
Le cours de bases de données (seconde année GTE) introduit le modéle entité/association qui permet de représenter les informations "Marie est la mére de Pierre et de Françoise" ; "Pierre et Françoise ont acheté ensemble le véhicule Renault Clio 1234 ZA 75", "Marie a une Citroën ZX" ; "la Twingo 3987 TT 51 n'est à personne", etc., sous forme de tables relationnelles.
"est la mère de"
PERSONNE POSSEDE VEHICULE
|
Nom |
Mére |
|
Marie |
? |
|
Pierre |
Marie |
|
Françoise |
Marie |
|
Véhicule |
Immatriculation |
Marque |
Modéle |
|
1234 ZA 75 |
1234 ZA 75 |
Renault |
Clio |
|
1234 ZA 75 |
1001 AR 34 |
Citroën |
ZX |
|
1001 AR 34 |
3987 TT 51 |
Renault |
Twingo |
Propriétaire Pierre
Françoise Marie
Un algorithme est un procédé automatique qui transforme une information symbolique en une autre information symbolique. Seuls les problèmes qui sont susceptibles d'être résolus par un algorithme sont accessibles aux ordinateurs.
|
DONNEES |
---- transformation ------> |
RESULTAT |
|
Entrée |
----- algorithme ---------> |
Sortie |
Ce qui caractérise l'exécution d'un algorithme, c'est la réalisation d'un nombre fini d'opérations élémentaires (instructions) ; chacune d'elles est réalisable en un temps fini. La quantité de données manipulées au cours du traitement est donc finie.
La notion d'opération élémentaire dépend du degré de raffinement adopté pour la description du procédé. Ainsi, chaque algorithme peut être considéré comme une opération élémentaire dans un procédé plus important.
Exemple d’algorithme : Factorisation de ax2+bx+c quand a?0. Algorithme A :
soient x1 et x2les zéros de ax2+bx+c ; alors ax2+bx+c = a (x-x1) (x-x2).
Algorithme B soit ?= b2-4ac; si ? = 0 alors soient x1 et x2égaux à -b/2a sinon si ? > 0 alors soient x1=(-b+??)/2a et x2=(-b-??)/2a sinon soient x1=(-b+i?(-?))/2a et x2=(-b-i?(-?))/2a;
alors ax2+bx+c = a (x-x1) (x-x2).
Avant de faire traiter la factorisation de ax2+bx+c quand a ? 0 par un ordinateur, il faut traduire cet algorithme dans le langage binaire susceptible d’être exécuté par la machine. Cette transformation est le travail du programmeur. Il dispose pour cela d’un langage de programmation dit de haut niveau, c’est-à-dire qu’un être humain peut apprendre et manipuler sans trop de difficultés, et de programmes spécialisés, appelés compilateurs, qui font la conversion d’un fichier écrit dans le langage de haut niveau en code binaire exécutable par la machine cible. Une fois compilé, le programme (s’il est correct) peut être exécuté de multiples fois. Les résultats de son exécution (les sorties) dépendent des paramètres fournis en entrée.
Avant de passer à la phase de programmation il est donc nécessaire de définir très précisément le cahier des charges du programme, c’est-à-dire dans quelles conditions initiales il devra fonctionner, comment il devra procéder (algorithme) et sous quelle forme seront présentés les résultats.
Dans l’exemple de la factorisation ci-dessus, les entités manipulées sont des nombres (complexes et réels), des coefficient constants (a, b, c), une “inconnue” (x), des variables x1 et x2, le symbole ? du discriminant et les opérations élémentaires sur l’ensemble des nombres réels (<, >, =, +, -, *, /). On dira que les types de données sont des constantes et des variables de type réel. L’algorithme emploie aussi des structures de contrôle conditionnelles : Si (condition) alorsinstructionsinoninstruction.. Un instruction est soit une affectation — ?= b2-4ac; —, soit un test— si ? = 0 alors — .Le langage de programmation devra fournir des équivalents de toutes ces entités. Enfin le langage doit permettre de créer un programme qui reçoive des paramètres —saisie de la valeur des coefficients— et retourne des résultats à l’utilisateur —affichage—.
