2. Algoritmy

1. Algoritmus

Algoritmus je postup ako riešiť úlohu. Program je algoritmus zapísaný do matematickej formy, ktorú vie vykonávať počítač. Algoritmus zo vstupných údajov určí výstupné údaje. Pre jednu úlohu môže existovať viac vhodných algoritmov, podľa toho pre koho je určený, alebo čo berie do úvahy.

Príklad 1: Algoritmus pre ľudí: Príprava hrianok:

  • nakrájame chlieb
  • na panvicu dáme olej
  • zapneme ohrev a položíme chlieb
  • čakáme kým zhnedne a potom vyberieme

Príklad 2: Algritmus pre počítač: Súčet dvoch čísel.

  • načítaj 2 čísla A, B
  • C ← A + B
  • vypíš C

Algoritmizácia úlohy - je postup ako nájsť riešenie a zapísať ho do podoby vhodnej pre spracovanie údajov:

  1. definovanie vstupov
  2. definovanie výstupov
  3. hľadať riešenia, vybrať to najlepšie
  4. rozdeliť riešenie na menšie úlohy, ktoré možno zapísať matematicky

Príklad 3: Algoritmizácia úlohy: Určenie skutočnej spotreby auta po bežnej trase.

  1. vstupy: kilomtere, litre
  2. výstupy: litrov/km
  3. hľadanie riešení:
    1. až auto zastane, naliať liter benzínu a zmerať koľko kilometrov ešte prejdeme
    2. natankovať plnú nádrž, nejaký čas jazdiť a potom znova natankovať plnú nádrž
    3. počkať kým zasvieti signalizácia rezervy, niečo natankovať, a jazdiť kým znova nezasvieti rezerva ... tento riešenie som si vybral
  4. rozdelenie úlohy na menšie časti:
    • ak zasvieti rezerva, odčítať stav kilometrov KM1
    • po natankovaní poznačiť množstvo natankovaného benzínu LITRE
    • keď znova zasvieti rezerva, poznačiť stav kilometrov KM2
    • vypočítať prejdené kilentre KM = KM2 - KM1
    • vypočítať spotrebu na km SPOTREBA = LITRE : KM
    • poznačiť si údaj SPOTREBA na papier
PrílohaVeľkosť
AlgoritmyStruktury.svg55.46 KB
AlgoritmusProgram.odg10.03 KB
AlgoritmusProgram.svg13.24 KB

2. Vývojové diagramy

Značky

Lineárny algoritmus

- obsahuje sled príkazov.

Príklady 1: Súčet dvoch čísel:

Príklady 2: Priemer 2 čísel:

C <-- (A + B)/2

PrílohaVeľkosť
DiagramyVyvojoveZnacky.PNG29.32 KB
algoritmus1.PNG13.25 KB
algoritmus2.PNG17.64 KB
algoritmus4.PNG21.25 KB
algoritmus3.PNG17.19 KB
algoritmus5.PNG14.98 KB
VyvojoveDiagramy.svg40.31 KB
VyvojoveDiagramy.zip54.71 KB
VyvojoveDiagramy2.svg20.59 KB
VyvojoveDiagramy3.svg18.63 KB
VyvojoveDiagramy4.svg21.41 KB
VyvojoveDiagramy1.odg20.15 KB
VyvojoveDiagramy1v2.svg42.61 KB

3. Programovanie

Úrovne programovania

  1. Strojový kód - príkazy a dáta sa píšu v binárnom kóde (1 a 0), ktoré vykonáva procesor. Binárny je .exe súbor vo Windows.
  2. Vyššie programovacie jazyky - napríklad Basic, Pascal, Java, C - slovne popisujú problém. Program zapísaný vo vyššom jazyku sa nazýva zdrojový. Pre Pascal je to súbor .pas.
  3. Vývojové nástroje - sú program na programovanie, napríklad FreePascal, Delphi, Lazarus. Uľahčujú programovanie, napríklad hľadajú chyby, vytvárajú binárne programy, vkladajú časti zdrojového programu.

Požadované vlastnosti programu

  1. Konečnosť = po urrčitom čase alebo počte krokov muí skončiť.
  2. Jednoznačnosť = má robiť to čo po ňom chceme a nič iné.
  3. Efektivita = s najmenší úsilím dosiahnúť najlepšie výsledky.
  4. Všeobecnosť = rieši množinu problémov.
  5. Prehľadnosť = program nás informuje.

4. Číselné sústavy

Číselná sústava je spôsob, akým sú zapisované čísla pomocou znakov (nazývaných cifry).

Nepozičná číselná sústava

Nepozičná číselná sústava je spôsob reprezentácie čísel, v ktorom nie je hodnota číslice daná jej umiestnením v danej sekvencii číslic. Tieto spôsoby zápisu čísel sa dnes už takmer nepoužívajú a sú považované za zastarané.

V najjednoduchšom systéme stačí sčítať hodnoty jednotlivých číslic. Ak by napríklad boli hodnoty symbolov nasledovné: A = 1, B = 10, C = 100, D = 1000, potom by vyjadrením čísla 3542 mohol byť napríklad reťazec "AABBBBCCCCCDDD", ale rovnako dobre aj "ACDABBCCCCDDBB" a pod. (z hľadiska hodnoty, ale za cenu horšej zrozumiteľnosti).

Nevýhody

  • Často neobsahovali symbol pre nulu a záporné čísla
  • Dlhý zápis čísel, ktorá výrazne prevyšujú hodnotu najväčšieho symbolu sústavy

Výhody: Jednoduché sčítanie a odčítanie

Rímske číslice sú spôsob zápisu čísiel pomocou písmen abecedy. Ešte v 19. storočí bola veľmi rozšírená. Dnes sa používa zriedkavo, napríklad čísla kapitol v knihách.

Základné symboly:

  • I = 1
  • V = 5
  • X = 10
  • L = 50
  • C = 100
  • D = 500
  • M = 1 000

Spájaním a opakovaním sa zapisujú väčšie čísla, väčšie číslice predchádzajú menším. Napríklad VI je 6, CLXXIII je 173, MDCCCXXII je 1822. Rimania písali číslo 4 ako IIII, číslo 40 ako XXXX, číslo 999 ako DCCCCLXXXXVIIII. Ku skráteniu zápisu dlhých čísiel sa v stredoveku používalo pravidlo pre odčítanie, použilo sa šesť zložených symbolov, v ktorých menšia číslica predchádza väčšej:

  • IV = 4
  • IX = 9
  • XL = 40
  • XC = 90
  • CD = 400
  • CM = 900

Pri použití tohto pravidla možno číslo 999 napísať úspornejším spôsobom CMXCIX. Používanie iných symbolov nie je dovolené. Preto nemožno napísať 999 ako IM. Na druhej strane ale používanie tohto pravidla nie je povinné. Číslicu 4 možno napísať správne ako IV aj ako IIII.

Neskôr sa používajli aj malé písmená, napr. vi znamená 6 a cxiv 114. Niekedy sú miešané, napr. Cxl pre 140. Niekedy sa dokonca používa namiesto malého i písmeno j. Niekedy sa používa písmeno j iba ako posledný znak v slede jednotiek, napr. xxiij pre 23.

Pozičná číselná sústava

Pozičná číselná sústava je dnes prevládajúci spôsob písomnej reprezentácie čísel. Váha každej číslice je daná jej pozíciou v postupnosti symbolov. Základ je zvyčajne prirodzené číslo väčšie ako jedna. Váhy jednotlivých číslic sú potom mocninami tohto základu. Zároveň základ určuje počet symbolov pre číslice používané v danej sústave. V pozičných číselných sústavách má tiež zmysel hovoriť o rádoch čísel. Kde za rád číslice považujeme jej váhu a za rád čísla maximálnu váhu nenulovej číslice.

Desiatková sústava, nazvaná podľa svojho základu (10) má desať symbolov pre číslice: 0, 1, 2, 3, 4, 5, 6, 7, 8 a 9. Váhy jednotlivých číslic sú mocniny čísla 10: ...; 1000; 100; 10; 1; 0,1; 0,01; ... Pre sústavy o vyššom základe ako je tradičný počet číslic (teda desať) sa pre vyššie číslice používajú písmená bez akcentov. Napríklad šestnástková sústava má symboly: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Pričom A = 10, B = 11... F = 15.

V bežne používaných číselných sústavách sa jednotlivé číslice zapisujú za seba, nijako sa neoddeľujú. Čiarka odlišuje len celú a zlomkovú časť čísla. Niekedy sa pre prehľadnosť oddeľujú tiež významnejšie rády: tisíce, milióny, a pod. Číslo sa zapíše do zátvoriek za ktorou je dolný index so základom. V prípade desiatkovej sústavy sa číslo nemusí zapisovať do zátvoriek, ani nie je nutné k nemu písať jeho základ.

Hodnotu čísla zapísanáho v danej sústave získame ako súčet hodnôt jednotlivých číslic vynásobených ich váhou. Napríklad:

(10010)2 = 0 ⋅ 20 + 1 ⋅ 21 + 0 ⋅ 22 + 0 ⋅ 23 + 1 ⋅ 24 = 0 + 2 + 0 + 0 + 16 = 18

(152)8 = 2 ⋅ 80 + 5 ⋅ 81 + 2 ⋅ 83 = 2 + 40 + 64 = 105

(A3F)16 = 15 ⋅ 160 + 3 ⋅ 161 + 10 ⋅ 162 = 15 + 48 + 2560 = 2623

Postup pre zápis čísla v danej číselnej sústave sa líši pre jeho celú a zlomkovú časť.

Celá časť čísla (metóda delenia základom) možno vypočítať takto:

  1. Prepočítavané číslo celočíselne delíme základom cieľovej sústavy.
  2. Z podielu zapíšeme celé číslo a zvyšok po delení.
  3. Výsledok delenia použijeme v ďalšom cykle algoritmu.
  4. Predchádzajúce kroky opakujeme, kým nie je výsledkom delenia nula.
  5. Prepočítané číslo je zápis zvyškov po delení v opačnom poradí ako sa vypočítali.

Príklad: (152)10= (x)2:

152 : 2 = 76 zv. 0
79 : 2 = 38 zv. 0
38 : 2 = 19 zv. 0
19 : 2 = 9 zv. 1
9 : 2 = 4 zv. 1
4 : 2 = 2 zv. 0
2 : 2 = 1 zv. 0
1 : 2 = 0 zv. 1

Výsledok: (152)10= (10011000)2

Zlomková časť čísla (metóda násobenia základom) sa vyráta podobne, len namiesto delenia sa násobí. Postup je nasledujúci:

  1. Zlomkovú (desatinnú) časť násobíme základom cieľovej sústavy.
  2. Výsledok zapíšeme ako súčet celej a zlomkovej časti. Zlomkovú časť použijeme v ďalšom opakovaní tohto násobenia.
  3. Predchádzajúce kroky sa opakujú, až kým nie je dosiahnutý zvyšok 0 alebo požadovaná presnosť výsledku
  4. Cela časť získaného čísla je príslušnou číslicou požadovaného zápisu v inej číselnej sústave. Zapisuje sa od desatinnej čiarky doprava v poradí ako bola vypočítaná.
  5. Príklad. (0,6789)10= (x)2:

    0,678 9 ⋅ 2 = 1,357 8 = 1 + 0,357 8
    0,357 8 ⋅ 2 = 0,715 6 = 0 + 0,715 6
    0,715 6 ⋅ 2 = 1,431 2 = 1 + 0,431 2
    0,431 2 ⋅ 2 = 0,862 4 = 0 + 0,862 4
    0,862 4 ⋅ 2 = 1,724 8 = 1 + 0,724 8

    Výsledok je (0,6789)10= (0,10101)2.

    Priame prevody medzi sústavami sú možné, ak základ jednej sústavy je mocninou základu sústavy druhej. Obvykle sa tento postup používa pri prevode medzi dvojkovou a šestnástkovou. Pretože je 16=24, zodpovedá každým štyrom čísliciam dvojkového čísla práve jedna číslica šestnástková. Napríklad číslo (10010001)2obsahuje 2 štvorice znakov (1001)2 = (9)16 a (0001)2 = (1)16 a preto (10010001)2=(91)16. Pri priamom prevode zo 16-kovej do 2-kovej sústavy stačí nahradiť každý znak 16-kovej sústavy kombináciou dvojkových číslic:

    0 = 0000
    1 = 0001
    2 = 0010
    3 = 0011
    4 = 0100
    5 = 0101
    6 = 0110
    7 = 0111
    8 = 1000
    9 = 1001
    A = 1010
    B = 1011
    C = 1100
    D = 1101
    E = 1110
    F = 1111

    Napríklad (A2)16 = (1010 0010)2.

    Otázky na opakovanie

    1. Zapíšte rímskymi číslicami 2018.
    2. Zapíšte v desiatkovej sústave (1011)2
    3. Prepočítajte do dvojkovej sústavy 14,25
    4. Spravte priamy prevod medzi sústavami (10110011)2 = (x)16 ; (A2)16 = (x)2

5. Logické operácie

Logické hodnoty:

  • True = pravda = logická 1
  • False = nepravda = logická 0

Príklad 1: Výrok "v januári mrzne" má logickú hodnotu "pravda".

Základné logické funkcie:

  • AND = a zároveň - musia byť splnené všetky podmienky
  • OR = alebo - stačí aby bola splnená aspoň jedna podmienka
  • NOT = negácia = opak - opačná hodnota

Príklady:

  • AND - Pri horení je potrebné palivo a vzduch./li>
  • OR - Kúriť možno plynom alebo elektrinou.
  • NOT - Dnes je slnečné počasie a zajtra bude opak, zamračené.

Zápis logických operácií:

  • logický súčet: AND, "+", "∨"
  • logický súčin: OR, "." , "x" , "∧"
  • negácia: NOT, čiara nad premennou, apostrof, znak mínus "-"

Odvodené logické funkcie:

  • XOR - exkluzívna disjunkcia = nezhoda = buď alebo. Porovnáva unikátnosť hodnoty každého vstupu: a XOR b = a.b´ + a´.b
  • EQ - ekvivalencia = zhoda. a EQ b = ab + a´b´= (a + b´) . (a´+ b)

Príklady:

  • XOR - Na výlet pôjdeme buď na turisitiku do hôr, alebo k vodnej nádrži.
  • EQ - Na idúcom aute majú byť zapnuté obrysové aj stretávacie svetlá, alebo žiadne z nich.

Pravdivostné tabuľky funkcií obsahujú všetky kombinácie stavov premenných:

Úlohu: Napíšte logickú rovnicu pre stavbu snehuliaka. Snehuliak sa stavia (Q) ak je sneh (A), a je teplo (B) alebo svieti slnko (C).

Q = A AND (B OR C)

Q = A . (B + C)

Zápis logického výrazu z tabuľky hodnôt:

  1. Súčinova metóda: Z tabuľky zvolíme riadky s výslednou hodnotou 1. Premenné v riadku zapíšeme ako logický súčin, pričom premenné ktoré majú hodnotu 0 sa zapíšu ako negácia. Jednotlivé riadky zapíšeme ako logický súčet.
  2. Súčtová metóda: Z pravdivostní tabulky sa vyberú riadky, ktoré majú výsledek operácie rovný logickej nule. Z vybraných riadkov sa vytvoria logické súčty. Ak je premenná rovna 1, tak sa neguje. Ak je logická premenná rovná 0, neneguje sa.

Úloha: Napíšte logickú rovnicu z pravdivostnej tabuľky pre stavbu snehuliaka:

Použijeme metódu ktorá dáva jednoduchšiu rovnicu, v tomto prípade súčinovú:
Q = (´A . B . C) + (A . ´B . C)

Minimalizácia logického výrazu sa dá robiť pomocou

  1. Booleova algebra – vhodná pre jednoduché funkcie a učnú úpravu, https://is.muni.cz/th/322248/pedf_b/Booleova_algebra.pdf .
  2. Karnaughove mapy – pre ručnú úpravu, vhodné pre max. 3 premenné, https://sk.wikipedia.org/wiki/Karnaughova_mapa
  3. Quineova metóda - pre počítačové riešenie, pre max 4 premenné, https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm
  4. Heuristické metódy - pre počítače a veľa premenných, program https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer

Booleova algebra zovšeobecňuje vlastnosti množinových a logických operácií, pre ktoré sú definované axiómy (základné vety):

  • komutativita: A + B = B + A
  • distributivita:
    A + (B x C) = (A + B) x (A + C)
    A x (B + C) = (A x B) + (A x C)
  • neutralita:
    A + 0 = A
    A x 1 = A
  • komplementarita
    A + -A = 1
    A x -A = 0

Platí:

  • asociativita:
    (A + B) + C = A + (B + C)
    (A x B) x C = A x (B x C)
  • absorpcia:
    A + (A x C) = A
    A x (A + B) = A
  • agresivita nuly: A x 0 = 0
  • agresivita jednotky: A + 1 = 1
  • idempotencia:
    A + A = A
    A x A = A
  • absorpcia negácie:
    A + (−A x B) = A + B
    A x (−A + B) = A x B
  • dvojitá negácia: −(−A) = A
  • De Morganove zákony:
    −A x −B = −(A + B)
    −A + −B = −(A x B)
  • 0 a 1 sú vzájomne komplementárne:
    −0 = 1
    −1 = 0

Príklady na zjednodušenie:

  1. a.(b+c) + ac = ab + ac + ac = ab + ac = a(b+c)
  2. ab + ac + ac´ = ab + a.(c + c´) = ab + a.(1) = ab + a = a(b + 1) = a
  3. stavba snehuliaka: Q = (-A x B x C) + (A x -B x C) = C x (-A x B + A x -B)

Karnaughova mapa - V tabuľke sú výsledky, v hlavičke sú úseky pre hodnoty 0 a 1 pre jednotlivé premenné. Pre stavbu snehuliaka môže vyzerať takto:

Z tejto tabuľky vyčítame minimálnu funkciu. Q = C x (-A x B + A x -B)

PrílohaVeľkosť
LogickaTabulkaFunkcia.PNG8.17 KB
LogickaTabulkaFunkcia.PNG6.92 KB
LogickaTabulkaFunkcia.PNG9.12 KB
LogickaTabulkaFunkcia.PNG9.24 KB
LogikaStaviameSnehuliaka.PNG4.78 KB
LogFunkcieTabulky.PNG4.7 KB
KarnaughSnehuliak.PNG1.59 KB