Lekce 15 - K čemu jsou algoritmy?

V minulé lekci, Matematické funkce ve VB.NET a knihovna Math, jsme si představili matematické funkce.

Základní konstrukce jazyka Visual Basic .NET máme téměř za sebou. Než je ale zcela opustíme, musíme vědět, že o efektivním využívání těchto konstrukcí existuje celá další věda. Naštěstí nám o ní stačí jen vědět a občas do ní nahlédnout, když chceme něco speciálního. Tou vědou je algoritmizace a dnes si ji představíme.

Co jsou to algoritmy?

V té nejjednodušší definici je algoritmus postup pro řešení konkrétního problému. V podstatě vše, co není jen o zavolání nějaké předpřipravené funkce jazyka, musíme krok za krokem vymyslet a zapsat jako posloupnost příkazů. Vzpomeňme si např. na náš program, který počítal kořeny kvadratické rovnice . Bez znalosti přesného postupu, jak se kvadratická rovnice řeší, bychom si asi neškrtli. Tento postup jsme měli protentokrát přímo v zadání a naší jedinou úlohou bylo převést jej do kódu. V praxi nám ale klient samozřejmě neřekne, co budeme v jeho aplikaci řešit za problémy a už vůbec ne, jak je implementovat

Problémy s neznalostí algoritmů

Algoritmy používáme v reálných komerčních aplikacích zejména pro řazení a vyhledávání. Problémy s neznalostí algoritmů jsou hned dva:

• buď nebudeme schopní určité úlohy vyřešit,
• nebo je vyřešíme špatně (je sice fajn něco vymyslet sám, ale je potřeba řešení minimálně pak porovnat s reálným světem).

Špatné řešení se pak projeví nejčastěji tím, že naše aplikace vyhledávající cestu v grafu bude potřebovat 5 minut na to, aby zjistila, jak se jede z Prahy do Brna. Náš algoritmus totiž nebude efektivní.

Pro spoustu problémů naštěstí již existuje ideální algoritmus, který vymyslel někdo před námi. Lidé nad řešením často strávili část života a dostali za něj vědeckou cenu. Tedy pravděpodobnost, že bychom vymysleli lepší, nebo že lepší algoritmus pro daný problém vůbec existuje, je velmi nízká

Kurzy algoritmů na ITnetwork

Algoritmy tedy budeme brát jako kuchařku s recepty. Stačí nám nakouknout do místní sekce Algoritmy na konkrétní místo v případě, kdy potřebujeme konkrétní algoritmus. Např. algoritmus řešení kvadratické rovnice nalezneme v kurzu Matematické algoritmy . Algoritmy se nejčastěji týkají řazení a vyhledávání prvků, ale samozřejmě se může jednat i např. o neurální algoritmus k rozpoznání objektů v obrázku . Takovouto věc si ovšem již nebudeme psát na koleni, ale stáhneme si pro ni knihovnu.

Co algoritmy řeší?

Nejdříve se podívejme na dva hlavní problémy programů.

Paměť

Ač by se zdálo, že slovní spojení nedostatek paměti je fráze z učených knih na konci minulého století, potýkáme se s tím všichni. Zvlášť, pokud budeme psát aplikace pro Android. Pokud naše aplikace bude zabírat 1GB, nikdo si ji nestáhne. Navíc zde funguje zajímavý zákon, když se zvětší paměť, zvětší se i velikost programů a s nedostatkem paměti se musíme potýkat nanovo.

Čas

Jestli je problém s pamětí znepokojující, čas je naprosto hrůzostrašný. Uživatelé aplikací mají příšernou vlastnost, nedočkavost. Když například stisknou tlačítko, očekávají, že se něco stane hned. Nemažme si med kolem pusy, i my jsme takoví uživatelé. Nechceme čekat, až náš skvělý program vyhodí výsledek. Nemusí to být ani složité výpočty. Pokud programujeme hru, očekáváme, že hned po stisknutí klávesy se panáček pohne. Očekáváme, že po otevření okna se nám zobrazí seznam uživatelů seřazený podle jména.

Konkrétní příklady pro algoritmizaci

Ukážeme si, že všechny ostatní problémy se přímo či nepřímo dotýkají těchto dvou základních kamenů úrazu.

Interakce se světem

Pokud znáte hru Kingdom Come Deliverance tak víte, že se může pochlubit světem, kde je možné interagovat s každou postavou a s mnoha objekty. Taková možnost s sebou přináší různé problémy, jako je například paměťový nárok. Kdybychom každou postavu a každý domek poctivě vytvořili, svět o velikosti města s 300 lidmi by zabíral obrovské množství paměti, kterou by nakonec hráč asociál vůbec nevyužil.

Příběh ze života

Představme si, že pro zákazníka vytvoříme e-shop pro prodej jednoho kusu oblečení, konkrétně kožených bund. Později ale zjistíme, že náš program má fungovat i v angličtině. Dáme tedy jednoduchou podmínku If-Else pro jazyky a přepíšeme stránku do angličtiny. Pak přijde požadavek z Německa, že by bylo dobré, kdyby e-shop mohl běžet i v německém jazyce. Požadavku vyhovíme a dopíšeme i německou verzi.

Poté si zákazník vymyslí, že by se mohl přidat i bazar kožených bund. Nejspíš na to stránka nebyla připravena, takže vytvoříme novou stránku s odkazem na původní, která je zase trojjazyčná. Tentokrát si už zvolíme efektivní návrh, kdyby firma pronikla například do Francie. Bazar bude formou aukcí, zadáme čas a čekáme, zda lidé mohou přihazovat. Ukázalo se, že kolegové z Ruska mohou přihazovat i po tom, co náš čas uběhl a kolegové z Anglie naopak přišli o hodinu. Program tedy lehce poupravíme.

E-shop se rozrostl a má tolik bund, že se v něm nakupující těžko orientují. Náš zákazník se proto rozhodne, že bundy rozdělí do kategorií a že nakupující bude moci vyhledávat podle ceny a jména. Najdeme si tedy návod, jak někdo naprogramoval vyhledávání podle ceny i podle jména a implementujeme ho do e-shopu.

Následně zákazník přijde s tím, že by bylo skvělé, kdyby nakupující mohl přidat kritéria a hledat třeba jen ze svých tří oblíbených značek a v určitém cenovém rozmezí. Opět si najdeme řešení pro vícenásobné klíče při vyhledávání a několikafázové třídění a aplikujeme ho do e-shopu. V tom zavolá zákazník, že náš program nefunguje. Kód, který jsme stáhli z internetu, nefunguje pro velká data. Naše několika-jazyková stránka trpí tím, že tam občas ukáže jiný jazyk a my nemáme jinou možnost, než vyřešit vše, co za nás "pokazil" někdo jiný.

Co s tím?

Zde jsme se dotkli hned dvou témat. První téma, které jsme již nakousli, je otázka správných praktik v programování. Tedy toho, co bychom měli dodržovat, aby šel vývoj softwaru hladce. Druhé téma je však schopnost algoritmicky myslet. Jak konkrétně vyřešit problém, například třídění. Jestli nejprve třídit, pak až osekat, či naopak. A jsme u otázky času. Pokud nejdříve osekáme, pak třeba z desetitisíců položek třídíme jen stovky. A ta rychlost je pak jasná. Navíc, pokud jen tak přejímáme kód někoho jiného, nezbývá nám než věřit, že dotyčný ví, co jeho kód dělá. Sice si můžeme kód vyzkoušet, ale co když jeho algoritmus funguje jen pro malá data?

Je spoustu problémů, které nikdo neřešil a měli bychom vědět, jak při jejich řešení postupovat. K tomu slouží naše sekce pro výuku algoritmů.

V další lekci, K čemu jsou algoritmy - Příklady třídění ve VB.NET, si ukážeme třídění prvků pomocí algoritmů Selection sort, Bubble sort a Insertion sort. Výsledky třídění si pak porovnáme.