INFORMATIKA MATEMATIKAI ALAPJAI
Készítette: Kiss Szilvia ZKISZ informatikai szakcsoport
Az információ 1. Az információ fogalma Az érzékszerveinken keresztül megszerzett új ismereteket információnak nevezzük. Az információ lehet "sőrített" (pl. egy távirat szövege) és "terjengıs" is. Ez utóbbi "terjengısséget" nevezzük redundanciának (pl. egy lírai alkotás; a vasúti átjárót elıjelzı táblák).
2. Az információ közvetlen, illetve kódolt érzékelése a) Közvetlen érzékelés: • kódolatlan képinformációk pl.: egy természeti jelenség megfigyelése • kódolatlan hanginformációk pl.: egy koncert meghallgatása • egyéb információk (ízek, szagok, hı-, és mechanikai hatások, stb.) a többi
érzékszervvel pl. étel megízlelése, egy felület érdességének kézzel történı megállapítása b) Kódolt érzékelés: •kódolt képi információ: −írott információ: pl. kézírás, gépi írás, piktogram −speciális jelek: pl. zászlójelek, karjelzések, stb. •kódolt hanginformáció: −szóbeli információ: pl. anyanyelv, idegen nyelv −zenei információ: pl. kürtjelek, tam-tam dob, stb.
A jel 1. A jel fogalma A jelek az információ hordozására alkalmas szimbólumok. Ilyenek lehetnek például: − − − − −
a magyar abc betői a kottázáshoz alkalmazott jelek a karjelzések a térképeken alkalmazott jelek a közlekedési táblák, stb.
2. Az információ és a jel kapcsolata • a jelek alkalmasak az információ hordozására, de nem azonosak azzal • nem függ az információ attól, hogy milyen jelek hordozzák, csak
értelmezhetıek legyenek (pl.: közlekedési lámpa, illetve a rendır karjelzései) • a jelek számának változásával nem változik szükségszerően az információ tartalma (pl.: 174(10) = 10101110(2)) • azonos jelek más összefüggésekben különbözı információkat is hordozhatnak (pl.: 1994 jelenthet évszámot | irányítószámot)
3. Az informatika két alapvetı jeltípusa a) Analóg jelek Az adatok valamely fizikai mennyiség változása alapján tárolódnak. A fizikai mennyiség képviseli az információt. pl.: az áramerısség, a feszültség változásai b) Digitális jelek Az adatok számkódok alapján tárolódnak. A szám képezi az információt. A betőket is számokkal kódolják. Így a szöveg is számként értelmezett jelek kombinációjának összessége.
A jelátalakítás 1. A jelátalakítás szükségessége Az elektronikus kommunikáció esetén az információt át kell alakítani - technikai okok miatt - olyan jelekké, amely az ember számára nem értelmezhetı. Természetesen a vételhez újra vissza kell alakítani azt. Ezt az oda-visszaalakítást nevezik jelátalakításnak.
2. A kódolás, dekódolás fogalma A kódolás olyan mővelet, amely egy jelrendszer elemeihez egy másik jelrendszer elemeit elıre meghatározott szabályok szerint (kódkulcs) hozzárendeli. A dekódolás a kódolás fordított mővelete. Információ
Kód
Kódoló Kódoló
Dekódoló Dekódoló
Információ
3. Technikai kódok Egy kóddal, kódrendszerrel szembeni követelmény az egyszerőség, rövidség, egyértelmőség, bıvíthetıség. a) BCD kód (Binary Coded Decimal) Elsısorban a tízes számrendszerbeli számok ábrázolását segíti elı. Egy tízes számrendszerbeli helyérték ábrázolására 4 bitet használ. Ábrázolhatók azonban betők és egyéb jelek is, ekkor már 6 bitre van szükség, így 26 = 64 kódhoz rendelhetünk egy-egy karaktert. Például:
Információ
BCD kód
0 5 9 A D
000000 000101 001001 001010 001101
b) EBCDIC kód (Extended Binary Coded Decimal Interchange Code) A BCD kód kiterjesztett változata, amely már 8 bites, így 28 = 256 kódhoz rendelhetünk egy-egy karaktert. A nagy számítógépek kódrendszere. Például:
információ
EBCDIC kód
Hexadecimálisan
I R A T
11001001 11011001 11000001 11100011
(C9) (D9) (C1) (E3)
c) ASCII kód (American Standard Code for Information Interchange) A mikroszámítógépek kódja, amely 8 bites, így szintén 256 kóddal rendelkezik. Az angol ábécé, decimális számjegyek, írásjelek, aritmetikai és logikai mőveleti jelek, vezérlıjelek ábrázolása lehetséges. Emellett beállíthatók nemzeti karakterkészletek is.
Az adat 1. Az adat fogalma Az információt nagyon sokféle módon lehet megjeleníteni. Így például a mostani információt - a magyar abc jelei alapján - "kódolva" jelenítettük meg. Ilyen értelemben az adat nem más, mint kódolt információ. A számítástechnikában sokszor csak a valamilyen formában rögzített információt nevezik adatnak. Például egy mágneses adattároló eszközön, a floppy-n rögzített információt. Az adat az információ megjelenített, rögzített formája.
2. Az adat megjelenési formái •Szám (numerikus adat): 1,2,3,4,…,9 •Szöveg (alfanumerikus adat):
−Betők: A, a, B, b, ... −Számok: 1,2,3,4,…,9 (A numerikus adatokkal ellentétben számítási mőveletekre nem alkalmasak.) −Írásjelek: .,;-?!… −mőveleti jelek: + - / * ^ … −speciális jelek: @ $ # & ... •Logikai adat: az állítások tartalmának megfelelıen kétféle lehet, igaz (true),
vagy hamis (false)
Számítógépes adatábrázolás A számítógépes adatfeldolgozás ideje alatt az adatokat a számítógép tárolja. Ezt a tárolást adatábrázolásnak nevezzük, melynek fajtái – az elızıekben ismertetett adatok típusaitól függıen - a következık lehetnek •
számok ábrázolása
•
szöveges adatok ábrázolása
•
logikai adatok ábrázolása
Az ember a tízes számrendszert, a számítógép a - technikailag legegyszerőbben megvalósítható - kettes számrendszert használja. A számítógép-ember kommunikációban az kedvéért - a tizenhatos számrendszer alkalmazott.
egyszerőbb felírhatóság
Így az adatábrázolás elıtt ismerkedjünk meg a számrendszerekkel.
1. A decimális (tízes) számrendszer
Ennek alapján rögzítsünk néhány számrendszerrel kapcsolatos alapfogalmat: • Alapszám: Az egyes helyértékeken szerepelhetı különbözı együtthatók száma. A tízes számrendszer esetén: 10 • Helyérték: Az alapszám egészkitevıs hatványai. A tízes számrendszer esetén: 100, 101, 102, 103 … • Együttható: Az egyes helyértékeken szereplı szorzók. A tízes számrendszer esetén: 0,1,2...9 • A szám értékének meghatározása: Szám = ∑ (együttható * helyérték)
Pl: 2*1000 + 6*100 + 5*10 + 7*1 = 2657
2. A bináris (kettes) számrendszer A bináris számrendszerben is hasonlóan minden más számrendszerhez - helyértékek vannak, melyek a kettı hatványai szerint jobbról balra növekednek. Alapszám: 2 Együtthatók: 0,1
218(10) = 11011010(2) = 172(10) = 10101100(2) = 255(10) = 11111111(2) =
27 128
26 64
25 32
24 16
23 8
22 4
21 2
20 1
1 1 1
1 0 1
0 1 1
1 0 1
1 1 1
0 1 1
1 0 1
0 0 1
A számítógépben egy bináris helyértéket bitnek nevezünk, melynek állapota - a bináris számrendszer együtthatói alapján - 0 vagy 1 lehet.
3. A hexadecimális (16-os) számrendszer Alapszám: 16 Együtthatók: 0, 1, 2, ..., 9, A, B, C, D, E, F Mivel az együtthatók nem adhatók meg minden esetben a tízes számrendszerben alkalmazott számokkal, szükség volt a 9 utáni számokhoz egy-egy jelet hozzárendelni. Ezek a következık: A=10, B=11, C=12, D=13, E=14, F=15
163
162
161
160
4096
256
16
1
1 1 1
0 A 5
E 0 C
F 6 8
10EF16 = 433510 = 1A0616 =666210 = 15C816 = 557610 =
Pl.: 1*4096 + 0*256 + 14*16 + 15*1 =4335
4. Átváltások az egyes számrendszerek között a) Átváltás binárisból decimálisba Az átváltáskor az együtthatókkal (0,1) szorozzuk az adott helyértékeket. Például: 11001100(2)=1*27+1*26+0*25+0*24+1*23+1*22+0*21+0*20= 128+64+0+0+8+4+0+0 = 204(10) b) Átváltás decimálisból binárisba A decimális bináris átalakítást speciális formában, "maradékos osztás elve" alapján végezzük. Példaként nézzük az elızı feladat visszaalakítását: Baloldal 204 : 2 = 102 102 : 2 = 51 51 : 2 = 25 25 : 2 = 12 12 : 2 = 6 6:2=3 3:2=1 1:2=0
204 102 51 25 12 6 3 1 0
2 0 0 1 1 0 0 1 1
Jobboldal maradt: 0 maradt: 0 maradt: 1 maradt: 1 maradt: 0 maradt: 0 maradt: 1 maradt: 1
A bináris számot úgy kapjuk, hogy a maradékokat alulról felfelé összeolvassuk: 204(10) = 11001100(2)
c) Átváltás hexadecimálisból decimálisba Az átváltáskor az együtthatókkal (0, 1, 2 ... A, B, C, D, E, F ) szorozzuk az adott helyértékeket, majd összeadjuk ıket. Például: 10AC(16) = 1*163+0*162+A*161+C*160 = 4096+0+160+12 = 4268(10) d) Átváltás binárisból hexadecimálisba Mivel tudjuk, hogy egy hexadecimális számjeggyel négy bináris érték adható meg egyszerő módon végezhetı el az átalakítás. A bináris számjegyet jobbról négyes csoportokra osztjuk, utána külön- külön hexadecimális számra váltjuk, majd az így kapott eredményt sorban egymás mellé írjuk. Ha a balról a legelsı csoportban nincs 4 db bináris szám, akkor azok elé annyi 0-t írunk, hogy azok is egy teljes csoportot alkossanak (Mivel a számok elé és nem utána írtuk a nullákat, ezért a szám értéke nem változott meg.). Például:
c) Átváltás hexadecimálisból binárisba Az elv ugyanaz, mint az elızı pontban, vagyis minden hexadecimális számjegybıl egy bináris számnégyest készítünk, és az így kapott eredményt sorban egymás mellé írjuk. Például:
5. Mőveletvégzés az egyes számrendszerekben a) Bináris összeadás Az összeadás mőveleti szabályai: 0+0=0 0+1=1 1+0=1 1 + 1 = 10 = 10 1 + 1 + 1 = 11 = 11 Példa a bináris összeadásra a decimális megfelelıjével történı ellenırzéssel:
b) Bináris kivonás A számítógép tervezésekor arra törekedtek, hogy minél kevesebb mőveletet kelljen ismernie a számítógép központi egységének. Így az összes mőveletet az összeadásra vezették vissza. Így az összeadással elvégzett kivonás elött a negatív számokat speciális formára, komplemenssé kell alakítani. Példaként nézzük meg a −168(10)-as, azaz a 10101000(2) szám átalakítását. Egyes komplemens képzése: Lépés
Mővelet
Eredmény
1. 2.
abszolút érték felírása egyes komplemens képzése
10101000(2) 01010111(2)
A biteket ellenkezıjére váltjuk.
Az egyes komplemens képzésekor problémaként vetıdik fel, hogy így a nullára két kód is van: 00000000(2) = " +0 " 11111111(2) = " −0 " Erre megoldást kínál a kettes komplemens képzés. Kettes komplemens képzésére nézzük az elızı példát: Lépés
Mővelet
Eredmény
1. 2. 3.
abszolút érték felírása egyes komplemens képzése kettes komplemens képzése
10101000(2) 01010111(2) 01011000(2)
Az egyes komplemenshez 1-et hozzáadunk.
Ezek után nézzünk konkrét példát a bináris kivonásra. Végezzük el a következı mőveletet: 184(10) – 100(10) Lépés Mővelet 1. – 100(10) abszolút értékének felírása 2. A kettes komplemes meghatározása 3. A kivonás elvégzése: 184 - 100 84(10)
Eredmény 01100100(2) 10011100(2) 10111000 + 10011100 101010100(2)
Túlcsordult számjegy.
A számítástechnikában mindig elıre rögzítenünk kell a számok ábrázolásának hosszát. Mivel a 184(10) nyolc bináris számjegy hosszúságú, ezért ezt a hosszúságot rögzítettük. Így a –100 bináris alakját is egy 0-val kiegészítve 8 jegybıl állóra alakítottuk. A végeredmény azonban ennél hosszabb számot eredményezett. Mivel az ábrázoláshoz továbbra is csak 8 jegynyi hely áll rendelkezésünkre, ezért az ún. túlcsordulás következett be, amely számjegyek “elvesztek”. Gyızıdjünk meg róla, hogy így kaptuk meg a helyes eredményt.
6. Az adatábrázolás alapegységei a) Bit A bináris szám egy helyértékét bitnek nevezzük. A bit állapota ennek megfelelıen 0 vagy 1 lehet. b) Byte 8 bit összekapcsolásával kialakított egység. c) Szó A processzor típusától függı érték. Jelenleg a 32 bites szervezéső processzorok az elterjedtek, így ezek esetében a 32 bitbıl kialakított egységet nevezzük szónak. 1 bit 1 Byte = 8 bit 1 szó = 4 Byte = 32 bit
Az eddigi ismereteink alapján tudjuk, hogy a tízes számrendszerben az 1Kilo az 1000-t jelenti. A bináris számrendszerben a helyértékek mások, így ebben az esetben az 1Kilo 1024-nek felel meg. Értelem szerően ennek megfelelıen változik a Mega, illetve a Giga értéke is. Ennek alapján a váltások: 1 Byte = 8 bit 1 KB = 1024 Byte = 8*1024 bit 1 MB = 1024 KB= 1024*1024 Byte= 8*1024*1024 bit 1 GB=1024 MB=1024*1024 KB=1024*1024*1024 Byte = 8*1024*1024*1024 bit
7. A számok ábrázolása a számítógépben Ez a számok mőveletvégzésre alkalmas formában történı tárolására szolgál.
a) Fixpontos ábrázolás Pozitív és negatív egész számok ábrázolására. A negatív számokat a már ismertetett kettes komplemens szerint értelmezik a gépek. Törtrésszel rendelkezı számokat is ábrázolhatunk, de ekkor a törtet jelzı pont csak logikailag létezik, a számítógép nem "teszi ki", helyét nem változtatja. Nyomtatásnál az elhelyezésérıl a programozónak kell gondoskodnia. A 2 Byte-on történı ábrázolás általános modellje:
A fixpontos számábrázolás hátrányai: • az ábrázolható tartomány kicsi: 2 Byte-on a legnagyobb 32.767, a legkisebb -32.768 • a számok pontossága erısen korlátozott: ha egész számot ábrázol 7/4 =1 és a 4 /4=1
b.) Lebegıpontos számábrázolás A fixpontos hátrányait kiküszöbölı, a számok hatványkitevıs (matematikában használt normál alakhoz hasonlatos) felírásán alapuló számábrázolás. Például: 175(10) = 0.175 * 103 10110011(2)= 0.10110011 * 28 0.375(10) = 0.375 * 100
0.011(2)
= 0.11 * 2-1
Általánosan felírva: A = M * pk A = az eredeti szám M = az együttható, ennek a tört része az ún. mantissza p = a hatvány alapja k = a hatvány kitevıje, az ún. karakterisztika Ebbıl észre vehetjük, hogy néhány elem minden szám esetén ismétlıdik, ezért ezeket a számítógépen nem kell külön ábrázolni.
Mi hagyható el? - 0 és a pont (.) - a hatvány alapja
Mi az ami megmarad? - mantissza ill. a mantissza elıjele - karakterisztika ill. a karakterisztika elıjele
b.) Lebegıpontos számábrázolás
A számokat 6 bájtos valós típusú mennyiségként ábrázoljuk Pl.: -23.1875 A mantissza egészrésze 23 1 (23÷2= 11 marad: 11 1 (11÷2= 5 marad: 5 1 ( 5÷2= 2 marad: 2 0 ( 2÷2= 1 marad: 1 1 ( 1÷2= 0 marad:
mantissza :
1 ≤ m ≤1 2 m∈ℝ
karakterisztika
k ∈ℤ
X = mi 2 k 1) 1) 1) 0) 1)
0
A mantissza törtrésze 0,1875 0 (0,1875×2=0, 0,375 375) 0,375 0 (0,375 ×2= 0,75 0,75) 0,75 1 (0,75 ×2= 1,5 1,5) 0,5 1 (0,5 ×2= 1,0 1,0) 0
b.) Lebegıpontos számábrázolás
A számokat 6 bájtos valós típusú mennyiségként ábrázoljuk Pl.: -23.1875 A mantissza egészrésze=10111 A mantissza törtrésze=0011
1 ≤ m ≤1 2 mantissza : m∈ℝ m = 10111.0011 karakterisztika k ∈ℤ 1 0 1 1 1. 0 0 1| 1 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | k k k k k k k k m = 0.101110011 X = mi 2 k
.1 0 1 1 1 0 0 1| 1 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | k k k k k k k k m = 0.101110011 k = 5 Normálás 0.1xxxx A pontot 5 lépéssel balra tettük
b.) Lebegıpontos számábrázolás
A mantissza elıjele m = 0.101110011 .1 0 1 1 1 0 0 1| 1 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | k k k k k k k k Ha a mantissza negatív, akkor legyen 1 különben legyen 0
X = mi 2 k mantissza : karakterisztika
1 ≤ m ≤1 2 m∈ℝ k ∈ℤ
m = 0.101110011 Mivel itt mindig 1 állna, ezért ez a bitet ruházzuk fel a mantissza elıjelének jelentésével
k =5
b.) Lebegıpontos számábrázolás A karakterisztika (kitevı) elıjele
A
karakterisztikát az ábrázolt 1 legkisebb szám abszolút X = mi2k ≤ m ≤1 2 értékével megnöveljük, azaz m∈ℝ hozzá adunk |-128|=128-at, mantissza : k ∈ℤ majd átváltjuk 2-es karakterisztika számrendszerbe. Tehát ha k=5, akkor k:=5+128=133 Ezt az alakot nevezzük 128-cal eltolt nullpontú ábrázolásnak
b.) Lebegıpontos számábrázolás A karakterisztika (kitevı) elıjele
A karakterisztika 133 1 (133÷2= 66 66 0 ( 66÷2= 33 33 1 ( 33÷2= 16 16 0 ( 16÷2= 8 8 0 ( 8÷2= 4 4 0 ( 4÷2= 2 2 0 ( 2÷2= 1 1 1 ( 1÷2= 0
X = mi 2 k marad: marad: marad: marad: marad: marad: marad: marad:
1) 0) 1) 0) 0) 0) 0) 1)
mantissza : karakterisztika
k=10000101
0
b.) Lebegıpontos számábrázolás A 6 bájtos normált ábrázolás eddigiek ismeretében:
Ábrázolható tartomány: konvenció (megállapodás): 0:= {k=-128, mantissza=tetszıleges} A legkisebb pozitív valós szám: 0.5 * 2-127 ≈2,938*10-39
1 ≤ m ≤1 2 m∈ℝ k ∈ℤ
8. Logikai mőveletek A számítógép nem csak - a számrendszereknél ismertetett - matematikai mőveletek, hanem logikai mőveletek végrehajtására is képes. A logikában állítások vannak, melyek vagy igazak vagy hamisak. Ennek megfelelıen a logikai adatok két értéket vehetnek fel: ha igaz, az értéke 1, ha hamis, az értéke 0. A logikai adatok ábrázolása általában 1Byte-on történik: • 00000001 = logikai igaz • 00000000 = logikai nem Ismerkedjünk meg néhány logikai mővelettel: a) Negálás (NOT) Olyan mővelet, amely során az igazból hamisra, a hamisból igazra váltunk.
A
¬A
0 1
1 0
b) ÉS kapcsolat (AND) A mővelet elvégzése után az eredmény akkor igaz, ha az A és B is igaz volt, miden más esetben hamis. A B A∧B 0 0 1 1
0 1 0 1
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
c) VAGY kapcsolat (OR) Az eredmény akkor igaz, ha vagy az A vagy a B is igaz volt, beleértve azt is, A B A∨B amikor mindkettı igaz.
d) KIZÁZÓ VAGY kapcsolat (XOR) Az eredmény kizárólag akkor igaz, ha vagy A vagy B igaz volt. Ez a kapcsolat kizárja azt az esetet, amikor mindkettı igaz. A
B
A⊕B
0 0 1 1
0 1 0 1
0 1 1 0
Gyakorló feladatok
Gyakorló feladatok
Gyakorló feladatok
