informatika.bilíčka.sk

Algoritmus

Algoritmus je postup, ktorého realizáciou získame zo zadaných vstupných údajov po konečnom počte činností v konečnom čase správny výsledok alebo vyriešime problém. 🤓

Inak povedané, algoritmus je postup, ktorý má nasledovné vlastnosti:

Vlastnosti algoritmov

  1. Elementárnosť
    • algoritmus je zložený zo základných (elementárnych) krokov, kroky musia byť elementárne (jednoduché, základné) pre toho, kto bude algoritmus vykonávať
    • napríklad by sme mohli vytvárať algoritmus pre robotický vysávač, ktorý vie vykonať len dva príkazy: [posuň sa o centimeter vpred] a [otoč sa o stupeň vpravo], zrejme by sme vhodným opakovaním a kombinovaním týchto príkazov dokázali pre robota napísať algoritmus, ktorého vykonaním by prešiel (povysával) celú miestnosť
    • programovacie jazyky tiež pozostávajú z obmedzeného počtu príkazov, ktoré vie vykonať počítač, veľa z nich sa naučíme neskôr v tomto roku :)
  2. Determinovanosť
    • pri vykonávaní algoritmu musí byť vždy jasné, ktorý krok nasleduje alebo či už sme na konci algoritmu
    • v každej situácii je úplne zrejmé čo sa má vykonať a ako má algoritmus pokračovať
    • predstavte si autonómne auto, ktoré má prejsť cez svetelnú križovatku, v kóde musí byť uvedené, čo presne nastane ak bude na semafore svietiť každé jedno z troch svetiel zelená-oranžová-červená, ak by sme jednu možnosť zabudli, čo by auto robilo?
  3. Konečnosť
    • algoritmus skončí vždy po vykonaní konečného počtu krokov a v konečnom (reálnom) čase
    • Majme takýto postup: Pomyslite si číslo od 1 do 10. Pripočítavajte jednotku až pokým vám nevyjde výsledok rovný -3.
    • Človek si vie uvedomiť že takýto postup nikdy nepovedie k výsledku, no počítač nie, a tak by postupne k vymyslenému číslu pripočítaval, pokiaľ má zdroj energie. Je našou programátorskou zodpovednosťou zabezpečiť, aby sa takéto nezmyselné veci počítaču nediali.
    • na zamyslenie: niektoré programy v počítači majú pracovať donekonečna, napríklad OS
  4. Rezultatívnosť
    • algoritmus dáva pre rovnaké vstupné údaje vždy rovnaké výsledky
    • príklad: Na matematike sa všetci učia tie isté algoritmy – postupy rôznych výpočtov. Napriek tomu nemajú v písomke všetci žiaci rovnaké výsledky. Prečo? - Chyba nie je v algoritmoch, ale v ľuďoch. Buď sa algoritmy nenaučili správne, alebo použili nesprávne algoritmy – určené na riešenie iného typu úloh.
  5. Hromadnosť
    • algoritmy navrhujeme tak, aby pokiaľ možno riešili veľký počet príbuzných problémov a nie len jeden špecifický
    • Predstavte si, že je vašou programátorskou úlohou vytvoriť losovací systém, ktorý sa použije na futbalovom turnaji - určí, kto bude hrať proti komu. Na turnaji bude 20 tímov. Aj tak sa oplatí vyriešiť problém všeobecnejšie - vytvoriť program, ktorý rozlosuje ľubovoľný počet tímov, bude tak použiteľný aj na iných turnajoch a aj v prípade, že sa napríklad niektorý tím nedostaví...
  6. Efektívnosť
    • Táto vlastnosť sa často považuje za doplnkovú, aj neefektívny algoritmus je stále algoritmus. 😀
    • Efektivita spočíva v tom, že algoritmus umožní získať výsledok v čo najkratšom čase a s využitím čo najmenšieho počtu prostriedkov – finančných, technických, ľudských. Často sa najskôr vytvorí akýkoľvek funkčný algoritmus, ktorý sa v prípade potreby vylepšuje – ak máme na to dostatok prostriedkov. Požiadavka získať výsledok čo najrýchlejšie je často v rozpore s požiadavkou minimalizovať použité prostriedky.
    • Hlavné dva prostriedky, ktorými môže program šetriť sú čas a priestor (pamäť). Rýchly program je samozrejme lepší, niekedy máme dokonca také pomalé programy, že sa ani neoplatí čakať na ich výsledky - ak by napríklad hrozila kolízia planét, ktorých rýchlosť a vzdialenosť naznačujú, že k nárazu príde do 7 dní, nemá zmysel počítať presné dráhy letu neefektívnym algoritmom, ktorému by výpočet trval mesiac. Pamäť je v počítači samozrejme obmedzená - program je závislý hlavne na operačnej pamäti RAM, tej máme v počítačoch rádovo desiatky gigabajtov. V operačnej pamäti sú dáta, s ktorými program práve pracuje, ak by mal napríklad program spracúvať dáta obyvateľov celého Slovenska, je možné, že by niektoré operácie nemohol robiť naraz so všetkými záznamami (proste by sa mu nezmestili do pamäte). Dáta by ale mohol spracovávať dávkovo, načítať si len 10000 záznamov, vypočítať čo treba, potom načítať ďalších 10000... a toto už je postup, ktorý musí zabezpečiť šikovný programátor.

Pojmy