ALGORITMY A PROGRAMOVANIE

Základné pojmy

Problém - stav, v ktorom jestvuje rozdiel medzi tým, čo v danom momente máme a tým, čo chceme dosiahnuť

Riešenie problému - odstraňovanie rozdielu medzi pôvodným stavom a tým, čo chceme dosiahnuť

Algoritmus - postup, ktorým sa pri riešení problému riadime

Program - zápis algoritmov v počítači.

Pretože program je návod ako spracovávať určité informácie, musíme najskôr náš problém sformulovať ako problém spracovania informácií. To znamená, že najskôr musíme vytvoriť určitý informačný model riešenia problému. Informačný model, ktorý sa nazýva úloha, musí obsahovať:

1. popis informácií potrebných pre riešenie problému, t.j. popis vstupných podmienok,
2. popis informácií, ktoré majú predstavovať riešenie úlohy, t.j. popis výstupných podmienok,
3. vzťahy, ktorými sa dostaneme od vstupných k výstupným podmienkam.

Okrem týchto základných požiadaviek musí úloha obsahovať rad ďalších upresnení (špecifikácií), napr. časové a organizačné podmienky alebo charakteristiku prostredia, v ktorom bude úloha riešená.

V prvej fáze formulácie úlohy je vhodné, ak si túto úlohu zapíšeme v tvare:

{VST: vstupné podmienky}
?
{VYST: výstupné podmienky}

Zložité problémy sme často nútení rozložiť na rad vzájomne závislých čiastkových úloh, ktoré až ako celok predstavujú celý problém.

Napríklad - formuláciu úlohy pre riešenie kvadratickej rovnice ax² + bx + c = 0. Naša úloha bude obsahovať:

1. Vstupné podmienky: ľubovoľné reálne čísla a, b, c, pričom a nesmie byť rovné 0
2. Výstupné podmienky: podmnožina X reálnych čísel predstavujúcich riešenie kvadratickej rovnice.
3. Vzťahy medzi vstupnými a výstupnými informáciami:
     pre každé x patriace do X platí ax² + bx + c = 0.
     V našom zápise to môžeme zapísať:

{VST: a, b, c - reálne, a≠0}
{VYST: x patrí do X}

Správna formulácia úlohy, ktorú chceme riešiť pomocou počítača, je prvým predpokladom úspechu. Nie vždy je ale formulácia úlohy taká jednoduchá. Je častý prípad, keď sa opakovane vraciame k formulácii a upresňujeme ju tak, ako postupne celý problém upresňujeme.

Algoritmus je elementárny pojem informatiky, preto nie je možné definovať ho pomocou jednoduchších pojmov.

Korektná definícia pojmu algoritmus je:
presná postupnosť krokov a inštrukcií, ktorá nás od (meniteľných) vstupných údajov privedie v konečnom čase k výsledku.

Nie každý postup je algoritmom, potrebuje spĺňať nasledovné vlastnosti:

• elementárnosť: postup je zložený z jednoduchých krokov, ktoré sú pre vykonávateľa (počítač, nemysliace zariadenie, človek) zrozumiteľné,
• determinovanosť: postup je zostavený tak, že v každom momente jeho vykonávania je jednoznačne určené, aká činnosť má nasledovať, alebo či sa už postup skončil,
• rezultatívnosť: postup dáva pre rovnaké vstupné údaje vždy rovnaké výsledky,
• konečnosť: postup vždy skončí po vykonaní konečného počtu krokov,
• hromadnosť: postup je použiteľný na celú triedu prípustných vstupných údajov,
• efektívnosť: postup sa uskutočňuje v čo najkratšom čase a s využitím čo najmenšieho množstva prostriedkov (časových i pamäťových).

Elementárnosť

Každý postup môže byť zapísaný viacerými spôsobmi. Dôležité je, aby mu rozumel jeho vykonávateľ.

Príklad: Problém zohrievania mlieka v mikrovlnej rúre:

Algoritmus pre dlhodobého vlastníka mikrovlnky môže byť: zohrej mlieko
Algoritmus pre nového majiteľa, musí byť podrobnejší

Príklad:
Ak zapíšeme jeden krok algoritmu nasledovne: zistite 6 mocninu dvojky
Pre piataka-šiestaka na ZŠ je formulácia v poriadku, druhák ju nezvládne, napriek tomu, že ide len o 2.2.2.2.2.2

S elementárnosťou súvisí aj potreba formulovať jednotlivé kroky algoritmu jednoznačne.

Príklad nejednoznačných formulácií:
Meľ dva dni staré rožky!
Rozbi dve vajcia!

Determinovanosť

V každom kroku musí byť jasné, kam sa má riešenie uberať, čím pokračovať.
Ak by sa napr. algoritmus „umyť, urobiť za sebou poriadok, vyzliecť a spať“ vykonával v inom poradí, nemuselo by už byť tým, čo bolo pôvodne zamýšľané
Ak by počítač vykonal najprv časovo najnáročnejšiu úlohu: najprv pôjde spať (vykoná časovo najnáročnejšiu úlohu) a až keď sa vyspí, urobí poriadok, vyzlečie sa a umyje

Rezultatívnosť

Výsledok za rovnakých vstupných podmienok má byť vždy rovnaký.
V bežnom živote sa to vždy podariť nemusí – ako príklad môžu slúžiť algoritmy pre  varenie, alebo pečenie (recepty).
Číslicová technika, pokiaľ nedôjde k poruche, s tým problémy nemá

Príklad:
Traja chlapci si v športovom obchode kúpili loptu. Zaplatili za ňu spolu 30,- Sk. Keď odišli, predavač zistil, že lopta stála len 25,- Sk a so zvyšnými peniazmi poslal za nimi pomocníka. Ten im dal 3,- Sk a 2,- Sk si ponechal „od cesty“. Takže chlapci (keďže každý dostal 1,- Sk nazad) zaplatili za loptu po 9,- Sk a pomocníkovi zostali 2,- Sk.
Spolu: 9 x 3 + 2 = 29,- Sk. Kam sa podela zvyšná koruna?

Konečnosť

Vlastnosť, ktorá má zabezpečiť, aby sa algoritmus vždy skončil.
Človek, pracujúci s problémom na základe skúseností dokáže určiť, či jeho postup dá alebo nedá správny výsledok (resp. či skončí alebo nie).
Počítač sa na takejto úrovni rozhodnúť nedokáže

Algoritmus pre počítač

1. polož hrniec s jedlom na varič,
   
2. pusti plyn,
   
3. miešaj, kým nezačne vrieť.

Nie je v tejto podobe konečný – počítač nedokáže určiť moment ukončenia postupu.

Existujú aj problémy, ktorých riešenie je síce konečné, ale nájdenie výsledku trvá veľmi dlho.

• šifrovacie algoritmy, keď síce teoreticky dokážeme rozšifrovať každú správu, no doba realizácie je taká dlhá, že správa po rozšifrovaní (po 10 rokoch) stráca zmysel.
• počítanie buniek v ľudskom tele,
• počítanie molekúl v litri vzduchu

Hromadnosť

Každý algoritmus musí byť čo najvšeobecnejší, aby bolo možné pomocou neho riešiť čo najširšie množstvo úloh. Predstavme si, že spracujete program, ktorý bude vedieť vypočítať koľko je 1+1. Algoritmus bude veľmi jednoduchý, ale bude to znamenať, že keď budeme chcieť spočítať iné dve čísla, budeme musieť vytvoriť síce veľmi podobný, ale nový algoritmus a ten potom naprogramovať. Preto je nutné algoritmus zovšeobecniť – umožniť načítanie ľubovoľných dvoch čísel a tie potom spočítať.

Efektívnosť

Táto vlastnosť znamená navrhnúť taký postup, ktorý s použitím minimálnych prostriedkov v čo najkratšom čase vyrieši problém.
Aj neefektívny algoritmus je však algoritmom.

Príklad:
Problém sčítavania čísel 1 až 100.
Prvý spôsob, ktorému všetci rozumieme je postupovať 1+2+3+4+...+100.
K výsledku sa síce dostaneme, ale ak vezmeme dvojice čísel 1+100, 2+99, 3+98... 50+51 (spolu ich je 50), vyriešime problém podstatne rýchlejšie: dvojíc je 50, ich súčet je 101, teda 101 x 50 = 5 050.

Proces, ktorý vykonávame pri zápise algoritmu sa nazýva algoritmizácia.
Použitie ľudského jazyka pri zápise algoritmov je problematické, kvôli veľkej nejednoznačnosti (použitie frazeologizmov, synonymá, homonymá, tvary, pády, osoby). Okrem toho ľudský jazyk sa prirodzene obohacuje o nové slová, niektoré slová sa prestávajú používať. Vzniká preto pre potreby zápisu algoritmov vytvoriť jazyk – algoritmický jazyk. Existuje niekoľko typov algoritmických jazykov:

1. vývojové diagramy (postupnosť činností popisovaná prostredníctvom grafických značiek a textu v nich),
2. štruktúrogramy (zhutnená obdoba vývojových diagramov, ktorá však oproti vývojovým diagramom nie je definovaná normou),
3. obrázkové jazyky (často detské programovacie jazyky umožňujúce programovať prostredníctvom spájania obrázkov),
4. rozhodovacie tabuľky (popisujú zložitejšie problémy pozostávajú zo zoznamu podmienok, kombinácie podmienok, zoznamu činností a kombinácie činností),
5. slovný zápis algoritmu v národnom jazyku (formalizované jazyky, ktoré sa od programovacích jazykov odlišujú použitím slov národného),
6. programovacie jazyky (formalizované algoritmické jazyky často založené na redukcii slov anglického jazyka).

Skladba algoritmického jazyka

Každý algoritmický jazyk má dve zložky.
Operačná zložka:

Príkazy:	vety jazyka prikazujúce procesoru vykonať presne stanovené činnosti. (vstupu, výstup a priradenie). Príkazy spracúvajú iné objekty: premenné, konštanty a výrazy.
Premenná	objekt obsahujúci počas realizácie algoritmu konkrétnu hodnotu presne stanoveného typu (napr. celé číslo, reálne číslo, reťazec znakov...).
Konštanta	objekt nadobúdajúci počas celej realizácie algoritmu jedinú konkrétnu hodnotu príslušného typu. Je to obdoba konštánt známych z matematiky, napr. pí, e, ale aj z fyziky: g, c, k, e, m.
Výraz	predpis obsahujúci konštanty, premenné a spôsob ich spracovania pomocou operácií a funkcií podobných tým, ktoré poznáme z matematiky. Výsledkom je hodnota príslušného typu, ktorá vznikne po vykonaní vo výraze naznačeného spracovania. napr.         obsah=a*b                 obsah=pí*r*r

 

Riadiaca zložka:

Predstavujú ju prostriedky pre riadenie postupnosti vykonávania jednotlivých prvkov operačnej zložky.
Vďaka nej je v každom kroku algoritmu jednoznačne určená činnosť, ktorá sa má vykonať
sekvencia
vetvenie
cyklus

Príklad sekvencie

Majme k dispozícii robotický vysávač, ktorý dokáže nasledovné činnosti:
posun – posunie vysávač vpred o 50 cm,
vysaj – zapne vysávanie prachu na 10 s,
vľavo bok - otočí sa o 90° doľava.

Zabezpečte, aby vysávač vysal metrový pás v smere, ktorý má nastavený.

Riešenie – sekvencia príkazov:

vysaj        
posun       
vysaj        
posun       

Problém sme vyriešili vďaka sekvencii príkazov, ktoré sa vykonávajú v takom poradí, v akom sú zapísané.
Vo všeobecnosti možno sekvenciu zapísať nasledovne:

        príkaz₁
        príkaz₂
        ...
        príkaz_n

 

Príklad alternatívy

Zabezpečte, aby sa vysávač v prípade narazenia na prekážku otočil doľava.
Na riešenie problému potrebujeme, aby vysávač dokázal zistiť (rozhodnúť), či má pred sebou prekážku alebo nie. Nevyhnutnou je teda nová schopnosť:
prekážka – v prípade existencie prekážky vráti hodnotu ANO, inak hodnotu NIE,

Riešenie:

ak prekážka = ÁNO tak
                    vľavo bok
inak
                    posun

Zápis obsahuje dve vetvy (alternatívy), pričom stroj, ktorý príkazy vykonáva si vyberie v závislosti od splnenia podmienky.
Vo všeobecnosti:

        ak podmienka tak
                príkaz₁₁
                príkaz₁₂
                ...príkaz_1m
        inak
                príkaz₂₁
                príkaz₂₂
                ...príkaz_2n
        koniec ak

Príklad cyklu

Zabezpečte, aby vysávač vyčistil 15 metrový pás.
Úlohu by sme mohli riešiť zápisom sekvencie tak, že by sme 30 ráz za sebou zopakovali dvojicu:
     vysaj posun     vysaj posun     vysaj posun         vysaj posun....
Vhodnejšie riešenie však predstavuje použitie cyklu.
Počet opakovaní nám je známy (30 x  - prečo?)

Riešenie:

opakuj 30 krát
        vysaj
        posun

Vo všeobecnosti:

        opakuj počet krát
            príkaz1
            príkaz2
            ...
            príkazn
        koniec opakuj

Použitý cyklus sa nazýva cyklus s pevným (známym) počtom opakovaní

Nie vždy je nám však počet opakovaní známy v momente vytvárania algoritmu. Preto je potrebné kontrolovať ukončenie cyklu buď:

• pred vykonaním kroku (tela) cyklu – cyklus s podmienkou na začiatku
• po vykonaní tela cyklu – cyklus s podmienkou na konci

V prvom prípade sa cyklus nemusí vykonať vôbec, v druhom prebehne minimálne raz.

Príklad cyklus s podmienkou na začiatku

Napíšte algoritmus, ktorý zabezpečí vysávanie od aktuálnej polohy po prekážku.

    pokiaľ prekážka = NIE rob
        vysaj
        posun
    koniec pokiaľ

Všeobecne:

    pokiaľ podmienka rob
            príkaz1
            príkaz2
            ...
            príkazn
        koniec rob

Príklad cyklus s podmienkou na konci

Upravte algoritmus zabezpečujúci vysávanie od aktuálnej polohy po prekážku tak aby sa vysávanie vykonalo minimálne raz.

    rob
        vysaj
        posun
     pokiaľ nebude prekážka = ANO

Všeobecne:

    rob
            príkaz1
            príkaz2
            ...
            príkazn
    pokiaľ nebude podmienka

Vývojové diagramy

Príkazy vstupu a výstupu

Príkaz vstupu

p1, ... , pn sú premenné, do ktorých sa uložia údaje na spracovanie

Príkaz výstupu

h1, ... , hn sú výstupné hodnoty (položkou výstupu môže byť aj text uzavretý v úvodzovkách)

Príkaz priradenia a sekvencia

Príkaz priradenia:

p je premenná; v je výraz, ktorého hodnotu priradením premenná p nadobudne

Sekvencia:

p1, ..., pn sú príkazy; vykonajú sa  v poradí v akom sú zapísané

Jednoduché príklady

• Vypočítajte súčet dvoch čísel.
• Zistite obsah a objem kruhu.
• Vypočítajte objem a povrch hranola.

Vetvenie (alternatíva)

Binárne úplné – obsahuje príkazy v oboch vetvách

p1, p2 sú príkazy (resp. zložené príkazy)

• ak je podmienka splnená vykoná sa p1,
• ak nie je splnená vykoná sa p2

Binárne neúplné – obsahuje príkazy  v oboch vetvách

•  ak je podmienka splnená vykoná sa príkaz p,
• inak je vetvenie bez účinku

Jednoduché príklady

• Zistite maximálnu hodnotu z dvoch zadaných čísel.
• Zistite podiel dvoch čísel (nezabudnite na nemožnosť delenia nulou).
• Zistite absolútnu hodnotu zadaného čísla.

Cyklus

S pevným počtom opakovaní

• i je riadiaca premenná cyklu, n je počet opakovaní, p je príkaz (resp. zložený príkaz), ktorý sa opakuje

S neznámym počtom opakovaní - s podmienkou na začiatku

S neznámym počtom opakovaní - s podmienkou na konci

Jednoduché príklady

• Vypočítajte hodnotu súčtu prvých N prirodzených čísel.
• Zistite faktoriál zadaného čísla
• Vypočítajte ciferný súčet číslic daného prirodzeného čísla N.