Základy číslicovej techniky a algoritmizácia – maturitná otázka z informatiky

Základy číslicovej techniky a algoritmizácia – maturitná otázka z informatiky

Maturitná otázka č. 1

A) Základy číslicovej techniky (hardvérová časť)

Boolova algebra

• Zahŕňa logické funkcie, ktoré sa využívajú v informatike a elektrotechnike.
• Na základe týchto funkcií sa vytvárajú logické hradlá, z ktorých sú zostavené tranzistory, integrované obvody a procesory.
• Boolova algebra využíva binárnu sústavu.
• Premenné v Boolovej algebre môžu nadobúdať hodnoty 0 alebo 1.
• Vstupné hodnoty premenných a výslednú hodnotu funkcie zapisujeme do pravdivostnej tabuľky.
• Vstupné hodnoty označujeme ako nezávislé premenné, výstupnú hodnotu označujeme ako závislú premennú.

Negácia

Negácia je najjednoduchšou boolovskou operáciou. Pri negácii nadobúda premenná opačnú hodnotu.

Pravdivostná tabuľka negácie:

Negácia sa označuje rovnou vodorovnou čiarou nad premennou.

Zápis negácie: x

Logický súčet (OR)

Logický súčet je operácia disjunkcie (zjednotenia).

Pre operáciu logického súčtu je charakteristická spojka alebo.

Možnosti zápisu logického súčtu:

• A OR B
• A + B
• A alebo B
• A ∨ B

Schematické znázornenie: spínače A a B zapojené paralelne.

Pravdivostná tabuľka logického súčtu:

Logický súčin (AND)

Logický súčin je operácia konjunkcie alebo prieniku. Označuje sa aj znakom ∧.

Pre logický súčin sú typické spojky a, aj, i.

Možnosti zápisu logického súčinu:

• A ∧ B
• A & B
• A · B
• A AND B

Výsledná hodnota funkcie je 1 len vtedy, ak všetky nezávislé premenné majú hodnotu 1.

Schematické znázornenie: spínače A a B zapojené sériovo.

Pravdivostná tabuľka logického súčinu:

Ďalšie boolovské funkcie

NAND (negovaný súčin)

Funkcia NAND má hodnotu 1, ak aspoň jedna nezávislá premenná má hodnotu 0.

NOR (negovaný súčet)

Funkcia NOR má hodnotu 1, ak všetky vstupy majú hodnotu 0.

XOR (exkluzívny súčet)

Funkcia XOR má hodnotu 1, ak vstupy majú rozdielne hodnoty.

Karnaughove mapy

Karnaughove mapy slúžia na zjednodušený zápis funkcie.

Aby bola mapa Karnaughovou mapou, musí spĺňať tieto podmienky:

1. Karnaughova mapa má toľko políčok, koľko má pravdivostná tabuľka riadkov (2ⁿ), pričom n je počet vstupov.
2. V Karnaughovej mape musí existovať jedna bunka, v ktorej majú všetky nezávislé vstupy hodnotu 0.
3. V Karnaughovej mape musí existovať jedna bunka, v ktorej majú všetky nezávislé vstupy hodnotu 1.
4. Pre každý nezávislý vstup musí platiť, že pre polovicu buniek Karnaughovej mapy má vstup hodnotu 0 a pre polovicu buniek má hodnotu 1.

Dva spôsoby zápisu Karnaughovej mapy:

1. Aritmetický zápis.
2. Zápis pomocou svoriek.

Príklad Karnaughovej mapy:

Do Karnaughovej mapy zapisujeme hodnotu funkcie, nie hodnotu vstupov.

Preklápacie obvody

Preklápací obvod je obvod, ktorý sa dokáže dostať zo stavu 0 do stavu 1 a naopak.

Rozlišujeme tri druhy preklápacích obvodov:

1. Monostabilný.
2. Bistabilný.
3. Astabilný.

1. Monostabilný preklápací obvod

Má stabilný iba jeden stav. Ak mu dáme povel (impulz), preklopí sa do opačného stavu a po určitom čase sa vráti do svojho stabilného stavu.

Príklad: Svetlá vo vchodoch bytoviek sú v stabilnej 0. Po stlačení vypínača sa dostanú do stavu 1 a po určitom čase sa vrátia do stabilnej 0 (zhasnú). Ďalším príkladom je infrasnímač.

2. Bistabilný preklápací obvod

Má stabilné oba stavy. Ak je v nule a dostane povel, preklopí sa do jednotky a na ďalší povel sa preklopí do nuly.

Príklad: Mikrospínač na televízore.

3. Astabilný preklápací obvod

Tento klopný obvod nemá stabilný ani jeden stav a preklápa sa z 0 do 1 alebo z 1 do 0.

Príklad: Blikač na bicykli.

V niektorých aplikáciách je potrebné zariadiť, aby klopný obvod po určitý čas nereagoval na vstup. Na tento účel boli navrhnuté tzv. synchrónne klopné obvody vybavené špeciálnym vstupom, označovaným ako hodinový vstup.

Na tento vstup je privedený tzv. hodinový signál, ktorý určuje, či bude klopný obvod na ostatné vstupy reagovať, alebo ich ignorovať.

• Synchrónne klopné obvody – s hodinovým vstupom.
• Asynchrónne klopné obvody – bez hodinového vstupu.

B) Algoritmizácia (softvérová časť)

Algoritmus

Algoritmus je postupnosť príkazov (postup), kde zo zadaných vstupných údajov po konečnom počte krokov a v konečnom čase dostaneme správy (očakávaný výsledok).

Vlastnosti algoritmu

1. Elementárnosť – algoritmus musí byť zrozumiteľný pre realizátora.
2. Determinovanosť – v každom kroku vykonávania algoritmu musí byť jasné, aký krok bude nasledovať alebo či už algoritmus skončil.
3. Rezultatívnosť – algoritmus dáva pre rovnaké vstupné údaje vždy rovnaký výsledok.
4. Hromadnosť – algoritmus je aplikovateľný na celú skupinu prípustných vstupných údajov.
5. Konečnosť – algoritmus musí skončiť vždy v konečnom čase po vykonaní konečného počtu krokov.
6. Efektívnosť – postup je vytvorený v čo najkratšom čase s využitím čo najmenšieho počtu prostriedkov.