Algoritmizácia

Obsah tém. 

  1. Čo je to algoritmus?
  2. Vlastnosti algoritmov
  3. Algoritmické metódy
  4. Grafické značky vývojových diagramov
  5. Príklady algoritmov 1.   2.   3.   4.   5.  
  6. Základné štruktúry algoritmov
  7. Opakovanie
  8. Príklady úloh

Počítač je prostriedkom pre automatizované riešenie úloh založených na informačných procesoch. Proces vykonávania operácií sa nazýva výpočtový proces.
Riešenie úlohy je často formulované tak, že postupnosť operácií nie je celkom jasná. Treba preto stanoviť presné pravidlá- tomuto procesu sa hovorí algoritmizácia úlohy.
Výsledkom algoritmizácie je zostavenie algoritmu.

Algoritmizácia úlohy prebieha v troch etapách:

  • formulácia- slovné zadanie úlohy
  • analýza- úloha sa zovšeobecňuje, určujú sa podmienky postupu
  • zostavenie algoritmu- presné vyjadrenie logiky a postupu riešenia

Čo je algoritmus?

Algoritmus je konečná postupnosť dobre definovaných inštrukcií na splnenie určitej úlohy.

Algoritmy môžu byť zapísané (implementované) vo forme počítačových programov.
Logická chyba v algoritme môže viesť k zlyhaniu výsledného programu.

Pojem algoritmu sa často ilustruje na príklade receptu, hoci algoritmy sú často oveľa zložitejšie.
V algoritmoch sa často niekoľko krokov viacnásobne opakuje (iterácia), alebo ďalší postup závisí od aktuálneho stavu (vetvenie).

Na riešenie tej istej úlohy môže existovať niekoľko rôznych algoritmov s rôznymi postupnosťami inštrukcií.
Rôzne algoritmy sa tiež môžu líšiť v množstve času a pamäte potrebných na splnenie úlohy.

Slovo algoritmus je odvodené od mena stredovekého matematika Muhammada al-Chorezmího.

Vlastnosti algoritmov

Rezultatívnosť ( konečnosť )
Každý algoritmus musí skončiť po vykonaní konečného počtu krokov.
Tento počet krokov môže byť ľubovoľne veľký (podľa rozsahu a hodnôt vstupných údajov), ale pre každý jednotlivý vstup musí byť konečný.
Postupy, ktoré túto podmienku nespĺňajú, sa môžu nazývať výpočtové metódy.
Špeciálnym príkladom nekonečnej výpočtovej metódy je reaktívny proces, ktorý priebežne reaguje s okolitým prostredím.

Determinovanosť
Každý krok algoritmu musí byť jednoznačne a presne definovaný; v každej situácii musí byť úplne zrejmé, čo a ako sa má vykonať,
ako má vykonávanie algoritmu pokračovať.
Pretože bežný jazyk zvyčajne neposkytuje úplnú presnosť a jednoznačnosť vyjadrovania, boli pre zápis algoritmov navrhnuté programovacie jazyky,
v ktorých má každý príkaz jasne definovaný význam. Vyjadrenie algoritmu v programovacom jazyku sa nazýva program.

Vstup
Algoritmus zvyčajne pracuje s nejakými vstupmi, veličinami, ktoré sú mu odovzdané pred začatím jeho vykonávania, alebo v priebehu jeho činnosti.
Vstupy majú definované množiny hodnôt, ktoré môžu nadobúdať.

Výstup
Algoritmus má aspoň jeden výstup, veličinu, ktorá je v požadovanom vzťahu k zadaným vstupom, a tým tvorí odpoveď na problém, ktorý algoritmus rieši.

Efektivita
Všeobecne požadujeme, aby algoritmus bol efektívny, v tom zmysle, že požadujeme, aby každá operácia požadovaná algoritmom,
bola dostatočne jednoduchá na to, aby mohla byť aspoň v princípe prevedená v konečnom čase iba s použitím ceruzky a papiera.

Všeobecnosť
Algoritmus nerieši jeden konkrétny problém (napr. „ako vypočítať 3×7“), ale rieši všeobecnú triedu obdobných problémov (napr. „ako vypočítať súčin dvoch celých čísel“).


Pozn. Príklad algoritmu: Športová zábava.
Ráno vstanem a nahliadnem do kalendára. Je školský deň alebo deň voľna? Ak je školský deň končí zábava inak Je deň voľna rozhodnem sa pre zábavu.
Nahliadnem do kalendára. Je leto alebo zima? Ak je leto idem sa kúpať inak Ak je zima rozhodneme sa pre zimné športy.
Nahliadnem na teplomer za oknom. Je pod bodom mrazu áno. Ak nie idem do kina ak áno rozhodnem sa podľa množstva snehu.
Ak je veľa snehu idem sa lyžovať inak sa pôjdem korčuľovať. Vezmem správny nástroj a odchádzam z domu.


Algoritmické metódy

Algoritmické postupy sa dajú zobraziť mnohými spôsobmi. Dôležité je aby sme si po čase vedeli spomenúť čo sme zaznamenali a aby nášmu záznamu rozumeli aj ostatní.
Pre zobrazenie algoritmu používame rôzne metódy; patrí k nim napr:
 

  • formalizovaný popis priebehu pracovného postupu vo forme textu členeného na odstavce (logické štruktúry z funkčného hľadiska)
  • dátovo orientované diagramy HIPO (z angl. Hierarchy plus Input- Process- Output, tzn. hierarchický diagram a diagram vstupu, spracovania, výstupu), spojujúce v grafickom vyjadrení funkčné členenie problému, štruktúry dát a pracovných postupov pri rôznom stupni podrobnosti
     
  • štruktúrne diagramy zamerané predovšetkým na zobrazenie postupností operácií v úlohe, avšak s využitím štandardných algoritmických štruktúr
     
  • štruktúrne diagramy vo forme stromového diagramu, v ktorom sa procesy postupne členia až na najnižšiu úroveň, tzn. k operáciám so súčasnou charakteristikou algoritmickej štruktúry (vetvenie, opakovanie a pod.)
     
  • vývojové diagramy toku dát a vývojové diagramy programu zobrazujúce predovšetkým postupnosť operácií v systéme a v jednotlivých úlohách
     
  • rozhodovacie tabuľky využívané zvlášť pri zložitých rozhodovacích procesoch v algoritmoch programu
  • slovný zápis
     

Grafické zobrazenie algoritmu úlohy voláme vývojové diagramy
Vývojové diagramy popisujú algoritmus programu grafickými značkami

Grafické značky vývojových diagramov

Význam jednotlivých značiek:
  • a - začiatok algoritmu
  • b - koniec algoritmu
  • c - začiatok podprogramu
  • d - koniec podprogramu
  • e - jednoduchý príkaz (viac za sebou vytvárajú blok príkazov)
  • f - čítaj resp. vypíš (aj vytlač)
  • g - volanie podprogramu
  • h - riadený cyklus s konkrétnym počtom opakovaní
  • i, j - spojenie dvoch ciest resp. smerovanie programu
  • k - odskok na návestie
  • l - návestie na ktoré smeruje skok
  • m - rozhodovací blok s jedným vstupom a viacerími výstupmi.

Jednotlivé značky sú spojené spojnicami

  • vodorovné

  • zvislé


Môžu, ale nemusia mať šípku, ktorá určuje smer vykonávania jednotlivých činností
Spojnice sa vo vývojovom diagrame môžu:

• križovať   
• spájať      

 

Príklady algoritmov

Príklad č.1

Algoritmus , ktorý vypočíta paralelný resp. sériový odpor na základe rozhodnutia.

Vieme, že:        Rp=(R1*R2)/(R1+R2)
                        Rs=R1+R2
Vstup:
R1,R2 - hodnoty odporov
znak - premenná do ktorej sa ukladá 1 znak (p - pre paralelný odpor / s - pre sériový odpor)
Výstup:
Rp -  paralelný odpor
Rs - sériový odpor
"Zadal si iný znak"

Algoritmus Štrukturogram

 

Príklad č.2

Algoritmus, ktorý zistí či je možné zostrojiť trojuholník ak zadáme dĺžky troch strán.

Trojuholník je možné zostrojiť ak súčet dĺžok každých dvoch strán je väčší ako dĺžka tretej strany.
Teda musíme zistiť či:
a + b > c
a + c > b
b + c > a

Vstup:
Dĺžky strán a,b,c
Výstup:
Je možné zostrojiť trojuholník alebo nie.

Algoritmus Štrukturogram

 

Príklad č.3

Algoritmus pre výpočet kvadratickej rovnice s reálnymi koreňmi.

a*x*x + b*x +c = 0            D = b*b - 4*a*c

Testujeme D:
ak    D > 0    kvadratická rovnica má dva korene
                    x1 = (-b + SQRT(D)) / (2*a)
                    x2 = (-b - SQRT(D)) / (2*a)
ak    D = 0    kvadratická rovnica má jeden koreň
                    x1 = x2 = (-b ) / (2*a)
ak    D < 0    kvadratická rovnica nemá riešenie v reálnych číslach

Vstup: a,b,c
Výstup: korene kvadratickej rovnice

Algoritmus Štrukturogram

 

Príklad č.4

Algoritmus pre zistenie počtu slov vo vete.
Ide o algoritmus v ktorom sa postupne zadáva jedno písmeno po druhom, zadávanie končí bodkou. Jednotlivé slová vo vete sú oddelené medzerou.
Princíp spočíva v zisťovaní či každý znak, ktorý sa načíta nie je medzera. Na počítanie slov použijeme pomocnú premennú, ktorá sa zvýši o 1 ak sa zistí znak medzera.
Tento proces sa opakuje, pokiaľ načítaný znak nie je bodka. Počet medzier zvýšený o 1 určuje počet slov vo vete.

Algoritmus Štrukturogram

Príklad č.5

Algoritmus, ktorý vynásobí dve celé čísla za podmienky, že nebude použitá inštrukcia násobenia, ale len sčítania.

Princíp riešenia:
Pamätáte si ako nás učili násobiť na základnej škole ?
5 * 2    je to isté ako    5+5
8 * 3    je to isté ako    8+8+8
Pokúsme sa to zovšeobecniť.
a * b    je ako    a+a+a...+a     Z toho vyplýva    a sčítame b-krát

Cyklus so známym počtom opakovaní

Vstup:      a, b - dve čísla, ktoré máme medzi sebou vynásobiť
                c - premenná na ukladanie medzivýsledkov súčtov. Nakoniec v nej bude uložený výsledok.
                i - riadiaca premenná cyklu 
Výstup:    výsledný súčet, uložený v premennej c   

Algoritmus Štrukturogram

 

Základné štruktúry algoritmov

lineárna jednoduchá štruktúra (sekvenčná)
algoritmus prebieha lineárne bez opakovania a obsahuje v podstate vstupné, výpočtové a výstupné operácie

 

lineárna rozvinutá štruktúra (rozhodovacia)
algoritmus opäť prebieha lineárne bez opakovania, obsahuje však najviac operáciu výberu, keď určité operácie sa prevedú len za splnenia určitých podmienok. V opačnom prípade sa pokračuje ďalej vo výpočte alebo sa realizujú iné operácie. Dochádza teda k vetveniu v lineárnej sekvencii operácie programu. Vetvenie môže byť viacnásobné, závislé na hodnotách, ktoré obsahuje premenná nazývaná prepínač.

neúplná - Podmienečné vykonanie
úplná - Alternatívne vykonanie Prepínač

 

cyklická štruktúra
Algoritmus prebieha ak dlho pokiaľ je splnená podmienka. Činnosť, ktorá sa má opakovať nazývame telom cyklu
Podmienku, ktorá určuje dokedy sa bude cyklus opakovať, nazývame podmienka cyklu

  1. cyklus so známym počtom opakovaní - telo cyklu sa opakuje vopred známy počet krát
  2. cyklus s podmienkou na začiatku - najčastejšie sa volí cyklus, kedy sa telo cyklu opakuje, pokiaľ platí podmienka cyklu
  3. cyklus s podmienkou na konci - je opačný cyklus s podmienkou na začiatku- najskôr sa vykoná telo cyklu. Potom sa zisťuje splnenie podmienky cyklu.
a b c

Opakovanie

  • Čo je počítač?
  • Čo je program?
  • Čo je algoritmizácia?
  • Čo je algoritmus?
  • Základné vlastnosti algoritmov?
  • Napísať Grafické značky:  vstup, vykonaj, rozhodni, cykly, začiatok a koniec vývojového diagramu.
  • Popísať základné štruktúry algoritmov.

Príklady

  1. Vytvorte algoritmus, ktorý zistí či načítané číslo je parne alebo nepárne.
  2. Vytvorte algoritmus pre výpočet obvodu alebo obsahu štvorca.
  3. Vytvorte algoritmus, ktorý vypočíta odmocninu zo zadaného čísla.
  4. Vytvorte algoritmus pre výpočet absolútnej hodnoty  čísla.
  5. Vytvorte algoritmus, ktorý porovná dve čísla zo vstupu a vypíše väčšie z nich.
  6. Vytvorte algoritmus, ktorý porovná tri čísla a vypíše najväčšie z nich.
  7. Vytvorte algoritmus, ktorý porovná tri čísla a pomocou pomocnej premennej ich usporiada od najväčšieho po najmenší.
  8. Vytvorte algoritmus, ktorý či číslo je kladné, záporné alebo rovné 0.
  9. Vytvorte algoritmus, ktorý nájde najväčší spoločný deliteľ.
  10. Vytvorte algoritmus pre výpočet faktoriálu.