Predosla stranka z cviceni je tu. Tato bude obsahovo dost podobna. Veci, ktore som len skopcil, sa budem snazit davat do kurzivy.
Poznamky k tomuto predmetu najdete 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.
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 od R.S. na zaver:
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.
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. Čo si teraz precvičíte, v druhej polovici semestra akoby ste našli.
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:
Je dobre mat nejaku prax s TS, lebo potom bude jednoduchsie prehryzt sa niektorymi castami zo zlozitosti v druhej polovici semestra.
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.
Zopar poznamok k prikladom z cvicenii k tejto teme je tu.
Rozdeluj a panuj
Najbližšie body v rovine (1, 2, 3)
Binárne vyhľadávanie (link)
Výpočet b^N je napríklad kapitola 9.2 v How to think about algorithms (link).
Nieco (nie len) k tejto teme sa este da najst tu (informaticka Tvorba efektivnych algoritmov).
Priklad, v ktorom som sa pomylil na cviceni je tu.
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, pripadne sa nieco da najst aj tu v kapitole 4 (na konci je tiez niekolko prikladov na zamyslenie).
Príklad 1: O zbieraní jabĺk (sekcia: Intermediate problem)
Príklad 2: O meškajúcich študentoch.
Domáca úloha: Tu. Zadaná bola pre ľubovoľnú dĺžku N a pre kachličky dĺžky 1,2 a 3, ale to je v podstate jedno. Dobré cvičenie pre vás môže byť skúsiť si to naprogramovať vo vašom obľúbenom programovacom jazyku a výsledok odovzdať v systéme na danej stránke (po registrácií), nech viete, či to máte dobre (rovnako pre príklad 2).
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 :)
Jeff Erickson - príklad s randením je kapitola 4.2
Greedy tutorial
Opat prislusne kapitoly z ADS (problem vyberu aktivit, Huffmanov kod) a skripta TEA (algoritmy na grafoch - Kruskal, Dijkstra).
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).
Simulátor TS: tu
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.
Stále sú relevantné i linky z cvičenia 2
Príklady z cvičenia:
L_1={abaab}
L_2={abb,aba,aabbaba,bbbab,bbab} (resp. iný konečný 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ý} (z úvodnej rozpravy o problémoch a jazykoch, ak chcete domyslite detaily)
Príklady na precvičenie:
L_1'={uabaabw | kde u a w sú lubovoľné stringy nad vstupnou abecedou}
L_2'={uvw | kde v je prvok z L_2 a u, w sú lubovoľné stringy nad vstupnou abecedou}
L_6={M | M je zmysluplný kód TS} (kódovanie si určite 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.
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.
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.