Algoritmy Nezačaté

0. Kľúčové fakty

1. Algoritmus — Algoritmus je presný a konečný postup, ktorý krok po kroku vedie k vyriešeniu určitého problému alebo splneniu úlohy. Musí byť jednoznačný, aby ho dokázal vykonať ktokoľvek (alebo počítač) bez domýšľania. S algoritmami sa stretávame aj v bežnom živote — recept na koláč, návod na zloženie nábytku či postup pri riešení rovnice sú tiež algoritmy.

2. Vlastnosti algoritmu — Správny algoritmus musí byť konečný (po určitom počte krokov sa skončí), determinovaný (každý krok je jednoznačne určený), hromadný (rieši celú skupinu podobných úloh, nielen jeden konkrétny prípad) a rezultatívny (vždy dáva výsledok). Tieto vlastnosti odlišujú skutočný algoritmus od nejasného alebo nikdy nekončiaceho postupu. Ak algoritmus niektorú z nich nespĺňa, často zlyhá alebo „zacyklí sa" donekonečna.

3. Vstup, spracovanie a výstup — Väčšina algoritmov pracuje so vstupnými údajmi (vstup), tie nejako spracuje (výpočet, rozhodovanie) a vráti výsledok (výstup). Napríklad algoritmus na výpočet obvodu obdĺžnika dostane na vstupe dĺžku a šírku, spracuje ich vzorcom a vypíše obvod. Tento model „vstup → spracovanie → výstup" je základom takmer každého programu.

4. Postupnosť (sekvencia) — Postupnosť je najjednoduchšia štruktúra, kde sa príkazy vykonávajú jeden za druhým v presnom poradí, zhora nadol. Poradie krokov je dôležité — ak ich zameníme, výsledok môže byť nesprávny (napr. najprv musíme naliať vodu, až potom variť). Sekvencia tvorí „kostru" každého algoritmu, do ktorej sa vkladajú zložitejšie štruktúry.

5. Vetvenie (rozhodovanie) — Vetvenie umožňuje algoritmu vybrať si medzi rôznymi cestami podľa toho, či je splnená nejaká podmienka. Zapisuje sa slovami „ak – potom – inak" (v programovaní if – else) a vždy sa vyhodnocuje, či je podmienka pravdivá alebo nepravdivá. Vďaka vetveniu vie program reagovať na rôzne situácie — napríklad rozhodnúť, či je číslo párne alebo nepárne.

6. Cyklus (opakovanie) — Cyklus dovoľuje opakovať tú istú skupinu príkazov viackrát, čím sa algoritmus skráti a zjednoduší. Rozlišujeme cyklus so známym počtom opakovaní (napr. „opakuj 10-krát") a cyklus s podmienkou (opakuj, kým platí podmienka). Cyklus musí mať vždy spôsob, ako skončiť — inak vznikne nekonečný cyklus a program „zamrzne".

7. Podmienka — Podmienka je tvrdenie, ktoré môže byť buď pravdivé, alebo nepravdivé (napr. „číslo je väčšie ako 5"). Riadi vetvenie aj cykly — podľa jej vyhodnotenia sa algoritmus rozhodne, ktorou cestou pôjde alebo či bude pokračovať v opakovaní. Pri tvorbe podmienok sa používajú porovnávacie operátory ako väčší (>), menší (<), rovná sa (=) a logické spojky a, alebo, nie.

8. Vývojový diagram — Vývojový diagram je grafický spôsob zápisu algoritmu pomocou dohodnutých značiek: ovál označuje začiatok a koniec, obdĺžnik príkaz (spracovanie), kosoštvorec (romboid) rozhodovanie a šípky určujú smer postupu. Diagram robí algoritmus prehľadným a ľahko sa v ňom hľadajú chyby ešte pred programovaním. Je to medzistupeň medzi nápadom v hlave a hotovým programom.

9. Spôsoby zápisu algoritmu — Algoritmus môžeme zapísať slovne (vetami), pomocou vývojového diagramu, v pseudokóde (zjednodušený programovací jazyk blízky bežnej reči) alebo priamo v programovacom jazyku. Pseudokód je užitočný, lebo opisuje logiku bez prísnych pravidiel konkrétneho jazyka, takže sa naň sústredíme na samotné riešenie. Každý zápis opisuje ten istý postup, len inou formou.

10. Premenná — Premenná je pomenované miesto v pamäti počítača, do ktorého si algoritmus ukladá hodnotu (číslo, text), pričom túto hodnotu môže počas behu meniť. Predstaviť si ju možno ako pomenovanú škatuľku, do ktorej vkladáme a vyberáme údaje. Premenné sú nevyhnutné napríklad pri počítaní (sčítavanie do premennej „súčet") alebo pri zapamätaní vstupu od používateľa.

11. Overenie správnosti (testovanie) — Po zostavení algoritmu treba overiť, či naozaj funguje správne — najčastejšie ho „ručne prejdeme" na konkrétnych vstupoch a sledujeme, aké hodnoty vychádzajú. Testujeme aj hraničné a netypické prípady (napr. nulu, záporné číslo, prázdny vstup), kde sa chyby objavujú najčastejšie. Chyba v algoritme sa nazýva bug a jej hľadanie a opravovanie debugovanie (ladenie).

12. Ladenie a efektívnosť — Ten istý problém sa dá vyriešiť viacerými algoritmami, ktoré sa líšia rýchlosťou a počtom krokov — niektoré sú efektívnejšie ako iné. Dobrý programátor hľadá riešenie, ktoré je nielen správne, ale aj jednoduché a rýchle, najmä pri veľkom množstve údajov. Schopnosť rozložiť zložitý problém na menšie kroky a zostaviť preň algoritmus sa nazýva algoritmické myslenie a je základom celej informatiky.

1. Poučka

Algoritmus je presný, konečný postup, ktorý krok po kroku rieši nejaký problém alebo úlohu. Skladá sa z troch základných stavebných prvkov: - postupnosť — príkazy idú jeden za druhým v určenom poradí, - vetvenie (rozhodovanie) — podľa splnenia podmienky sa vykoná jedna alebo druhá vetva, - cyklus (opakovanie) — časť príkazov sa zopakuje viackrát.

Každý algoritmus má vstup, spracovanie a výstup a musí byť správny (dáva očakávaný výsledok) a konečný (raz skončí).

2. Vysvetlenie

Predstav si algoritmus ako presný recept. Aby fungoval pre každého, kto ho prečíta, musí byť jasný a jednoznačný.

Postupuj takto: 1. Pochop problém — čo je vstup (čo mám k dispozícii) a čo má byť výstup (čo chcem dostať). 2. Rozlož ho na kroky — napíš jednoduché príkazy v správnom poradí (postupnosť). 3. Pridaj rozhodovanie — keď sa postup vetví, použiješ ak – tak – inak (vetvenie). Napr. „Ak prší, vezmi dáždnik, inak vezmi okuliare." 4. Pridaj opakovanie — keď sa niečo robí viackrát, použiješ cyklus, napr. „Opakuj 5-krát: urob drep." 5. Zapíš algoritmus — slovne, vývojovým diagramom alebo pseudokódom (skrátený zápis blízky programu). 6. Over správnosť — prejdeš algoritmus krok po kroku na konkrétnom príklade (tzv. trasovanie) a skontroluješ výsledok.

3. Príklady a prečo je to dôležité

Príklad 1 — krokovanie (trasovanie) cyklu: Čo vypíše algoritmus? Nastav s ← 0. Pre i od 1 po 4 opakuj: s ← s + i. Vypíš s.
Vstup: žiadny, začíname s hodnotou s = 0.
Krok i = 1: s = 0 + 1 = 1
Krok i = 2: s = 1 + 2 = 3
Krok i = 3: s = 3 + 3 = 6
Krok i = 4: s = 6 + 4 = 10
Cyklus skončil (i prešlo hodnoty 1 až 4), algoritmus vypíše s → 10

Príklad 2 — vetvenie ak – inak: Algoritmus: Načítaj číslo n. Ak je zvyšok po delení n číslom 2 rovný 0, vypíš „párne", inak vypíš „nepárne". Čo vypíše pre n = 7?
Vstup: n = 7.
Podmienka: zvyšok 7 : 2 je 1 (7 = 3 · 2 + 1), takže zvyšok nie je 0.
Podmienka je nepravdivá, vykoná sa vetva „inak".
Výstup → nepárne

Príklad 3 — cyklus + vetvenie (najväčšie číslo): Nájdi najväčšie číslo v zozname 4, 9, 2, 7 algoritmom: Zapamätaj si prvé číslo ako max. Pre každé ďalšie číslo: ak je väčšie ako max, ulož ho do max. Na konci vypíš max.
Začiatok: max = 4.
Číslo 9: 9 > 4 platí, max sa zmení na 9.
Číslo 2: 2 > 9 neplatí, max ostáva 9.
Číslo 7: 7 > 9 neplatí, max ostáva 9.
Koniec zoznamu, výstup → 9

Príklad 4 — vývojový diagram slovne: Opíš vývojový diagram pre algoritmus: Načítaj vek. Ak je vek aspoň 15, vypíš „môžeš ísť", inak vypíš „nemôžeš ísť".
Ovál „Začiatok".
Rovnobežník alebo obdĺžnik „Načítaj vek" (vstup).
Kosoštvorec s podmienkou „vek ≥ 15?" – vychádzajú z neho dve šípky: áno a nie.
Na vetve áno obdĺžnik „Vypíš môžeš ísť", na vetve nie obdĺžnik „Vypíš nemôžeš ísť".
Obe vetvy sa spoja šípkami do oválu „Koniec".
Rozhodovanie je teda len v jednej značke → jeden kosoštvorec s dvoma vetvami áno/nie medzi začiatkom a koncom

Príklad 5 — hľadanie chyby (nekonečný cyklus): Prečo tento algoritmus nikdy neskončí? Nastav k ← 10. Opakuj, kým k > 0: vypíš k.
Podmienka cyklu je k > 0, na začiatku 10 > 0 platí.
V tele cyklu sa k nikdy nemení, takže podmienka platí stále.
Oprava: do tela cyklu pridáme príkaz k ← k − 1, potom sa k postupne zmenší až na 0 a cyklus skončí.
Chyba → v tele cyklu chýba zmena premennej k (oprava k ← k − 1)

Príklad 6 — z bežného života (postupnosť + vetvenie): Zostav algoritmus na ranné odchádzanie do školy, ktorý sa rozhoduje podľa počasia.
Postupnosť: vstaň, umy sa, naraňajkuj sa, obleč sa.
Vetvenie: ak prší, zober dáždnik, inak zober slnečné okuliare.
Postupnosť pokračuje: zober tašku, zamkni dvere, choď do školy.
Algoritmus má jasný začiatok, koniec a jedno rozhodnutie → postupnosť krokov s jedným vetvením „ak prší – inak"

Prečo je to dôležité:
- Algoritmické myslenie ťa naučí rozložiť veľký problém na malé zvládnuteľné kroky — to využiješ v každom predmete aj v živote.
- Je to základ programovania — počítač, telefón, hra aj umelá inteligencia robia presne to, čo im algoritmus prikáže.
- Učí ťa presnosti a logike — keď je algoritmus zle zapísaný, výsledok je chybný. Hľadanie chýb (ladenie) je dôležitá zručnosť.

Precvič si

1. Ktoré tri základné stavebné prvky má algoritmus?
2. Čo vypíše algoritmus: Nastav a ← 3. Nastav a ← a · 2. Nastav a ← a + 4. Vypíš a.
3. Algoritmus: Ak je teplota menšia ako 0, vypíš „mrzne", inak vypíš „nemrzne". Čo vypíše pre teplotu 0?
4. Koľkokrát sa vykoná telo cyklu Pre i od 2 po 6 opakuj: vypíš i?
5. Trasuj: Nastav p ← 1. Opakuj 4-krát: p ← p · 2. Vypíš p.
6. Cyklus Nastav x ← 20. Opakuj, kým x > 5: x ← x − 4. skončí. Akú hodnotu má x po skončení?