Positsioonilised arvusüsteemid ja andmed arvuti mälus

Bool'i loogika ja informatsiooniteooria

George Boole (1815-1864) oli inglise matemaatik. Tema panuseks praegusesse arvutiteadusesse võib pidada järgmisi saavutusi:

1847 – Loogika matemaatiline analüüs
1854 – Mõtlemise reeglid

G. Boole'i tegevuse eesmärgiks oli loogikatehete väljaarendamine ja "mõtlemise aritmeetika" ehitamine. Ta andis matemaatilise kuju lausearvutusele. Näiteks tähistused 1 ja 0 pärinevad just Boole'ilt.

Boole'i loogika ehk Boole'i algebra põhisisu:

Loogikaväited koosnevad lihtsamatest lausetest, mis on omavahel seotud loogikaseoste ehk tehetega (ja; või; ei; kui ..., siis ..., jne).
Lausearvutuse seoste korral määravad osalausete tõeväärtused kogu lause tõeväärtuse, osalausete konkreetne sisu ei ole aga tähtis.
Lausearvutuse tehteks nimetatakse niisugust lausetes kasutatavat seost, mille tõeväärtus on tema osalausete tõeväärtuste funktsioon (st sõltub osalausete tõeväärtustest) (e. Boole’i funktsioon).
Lausearvutuse tehe on defineeritud tõeväärtustabeliga (nn Boole’i funktsiooni graafik).
Tõeväärtused: tõene – T, 1 (true) ja väär – F,0 (false)

Claude Elwood Shannon (1916 – 2001)

Claude Shannonit kutsutakse elektroonilise infoajastu isaks. Peamised arvutiteadusega teetähised tema eluloos oleksid järgmised:

1936 kaitses MIT-is magistritöö ("A Symbolic Analysis of Relay and Switching Circuits"), milles käsitles Booli loogika rakendamist elektriskeemidele / lülitustele (nn loogikavõrkudele). Selleks ajaks oli Boole'i tööd loogika vallas unustatud ja Shannon kaevas need välja ning seostas elektriskeemidega. Shannon näitas ka, et põhimõtteliselt on võimalik ehitada loogikamasinat.
Sõja ajal tegeles C. Shannon muuhulgas krüptograafiaga - "A Mathematical Theory of Cryptography" (kust edasi tekkis ka huvi kommunikatsiooniprobleemide vastu)
1948 – informatsiooniteooria alus publikatsiooniga "A Mathematical Theory of Communication".
1949 – sama nimega raamat kahasse Warren Weaveriga.

C. Shannon esitas küsimuse: kuidas kvantitatiivselt mõõta informatsiooni? Ja sõnastas järgmised põhimõtted:

Info mõõtmise aluseks on "jah/ei" situatsioon, mis sisaldab 1 bitt (binary digit - bit) informatsiooni. Shannoni "loogikamasinas" tähendaks 1, ei vooluring on suletud ja vool on sees, ning 0, et vooluring on avatud ja vool väljas.
Keerulisema informatsiooni (kus on rohkem infoühikuid) saab ülesehitada mitut bitti kasutades.

Entroopia on informatsiooni puudujääk teate sisus. Kui korrastamata süsteemi tuleb juurde informatsiooni, väheneb entroopia ja süsteem muutub korrastatumaks.

Kommuniaktsioonisüsteemi põhielemendid:

infoallikas (source) koos edastusseadmega, mis muundab info või teate vormi sobivaks, et edastada ta kanalis (näiteks õppejõud klassis loengut pidamas ja tema hääletekitamise mehhanism, mis helilaineid väljastab)
kanal (channel) või vahend mida mööda toimub info ülekanne (transmission) (õhk klassis, mida mööda helilained on võimalised levima)
vastuvõtja (receiver) dekodeerib teate originaalilähedasele kujule (üliõpilase kõrv, mis tänu oma ülesehitusele suudab helilained kõneks muuta - loe täpsemalt anatoomia õpikust)
siht (destination), kes või mis peab teate vastuvõtma (üliõpilase mõistus, mis peab sisuga hakkama saama)
müra allikas (source of noise), mis muudab teadet ülekande jooksul etteaimamatult (teine üliõpilane, kes samal ajal midagi seletab; akna tagant mööduv mürisev auto vms)

Info mõõtmisel pole informatsiooniteoorias mingit seost teate sisuga. Mõõdetavad suurused on järgmised:

sagedus, millega allikas infot tekitab
kanali mahtuvus/suutlikus informatsiooni edastada
vastavat tüüpi teates sisalduva informatsiooni hulk

1949 a ilmus raamat „A Mathematical Theory of Communication“, mis oli koostatud koostöös Warren Weaver'iga. C. Shannoni jaoks oli informatsiooniteooria ainult tehniline probleem. Selles raamatus aga Weaver seostab informatsiooniteooria inimeste-vahelise kommunikatsiooniga, kus ta eristab kolme tasandit:

A tasand - kui adekvaatselt edastatakse kommunikatsioonisümboleid (tehniline probleem)
B tasand - kui täpselt edastatavad sümbolid kannavad ihaldatud tähendust (semantiline probleem)
C tasand - kui efektiivselt kätte saadud teade mõjutab saajat soovitud suunas (efektiivsuse või käitumuslikkuse probleem)

Positsioonilised arvusüsteemid

Kahendsüsteem (binary)

Enamus kaasaegseid arvuteid kasutavad kahendloogikat, seepärast on vajalik mõista ka kahendsüsteemi.

Kahe seisundi märkimiseks kasutatakse kahte sümbolit - 0 ja 1.

Arvusüsteemi alus on 2 ja igal positsioonil arvus on oma kaal (2 aste):

1100 1010 = 1*27 + 1*26 + 0*25 + 0*24 + 1*23 + 0*22 + 1*21 + 0*20 =
= 1*128 + 1*64 + 0*32 + 0*16 + 1*8 + 0*4 + 1*2 + 0*1=202

Teisendamine

Kümnendndsüsteemist kahendndsüsteemi saab arve teisendada kahte võtet kasutades (pean silmas nö omade jõududega teisendamist kalkulaatorit kasutamata): lahutamist ja jagamist.

Jagamisel jagatakse teisendatav arv kahega ja leitakse jääk:

202 | 0
101 | 1
 50 | 0
 25 | 1
 12 | 0
  6 | 0
  3 | 1
  1 | 1
  0
Tulemus: 11001010

Lahutamisel leitakse suurim kahe aste, mis teisendatavasse arvu mahub, pannakse see kirja ja lahutatakse arvust maha. Edasi leitakse järgmine kahe aste, millega sama moodi toimitakse jne kuni jõutakse 0-i. Nüüd on olemas mingi kahe astmed, millele kahendsüsteemi arvus hakkavad vastama 1-d. Ülejäänud positsioonidesse kirjutatakse 0-d.

Kaheksandsüsteem (octal)

Üldine pilt on analoogiline kahendsüsteemiga, kuid loomulikult on erinevused, mis just kaheksandsüsteemile omased: Arvusüsteemi alus on 8 ja igal positsioonil on oma kaal, milleks on 8 vastav aste. Kasutatavad sümbolid on

0,1,2,3,4,5,6,7

Teisendamine

Kümnendsüsteemist kaheksandsüsteemi saab teisendada taas jagamisega - seekord siis jagatakse 8-ga leitakse samal viisil ka jääk. Jääkidest moodustub kaheksandsüsteemi arv (vt kahendsüsteemi).

Kahendsüsteemist kaheksandsüsteemi on kõige mugavam tükeldada kahendsüsteemi arv paremlt poolt alates kolmikuteks ning seada igale kolmikule vastavusse üks ühekohaline kaheksandsüsteemi arv:

011 001 010
 3   1   2

Seega teisenduse tulemuseks on 312. Nagu näha võib vajaduse korral arvu algusesse nulle juurde lisada, sest see ei muuda kunagi arvu tegelikku väärtust.

Kuueteistkümnendsüsteem (hexadecimal)

Arvusüsteemi alus on 16, iga positsiooni kaal on 16 vastav aste. Kasutatavad sümbolid on:

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

Nagu kaheksandsüsteem, nii on ka kuueteistkümnendsüsteem mugavalt kahendsüsteemiga seotud (16 on teatavasti kahe 4 aste). Kuueteistkümnendsüsteemil on kahendsüsteemi ees mõned eelised:

on kompaktne (võrreldes kahendsüsteemiga)
on kergesti teisendatav kahendsüsteemi (võrreldes kümnendsüsteemiga)

Teisendamine

Kümnendsüsteemist kuueteistkümnendndsüsteemi saab teisendada taas jagamise abil. Seekord on siis vaja jagada ja jääke leida 16-ga.

Näide: Teisendame kümnendesüsteemi arvu 299 kuueteistkümnendsüsteemi:

299 // 16 = 18 jääk (ehk 299 % 16) on 11
 18 // 16 =  1 jääk (ehk  18 % 16) on 2
  1 // 16 =  0 jääk (ehk   1 % 16) on 1
Et 11_dec = B_hex, siis saame järgmise tulemuse
299_dec = 12B_hex

See arvutamine on peast juba üsna tülikas.

Kahendsüsteemist kuueteistkümnendsüsteemi Kahendarv jagatakse paremalt alates nelikuteks ja igale nelikule seatakse vastavusse 1 kuueteistkümnendsüsteemi number:

1100 1010
  C    A

Kui kahendsüsteemi 16 esimest arvu veel hästi pähe ei ole jäänud, aitab järgmine tabel:

Erinevate arvusüsteemide vastavus

 Binary Octal Decimal Hexdecimal
 0000     00     00     00
 0001     01     01     01
 0010     02     02     02
 0011     03     03     03
 0100     04     04     04
 0101     05     05     05
 0110     06     06     06
 0111     07     07     07
 1000     10     08     08
 1001     11     09     09
 1010     12     10     0A
 1011     13     11     0B
 1100     14     12     0C
 1101     15     13     0D
 1110     16     14     0E
 1111     17     15     0F
10000     20     16     10

Kahendarvudest moodustatavad struktuurid

Mõisteid ja põhimõtteid:

0-de lisamine struktuuri algusesse ei muuda tema väärtust
kõige parempoolsem bitt kannab numbrit 0 ja nime LSB (least significant bit) - madalaim bitt, vähima kaaluga bitikoht positsioonilises süsteemis
iga järgnev bitt kannab ühe võrra suuremat järjenumbrit
kõige vasakpoolsem bitt kannab nime MSB (most significant bit) - kõrgeim bitt, suurima kaaluga bitikoht positsioonilises süsteemis

Bitt (binary digit, lühend b) on vähim infoühik, millega saab näidata kahte võimalust/olekut.

Nibble - 4-bitine kombinatsioon bittidest. Saab kujutada 24 kombinatsiooni e ühe 16ndarvu.

Bait (byte, lühend B)- olulisim struktuur praeguste mikroprotsessorite juures (vähim adresseeritav üksus). Ristiisa 1956 a. dr. Werner Buchholz (töötas IBM-is).

1 bait = 2 nibble = 8 bitti

1 baidiga saab esitada 2⁸=256 erinevat kombinatsiooni.

Ühe baidiga saab esitada:

märgita täisarv: 0 .. 255
märgiga täisarv -128 .. +127
ASCII kooditabeli sümbol (kaaluta tabel) - põhitabel + laiendatud tabel

Sõna (Word) – on olnud klassikaliselt seotud arvuti arhitektuuriga: fikseeritud pikkusega bittide grupp, mida arvutis korraga töödeldakse. Bittide arv sõnas on arvuti arhitektuuris oluline näitaja. Praegustes arvutites on sõna suurus 16, 32 või 64 bitti.

16-bitise sõnaga saab kujutada 2¹⁶=65 536 erinevat väärtust:

märgita täisarvu 0 .. 65 536
märgiga täisarvu -32 768 .. +32 767

32-bitine sõna on 4 baiti ja seega 2^{32 erinevat väärtust}

Erinevad eesliited baitidele:

prefix  decimal  binary
kilo-   10001   10241 = 210 = 1024 
mega-   10002   10242 = 220 = 1 048 576 
giga-   10003   10243 = 230 = 1 073 741 824 
tera-   10004   10244 = 240 = 1 099 511 627 776 
peta-   10005   10245 = 250 = 1 125 899 906 842 624 
exa-    10006   10246 = 260 = 1 152 921 504 606 846 976 
zetta-  10007   10247 = 270 = 1 180 591 620 717 411 303 424 
yotta-  10008   10248 = 280 = 1 208 925 819 614 629 174 706 176

Erinevad andmetüübid arvuti mälus

Kuidas andmeid arvuti mälus hoitakse?
Kui suur saab olla arv, mida arvuti suudab õigesti salvestata?
Millise täpsusega arvuti arvutab?
Kuidas hoitakse arve, et arvutusi oleks lihtsam realiseerida?

Lihtandmetüüpide kujutamine sõltub nii arvutist kui ka keelest ja kompilaatorist.

Täisarv - Integer

Täisarvude esitamise võimalused on järgmised:

Märgita esitus (Unsigned integer representatsion) - mittenegatiivse täisarvu esitamine

positsioonilises kahendsüsteemis.

Märk suurusjärguga (Sign magnitude) - 1 bitt (MSB) määrab märgi (0 +, 1 -), ülejäänud bitid annavad suurusjärgu.
Täiendesitus (Complement representation) - positiivsed täisarvud on kahendkujul. Esimese täiendväärtuse (One's complement) puhul on negatiivsetel arvudel 1 MSB-s ja teised bitid saadakse positiivset arvu bitt haaval inverteerides (nullid ühtedeks ja ühed nullideks). Teine täiendväärtus (Two's complement) saadakse 1. täiendväärtusele 1

juurde liitmisel. Seda kasutatakse täisarvude salvestamiseks.

Näide: Olgu meil 4-bitine arv, millest 1 bitt on märgi jaoks. Leiame, milline on -5 101₂ (5₁₀). Lisades ette positiivse märgibiti 0 saame arvuks:

Esimene täiendväärtus (märgibitt 1, inverteeritud) on järgmine:

Teine täiendväärtus (liidame 1):

1010
   1
----
1011

Liida kokku -5 ja 5 ning vaata, kas tuleb 0? (kui bitid ei mahu ära „kukuvad nad üle serva“).

Esitus nihkega (Biased representation) - arvud kujutatakse kui positiivsed märgita arvud, arvu M tegelik väärtus leitakse M - nihe (bias). Nihe on N-bitise arvu korral 2N-1 või 2N-1-1.

Näide 3 bitiga:

 bitid:         100   101  110  111  000  001  010  011
 1. täiendv.:   -3    -2   -1    0    0    1    2    3
 2. täiendv.:   -4    -3   -2   -1    0    1    2    3
 negatiivsed arvud nihkuvad ühe koha võrra allapoole, et vältida kahte 0-i.

Ujukomaarv – Float

Ujukomaarve (floating-point representation) saab kujutada teatud täpsusega ε (epsilon) (arv-epsilon<=arv<=arv+epsilon). Kokkulepitud komakohtade arvu puhul on tegemist arvu püsikomaesitusega (fixed-point representation).

Arvutis kasutatakse arvu ujukomaesitust. Arv koosneb kolmest osast:

märk (0 – positiivne, 1 – negatiivne)
mantissi absoluutväärtus (annab täpsuse, kus koma paikneb vasakult 1. ja 2. positsiooni vahel)
astme suurus ehk eksponent (nihkega esitus, et kujutada nii positiivset kui ka negatiivset astet)

IEEE standardi 754 järgi on kahte tüüpi ujukomaarve:

lihttäpsusega ujukomaarv (single precision)':

Arvu suurus on 32 bitti (1 bitt märgile, 8 bitti eksponendile nihe 127, 23 bitti mantissile). Sellest tulenevalt on arvu piirid: 1.5E-45 .. 3.4E38 ja täpsus: 7-8 kohta. Koma on tüvenumbites vasakpoolse arvu järel, eksponendi esitamiseks kasutatakse täisarvu nihkega esitust.

topelttäpsusega ujukomaarv (double precision)

Arvu suurus on 64 bitti (1 bitt märgile, 11 bitti eksponendile nihe 1023, 52 bitti mantissile). Arvu piirid on 5.0E-324 .. 1.7E308 ja täpsus: 15-16 kohta. Koma on tüvenumbites vasakpoolse arvu järel, eksponendi esitamiseks kasutatakse täisarvu nihkega esitust.

Tõeväärtus – Boolean

Tõeväärtus esindab kahte väärtust True ja False, millele vastavad 0 ja 1. Ehkki see andmetüüp mahuks ära ka ühele bitile, muutuks adresseerimine tülikamaks ja seetõttu kasutatakse 1 baiti.

Tekstilise info kodeerimine ja kooditabelid

Kooditabelite ülesanne on luua seos arvutikoodide (bitijadade) ja erinevate tähemärkide jt märkide vahel, mida kasutatakse teksti kirjutamisel. Kodeerimine lubab digitaalsetel seadmetel tekstandmeid salvestada, töödelda ja vahetada.

ASCII koodiatbel

ASCII (American Standard Code for Information Interchange) on vanimaid kasutusel olevaid kooditabeleid. Tabel tugineb inglise alfabeedile. Esimene standardi versioon avaldati 1963. Klassikaline ASCII tabel sisaldas 7-bitist koodi, iga sümbol kodeeriti mustriga 7-st bitist. Kaheksas bitt oli andmete ülekandmise kontrolliks vajalik paarsusbitt (parity bit). Seega ASCII tabel kirjeldab/kodeerib 128 märki, millest 32 esimest ei ole trükitavad, vaid olid kasutusel seoses telegraafi ülekande vajadustega.

Laiendatud ASCII

Rahvuslike tähtede lisamiseks on võetud kasutusele 8. bitt ja räägitakse laiendatud ASCII tabelist (extended ASCII). Kui tabeli esimesed 128 sümbolit on alati ühesugused, siis tagumised 128 varieeruvad, sest vajadused erinevate tähtede järele on kultuuriliselt erinevad. Neid erinevaid variante kutsutakse koodilehekülgedeks (code pages), nimi on IBM-lt, kes IBM PC jaoks rahvuslik-kultuurilised laiendused algatas.

Teistsuguse standardi lõi ISO: ISO 8859, milles oli kirjeldatud teistsugune 8-bitine kooditabel. Esimesed 128 märki kattuvad ASCII tabeli omadega. Populaarseim - ISO 8859-1, ka ISO Latin-1 (tähed Lääne-Euroopa keelte jaoks). ISO 8859-2 sobib Ida-Euroopa keelte jaoks.

MS tegi oma standardi ja andis talle nimeks code page 1252. See on suures osas vastavuses ISO 8859-1-ga.

Unicode

Unicode on standard, mis püüab likvideerida erinevatest kodeeringutest tulenevaid konflikte ja kodeerida kõikvõimalikud sümbolid, milles teksti esitatakse. Tabelisse on reserveeritud 2²⁰ + 2¹⁶ = 1 114 112 positsiooni. Nendest esimesed 256 on vastavuses ISO 8859-1-ga.

Unicode peaks võimaldama ühekorraga kasutada rohkem kui paari keele sümboleid. Kogu kooditabelit ei ole korraga vaja kasutada ja seetõttu võetakse sellest välja osasid. On kaks vastavuste tekitamise meetodit (mapping): Unicode Transformation Format (UTF) kodeering ja Universal Character Set (UCS) kodeering. Konkreetsesse kodeeringusse võetakse fikseeritud suurusega ja fikseeritud piirkonnast kodeeritud sümbolid. Numbrid kodeeringute nimedes tähendavad vastavalt kasutatavate bittide (UTF) või baitide (UCS) arvu. Arvatavasti on UTF-8 ja UTF-16 ühed tuntumad skeemid. Näiteks UTF-8 on 8-bitine, kuid muutuva pikkusega kodeering maksimaalselt vastavuses ASCII-ga. UTF-8 kasutab 1 kuni 4 baiti sümboli kodeerimiseks.

Pythoni andmetüübid

Täisarv (integer)

Pythoni täisarvud on traditsiooniliselt negatiivsed ja positiivsed. Eristatakse kahte tüüpi täisarve: long integers ja booleans.

Long integers on väidetavalt piiranguteta. Loomulikuks piiranguks vaid arvuti mälumaht. Andmetüüpi hoitakse teise täiendväärtuse. Booleans kasutatakse loogikaväärtuste True ja False esitamiseks. Ta on väike täisarv ja väärtused on 0 või 1. Kui neid väärtuseid on vaja näidata, siis teisendatakse 0 ja 1 stringideks.

Ujukomaarv (Floating point number)

Ujukomaarve kujutatakse masina tasemel IEEE standardi topelttäpsusega ujukomaarvudena. Dokumentatsiooni kohaselt määravad arvu täpsuse ja piirid, samuti käitumise ületäitumiste korral masina arhitektuur.

Kompleksarv (Complex numbers)

Masina tasemel esitatakse kompleksarv kahe topelttäpsusega ujukoamarvu paarina. Kõik, mis kehtib ujukomaarvu kohta, kehtib ka siin. Reaal- ja imaginaarosa saab lugeda read-only atribuutide z.real ja z.imag kaudu.

Struktuursed andmetüübid

Struktuurset tüüpi muutuja saab sisaldada mitut väärtust korraga. Klassikalisteks struktuurseteks andmetüüpideks on massiiv (array) ja kirje (record). Massiiv võimaldab salvestada ühte tüüpi andmeid. Andmetele ligipääs tagatakse indeksite abil. Massiivid võivad olla ühemõõtmelised, kahemõõtmelised jne ...mõõtmelised. Sõltub keelest, kuidas massiive kasutada saab arvutusteks, sisestamiseks, väljastamiseks – st kas on olemas käsud kogu massiiviga töötamiseks või tuleb elemente ükshaaval töödelda.

Massiivid võivad olla staatilised või dünaamilised.

Staatiline massiiv: elementide maksimaalne arv määratakse programmi töö alguses, hiljem seda suurendada ei saa.
Dünaamiline massiiv: elementide arv massiivis on muudetav (tavaliselt lisatakse elemente juurde)

Kasutatavast keelest sõltub ka indekseerimise tava. C-tüüpi keeled määravad alati massiivi indeksid 0-st. Pascal lubab kirjeldada massiivile suvalise indeksite vahemiku, tavaliseks on algus 1-st. Tüüpiliselt kasutatakse indeksite eristamiseks massiivi nime taga kandilisi sulge []

Näide:

On massiiv nimed, kuhu lubatud salvestada stringe (massiiv on deklareeritud stringidest koosnema).

nimed[2]

Tähendab massiivi 2. või 3. elementi ehk 2. nime või 3. nime. Sõltub indekseerimise kokkulepetest antud keeles (kas esimene indeks on 1 või 0)

nimed[2] = "Juuli"

Indeksiga 2 tähistatud lahtrisse kirjutatakse Juuli.

Massiivis on N elementi, iga elemendiga on seotud indeks:

Maali Juuli Tuuli Meeli ... ... Aali Raali
  1     2     3     4   ... ...  N-1   N

Alternatiivne indekseerimine - alustatakse indeksiga 0:

Maali Juuli Tuuli Meeli ... ... Aali Raali
  0     1     2     3   ... ...  N-2  N-1

Massiivi on sobiv kasutada loogilises mõttes ühte tüüpi/sorti andmete hoidmiseks, kus töötlemisel on vaja kõigi andmetega samu toiminguid teha (nimed, pikkused, hinded jms). Kirje võimaldab salvestada ja töödelda erinevat tüüpi andmeid. Kirjesse on tavaks koondada info sama objekti kohta. Näiteks üliõpilase eesnimi, perekonnanimi, õpinguraamatu number, sünniaasta ja eriala. Kirjes olevaid positsioone andmete salvestamiseks nimetatakse kirje väljadeks (field). Igale väljale antakse nimi, mille kaudu väljas olevat infot käidelda saab. Igal kirje väljal on tüüp, mis kuulub keele standardtüüpide (liht- või struktuursete) hulka. St kirje väljaks võib olla teine kirje või massiiv, täis- ja ujukomaarvudest rääkimata.

Süntaks ja mängureeglid kirje väljade käitlemiseks on keeleti erinevad. Näiteks:

opilane.eesnimi
opilane->eesnimi
(kus opilane on kirje nimi ja eesnimi on välja nimi)

Pythoni jadadest sobib lugeda vastavast materjalist.

< 5. nädala teemad