Cours gratuits » Cours informatique

Cours Introduction à l’informatique

Documents similaires

44 étoiles sur 5 a partir de 1 votes.
Votez ce document: ☆☆☆☆☆★★★★★

Lien de téléchargement

Introduction à l’informatique cours de L1 Miashs, Lille3

I.Tellier

Ce document est soumis à la licence libre GFDL et aux droits qui en découlent. Il est aussi disponible aux format HTML (sous forme de page Web) et PDF (téléchargeable gratuitement) à partir de la page “enseignement” de son auteur : http ?

Table des matières

Chapitre 1

C’est devenu une banalité : l’ordinateur s’accapare nos bureaux, modifie nos modes de travail, envahit nos maisons, s’intègre dans les objets les plus quotidiens et nous propose des loisirs inédits. Il est même à l’origine de nouveaux modes de sociabilité et d’une nouvelle économie : l’informatique est partout!

Pourtant, l’ordinateur lui-même demeure pour beaucoup une énigme, un objet mystérieux et un peu magique. Le terme d’informaticien semble d’ailleurs recouper une grande diversité de métiers et d’occupations réelles, allant du technicien à l’ingénieur réseau, en passant par le webmaˆ?tre. Quant à la nature du travail de ceux qui font de la «recherche en informatique», c’est sans doute (à en juger par les réactions auxquelles j’ai moi-même été confrontée) une mystère encore plus épais, malgré le prestige un peu mythique que conservent des projets comme ceux de la robotique ou de l’intelligence artificielle.

Ce document se veut (en partie) une réponse à ceux qui se demandent quels sont les fondements de l’informatique. Il n’est pas conc¸u pour initier au maniement pratique des ordinateurs, ce n’est pas une introduction à la bureautique. Ce n’est pas non plus un manuel technique à l’usage de ceux qui souhaitent bricoler leur machine favorite. Si, au fil des pages, des informations utiles à ces deux catégories d’utilisateurs, ou aux novices, pourront être glanées (vocabulaire spécialisé, typologie de matériels, ordre de grandeurs des performances des machines actuelles ), tel n’est pas son objectif premier.

L’informatique dont il sera question ici est une discipline scientifique qui, en tant que telle, a ses propres questions, ses propres problèmes, et dispose pour les aborder d’outils et de méthodes spécifiques. De cette discipline, on abordera les fondements théoriques ainsi que quelques réalisations pratiques, mais on insistera plus sur les concepts que sur la technique. Cette présentation relève donc principalement d’une démarche de vulgarisation scientifique destinée à un public de non spécialistes, mais qui se place à un niveau non trivial, difficilement trouvable dans les manuels habituellement disponibles.

J’ai ici essayé de décrire, de fac¸on aussi abordable que possible, ce que, en tant qu’informaticienne, je souhaite que «l’honnête homme du XXIème siècle» sache et pense de ma discipline, appelée à coup suˆr à un grand développement dans les années qui viennent.

Chapitre 2

Le statut de l’informatique en tant que discipline est ambigu et mal compris : est-il à chercher du côté de la science ou du côté de la technique? Quel est l’objet d’étude propre aux informaticiens? Quelles sont leurs vraies compétences? Avant de nous engager sur ces points, commenc¸ons par éliminer les mauvaises réponses :

– l’informatique n’est pas la«science des ordinateurs» (ce que, pourtant, laisse croire sa traduction anglaise, «computer science») : non, les informaticiens ne savent pas nécessairement réparer un ordinateur en panne, diagnostiquer un problème électronique ou effectuer des branchements compliqués, ils ne sont pas toujours les meilleurs guides quand il s’agit d’acheter un nouveau modèle de scanner ou de modem; oui l’informatique peut s’étudier avec un papier et un crayon, même en absence d’ordinateur

– l’informatique n’est pas la«science des logiciels» : non, les informaticiens ne connaissent pas nécessairement toutes les nouvelles versions des programmes du commerce, ils ne savent pas toujours utiliser toutes leurs fonctions, ils ne passent pas (toujours) leurs journées à tester des jeux ou à chercher des bugs La compétence réelle des informaticiens n’est ni matérielle, ni fonctionnelle. Alors, qu’est ce que l’informatique? C’est quelque chose entre les deux, quelque chose de plus abstrait et de plus fondamental sans quoi ni les ordinateurs ni les logiciels ne pourraient fonctionner Pour arriver à une définition satisfaisante, notre démarche sera de partir de ces deux niveaux de description habituels : matériel et logiciel, et de faire émerger leurs principes sous-jacents.

Commenc¸ons donc par l’aspect logiciel. La connaissance commune de l’informatique se fonde en effet généralement sur la pratique de quelques logiciels d’usage courant : traitements de texte, tableurs, navigation sur l’Internet L’image de l’ordinateur comme «grosse machine à calculer», fonctionnant pendant des heures pour réaliser ses calculs, reste également présente, mais de fac¸on plus mythique et lointaine, vue au cinéma. Y a-t-il une base commune à tous ces usages, apparemment si disparates? Quelles sont les caractéristiques partagées par tous ces logiciels?

Pour aborder ces questions, on peut commencer par remarquer que tout programme peut être décrit par deux aspects fondamentaux : les données qu’il manipule et les traitements qu’il permet de réaliser sur ces données. Le tableau de la figure

logiciel	données	traitemements
traitement de textes	caractères alphanumériques (lettres de l’alphabet, chiffres et tous les autres caractères du clavier)	copier, coller, effacer, déplacer, intervertir, changer la casse ou la police, mettre en page
calculs numériques, tableurs, outils de gestion	nombres, opérations et symboles mathématiques	calculer, écrire et résoudre des équations, faire des graphiques
jeux	dessins, personnages animés, sons	appliquer les règles du jeu
bases de données, logiciels documentaires	textes, images, données factuelles	stocker en mémoire et rechercher des données
Internet, CD-Rom	toutes les données citées précédemment	tous les traitements cités précédemment + communication entre machines, échange de données

Fig. 2.1 – données et traitements des logiciels courants

2.1 permet de résumer ces caractéristiques pour les logiciels les plus couramment utilisés.

Toutes les données citées dans ce tableau (et toutes celles, en général, manipulées par les ordinateurs) ont un point commun : ce sont des données discrètes, c’est-à-dire distinctes les unes des autres et qu’on peut énumérer une par une. Tous les traitements évoqués ici (et tous les autres traitements possibles en informatique) ont également en commun d’être des traitements effectifs, exprimables par des algorithmes. Les fondements de l’informatique sont à chercher dans ces deux notions, que nous allons donc maintenant détailler.

Tout le monde a entendu dire que les ordinateurs «ne fonctionnent qu’avec des 0 et des 1». Qu’est-ce que cela signifie exactement et ou`, dans l’ordinateur, sont donc cachés ces 0 et ces 1? Pour le comprendre, il faut cette fois partir des composants matériels qui constituent un ordinateur et aborder quelques notions élémentaires de la théorie de l’information.

L’unité de base de la théorie de l’information est le bit, contraction de binary digit, qui signifie en anglais nombre binaire. Un bit, par définition, est un composant quelconque ne pouvant se trouver que dans deux états possibles, exclusifs l’un de l’autre. On peut imaginer bien des dispositifs physiques pouvant répondre à cette définition, et nombre d’entre eux ont été exploités au moins une fois dans l’histoire de l’informatique. Ainsi, par exemple :

– une lampe électrique qui est soit allumée soit éteinte : les tout premiers ordinateurs, dans les années 40, utilisaient ainsi des milliers de lampes ou «tubes à vide» : un tel dispositif était hélas en panne dès qu’une lampe grillait;

– un fil électrique dans lequel le courant circule ou pas (ou sa version miniatu-risée, le «circuit intégré») : c’est évidemment le composant de base des ordinateurs, avec les transistors qui peuvent, eux, être vus comme des interrupteurs miniatures. Les fibres optiques réalisent la même fonction que les fils, mais avec la lumière au lieu de l’électricité.

– un aimant pouvant être polarisé «Sud» ou «Nord» : les mémoires des ordinateurs actuels, leur «disque dur», ainsi que les anciennes disquettes, sont composés de milliards de petits aimants;

– une surface ayant soit un creux soit une bosse : les CD-audio, les CD-Rom, lesDVD, ne sont rien d’autre que des morceaux de plastique gravés de creux et de bosses tellement minuscules que seul un faisceau laser peut les distinguer;

– un récipient pouvant être plein ou vide : il y a, à la Cité des Sciences de la Villette, un «calculateur à eau» fonctionnant avec des seaux et des tuyaux remplis d’eau.

Par convention, pour s’abstraire de ces contingences matérielles, on appelle l’un des deux états possibles d’un tel composant 0, et l’autre 1. Ces deux symboles sont arbitraires et n’ont pas de signification numérique. On aurait tout aussi bien pu choisir les symboles a et b à la place, ou tout autre couple de deux signes distincts, puisque c’est uniquement cette distinction qui est importante.

A partir de maintenant, un bit sera donc pour nous un espace dans lequel on

pourra soit écrire 0, soit écrire 1. Que faire avec de tels composants aussi élémentaires?

Avec un seul, pas grand chose, mais avec plusieurs, beaucoup de choses!

Si, en effet, on dispose de deux bits, alors le nombre total d’états possibles que peuvent prendre ces deux bits est de quatre : 00, 01, 10 ou 11.

Si on en prend trois, alors huit combinaisons sont possibles : 000, 001, 010, 011, 100, 101, 110, 111. On peut représenter ces huit combinaisons comme tous les différents parcours possibles dans un arbre ou` chaque branche est un choix entre 0 ou 1, comme dans la figure 2.2.

0 1 0 1 0 1 0 1

Fig. 2.2 – arbre des combinaisons possibles de 3 bits

En fait, ajouter un bit multiplie par deux le nombre de combinaisons possibles, puisque le bit ajouté a lui-même deux états possibles. Dans la représentation arborescente, cela revient à dédoubler chaque «feuille» de l’arbre (chaque dernier élément), et donc à multiplier par deux le nombre total de chemins possibles (égal au nombre de feuilles). Ce raisonnement permet de montrer que, avec n bits, on a 2ⁿ combinaisons possibles.

Le bit est l’unité de comptage de la mémoire des ordinateurs. Les multiples utilisés se comptent également en puissance de deux.

1 octet (byte en anglais) = 8 bits (8 = 2³) et permet 2⁸ = 256 combinaisons différentes possibles

1 Kilo-octet = 2¹⁰ octets = 1024 octets, et co¨?ncide presque avec la définition usuelle du kilo qui vaut 10³

1 Mega-octet = 1024 Kilo-octets, soit environ 10⁶ octets

1 Giga-octet = 1024 Mega-octets, soit environ 10⁹ octets 1 Tera-octet = 1024 Giga-octets, soit environ 10¹² octets

Pour avoir un ordre de grandeur de ces valeurs : une disquette a une capacité d’environ 1 Mega-octet, une clé USB entre 64 Mega-octet et 1 Giga octet, un CD contient environ 600 Mega-octet, un DVD jusqu’à environ 17 Giga-octets. La mémoire des disques durs actuels se compte aussi en Giga-octets. On peut en déduire par exemple le nombre d’aimants contenus sur une disquette Voyons maintenant comment coder les données citées dans le tableau de la figure 2.1 à l’aide de bits.

Les caractères alphanumériques sont tous les caractères disponibles sur un clavier d’ordinateur, ainsi que ceux qui résultent des combinaisons de touches. Combien existe-t-il de caractères alphanumériques? L’alphabet latin utilise 26 symboles différents, dont chacun existe en version minuscule et majuscule, ce qui fait 52 symboles. A ces lettres, s’ajoutent les 10 symboles de chiffres : 0, 1, 2, 9 et une vingtaine de notations mathématiques courantes : opérateurs (+, ?, ?, /), comparateurs (<, >), signe d’égalité (=), symboles logiques De nombreux autres caractères sont utilisées dans les graphies usuelles : ponctuations (“.”, “;”, “?”, “!”, “ :”), apostrophe, guillemets, tirets, parenthèses, crochets, accolades, soit encore au moins quinze dessins nouveaux. De plus, des caractères spéciaux sont passés à l’usage courant : symboles de monnaies ($, £) ou abréviations comme : &, §, @ Comptons-en donc une dizaine. Enfin, un éditeur de textes considère comme symbole certains signes invisibles comme les espaces blancs, les passages à la ligne ou les fins de fichier (comptons en 5). Notre très grossier calcul nous amène donc à environ :

52 + 10 + 20 + 15 + 10 + 5 = 112

Pour associer à chacun de ces caractères une suite distincte de 0/1 qui le code, nous avons donc au minimum besoin, d’après notre calcul précédent, de 7 bits, puisque 2⁷ = 128. C’est précisément ce que réalisait la première version du code ASCII (pour American Standard for Communication and International Interchange).

Mais ce calcul est trop restrictif. En effet, certaines langues utilisent en outre des caractères spéciaux : voyelles accentuées, trémas et cédilles en franc¸ais, tilde espagnol, ? allemand Un nouveau symbole, comme celui qui a été choisi pour l’Euro, peut apparaˆ?tre pour des raisons indépendantes de l’informatique. Il est donc plus raisonnable de conserver une marge de manoeuvre, et de prendre plutôt 8 bits, soit un octet, qui permet 256 combinaisons différentes. C’est ce que réalise le code ASCII actuel.

Ce code a donc subi des modifications, et il en existe de multiples variantes, mais nous ne rentrerons pas dans ces détails ici Ces variations expliquent toutefois que des messages peuvent être plus ou moins déchiffrables quand on les fait passer d’une machine à une autre (parfois même d’un programme à un autre sur une même machine). Il a par exemple longtemps été recommandé d’éviter d’utiliser les caractères accentués dans les courriers éléctroniques, parce que certains programmes de gestion de ces courriers utilisaient un code rudimentaire (fondé sur les claviers américains) qui les ignorait.

Quelle que soit la variante adoptée, le codage des caractères alphanumériques est donc réalisé par une association arbitraire et conventionnelle entre un caractère et une suite de bits. Le tableau de la figure 2.3 donne quelques exemples du code ASCII sur 8 bits associé à certains caractères :

code ASCII	caractère
00100011	#
00100100	$
00100101	%
01111010	z
01111011	{
00100001	!
00110001	1

Fig. 2.3 – quelques exemples de code ASCII

Depuis les années 90, une initiative internationale cherche à promouvoir une nouvelle manière de référencer tous les caractères de toutes les langues écrites (actuelles ou ayant existé) du monde : c’est la norme unicode. Elle répertorie environ 250 000 caractères différents, chacun associé à un nombre distinct. Mais cette norme ne fixe pas un codage en bits unique, et peut utiliser un nombre variable de bits (tous les caractères ne sont pas codés avec le même nombre de bits); nous ne la détaillerons pas non plus ici.

Les «éditeurs de textes» (comme le «Bloc Note» de Windows) sont des programmes servant à manipuler (copier, coller, effacer, déplacer, intervertir ) les caractères alphanumériques «purs». Ils permettent donc des substitutions de bits correspondant à des codes ASCII. Ils ne sont pas adaptés à la mise en page des textes, à leur formatage visuel, mais sont largement suffisants pour écrire des messages factuels ou des programmes informatiques.

Les logiciels de «traitements de textes» utilisent en outre des codes spéciaux spécifiques pour représenter la mise en page du texte : les marges, l’aspect «centrée» ou «justifié» d’un paragraphe, la police et la taille de l’affichage des caractères Même en prenant en compte les nouveaux codes associés à cette présentation, le codage des textes est économique : sur une disquette (environ 1 Mega-octets) on peut stocker un livre de 500 pages et sur un CD (environ 600 Mega-octets) une encyclopédie.

On pourrait procéder avec les nombres entiers de la même fac¸on que précédemment, c’est-à-dire par association arbitraire. Les chiffres de 0 à 9 ont d’ailleurs, nous l’avons vu, en tant que caractère, un code ASCII. Mais les nombres ont un statut et un usage particuliers : ils sont complètement ordonnés et servent à faire des calculs. Leur codage utilise une technique mathématique adaptée : la numérotation binaire (ou en base 2).

Pour comprendre le codage binaire des nombres, le mieux est d’abord de bien analyser leur représentation usuelle en base 10, dite aussi décimale. Cette représentation fait usage de 10 symboles différents de base : 1, 2, 3, , 9 et 0 et utilise le principe de la numérotation de position. Cette numérotation a été inventée par les indiens au Vème siècle en même temps que le symbole 0 (qu’elle rend nécessaire), et transmis en occident par l’intermédiaire des arabes (d’ou` le nom de «chiffres arabes»). Son principe est que chacun des symboles constituant un nombre représente en fait une puissance croissante de 10 lu de droite à gauche. La valeur réelle du nombre est alors la somme de ces puissances. Ainsi par exemple :

533 = 5 ? 100 + 3 ? 10 + 3 ? 1 = 53 ? 10² + 32 ? 10¹ + 31 ? 10⁰

2001 = 2 ? 1000 + 1 ? 1 = 2 ? 10 + 0 ? 10 + 0 ? 10 + 1 ? 10⁰

Quand on «lit» un tel nombre, on attribue à chaque chiffre qui le constitue, en fonction de sa place dans l’écriture du nombre, une certaine puissance de 10. Ainsi, les deux symboles «3» du premier nombre ne représentent pas, en fait, la même valeur (l’un vaut 30, l’autre vaut 3). La «grille de lecture» sous-jacente est donc un tableau de la forme :

10³	10²	10¹	10⁰
	5	3	3
2	0	0	1

Le principe de la «retenue» dans les additions est alors naturel : une somme de chiffres qui dépasse 10 pour une puissance de 10 donnée peut être représentée en passant à la puissance de 10 suivante, c’est-à-dire celle immédiatement à gauche. La représentation des chiffres romains n’utilise pas, elle, la numérotation de position. Par exemple, dans l’écriture du nombre 18 en chiffre romains : XVIII, les trois symboles «I» à la fin valent tous les trois 1, indépendamment de leur position. Dans un tel système, les opérations mathématiques s’effectuent très difficilement.

Le principe de la numérotation de position se généralise à n’importe quelle base de représentation en changeant simplement la puissance correspondante : pour la représentation binaire, ce sont donc les puissances de 2 qui vont servir. Pour une fois, nous prenons donc nos symboles 0/1 au sérieux : ici, 0 correspond bien au chiffre 0 et 1 au chiffre 1. Le tableau suivant donne des exemples de codage de nombres en base 2 :

2⁵ = 32	2⁴ = 16	2³ = 8	2² = 4	2¹ = 2	2⁰ = 1	nombre décimal
		1	0	0	1	8 + 1 = 9
			1	1	1	4 + 2 + 1 = 7
	1	0	1	1	1	16 + 4 + 2 + 1 = 23
1	0	0	1	0	1	32 + 4 + 1 = 37

Grâce à cette représentation, les opérations mathématiques usuelles sur les nombres binaires s’effectuent exactement de la même manière que sur les nombres décimaux. Ainsi, les «retenues» sont nécessaires dès que l’on dépasse un total de 2 pour une puissance de 2 donnée; elles consistent, comme en base 10, a` ajouter 1 dans une colonne plus à gauche (par exemple : si le résultat d’une colonne vaut 2, on pose 0 en bas de cette colonne et une retenue de 1 dans la colonne immédiatement à gauche, puisque «10» en base 2 correspond au nombre décimal 2).

Example 1L’addition 10111 + 101 est exécutée en base 2 ci-dessous.

1 1 1

1 0 1 1 1

+ 1 0 1

1 1 1 0 0

En base 10, l’opération mathématique correspondante est : 23 + 5 = 28.

Pour représenter les nombres négatifs, il suffit de réserver l’un des bits (par exemple le plus à gauche) pour coder le signe du nombre : par exemple la valeur 0 de ce bit signifie que le nombre est positif, 1 que le nombre est négatif (pour le nombre 0, la valeur de ce bit est alors indifférente : 0 a donc dans ce cas deux représentations différentes possibles). Mais ce codage rend délicat les calculs avec les nombres négatifs. D’autres codages plus astucieux (que nous ne détaillerons pas ici) permettent de réaliser des opérations mathématiques aussi simplement avec les nombres négatifs qu’avec les nombres positifs.

Pour un nombre donné, le codage en base 2 occupe plus de place que le codage décimal (c’est naturel puisque, en revanche, il utilise moins de symboles distincts de base). Pour maˆ?triser l’espace mémoire nécessaire au codage des nombres, un nombre fixe de bits est réservé pour toute donnée de type «nombre entier». Si, lors d’un calcul avec des nombres entiers, cet espace est insuffisant (à cause des retenues), alors le résultat annoncé du calcul sera faux (c’est le même problème que pour le «bogue de l’an 2000»).

Ainsi, même dans les dernières versions de Turbo Pascal (un environnement de programmation pour le langage Pascal encore en usage), deux octets étaient réservés pour tout nombre entier. Or 2 octets ne permettent que 2¹⁶ = 65536 combinaisons différentes de 0/1. Concrètement, cela signifie que les seuls nombres entiers relatifs qui peuvent être représentés sont ceux compris entre ?32768 et 32767. Cette limite va donner lieu à des erreurs dès que ces bornes sont dépassées dans un calcul.

Pour coder les grands nombres sans risquer les erreurs précédentes, et pour coder les nombres décimaux (c’est-à-dire avec une virgule), la méthode adoptée s’appelle «représentation en virgule flottante». Son principe est de normaliser l’écriture de ces nombres, en jouant sur les puissances de la base, et de coder indépendamment la partie «exposant» et la partie «mantisse» du résultat.

Example 2En base 10, on peut écrire :

27000000 = 0,27.10⁹

0,000027 = 0,27.10^?4

Tout nombre en base 10 peut ainsi s’écrire sous la forme d’un nombre décimal commenc¸ant par 0, suivi de ce qui s’appelle la «mantisse», qui contient les chiffres significatifs du nombre (et commence donc toujours par un chiffre différent de 0) et multiplié par une certaine puissance entière de 10 (éventuellement négative). Le principe est exactement le même si la base de la numérotation est 2. Par exemple le nombre 27 en base 2 peut s’écrire :

11011 = 0,11011.2¹⁰¹, ou` 11011 est la mantisse et 101 (qui vaut 5 en base 10) est l’exposant.

Dans la représentation en virgule flottante, un espace mémoire est réservé pour coder la mantisse, et un autre est réservé pour coder la valeur de la puissance. Un nombre trop grand pour être codé de fac¸on traditionnelle sur deux octets peut être codé correctement avec ce système.

La représentation en virgule flottante n’exclut pourtant pas tout risque d’erreur : pour un nombre très grand avec beaucoup de chiffres significatifs, l’ordre de grandeur du nombre sera conservé (grâce au codage de l’exposant) mais le détail des décimales peut être perdu. De même un nombre très proche de 0, dont l’exposant est très grand en valeur absolue et négatif peut ne pas être représenté correctement : tout ordinateur a sa limite en terme de représentation des nombres (pour les petits nombres, on parle de «epsilon machine»).

Les nombres décimaux qui s’écrivent avec un nombre infini non périodique de chiffres après la virgule (par exemple : ?) n’appartiennent pas au monde du «discret» : les coder avec des 0/1 impose donc une part d’approximation irrémédiable. Les «erreurs d’arrondis» sont une conséquence directe et inévitable du codage des nombres réels à l’aide de symboles discrets.

Les tableaux, utiles dans les tableurs ou les bases de données, peuvent être eux aussi codés à l’aide de 0/1. Imaginons par exemple que nous souhaitions coder le tableau suivant, qui ne contient que des nombres entiers :

12	5	-3	0	-1
-15	7	2	0	5
-8	-2	0	1	2

Pour représenter un tel tableau, il suffit par exemple :

– de repérer le nombre de lignes et le nombre de colonnes du tableau;

– de fixer un nombre de bits permettant de coder à la fois le nombre de ligneset de colonnes et chacune des données présentes dans une case du tableau; – de coder successivement chacune de ces données dans une longue chaˆ?ne de 0/1.

Dans notre exemple, le tableau a 3 lignes et 5 colonnes, et tous les nombres qu’il contient sont inférieurs à 16 = 2⁴ en valeur absolue. Chacune de ces données peut donc être codée sur 5 bits (le premier bit servira pour le signe). En codant successivement le nombre de lignes puis le nombre de colonnes et enfin chaque case lue de gauche à droite et de haut en bas, on obtient la chaˆ?ne suivante (pour faciliter la lecture, on laisse un espace entre chaque donnée distincte) :

00011 00101 01100 00101 10011 00000 10001 11111 00111 00010 00000 00101 11000 10010 00000 00001 00010

A partir de cette chaˆ?ne, et à condition bien suˆr de connaˆ?tre les conventions de codage, on peut entièrement reconstituer le tableau initial.

De même, on peut aussi coder un tableau de données discrètes hétérogènes (par exemple : dont certaines cases contiennent un nombre et d’autres cases un ou des caractères). Dans ce cas, il faut prévoir d’inclure dans le codage quelques bits qui signalent, pour chaque case, la nature de la donnée qu’elle contient. Par exemple, si chaque case ne peut contenir qu’un nombre ou qu’un caractère, il suffit de le signaler par un bit supplémentaire (valant 0 pour «caractère» et 1 pour «nombre») associé à chaque case, indiquant comment interpréter les bits suivants.

Les bases de données et les logiciels documentaires sont essentiellement constituées de tableaux de données hétérogènes, constituant ce que nous avons appelé dans la figure 2.1 des «données factuelles». Par exemple, le catalogue (simplifié) d’une bibliothèque peut avoir la forme du tableau de la figure 2.4, dans lequel chaque colonne est d’un type particulier. Dans notre exemple, les trois premières colonnes seraient de type «chaˆ?ne de caractères» (il faudrait préciser pour chacune le nombre de caractères maximum qu’elle peut contenir), la dernière étant de type «nombre entier».

titre de livre disponible	nom auteur	prénom auteur	date parution
Mme Bovary	Flaubert	Gustave	1857
Notre Dame de Paris	Hugo	Victor	1831
Les misérables	Hugo	Victor	1862

Fig. 2.4 – début d’un catalogue simplifié de bibliothèque

Les sons semblent être de nature différente des symboles et des nombres. On va en fait montrer comment un son, via une part d’approximation, peut se ramener à une suite de nombres. Un son peut (très schématiquement) se représenter par une courbe exprimant son amplitude en fonction du temps, comme sur la figure 2.5.

Un son réel est en fait une superposition de courbes de ce genre, mais l’oreille humaine n’est pas sensible à toutes les «harmoniques» qu’il contient. Le principe du fameux format de codage appelé MP3 est, précisément, de ne coder que la partie du son que les sens humains perc¸oivent.

Pour coder une telle courbe continue en bits, il est nécessaire de la discrétiser, c’est-à-dire de transformer les paramètres qui la définissent (le temps et l’amplitude), qui varient suivant des échelles continues, en paramètres discrets ne pouvant prendre

Fig. 2.5 – courbe sonore continue

qu’un nombre fixé de valeurs distinctes. On peut décomposer ce processus en deux étapes :

– on discrétise le temps, en abscisse, en procédant à un échantillonnage : le temps est «découpé en morceaux» à intervalles réguliers. On appelle fréquence d’échantillonnage le nombre d’intervalles découpés par seconde (ainsi, doubler la fréquence d’échantillonnage revient à multiplier par deux le nombre de morceaux découpés, c’est-à-dire à diviser par deux la largeur de chaque morceau);

– on discrétise l’amplitude en approchant la courbe par un nombre : pour chaqueintervalle de temps, on prend le nombre qui permet de «s’approcher le plus possible» de la courbe réelle.

En appliquant ce traitement à la courbe de la figure 2.5, avec une fréquence d’échantillonnage de 1 unité par seconde et en n’acceptant que des valeurs entières pour l’amplitude, on obtient la nouvelle courbe de la figure 2.6.

Pour coder cette courbe, il suffit maintenant de coder successivement les valeurs correspondant à chaque morceau de temps. Dans notre exemple, ces valeurs successives sont approximativement : 4, 7, 11, 11, 7, 3, 2 6, 11, 12. A condition de connaˆ?tre la fréquence d’échantillonnage, la donnée de ces nombres suffit à reconstruire la courbe discrétisée, et donc à reconstituer les variations du son initial.

Sur notre exemple, l’approximation semble grossière, mais en prenant une fréquence d’échantillonnage très grande et un codage des nombres permettant une grande précision pour les réels, la courbe discrète suit de si près la courbe réelle que le son y est parfaitement retranscrit. Dans un CD-audio haute fidélité, par exemple,

Fig. 2.6 – courbe sonore discrétisée

la fréquence d’échantillonnage est de 44 100 échantillons par seconde. Le nombre de bits occupés par un CD-audio usuel (non codé en MP3) est d’environ 500 Mega octets.

Il y a plusieurs manières de coder une image, de la «discrétiser». On distingue principalement deux formats de codage, chacun étant adapté à un type d’image particulier et à un usage particulier.

1. Le codage «bit map»

Ce codage est utilisé pour numériser des images existantes (photos, reproductions de peintures ). Il est donc plutôt adapté à l’analyse et au traitement des images. Son principe est celui du quadrillage : l’image est découpée à travers une grille au maillage plus ou moins fin, suivant des lignes horizontales et verticales. Cette grille découpe donc l’image en petits éléments rectangulaires appelés «pixels» (par contraction de l’anglais picture element). On appelle définition d’une image numérique le nombre de pixels qu’elle contient par unité d’espace, donc par cm². Cette définition est d’autant plus grande que la grille est fine, et donc que les pixels sont petits. Pour coder une image ainsi découpée, il suffit maintenant d’associer à chaque pixel sa couleur dominante, et de coder les couleurs des pixels les unes après les autres, dans un ordre fixé à l’avance (par exemple de haut en bas et de gauche à droite).

Les codages des couleurs les plus courants sont les suivants :

– le codage en noir et blanc pur : un bit suffit alors pour coder un pixel, suivant une association arbitraire (par exemple : 0 pour blanc et 1 pour noir);

– le codage en 256 couleurs (ou 256 niveaux de gris) : le spectre des couleurs(ou des niveaux de gris) est découpé en 256, et un code arbitraire sur un octet est associé à chacune des nuances (rappel : 1 octet = 8 bits et permet donc de coder 2⁸ = 256 couleurs différentes possibles)

– le codage en 16 millions de couleurs : ce codage, aussi appelé RGB (pour Red,Green, Blue), utilise la décomposition des couleurs à l’aide des 3 couleurs primaires (rouge, vert et bleu), comme pour les écrans de télévision. Rappelons qu’additionner des faisceaux lumineux tend à les éclaircir (puisque le blanc est la somme de toutes les couleurs); les règles d’addition des rayons lumineux ne sont donc pas les mêmes que celles des additions des couches de peinture La contribution de chaque couleur primaire à la définition d’une certaine couleur est alors codée sur 1 octet, ce qui nécessite donc 3 octets pour coder chaque pixel. Dans ce cas, le premier octet code la contribution du rouge à la couleur du pixel, le deuxième la contribution du vert et le troisième celle du bleu (or 2^8?3 vaut environ 16 millions, donc il y a bien 16 millions de couleurs différentes qui peuvent être codées par ce système).

Lorsqu’on numérise une image à l’aide d’un scanner, il faut préciser la définition de l’image et le codage des couleurs souhaité; ces 2 paramètres conditionnent fortement l’espace mémoire nécessaire au codage de l’image. Le codage d’une image «bit map» à haute définition et à l’aide de couleurs fines nécessite un grand nombre de bits. La figure 2.7 montre la même image bit map à deux

échelles différentes, pour illustrer l’importance de la définition dans l’impression globale rendue par une telle image. Les images bit map sont souvent ce qui occupe le plus de place dans la mémoire des ordinateurs

Fig. 2.7 – images bits map

2. Le codage vectoriel

Ce codage sert principalement à la synthèse d’images. Il est particulièrement bien adapté aux images qui se présentent sous la forme de schémas ou de plans. Il y en a plusieurs variantes, suivant que l’image à créer doit être vue en 2 ou en 3 dimensions.

– images en 2D

Le codage vectoriel en 2D considère qu’une image est une combinaison de figures géométriques standards : ellipses, droites, rectangles, flèches Un code arbitraire peut être associé à chacune de ces figures (il y en a un nombre fini). Par ailleurs, l’espace du dessin est repéré par un système de coordonnées classiques, désignées habituellement par X et Y. Pour repérer une figure particulière dans un dessin, il suffit de connaˆ?tre : – sa nature (par exemple : un rectangle) déterminée par son code;

– les coordonnées (X, Y) de deux points extrêmes qui permettent de lesituer sans ambigu¨?té dans l’espace (pour un rectangle : son coin supérieur gauche et son coin inférieur droit);

– son éventuelle couleur de trait et de remplissage (repérée comme pour lesimages bit map).

Contentons-nous ici de dessins «au crayon», sans tenir compte des couleurs. Imaginons par exemple que les codes des figures standards soient les suivants : – ellipse : 000; – rectangle : 001; – ligne continue : 010 et que l’on veuille coder le dessin de la figure 2.8.

Fig. 2.8 – dessin vectoriel

Les coordonnées (supposées entières) des points extrêmes peuvent aussi être codées sur 3 bits. Chaque figure élémentaire est alors représentée par 5 groupes de 3 bits chacun. Par exemple, l’ellipse de la figure 2.8 est codée par : 000 001 100 101 001. Dans ce code, le premier groupe de 3 bit est le code de la figure ellipse, les deux suivants codent les nombres 1 et 4, qui sont les coordonnées (X,Y) du point qui circonscrit cette ellipse en haut à gauche, les deux derniers codent les nombres 5 et 1 qui sont les coordonnées (X,Y) du point qui la circonscrit en bas à droite. Le dessin complet se code par la succession des codes des figures élémentaires (dans un ordre quelconque) qui le composent, soit par exemple :

000 001 100 101 001 001 011 101 111 010 010 010 101 101 000 ? code de l’ellipse ? ? code du rectangle ? ? code de la ligne?

D’autres codes représentant la couleur de trait et de remplissage de chaque figure élémentaires, l’ordre de superposition de ces figures, etc. devraient être ajoutés à cette suite.

Le codage vectoriel 2D est celui qui est exploité par les logiciels de dessin usuels comme PaintBrush, et il permet de faire subir simplement les transformations géométriques classiques (translations, rotations, symétries, homothéties ) aux images.

Il est très économe en espace mémoire, et c’est aussi la raison pour laquelle il est utilisé pour créer des animations sur Internet avec la technologie «Flash».

– images en 3D

Le principe de ce codage est exactement le même que le précédent, sauf que les primitives graphiques utilisées sont des volumes (sphères, cylindres, parallélépipèdes ) au lieu d’être des figures de la géométrie plane.

C’est lui qui est utilisé dans les logiciels de CAO (Conception Assisté par Ordinateur), de réalité virtuelle, ou pour les effets spéciaux numériques dans les films Il nécessite un effort de modélisation considérable pour représenter un environnement complet uniquement à partir de primitives, mais permet ensuite des applications spectaculaires en simulant les intéractions opérant dans cet environnement. Plus la modélisation est fine, plus la capacité de mémoire et de calcul nécessaire est importante.

En résumé, les données manipulées par les ordinateurs sont exclusivement des données discrètes. Le monde du discret, dans lequel on peut énumérer chaque entité distincte les unes après les autres s’oppose au monde du continu, dans lequel ce n’est pas possible. Mathématiquement, un ensemble est discret s’il peut être mis en bijection avec N ou une partie de N, il est continu s’il peut être mis en bijection avec l’ensemble des nombres réels R, ou un de ses intervalles. Dans R, contrairement à N, on ne peut pas “compter”, c’est-à-dire énumérer tous ses éléments les uns après les autres sans en oublier aucun. Une autre manière de caractériser les données discrètes est précisément leur caractère codable à l’aide d’un alphabet fini (par exemple 0/1). On parle aussi de codage numérique (0 et 1 sont des nombres), mais cela ne signifie pas, nous l’avons vu, qu’il ne code que les nombres.

Les caractères alphanumériques et les nombres entiers appartiennent naturellement au monde du discret, et leur codage numérique ne pose donc pas de problème. En effet, quand il s’agit de traiter des données de nature discrète à l’aide d’un autre dispositif discret, le codage/décodage est exact, c’est-à-dire qu’il préserve toute l’information. En revanche, les nombres réels, les sons et les images appartiennent au monde du continu. C’est pourquoi jusqu’à l’émergence de l’informatique multimédia, leur codage passait plutôt par un mode analogique : un tel code traduit des données continues à l’aide d’un autre dispositif lui aussi continu. Par exemple, dans les anciens disques en vinyle et les anciennes cassettes audio, le son était codé et restitué grâce à un sillon continu, dont la forme reproduisait (par une relation «d’analogie») la courbe des sons. La radio FM et la télévision hertzienne actuelles sont encore transmises à l’aide d’ondes continues dont les variations (les «modulations») traduisent suivant une échelle continue les variations du son. Les photographies “argentiques” sont réalisées à l’aide d’une surface (quasi) continue de produit chimique réactif qui restitue le continuum de nuances du spectre des couleurs. Les anciennes cassettes vidéo reproduisaient ainsi, une par une, les images d’un film sur leur bande.

Le codage numérique, lui, n’a droit qu’aux symboles 0 et 1. Pour coder numériquement des données continues, il faut donc passer par une phase de discrétisation ou numérisation, qui se paie par une part d’approximation. La qualité du son des CD-audio est néanmoins supérieure à celle des anciens disques «33 tours», et la définition des photographies numériques s’approche à grands pas de la précision des photographies traditionnelles.

L’échange de données entre matériels fonctionnant sous un mode numérique ou analogique impose parfois de passer par des phases de numérisation. Les plus courants de ces dispositifs sont les suivants :

– les modems (contraction de «modulateur»/«démodulateur») sont des appareils qui transforment des données discrètes sous forme de bits en données analogiques pouvant circuler sur les lignes téléphoniques (et réciproquement). Il sont donc indispensables pour relier les ordinateurs entre eux en passant par le réseau téléphonique franc¸ais (qui, lui, transmet des données continues). Les boˆ?tiers fournis pour se connecter à l’Internet haut débit (freebox, livebox et autres) en sont les versions améliorées. L’ADSL est en effet simplement une technologie qui emploie pour transmettre ses données des fréquences non utilisées par la voie humaine dans les conversations téléphoniques. C’est pourquoi on peut à la fois téléphoner et envoyer/recevoir des données en passant pas la même ligne téléphonique avec ces boˆ?tiers.

– les scanners ou numériseurs, transforment des images quelconques (textes ouphotos) en suites de bits codant ces images sous forme «bit map».

Par ailleurs, les différents types de données étant, comme nous l’avons vu, codés de fac¸on spécifiques, il peut parfois être nécessaire de passer d’un mode de codage à un autre. C’est ce que réalisent des logiciels comme :

– les Optical Character Recognizer (OCR) sont des programmes qui transformentles images sous forme «bit map» d’un texte en une suite de caractères ASCII. Il peuvent aussi reconnaˆ?tre la mise en page du texte et la traduire dans les codes spécifiques utilisés pour les représenter dans les traitements de textes. Ils sont indispensables si on veut «traiter» avec un éditeur ou un traitement

de textes un fichier (2.4) issu de la numérisation d’un texte écrit.

– les vectoriseurs d’images transforment les dessins sous forme «bit map» en images vectorielles. Ils sont utilisés pour traiter des plans techniques ou des dessins d’architectes.

De manière générale, tout logiciel qui permet de manipuler des données de natures différentes (par exemple, des caractères et des nombres) accorde un rôle primordial à la notion de typage ou de format. Connaˆ?tre le type d’une donnée, en effet, est indispensable pour savoir comment interpréter la suite de 0/1 qui la code.

Enfin, certains codages sont plus économiques que d’autres, au sens ou` ils nécessitent de réserver un plus ou moins grand nombre de bits pour coder une même donnée. Les logiciels de compression de données ont pour objectif de réduire au maximum l’espace mémoire occupé par le codage d’un certain type de données. Les stratégies qu’ils mettent en oeuvre varient évidemment suivant la nature des données, et donc des codages, qu’ils ont à traiter, et suivant que la compression visée est exacte ou approchée (c’est-à-dire si elle préserve ou non toute l’information présente ou pas). Par exemple, pour compresser l’image «bit map» d’un texte, on peut commencer par coder de fac¸on vectorielle les espaces blancs de la page. Pour le codage d’une scène vidéo (correspondant à une succession d’images «bit map»), on peut se contenter de coder complètement la première image, puis seulement la différence entre chaque image et la précédente

On comprend mieux, à l’issue de ce passage en revue de tous les codages utilisés en informatique, la puissance du monde numérique : elle vient de la capacité à stocker et à échanger des informations de nature très variées sur un seul support, sous forme de bits. La distinction élémentaire, abstraite, entre deux états possibles de n’importe quel dispositif permet une combinatoire suffisante pour apparemment tout «coder». Loin d’être limitée, cette stratégie a rendu possible l’apparition du multimédia (qui associe textes, sons et images) dans les CD-Rom ou l’Internet et donné naissance aux «autoroutes de l’information».

A la fin du siècle dernier, le mathématicien allemand d’origine russe Georg Cantor a démontré que l’ensemble infini (et discret) des nombres entiers N est fondamentalement moins «puissant» que l’ensemble infini (et continu) des nombres réels R, c’est-à-dire qu’il est impossible de définir une bijection entre ces deux ensembles. Il existe en quelque sorte plusieurs niveaux d’infinis.

Notre monde physique, lui, est-il discret ou continu? La réponse n’a rien d’évident. Les physiciens ont tendance à écrire et à manipuler des équations dont les variables parcourent un espace continu et dont les fonctions sont aussi continues. Le temps, par rapport auquel ils dérivent souvent les autres fonctions, est ainsi généralement considéré comme continu. Pour eux, le discret est plutôt conc¸u comme une approximation du continu. Pourtant, la notion de «particule élémentaire» laisse penser à une nature discrète des éléments constituant l’univers. Mais la physique quantique a aussi découvert que particules (discrètes) et ondes (continues) ne sont que les deux aspects d’une même réalité, ce qui ne contribue pas à simplifier les choses.

Il y a pourtant au moins deux domaines naturels fondamentaux dans lesquels le mode numérique a prévalu sur le mode analogique :

– le code génétique : le patrimoine génétique de tous les êtres vivants est codé non pas à l’aide de 0/1 mais sur l’alphabet à quatre lettres des bases chimiques notées A, T, C et G. C’est donc un codage discret en base 4;

– les langues humaines : elles sont toutes constituées, à chacun de leur niveaux(les sons élémentaires utilisés par une langue donnée ou phonèmes, les mots, les règles de grammaires ), d’une combinatoire d’éléments discrets.

Ces deux domaines sont ceux qui permettent la transmission d’information (génétiques ou culturelles) d’une génération à une autre. Si la nature a sélectionné des mécanismes discrets pour réaliser cette transmission, c’est sans doute que le codage numérique a de meilleures propriétés que le codage analogique. L’exercice 1 (énoncé en 1.1, corrigé en 2.1) donne quelques éléments pour comprendre comment la transmission de données discrètes peut être rendue robuste par des mécanismes d’auto-correction.

Par ailleurs, ce n’est évidemment pas un hasard si l’informatique est de plus en plus utilisé pour aider l’expertise humaine dans ces domaines, puisque le codage peut y être exact

La représentation binaire des nombres était connue bien avant l’apparition des ordinateurs; elle fut inventée dès le XVIème siècle par Francis Bacon, et fut utilisée par Leibniz au XVIIème siècle. Evidemment, le codage numérique des autres types de données (caractères, images, sons ) ne s’est généralisé que récemment, mais les principes qu’il met en oeuvre ne sont pas fondamentalement difficiles. Ce qui, en revanche, a signé l’acte de naissance de l’informatique, c’est l’explicitation de la notion de traitement effectif, ou encore de procédure de calcul ou d’algorithme (par la suite, ces termes seront utilisés comme des synonymes), qui permet de décrire ce que réalise un ordinateur sur les données qu’on lui fournit. Nous avons montré comment l’on pouvait ramener la diversité des données à des composants élémentaires. Nous allons maintenant voir que l’on peut aussi ramener la variété des traitements réalisables par les ordinateurs à une combinatoire de traitements élémentaires.

Qu’est-ce qu’un algorithme? En première approximation, c’est une méthode systématique définie étape par étape et permettant de résoudre à coup suˆr et en un nombre fini d’étapes une certaine classe de problèmes ou de répondre à une certaine classe de questions. Chacune de ces caractéristiques va bien suˆr devoir être explicitée. De telles méthodes ont été découvertes bien avant l’apparition de l’informatique et sont connues depuis longtemps par les mathématiciens. L’enseignement des mathématiques passe d’ailleurs par l’apprentissage de nombreux algorithmes : par exemple, comment réaliser une opération élémentaire (addition, multiplication, etc.) sur 2 nombres, entiers ou décimaux, comment résoudre une équation, etc.

Partons du problème suivant, un peu plus difficile : comment savoir si un certain nombre entier n (n’importe lequel) est un nombre premier, c’est-à-dire s’il n’admet aucun autre diviseurs que lui-même et 1? Pour le savoir, on peut adopter la stratégie suivante :

– essayer de diviser n par 2 :

? si la division est juste (le reste est nul), alors n est divisible par 2 : n n’est pas premier

– sinon, essayer de diviser n par 3 :

? si la division est juste (le reste est nul), alors n est divisible par 3 : n n’est pas premier

– essayer de diviser n par (essayer tous les nombres jusqu’à n ? 1) :

? si au moins une division est juste : n n’est pas premier

? si aucune division n’est juste : n est premier

Cette stratégie est très élémentaire (il en existe de bien plus efficaces : par exemple, on peut s’arrêter quand on dépasse ), mais elle assure :

– de toujours savoir ce qu’il faut faire pour obtenir la réponse;

– de fonctionner quel que soit le nombre entier n de départ : elle répond bien à une classe de questions (comme «un nombre entier quelconque est-il premier?») et non à une question particulière (comme «le nombre 31457 est-il premier?»);

– de demander un nombre fini de calculs (qui dépendra néanmoins du nombre n que l’on teste) et de donner toujours une réponse correcte, qu’elle soit positive ou négative.

Un algorithme peut aussi être vu comme la réalisation concrète d’une certaine fonction : dans notre exemple, c’est la fonction f qui à chaque nombre entier associe la réponse «oui» ou «non» suivant que ce nombre est premier ou non. On peut coder cette réponse par 0 ou 1 (0 signifie «non», 1 signifie «oui»). Le nombre n à tester est la donnée d’entrée, tandis que la réponse finale est la donnée de sortie de l’algorithme. On peut donc représenter cette fonction ainsi :

f : N??{0,1} n 7?? f(n)

Notre exemple illustre aussi qu’un algorithme est défini à l’aide d’instructions

élémentaires (comme de savoir faire une division), de tests (vérifier si le reste de cette division est nul ou non) et d’une structure définie par la fac¸on et l’ordre dans lesquels il s’enchaˆ?nent.

Un des plus anciens algorithmes intéressants connus (légèrement plus compliqué que celui de l’exemple), appelé «algorithme d’Euclide» et datant environ de 300 avant J.C., permet de répondre à la classe de questions suivante : comment savoir si deux nombres entiers quelconques sont premiers entre eux (c’est-à-dire s’ils ont un diviseur commun)?

Le mot «algorithme», lui, a été créé à partir du nom de Al Khowarizmi, mathématicien persan du IXème siècle, connu pour être l’auteur en 825 d’un traité d’arithmétique ou` il transmettait aux arabes des algorithmes de calculs connus des indiens et utilisant la numérotation de position.

La notion d’algorithme existe donc depuis longtemps. Mais la nécessité de lui donner un contenu, une définition mathématique précise n’a émergé que très tardivement, pour répondre à des interrogations plus générales.

L’histoire contemporaine des algorithmes commence en 1900. Cette année-là, a lieu à Paris le grand congrès de la société des mathématiciens. L’invité d’honneur y est David Hilbert, très grand mathématicien allemand de l’époque. Pour faire honneur à la date de la conférence, il choisit de se livrer a` l’exercice périlleux de la prospective, en proposant une liste de problèmes fondamentaux qui, selon lui, vont dominer les mathématiques du XXème siècle : ce sont les désormais célèbres «23 problèmes de Hilbert». Il n’est bien suˆr pas question de tous les exposer ici, mais il suffit de savoir qu’ils ont effectivement recensé une bonne partie des recherches mathématiques à venir.

Celui qui nous intéresse particulièrement porte le numéro 10, et il s’énonce de la fac¸on suivante : «Existe-t-il une méthode pour résoudre n’importe quelle équation diophantienne?». Une équation diophantienne s’exprime sous la forme d’un polynôme dont les coefficients sont des nombres entiers et dont on cherche les racines entières.

Example 3Quelques exemples d’equations diophantiennes : chercher les valeurs entières de x telles que : 3x² ? 5x2+ 1 = 0 chercher les valeurs entières de x et y telles que : 6xy ? y + 7x = 0

Dans certains cas particuliers (comme dans le premier exemple), on sait résoudre le problème, mais dans la plupart des autres aucune méthode générale, aucun algorithme, n’est connu et on commence à soupc¸onner qu’il n’en existe peut-être pas. Or les mathématiciens savent depuis longtemps démontrer qu’une certaine stratégie, une certaine méthode de calcul qu’ils ont inventée est juste et aboutira toujours au résultat souhaité, mais comment démontrer qu’il n’en existe aucune pour répondre à un problème donné? Comment être suˆr d’avoir testé toutes les méthodes possibles si on ne fait pas de cette notion de «méthode» elle-même un objet mathématique sur lequel il sera possible de faire des raisonnements et des démonstrations? C’est l’enjeu de la formalisation de la notion d’algorithme, qui va se préciser au fil des ans.

Ainsi en 1928, à Bologne, Hilbert, de nouveau invité au congrès des mathématiciens (qui a lieu tous les quatre ans jusqu’à aujourd’hui), précise les objectifs de sa recherche, de son «programme». A cette époque, il espère fonder les mathématiques (qui ont traversé au début du XXème siècle une «crise des fondements» due à la découverte de paradoxes dans certaines théories) à l’aide de la logique, alors en plein essor. Sans entrer dans les détails, la logique est un langage permettant d’exprimer des énoncés mathématiques et de démontrer qu’ils sont vrais ou faux. Mais pour lui faire jouer un tel rôle, il faut s’assurer qu’elle-même est «bien fondée», c’est-à-dire qu’elle est consistante (elle ne permet pas d’aboutir à des contradictions) et complète (toute formule logique doit être soit vraie soit fausse). Il serait bon aussi qu’elle soit décidable, c’est-à-dire qu’il existe une procédure effective permettant de savoir si une formule logique donnée quelconque est vraie ou fausse; c’est ce que Hilbert appelle le «Entcheidungsproblem» ou «problème de la décision».

Malheureusement pour Hilbert, le logicien autrichien Kurt G¨odel démontre en 1929 et surtout 1931 dans un article devenu très célèbre que si la logique élémentaire est effectivement complète, tout langage assez puissant pour fonder l’arithmétique est, lui, nécessairement incomplet, et que sa consistance est indémontrable. Le «programme de Hilbert» est plutôt mal parti. Reste le problème de la décision, qui ne trouvera sa solution, négative, qu’en 1936. Pour y parvenir, il a en effet fallu définir précisément ce qu’est une procédure effective et montrer qu’aucune d’entre elles ne peut résoudre ce problème. C’est ce qu’est parvenu à faire Alan Turing, auteur de l’article qui met fin à l’Entcheidungsproblem.

En 1936, Alan Turing a 24 ans. C’est un jeune et brillant étudiant en mathématiques à Cambridge, en Angleterre. Son professeur de logique a assisté à la conférence de Hilbert à Bologne, et lui-même est fasciné par la capacité humaine de raisonner et de faire des calculs. Plus tard, il cherchera à construire un «cerveau artificiel».

Dans son article de 1936, il propose tout d’abord de formaliser la notion d’algorithme grâce à la définition d’un dispositif abstrait que depuis on appelle «machine de Turing». Il montre ensuite qu’aucun de ces dispositifs ne sera jamais capable de décider si une formule logique quelconque est vraie ou fausse. La «machine de Turing» est le modèle de base qui fonde l’informatique, nous allons donc détailler sa construction et son fonctionnement.

Pour introduire cette définition de fac¸on intuitive, essayons de décomposer un calcul en «atomes» le plus élémentaires possible, en recensant tout ce qui est nécessaire à son exécution. L’objectif est de construire la machine la plus simple possible capable de réaliser n’importe lequel de ces calculs. Soit par exemple une multiplication entre deux nombres entiers : 25 ? 13.

Pour réaliser une telle opération, il faut d’abord «poser le calcul», en général en l’écrivant sur une feuille de papier. De combien de papier a-t-on besoin? On se restreint à des opérations portant uniquement sur des données discrètes. Par définition, elles peuvent donc être codées à l’aide d’un alphabet fini : 0 et 1 par exemple! Les deux dimensions de la feuille de papier ne sont pas fondamentales : il suffit donc de disposer d’un ruban de papier séparé en cases, chaque case pouvant contenir soit le symbole 0, soit le symbole 1, soit rester vide (caractère noté B pour «blanc», et servant à séparer les différentes données). Les données de notre multiplication peuvent ainsi être «posées» de la fac¸on suivante :

L’accès à ces données se fait par le biais d’une tête de lecture/écriture qui a le droit de parcourir le ruban case par case, un peu comme dans un magnétophone ou un magnétoscope. Nous la notons par une flèche sous la case du ruban qui est en train d’être lue (dans le dessin précédent, la tête se trouvait en train de lire la première case). C’est l’équivalent de la pointe du crayon avec lequel on écrit quand on effectue le calcul à la main.

Pour la suite des calculs, nous aurons besoin de poser d’autres données correspondant à des résultats intermédiaires. De même qu’on peut toujours disposer d’une nouvelle feuille de brouillon, on doit toujours pouvoir disposer de cases libres sur le ruban : nous supposons donc que celui-ci est infini vers la droite (et contenant initialement, à l’infini, des cases notées B).

Le deuxième composant fondamental d’une machine de Turing est la notion d’état. En effet, pour réaliser notre multiplication, nous devons passer par plusieurs phases, plusieurs étapes au cours desquelles l’opération réalisée est différente. Chacune suppose en quelque sorte un état d’esprit différent. Dans notre exemple, au moins deux phases successives sont nécessaires :

– une phase de multiplications élémentaires entre chiffres : 3 ? 5 puis 3 ? 2 puis 1 ? 5 puis 1 ? 2;

– une phase d’additions élémentaires entre les résultats de la phase précédente.

De même, une machine de Turing disposera d’un ensemble fini d’états distincts, que par la suite nous repérerons par des nombres disposés les uns à la suite des autres dans un tableau. A chaque instant un et un seul de ces état est «actif» et on l’appelle «état courant» : c’est celui dans lequel se trouve la machine à cet instant-là. La machine peut passer de n’importe quel état à n’importe quel autre à chaque étape du calcul. Enfin, un état particulier appelé «état final» et noté F correspondra à l’état dans lequel se trouve la machine à la fin de son calcul. Il signifie l’arrêt de son fonctionnement. Ainsi, si une machine a trois états possibles (plus F) et se trouve en ce moment dans l’état 2, nous notons :

L’état courant est repéré par un cercle. La machine commence toujours en partant de l’état initial noté 1, et s’arrête dès qu’elle atteint l’état F.

On appelle configuration d’une machine de Turing l’ensemble constitué par le symbole du ruban sur lequel pointe sa tête de lecture et l’état courant dans lequel elle se trouve. La machine donnée en exemple jusqu’à présent serait ainsi dans la configuration : (symbole lu : 1, état : 2). Réaliser un calcul avec un tel dispositif consiste, fondamentalement, à enchaˆ?ner des changements de configuration à partir des données de départ, pour aboutir à de nouvelles données.

Pour comprendre le fonctionnement d’une telle machine, reprenons notre exemple de multiplication. Chaque étape du calcul revient à écrire de nouveaux chiffres sur la feuille blanche en consultant (mentalement ou matériellement) une table de multiplication ou une table d’addition, suivant l’étape de calcul dans laquelle on se trouve.

De même, dans une machine de Turing, chaque instruction élémentaire revient simplement à substituer certains symboles à d’autres sur le ruban, en tenant compte des résultats intermédiaires qui y sont déjà écrits et de l’état courant de la machine, en consultant une table.

Pour une configuration donnée, c’est-à-dire :

– le contenu de la case du ruban lue par la tête de lecture;

– l’état courant de la instruction élémentaire sera, en effet, définie par 3 composantes : – le symbole écrit par la tête de lecture à la place de celui qu’elle a lu;

– le déplacement de la tête de lecture : soit une case vers la gauche (G) soit une case vers la droite (D);

– le nouvel état courant du calcul.

La première et la troisième composante décrivent la nouvelle configuration de la machine, la deuxième composante est le déplacement minimal qui permet d’enchaˆ?ner les instructions élémentaires les unes après les autres. La liste des instructions élémentaires constituant un calcul complet peut donc bien figurer dans un tableau dont les deux paramètres d’entrée sont le symbole lu et l’état courant, et dont chaque case contient 3 symboles correspondant aux 3 composantes de chaque instruction.

En résumé, un calcul effectué par une telle machine commence une fois les données d’entrée écrites sur le ruban, la tête de lecture mise sous la première case du ruban et l’état 1 fixé comme état courant. Chaque étape du calcul consiste a` chercher dans le tableau l’instruction à exécuter et à l’effectuer, jusqu’à temps que l’état courant soit l’état F. La donnée de sortie de l’algorithme, c’est-à-dire le résultat du calcul, doit alors être lisible sur le ruban.

La machine à multiplier les nombres (décimaux ou binaires) est malheureusement trop compliquée à écrire. Nous en prenons une beaucoup plus simple ici, celle réalisant la fonction suivante :

f : N??N

n 7?? n + 1

Notre machine de Turing doit donc ajouter 1 à un nombre binaire quelconque,

écrit sur son ruban, infini dans les deux sens (le fait que le ruban soit infini dans les deux sens est aussi choisi pour simplifier l’écriture de la machine). Dans cette machine, le résultat du calcul (le nombre initial + 1) va être écrit à la place de la donnée de départ sur le ruban. Son tableau est le suivant :

état courant \ symbole lu	0	1	B
1	0,D,1	1,D,1	B,G,2
2	1,D,F	0,G,2	1,D,F

Par exemple, la case qui se trouve à l’intersection de la colonne notée 1 et de la ligne notée 2 contient l’instruction qui doit être exécutée si la tête de lecture est en face d’une case du ruban contenant le symbole 1 et que la machine se trouve dans l’état 2 (on note les états en gras pour les distinguer des symboles écrits sur le ruban). Dans notre tableau, cette instruction est : 0,G,2. Ce code signifie que l’instruction consiste alors à écrire avec la tête de lecture/écriture le symbole 0 dans la case (à la place du 1), puis à déplacer cette tête d’une case vers la gauche sur le ruban, tandis que l’état courant de la machine reste l’état 2.

Pour vérifier l’exactitude de cette table, il suffit de la tester en écrivant sur le ruban un nombre binaire (positif) quelconque, en plac¸ant la tête de lecture sous la première case de ce nombre et en fixant l’état courant à 1, puis en exécutant systématiquement les instructions de la table. Quand l’état F est atteint, le nouveau nombre écrit sur le ruban doit être le nombre initial +1.

Prenons l’exemple du nombre n = 5, et donc de l’addition suivante :

1 0 1

+ 1

1 1 0

Example 4Au début du calcul, le ruban contient le nombre 5, codé en binaire comme suit :