16. diel - Na čo sú algoritmy?
V minulej lekcii, K čomu sú algoritmy - Príklady triedenia vo VB.NET , sme si ukázali triedenie prvkov pomocou algoritmov Selection sort, Bubble sort a Insertion sort.
Základnú konštrukciu jazyka Visual Basic .NET máme takmer za sebou. Kým ich ale úplne opustíme, musíme vedieť, že o efektívnom využívaní týchto konštrukcií existuje celá ďalšia veda. Našťastie nám o nej stačí len vedieť a občas do nej nahliadnuť, keď chceme niečo špeciálne. Tou vedou je algoritmizácia a dnes si ju predstavíme.
Čo sú to algoritmy?
V tej najjednoduchšej definícii je algoritmus postup pre riešenie
konkrétneho problému. V podstate všetko, čo nie je len o zavolaní
nejakej predpripravenej funkcie jazyka, musíme krok za krokom vymyslieť a
zapísať ako postupnosť príkazov. Spomeňme si napr. na nášprogram,
ktorý počítal korene kvadratickej rovnice. Bez znalosti presného
postupu, ako sa kvadratická rovnica rieši, by sme si asi neškrtli. Tento
postup sme mali tentokrát priamo v zadaní a našou jedinou úlohou bolo
previesť ho do kódu. V praxi nám ale klient samozrejme nepovie, čo budeme v
jeho aplikácii riešiť za problémy a už vôbec nie, ako ich implementovať
Problémy s neznalosťou algoritmov
Algoritmy používame v reálnych komerčných aplikáciách najmä na radenie a vyhľadávanie. Problémy s neznalosťou algoritmov sú hneď dva:
- buď nebudeme schopní určité úlohy vyriešiť,
- alebo ich vyriešime zle (je síce fajn niečo vymyslieť sám, ale je potrebné riešenie minimálne potom porovnať s reálnym svetom).
Pre množstvo problémov našťastie už existuje ideálny
algoritmus, ktorý vymyslel niekto pred nami. Ľudia nad riešením
často strávili časť života a dostali zaň vedeckú cenu. Teda
pravdepodobnosť, že by sme vymysleli lepší, alebo že lepší algoritmus pre
daný problém vôbec existuje, je veľmi nízka
Kurzy algoritmov na ITnetwork
Algoritmy teda budeme brať ako kuchárku s receptami. Stačí nám nazrieť do miestnej sekcie Algoritmy na konkrétne miesto v prípade, keď potrebujeme konkrétny algoritmus. Napr. algoritmus riešenie kvadratickej rovnice nájdeme v kurze Matematické algoritmy. Algoritmy sa najčastejšie týkajú radenia a vyhľadávania prvkov, ale samozrejme môže ísť aj napr. o neurálny algoritmus na rozpoznanie objektov v obrázku. Takúto vec si však už nebudeme písať na kolene, ale stiahneme si pre ňu knižnicu.
Čo algoritmy riešia?
Najskôr sa pozrime na dva hlavné problémy programov.
Pamäť
Hoci by sa zdalo, že slovné spojenie nedostatok pamäti je fráza z učených kníh na konci minulého storočia, stretávame sa s tým všetci. Zvlášť, ak budeme písať aplikácie pre Android. Pokiaľ naša aplikácia bude zaberať 1GB, nikto si ju nestiahne. Navyše tu funguje zaujímavý zákon, keď sa zväčší pamäť, zväčší sa aj veľkosť programov as nedostatkom pamäte sa musíme stretávať nanovo.
Čas
Ak je problém s pamäťou znepokojujúci, čas je úplne hrôzostrašný. Užívatelia aplikácií majú príšernú vlastnosť, nedočkavosť. Keď napríklad stlačia tlačidlo, očakávajú, že sa niečo stane hneď. Nemažme si med okolo pusy, aj my sme takí používatelia. Nechceme čakať, kým náš skvelý program vyhodí výsledok. Nemusí to byť ani zložité výpočty. Pokiaľ programujeme hru, očakávame, že hneď po stlačení klávesy sa panáčik pohne. Očakávame, že po otvorení okna sa nám zobrazí zoznam užívateľov zoradený podľa mena.
Konkrétne príklady pre algoritmizáciu
Ukážeme si, že všetky ostatné problémy sa priamo alebo nepriamo dotýkajú týchto dvoch základných kameňov úrazu.
Interakcia so svetom
Pokiaľ poznáte hru Kingdom Come Deliverance tak viete, že sa môže pochváliť svetom, kde je možné interagovať s každou postavou as mnohými objektmi. Takáto možnosť so sebou prináša rôzne problémy, ako je napríklad pamäťový nárok. Keby sme každú postavu a každý domček poctivo vytvorili, svet s veľkosťou mesta s 300 ľuďmi by zaberal obrovské množstvo pamäte, ktorú by nakoniec hráč asociál vôbec nevyužil.
Príbeh zo života
Predstavme si, že pre zákazníka vytvoríme e-shop na predaj jedného kusu
oblečenia, konkrétne kožených búnd. Neskôr ale zistíme, že náš program
má fungovať aj v angličtine. Dáme teda jednoduchú podmienku
If-Else pre jazyky a prepíšeme stránku do angličtiny. Potom
príde požiadavka z Nemecka, že by bolo dobré, keby e-shop mohol bežať aj v
nemeckom jazyku. Požiadavku vyhovieme a dopíšeme aj nemeckú verziu.
Potom si zákazník vymyslí, že by sa mohol pridať aj bazár kožených búnd. Zrejme na to stránka nebola pripravená, takže vytvoríme novú stránku s odkazom na pôvodnú, ktorá je zase trojjazyčná. Tentoraz si už zvolíme efektívny návrh, keby firma prenikla napríklad do Francúzska. Bazár bude formou aukcií, zadáme čas a čakáme, či ľudia môžu prihadzovať. Ukázalo sa, že kolegovia z Ruska môžu prihadzovať aj po tom, čo náš čas ubehol a kolegovia z Anglicka naopak prišli o hodinu. Program teda ľahko poupravíme.
E-shop sa rozrástol a má toľko búnd, že sa v ňom nakupujúci ťažko orientujú. Náš zákazník sa preto rozhodne, že bundy rozdelia do kategórií a že nakupujúci bude môcť vyhľadávať podľa ceny a mena. Nájdeme si teda návod, ako niekto naprogramoval vyhľadávanie podľa ceny aj podľa mena a implementujeme ho do e-shopu.
Následne zákazník príde s tým, že by bolo skvelé, keby nakupujúci mohol pridať kritériá a hľadať napríklad len zo svojich troch obľúbených značiek av určitom cenovom rozmedzí. Opäť si nájdeme riešenie pre viacnásobné kľúče pri vyhľadávaní a niekoľkofázovom triedení a aplikujeme ho do e-shopu. V tom zavolá zákazník, že náš program nefunguje. Kód, ktorý sme stiahli z internetu, nefunguje pre veľké údaje. Naša niekoľko-jazyková stránka trpí tým, že tam občas ukáže iný jazyk a my nemáme inú možnosť, ako vyriešiť všetko, čo za nás "pokazil" niekto iný.
Čo s tým?
Tu sme sa dotkli hneď dvoch tém. Prvá téma, ktorú sme už zahryzli, je otázka správnych praktík v programovaní. Teda toho, čo by sme mali dodržiavať, aby šiel vývoj softvéru hladko. Druhá téma je však schopnosť algoritmicky myslieť. Ako konkrétne vyriešiť problém, napríklad triedenie. Či najprv triediť, potom až osekať, alebo naopak. A sme pri otázke času. Pokiaľ najskôr osekáme, potom napríklad z desaťtisícov položiek triedime len stovky. A tá rýchlosť je potom jasná. Navyše, pokiaľ len tak preberáme kód niekoho iného, nezostáva nám než veriť, že dotyčný vie, čo jeho kód robí. Síce si môžeme kód vyskúšať, ale čo ak jeho algoritmus funguje iba pre malé dáta?
Je veľa problémov, ktoré nikto neriešil a mali by sme vedieť, ako pri ich riešení postupovať. Na to slúži naša sekcia pre výučbu algoritmov.
V nasledujúcom kvíze, Kvíz - Základná konštrukcia VB.NET, si vyskúšame nadobudnuté skúsenosti z kurzu.
