UNIVERSITATEA “BABES-BOLYAI” CLUJ-NAPOCA
Facultatea de Centrul de Formare Continuă
Matematică
şi Informatică
şi Invăţământ la Distanţă
Presa
Universitară Clujeană
2000
Cuprins
0 Prefaţă 5
1 BAZE DE NUMERAŢIE.. 7
1.1 Elemente de aritmetică 7
1.1.1 Impărţirea cu rest şi
cmmdc.. 7
1.1.2 Funcţii de tip parte
întreagă 8
1.2 Tipuri de sisteme de numeraţie 9
1.2.1 Sistemul de numeraţie aditiv
(roman) 10
1.2.2 Sistemul de numeraţie
poziţional (arab) 11
1.3 Sisteme poziţionale de numeraţie în diverse
baze 11
1.3.1 Reprezentarea numerelor naturale
într-o bază b 11
1.3.2 Reprezentarea numerelor reale într-o
bază b 13
1.4 Conversii între baze de numeraţie 16
1.4.1 Conversia întregilor prin
împărţiri succesive 16
1.4.2 Conversia părţilor
fracţionare prin înmulţiri succesive 18
1.4.3 Conversia prin metoda
substituţiei 21
1.4.4 Sumar al conversiilor între baze 22
1.4.5 Conversie rapidă între bazele 8
şi 10 22
1.5 Relaţii între bazele 2, 8 şi 16 23
1.5.1 Cifre binare, octale, zecimale, hexazecimale 24
1.5.2 Conversii binar - octal 24
1.5.3 Conversii binar - hexazecimal 26
1.5.4 Conversii octal - hexazecimal 27
1.6 Operatii cu numere mari, în baze de numeraţie mari 28
1.6.1 Adunarea 29
1.6.2 Scăderea 30
1.6.3 Inmulţirea 31
1.6.4 Impărţirea 33
2 ALGEBRA BOOLEANA 37
2.1 Elemente de algebră booleană 37
2.1.1 Mulţimea B2;
operaţii 37
2.1.2 Funcţii booleene şi
reprezentări ale lor 39
2.2 Simplificarea funcţiilor booleene 40
2.2.1 Forme normale 40
2.2.2 Problema simplificării
funcţiilor booleene 41
2.2.3 Metoda tabelelor lui Karnaugh 43
2.2.4 Metoda implicanţilor primi
(Quine – McCluskey) 46
2.3 Circuite combinationale..... 49
2.3.1 Circuite poartă şi
realizarea lor fizică 49
2.3.2 Implementarea funcţiilor
booleene folosind circuite poartă 50
2.4 Câteva circuite remarcabile 52
2.4.1 Circuite de însumare binară 52
2.4.2 Circuite de deplasare 55
2.4.3 Circuit multiplexor 55
2.4.4 Circuit selector 56
2.4.5 Gestiunea bitului de paritate 57
3 CODIFICAREA INFORMATIEI 59
3.1 Noţiunea de cod; exemple. 59
3.1.1 Definirea codului 59
3.1.2 Exemple simple de coduri 60
3.1.3 Problema decodificării 61
3.2 Codificarea datelor în calculator 62
3.2.1 Codificarea caracterelor 62
3.2.2 Codificări zecimale ale
numerelor întregi 66
4 REPREZENTAREA NUMERELOR REALE........... 68
4.1 Reprezentarea în virgulă fixă 68
4.2 Reprezentarea în virgulă flotantă 70
4.2.1 Principiile reprezentărilor în
virgulă flotantă 70
4.2.2 Standarde de reprezentare în
virgulă flotantă 73
4.3 Conceptul de depăşire 78
4.4 Compararea numerelor reale...... 80
5 CODIFICARI BINARE SI ARITMETICA
BINARA A NUMERELOR INTREGI....... 82
5.1 Dimensiuni şi tipuri de reprezenări 82
5.2 Aritmetica numerelor întregi fără semn 83
5.2.1 Convenţia de reprezentare
fără semn 83
5.2.2 Adunarea şi scăderea
fără semn 84
5.2.3 Inmulţirea întregilor
fără semn 86
5.2.4 Impărţirea întregilor
fără semn 88
5.3 Reprezentări ale întregilor cu semn. 89
5.3.1 Particularizări ale reprezentării
în virgulă fixă 89
5.3.2 Coduri de reprezentare a întregilor
cu semn 90
5.4 Operaţiile aritmetice în cod complementar 96
5.4.1 Suma algebrică în cod
complementar 96
5.4.2 Inmulţirea în cod complementar 99
5.4.3 Impărţirea în cod
complementar 100
6 CODURI DETECTOARE DE ERORI.. 103
6.1 Problema transmiterii informaţiei 103
6.2 Coduri liniare binare.. 104
6.2.1 Control prin bit de paritate 104
6.2.2 Definirea codului liniar binar 105
6.2.3 Relaţii de control în coduri
liniare binare 107
6.2.4 Evaluarea capacităţii de
detecţie a codurilor liniare binare 109
6.2.5 Coduri iterative 110
7 Aplicaţii aritmetice în
criptografie 113
7.1 Terminologie 113
7.2 Sistemul DES (Data Encryption Standard) 114
7.3 Sisteme de cifrare cu chei publice. 116
7.3.1 Sisteme de cifrare
exponenţială RSA 118
7.3.2 Cifrul El Gamal 122
7.4 Dificultatea spargerii cifrurilor de tip exponenţial 123
8 SISTEME DE CALCUL 125
8.1 Principiile von Neumann de construire a unui calculator 125
8.2 Modelul formal al unui calculator 126
8.3 Structura şi componentele unui SC 127
8.3.1 Structura şi funcţiile
hardware. 127
8.3.2 Memoria 127
8.3.3 Componenta de prelucrare 129
8.3.4 Periferice: clasificări 129
8.3.5 Componenta de control 130
8.3.6 Caracteristici hard ale suporturilor
de tip disc 130
8.3.7 Videoterminale 132
8.4 Structura unui bloc de informaţie pe suport magnetic 133
8.5 reprezentarea în memorie a datelor numerice 136
8.5.1 Un program "ciudat" 136
8.6 Reprezentări numerice în implementări de
limbaje 139
8.7 Ordinea de plasare la diverse maşini.. 140
9 Probleme propuse spre rezolvare 146
9.1 Implementări privind bazele de numeraţie 146
9.2 Simplificarea funcţiilor booleene şi circuite 146
9.3 Codificarea caracterelor 148
9.4 Reprezentări ale numerelor reale.... 148
9.5 Reprezentarea numerelor întregi. 149
9.6 Coduri detectoare de erori 150
9.7 Elemente de criptografie 151
9.8 Sisteme de calcul. 151
10 B I B L I O G R A F I E.. 153
Deşi tehnologia
construcţiei calculatoarelor a evoluat extrem de mult, mai ales în ultimii
10-15 ani, principiile fundamentale după caresunt construite sunt
aceleaşi ca şi acum 40 de ani. Funcţionarea unui calculator, cu
toată complexitatea lui,are ca suport matematic o serie de concepte
aritmetice şi algebrice simple: bazele de numeraţie, cele patru
operaţii în aceste baze, noţiunea de funcţie, elemente de
calculul propoziţiilor etc. Suportul electronic al unui calculator are la
bază materializarea fizică a cifrelor binare 0 şi 1, iar la
nivelul imediat superior are la bază circuitele poartă, cele care
materializează fizic operaţiile SI, SAU, NU şi SUMA modulo 2,
cunoscute din calculul propoziţiilor.
Lucrarea de faţă are ca
scop principal fundamentarea matematică a tehnologiei de construcţie
a calculatoarelor, deci prezentarea modului în care sunt combinate suportul
matematic şi cel electronic în vederea implementării principalelor
funcţiuni ale unui sistem de calcul. In acest scop se prezintă
"drumul" parcurs de cercetarea ştiinţifică de a
direcţiona şi dezvolta unele concepte şi tehnici proprii
aritmeticii, spre a putea fi implementate şi realizate fizic cât mai
eficient. Această eficienţă este urmărită numai la
nivel conceptual! Deci faptul că circuitele sunt realizate cu relee ca
acum 60 de ani, cu tuburi electronice ca acum 50 de ani, cu tranzistori ca acum
30 de ani sa cu circuite integrate pe scară foarte largă cum sunt
realizate în prezent, nu face decât să crească în mod spectaculos
viteza sau capacitatea componentei electronice respective, prelucrarea
informaţiei rămânând în esenţă aceeaşi.
Capitolul 1 abordează
problematica bazelor de numeraţie: reprezentarea numerelor într-o
anumită bază şi conversii între diverse baze. Este pus un accent
deosebit pe bazele 2, 8 şi 16, ca baze de largă utilizare în
informatică. Tot aici se tratează problematica operării cu
numere foarte mari, scrise în baze mari de numeraţie mari. Aritmeticile
mari au multiple aplicaţii acolo unde sunt necesare efectuarea unor
calcule cu precizie foarte mare, de ordinul a sute sau mii de cifre
semnificative.
Capitolul
2 este destinat algebrei booleene. Se definesc mai întâi principalele
operaţii booleene, algebra booleană, inelul boolean, funcţii
booleene, expresii booleene etc. Se definesc formele normale şi metodele
de simplificare a funcţiilor booleene. Ultima parte a capitolului
tratează circuitele combinaţionale. Cu ajutorul lor se
realizează fizic principalele funcţiuni a unităţii
aritmetice a unui calculator.
Capitolul 3 se ocupă de
codificarea şi reprezentarea informaţiei în calculator. Sunt
prezentate cele mai actuale principii de reprezentare a caracterelor şi a
numerelor.
Capitolele 4 şi 5 sunt destinate special
reprezentării numerelor. Aici sunt descrise funcţiile de reprezentare
binară a numerelor întregi şi reale, precum şi algoritmii
specifici folosiţi în construcţia calculatoarelor pentru efectuarea
celor patru operaţii. Cunoaşterea modurilor de reprezentare a
informaţiei în calculator este esenţială pentru orice
programator.
Capitolul 6 prezintă câteva
metode de codificare a informaţiei prin care să se asigure detectarea
posibilelor alterări de informaţii în timpul prelucrărilor.
Deoarece problematica codurilor detectoare şi corectoare de erori este
deosebit de vastă, aici sunt prezentate doar tehnicile folosite cel mai
frecvent în construcţia calculatoarelor.
Capitolul 7 abordează probleme
de criptografie. Am considerat util să abordăm această
tematică din două motive. Ma întâi că asigurarea confidenţialităţii
şi autentificării în comunicaţia între calculatoare este
astăzi o problemă crucială. Apoi, modelele de cifrare şi
descifrare sunt eminamente modele de calcul aritmetic folosind numere foarte
mari şi implicit, baze mari de numeraţie. Va fi benefic pentru
cititor să înţeleagă cât de simplu se realizează,
conceptual cifrarea şi descifrarea de către protagoniştii
autorizaţi, dar cât de greu, dacă nu imposibil aceste operaţii
pot fi efectuate de către intruşi rău intenţionaţi.
Capitolul 8 prezintă mai întâi
structura şi funcţiile unui sistem de calcul, pe de o parte ca un
sistem matematic formal, iar pe de altă parte într-o abordare
intuitivă descriindu-se principalele lui componente. Apoi tratează
probleme de principiu în reprezentarea şi plasarea datelor în memoria
internă şi pe suporturile magnetice externe. O secţiune
specială este destinată implementării reprezentărilor de
către diverse limbaje de programare. In această ediţie a
cărţii am inclus şi Java printre aceste limbaje.
Capitolul 9 conţine probleme
propuse pentru fiecare dintre capitolele precedente. Propunerile sunt fie
simple exerciţii care pot fi efectuate manual, fie studii matematice care
pot fi laborioase, fie propuneri de implementări prin intermediul unor
programe C, C++, Pascal sau Java.
Lucrarea se adresează în primul
rând studenţilor informaticieni, fie de la zi fie celor care studiază
în forma învăţământ la distanţă. Este utilă
însă şi specialiştilor, mai ales programatorilor. Prin nivelul
matematic de la care se pleacă ea este accesibilă într-o mare
măsură şi elevilor din liceele de matematică - fizică,
precum şi a celor din clasele speciale de informatică.
Prezenta
lucrare este în fapt o ediţie nouă a lucrărilor noastre [6]
şi [7], Prezenta ediţie conţine, după cum se poate
uşor constata, aduceri la zi şi îmbunătăţiri
substanţiale, impuse de evoluţiile rapide din domeniu,.
Contribuţia autorilor este: Boian Fl capitolele 1-6 şi 8-9; Bozga
Liana capitolul 7. Mulţumim anticipat pentru orice fel de observaţii
şi sugestii pentru o ediţie viitoare. In acest scop stau la
dispoziţie adresele noastre de email: florin@cs.ubbcluj.ro şi liana@cs.ubbcluj.ro
Cluj-Napoca,
octombrie 2000 Autorii