Les bases de l'informatique et de la programmation
1018
Les bases de l'informatique et de la programmation Le contenu de ce livre pdf de cours d'initiation à la programmation est inclus dans un ouvrage papier de 1372 pages édité en Novembre 2004 par les éditions Berti à Alger. http://www.berti-editions.com L'ouvrage est accompagné d'un CD-ROM contenant les assistants du package pédagogique. Rm di Scala Corrections du 04.01.05
Les bases de l'informatique et de la programmation
1. Les bases de l'informatique et de la programmation Le
contenu de ce livre pdf de cours d'initiation la programmation est
inclus dans un ouvrage papier de 1372 pages dit en Novembre 2004
par les ditions Berti Alger. http://www.berti-editions.com
L'ouvrage est accompagn d'un CD-ROM contenant les assistants du
package pdagogique. Rm di Scala Corrections du 04.01.05
2. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 1 SOMMAIRE Introduction 4 Chapitre 1.La machine
1.1.Ordinateur et volution 6 1.2.Les circuits logiques 14
1.3.Codage et numration 44 1.4.Formalisation de la notion
dordinateur 55 1.5.Architecture de lordinateur 66 1.6.Systme
dexploitation 100 1.7.Les rseaux 126 Exercices avec solutions 145
Chapitre 2.Programmer avec un langage 2.1.Les langages 147
2.2.Relations binaires 155 2.3.Thorie des langages 161 2.4.Les
bases du langage Delphi 177 Exercices avec solutions 219 Chapitre
3.Dvelopper du logiciel avec mthode 3.1.Dveloppement mthodique du
logiciel 223 .Machines abstraites : exemple 259 3.2.Modularit 269
3.3.Complexit, tri, recherche 278 tri bulle 286
3. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 2 tri par slection 292 tri par insertion 300 tri
rapide 306 tri par tas 316 recherche en table 331 Exercices avec
solutions 336 Chapitre 4. Structures de donnes 4.1.spcifications
abstraites de donnes 355 4.2 types abstraits TAD et implantation
371 exercice TAD et solution d'implantation 379 4.3 structures
d'arbres binaires 382 Exercices avec solutions 413 Chapitre 5.
Programmation objet et vnementielle 5.1.Introduction la
programmation oriente objet 445 5.2.Programmez objet avec Delphi
462 5.3.Polymorphisme avec Delphi 489 5.4.Programmation
vnementielle et visuelle 523 5.5.Les vnements avec Delphi 537
5.6.Programmation dfensive 564 Exercices avec solutions 582
Chapitre 6. Programmez avec des grammaires 6.1.Programmation avec
des grammaires 605 6.2.Automates et grammaires de type 3 628
6.3.projet de classe mini-interprteur 647 6.4.projet d'indentateur
de code 667 Exercices avec solutions 691
4. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 3 Chapitre 7. Communication homme-machine 7.1.Les
interfaces de communication logiciel/utilisateur 707 7.2. Grammaire
pour analyser des phrases 714 7.3. Interface et pilotage en
mini-franais 734 7.4. Projet d'IHM : enqute fumeurs 754 7.5.
Utilisation des bases de donnes 766 Exercices avec solutions 802
Chapitre 8. Les composants sont des logiciels rutilisables
8.1.Construction de composants avec Delphi 861 8.2. Les messages
Windows avec Delphi 902 8.3. Cration d'un vnement associ un message
923 8.4. ActiveX avec la technologie COM 930 Exercices avec
solutions 948 Annexes Notations mathmatiques utilises dans
l'ouvrage 982 Syntaxe compare LDFA- Delphi-Java/C# 988 Choisir
entre agrgation ou hritage 990 5 composants logiciels en Delphi,
Java swing et C# 995
5. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 4 Introduction Issu d'un cours de programmation
l'universit de Tours en premier cycle scientifique, en DESS, Master
Sciences et technologie comptence complmentaire informatique et en
Diplme Universitaire ( DU ) comptence complmentaire informatique
pour les NTIC (rservs des non- informaticiens), cet ouvrage est une
synthse (non exhaustive)sur les minima connatre sur le sujet. Il
permettra au lecteur d'aborder la programmation objet et l'criture
d'interfaces objets vnementielles sous Windows en particulier. Ce
livre sera utile un public tudiant (IUT info, BTS info, IUP
informatique et scientifique, DEUG sciences, licence pro
informatique, Dess, Master et DU comptence complmentaire en
informatique) et de toute personne dsireuse de se former par
elle-mme (niveau prrequis Bac scientifique). Le premier chapitre
rassemble les concepts essentiels sur la notion d'ordinateur, de
codage, de systme d'exploitation, de rseau, de programme et
d'instruction au niveau machine. Le second chapitre introduit le
concept de langage de programmation et de grammaire de chomsky, le
langage pascal de Delphi sert d'exemple. Le chapitre trois forme le
noyau dur d'une approche mthodique pour dvelopper du logiciel, les
thmes abords sont : algorithme, complexit, programmation
descendante, machines abstraites, modularit. Ce chapitre fournit
aussi des outils de tris sur des tableaux. montre comment utiliser
des grammaires pour programmer en mode gnration ou en mode analyse.
Le chapitre quatre dfini la notion de types abstraits. Il propose
l'tude de type abstrait de structures de donnes classiques : liste,
pile, file, arbre avec des algorithmes classiques de traitement
d'arbres binaires. Le chapitre cinq contient les lments
fondamentaux de la programmation oriente objet, du polymorphisme
d'objet, du polymorphisme de mthode, de la programmation
vnementielle et visuelle, de la programmation dfensive. Le langage
Delphi sert de support l'implantation pratique de ces notions
essentielles. Le chapitre six montre comment utiliser la
programmation par les grammaire avec des outils pratiques comme les
automates de type 3 et les automates piles simples. Deux projets
complets sont traits dans ce chapitre. Le chapitre sept correspond
la construction d'interface homme-machine, et l'utilisation des
bases de donnes avec des exemples pratiques en Delphi et Access. Le
chapitre huit composant avec Delphi, puis aborde le traitement des
messages dans Windows et comment programmer des applications
utilisant les messages systme pour communiquer. Il fournit aussi
une notice pratique pour construire un composant ActiveX et le
dployer sur le web avec Delphi.
6. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 5 Chapitre 1 : La machine 1.1.Ordinateur et
volution les 3 grandes lignes de penses les gnrations d'ordinateurs
l'ordinateur information-informatique 1.2.Les circuits logiques
logique lmentaire pour l'informatique algbre de Boole circuits
boolens 1.3.Codage numration codage de l'information numration
1.4.Formalisation de la notion dordinateur machine de Tring
thorique machine de Tring physique 1.5.Architecture de lordinateur
les principaux constituants mmoires, mmoire centrale une petite
machine pdagogique 1.6.Systme dexploitation notion de systme
d'exploitation systmes d'exploitation des micro-ordinateurs 1.7.Les
rseaux les rseaux d'ordinateurs liaisons entre rseaux
7. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 6 1.1 Ordinateur et volution Plan du chapitre: 1.
Les 3 grandes lignes de pense 1.1 Les machines calculer 1.2 Les
automates 1.3 Les machines programmables 2. Les gnrations de
matriels 2.1 Premire gnration 1945-1954 2.2 Deuxime gnration
1955-1965 2.3 Troisime gnration 1966-1973 2.4 Quatrime gnration
partir de 1974 3. Lordinateur 3.1 Utilit de lordinateur 3.2
Composition minimale dun ordinateur 3.3 Autour de lordinateur : les
priphriques 3.4 Pour relier tout le monde 4. Information -
Informatique 4.1 Les dfinitions 4.2 Critre algorithmique
lmentaire
8. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 7 1. Les 3 grandes lignes de pense Lhistoire de
linformatique dbute par linvention de machines (la fonction cre
lorgane) qui au dpart correspondent des lignes de pense diffrentes.
Linformatique rsultera de la fusion des savoirs acquis dans ces
domaines. Elle nest pas une synthse de plusieurs disciplines, mais
plutt une discipline entirement nouvelle puisant ses racines dans
le pass. Seul leffort permanent du gnie cratif humain la rendue
accessible au grand public de nos jours. 1.1 Les machines
calculer
9. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 8 La Pascaline de Pascal, 17me sicle. Pascal
invente la Pascaline, premire machine calculer (addition et
soustraction seulement), pour les calculs de son pre. La machine
multiplicatrice de Leibniz, 17me sicle. Leibniz amliore la machine
de Pascal pour avoir les quatre oprations de base (+,-,*,/). 1.2
Les automates Les automates, les horloges astronomiques, les
machines militaires ds le 12me sicle. 1.3 Les machines
programmables Le mtier tisser de Jacquard, 1752-1834 Dbut de
commercialisation des machines mcaniques scientifiques (usage
militaire en gnral). Babage invente la premire machine analytique
programmable. 2. Les gnrations de matriels On admet gnralement que
l're de l'informatique qui couvre peu de dcennies se divise en
plusieurs gnrations essentiellement marques par des avances
technologiques 2.1 Premire gnration 1945 - 1954 Informatique
scientifique et militaire.
10. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 9 Il faut rsoudre les problmes des calculs
rptitifs. Cration de langages avec succs et checs dans le but de
rsoudre les problmes prcdents. Technologie lourde (Tube et tore de
ferrite), qui pose des problmes de place et de consommation
lectrique. Les trs grandes nations seules possdent loutil
informatique. 2.2 Deuxime gnration 1955-1965 Naissance de
linformatique de gestion. Nouvelle technologie base sur le
transistor et le circuit imprim. Le langage Fortran rgne en matre
incontest. Le langage de programmation Cobol orient gestion,
devient un concurrent de Fortran. Les nations riches et les trs
grandes entreprises accdent loutil informatique. 2.3 Troisime
gnration 1966-1973 Naissance du circuit intgr. Nouvelle technologie
base sur le transistor et le circuit intgr. Les ordinateurs
occupent moins de volume, consomment moins dlectricit et sont plus
rapides. Les ordinateurs sont utiliss le plus souvent pour des
applications de gestion. Les PME et PMI de tous les pays peuvent se
procurer des matriels informatiques. 2.4 Quatrime gnration partir
de 1974 Naissance de la micro-informatique La cration des
microprocesseurs permet la naissance de la micro-informatique(le
micro-ordinateur Micral de R2E est invent par un franais Franois
Gernelle en 1973). Steve Jobs (Apple) invente un nouveau concept
vers la fin des annes 70 en recopiant et en commercialisant les
ides de Xerox parc travers le MacIntosh et son interface graphique.
Un individu peut actuellement acheter son micro-ordinateur dans un
supermarch.
11. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 10 Nous observons un phnomne fondamental : La
dmocratisation dune science travers un outil. Linformatique qui ses
dbuts tait une affaire de spcialistes, est aujourdhui devenue
laffaire de tous; do limportance dune solide formation de tous aux
diffrentes techniques utilises par la science informatique, car la
banalisation dun outil ou dune science a son revers :
lassoupissement de lattention envers les inconvnients inhrents tout
progrs technique. Tableau synoptique des gnrations dordinateurs :
3. L'ordinateur
12. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 11 3.1 Utilit de lordinateur Un ordinateur est
une machine traiter de linformation. Linformation est fournie sous
forme de donnes traites par des programmes (excuts par des
ordinateurs). 3.2 Composition minimale dun ordinateur : le cur Une
mmoire Centrale . Une unit de traitement avec son UAL (unit de
calcul). Une unit de commande ou contrle. Une ou plusieurs units
dchanges. Schma simplifi du cur de lordinateur 3.3 Autour de
lordinateur : les priphriques Les priphriques sont chargs
deffectuer des tches dentres et/ou de sortie de linformation. En
voici quelques uns. Priphriques dentre Clavier, souris, crayon
optique, cran tactile, stylo code barre, carte son, scanner, camra,
etc.
13. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 12 Priphriques de sortie Ecran, imprimante, table
traante, carte son, tlcopie, modem etc. Priphriques dentre sortie
Mmoire auxiliaire (sert stocker les donnes et les programmes): 1.
Stockage de masse sur disque dur ou disquette. 2. Bande magntique
sur drouleur (ancien) ou sur streamer. 3. Mmoire clef USB 4.
CD-Rom, DVD, disque magnto-lectrique etc 3.4 Pour relier tout le
monde : Les Bus Les Bus reprsentent dans lordinateur le systme de
communication entre ses divers constituants. Ils sont au nombre de
trois : le Bus dadresses, (la notion dadresse est prsente plus
loin) le Bus de donnes, le Bus de contrle. 4. Information -
informatique 4.1 Les dfinitions Linformation est le support formel
dun lment de connaissance humaine susceptible dtre reprsente laide
de conventions (codages) afin dtre conserve, traite ou
communique.
14. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 13 Linformatique est la science du traitement de
linformation dans les domaines scientifiques, techniques,
conomiques et sociaux. Une donne est la reprsentation dune
information sous une forme conventionnelle (code) destine faciliter
son traitement. schma simplifi du traitement de linformation 4.2
Critre algorithmique lmentaire Une application courante est
justiciable dun traitement informatique si : Il est possible de
dfinir et de dcrire parfaitement les donnes dentre et les rsultats
de sortie. Il est possible de dcomposer le passage de ces donnes
vers ces rsultats en une suite doprations lmentaires dont chacune
peut tre excute par une machine. Nous pouvons considrer ce critre
comme une dfinition provisoire dun algorithme. Actuellement
linformatique intervient dans tous les secteurs dactivit de la vie
quotidienne : dmontrer un thorme (mathmatique) faire jouer aux
checs (intelligence artificielle) dpouiller un sondage (conomie)
grer un robot industriel (atelier) facturation de produits
(entreprise) traduire un texte (linguistique) imagerie mdicale
(mdecine) formation distance (ducation) Internet (grand
public)...etc
15. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 14 1.2 Les circuits logiques Plan du chapitre: 1.
Logique lmentaire pour linformatique 1.1 Calcul propositionnel naf
1.2 Proprits des connecteurs logiques 1.3 Rgles de dduction 2.
Algbre de Boole 2.1 Axiomatique pratique 2.2 Exemples dalgbre de
Boole 2.3 Notation des lectroniciens 3.Circuits boolens ou logiques
3.1 Principaux circuits 3.2 Fonction logique associe un circuit 3.3
Circuit logique associ une fonction 3.4 Additionneur dans lUAL 3.5
Circuit multiplexeur 3.6 Circuit dmultiplexeur 3.7 Circuit dcodeur
d'adresse 3.8 Circuit comparateur 3.9 Circuit bascule 3.10 Registre
3.11 Mmoires SRAM et DRAM 3.12 Afficheur LED 3.13 Compteurs 3.14
Ralisation lectronique de circuits boolens
16. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 15 1. Logique lmentaire pour linformatique 1.1
Calcul propositionnel naf Construire des programmes est une activit
scientifique fonde sur le raisonnement logique. Un peu de logique
simple va nous aider disposer doutils pratiques mais rigoureux pour
construire des programmes les plus justes possibles. Si la
programmation est un art, cest un art rigoureux et logique. La
rigueur est dautant plus ncessaire que les systmes informatiques
manquent totalement de sens artistique. Une proposition est une
proprit ou un nonc qui peut avoir une valeur de vrit vraie (note V)
ou fausse (note F). " 2 est un nombre impair " est une proposition
dont la valeur de vrit est F. Par abus de langage nous noterons
avec le mme symbole une proposition et sa valeur de vrit, car seule
la valeur de vrit dune proposition nous intresse ici. Soit
lensemble P = { V , F } des valeurs des propositions. On le munit
de trois oprateurs appels connecteurs logiques : . : P x PP (se lit
" et ") : P x PP (se lit " ou ") : P P (se lit " non ") Ces
connecteurs sont dfinis en extension par leur tables de vrit : p q
p p q p q V V F V V V F F F V F V V F V F F V F F
17. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 16 1.2 Proprits des connecteurs logiques Nous
noterons p = q , le fait la proposition p et la proposition q ont
la mme valeur de vrit. Le lecteur pourra dmontrer laide des tables
de vrit par exemple, que et possdent les proprits suivantes : p q =
q p p q = q p p (q r) = (p q) r p (q r) = (p q) r p (q r) = (p q)
(p r) p (q r) = (p q) (p r) p p = p p p = p p = p (p q) = p q (p q)
= p q Nous notons p q , la proposition : p q (limplication). Table
de vrit du connecteur : p q p q V V V V F F F V V F F V Il est
aussi possible de prouver des " galits " de propositions en
utilisant des combinaisons de rsultats prcdents.
18. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 17 Exemple : Montrons que : p q = q p
(implication contrappose), par dfinition et utilisation vidente des
proprits : p q = p q = q p = q) p = q p 1.3 Rgles de dduction
Assertion : cest une proposition construite laide des connecteurs
logiques ( , en particulier) dont la valeur de vrit est toujours V
(vraie). Les rgles de dduction permettent de faire du calcul sur
les assertions. Nous abordons ici le raisonnement rationnel sous
son aspect automatisable, en donnant des rgles dinfrences extraites
du modle du raisonnement logique du logicien Gentzen. Elles peuvent
tre une aide trs apprciable lors de la construction et la
spcification dun programme. Les rgles de dduction sont spares en
deux membres. Le premier contient les prmisses ou hypothses de la
rgle, le deuxime membre est constitu par une conclusion unique. Les
deux membres sont spars par un trait horizontal. Gentzen classe les
rgles de dduction en deux catgories : les rgles dintroduction car
il y a utilisation dun nouveau connecteur, et les rgles
dliminations qui permettent de diminuer dun connecteur une
proposition. Syntaxe dune telle rgle : Quelques rgles de dductions
pratiques : Rgle dintroduction du : Rgle dintroduction du : Rgle
dintroduction du : Rgles dlimination du : ,
19. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 18 Rgle du modus ponens : Rgle du modus tollens :
Le systme de Gentzen contient dautres rgles sur le ou et sur le
non. Enfin il est possible de construire dautres rgles de dduction
partir de celles-ci et des proprits des connecteurs logiques. Ces
rgles permettent de prouver la valeur de vrit dune proposition.
Dans les cas pratiques lessentiel des raisonnements revient des
dmonstrations de vracit dimplication. La dmarche est la suivante :
pour prouver quune implication est vraie, il suffit de supposer que
le membre gauche de limplication est vrai et de montrer que sous
cette hypothse le membre de droite de limplication est vrai.
Exemple : soit montrer que la rgle de dduction R0 suivante est
exacte : R0 : (transitivit de ) Hypothse : p est vrai nous savons
que : p q est vrai et que q r est vrai En appliquant le modus
ponens : nous dduisons que : q est vrai. En appliquant le modus
ponens (q , q r) nous dduisons que : r est vrai. Comme p est vrai
(par hypothse) on applique la rgle dintroduction de sur (p , r)
nous dduisons que : p r est vrai (cqfd). Nous avons prouv que R0
est exacte. Ainsi nous avons construit une nouvelle rgle de
dduction qui pourra nous servir dans nos raisonnements. Nous venons
d'exhiber un des outils permettant la construction raisonne de
programmes. La logique interne des ordinateurs est encore
actuellement plus faible puisque base sur la logique boolenne, en
attendant que les machines de 5me gnration bases sur la logique du
premier ordre (logique des prdicats, suprieure la logique
propositionnelle) soient dfinitivement oprationnelles. 2. Algbre de
Boole
20. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 19 2.1 Axiomatique pratique Du nom du
mathmaticien anglais G.Boole qui linventa. Nous choisissons une
axiomatique compacte, laxiomatique algbrique : On appelle algbre de
Boole tout ensemble E muni de : deux lois de compositions internes
notes par exemple : et , une application involutive f (f2 = Id ) de
E dans lui-mme,note chacune des deux lois , , est associative et
commutative, chacune des deux lois , , est distributive par rapport
lautre, la loi admet un lment neutre unique not e1, xE, x e1 = x la
loi admet un lment neutre not e0, x, x e0 = x tout lment de E est
idempotent pour chacune des deux lois : xE, x x = x et x x = x
axiomes de complmentarit : lois de Morgan : (x,y) E2 , (x,y) E2
,
21. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 20 2.2 Exemples dalgbre de Boole a) Lensemble
P(E) des parties dun ensemble E, muni des oprateurs intersection
,union , et lapplication involutive complmentaire dans E CE , (si E
), si E est fini et possde n lments, P(E) est de cardinal 2n . Il
suffit de vrifier les axiomes prcdents en substituant les lois du
nouvel ensemble E aux lois , , et . Il est montr en mathmatiques
que toutes les algbres de Boole finies sont isomorphes un ensemble
(P(E), , CE) : elles ont donc un cardinal de la forme 2n . b)
Lensemble des propositions (en fait l'ensemble de leurs valeurs {V,
F} ) muni des connecteurs logiques (lapplication involutive) , , ,
est une algbre de Boole minimale deux lments. 2.3 Notation des
lectroniciens Lalgbre des circuits lectriques est une algbre de
Boole minimale deux lments : Lensemble E = {0,1} muni des lois " "
et " + " et de lapplication complmentaire . Formules pratiques et
utiles (rsultant de laxiomatique) : a + 1 = 1 a + 0 = a a + a = a =
1 = a.1 = a a.0 = 0 a.a = a = 0 = Formule dabsorbtion : a+(b.a) =
a.(a+b) = (a+b).a = a+b.a = a Montrons par exemple : a+(b.a) = a
a+(b.a)= a+a.b = a.1+a.b = a.(1+b) = a.1 = a Le reste se montrant
de la mme faon. Cette algbre est utile pour dcrire et tudier les
schmas lectroniques, mais elle sert aussi dans dautres domaines que
llectricit. Elle est tudie ici parce que les ordinateurs actuels
sont bass sur des composants lectroniques. Nous allons descendre un
peu plus bas dans la ralisation interne du cur dun ordinateur, afin
daboutir la construction dun additionneur en binaire dans
lUAL.
22. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 21 Tables de vrit des trois oprateurs : x y x . y
x + y 1 1 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 3. Circuits boolens
ou logiques Nous reprsentons par une variable boolenne x {0,1} le
passage dun courant lectrique. Lorsque x = 0, nous dirons que x est
ltat 0 (le courant ne passe pas) Lorsque x = 1, nous dirons que x
est ltat 1 (le courant passe) Une telle variable boolenne permet
ainsi de visualiser, sous forme dun bit dinformation (0,1) le
comportement dun composant physique laissant ou ne laissant pas
passer le courant. Nous ne nous proccuperons pas du type de
circuits lectriques permettant de construire un circuit logique
(les composants lectriques sont bass sur les circuits intgrs). Nous
ne nous intresserons qu la fonction logique (boolenne) associe un
tel circuit. En fait un circuit logique est un oprateur dune algbre
de Boole cest--dire une combinaison de symboles de lalgbre {0,1}, .
,+, ). 3.1 Principaux circuits Nous proposons donc 3 circuits
logiques de base correspondant aux deux lois internes et loprateur
de complmentation involutif. Le circuit OU associ la loi " + " : La
table de vrit de ce circuit est celle de l'oprateur + Le circuit ET
associ la loi "" : La table de vrit de ce circuit est celle de
l'oprateur
23. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 22 Le circuit NON associ la loi " " : la table de
vrit est celle de l'oprateur involutif On construit deux circuits
classiques laide des circuits prcdents : Loprateur XOR = " ou
exclusif " : dont voici le schma : Table de vrit du ou exclusif : a
b a b 1 1 0 1 0 1 0 1 1 0 0 0 Loprateur NAND (le NON-ET): dont
voici le schma : Table de vrit du Nand : a b 1 1 0 1 0 1 0 1 1 0 0
1
24. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 23 Loprateur NOR (le NON-OU): dont voici le schma
: Table de vrit du Nor : a b a b 1 1 0 1 0 0 0 1 0 0 0 1 L'on
montre facilement que les deux oprateurs NAND et NOR rpondent aux
critres axiomatiques d'une algbre de Boole, ils sont ralisables trs
simplement avec un minimum de composants lectroniques de type
transistor et diode (voir paragraphes plus loin). Enfin le NOR et
le NAND peuvent engendrer les trois oprateurs de base non, et , ou.
: Oprateur de base Ralisation de l'oprateur en NAND ou en NOR
circuit ET circuit OU circuit NON Expression des 3 premiers
oprateurs (x , + , . ) l'aide de NAND et de NOR
25. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 24 3.2 Fonction logique associe un circuit Un
circuit logique est un systme de logique squentielle o la valeur de
sortie S (tat de la variable boolenne S de sortie) dpend des
valeurs des entres e1,e2,...,en (tats des variables boolennes
dentres ei ). Sa valeur de sortie est donc une fonction S =
f(e1,e2,...,en). Pour calculer la fonction f partir dun schma de
circuits logiques, il suffit dindiquer la sortie de chaque oprateur
(circuit de base) la valeur de lexpression boolenne en cours. Puis,
la fin, nous obtenons une expression boolenne que lon simplifie
laide des axiomes ou des thormes de lalgbre de Boole. Exemple : En
simplifiant S : (a+b).b+ = b + (formule dabsorbtion) b + = 1. 3.3
Circuit logique associ une fonction A linverse, la cration de
circuits logiques partir dune fonction boolenne f n entres est
aussi simple. Il suffit par exemple, dans la fonction, dexprimer
graphiquement chaque oprateur par un circuit, les entres tant les
oprandes de loprateur. En rptant laction sur tous les oprateurs, on
construit un graphique de circuit logique associ la fonction f.
Exemple : Soit la fonction f de 3 variables boolennes, f (a,b,c) =
(a+b)+(b.c) Construction progressive du circuit associ. 1) oprateur
" + " :
26. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 25 2) branche suprieure de loprateur " + " : 3)
branche infrieure de loprateur " + " : Les lectroniciens classent
les circuits logiques en deux catgories : les circuits
combinatoires et les circuits squentiels (ou mmoire). Un circuit
combinatoire est un circuit logique n entres dont la fonction de
sortie ne dpend uniquement que des variables d'entres. Un circuit
mmoire (ou squentiel) est un circuit logique n entres dont la
fonction de sortie dpend la fois des variables d'entres et des tats
antrieurs dj mmoriss des variables de sorties. Exemple de circuit
mmoire f( a , b , S3 ) = S3 La sortie intermdiaire S2 est value en
fonction de la sortie S3 : S2 = b . S3 (valeur de S3 un temps
avant) Si b=0 alors S2 = 0 Si b=1 alors S2 = S3 Nous avons S3 = S1
+ S2 En notant S'3 la valeur au temps t0 et S3 la valeur au temps
t0+dt, il vient que S3 = S1 + b . S'3 Table de vrit associe ce
circuit : a b S1 S2 S3 f(a,b,S3) 1 1 0 S'3 S'3 S'3 1 0 0 0 0 1 0 1
1 S'3 1 0 0 0 1 0 1 0 Dans le cas a=1 et b=1 ce circuit fictif
fournit le complment de la valeur antrieure.
27. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 26 Quelques noms de circuits logiques utiliss
dans un ordinateur Circuit combinatoire : additionneur,
multiplexeur, dcodeur, dcaleur, comparateur. Circuit mmoire :
bascules logiques. 3.4 Additionneur dans lUAL (circuit
combinatoire) a) Demi-additionneur Reprenons les tables de vrits du
" " (Xor), du " + " et du " " et adjoignons la table de calcul de
laddition en numration binaire. Tout dabord les tables compares des
oprateurs boolens : a b a b a+b a.b 1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0
0 0 0 0 Rappelons ensuite la table daddition en numration binaire :
+ 0 1 0 0 1 1 1 0(1) 0(1) reprsente la retenue 1 reporter. En
considrant une addition binaire comme la somme effectuer sur deux
mmoires un bit, nous observons dans laddition binaire les
diffrentes configurations des bits concerns (nots a et b). Nous
aurons comme rsultat un bit de somme et un bit de retenue : bit a
bit b bit somme bit de retenue 1 + 1 = 0 1 1 + 0 = 1 0 0 + 1 = 1 0
0 + 0 = 0 0
28. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 27 Si lon compare avec les tables doprateurs
boolens, on saperoit que loprateur "" (Xor) fournit en sortie les
mmes configurations que le bit de somme, et que loprateur "" (Et)
dlivre en sortie les mmes configurations que le bit de retenue. Il
est donc possible de simuler une addition binaire (arithmtique
binaire) avec les deux oprateurs "" et "". Nous venons de
construire un demi-additionneur ou additionneur sur un bit. Nous
pouvons donc raliser le circuit logique simulant la fonction
complte daddition binaire, nous lappellerons " additionneur binaire
"(somme arithmtique en binaire de deux entiers en binaire). schma
logique dun demi-additionneur Ce circuit est not : b)Additionneur
complet Une des constructions les plus simples et la plus
pdagogique dun additionneur complet est de connecter entre eux et
en srie des demi-additionneurs (additionneurs en cascade). Il
existe une autre mthode dnomme " diviser pour rgner " pour
construire des additionneurs complets plus rapides lexcution que
les additionneurs en cascade. Toutefois un additionneur en cascade
pour UAL 32 bits, utilise 2 fois moins de composants lectroniques
quun additionneur diviser pour rgner. Nous concluons donc quune UAL
neffectue en fait que des oprations logiques (algbre de Boole) et
simule les calculs binaires par des combinaisons doprateurs
logiques Soient a et b deux nombres binaires additionner dans lUAL.
Nous supposons quils sont stocks chacun dans une mmoire n bits.
Nous notons apet bp leur bit respectif de rang p. Lors de laddition
il faut non seulement additionner les bits ap et bp laide dun
demi-aditionneur, mais aussi lventuelle retenue note Rp provenant
du calcul du rang prcdent.
29. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 28 additionneur en cascade (addition sur le bit
de rang p) On radditionne Rp laide dun demi-additionneur la somme
de apet bpet lon obtient le bit de somme du rang p not Sp. La
propagation de la retenue Rp+1 est faite par un " ou " sur les deux
retenues de chacun des demi-additionneurs et passe au rang p+1. Le
processus est itratif sur tous les n bits des mmoires contenant les
nombres a et b. Notation du circuit additionneur : Soit un exemple
fictif de ralisation d'un demi-additionneur simulant l'addition
binaire suivante : 0 + 1 = 1. Nous avons figur le passage ou non du
courant l'aide de deux interrupteurs (valeur = 1 indique que
l'interrupteur est ferm et que le courant passe, valeur = 0 indique
que l'interrupteur est ouvert et que le courant ne passe pas) Le
circuit et fournit le bit de retenue soit : 0 1 = 0
30. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 29 Le circuit Xor fournit le bit de somme soit :
0 1 = 1 Nous figurons le dtail du circuit Xor du schma prcdent
lorsqu'il reoit le courant des deux interrupteurs prcdents dans la
mme position (l'tat lectrique correspond l'opration 0 1 = 1 ) Si
lUAL effectue des additions sur 32 bits, il y aura 32 circuits
comme le prcdent, tous relis en srie pour la propagation de la
retenue. Un exemple d'additionneur sur deux mmoires a et b 2 bits
contenant respectivement les nombres 2 et 3 : Les 4 interrupteurs
figurent le passage du courant sur les bits de mme rang des mmoires
a=2 et b=3, le rsultat obtenu est la valeur attendue soit 2+3 =
5.
31. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 30 Notation du circuit additionneur sur 2 bits :
Remarque : Ce circuit d'addition sur 2 bits engendre en fait en
plus des bits de somme un troisime bit de retenue qui sera
gnralement mmoris dans le bit de retenue (bit de carry not C) du
mot d'tat programme ou PSW (Progral Status Word) du processeur.
C'est le bit C de ce mot qui est consult par exemple afin de savoir
si l'opration d'addition a gnr un bit de retenu ou non. 3.5 Circuit
multiplexeur (circuit combinatoire) C'est un circuit d'aiguillage
comportant 2n entres, n lignes de slection et une seule sortie. Les
n lignes de slection permettent de "programmer" le numro de l'entre
qui doit tre slectionne pour sortir sur une seule sortie (un bit).
La construction d'un tel circuit ncessite 2n circuits "et", n
circuits "non" et 1 circuit "ou". Notation du multiplexeur : 3.6
Circuit dmultiplexeur (circuit combinatoire) C'est un circuit qui
fonctionne l'inverse du circuit prcdent, il permet d'aiguiller une
seule entre (un bit) sur l'une des 2n sorties possibles, selon la
"programmation"( l'tat ) de ses n lignes de slection.
32. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 31 Notation du dmultiplexeur : 3.7 Circuit
dcodeur d'adresse (circuit combinatoire) C'est un circuit compos de
n lignes d'entres qui reprsentent une adresse sur n bits et de 2n
lignes de sortie possibles dont une seule est slectionne en
fonction de la "programmation" des n lignes d'entres. Notation du
dcodeur d'adresse : Exemple d'utilisation d'un dcodeur d'adresse 8
bits : On entre l'adresse de la ligne slectionner soit 10100010 (
A0 =1 , A1 = 0, A2 = 1, , A7 = 0 ) ce nombre binaire vaut 162 en
dcimal, c'est donc la sortie S162 qui est active par le composant
comme le montre la figure ci-dessous. La construction d'un circuit
dcodeur d'adresse n bits ncessite 2n circuits "et", n circuits
"non". Ce genre de circuits trs frquent dans un ordinateur sert
slectionner des registres, des cellules mmoires ou des lignes de
priphriques. 3.8 Circuit comparateur (circuit combinatoire) C'est
un circuit ralisant la comparaison de deux mots X et Y de n bits
chacun et sortant une des trois indication possible X+Y ou bien
X>Y ou X
33. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 32 Notation du comparateur de mots n bits : 3.9
Circuit bascule (circuit mmoire) C'est un circuit permettant de
mmoriser l'tat de la valeur d'un bit. Les bascules sont les
principaux circuits constituant les registres et les mmoires dans
un ordinateur. Les principaux types de bascules sont RS, JK et D,
ce sont des dispositifs chargs de "conserver" la valeur qu'ils
viennent de prendre. Schma lectronique et notation de bascule RS
minimale thorique notation Table de vrit associe cette bascule : R
S Qt+dt 1 1 ------ 1 0 0 0 1 1 0 0 Qt Qt reprsente la valeur de la
sortie au temps t , Qt+dt reprsente la valeur de cette mme sortie
un peu plus tard au temps t+dt. L'tat R=1 et S=1 n'est pas autoris
L'tat R=0 et S=0 fait que Qt+dt = Qt , la sortie Q conserve la mme
valeur au cours du temps, le circuit "mmorise" donc un bit. Si l'on
veut que le circuit mmorise un bit gal 0 sur sa sortie Q, on
applique aux entres les valeurs R=1 et S=0 au temps t0, puis t0+dt
on applique les valeurs R=0 et S=0. Tant que les entres R et S
restent la valeur 0, la sortie Q conserve la mme valeur (dans
l'exemple Q=0). En pratique ce sont des bascules RS synchronises
par des horloges (CLK pour clock) qui sont utilises, l'horloge sert
alors commander l'tat de la bascule. Seule la sortie Q est
considre. Dans une bascule RS synchronise, selon que le top
d'horloge change d'tat ou non et selon les valeurs des entres R et
S soit d'un top l'autre la sortie Q du circuit ne change pas soit
la valeur du top d'horloge fait changer (basculer) l'tat de la
sortie Q.
34. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 33 Schma lectronique gnral et notation d'une
bascule RS synchronise notation Remarque Certains types de mmoires
ou les registres dans un ordinateur sont conus avec des variantes
de bascules RS (synchronises) note JK ou D. Schma lectronique gnral
et notation d'une bascule de type D notation Fonctionnement
pratique d'une telle bascule D dont les entres sont relies entre
elles. Supposons que la valeur de l'entre soit le boolen x (x=0 ou
bien x=1) et que l'horloge soit 0. En simplifiant le schma nous
obtenons une autre prsentation faisant apparatre la bascule RS
minimale thorique dcrite ci-haut :
35. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 34 Or la table de vrit de cet lment lorsque les
entres sont gales 0 indique que la bascule conserve l'tat antrieur
de la sortie Q: R S Qt+dt 0 0 Qt Conclusion pour une bascule D
Lorsque l'horloge est 0, quelque soit la valeur de l'entre D (D=0
ou D=1) une bascule D conserve la mme valeur sur la sortie Q. Que
se passe-t-il lorsque lors d'un top d'horloge celle-ci passe la
valeur 1 ? Reprenons le schma simplifi prcdent d'une bascule D avec
une valeur d'horloge gale 1. Nous remarquons que sur les entre R et
S nous trouvons la valeur x et son complment x , ce qui limine deux
couples de valeurs d'entres sur R et S (R=0 , S=0) et (R=1 , S=1).
Nous sommes srs que le cas d'entres non autoris par un circuit RS
(R=1 , S=1) n'a jamais lieu dans une bascule de type D. Il reste
envisager les deux derniers couples (R=0 , S=1) et (R=1 , S=0).
Nous figurons ci- aprs la table de vrit de la sortie Q en fonction
de l'entre D de la bascule (l'horloge tant positionne 1) et pour
clairer le lecteur nous avons ajout les deux tats associs des
entres internes R et S : x R S Q 0 1 0 0 1 0 1 1 Nous remarquons
que la sortie Q prend la valeur de l'entre D (D=x ), elle change
donc d'tat. Conclusion pour une bascule D Lorsque l'horloge est 1,
quelque soit la valeur de l'entre D (D=0 ou D=1) une bascule D
change et prend sur la sortie Q la valeur de l'entre D.
36. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 35 3.10 Registre (circuit mmoire) Un registre est
un circuit qui permet la mmorisation de n bits en mme temps. Il
existe dans un ordinateur plusieurs varits de registres, les
registres parallles, les registres dcalage (dcalage droite ou
dcalage gauche) les registres sries. Les bascules de type D sont
les plus utilises pour construire des registres de diffrents types
en fonction de la disposition des entres et des sorties des
bascules : les registres entre srie/sortie srie, entre srie/sortie
parallle, entre parallle/sortie parallle, entre parallle/sortie
srie. Voici un exemple de registre n entres parallles (a0,a1,,an-1)
et n sorties parallles (s0,s1,,sn-1) construit avec des bascules de
type D : Examinons le fonctionnement de ce "registre parallle n
bits" La ligne CLK fournit le signal d'horloge, la ligne RAZ permet
l'effacement de toutes les sorties sk du registre, on dit qu'elle
fournit le signal de validation : Lorsque RAZ = 0 on a (s0=0, s1=0,
, sn-1=0) Lorsque RAZ = 1 on a (s0= q0, s1= q1, , sn-1= qn-1) Donc
RAZ=0 sert effacer tous les bits de sortie du registre, dans le cas
o RAZ=1 qu'en est-il des sorties sk. D'une manire gnrale nous avons
par construction sk = RAZ . qk : Tant que CLK = 0 alors, comme
RAZ=1 nous avons sk = qk (qk est l'tat antrieur de la bascule).
Dans ces conditions on dit que l'on "lit le contenu actuel du
registre". Lorsque CLK = 1 alors, tous les qk basculent et chacun
d'eux prend la nouvelle valeur de son entre ak. Comme RAZ=1 nous
avons toujours sk = qk (qk est le nouvel tat de la bascule). Dans
ces conditions on dit que l'on vient de "charger le registre" avec
une nouvelle valeur. Notations des diffrents type de registres
:
37. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 36 registre srie/srie registre srie/parallle
registre parallle/srie registre parallle/parallle Registre dcalage
C'est un registre entre srie ou parallle qui dcale de 1 bit tous
les bits d'entre soit vers "la droite" (vers les bits de poids
faibles), soit vers "la gauche" (vers les bits de poids forts). Un
registre dcalage dans un ordinateur correspond soit une
multiplication par 2 dans le cas du dcalage gauche, soit une
division par 2 dans le cas du dcalage droite. Conclusion
mmoire-registre Nous remarquons donc que les registres en gnral
sont des mmoires construites avec des bascules dans lesquelles on
peut lire et crire des informations sous forme de bits. Toutefois
ds que la quantit d'information stocker est trs grande les bascules
prennent physiquement trop de place (2 NOR, 2 AND et 1 NON).
Actuellement, pour laborer une mmoire stockant de trs grande
quantit d'informations, on utilise une technologie plus compacte
que celle des bascules, elle est fonde sur la reprsentation d'un
bit par 1 transistor et 1 condensateur. Le transistor ralise la
porte d'entre du bit et la sortie du bit, le condensateur selon sa
charge ralise le stockage du bit. Malheureusement un condensateur
ne conserve pas sa charge au cours du temps (courant de fuite
inhrent au condensateur), il est alors indispensable de restaurer
de temps en temps la charge du condensateur (opration que l'on
dnomme rafrachir la mmoire) et cette opration de rafrachissement
mmoire a un cot en temps de ralisation. Ce qui veut donc dire que
pour le mme nombre de bits stocker un registre bascule est plus
rapide lire ou crire qu'une mmoire transistor, c'est pourquoi les
mmoires internes des processeurs centraux sont des registres.
38. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 37 3.11 Mmoire SRAM et mmoire DRAM Dans un
ordinateur actuel coexistent deux catgories de mmoires : 1) Les
mmoires statiques SRAM labores l'aide de bascules : trs rapides
mais volumineuses (plusieurs transistors pour 1 bit). 2) Les
mmoires dynamiques DRAM labores avec un seul transistor coupl un
condensateur : trs facilement intgrables dans une petite surface,
mais plus lente que les SRAM cause de la ncessit du
rafrachissement. Voici titre indicatif des ordres de grandeur qui
peuvent varier avec les innovations technologiques rapides en ce
domaine : SRAM temps d'accs une information : 5 nanosecondes DRAM
temps d'accs une information : 50 nanosecondes Fonctionnement d'une
DRAM de 256 Mo fictive La mmoire physique aspect extrieur : Le
schma gnral de la mmoire : Vcc = alimentation lectrique D1 D8 =
bits de donnes (1 octet ici) Ligne, Colonne = lignes de slection
soit d'une adresse de ligne soit d'une adresse de colonne W =
autorisation d'criture R = validation de lecture A0, , A13 =
adresse d'une ligne ou adresse d'une colonne = symbole de mise la
masse Nous adoptons une vision abstraite de l'organisation interne
de cette mmoire sous forme d'une matrice de 214 lignes et 214
colonnes soient en tout 214 . 214 = 228 cellules de 1 octet chacune
(228 octets = 28 . 220 o = 256 . 220 o = 256 Mo, car 1 Mo = 220 o)
Ce qui donne une matrice de 16384 lignes et 16384 colonnes,
numrotes par exemple de 20 = 1
39. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 38 jusqu' 214 = 16384, selon la figure ci-dessous
: Dans l'exemple gauche : La slection d'une ligne de numro m donn
(d'adresse m-1 donne) et d'une colonne de numro k donn (d'adresse
k-1 donne) permet de slectionner directement une cellule contenant
8 bits. Exemple de slection de ligne dans la matrice mmoire partir
d'une adresse (A0, , A13) , dans notre exemple thorique la ligne de
numro 20 = 1 a pour adresse (0,0,,0) et la ligne de numro 214 =
16384 a pour adresse (1,1,,1). Lorsque l'adresse de slection d'une
ligne arrive sur les pattes (A0, , A13) de la mmoire elle est range
dans un registre interne (not tampon) puis passe un circuit interne
du type dcodeur d'adresse 14 bits (14 entres et 214 = 16384
sorties) qui slectionne la ligne adquate. Il en va de mme pour la
slection d'une colonne :
40. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 39 La slection d'une ligne, puis d'une colonne
permet d'obtenir sur les pattes D, D2, , D8 de la puce les 8 bits
slectionns. Ci dessous une slection en mode lecture d'une cellule
de notre mmoire de 256 Mo : Il est possible aussi d'crire dans une
cellule de la mmoire selon la mme dmarche de slection. Pour oprer
une lecture il faut que la ligne de validation R de la mmoire soit
active, pour oprer une criture, il faut que la ligne de validation
W de la mmoire soit active. En attendant une nouvelle technologie
(optique, quantique, organique,) les constituants de base d'un
ordinateur sont fonds sur l'lectronique base de transistor
dcouverts la fin des annes quarante. De nos jours deux technologie
de transistor sont prsentes sur le march : la technologie TTL
(Transistor Transistor Logic) la plus ancienne et la technologie
MOS (Metal Oxyde Semi- conductor).
41. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 40 3.12 Afficheur LED 7 segments On utilise dans
les ordinateurs des afficheurs LED, composs de 7 led diffrentes qui
sont allumes indpendamment les unes des autres, un circuit dcodeur
3 bits permet de raliser simplement cet affichage : 3.13 Compteurs
Ce sont des circuits chargs d'effectuer un comptage cumulatif de
divers signaux. Par exemple considrons un compteur sur 2 bits avec
retenue ventuelle, capable d'tre activ ou dsactiv, permettant de
compter les changement d'tat de la ligne d'horloge CLK. Nous
proposons d'utiliser deux demi-additionneurs et deux bascules de
type D pour construire le circuit. Le circuit compteur de gauche
possde deux entres En et CLK, il possde trois sorties a0, a1 et
carry. Ce compteur sort sur les bits a0, a1 et sur le bit de carry
le nombre de changements en binaire de la ligne CLK (maximum 4 pour
2 bits) avec retenue s'il y a lieu. La ligne d'entre En est charge
d'activer ou de dsactiver le compteur Notation pour ce compteur
:
42. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 41 Fonctionnement de l'entre En (enable) du
compteur prcdent : Lorsque En = 0, sur la premire bascule en entre
D nous avons D = a0 0 (or nous savons que : x, x 0 = x ), donc D =
a0 et Q ne change pas de valeur. Il en est de mme pour la deuxime
bascule et son entre D vaut a1. Donc quoiqu'il se passe sur la
ligne CLK les sorties a0 et a1 ne changent pas, on peut donc dire
que le comptage est dsactiv lorsque le enable est zro. Lorsque En =
1, sur la premire bascule en entre D nous avons D = a0 1 (or nous
savons que : x, x 1 = x ), donc Q change de valeur. On peut donc
dire que le comptage est activ lorsque le enable est un. Utilisons
la notation du demi-additionneur pour reprsenter ce compteur 2 bits
: un demi-additionneur le compteur 2 bits En gnralisant la notion
de compteur n bits nous obtenons le schma ci-aprs :
43. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 42 3.14 Ralisation lectronique de circuits
boolens Dans ce paragraphe nous indiquons pour information
anecdotique au lecteur, partir de quelques exemples de schmas
lectroniques de base, les ralisation physiques possibles de
diffrents oprateurs de l'algbre de Boole. Le transistor est
principalement utilis comme un interrupteur lectronique, nous
utiliserons les schmas suivants reprsentant un transistor soit en
TTL ou MOS et une diode. Circuits (ET, OU , NON) labors partir de
diodes : NON OU ET Circuits (NOR, NAND , NON) labors partir de
transistor MOS : NON NAND NOR Ce sont en fait la place occupe par
les composants lectroniques et leur cot de production qui sont les
facteurs essentiels de choix pour la construction des oprateurs
logiques de base.
44. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 43 Voici par exemple une autre faon de construire
une circuit NOR partir de transistor et de diodes : Le lecteur
intress consultera des ouvrages d'lectronique spcialiss afin
d'approfondir ce domaine qui dpasse le champ de l'informatique qui
n'est qu'une simple utilisatrice de la technologie lectronique en
attendant mieux ! Finissons ce paragraphe, afin de bien fixer nos
ides, par un schma montrant comment dans une puce lectronique sont
situs les circuits boolens : Supposons que la puce prcdente
permette de raliser plusieurs fonctions et contienne par exemple 4
circuits boolens : un OU, un ET, deux NON. Voici figur une possible
implantation physique de ces 4 circuits dans la puce, ainsi que la
liaison de chaque circuit boolen avec les pattes du composant
physique : Pour information, le micro-processeur pentium IV
Northwood de la socit Intel contient environ 55 000 000 (55
millions) de tansistors, le micro-processeur 64 bits Opteron de la
socit concurrente AMD plus rcent que le pentium IV, contient 105
000 000 (105 millions) de transistor.
45. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 44 1.3 Codage numration Plan du chapitre: 1.
Codage de linformation 1.1 Codage en gnral : le pourquoi 1.2 Codage
des caractres : code ASCII 1.3 Codage des nombres entiers :
numration 1.4 Les entiers dans une mmoire n+1 bits 1.5 Codage des
nombres entiers 1.6 Un autre codage des nombres entiers 2.
Numration 2.1 Oprations en binaire 2.2 Conversions base quelconque
dcimal 2.3 Exemple de conversion dcimal binaire 2.4 Exemple de
conversion binaire dcimal 2.5 Conversion binaire hexadcimal 2.6
Conversion hexadcimal binaire
46. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 45 1. Codage de linformation 1.1 Codage en gnral
: le pourquoi Dans une machine, toutes les informations sont codes
sous forme d'une suite de "0" et de "1" (langage binaire). Mais
l'tre humain ne parle gnralement pas couramment le langage binaire.
Il doit donc tout "traduire" pour que la machine puisse excuter les
instructions relatives aux informations qu'on peut lui donner. Le
codage tant une opration purement humaine, il faut produire des
algorithmes qui permettront la machine de traduire les informations
que nous voulons lui voir traiter. Le codage est une opration
tablissant une bijection entre une information et une suite de " 0
" et de " 1 " qui sont reprsentables en machine. 1.2 Codage des
caractres : code ASCII Parmi les codages les plus connus et
utiliss, le codage ASCII (American Standard Code for Information
Interchange)tendu est le plus courant (version ANSI sur Windows).
Voyons quelles sont les ncessits minimales pour lcriture de
documents alphanumriques simples dans la civilisation occidentale.
Nous avons besoin de : Un alphabet de lettres minuscules ={a, b,
c,...,z} soient 26 caractres Un alphabet de lettres majuscules
={A,B,C,...,Z} soient 26 caractres Des chiffres {0,1,...,9} soient
10 caractres Des symboles syntaxiques {? , ; ( " ... au minimum 10
caractres Soit un total minimal de 72 caractres Si lon avait choisi
un code 6 bits le nombre de caractres codables aurait t de 26 = 64
( tous les nombres binaires compris entre 000000 et 111111), nombre
donc insuffisant pour nos besoins. Il faut au minimum 1 bit de
plus, ce qui permet de dfinir ainsi 27 = 128 nombres binaires
diffrents, autorisant alors le codage de 128 caractres.
47. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 46 Initialement le code ASCII est un code 7 bits
(27 = 128 caractres). Il a t tendu un code sur 8 bits ( 28 = 256
caractres ) permettant le codage des caractres nationaux (en France
les caractres accentus comme : ,,,,,...etc) et les caractres
semi-graphiques. Les pages HTML qui sont diffuses sur le rseau
Internet sont en code ASCII 8 bits. Un codage rcent dit " universel
" est en cours de diffusion : il sagit du codage Unicode sur 16
bits (216 = 65536 caractres). De nombreux autres codages existent
adapts diverses solution de stockage de linformation (DCB,
EBCDIC,...). 1.3 Codage des nombres entiers : numration Les nombres
entiers peuvent tre cods comme des caractres ordinaires. Toutefois
les codages adopts pour les donnes autres que numriques sont trop
lourds manipuler dans un ordinateur. Du fait de sa constitution, un
ordinateur est plus " habile " manipuler des nombres crits en
numration binaire (qui est un codage particulier). Nous allons
dcrire trois modes de codage des entiers les plus connus. Nous
avons lhabitude dcrire nos nombres et de calculer dans le systme
dcimal. Il sagit en fait dun cas particulier de numration en base
10. Il est possible de reprsenter tous les nombres dans un systme
base b (b entier, b1). Nous ne prsenterons pas ici un cours
darithmtique, mais seulement les lments ncessaires lcriture dans
les deux systmes les plus utiliss en informatique : le binaire
(b=2) et lhexadcimal (b=16). Lorsque nous crivons 5876 en base 10,
la position des chiffres 5,8,7,6 indique la puissance de 10
laquelle ils sont associs : 5 est associ 103 8 est associ 102 7 est
associ 101 6 est associ 100 Il en est de mme dans une base b
quelconque (b=2, ou b=16). Nous conviendrons de mentionner la
valeur de la base au dessus du nombre afin de savoir quel est son
type de reprsentation. Soit un nombre x crit en base b avec n+1
symboles. " xk " est le symbole associ la puissance " bk " " xk "
{0,1, ... , b-1}
48. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 47 Lorsque b=2 (numration binaire) Chaque symbole
du nombre x, " xk " {0,1}; autrement dit les nombres binaires sont
donc crits avec des 0 et des 1, qui sont reprsents physiquement par
des bits dans la machine. Voici le schma dune mmoire n+1 bits (au
minimum 8 bits dans un micro-ordinateur) : Les cases du schma
reprsentent les bits, le chiffre marqu en dessous dune case,
indique la puissance de 2 laquelle est associ ce bit (on dit aussi
le rang du bit). Le bit de rang 0 est appel le bit de poids faible.
Le bit de rang n est appel le bit de poids fort. 1.4 Les entiers
dans une mmoire n+1 bits : binaire pur Ce codage est celui dans
lequel les nombres entiers naturels sont crits en numration binaire
(en base b=2). Le nombre " dix " scrit 10 en base b=10, il scrit
1010 en base b=2. Dans la mmoire ce nombre dix est cod en binaire
ainsi: Une mmoire n+1 bits (n>0), permet de reprsenter sous
forme binaire (en binaire pur) tous les entiers naturels de
l'intervalle [ 0 , 2n+1 -1 ]. soit pour n+1=8 bits, tous les
entiers de l'intervalle [ 0 , 255 ] soit pour n+1=16 bits, tous les
entiers de l'intervalle [ 0 , 65535 ] 1.5 Codage des nombres
entiers : binaire sign Ce codage permet la reprsentation des
nombres entiers relatifs. Dans la reprsentation en binaire sign, le
bit de poids fort ( bit de rang n associ 2n ) sert reprsenter le
signe (0 pour un entier positif et 1 pour un entier ngatif), les n
autres bits reprsentent la valeur absolue du nombre en binaire
pur.
49. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 48 Exemple du codage en binaire sign des nombres
+14 et -14 : +14 est reprsent par 0000...01110 -14 est reprsent par
1000...01110 Une mmoire n+1 bits (n>0), permet de reprsenter
sous forme binaire (en binaire sign) tous les entiers naturels de
l'intervalle [- (2n - 1) , (2n -1)] soit pour n+1=8 bits, tous les
entiers de l'intervalle [-127 , 127] soit pour n+1=16 bits, tous
les entiers de l'intervalle [-32767 , 32767] Le nombre zro est
reprsent dans cette convention (dites du zro positif) par :
0000...00000 Remarque : Il reste malgr tout une configuration
mmoire inutilise : 1000...00000. Cet tat binaire ne reprsente
priori aucun nombre entier ni positif ni ngatif de lintervalle [-
(2n - 1) , (2n -1)]. Afin de ne pas perdre inutilement la
configuration " 1000...00000 ", les informaticiens ont dcid que
cette configuration reprsente malgr tout un nombre ngatif parce que
le bit de signe est 1, et en mme temps la puissance du bit
contenant le "1", donc par convention -2n . Lintervalle de
reprsentation se trouve alors augment dun nombre : il devient :[-2n
,2n -1] soit pour n+1=8 bits, tous les entiers de l'intervalle
[-128 , 127] soit pour n+1=16 bits, tous les entiers de
l'intervalle [-32768 , 32767] Ce codage nest pas utilis tel quel,
il est donn ici titre pdagogique. En effet le traitement spcifique
du signe cote cher en circuits lectroniques et en temps de calcul.
Cest une version amliore qui est utilise dans la plupart des
calculateurs : elle se nomme le complment deux. 1.6 Un autre codage
des nombres entiers : complment deux Ce codage, purement
conventionnel et trs utilis de nos jours, est driv du binaire sign
; il sert reprsenter en mmoire les entiers relatifs. Comme dans le
binaire sign, la mmoire est divise en deux parties ingales; le bit
de poids fort reprsentant le signe, le reste reprsente la valeur
absolue avec le codage suivant : Supposons que la mmoire soit n+1
bits, soit x un entier relatif reprsenter :
50. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 49 si x > 0, alors c'est la convention en
binaire sign qui s'applique (le bit de signe vaut 0, les n bits
restants codent le nombre), soit pour le nombre +14 : +14 est
reprsent par 0000...01110 si x < 0, alors (3 tapes suivre) On
code la valeur absolue du nombre x, |x| en binaire sign. Puis lon
complmente tous les bits de la mmoire (complment 1 ou complment
restreint). Cette opration est un non logique effectu sur chaque
bit de la mmoire. Enfin lon additionne +1 au nombre binaire de la
mmoire (addition binaire). Exemple, soit reprsenter le nombre -14
en suivant les 3 tapes : codage de |-14|= 14 complment 1 addition
de 1 Le nombre -14 s'crit donc en complment 2 : 1111..10010. Un des
intrts majeurs de ce codage est dintgrer la soustraction dans
lopration de codage et de ne faire effectuer que des oprations
simples et rapides (non logique, addition de 1). Nous venons de
voir que le codage utilisait essentiellement la reprsentation d'un
nombre en binaire (la numration binaire) et qu'il fallait connatre
les rudiments de l'arithmtique binaire. Le paragraphe ci-aprs
traite de ce sujet.
51. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 50 2. Numration Ce paragraphe peut tre ignor par
ceux qui connaissent dj les lments de base des calculs en binaire
et des conversions binaire-dcimal-hexadcimal, dans le cas
contraire, il est conseill de le lire. Pour des commodits
d'criture, nous utilisons la notation indice pour reprsenter la
base d'un nombre en parallle de la reprsentation avec la barre au
dessus. Ainsi 14510 signifie le nombre 145 en base dix; 11010112
signifie 1101011 en binaire. 2.1 Oprations en binaire Nous avons
parl daddition en binaire ; comme dans le systme dcimal, il nous
faut connatre les tables daddition, de multiplication, etc... afin
deffectuer des calculs dans cette base. Heureusement en binaire,
elles sont trs simples : Exemples de calculs (109+19=12810
=100000002 ) et (22x5=110) : addition multiplication 1101101 +
10011 _____________ 100000002 =12810 10110 x 101 ____________ 10110
10110.. ___________ 11011102 =11010 Vous noterez que le procd est
identique celui que vous connaissez en dcimal. En hexadcimal (b=16)
il en est de mme. Dans ce cas les tables doprateurs sont trs
longues apprendre. Etant donn que le systme classique utilis par
chacun de nous est le systme dcimal, nous nous proposons de fournir
dune manire pratique les conversions usuelles permettant d'crire
les diverses reprsentations dun nombre entre les systmes dcimal,
binaire et hexadcimal.
52. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 51 2.2 Conversions base quelconque dcimal Voici
ci-dessous un rappel des mthodes gnrales permettant de convertir un
nombre en base b (b>1)en sa reprsentation dcimale et
rciproquement. A ) Soit un nombre crit en base b. Pour le convertir
en dcimal (base 10), il faut : convertir chaque symbole xk en son
quivalent ak en base 10, nous obtenons ainsi la suite de chiffres :
an,....,a0 Exemple, soit b=13, les symboles de la base 13 sont : {
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C } Si le chiffre xk de rang k
du nombre s'crit C, son quivalent en base 10 est ak=12 rcrire le
nombre comme une somme : effectuer tous les calculs en base 10
(somme, produit, puissance). B ) Soit " a " un nombre crit dcimal
et reprsenter en base b : La mthode utilise est un algorithme fond
sur la division euclidienne. Si a < b, il n'a pas besoin d'tre
converti. Si a = b, on peut diviser a par b. Et lon divise
successivement les diffrents quotients qk obtenus par la base b. De
manire gnrale on aura : a = bk .rk + bk-1 .rk-1 + ... + b.r1 + r0
(o ri est le reste de la division de a par b). En remplaant chaque
ri par son symbole quivalent pi en base b, nous obtenons :
53. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 52 Cet algorithme permet d'obtenir une
reprsentation de a dans la base b. Les pi quivalents en base 13
sont: r0 = 8 p0 = 8 r1 = 11 p1 = B r2 = 10 p2 = A r3 = 2 p3 = 2
Donc 623510 = 2AB813 Dans les deux paragraphes suivants nous allons
expliciter des exemples pratiques de ces mthodes dans le cas o la
base est 2 (binaire). 2.3 Exemple de conversion dcimal binaire Soit
le nombre dcimal 3510 , appliquons l'algorithme prcdent afin de
trouver les restes successifs : Donc : 3510 = 1000112
54. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 53 2.4 Exemple de conversion binaire dcimal Soit
le nombre binaire : 11011012 sa conversion en dcimal est immdiate :
11011012 = 26 +25 +23 +23 +22 +1 =64+32+8+4+1 =10910 Les
informaticiens, pour des raisons de commodit (manipulations
minimales de symboles), prfrent utiliser lhexadcimal plutt que le
binaire. Lhumain, contrairement la machine, a quelques difficults
fonctionner sur des suites importantes de 1 et de 0. Ainsi
lhexadcimal (sa base b=24 tant une puissance de 2) permet de
diviser, en moyenne, le nombre de symboles par un peu moins de 4
par rapport au mme nombre crit en binaire. Cest lunique raison
pratique qui justifie son utilisation ici. 2.5 Conversion binaire
hexadcimal Nous allons dtailler laction de conversion en 6 tapes
pratiques : Soit a un nombre crit en base 2 (tape 1). On dcompose
ce nombre par tranches de 4 bits partir du bit de poids faible
(tape 2). On complte la dernire tranche (celle des bits de poids
forts)par des 0 sil y a lieu (tape 3). On convertit chaque tranche
en son symbole de la base 16(tape 4). On rcrit sa place le nouveau
symbole par changements successifs de chaque groupe de 4 bits,(tape
5). Ainsi, on obtient le nombre crit en hexadcimal (tape 6).
Exemple : Soit le nombre 1111012 convertir en hxadcimal. Rsultat
obtenu : 1111012 = 3D16
55. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 54 2.6 Conversion hexadcimal binaire Cette
conversion est lopration inverse de la prcdente. Nous allons la
dtailler en 4 tapes : Soit a un nombre crit en base 16 (ETAPE 1).
On convertit chaque symbole hexadcimal du nombre en son criture
binaire (ncessitant au plus 4 bits) (ETAPE 2). Pour chaque tranche
de 4 bits, on complte les bits de poids fort par des 0 s'il y a
lieu (ETAPE 3). Le nombre " a " crit en binaire est obtenu en
regroupant toutes les tranches de 4 bits partir du bit de poids
faible, sous forme dun seul nombre binaire(ETAPE 4). Exemple : Soit
le nombre 23D516 convertir en binaire. Rsultat obtenu : 23D516 =
100011110101012
56. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 55 1.4 Formalisation de la notion d'ordinateur
Plan du chapitre: 1. Machine de Turing thorique 1.1 Dfinition :
machine de Turing 1.2 Dfinition : Etats de la machine 1.3 Dfinition
: Les rgles de la machine 2. La Machine de Turing physique 2.1
Constitution interne 2.2 Fonctionnement 2.3 Exemple : machine de
Turing arithmtique 2.4 Machine de Turing informatique
57. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 56 1. La Machine de Turing thorique Entre 1930 et
1936 le mathmaticien anglais A.Turing invente sur le papier une
machine fictive qui ne pouvait effectuer que 4 oprations lmentaires
que nous allons dcrire. Un des buts de Turing tait de faire rsoudre
par cette " machine " des problmes mathmatiques, et dtudier la
classe des problmes que cette machine pourrait rsoudre. Dfinitions
et notations (modle dterministe) Soit A un ensemble fini appel
alphabet dfini ainsi : A = { a1 ,..., an } ( A ) Soit = { D,G } une
paire 1.1 Dfinition : machine de Turing Nous appellerons machine de
Turing toute application T : T : E N x ( A) o E est un ensemble
fini non vide : E N x A 1.2 Dfinition : Etats de la machine Nous
appellerons Et ensemble des tats intrieurs de la machine T: Et = {
qi N , (ai A / (qi ,ai) Dom(T)) o ( x / (qi , x) Im(T)) } Dom(T) :
domaine de dfinition de T. Im(T) : image de T (les lments T(a) de N
x ( A), pour a E) Comme E est un ensemble fini, Et est
ncessairement un ensemble fini, donc il y a un nombre fini dtats
intrieurs nots qi. 1.3 Dfinition : Les rgles de la machine Nous
appellerons " ensemble des rgles " de la machine T, le graphe G de
lapplication T. Une rgle de T est un lment du graphe G de T.
58. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 57 On rappelle que le graphe de T est dfini comme
suit : G = {(a,b) E x [Et x ( A)] / b = T(a) } Notation : afin
dviter une certaine lourdeur dans lcriture nous conviendrons dcrire
les rgles en omettant les virgules et les parenthses. Exemple : la
rgle ( (qi ,a) , (qk ,b) ) est note : qi a qk b 2. La Machine de
Turing physique 2.1 Constitution interne Nous construisons une
machine de Turing physique constitue de : Une bote note UC munie
dune tte de lecture-criture et dun registre dtat. Un ruban de
papier suppos sans limite vers la gauche et vers la droite. Sur le
ruban se trouvent des cases contigus contenant chacune un seul
lment de lalphabet A. La tte de lecture-criture travaille sur la
case du ruban situe devant elle ; elle peut lire le contenu de
cette case ou effacer ce contenu et y crire un autre lment de A. Il
existe un dispositif dentranement permettant de dplacer la tte de
lecture-criture dune case vers la Droite ou vers la Gauche. Dans la
tte lecture-criture il existe une case spciale note registre dtat,
qui sert recevoir un lment qi de Et. Cette machine physique est une
reprsentation virtuelle d'une machine de Turing thorique T,
d'alphabet A, dont l'ensemble des tats est Et, dont le graphe est
donn ci-aprs : G = {(a,b) E x [Et x ( A)] / b = T(a) } Donnons une
visualisation schmatique d'une telle machine en cours de
fonctionnement. La tte de lecture/criture pointe vers une case
contenant l'lment ai de A, le registre d'tat ayant la valeur qk
:
59. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 58 2.2 Fonctionnement Dpart : On remplit les
cases du ruban dlments ai de A. On met la valeur " qk " dans le
registre dtat. On positionne la tte sur une case contenant " ai ".
Actions : (la machine se met en marche) La tte lit le " ai ". LUC
dont le registre dtat vaut " qk ", cherche dans la liste des rgles
si le couple (qk , ai) Dom(T). Si la rponse est ngative on dit que
la machine " bloque " (elle sarrte par blocage). Si la rponse est
positive alors le couple (qk , ai) a une image unique (machine
dterministe)que nous notons (qn , y). Dans ce couple, y ne peut
prendre que l'un des 3 types de valeurs possibles ap , D , G : a)
soit y=ap , dans ce cas la rgle est donc de la forme qk ai qn ap
a.1) LUC fait effacer le ai dans la case et le remplace par llment
ap. a.2) LUC crit qn dans le registre dtat en remplacement de la
valeur qk. b) soit y = D , ici la rgle est donc de la forme qk ai
qn D
60. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 59 b.1) LUC fait dplacer la tte vers la droite
dune case. b.2) LUC crit qn dans le registre dtat en remplacement
de la valeur qk. c) soit y = G , dans ce cas la rgle est donc de la
forme qk ai qn G c.1) LUC fait dplacer la tte vers la gauche d'une
case. c.2) LUC crit qn dans le registre dtat en remplacement de la
valeur qk. Puis la machine continue fonctionner en recommenant le
cycle des actions depuis le dbut : lecture du nouvel lment ak
etc... 2.3 Exemple : machine de Turing arithmtique Nous donnons
ci-dessous une machine T1 additionneuse en arithmtique unaire. A =
{#,1} ={D,G} un entier n est reprsent par n+1 symboles " 1 "
conscutifs (de faon pouvoir reprsenter " 0 " par un unique " 1
").
61. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 60 Etat initial du ruban avant actions : 2 3 2
est reprsent par 111 3 est reprsent par 1111 Rgles T1: (application
des rgles suivantes pour simulation de 2+3) q1 1 q2D q6 1 q7D q11 1
q12# q2 1 q3D q7 1 q8D q12 # q13G q3 1 q4D q8 1 q9D q13 1 q14# q4 #
q51 q9 1 q10D q5 1 q6D q10 # q11G En dmarrant la machine sur la
configuration prcdente on obtient : Etat final du ruban aprs
actions : (Cette machine ne fonctionne que pour additionner 2 et 3)
. 5 . . Gnralisation de la machine additionneuse Il est facile de
fournir une autre version plus gnrale T2 fonde sur la mme stratgie
et le mme tat initial permettant d'additionner non plus seulement
les nombres 2 et 3, mais des nombres entiers quelconques n et p. Il
suffit de construire des nouvelles rgles. Rgles de T2: q1 1 q1D q3
1 q3# q1 # q21 q3 # q4G q2 1 q2D q4 1 q5# q2 # q3G
62. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 61 Cette machine de Turing T2 applique l'exemple
prcdent (addition de 2 et 3) laisse le ruban dans le mme tat final,
mais elle est construite avec moins dtats intrieurs que la
prcdente. En fait elle fonctionne aussi si la tte de
lecture-criture est positionne sur nimporte lequel des lments du
premier nombre n. et les nombres n et p sont quelconques : Etat
initial sur le nombre de gauche Etat final la fin du nombre calcul
(il y a n+p+1 symboles " 1 ") Nous dirons que T2 est plus "
puissante " que T1 au sens suivant : T2 a moins dtats intrieurs que
T1 . T2 permet dadditionner des entiers quelconques. Il est
possible de dmarrer ltat initial sur nimporte lequel des " 1 " du
nombre de gauche. On pourrait toujours en ce sens chercher une
machine T3 qui possderait les qualits de T2 , mais qui pourrait
dmarrer sur nimporte lequel des " 1 " de lun ou lautre des deux
nombres n ou p, le lecteur est encourag chercher crire les rgles
d'une telle machine. Nous voyons que ces machines sont capables
deffectuer des oprations, elles permettent de dfinir la classe des
fonctions calculables (par machines de Turing). Un ordinateur est
fond sur les principes de calcul dune machine de Turing. J. Von
Neumann a dfini la structure gnrale dun ordinateur partir des
travaux de A.Turing. Les lments physiques supplmentaires que possde
un ordinateur moderne naugmentent pas sa puissance thorique. Les
fonctions calculables sont les seules que lon puisse implanter sur
un ordinateur. Les priphriques et autres dispositifs auxiliaires
extrieurs ou intrieurs nont pour effet que damliorer la " puissance
" en terme de vitesse et de capacit. Comme une petite voiture de
srie et un bolide de formule 1 partagent les mmes concepts de
motorisation, de la mme manire les diffrents ordinateurs du march
partagent les mmes fondements mathmatiques.
63. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 62 2.4 Machine de Turing informatique Nous
faisons voluer la reprsentation que nous avons de la machine de
Turing afin de pouvoir mieux la programmer, c'est dire pouvoir
crire plus facilement les rgles de fonctionnement d'une telle
machine. Nous dfinissons ce qu'est un algorithme pour une machine
de Turing et nous proposons une description graphique de cet
algorithme l'aide de schmas graphiques symboliques dcrivant des
actions de base d'une machine de Turing. A) Une machine de Turing
informatique est dite normalise au sens suivant : Lalphabet A
contient toujours le symbole " # " Lensemble des tats E contient
toujours deux tats distingus q0 (tat initial) et qf (tat final). La
machine dmarre toujours ltat initial q0 . Elle termine sans blocage
toujours ltat qf . Dans les autres cas on dit que la machine "
bloque ". B)Algorithme dune machine de Turing informatique Cest
lensemble des rgles prcises qui dfinissent un procd de calcul
destin obtenir en sortie un " rsultat " dtermin partir de certaines
" donnes " initiales. C) Algorithme graphique dune machine de
Turing Nous utilisons cinq classes de symboles graphiques
Positionne la tte de lecture sur le symbole voulu, met la machine
ltat initial q0 et fait dmarrer la machine. Signifie que la machine
termine correctement son calcul en sarrtant ltat final qf .
64. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 63 Aucune rgle de la machine ne permettant la
poursuite du fonctionnement, arrt de la machine sur un blocage.
Dplacer la tte dune case vers la gauche (la tte de lecture se
positionne sur la case davant la case actuelle contenant le symbole
ap). Correspond la rgle : qi ap qj G Correspond laction excuter
dans la deuxime partie de la rgle : qi ap qj ak (la machine crit ak
dans la case actuelle et passe ltat qj ). Correspond laction
excuter dans la premire partie de la rgle : qj ak ... ou qi # ...
(la machine teste le contenu de la case actuelle et passe ltat qj
ou ltat qi selon la valeur du contenu). D) Organigramme dune
machine de Turing On appelle organigramme dune machine de Turing T,
toute reprsentation graphique constitue de combinaisons des
symboles des cinq classes prcdentes. Les rgles de la forme qn ak qn
G ou qnakqnD se traduisent par des schmas " boucls " ce qui donne
des organigrammes non linaires.
65. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 64 diagramme pour :q0a q0G diagramme pour :q0a
q0D Exemple : organigramme de la machine T2 normalise(additionneuse
n+p) Rgles de T2 normalise : q0 1 q0D q2 1 q2# q0 # q11 q2 # q3G q1
1 q1D q3 1 qf# q1 # q2G
66. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 65 Nous voyons que ce symbolisme graphique est un
outil de description du mode de traitement de linformation au
niveau machine. Cest dailleurs historiquement dune faon semblable
que les premiers programmeurs dcrivaient leur programmes.
67. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 66 1.5 Architecture de l'ordinateur Plan du
chapitre: Les principaux constituants 1.1 Dans lUnit Centrale :
lunit de traitement 1.2 Dans lUnit Centrale : lunit de commande 1.3
Dans lUnit Centrale : les Units dchange 1.4 Exemples de machine une
adresse : un micro-processeur simple 1.5 Les Bus 1.6 Schma gnral
dune micro-machine fictive 1.7 Notion de jeu dinstructions-machine
1.8 Architectures RISC et CISC 1.9 Pipe line dans un processeur
1.10 Architectures super-scalaire 1.11 Principaux modes
d'adressages des instructions machines 2. Mmoires : Mmoire centrale
- Mmoire cache 2.1 Mmoire 2.2 Les diffrents types de mmoires 2.3
Les units de capacit 2.4 Mmoire centrale : dfinitions 2.5 Mmoire
centrale : caractristiques 2.6 Mmoire cache ( ECC, associative ) 3.
Une petite machine pdagogique 8 bits " PM " 3.1 Unit centrale de PM
(pico-machine) 3.2 Mmoire centrale de PM 3.3 Jeu dinstructions de
PM 4. Mmoire de masse (auxiliaire ou externe) 4.1 Disques
magntiques - disques durs 4.2 Disques optiques compacts - CD /
DVD
68. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 67 1. Les principaux constituants d'une machine
minimale Un ordinateur, nous lavons dj not, est compos dun centre
et dune priphrie. Nous allons nous intresser au cur dun ordinateur
fictif mono-processeur. Nous savons que celui-ci est compos de :
Une Unit centrale comportant : Unit de traitement, Unit de contrle,
Units dchanges. Une Mmoire Centrale. Nous dcrivons ci-aprs
l'architecture minimale illustrant simplement le fonctionnement
d'un ordinateur (machine de Von Neumann). 1.1 Dans lUnit Centrale :
lUnit de Traitement Elle est charge deffectuer les traitements des
oprations de types arithmtiques ou boolennes. LUAL est son
principal constituant. Elle est compose au minimum : dun registre
de donnes RD dun accumulateur ACC (pour les machines une adresse)
des registres spcialiss (pour les machines plusieurs adresses) dune
unit arithmtique et logique : UAL Schma gnral thorique de lunit de
traitement : machine une adresse machine plusieurs adresses
69. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 68 La fonction du registre de donnes (mmoire
rapide) est de contenir les donnes transitant entre lunit de
traitement et lextrieur. La fonction de laccumulateur est
principalement de contenir les oprandes ou les rsultats des
oprations de lUAL. La fonction de lUAL est deffectuer en binaire
les traitements des oprations qui lui sont soumises et qui sont au
minimum: Oprations arithmtiques binaires: addition,multiplication,
soustraction, division. Oprations boolennes : et, ou, non. Dcalages
dans un registre. Le rsultat de lopration est mis dans
laccumulateur (Acc) dans le cas d'une machine une adresse, dans des
registres internes dans le cas de plusieurs adresses. 1.2 Dans
lUnit Centrale : lUnit de Contrle ou de Commande Elle est charge de
commander et de grer tous les diffrents constituants de lordinateur
(contrler les changes, grer lenchanement des diffrentes
instructions, etc...) Elle est compose au minimum de : dun registre
instruction RI, dun compteur ordinal CO, dun registre adresse RA,
dun dcodeur de fonctions, dune horloge. Schma gnral de lunit de
contrle
70. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 69 Vocabulaire : Bit = plus petite unit
dinformation binaire (un objet physique ayant deux tats reprsente
un bit). Processeur central = unit de commande + unit de
traitement. IL a pour fonction de lire squentiellement les
instructions prsentes dans la mmoire, de dcoder une instruction, de
lire, crire et traiter les donnes situes dans la mmoire.
Instruction = une ligne de texte comportant un code opration, une
ou plusieurs rfrences aux oprandes. Soit linstruction fictive
daddition du contenu des deux mmoires x et y dont le rsultat est
mis dans une troisime mmoire z : (exemple d'instruction trois
adresses) | Oprateur | rfrences oprandes | Registre instruction =
contient linstruction en cours dexcution, elle demeure dans ce
registre pendant toute la dure de son excution. Compteur ordinal =
contient le moyen de calculer ladresse de la prochaine instruction
excuter. Registre adresse = contient ladresse de la prochaine
instruction excuter. Dcodeur de fonction = associ au registre
instruction, il analyse linstruction excuter et entreprend les
actions appropries dans lUAL ou dans la mmoire centrale. Au dbut,
la diffrentiation des processeurs s'effectuait en fonction du
nombre d'adresses contenues dans une instruction machine. De nos
jours, un micro-processeur comme le pentium par exemple, possde des
instructions une adresse, deux adresses, voir trois adresses dont
certaines sont des
71. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 70 registres. En fait deux architectures machines
coexistent sur le march : l'architecture RISC et l'architecture
CISC, sur lesquelles nous reviendrons plus loin. Historiquement
l'architecture CISC est la premire, mais les micro-processeur
rcents semblent utiliser un mlange de ces deux architectures
profitant ainsi du meilleur de chacune d'elle. Il existe de trs
bons ouvrages spcialiss uniquement dans l'architecture des
ordinateurs nous renvoyons le lecteur certains d'entre eux cits
dans la bibliographie. Dans ce chapitre notre objectif est de
fournir au lecteur le vocabulaire et les concepts de bases qui lui
sont ncessaires et utiles sur le domaine, ainsi que les notions
fondamentales qu'il retrouvera dans les architectures de machines
rcentes. L'volution matrielle est actuellement tellement rapide que
les ouvrages spcialiss sont mis jour en moyenne tous les deux ans.
1.3 Dans lUnit Centrale : les Units dchange Une unit dchange est
spcialise dans les entres/sorties. Ce peut tre un simple canal, un
circuit ou bien un processeur particulier. Cet organe est plac
entre la mmoire et un certain nombre de priphriques (dans un micro-
ordinateur ce sont des cartes comme la carte son, la carte vido,
etc...). Une unit dchange soulage le processeur central dans les
tches de gestion du transfert de linformation. Les priphriques sont
trs lents par rapport la vitesse du processeur (rapport de 1 109 ).
Si le processeur central tait charg de grer les changes avec les
priphriques il serait tellement ralenti quil passerait le plus
clair de son temps attendre. 1.4 Exemple de machine une adresse :
un micro-processeur simple Un micro-processeur simple a les mmes
caractristiques que celles dun processeur central avec un niveau de
complexit et de sophistication moindre. Il faut savoir que plus une
instruction machine contient d'adresses (de rfrences des oprandes),
plus le processeur est complexe. En effet avec les instructions une
adresse, le processeur est moins complexe en contre partie les
programmes (listes d'instructions machines) contiennent beaucoup
d'instructions et sont donc plus longs excuter que sur un matriel
dont le jeu d'instruction est plusieurs adressses. Un
micro-processeur simple est essentiellement une machine une
adresse, cest dire une partie code oprande et une rfrence un seul
oprande. Ce genre de machine est fond sur un cycle de passage par
laccumulateur. Lopration prcdente z = x + y , se dcompose dans une
telle machine fictivement en 3 oprations distinctes illustres par
la figure ci-aprs : LoadAcc x { chargement de laccumulateur avec x
: (1) } Add y { prparation des oprandes x et y vers lUAL : (2) } {
lancement commande de lopration dans lUAL : (3) } { rsultat transfr
dans laccumulateur : (3) } Store z { copie de laccumulateur dans z
: (4) }
72. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 71 Laccumulateur gardant son contenu au final.
Comparaison de "programme" ralisant le calcul de l'opration
prcdente "z = x + y "avec une machine une adresse et une machine
trois adresses : Une machine une adresse (3 instructions) Une
machine trois adresses (1 instruction) 1.5 Les Bus Un bus est un
dispositif destin assurer le transfert simultan dinformations entre
les divers composants dun ordinateur. On distingue trois catgories
de Bus : Bus dadresses (unidirectionnel) il permet lunit de
commande de transmettre les adresses rechercher et stocker.
73. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 72 Bus de donnes (bi-directionnel) sur lequel
circulent les instructions ou les donnes traiter ou dj traites en
vue de leur rangement. Bus de contrle (bi-directionnel) transporte
les ordres et les signaux de synchronisation provenant de lunit de
commande vers les divers organes de la machine. Il vhicule aussi
les divers signaux de rponse des composants. Largeur du bus Pour
certains Bus on dsigne par largeur du Bus, le nombre de bits qui
peuvent tre transports en mme temps par le Bus, on dit aussi
transports en parallle. Les principaux Bus de donnes rcents de
micro-ordinateur Les Bus de donnes sont essentiellement des bus
"synchrones", c'est dire qu'ils sont cadencs par une horloge
spcifique qui fonctionne un frquence fixe. Entre autres
informations commerciales, les constructeurs de Bus donnent en plus
de la frquence et pour des raison psychologiques, le dbit du Bus
qui est en fait la valeur du produit de la frquence par la largeur
du Bus, ce dbit correspond au nombre de bits par seconde transports
par le Bus. Quelques chiffres sur des Bus de donnes parallles des
annes 2000 BUS Largeur Frquence Dbit Utilisation PCI 64 bits 66 MHz
528 Mo/s Processeur/priphrique non graphique AGP 32 bits 66 MHz x 8
4 Go/s Processeur/carte graphique SCSI 16 bits 40 MHz 80 Mo/s
Echanges entres priphriques Il existe aussi des "Bus srie" ( Bus
qui transportent les bits les uns la suite des autres,
contrairement aux Bus parallles), les deux plus rcents concurrents
quipent les matriels de grande consommation : USB et Firewire. BUS
Dbit Nombre de priphriques accepts USB 1,5 Mo/s 127 USB2 60 Mo/s
127 Firewire 50 Mo/s 63 FirewireB 200 Mo/s 63 Ces Bus vitent de
connecter des priphriques divers comme les souris, les lecteurs de
DVD, les GSM, les scanners, les imprimantes, les appareils photo, ,
sur des ports spcifiques de la machine
74. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 73 1.6 Schma gnral dune micro-machine fictive une
adresse 1.7 Notion de jeu dinstructions-machine : Les premiers
programmes Comme dfini prcdemment, une instruction-machine est une
instruction qui est directement excutable par le processeur.
Lensemble de toutes les instructions-machine excutables par le
processeur sappelle le " jeu dinstructions " de lordinateur. Il est
compos au minimum de quatre grandes classes dinstructions dans les
micro-processeurs : instructions de traitement instructions de
branchement ou de droutement instructions dchanges instructions de
comparaisons Dautres classes peuvent tre ajoutes pour amliorer les
performances de la machine (instructions de gestion mmoire,
multimdias etc..) 1.8 Architectures CISC et RISC
Traditionnellement, depuis les annes 70 on dnomme processeur
architecture CISC (Complex Instruction Set Code) un processeur dont
le jeu d'instructions possde les proprits suivantes : Il contient
beaucoup de classes d'instructions diffrentes. Il contient beaucoup
de type d'instructions diffrentes complexes et de taille variable.
Il se sert de beaucoup de registres spcialiss et de peu de
registres gnraux. L'architecture RISC (Reduced Instruction Set
Code) est un concept mis en place par IBM dans les
75. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 74 annes 70, un processeur RISC est un processeur
dont le jeu d'instructions possde les proprits suivantes : Le
nombre de classes d'instructions diffrentes est rduit par rapport
un CISC. Les instructions sont de taille fixe. Il se sert de
beaucoup de registres gnraux. Il fonctionne avec un pipe-line
Depuis les dcennies 90, les microprocesseur adoptent le meilleur
des fonctionnalits de chaque architecture provoquant de fait la
disparition progressive de la diffrence entre RISC et CISC et le
invitables polmiques sur l'efficacit suppose meilleure de l'une ou
de l'autre architecture. 1.9 Pipe-line dans un processeur
Soulignons qu'un processeur est une machine squentielle ce qui
signifie que le cycle de traitement d'une instruction se droule
squentiellement. Supposons que par hypothse simplificatrice, une
instruction machine soit traite en 3 phases : 1 - lecture : dans le
registre instruction (RI) 2 - dcodage : extraction du code opration
et des oprandes 3 - excution : du traitement et stockage ventuel du
rsultat. Reprsentons chacune de ces 3 phases par une unit matrielle
distinctes dans le processeur (on appelle cette unit un "tage") et
figurons schmatiquement les 3 tages de traitement d'une instruction
: Supposons que suivions pas pas l'excution des 4 instructions
machines suivants le long des 3 tages prcdents : ADD 100, 200, 300
MUL 150, 250, 350 DIV 300, 200, 120 MOV 100, 500 Chacune des 4
instruction est traite squentiellement en 3 phases sur chacun des
tages; une fois une instruction traite par le dernier tage (tage
d'excution) le processeur passe l'instruction suivante et la traite
au premier tage et ainsi de suite :
76. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 75 Traitement de la premire instruction ADD 100,
200, 300 On remarquera que : Pendant le temps d'activation d'un
tage, les deux autres restent inactifs. Il faut attendre la fin du
traitement de l'instruction ADD 100, 200, 300 pour pouvoir passer
au traitement de l'instruction MUL 150, 250, 350 etc Le cycle
recommence identique pour l'instruction MUL 150, 250, 350
L'architecture pipe-line consiste optimiser les temps d'attente de
chaque tage, en commenant le traitement de l'instruction suivante
ds que l'tage de lecture a t libr par l'instruction en cours, et de
procder identiquement pour chaque tage de telle faon que durant
chaque phase, tous les tages soient occups fonctionner (chacun sur
une instruction diffrente). A un instant t0 donn l'tage d'excution
travaille sur les actions effectuer pour l'instruction de rang n,
l'tage de dcodage travaille sur le dcodage de l'instruction de rang
n+1, et l'tage de lecture sur la lecture de l'instruction de rang
n+2. Il est clair que cette technique dnomme architecture pipe-line
acclre le traitement d'une instruction donne, puisqu' la fin de
chaque phase une instruction est traite en entier. Le nombre
d'units diffrentes constituant le pipe-line s'appelle le nombre
d'tages du pipe-line.
77. Les bases de linformatique - programmation - ( rv.
04.01.2005 ) page 76 La figure ci-dessous illustre le dmarrage du
traitement des 4 instructions selon un pipe-line 3 tages (lecture,
dcodage, excution) : etc Priode initiale (une seule fois au
dmarrage) Chaque tage se met en route Excution de l'instruction ADD
Excution de l'instruction MUL La prochaine phase verra la fin de
l'excution de l'instruction DIV, 1.10 Architecture super-scalaire
On dit qu'un processeur est super-scalaire lorsqu'il possde
plusieurs pipe-lines indpendants dans lesquels plusieurs
instructions peuvent tre traites simultanment. Dans ce type
d'architecture apparat la notion de paralllisme avec ses
contraintes de dpendances (par exemple lorsqu'une instruction
ncessite le rsultat de la prcdente pour s'excuter, ou encore
lorsque deux instructions accdent la mme ressource mmoire,).
Examinons l'excution de notre exemple 4 instructions sur un
processeur super-scalaire 2 pipe- lines. Nous supposons nous
trouver dans le cas idal p
