Ako začať s algoritmami

Autor: Adrián Lachata | 31.7.2009 o 15:38 | (upravené 28.8.2010 o 14:37) Karma článku: 7,60 | Prečítané:  3040x

Potešilo ma, že začínajúci programátori sa už neobzerajú iba po konkrétnych programovacích jazykoch ale aj po algoritmoch ako takých. V tomto článku trochu formálnejšie predstavím pojem algoritmu, poukážem na, podľa môjho názoru, dobré knihy, pár webových stránok i skúsim navnadiť na pár možných druhov ich tréningu. Cieľom tohto článku je ukázať niekoľko možnosti človeku, ktorý už ovláda nejaký programovací jazyk a chce sa dozvedieť niečo o algoritmoch.

Trochu formálny úvod. Algoritmom rozumieme návod na systematický matematický postup, ktorý v konečnom počte krokov dáva odpoveď na určitú otázku. Trochu presnejšie. Návod na postup, ktorý spĺňa tieto základné vlastnosti: diskrétnosť (algoritmus sa skladá z krokov, napríklad inštrukcií procesora), determinovanosť (nasledujúci krok je vždy jasný, neexistuje náhoda), hromadnosť (použiteľný pre obrovské množstvo úloh) a konečnosť (algoritmus vždy skončí). Možno to na prvý pohľad tak nevyzerá, ale práve s poslednou vlastnosťou sú najväčšie problémy. Aj v dnešnej dobe je neúnavne skúmaná mnohými matematikmi a informatikmi.

Algoritmus ako pojem vznikol ako polatinčenie mena arabského matematika Abú Abdalláh Muhammad ibn Músá al-Chorezmí al-Mádzúsí a jeho pojednania Kniha o sčítaní a odčítaní podľa indického počtu. Síce sa to pojednanie v originály nezachovalo ale knižnica Cambridgskej univerzity vlastný preklad z polovice 13. storočia, ktorý začína slovami „Dixit Algorizmi ...“. V druhej polovici 14. storočia napísal Nicole Oresme pojednanie s názvom „Algorismus proportionum“, v ktorej sa slovo už slovo algoritmus používa na označenie určitého postupu. A tak sa z mena al-Chorezmí stal algoritmus, ktorý sa ako pojem usadil. Koniec formálneho úvodu, pri ktorom boli použitá literatúra Lev Bukovský, Teória algoritmov, 2004. Ešte dodám, že prakticky môžeme algoritmus definovať ako program napísaný v nejakom programovacom jazyku. V teórii je kľúčový pojem pre model algoritmu Turingov stroj.

Nahliadnime sa do praktického sveta. Počas základnej školy by som ešte neodporúčal zaoberať sa učením nejakých algoritmov. Skôr by som kládol dôraz na logické hry, matematické súťaže, a čo sa týka informatiky, hrať sa s Karol, Imagine, Baltík. Určite by neboli na škodu aj základy programovacieho jazyka Pascal, v ktorom alebo jemu podobnom (pseudo)jazyku sú písané základne netriviálne algoritmy. V knihách o algoritmoch sa Pascal vôbec nerozoberá. Takmer vždy sa predpokladá jeho znalosť. Teda rozumieť jeho jednoduchým vstavaným dátovým typom  (integer, real...), zloženým (polia -array, reťazce – string, záznam – record), podmienkam, cyklom, procedúram/funkciám a smerníkom.

Najjednoduchšia a pre začiatočníkov najvhodnejšia kniha, s akou som sa stretol, je Pavel Töpfer, Algoritmy a programovacie techniky. Síce všetky potrebné matematické pojmy (množiny, postupnosti, stromy a grafy, logaritmus) si definuje a vysvetlí v úvode, ale vzhľadom na to, že po úvode nasleduje pojednanie o zložitosti algoritmu, vysvetlenie výhod a nevýhod základných dátových štruktúr by som už túto knihu odporučil pre stredné školy, hoci je veľmi pekne myšlienkovo-intuitívne písaná, ale sa už ide seriózne po algoritmoch. Každý algoritmus je priamo v knihe zapísaný v Pascale. Na úvod vrelo odporúčam. Ešte mnoho ľudí špekuluje nad Piotr Wróblewski, Algoritmy Datové struktury a programovací techniky. Mal som sú v rukách, no videla sa mi až taká rozťahaná, že tam dokopy nič nie je. Súhlasia s tým aj všetci moji známi, ktorí ju majú doma. Neodporúčam kupovať.

Ďalej mám doma Robert Sedgewick, Algoritmy v C. Veľmi dobrá kniha, ktorá už ale predpokladá zbehlosť v počtoch, programovaní v C a určitú dávku abstrakcie. Pokrýva veľmi veľkú časť základných všeobecných algoritmov, ponúka dôkazy správnosti, no už sa podobá vysokoškolským učebným textom. Vynikajúca kniha, odporúčam, ale až po zvládnutí knihy Algoritmy a programovacie techniky. Pokiaľ Vám C nie je po vôli, alebo Vás nezaujíma konkrétná implementáciu kódu, stačí Vám všeobecný ale presný postup tak vrelo odporúčam Introduction to Algorithms. Kniha je písaná logicky veľmi pekne. Pokiaľ Vám nerobí problém angličtina, prípadne sa ju učíte, tak je to naozaj krásna kniha. Voľne prístupná kniha odporúčaná kolegami je Algorithms.

Myslím, že knižiek som vymenoval dosť, teraz sa pozrime na to, ako nám môže pomôcť internet. Pre stredoškolákov je primárne určený KSP (Korešpondenčný seminár z programovania). Organizátori sú poväčšine študenti matfyzu, ktorí to robia pre radosť, aj keď to je často krát nudné a veľmi únavné. Ale majú radi programovanie, algoritmy, baví ich šíriť vedomosti ďalej a venovať sa stredoškolákom tak, ako kedysi iní organizátori venovali zdarma svoj čas im. V KSP sú zverejnené série úloh. Keď úlohu vyriešite, treba odvodniť, prečo by malo Vaše riešenie fungovať pre všetky prípustné vstupy. Správne riešenie pre všetky vstupy dostane viac ako polovicu bodov ale nezanedbateľná je aj rýchlosť Vášho algoritmu. Ráta sa s uvedením časovej a pamäťovej zložitosti Vášho algoritmu. Technicky to funguje tak, že pošlete v danom termíne úlohy z danej série s Vašími riešeniami. Obratom Vám prídu okomentované Vaše riešenia, ďalšia séria úloh a rozobraté vzorové riešenia.  Úlohy sú často na použitie nejakého algoritmu. Pokiaľ algoritmy viete, zvolíte najvhodnejšie a vyskúšate ich prakticky implementovať. Ak neviete, môžete skúsiť vymyslieť vlastný algoritmus.

Za pozornosť určite stojí Kuchařky pražského KSP. Je to súhrn tých najzákladnejších algoritmov. Vynikajúca vec bratislavského KSP je tvz. Programtórská liaheň, kde sa riešia úlohy s rastúcou obtiažnosťou. Riešenie spočíva v poslaní zdrojového kódu, ktorého správnosť je vyhodnotená takmer okamžite. Po úšpesne prijatom riešení sa Vám ukáže vzorové riešenie s popisom, máte možnosť nahliadnúť úspešné riešenia spoluriešiteľov a objavia sa Vám nové zaujímavé úlohy.

Zo slovenských online súťaži v programovaní so zameraním na algoritmy je mi známa PALMA. Z online súťaží v angličtine spomeniem TOPCODER. Alternatíva k liahni je USACO.

K angličtine. KSP je v slovenčine, prípadne v češtine. Základné algoritmy sú tiež, sem-tam sa nejaká kniha preloží. Vďaka slušnej grafovej komunite u nás sa dajú nájsť aj pokročilejšie grafové algoritmy v týchto jazykoch. No väčšinou algoritmus, ktorý chcete vedieť, sa zadá do vyhľadávača, kde sú takmer všetky odkazy v angličtine. Angličtina sa už ani neberie ako nejaká výhoda, ale radí sa medzi gramotnosť, ak sa chce človek zaoberať prírodnými vedami. Žijeme v modernej dobe, rôzne videá o algoritmoch, použite vyhľadávačov beriem ako samozrejmosť.

Kto sa chce zaoberať algoritmami čisto po teoretickej stránke môžem, odporučiť Lev Bukovský, Teória algoritmov. Ide o čistú teóriu, na ktorej stojí (skôr padá) celá informatika. Vyžaduje značnú mieru abstrakcie, preto by som si ju netrúfal dať stredoškolákovi. Ináč, ak by ste mali pocit, že na skúmanie algoritmu nutne musíte vedieť programovať, tak Vám poviem jednu perličku :). Lev Bukovský sa stále chvasce, že on programovať nevie. On ma na to ľudí. :)

Páčil sa Vám tento článok? Pridajte si blogera medzi obľúbených a my Vám pošleme email keď napíše ďalší článok
Pridaj k obľúbeným

Hlavné správy

Archívny článok

Odborníci radia, čo robiť v horiacej budove

Staré budovy nemajú dostatok únikových ciest ani protipožiarne technológie.


Už ste čítali?