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 = \emptyset\)

  • \(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 = \emptyset\)

  • \(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 \rightarrow 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 \rightarrow \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 = \max_{k \leq x} k, \quad x \in \mathbb{R}, k \in \mathbb{Z}.\]

\(k = \lfloor x \rfloor\) esetén mindig teljesül, hogy \(k \leq 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 = \min_{k \geq x} k, \quad x \in \mathbb{R}, k \in \mathbb{Z}.\]

\(k = \lceil x \rceil\) esetén mindig teljesül, hogy \(k - 1 < x \leq k\).

Tulajdonságok

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

  • \(a = \lfloor a \rfloor = \lceil a \rceil\).

  • \(\lfloor x \rfloor \leq \lceil x \rceil\).

  • Ha \(x \leq y\), akkor \(\lfloor x \rfloor \leq \lfloor y \rfloor\) és \(\lceil x \rceil \leq \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 \geq \lfloor x \rfloor + \lfloor y \rfloor\), \(\lceil x + y \rceil \leq \lceil x \rceil + \lceil y \rceil\).

  • \(\lfloor x - y \rfloor \leq \lfloor x \rfloor - \lfloor y \rfloor\), \(\lceil x - y \rceil \geq \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) = \left\lfloor x + \dfrac{1}{2} \right\rfloor, \quad 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, \quad x \in \mathbb{R}.\]

Mindig fennáll, hogy \(0 \leq \{x\} < 1\).

Egész hányados képzése

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

\[a \text{ div } b = \left\lfloor \dfrac{a}{b} \right\rfloor.\]

Egész maradék képzése

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

\[\begin{split}a \text{ mod } b = \begin{cases} a - \lfloor a / b \rfloor \cdot b, & \text{ha } b \neq 0, \\ a, & \text{ha } b = 0. \end{cases}\end{split}\]

Számrendszerek

Jelölje \(b\) természetes szám (\(b \geq 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}, \ldots, c_1, c_0,\]

ahol \(0 \leq c_k < b, k = 0, 1, \ldots, 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 \neq 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, \ldots, 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\)

\(\vdots\)

\(\vdots\)

\(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} \ldots c_{k} \ldots\]

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

\[x = \dfrac{c_1}{b^1} + \dfrac{c_2}{b^2} + \dfrac{c_3}{b^3} + \cdots + \dfrac{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 \}\)

\(\vdots\)

\(\vdots\)

\(c_k = \lfloor x_{k-1} \cdot b \rfloor\)

\(x_k = \{ x_{k-1} \cdot b \}\)

\(\vdots\)

\(\vdots\)

Horner-séma

Egészek átváltása

\[x = (\ldots ((c_n) \cdot b + c_{n-1}) \cdot b + \cdots + c_1) + c_0\]

Törtek átváltása

\[x = (\ldots (((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}, \ldots, c_1, c_0\]

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

\[n + 1 = \left\lfloor \log_b x \right\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 \left( c_n + \dfrac{c_{n-1}}{b} + \cdots + \dfrac{c_1}{b^{n-1}} + \dfrac{c_0}{b^n} \right)\]

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

\[x = b^n \cdot y.\]

Teljesül, hogy \(1 \leq c_n \leq y < b\), amiből logaritmust véve azt kapjuk, hogy

\[0 \leq \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 = \left\lfloor \log_b x \right\rfloor\]

alakot kapjuk (mivel \(n\) egész és \(\left\lfloor \log_b y \right\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) = \left\lfloor x + \dfrac{1}{2} \right\rfloor = \left\lceil x - \dfrac{1}{2} \right\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)}, 8FB2_{(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{split}&1011101_{(2)} + 11001_{(2)} \\ &2133_{(4)} + 321_{(4)} \\ &43705_{(8)} + 1162_{(8)} \\ &30112_{(5)} + 4040_{(5)} \\\end{split}\]

  • 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?