Vybrané kapitoly z teoretickej informatiky (1)

V piatok 24. júna o 13:00 prebehne dalšie (a pravdepodobne posledné) kolo konzultácií v akváriu č. IX.
Ak sa to prekrýva s nejakou skúškou, tak mi dajte včas vedieť.
Ako už isto viete, nepôjde o klasické cvičenie, ale pokúsime sa prejsť veci, ktoré vám nie sú úplne jasné, preto si skúste rozmyslieť konkrétne časti preberanej látky ktorých sa to týka.
(dajte si o tom nejakým spôsobom vedieť -- je mi jasné, že toto nie je najčítanejší web v okolí (dokonca ani v okolí termínov skúšky) )

Cvičenia

Richard Štefanec, M101
kontakt

Na tejto stránke budú postupne pribúdať materiály, ktoré by sa vám mohli hodiť pri príprave na písomku, resp. ku skúške. Pôjde primárne o materiály, ktoré som spomínal na cvičení, z ktorých som si pripravoval príklady a také, ktoré som zabudol spomenúť resp. o rady, ako pristupovať k niektorým problémom. Malo by ísť o doplnok k oficiálnym materiálom z prednášky. Táto stránka bude updatovaná priebežne, ako budem nachádzať zaujímavé materiály k jednotlivým témam, nie nutne len k najnovšiemu cvičeniu.

Cvičenie 1+2 (Turingove stroje, RAM)

(M)RAM

Wiki stránka o modeli RAM.
RAM emulátory (WIN, LINUX)
Zaujímavý príklad na precvičenie je naprogramovať nejaký triviálny sort ako napr. insertsort, alebo bubblesort. Prípadne nejaký obdobne jednoduchý program. Na úplny začiatok si overte, či viete v RAMe napísať bežné konštrukcie ako cykly, ify a procedúry, súčet 2 hodnôt, výmena dvoch hodnôt etc.
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ť.

Turingove stroje

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.

Cvičenie 3 (Zložitosť, rast funkcií, rekurencie)

Asymptotika

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

Cvičenie 4 (Rozdeluj a panuj, Rekurzia)

Najbližšie body v rovine (1, 2, 3)
Binárne vyhľadávanie (link)
Výpočet b^N je napríklad kapitola 8.2 v How to think about algorithms (podla verzie 0.12).

Cvičenie 5 (Dynamické programovanie)

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

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).

Cvičenie 6 (Greedy)

Jeff Erickson - príklad s randením je kapitola 4.2
Greedy tutorial

Cvičenie 7 (Deterministický Turingov stroj)

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 1+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 detajly, alebo si ho rovno naimplementujte)
L_5={G | graf G je súvislý} (z úvodnej rozpravy o problémoch a jazykoch, ak chcete domyslite detajly)
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)
Metaotázky z cvičenia:
Majme kód DTS a vstupné slovo, vieme ako bude vyzerať konfigurácia po k-tom kroku výpočtu?
Majme kód DTS, vstupné slovo a konfiguráciu, vieme či je táto konfigurácia dosiahnuteľná?
Majme kód DTS, vstupné slovo a číslo n, vieme či daný DTS po n krokoch výpočtu zastane?
Majme kód DTS a vstupné slovo, vieme či daný DTS po zastane?
Majme kód DTS, vstupné slovo a číslo k, vieme či daný DTS spotrebuje viac ako k miest na páske?
Zamyslenie o zacyklení sa po tom ako nastala 2x rovnaká konfigurácia. Zamyslenie sa o iných nezmyselných činnostiach, ktoré vie TS robiť nekonečne dlho.
Metaotázky z na dlhé večery:
Majme vstupné slovo a konfiguráciu. Koľko krokov musí ľubovoľný DTS urobiť, aby takúto konfiguráciu dosiahol? (minimum)
Majme vstupné slovo a konfiguráciu. Koľko krokov môže nejaký DTS urobiť predtým než túto konfiguráciu dosiahne? (maximum)
Predchádzajúce 2 otázky sa dajú rôzne varírovať, napr. môžeme začínať na prázdnej páske a namiesto konfigurácie nás zaujíma len to koľko musíme resp. môžeme počítať predtým než minieme dostatočne veľa pásky. (áno, niečo také bolo na tabuli)
Ešte dlhšie večery:
Najmenšie známe Univerzálne Turingove stroje: prehľad(wiki), stroj s 22 inštrukciami.
Motivačný článok Scotta Aaronsona o niektorých zaujímavých stránkach detských hier, počítania a sveta Who Can Name the Bigger Number? (skryl som ho na koniec, ale je fakt veľmi dobre napísaný a oplatí sa vám ho prečítať ak máte záujem vidieť kam časť z tohto smeruje za hranicami tejto prednášky)

Materály

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.

NEW! Materiály k druhej časti semestra
Michal Forišek - Formálne jazyky a automaty - skriptá link
Pavol Ďuriš - Výpočtová zložitosť link
Juraj Hromkovič - Theoretical Computer Science
Táto kniha je síce súčasťou oficiálnych materiálov, ale nie je zlé si pripomenúť, že existuje jeden text obsahujúci väčšinu preberaných výsledkov.