Systèmes concrets de traitement de l’information
• L’ordinateur...
Informatique générale - Histoire de l’informatique
Systèmes concrets de traitement de l’information
• ...mais aussi...
Informatique générale - Histoire de l’informatique
Systèmes concrets de traitement de l’information
Edsger Dijkstra :
« L'informatique n'est pas plus la science des ordinateurs que
l'astronomie n'est celle des télescopes »
Informatique générale - Histoire de l’informatique
3
STIC : Science et Technologies de l’Information et de la
Communication
Quoi alors ?
Les STIC appréhendent toute la chaîne de l’information et de la
communication, avec ses concepts, ses traitements, mais aussi ses
réalisations matérielles essentielles pour acquérir l’information
comme pour la transmettre
d’après « Création d'un 10e Institut autour des Sciences et
Technologies de l'Information ? », groupe de travail autour de
Brigitte Vallée
Informatique générale - Histoire de l’informatique
STIC : mots-clés du domaine
• modèles de calcul, algorithmique (probabiliste, quantique, distribuée), complexité,
• langages de programmation, logiciel, génie logiciel, systèmes de preuve, test logiciel,
sûreté de fonctionnement
• systèmes d'information, bases de données, fouille de données, document électronique
• recherche opérationnelle, graphes, optimisation, aide à la décision, contraintes
• intelligence artificielle, représentation des connaissances, apprentissage automatique,
interaction homme-machine, traitement de la langue
• calcul formel, interface formel/numérique, calcul haute performance, modèles et
simulations numériques
• théorie de l’information, protection de l'information (cryptologie, codage), sécurité
numérique
• bio-informatique
• automatique, systèmes dynamiques, systèmes complexes, robotique, commande des
systèmes, contrôle non destructif
• traitement du signal et de l'image, multimédia, vision par ordinateur, réalité virtuelle ou
augmentée, communications numériques
• systèmes et réseaux, architecture, systèmes d’exploitation, systèmes distribués
• systèmes embarqués, systèmes matériel/logiciel, architectures programmables, systèmes
nomades communicants, capteurs et réseaux de capteurs, télécommunications
• micro et nanotechnologies, micro et nanosystèmes.
Informatique générale - Histoire de l’informatique
Système abstrait de traitement de l’information ?
• Qu’est-ce que c’est ?
– un système formel définissant des objets qui peuvent
représenter ce qu'on appelle de procédures de calcul, des
algorithmes ou des programmes. Ils définissent ensuite un
moyen systématique d'appliquer ces procédures, c'est-à-dire
de calculer
• Exemples de modèles de calcul
– Machine de Turing
– Lambda-calcul (λ-calcul)
Informatique générale - Histoire de l’informatique
4
Automate à états finis
• Définition
– Un automate est constitué d'états et de
transitions
– Son comportement est dirigé par un mot
fourni en entrée : l'automate passe d'état
en état, suivant les transitions, à la
lecture de chaque lettre de l'entrée
– L'automate est dit « fini » car il possède
un nombre fini d'états distincts : il ne
dispose donc que d'une mémoire
bornée.
• Un automate fini forme un graphe
orienté étiqueté
– les états de l’automate sont les sommets
du graphe
– les transitions de l’automate sont les
arêtes étiquetées
Informatique générale - Histoire de l’informatique
La machine de Turing (0/2)
Informatique générale - Histoire de l’informatique
La machine de Turing (1/2)
• Un « ruban »
– divisé en cases consécutives
– chaque case contient un symbole parmi un alphabet fini
– l'alphabet contient un symbole spécial « blanc » (’_’), et un ou
plusieurs autres symboles
– le ruban est supposé être de longueur infinie vers la gauche ou
vers la droite, en d'autres termes la machine doit toujours avoir
assez de longueur de ruban pour son exécution
– on considère que les cases non encore écrites du ruban
contiennent le symbole « blanc ».
• Une « tête de lecture/écriture »
– peut lire et écrire les symboles sur le ruban
– peut se déplacer vers la gauche ou vers la droite du ruban.
Informatique générale - Histoire de l’informatique
5
La machine de Turing (2/2)
• Un « registre d'état »
– mémorise l'état courant de la machine de Turing. Le nombre
d'états possibles est toujours fini, et il existe un état spécial
appelé « état de départ » qui est l'état initial de la machine
avant son exécution.
• Une « table d'actions »
– indique à la machine, en fonction du symbole lu sur le ruban et
de l'état courant de la machine :
• quel symbole écrire
• comment déplacer la tête de lecture (’<' pour une case vers la
gauche, ’>' pour une case vers la droite)
• quel est le nouvel état
– si aucune action n'existe pour une combinaison donnée d'un
symbole lu et d'un état courant, la machine s'arrête.
Informatique générale - Histoire de l’informatique
Machine de Turing : exemple 1
• Inversion de tous les bits
1,0 1,1,>
1,1 1,0,>
1,_ H,_,>
Si la machine est dans l’état 1 et qu’elle lit le symbole ‘0’,
elle passe dans l’état 1,
écrit le symbole 1,
et déplace la tête de lecture vers la droite
Informatique générale - Histoire de l’informatique
Machine de Turing : exemple 1
• Représentation sous forme d’un graphe
– les états de l’automate sont les sommets du graphe
– les transitions de l’automate sont les arêtes étiquetées
1,0 1,1,>
1,1 1,0,>
1,_ H,_,> 1, 0, > 0, 1, >
start H
_, _, >
Informatique générale - Histoire de l’informatique
6
Machine de Turing : exemple 2
• Compteur de parité
1,0 1,0,>
1,1 2,1,>
1,_ H,P,> start
2,0 2,0,>
2,1 1,1,>
2,_ H,I,>
Informatique générale - Histoire de l’informatique
Qu’est-ce qu’un ordinateur ?
• Un ordinateur est un équipement informatique ; il permet de
traiter des informations selon des séquences d'instructions
prédéfinies ou programmes. Il interagit avec l'environnement grâce
à des périphériques (écran, clavier, modem...).
• Un ordinateur est un ensemble de circuits électroniques
permettant de manipuler des données sous forme binaire, ou bits.
• Dictionnaire de l’Académie Française
– « Équipement informatique comprenant les organes nécessaires à son
fonctionnement autonome, qui assure, en exécutant les instructions
d’un ensemble structuré de programmes, le traitement rapide de
données codées sous forme numérique qui peuvent être conservées et
transmises. »
• Le terme « ordinateur » est d’origine biblique (il se trouvait dans le
Littré comme adjectif désignant « Dieu qui met de l’ordre dans le
monde »)
Informatique générale - Histoire de l’informatique
Qu’est-ce qu’un programme?
• Un programme informatique est une liste d'ordres
indiquant à un ordinateur ce qu'il doit faire. Il se présente
sous la forme d'une ou plusieurs séquences d'instructions,
comportant souvent des données de base, devant être
exécutées dans un certain ordre par un processeur ou par
processus informatique
• Un algorithme énonce une résolution sous la forme d'une
série d'opérations à effectuer. La mise en œuvre de
l'algorithme consiste en l’écriture de ces opérations dans un
langage de programmation et constitue alors la brique de
base d'un programme informatique
Informatique générale - Histoire de l’informatique
7
L’électronique numérique
• Systèmes électroniques fonctionnant sur la base d’états
électriques précis dont le nombre et les valeurs sont fixés à
leur conception, à chaque état correspondant une valeur
numérique
– pbs de parasites
– solution = limiter au maximum le nombre d’états distincts
• Le système binaire
– Basé sur l’utilisation de 2 états
– Les états sont notés FAUX/VRAI ou 0/1
– Ces états peuvent être combinés au travers de portes logiques
réalisant des opérations ou fonctions logiques telles le ET, le
OU, le NON, etc.
Informatique générale - Histoire de l’informatique
Une vue d’ensemble
Mécanique Invention des nombres
(binaire, décimal, sexagésimal, etc.)
Invention du calcul
Horlogerie, Automates
(cailloux, bouliers, abaques, tables, etc.)
Automates à programmes Calcul mécanisé
externes (P. Jaquet-Droz, A. Favre, ([Link], B. Pascal, G. W. Leibniz)
J. M. Jacquard, etc.)
Algorithmique Machine analytique Logique binaire
(A. Lovelace) (C. Babbage) (G. W. Leibniz, G. Boole)
Fondements théoriques
(D. Hilbert, K. Gödel, A Turing)
Electronique
Théorie de l’information
(C. Shannon)
Ordinateur numérique
(A. Turing, J. v. Neumann)
Informatique générale - Histoire de l’informatique
Compter
• Utilisation des doigts et des
mains
– compter un ensemble d’objets
– communiquer un nombre à son
interlocuteur
• Etymologie
– digitus (doigt) -> unité
• digit = chiffre (anglais)
• digital ~ numérique
– articulus (articulation) -> dizaine
Informatique générale - Histoire de l’informatique
8
Compter
• Encoches
– sur un os ou un bâton
– sur les parois des cavernes (plutôt que de dessiner n fois la
chose à compter)
• Nœuds sur une corde
• Problème
– compter sans erreur le nb d’encoches ou de nœuds
– lire le nb d’encoches
• solution
– répartition des encoches par groupes
– décomposition selon le principe des bases
Informatique générale - Histoire de l’informatique
Systèmes de numération additifs
• Principe
– Symboles juxtaposés jusqu’à un certain nombre (I, II, III, IIII)
– Nouveau symbole pour désigner le nombre suivant (V)
– Combinaison des symboles précédents pour former les
nombres (VI, VII, VIII, VIIII)
– Nouveau symbole pour désigner le nombre suivant (X)
• Exemples
– Sumer, Egypte, Grèce, Mésopotamie, Mayas, Phéniciens,
Romains
Informatique générale - Histoire de l’informatique
Système de numération additif de Sumer
Notation Notation
archaïque cunéiforme
(3200 av. J. C.) (2300 av. J. C.)
=?
1
10
=?
60
600
=?
3600
Informatique générale - Histoire de l’informatique
9
Autres systèmes de numération additifs
Egyptien Grec
Système
attique
=?
Système
alphabétique
=?
Informatique générale - Histoire de l’informatique
Le système romain
• Symboles
I=1 X = 10 C = 100 M = 1000
V=5 L = 50 D = 500
• Règles d’écriture :
– Toute lettre placée à la droite d’une autre figurant une valeur
supérieure ou égale à la sienne s’ajoute à celle-ci ;
– Toute lettre placée immédiatement à la gauche d'une lettre de
valeur supérieure, indique que le nombre qui lui correspond
doit être retranché au nombre qui suit ;
– Les valeurs sont groupées en ordre décroissant, sauf pour les
valeurs à retrancher selon la règle précédente ;
– La même lettre ne peut pas être employée quatre fois
consécutivement ;
Informatique générale - Histoire de l’informatique
Limites des systèmes additifs
• Beaucoup de symboles nécessaires pour écrire un nombre
– LXXXVIII = 88
• Opérations d’addition et de multiplication très compliquées
1 : 23
Exemple 2 77 *+13
94
Informatique générale - Histoire de l’informatique
10
Les systèmes positionnels
• Principe
– la valeur associée à un chiffre dépend de sa position dans le
nombre
– différentes bases possibles
• base 5 (peuples khmers et caraïbes)
• base 10
• base 20 (esquimaux, mayas, aztèques)
• base 60 (sumériens, babyloniens)
• Inventés 3 fois de manière indépendante
– par les babyloniens (~1800 av. J. C.)
– par les chinois (un peu avant 0)
– par les mayas
Informatique générale - Histoire de l’informatique
Système positionnel de Mari (~1800 av. J. C.)
• Positionnel
– symboles du 1 et du 100 identiques
• Non strictement positionnel
– symbole distinct pour le 10
Informatique générale - Histoire de l’informatique
Système positionnel de Babylone
• Strictement positionnel
– à base 60
– base 10 auxiliaire
• pb spécifique pour représenter le 0
– ajout d’un espace puis d’un signe spécifique
Informatique générale - Histoire de l’informatique
11
Système de numération indien (IVème siècle)
• A l’origine de notre système de numération moderne
– avec 0 opératoire
– système « parfait et universel »
– permet de représenter de très grands nombres
– est parvenu jusqu’à nous via les arabes
Informatique générale - Histoire de l’informatique
Calculer
• Etymologie
– grouper des cailloux (calculus) par dizaines ou par centaines
afin de réaliser des opérations arithmétiques
Informatique générale - Histoire de l’informatique
Le calcul digital
Informatique générale - Histoire de l’informatique
12