Algoritmus a problém

predpokladom potreby algoritmu je

existencia problému

v prvých rokoch života je riešenie

problémov postavené na iných základoch
ako neskôr

riešenie mnohých problémov je automatické

bez uvedomenia si existencie algoritmu

Problém pitia kakaa

 overiť dostatok surovín

1.

do hrnčeka nalejeme mlieko,

2.

dáme ho zohriať,

3.

do prázdnej šálky zmiešame cukor a kakao,

4.

skontrolujeme mlieko,

5.

ak nie je dosť teplé, vrátime sa do bodu 4.,

6.

zalejeme zmes v šálke,

7.

necháme vychladnúť,

8.

vypijeme.

 a je po probléme...

Terminológia

 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

 Nie každý problém je riešiteľný a nie vždy sa

dopracujeme k požadovanému výsledku

Algoritmus a život

 riešiť pomocou algoritmu problémy

reálneho života je dosť náročné, pretože

správny algoritmus vždy berie do úvahy

všetky možnosti, detaily, náhody alebo

zriedkavé situácie (pitie kakaa)

 o algoritmoch má zmysel hovoriť vtedy,

keď máme k dispozícii určitú obmedzenú

množinu príkazov (môže byť aj veľmi

veľká), pomocou ktorých dokážeme

navrhnúť postup pri riešení.

Algoritmus a Programovanie

 elementárny pojem, potrebná korektná

definícia:

 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:

Vlastnosti algoritmu



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ť: výpočet dáva po konečnom počte krokov výsledok,



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ľ
 zohrievanie mlieka v mikrovlnnej rúre:

–

dlhodobý vlastník: zohrej mlieko

–

nový majiteľ?

–

dieťa (počkaj na rodičov a požiadaj ich)



 zistite 6 mocninu dvojky

–

pre piataka-šiestaka je formulácia OK

–

druhák ju nezvládne, napriek tomu, že ide len o 2.2.2.2.2.2

 jednoznačnosť:

–

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. obľúbené „umyť, urobiť za sebou

poriadok, vyzliecť a spať“ vykonávalo 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ť

 realizácia dokázateľne vedie po konečnom počte krokov

k správnemu výsledku pri riešení ľubovoľnej zo skupiny
úloh, pre ktorú bol algoritmus vytvorený

–

v bežnom živote sa to vždy podariť nemusí – varenie/pečenie

–

číslicová technika, pokiaľ nedôjde k poruche, s tým problémy
nemá

Konečnosť

 vlastnosť 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č bez skúseností 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ť.

......

Konečnosť II.

 Kop, kým nenarazíš na poklad!
 Kým je zadané číslo menšie ako jedna, vynásob ho

dvoma!

 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,

–

molekúl v litri vzduchu

–

zrniek piesku na púšti.

Hromadnosť

 vlastnosť skôr užitočná ako nutná

–

nie každý algoritmus vie byť hromadný,

–

je potrebné vkladať do algoritmu určité vstupné parametre

–

napr. objem kvádra, výpočet dĺžky brzdnej dráhy pri rýchlosti
vozidla a povrchu vozovky a zadanej hmotnosti

 pri tvorbe algoritmu nejde o vyriešenie konkrétneho

problému, ale len o popísanie postupu, pomocou ktorého
možno získať výsledok

Efektívnosť

 opäť nepovinná vlastnosť
 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 algoritmom

 Pri prehliadke veliteľ potreboval zistiť počet nastúpených

vojakov. Vojaci stáli v 32 radoch po 17. Úlohou poveril dvoch

zástupcov. Prvý postupoval nasledovne: 17+17+17+17+....+17,

druhý to skúsil ako 17 x 32. Čo myslíte, ktorý sa dopracoval k

výsledku skôr?

 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.

Načo algoritmizovať?

 život je algoritmus (resp. je zložený z algoritmov)
 moje vstávanie:

–

zazvoní budík,

–

otvorím pravé oko,

–

udriem ho (budík),

–

zatvorím pravé oko,

–

o dvadsať minút sa strhnem,

–

v zhone zhltnem raňajky

–

bežím do práce

 na čo je dobrý popis algoritmu?

–

vďaka popisu dokážeme vykonávaním algoritmu poveriť iného človeka
alebo počítač

–

vďaka vyjadreniu myšlienok sa nám problém stáva zrozumiteľnejším
a sme schopní lepšie mu porozumieť

Algoritmizácia

 proces, ktorý pri zápise algoritmu vykonávame
 na začiatku vždy potrebujeme určiť:

–

vstupné podmienky (napr. rozsah hodnôt, ktoré môžu do
algoritmu vstupovať)

–

výstupné podmienky (vlastnosti výsledku)

 Zadanie algoritmu zapisujeme:

{VST: vstupné podmienky}

?

{VÝS: výstupné podmienky}

{VST: a, b, c : reálne čísla rôzne od 0}

?

{VÝS: V – reálne číslo - objem}

Algoritmický jazyk

 jazyk – dorozumievací prostriedok

–

slovenský jazyk cca 110.000 slov

–

anglický jazyk 800.000 slov

 použitie ľudského jazyka je problematické

–

frazeologizmy, príslovia a porekadlá

–

synonymá

–

homonymá

–

tvary, pády, osoby

–

plynulý prirodzený vývoj pribúdanie a „vypúšťanie“ slov

 => potreba redukcie prirodzeného jazyka

Algoritmické jazyky

 niekoľko typov:
a) vývojové diagramy (postupnosť činností popisovaná

prostredníctvom grafických značiek a textu v nich),

b) štruktúrogramy (zhutnená obdoba vývojových diagramov, ktorá

však oproti vývojovým diagramom nie je definovaná normou),

c) obrázkové jazyky (často detské programovacie jazyky umožňujúce

programovať prostredníctvom spájania obrázkov),

d) rozhodovacie tabuľky (popisujú zložitejšie problémy pozostávajú

zo zoznamu podmienok, kombinácie podmienok, zoznamu činností

a kombinácie činností – pre našu prácu nie sú vhodné),

e) 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),

f) programovacie jazyky (formalizované algoritmické jazyky často

založené na redukcii slov anglického jazyka).

Skladba algoritmického jazyka

 operačná zložka:
 Príkazy: vety jazyka prikazujúce procesoru vykonať presne

stanovené činnosti. (vstupu, výstup a priradenie).

–

musia spracúvať 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

Skladba algoritmického jazyka

 riadiaca zložka:
 prostriedky pre riadenie postupnosti vykonávania

jednotlivých prvkov zložky operačnej

 vďaka nej je v každom kroku algoritmu jednoznačne

určená činnosť, ktorá sa má vykonať

–

sekvencia

–

vetvenie

–

cyklus

Algoritmické konštrukcie

 sekvencia postupnosť príkazov (príkaz je povel, ktorý

počítač alebo iné zariadenie pozná a dokáže vykonať)
vykonávanú v takom poradí, v akom sú jednotlivé časti
zapísané

 vetvenie poskytuje možnosť rozhodnúť sa podľa

pravdivosti skúmaného znaku. Skladá sa z podmienky
uvedenej za slovíčkom ak a z príkazov, ktoré sa vykonajú
v prípade kladného a záporného výsledku. Týmto dvom
častiam hovoríme vetvy.

 cyklus umožňuje ľubovoľnú činnosť opakovať. Pri

opakovaní je dôležité čo (telo cyklu) sa má opakovať
a dokedy (podmienka cyklu) sa má opakovať

Vývojové diagramy

 zápis prostredníctvom prirodzeného jazyka nie je

prehľadný

 pre začiatočníkov sú najvhodnejším riešením vývojové

diagramy

– postupný prechod na programovací jazyk

 okrem

sekvencie, vetvenia a cyklu sú potrebné aj

prostriedky na vstup a výstup údajov

Príkazy vstupu a výstupu

 Príkaz vstupu

p

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

 Príkaz výstupu

h

1, ... , 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 obvod 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.