Stranka z minuleho roku je tu.
Stranka z cviceni R.S. je tu.
Tato stranka bude viac-menej kompilacia predoslych dvoch.
Poznamky k tomuto predmetu najdete tu.
Predosle midtermy najdete tu a tu.
V knižnici sa nachádza (prezenčne) viacero kníh, ktoré pokrývajú prvú časť prednášky, dobre sa číta napríklad kniha Robert Sedgewick - Algorithms 1-4, ktorá existuje vo variáciach in Java, in C++, in C. V knižnici je určite java a možno i C++. Vyčerpávajúci prehľad poskytuje kniha Introduction To Algorithms, ktorá je ale určená skôr pre hlbšie pochopenie. V podstate čokoľvek, čo má v názve algorithms a v indexe kapitoly recursion, dynamic programming alebo obdobné sa môže hodiť.
Z menej známych kníh by som ešte rád upozornil na nasledujúce dve:
Ian Parberry, William Gasarch - Problems on algorithms (free).
Zaujímavá zbierka príkladov na precvičenie, príklady sú delené podľa jednotlivých konceptov.
Jeff Edmonds - How to Think About Algorithms
Táto kniha je veľmi špecifická. Ak ste sa márne pokúšali niektorý z konceptov (dynamika, rekurzia) pochopiť a ani po desiatom materiáli to nedáva zmysel, možno je rozumné sa pozrieť do tejto knihy. Je zaručene odlišná od ľubovoľného dostupného textu, pomáha si zvláštnymi prirovnaniami, niekedy sa tvári ako kuchárka, dáva rady o tom ako rozmýšlať o jednotlivých konceptoch... jednoducho núdzové riešenie ak nič iné nepomohlo, resp. v prípade, že máte pocit, že autori všetkých ostatných kníh rozmýšlajú inak ako vy.
Jeff Erickson - Algorithms Course Materials
link
Relevantné sú kapitoly z časti Recursion.
Vzhladom na teoreticku povahu dalsich cviceni sa nove materialy budu objavovat skor sporadicky.
Doplnkove materialy k prednaske sa daju najst na:
Komu sa chce, moze si precitat, ako sa meni cas DTS pri redukcii z k pasok na 2. Tu je povodny clanok z 1966. Tu je kratsi dokaz, ale nejake detaily si je treba domysliet.
Odporucam precitat si ten povodny. Po stranu 8 su to take povedacky s obrazkami, ako to funguje ... tu je ta hlavna myslienka. Dalsie dve strany su potom o trochu viac technicke.
NEW NP uplnost 3-coloring (a teda aj k-coloring) najdete tu.
Wiki stránka o modeli RAM.
RAM emulátory (WIN, LINUX)
Bubblesort z cviceni najdete tu.
Na cviceniach sme sa stretli s tym, ze na pripocitanie jednotky k nejakemu registru treba az tri prikazy:
LOAD j
ADD =1
STORE j
co sme zhrnuli ako jednu novu instrukciu INC j. Skute si napisat podobne instrukcie pre
Dobra rada na zaver (RS):
Prudko odporúčam nepúšťať sa priamo do písania RAMu, ale najskôr si napísať daný program v nejakom vyššom programovaciom jazyku, rozmyslieť si ako využijete ktoré pamäťové miesta RAMu, v prípade, že budete často používať nejakú operáciu, tak si na ňu urobiť makro, alebo procedúru. Až následne generovať RAM s veľmi voľným označovaním čísiel riadkov, ich následným doplnením, keď už máte finálnu podobu kódu. Nezabudnúť odhadnúť pamäťovú i časovú zložitosť.
Wiki stránka o Turingovom stroji.
Video posh Turingoveho stroja a jeho legového variantu.
Simulátor TS: tu
Skriptá z formálnych jazykov a automatov (link). Odporúčam prejsť si kapitolu 6.1 a skúsiť si napísať turingov stroj pre niektoré z príkladov cvičenia 6.1.1.
V knižnici je celkom príjemne napísaná kniha Automata Theory, Languages and Computation (Hopcroft, Motwani, Ullman), z ktorej sú pre druhú polovicu semestra relevantné časti kapitol 8, 9 a 10.
Definiciu jazykov a veci okolo nich najdete tu (casti 1.1 a 1.2).
Veci okolo kodovania TS a rozhodnutelnosti su v prednaskach a potom sa nieco zaujimave da najst aj tu (cast 6.6 a dalej).
Automata Theory, Languages and Computation mozete najst na stranke ako hmu.djvu.
Vzorovy priklad na jednoduchy DTS s celou delta funkciou je tu.
DTS pre palyndrom z cviceni. Odporucam odsimulovat si ho na nejakom kratkom slove.
Uvazujme TS, ktory bude pracovat s cislami (teda vstupna aj pracovna abeceda bude mnozina cisel 0,...,9). Premyslite si, ako by vyzerala delta funkcia pre:
Dalsie priklady na precvicenie:
L_1={abaab}
L_2={abb,aba,aabbaba,bbbab,bbab} (resp. iny konecny jazyk)
L_3={a^i | i je deliteľné 2,3, alebo 5}
L_4={a^p | p je prvočíslo} (ak sa vám chce, tak premyslite detaily, alebo si ho rovno naimplementujte)
L_5={G | graf G je súvislý}
L_1'={uabaabw | kde u a w su lubovolne stringy nad vstupnou abecedou}
L_2'={uvw | kde v je prvok z L_2 a u, w su lubovolne stringy nad vstupnou abecedou}
L_6={M | M je zmysluplny kod TS} (kodovanie si urcite sami)
TS pre jazyky L_1, L_2, L_3, L_1', L_2' by ste mali zvladnut napisat aj celou delta funkciou. Pre jazyky L_4, L_5, L_6 treba vediet, ako bude cely vypocet prebiehat, ako sa bude pouzivat pasku atd. V tomto pripade netreba pisat delta funkciu, ale treba dostat vase riesenie do takeho tvaru, ze napisat tu delta funkciu je uz jednoducha (aj ked velmi pracna) zalezitost.
Dalej si mozete skusit vyrobit TS pre taketo jazyky:
L_7={a^n b^n c^n | n je prirodzene cislo} ... aj delta funkciu
L_8={a^n b^m | n deli m alebo m deli n}... aj delta funkciu
L_9={a^n b^m c^k | n + m^3 + 2^k je prvocislo}
L_10={a^n | n = 1 + 2^2 + 3^3 + 4^4 + 5^5 + ... + k^k pre nejake k}
v pripade 9 si detailne premyslite priebeh vypoctu ... potrebujete vediet ako z m vyrobit m^3 a ako z k vyrobit 2^k. Az ho budete mat hotovy, mozete skusit 10.
V pripade 10 mozete pouzit napr fakt, ze ak slovo na vstupe nepatri do jazyka L_10, potom TS vobec nemusi zastavit.
Pri rieseni mozete pouzit lubovolne vela pasok ale skuste si premysliet, ktore casti vypoctu by sa skomplikovali, ak by ste mali iba jednu.
Pri pouzivani viacerych pasok v pripade jazykov 7,8 treba pamatat na to, ze sa zmeni zapis delta funkcie ... treba ju adekvatne rozsirit podla poctu pasok. Teda namiesto povodnej d(k,a)=(l,b,x) treba v pripade 2 pasok pouzit d(k,a,a')=(l,b,x,b',x'), kde
k, l su stavy
a, a', b, b' su pracovne symboly (ciarkovane sa tykaju druhej pasky)
x, x' su z mnoziny {-1, 0, 1} vyjadrujuce pohyb hlavy na prvej resp. druhej paske.
ADS: problem vyberu aktivit, konstrukcia Huffmanovho kodu
TEA: algoritmy na grafoch - Kruskal, Dijkstra
Greedy tutorial
Jeff Erickson
continuous knapsack: 1, 2
Dalsie priklady sa daju najst v v Problems on algorithms (kapitola 9) a oplati sa precitat si prislusne casti v How to Think About Algorithms (kapitola 16).
Wiki stránka o dynamickom programovaní.
Okrem wiki sa oplatí začať s nejakou dobrou knihou o algoritmoch a dátových štruktúrach, takmer každá obsahuje kapitolu o dynamickom programovaní so základnými tézami a jednoduchými príkladmi.
Dynamické programovanie - tutoriály, základné koncepty (1,2)
Dymanické programovanie - séria tutoriálov, skôr pre pokročilých, s veľa príkladmi a zaujímavými trikmi (1, 2, 3)
Jeff Erickson
Dobry uvod do DP je v ADS v kapitole 5 tu (nasobenie matic, LCS) a v kapitole 4 tu (nasobenie matic, 0-1 knapsack).
Priklady z cviceni 1, 2, 3, 4.
Príklad o zbieraní jabĺk (sekcia: Intermediate problem)
Longest increasing subsequence LIS.
Oplati sa prejst si nejake priklady napr. z
Ian Parberry, William Gasarch - Problems on algorithms (free)
alebo
Jeff Edmonds - How to Think About Algorithms (nie je free, takze ste si alg.pdf nestiahli z tejto stranky :)
Na cviceniach sme to az tak velmi nespominali, ale premyslite si tiez casovu a priestorovu zlozitost tychto algoritmov.
Najbližšie body v rovine (1, 2, 3)
Binárne vyhľadávanie (link)
Výpočet b^N je v kapitole 9.2 v How to think about algorithms (link).
Majority problem (Problem 4)
Min Convex Hull (pripadne milion inych clankov na googli)
Skyline problem(4.5)
Jeden priklad z cviceni je tu.
Nasobenie Boolovskych matic a ine uzitocne veci su tu (informaticka Tvorba efektivnych algoritmov).
Skriptá ADŠ - Rast funkcií - 2.1 a Rekurentné vzťahy - 2.2.
"Kto googli ten nájde." ( k tomuto sa dá nájsť fakt veľa, takže ak vám niečo nie je jasné, tak mathworld.wolfram.com, wiki, alebo väčšina kníh o algoritmoch a dátových štruktúrach)
Hlavne sa oplatí si pozrieť sumy, rátanie rekurencií a možno sa hodia i logaritmické identity.
Jeff Erickson
ADS teraz vedie Misof, nejake dalsie materialy sa daju najst na jeho stranke tu.
Trochu ina (a vseobecnejsia) verzia Master metody pocitania rekurencii je v 27. kapitole tu. Oplati sa pozriet si niektore priklady z tejto kapitoly alebo si vymyslite vlastne.
Este vseobecnejsia Master metoda je tu (veta 4.2).
Zopar poznamok k prikladom z cvicenii k tejto teme je tu.
Definiciu AZ z cviceni a nejake priklady najdete tu. Samozrejme, treba si precitat aj prislunu cast z poznamok k prednaske.
Co tyka O notacie a hierarchie funkcii, koho to zaujalo, moze najst dodatocne informacie napriklad v tejto knihe, kapitola 9. Da sa najst bud u nas v kniznici alebo na stranke ako CM.pdf.
Relevantne linky k tejto casti su aj v dalsich cviceniach.