1. Információ, adat, számrendszerek

Információ

• Jellemző mértékegysége a bit.

• A számítógépeink többségében digitálisak és bit alapúak.

• Az adat az információ megjelenési formája.

Kapcsolódó tudományterületek

• Információelmélet

• Kommunikációelmélet

• Kódelmélet

Bit

• A tárolható adatmennyiség legkisebb egysége.

• Értéke lehet 0 vagy 1.

Byte

https://en.wikipedia.org/wiki/Byte

• A 8 bitből alkotott csoportokat byte-nak nevezzük.

• A 8-as darabszám praktikus és történeti okok miatt alakult ki. (Ezért nevezik oktett-nek is.)

• Számít a bitek sorrendje.

• A bit-ek helyét az egész számokhoz hasonlóan a helyiérték kitevőjének indexével adjuk meg.

[  .  .  .  .  .  .  .  . ]
   7  6  5  4  3  2  1  0

• A 2 byte-os egységet szó-nak szokták nevezni.

[  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . ]
  15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0

• A 4 byte-os egység a dupla szó.

• A fél byte-nak a(z egyik) neve nibble. Jellemzően az alsó- és felső fél byte-ot szokták tekinteni.

További mértékegységek

• KB: Kilobyte

• MB: Megabyte

• GB: Gigabyte

• TB: Terabyte

Számítások szemléltetésképpen

• Írjuk fel a byte-ok darabszámát 2 kitevőjeként 1 KB, 1 MB, 1 GB és 1 TB esetén!

• Tegyük fel, hogy négyzet alakú milliméter lapon szeretnénk adatokat tárolni. 1 bit $1\times 1$ milliméteres négyzetnek feleltethető meg. Mekkora lesz a lap mérete 1 KB, 1 MB, 1 GB és 1 TB esetén?

Adattípus

A számítógép egy automata, amely az adatok tárolásával, feldolgolgozásával, továbbításával foglalkozik.

Figyelem

Az információt nagyon nehéz elkülöníteni a konkrét megjelenési formájától!

Az adattípusokhoz hozzá értjük

• az adat ábrázolását (leírási módját), és

• a rajta elvégezhető műveleteket.

Ez a megközelítés fellelhető

• a matematikában például az algebrák, gyűrűk vizsgálatánál,

• az objektum-orientált programozásban,

• az adat- és a műveleti rész elkülönítésénél úgy általában.

Absztrakt adattípus

Az absztrakt adattípus adatok és a rajtuk végezhető műveletek halmazát írja le. Jelölhetjük $T$-vel, amely így tehát egy

$$T=(A,M)$$

pár lesz, amelyben az $A$ az adatok halmazát, az $M$ a műveletek halmazát jelöli.

Az absztrakció itt azt jelenti, hogy

• nem foglalkozunk a későbbi, gépi megvalósítással, realizációval,

• a halmazok lehetnek akár végtelen elemszámúak is.

Példa

A természetes számhalmaz segítségével definiálhatunk egy típust az alábbi formában:

$$T=(\mathbb{N},\{+,\cdot \}).$$

Figyelem

A műveletek eredménye mindig halmazon belül kell, hogy maradjon! (Nem tud máshol lenni.)

Adatstruktúra

Az absztrakt adattípus konkrét megjelenési formája, realizációja.

Implementáció

A számítógépen történő realizáció.

• Az implementáció magyarul megvalósítást jelent.

• Az absztrakt adatból az adatstruktúra definiálása, majd az implementáció megadása is veszteségekkel járhat (például a véges ábrázolási tartományok miatt).

• Az implementáció az adatstruktúra egy speciális esete.

Déscartes szorzat

Két halmaz Déscartes szorzatán egy olyan, rendezett elempárokból álló halmazt értünk, amely pároknak az első eleme az első halmazból, második eleme a második halmazból származik.

$$C=A\times B=\{(a,b)|a\in A,b\in B\}$$

Példa

Legyen $A=\{x,y\}$ és $B=\{3,4,5\}$. Ezek Déscartes szorzata:

$$A\times B=\{(x,3),(x,4),(x,5),(y,3),(y,4),(y,5)\}.$$

Halmaz hatványa

Halmazokon is értelmezhetjük a hatványozás műveletét.

• $A^0=\mathrm{\varnothing }$

• $A^1=A$

• $A^2=A\times A$

• $A^n=A^{n-1}\times A$

Példa

Tekintsük a $D=\{7,8\}$ halmazt!

• $D^0=\mathrm{\varnothing }$

• $D^1=\{7,8\}$

• $D^2=D\times D=\{(7,7),(7,8),(8,7),(8,8)\}$

Tulajdonságok

• Nem Kommutatív

• Asszociatív

Többváltozós műveletek

$n$-változós ($n$-áris) műveletnek nevezzük az $A$ halmazon az $f:A^n\to A$ leképzést (függvényt).

• $n=1$ esetén unáris művelet.

• $n=2$ esetén bináris művelet.

Hatványhalmaz

Egy halmaz összes lehetséges részhalmazának a halmaza.

Jelölése: $2^A$, $\mathcal{P}(A)$

Példa

Írjuk fel a $C=\{2,3,5\}$ halmaz hatványhalmazát!

Számosság

$$|2^A|=2^{|A|}$$

Orosz-paraszt módszer

• Két egész szám szorzására alkalmas.

• A módszert az ókori egyiptomiak fejlesztették ki (vagy legalábbis már használták).

Lépései

• Állítsunk be egy szorzat változót 0-ra!

• Vizsgáljuk meg, hogy a szorzónk páratlan-e!

• Hogy ha páratlan, akkor adjuk hozzá a szorzathoz!

• A szorzandót szorozzuk meg kettővel!

• A szorzót osszuk el egészesen kettővel!

• Ismételjük az eljárást a második lépéstől, amíg a szorzónk 0 nem lesz!

Példa

Számítsuk ki a $25\cdot 19$ szorzatot!

szorzandó	szorzó	szorzó páratlan-e?	szorzat
25	19	igen	0+25=25
50	9	igen	25+50=75
100	4	nem	75
200	2	nem	75
400	1	igen	75+400=475
	0

Elemi függvények, műveletek

A függvények és műveletek között a fő különbséget gyakorlatilag a jelölésmód jelenti. Definiálhatjuk például az összeadást a szokásos (infix) műveleti jellel, de megadhatnánk akár függvény formájában is:

$$+:{\mathbb{R}}^2\to \mathbb{R}.$$

Alsóegészrész függvény

Az alsóegészrész függvény minden valós számhoz a nála nem nagyobb egészek közül a legnagyobb egészet rendeli.

$$\lfloor x\rfloor =\underset{k\le x}{max}k,x\in \mathbb{R},k\in \mathbb{Z}.$$

$k=\lfloor x\rfloor$ esetén mindig teljesül, hogy $k\le x<k+1$.

Felsőegészrész függvény

A felsőegészrész függvény minden valós számhoz a nála nem kisebb egészek közül a legkisebb egészet rendeli.

$$\lceil x\rceil =\underset{k\ge x}{min}k,x\in \mathbb{R},k\in \mathbb{Z}.$$

$k=\lceil x\rceil$ esetén mindig teljesül, hogy $k-1<x\le k$.

Tulajdonságok

Legyen $a\in \mathbb{Z}$ és $x,y\in \mathbb{R}$.

• $a=\lfloor a\rfloor =\lceil a\rceil$.

• $\lfloor x\rfloor \le \lceil x\rceil$.

• Ha $x\le y$, akkor $\lfloor x\rfloor \le \lfloor y\rfloor$ és $\lceil x\rceil \le \lceil y\rceil$.

• $\lfloor x\pm a\rfloor =\lfloor x\rfloor \pm a$, $\lceil x\pm a\rceil =\lceil x\rceil \pm a$.

• $-\lfloor x\rfloor =\lceil -x\rceil$, $-\lceil x\rceil =\lfloor -x\rfloor$.

• $\lfloor x+y\rfloor \ge \lfloor x\rfloor +\lfloor y\rfloor$, $\lceil x+y\rceil \le \lceil x\rceil +\lceil y\rceil$.

• $\lfloor x-y\rfloor \le \lfloor x\rfloor -\lfloor y\rfloor$, $\lceil x-y\rceil \ge \lceil x\rceil -\lceil y\rceil$.

https://hu.wikipedia.org/wiki/Egészrész

Kerekítő függvény

A kerekítő függvény a valós számokhoz a hozzájuk legközelebbi egész számokat rendeli. Amennyiben ez nem egyértelmű, a nagyobbat választja.

$$\text{Round}(x)=\lfloor x+{\displaystyle \frac{1}{2}}\rfloor ,x\in \mathbb{R}.$$

Törtrész függvény

A törtrész függény azt mutatja, hogy mennyivel nagyobb egy valós érték az alsóegész részénél.

$$\{x\}=x-\lfloor x\rfloor ,x\in \mathbb{R}.$$

Mindig fennáll, hogy $0\le \{x\}<1$.

Egész hányados képzése

Legyenek $a,b\in \mathbb{Z}$ egészek, $b\ne 0$. Egész hányados alatt az $a/b$ hányados alsóegész részét értjük.

$$a\text{ div }b=\lfloor {\displaystyle \frac{a}{b}}\rfloor .$$

Egész maradék képzése

Legyenek $a,b\in \mathbb{Z}$ egészek.

$$\begin{array}{r}a\text{ mod }b=\{\begin{array}{ll}a-\lfloor a/b\rfloor \cdot b,& \text{ha }b\ne 0,\\ a,& \text{ha }b=0.\end{array}\end{array}$$

Számrendszerek

Jelölje $b$ természetes szám ($b\ge 2$) a számrendszeri alapszámot. Egy $x$ pozitív egész szám helyiértékes számábrázolást feltételezve az alábbi alakban írható föl:

$$c_n,c_{n-1},\dots ,c_1,c_0,$$

ahol $0\le c_k<b,k=0,1,\dots ,n$. Ekkor az $x$ érték a következőképpen számítható ki:

$$x=c_n\cdot b^n+c_{n-1}\cdot b^{n-1}+\cdots +c_1\cdot b^1+c_0\cdot b^0.$$

Feltételezhetjük, hogy $c_n\ne 0$, és $c_k=0$, hogy ha $k>n$.

A számrendszer alapszámát a szám jobb alsó sarkában alsó félkörrel vagy bekarikázva jelöljük, például: ${1234}_{(5)}$.

10 feletti számrendszerek

Amennyiben egy számjegy értéke nagyobb lenne, mint 9, akkor a latin ábécé betűit használjuk számjegyként.

$$A=10,B=11,C=12,D=13,E=14,F=15,G=16,\dots ,Z=35$$

https://hu.wikipedia.org/wiki/Sz%C3%A1mrendszer

Kitüntetett jelentőségű számrendszerek

• 2-es: bináris számrendszer

• 7-es: az ősmagyarok ezt használták

• 8-as: UNIX-szerű rendszerekben jogosultságkezelés kapcsán használatos

• 10-es: tipikusan ezt használjuk

• 16-os: hexadecimális számrendszer, byte-ok értékének egy jellemző leírási módja

https://tudasbazis.sulinet.hu/hu/matematika/matematika/matematika-5-osztaly/szamirasok/a-szamiras-fejlodese

Egész számok számrendszeri átváltása

$x$	$b$
$x_1=x\text{ div }b$	$c_0=x\text{ mod }b$
$x_2=x_1\text{ div }b$	$c_1=x_1\text{ mod }b$
$x_3=x_2\text{ div }b$	$c_2=x_2\text{ mod }b$
$⋮$	$⋮$
$x_n=x_{n-1}\text{ div }b$	$c_{n-1}=x_{n-1}\text{ mod }b$
$0$	$c_n=x_n\text{ mod }b$

Példa

Írjuk fel a 3456 értéket 8-as számrendszerben!

Törtek

Egy szám törtrésze helyiértékes számrendszerben, általános alakban:

$$0,c_1{c}_2{c}_3\dots c_k\dots$$

A szám értékének meghatározása:

$$x={\displaystyle \frac{c_1}{b^1}}+{\displaystyle \frac{c_2}{b^2}}+{\displaystyle \frac{c_3}{b^3}}+\cdots +{\displaystyle \frac{c_k}{b^k}}+\cdots$$

Számrendszeri átváltás:

$b$	$x$
$c_1=\lfloor x\cdot b\rfloor$	$x_1=\{x\cdot b\}$
$c_2=\lfloor x_1\cdot b\rfloor$	$x_2=\{x_1\cdot b\}$
$c_3=\lfloor x_2\cdot b\rfloor$	$x_3=\{x_2\cdot b\}$
$⋮$	$⋮$
$c_k=\lfloor x_{k-1}\cdot b\rfloor$	$x_k=\{x_{k-1}\cdot b\}$
$⋮$	$⋮$

Horner-séma

Egészek átváltása

$$x=(\dots ((c_n)\cdot b+c_{n-1})\cdot b+\cdots +c_1)+c_0$$

Törtek átváltása

$$x=(\dots (((c_n)/b+c_{n-1})/b+c_{n-2})/b+\cdots c_1)/b$$

Számjegyek számáról szóló tétel

Tétel

Jelöljön $x$ egy nemnegatív egész számot, melynek a számjegyeit általánosan a

$$c_n,c_{n-1},\dots ,c_1,c_0$$

alakban tudunk felírni. Az $x$ szám számjegyeinek a száma $b$ alapú számrendszerben

$$n+1=\lfloor {\log }_{b}x\rfloor +1.$$

Bizonyítás

A helyiértékes alakból írjuk fel $x$ értékét:

$$x=c_n\cdot b^n+c_{n-1}\cdot b^{n-1}+\cdots +c_1\cdot b^1+c_0\cdot b^0.$$

Emeljük ki $b^n$-t:

$$x=b^n\cdot (c_n+{\displaystyle \frac{c_{n-1}}{b}}+\cdots +{\displaystyle \frac{c_1}{b^{n-1}}}+{\displaystyle \frac{c_0}{b^n}})$$

Jelöljük a zárójelben lévő részt $y$-al:

$$x=b^n\cdot y.$$

Teljesül, hogy $1\le c_n\le y<b$, amiből logaritmust véve azt kapjuk, hogy

$$0\le {\log }_{b}y<1.$$

Az $x=b^n\cdot y$ kifejezésnek vegyük a logaritmusát:

$${\log }_{b}x=n\cdot {\log }_{b}b+{\log }_{b}y.$$

Az előbbiből azt kapjuk, hogy

$$n+{\log }_{b}y={\log }_{b}x.$$

Mindkét oldal alsóegészrészét véve:

$$n=\lfloor {\log }_{b}x\rfloor$$

alakot kapjuk (mivel $n$ egész és $\lfloor {\log }_{b}y\rfloor =0$). Mindkét oldalhoz 1-et hozzáadva megkapjuk a bizonyítandó összefüggést.

Kérdések

Halmazok

• Tetszőleges $A$ és $B$ halmazok esetén mennyi eleme lesz az $A\times B$ Déscartes szorzatnak?

• Asszociatív művelet-e a Déscartes szorzat? Lássuk is be!

• Kommutatív művelet-e a Déscartes szorzat? Lássuk is be!

• Mennyi eleme lesz az $E^3$ halmaznak, ha $E=\{1,2,3,4\}$?

Műveletek

• Milyen példák lehetnek unáris és bináris műveletekre!

• Előfordulhat-e, hogy egy számnak megegyezik az alsó- és felsőegész része? Ha igen, akkor adjon rá példát, ha nem akkor lássa be, hogy miért nem!

• Hogyan néz ki azon számok halmaza, melyek kerekített értéke megegyezik a felsőegész részükkel?

• Hogy ha az $a$ és $b$ érték szorzatát szeretnénk kiszámolni Orosz-paraszt módszerrel, akkor mennyi sora lesz a táblázatnak? (Fejlécet és a táblázat végén lévő 0-ás sort nem számítva.)

• Hogyan ábrázolható az alsóegészrész függvény?

• Hogyan ábrázolható a felsőegészrész függvény?

• Hogyan ábrázolható a kerekítő függvény?

• Hogyan ábrázolható a törtrész függvény?

Feladatok

Adatmennyiség

• Mennyi bitminta képezhető 10 biten?

• Mennyi olyan bitminta alakítható ki egy byte-on, amelyik a 01 bitekkel kezdődik?

• Mennyi olyan bitminta van egy byte-on, amely azonos számú 0-át és 1-est tartalmaz? (Írjuk fel az összefüggést általánosan $n$-re!)

• Mennyi bitje van egy duplaszónak?

Adattípusok

• Írjuk fel a valós számokhoz tartozó absztrakt adattípust a 4 alapművelettel!

Halmazok

Tekintsük az $A=\{p,q,r\}$ és $B=\{5,8\}$ halmazokat!

• Írjuk fel az $A\times A,A\times B,B\times A,B\times B$ Déscartes szorzatokat!

• Írjuk fel a $2^A$, $2^B$ halmazokat!

• A halmazok kiszámítása előtt határozzuk meg azok elemszámát!

Határozzuk meg az $|A^7\times B^8|$ értéket, hogy ha $A=\{5,9,x\},B=\{\gamma ,-4\}$.

Műveletek

• Számítsuk ki a 90 és a 179 szorzatát Orosz-paraszt módszerrel! Nézzük meg mindkét sorrendben elvégezve a műveletet!

• Adjunk példákat alsó- és felsőegészrész, kerekítés és törtrész számítására pozitív és negatív racionális számok esetén!

• Vizsgáljuk meg a $27$ és $5$ értékekkel, a lehetséges pozitív és negatív előjelekkel a div és a mod műveletek eredményeit!

• Vizsgáljuk meg, hogy teljesül-e az alábbi összefüggés!

$$\text{Round}(x)=\lfloor x+{\displaystyle \frac{1}{2}}\rfloor =\lceil x-{\displaystyle \frac{1}{2}}\rceil$$

• Adjon példát olyan $a,b\in \mathbb{Z}$ értékekre, amelyekre teljesül, hogy $a\text{ div }b=a\text{ mod }b$.

Számrendszerek

• Milyen értéket ábrázolnak a

$${7532}_{(10)},{10111010}_{(2)},{25136}_{(7)},8FB{2}_{(16)},{121020}_{(3)},{444}_{(5)},{5566}_{(8)}$$

értékek?

• Írjuk fel a 2021 értéket 2, 3, 4, 7, 8, 10, 11, 16-os számrendszerben! Vizsgáljuk meg a 2, 4, 8, 16 számrendszerek közötti összefüggéseket a számalakok alapján!

• Ellenőrízzük a számításokat Horner sémával!

• Végezzük el a következő műveleteket számrendszeri átváltás nélkül:

$$\begin{array}{rl}& {1011101}_{(2)}+{11001}_{(2)}\\ & {2133}_{(4)}+{321}_{(4)}\\ & {43705}_{(8)}+{1162}_{(8)}\\ & {30112}_{(5)}+{4040}_{(5)}\end{array}$$

• Adjunk össze a 4190 és a 618 számokat 8-as, 9-es és 15-ös számrendszerben!

• Mennyi számjegyből fog állni a 62982 szám 2, 3, 6, 10, 15, 16-os számrendszerben?