Programovací jazyky OCaml a F#, PRG049

Obsah semináře

Budeme se zaobírat funkcionálním programováním v jazycích z rodiny ML, především v jazycích OCaml a F#. Tyto jazyky mohou být užitečné v praxi, protože nejsou čistě funkcionální (můžete říct co se vyhodnocuje striktně a co líně, můžete používat imperativní konstrukce a funkce se side-efekty), přesto je možné v nich elegantně funkcionálně programovat. A nakonec nejdůležitější poznámka: v OCaml-u nejsou monády :)

Doba a místo konání

Seminář se koná ve středu v 15:40 na Malé Straně v SW1.

Zápočet

Pro získání zápočtu je třeba získat 30 bodů. Body je možné získávat za domácí úkoly (těch bude vypsáno alespoň za 80 bodů), za referáty (předpokládám tak jeden dva) a za zápočtový program (je možné se domluvit na obtížnosti 1 až 30 bodů, pro zájemce i více :). Body se sčítají.

Kde sehnat OCaml a F#

OCaml je možné stáhnout zde, přičemž zde je dokumentace.

F# je možné stáhnout zde, najděte odkaz 'Download the F# CTP'. Kromě překladače F# budete potřebovat .NET verze alespoň 2.0. Zde je popis jazyka a seznam funkcí.

Můžete použít .NET od MS, pak si stáhněte rovnou Microsoft Visual Studio Shell 2008 (integrated mode), tím získáte i IDE. VS Shell je zdarma. V tomto případě si vyberte .msi variantu překladače F#.

Dále můžete použít Mono 2.0. Mono doporučuji verze alespoň 2.0.1. Na widlich funguje bez problémů, na Linuxu ve fsi nefungují šipky a konzole vypisuje korektně až od druhého řádku. Začněte tedy zmáčknutím 'středník středník enter'. V tomto případě si vyberte .zip variantu překladače F#.

Nástroje pro parsování pro OCaml a F#

K tokenizování můžete použít ocamllex, což je generátor tokenizátorů. Dokumentace je zde. S kompilátorem F# je dodáván reimplementace tohoto nástroje jménem fslex, který má stejný formát vstupu. Další informace o něm si přečtěte tady.

Nad tokenizovátkem je možné postavit parser. Ke generování parserů lze použít ocamlyacc, jehož dokumentace je tady. Stejně jako předtím je v F# reimplementován jako fsyacc, o němž si můžete přečíst zde.

Obsahy přednášek

1. přednáška: základy, ocaml01.ml, ocaml01.ps, ocaml01.pdf.
2. přednáška: další základy jako vlastní datové typy, seznamy, pattern matching, tail rekurze atd. ocaml02.ml, ocaml02.ps, ocaml02.pdf.
3. přednáška: struktury, side-effekty, vstup a výstup, reference, pole, mutable položky struktur, value restriction ocaml03.ml, ocaml03.ps, ocaml03.pdf.
4. přednáška: líné vyhodnocování, vyjímky, kompilační jednotky a jejich interface, moduly v OCamlu ocaml04.ml, ocaml04.ps, ocaml04.pdf.
5. přednáška: moduly v OCamlu podruhé, funktory, objektový systém OCamlu ocaml05.ml, ocaml05.ps, ocaml05.pdf
6. přednáška: základy platformy .NET, základní a strukturované typy v F#, přetěžování operátorů, #light syntaxe, seznamy, pole a iterátory fsharp01.fs, fsharp01.ps, fsharp01.pdf
7. přednáška: finalizace v .NET a IDisposable a use .. in .., výjimky, objektová hierarchie a přetypování, vstupy a výstupy, nafukovací pole fsharp02.fs, fsharp02.ps, fsharp02.pdf
8. přednáška: třídy a objekty v .NET a F#, member functions a properties, rekordy s member functions a properties, konstruované třídy, defaultní a explicitní konstruktory, viditelnost, sequence expressions a compitation expressions fsharp03.fs, fsharp03.ps, fsharp03.pdf
9. přednáška: Delegate a Event v .NETu, IDelegateEvent, IEvent, DelegateEvent, Event v F#, Event je first-class value; monády aneb computation expressions fsharp04.fs, fsharp04.ps, fsharp04.pdf
10. přednáška: computation expressions aneb monády, a to obecné, parsovací, continuation passing a úplně na konci začátek asynchronních výpočtů fsharp05.fs, fsharp05.ps, fsharp05.pdf
11. přednáška: ThreadPool, BackgroundWorker jako jeho jednoduchá nadstavba, synchronizační kontexty, asynchronní výpočty, jejich vnitřní implementace, asynchronní předávání zpráv fsharp06.fs, fsharp06.ps, fsharp06.pdf
12. přednáška: Active Patterns, Quotations, reflexe v .NETu a její nadstavba v F# fsharp07.fs, fsharp07.ps, fsharp07.pdf
13. přednáška: klasické thready a zámky v .NET, STM monáda pro řešení synchronizace, tokenizování s fslex, parsování s fsyacc fsharp08.fs, fsharp08.ps, fsharp08.pdf

Domácí úkoly (28. 06. 2010)

Prosím posílejte úkoly jako textové přílohy mailu, nezabalujte je. Lépe se mi opravují. Pokud není řečeno jinak, můžete si vybrat, jestli chcete dělat domácí úkoly F# i v OCamlu.

Zadání domácích úkolů se může lehce změnit oproti tomu, které jsem zadával na hodině (když udělám nějakou chybu). Platná verze je vždy ta uvedená zde.

Datum
cvičení ID Body Popis
08. října 2008 Úkoly můžete odevzdávat do 05. listopadu 2008, 15:30.
pow 1 Napište operátor mocnění typu int -> int -> int. Umocnění na n-tou by mělo použít Ο(log n) násobení. Zvolte vhodné jméno aby měl operátor správnou prioritu :)
bitsum 1 Napište funkci typu int -> int, která v 31-bitovém intu posčítá bity, tj. vrátí počet jedničkových bitů v daném 31-bitovém intu. Implementace, která použije řádově Ο(log b) operací pro číslo o b bitech (v našem případě je b=31), dostane drobný bonus, a implementace, která použije řádově Ο(log log b) operací, dostane ještě něco navíc.
15. října 2008 Úkoly můžete odevzdávat do 12. listopadu 2008, 15:30.
sort 2.5 Napište libovolné třídění čísel s průměrnou složitostí Ο(N log N), přičemž se snažte, abyste potřebovali zásobník o řádové velikosti nejvýš log N (pokud potřebujete zásobník o velikosti Ω(N), strhnu vám bod).
Pro následující úložku předpokládejte type 'a tree = Nil | Node of 'a * ('a tree) * ('a tree).
opti 3.5 Napište funkci typu ('a * int) list -> 'a tree, která se seznamu (a_i, c_i) vytvoří optimální vyhledávací strom vzhledem k a_i. To je takový binární vyhledávací strom, že pokud se na prvek a_i ptáte c_i-krát, celkový čas strávený procházením stromu je minimální.
Plný počet bodů jenom za řešení v Ο(N²), za Ο(N³) je 2.5 bodů, za horší alespoň 1.5 bodu.
22. října 2008 Úkoly můžete odevzdávat do 19. listopadu 2008, 15:30.
ssrt 3 Napište funkci ssort : string array -> unit, která dostane na vstupu N řetězců o celkovém počtu P písmen, a setřídí je v čase Ο(P + A), kde A je velikost abecedy (tj. 256 pro nás teď není konstanta). Složitost Ο(P * A) dostane dva body, horší bod.
rost 2.5 Napište funkci rost : 'a list -> 'a list, která pro danou posloupnost najde nejdelší rostoucí podposloupnost (ne nutně souvislou) a tu vrátí. Plný počet bodů za Ο(N log N) řešení, za Ο(N²) 1.5 bodu a za ostatní polynomiální řešení bod.
Hint: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
maxis 2.5 Mějme obecné stromy typu type 'a tree = Node of 'a * 'a tree list. Napište funkci maxis : 'a tree -> 'a list, která najde libovolnou největší možnou množinu vrcholů takovou, že mezi těmito vrcholy nevede žádná hrana, a vrátí hodnoty v těchto vrcholech.
rsam 2 Napište funkci rsamodules : int -> int list, která vrátí daný počet nejmenších RSA modulů. Číslo je RSA modul, pokud je to součin dvou prvočísel. Plný počet bodů jenom za lepší řešení než Ο((N log N)^1.5), za pěkné nebo velmi rychlé řešení může být bonus.
29. října 2008 Úkoly můžete odevzdávat do 26. listopadu 2008, 15:30.
cenzor 2.5 Napište funkci cenzor : string -> string -> string, která ze druhého zadaného slova vymaže všechny výskyty prvního slova. Pozor na to, že smazáním jednoho slova může vzniknout další zakázané slovo, třeba cenzor "bug" "bububuggg".
Hint: KMP (http://mj.ucw.cz/vyuka/0708/ads2/ads2.ps strana 26) a po smazání slov se "vrátit" o dost zpět.
median 2.5 Napište funkci median : int list -> int, která spočítá medián dané nesetříděné posloupnosti. Za lineární složitost dostanete plný počet bodů, za průměrně lineární složitost dostanete 1.5 bodu a za horší složitost bod.
Hint: http://mj.ucw.cz/vyuka/0607/ads1/ads.ps strana 14.
med2 2 Napište funkci med2 : int array -> int array -> int, která dostane dvě setříděná pole a vrátí medián jejich sjednocení. Body dostanete podle složitosti, ale za lineární složitost jich určitě moc nebude.
Hint: Binární vyhledávání :)
psrt 3 Napište funkci psrt : int list -> int list, která setřídí danou posloupnost. Předpokládejte, že daná posloupnost je skoro setříděná v tom smyslu, že každý prvek je nejvýš o k pozic mimo (tedy pro každý prvek je rozdíl jeho indexů v zadané a setříděné posloupnosti nejvýš k). Optimalizujte časovou složitost, tj. Ο(n log k) za tři body, Ο(nk) za dva a zbytek za jeden. Hodnotu k přirozeně neznáte.
Hint: Ο(nk) je bubblesort, na Ο(n log k) stačí použít třídění haldou omezené velikosti. Velikost haldy zkoušet 2, 4, 16, 256, tj. 2^2ⁱ, dokud se to nepovede.
05. listopadu 2008 Úkoly můžete odevzdávat do 03. prosince 2008, 15:30.
rmq 2.5 Napište funkci, která dostane pole čísel A a vyrobí z něj vhodným předzpracováním nějakou datovou strukturu, která bude umět odpovídat na dotazy "jaké je maximum z hodnot A[i .. j] pro dané i a j". Předzpracování musíte zvládnout v lineárním čase, na dotazy musíte umět odpovídat alespoň v Ο(log n). Za Ο(1) na dotaz je nemalý bonus, ale pozor, je to docela těžké a pracné.
Hint: Nad polem si vyrobte vhodný vyvážený binární strom a v každém vrcholu si poznamenejte maximum ze všech jeho synů. Daný interval pak rozložte tak, aby stačilo šáhnout o řádově log N vrcholů v tomto stromě.
mul 2.5 Napište funkci mul : int array -> int array -> int array, která násobí dvě daná dlouhá čísla. Dlouhá čísla si reprezentujte jak chcete, jenom typ této reprezentace musí být int array. Triviální řešení v Ο(N²) za bod, lepší než kvadratické za dva a půl (a šílená řešení mohou dostat i bodů víc :–).
Hint: http://en.wikipedia.org/wiki/Karatsuba_algorithm
maxpath 2 Mějme obecné stromy typu type 'a tree = Node of 'a * 'a tree list. Napište funkci maxt : 'a tree -> 'a list, která dostane strom a vrátí jednu z nejdelších cest v tomto stromě. Cestu vraťte jako seznam hodnot typu 'a.
Hint: Jedno procházení do hloubky, v každém vrcholu si spočtěte dvě nejdelší cesty z něj dolů do listů. Nakonec si vyberte vrchol, ve kterém je součet těchto dvou cest maximální.
perm 2.5 Napište funkce rank : int array -> int a unrank : int -> int -> int array. Funkce rank dostane permutaci a vrátí její pořadové číslo, funkce unrank dostane délku permutace, její pořadové číslo a vrátí tuto permutaci. Samozřejmě jsou rank a unrank inverzní, ale jinak může být očíslování permutací libovolné (nemusí být například lexikografické). Předpokládejte, že se pořadové číslo permutace vejde do intu. Plný počet bodů jenom za lineární složitost obou funkcí.
Hint: http://citeseer.ist.psu.edu/myrvold00ranking.html
12. listopadu 2008 Úkoly můžete odevzdávat do 10. prosince 2008, 15:30.
short01 2 Napište funkci short01 : int -> byte list, která dostane číslo N a najde takové nenulové přirozené číslo, které má v desítkovém zápisu jenom nuly a jedničky, je dělitelné číslem N a jeho desítkový zápis je nejkratší možný. Toto číslo vraťte po cifrách v seznamu, v pořadí od nejméně důležité cifry (od jednotek). Body podle složitosti.
Hint: Prohledávání do šířky. Vrcholy jsou zbytek po dělení N (na začátku jsem ve vrcholu s hodnotou 1), hrany jsou přidání nuly nebo jedničky na konec čísla. Hledám nejkratší cestu do nuly.
min1 2 Napište funkci min1 : int -> byte list, která dostane číslo N a najde takové nenulové přirozené číslo, které má v desítkovém zápisu jenom nuly a jedničky, je dělitelné číslem N a jeho desítkový zápis obsahuje nejmenší možný počet jedniček. Toto číslo vraťte po cifrách v seznamu, v pořadí od nejméně důležité cifry (od jednotek). Body podle složitosti.
Hint: Jako minulá úloha, jenom musíme chytřeji provádět prohledávání grafu (hrany odpovídající přidání nuly jsou zadarmo).
zs 4 Pouze F# Mějme čísla x₁, x₂, ..., x_N a definujme hodnoty z_i jako součin všech x_j kromě x_i, takže z_i = Π_j<>i x_j. Vaším úkolem bude spočítat všechny z_i, přičemž nesmíte používat žádné jiné operace než násobení (speciálně ne dělení). Napište tedy funkci zs : int [] -> seq<int>. Tato funkce dostane na vstupu hodnoty x_i a vytvoří sekvenci, která vrátí postupně hodnoty z₁, z₂, ..., z_N. Vaším úkolem je co nejvíce šetřit časem a pamětí, přičemž uvažujeme časovou a paměťovou složitost pro spočtení všech z_i.
Čas Ο(N) a paměť Ο(N): +1 bod
Čas Ο(N) a paměť Ο(√N): +1 bod
Čas Ο(N log N) a paměť Ο(log N): +2 body
Řešení můžete poslat několik a body se sčítají podle toho, co splníte. Všimněte si, že pokud splníte druhou variantu, splnili jste automaticky i první variantu.
Hint: Předpočítáním si pro každé i součin x_ix_i+1...x_N od konce dostanu první variantu. Pokud si z těchto hodnot pamatuji pouze každou √N-tou, dostanu √N bloků. Každý vyřeším tak, že si hodnoty v něm spočtu z oné jedné zapamatované hodnoty do pomocné paměti o velikosti √N. Variantu s log N pamětí neporadím :)
19. listopadu 2008 Úkoly můžete odevzdávat do 17. prosince 2008, 15:30.
grep 1.5 Napište program, který jako parametr dostane regulární výraz, zpracovává standardní vstup a vypisuje ty řádky, které tomuto výrazu odpovídají. Umožněte ještě, aby bylo možno před regulárním výrazem zadat swištík -v, který způsobí, že se budou vypisovat řádky, které nevyhovují.
Hint: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regex_members.aspx
hist 2 Napište program, který načte řádky ze standardního vstupu a vypíše jejich histogram (tj. informace řádka vstupu a její četnost) setříděný od nejčastějších řádek. Takže program dělá přibližně to, co sort | uniq -c | sort -nr.
Hint: Hešování nebo stromečky :–)
sed 2.5 Pouze F# Napište program, který jako první parametr dostane v jazyce F# zdrojový kód nějaké funkce typu string -> string. Program pak načítá řádky standardního vstupu, na každý spustí tuto funkci a pokud vrátí neprázdný řetězec, vypíše ho na standardní výstup. Tahle úloha je dost technická, ale pokud by vás bavila, můžete začít třeba zde http://msdn.microsoft.com/en-us/library/system.codedom.compiler.codedomprovider_members.aspx nebo přímo v FSharp.Compiler.CodeDom.dll nebo FSharp.Compiler.dll.
dehash 3 Mějme nějakou funkci f : int -> int, přičemž víme, že posloupnost 0, f(0), f(f(0)), ..., je periodická, takže nějaké f^N(0) je rovno nějaké předchozí hodnotě. Vaším cílem je, když dostanete libovolnou takovou funkci f, provést nějaké předzpracování a pak umět odpovídat na otázky "když dostanu x, pro jaké y je f(y) = x"? Přičemž pro x, které jsou v posloupnosti 0, f(0), f(f(0)), ..., musíte odpovědět vždy správně, a pro x, která nejsou, řekněte, že nevíte.
Napište tedy funkci typu dehash : (int -> int) -> (int -> int option). Pro plný počet bodů musí předzpracování trvat Ο(N), musí si vystačit s ostře méně než Ο(N) paměti a odpovídat na otázky musíte umět také ostře lépe než v čase Ο(N).
Hint: Hodnoty funkce f tvoří ocásek a pak cyklus. Na ocásku i cyklu si pamatujte každou odmotnintou hodnotu a u každé si pamatujte, jaká odmocnintá hodnota je před ní. Když poté hledáte vzor x, jděte z x pořád dál, než narazíte na uloženou hodnotu, skočte na jejího předchůdce a jděte směrem k x.
26. listopadu 2008 Úkoly můžete odevzdávat do 07. ledna 2009, 15:30.
upword 2 Napište funkci upword : string -> string -> string, která dostane a a b a vrátí co nejkratší slovo, jehož jsou a i b (ne nutně souvislá) podslova.
Hint: http://en.wikipedia.org/wiki/Shortest_common_supersequence_problem
decrypt 2.5 Máme zprávu, která se skládá ze znaků 'a'..'z', které si očíslujeme 0..25. Posun písmene i o k je písmeno (i+k) mod 26 a posun celé zprávy o k je posun všech jejích písmen o k.
Napište funkci decrypt : string -> string -> string, která dostane zprávu posunutou o neznámou hodnotu k. Dále dostane nějaký text v jazyce, ve kterém je zašifrovaná zpráva. Cílem je vrátit jeden z posunů dané zašifrované zprávy, a to ten nepravděpodobnější. Pravděpodobnost nějaké zprávy můžete měřit například frekvencí jednotlivých znaků ('e' je v češtině nejpravděpodobnější, 'w' velmi málo pravděpodobné atd.).
Hint: http://en.wikipedia.org/wiki/Frequency_analysis
cmprs 5 Napište konzolové programy cmprs a uncmprs. Tyto programy dostanou na příkazové řádce právě jedno jméno souboru, který zabalí/rozbalí. Kompresní metoda by měla být jedna z následujících: Huffmanovo kódování nebo aritmetické kódování (případně i s BWT za dva bonusové body) či nějaká varianta LZ*. Koncovku zabaleného souboru si vyberte sami. Mělo by to být celé v F#, rozumně efektivní a na plný počet bodů byste měli i testovat integritu rozbaleného souboru (spočítat si nějaké CRC při zabalování a to po rozbalení zkontrolovat).
03. prosince 2008 Úkoly můžete odevzdávat do 14. ledna 2009, 15:30.
abcd 3 Abeceda ztraceného národa Atlantiďanů se skládala z nějaké podmnožiny Unicode znaků. Bohužel už není známo uspořádání těchto znaků, ale víte, že bylo lineární. Získali jste kus slovníku, tedy několik slov, která jsou lexikograficky setříděná. Předpokládejte, že písmena těchto slov tvoří kompletní atlantidskou abecedu. Vaším úkolem je nalézt lineární uspořádání písmen v abecedě, případně říct, že ho z daných slov nejde stanovit. Napište tedy funkci |abcd::string list -> char list option|, která dostane lexikograficky setříděná slova a pokud je možné určit jednoznačné lineární uspořádání všech písmen v těchto slovech, vrátí ho, jinak vrátí None. Můžete předpokládat, že data jsou konzistentní.
diff 4 Napište konzolový program diff, který dostane na příkazové řádce dva soubory (pokud jeden chybí, tak je to standardní vstup) a najde diff, tj. nejmenší počet řádek, které je třeba odstranit či přidat, aby se z prvního souboru stal druhý. Na výstup (jako diff -u) vypište nezměněné řádky s mezerou na začátku, odstraněné s - na začátku a přidané s + na začátku. Program musí fungovat se složitostí Ο(délka_delšího_souboru * velikost_diffu), za nic jiného body nejsou (složitost Ο(délka_jednoho * délka_druhého) je totiž pro velké soubory s malým počtem změn nepoužitelná).
10. prosince 2008 Úkoly můžete odevzdávat do 22. února 2009, 23:59.
volume 4.5 Obdélkík, jehož strany jsou rovnoběžné s osamy, můžeme reprezentovat souřadnicemi dvou protilehlých rohů jako float * float * float * float. Napište funkci volume : (float * float * float * float) list -> float, která dostane několik obdélníku, jejichž strany jsou rovnoběžné s osami, a spočte obsah jejich sjednocení. Za kvadratické řešení je 2.5 bodu, za Ο(N log N) je plný počet 4.5 bodu.
eval 3 Napište funkci eval : string -> float, která dostane na vstupu řetězec obsahující výraz a vrátí jeho hodnotu. Musíte umět celá a desetinná čísla, binární operátory +, -, *, /, ^ včetně priorit, funkce exp a log a závorky. Daný výraz může obsahovat libovolné počty mezer.
Hint: Můžete použít parsování z hodiny, ale také libovolné jiné.
deriv 1.5 Pokud vyřešíte úlohu eval, napište funkci diff : string -> string, která zderivuje daný výraz. Oba výrazy jsou v již popsaném formátu, jenom smí obsahovat ještě proměnnou x. Výsledný výraz nemusí být nijak zjednodušen, ale je možné za to přidělit body navíc.
vareval 1.5 Pokud vyřešíte úlohu eval, napište funkci vareval : string -> float. Výraz na vstupu je v popsaném formátu, jenom může obsahovat konstrukci let prom = a in b, kde prom je řetězec malých písmen, a a b jsou výrazy a ve výrazu b se může objevit proměnná prom, která bude mít hodnotu výrazu a. Oba výrazy a a b mohou uvnitř samozřejmě obsahovat další lety, například jako 1 + let a = 3 * let b = 3 in 1+b in a^2. Výraz za in parsujte nejdelší možný (takže je ukončen jenom jiným in nebo pravou závorkou).
17. prosince 2008 Úkoly můžete odevzdávat do 22. února 2009, 23:59.
crawler 4 Napište webový crawler. To je konzolový program, který dostane seznam dvojic (url, regexp) a číslo S. Crawler stáhne všechny stránky na seznamu. Z každé stránky vyextrahuje odkazy a ty, které matchují danému regexpu, opět stáhne, a odkazy na nich, které matchují danému regexpu, opět rekurzivně stáhne... V jednom časovém okamžiku stahujte najednou S stránek a jedno konkrétní url stahujte nanejvýš jednou.
web 3 Napište jednoduchý webserver. Webserveru při spuštění dáte port a adresář, ze kterého má obsluhovat. Webserver pak sedí na daném portu. Když se ho někdo zeptá, obslouží ho, a obsluhovat zvládne libovolně lidí najednou. Implementujte HTTP 0.9, přičemž byste měli v adresách umět dekódovat "%xy", viz zde. Mělo by to fungovat natolik, aby se se serverem dokázaly mé prohlížeče (Opera, Firefox) bavit.
chat 3 Napište jednoduchý chatovací server. Server by měl poslouchat na zadaném portu. Připojit se může libovolný počet lidí. Když se někdo připojí, tak na první řádce napíše svůj nickname. Každá dalšá řádka od něj se pošle všem ostatním připojeným (těm, kteří už poslali nickname) ve formátu "nickname: řádka".

Datum cvičení	ID	Body	Popis
08. října 2008	Úkoly můžete odevzdávat do 05. listopadu 2008, 15:30.
pow	1	Napište operátor mocnění typu `int -> int -> int`. Umocnění na n-tou by mělo použít Ο(log n) násobení. Zvolte vhodné jméno aby měl operátor správnou prioritu :)
bitsum	1	Napište funkci typu `int -> int`, která v 31-bitovém `int`u posčítá bity, tj. vrátí počet jedničkových bitů v daném 31-bitovém intu. Implementace, která použije řádově Ο(log b) operací pro číslo o b bitech (v našem případě je b=31), dostane drobný bonus, a implementace, která použije řádově Ο(log log b) operací, dostane ještě něco navíc.
15. října 2008	Úkoly můžete odevzdávat do 12. listopadu 2008, 15:30.
sort	2.5	Napište libovolné třídění čísel s průměrnou složitostí Ο(N log N), přičemž se snažte, abyste potřebovali zásobník o řádové velikosti nejvýš log N (pokud potřebujete zásobník o velikosti Ω(N), strhnu vám bod).
		Pro následující úložku předpokládejte `type 'a tree = Nil \| Node of 'a * ('a tree) * ('a tree)`.
opti	3.5	Napište funkci typu `('a * int) list -> 'a tree`, která se seznamu (a_i, c_i) vytvoří optimální vyhledávací strom vzhledem k a_i. To je takový binární vyhledávací strom, že pokud se na prvek a_i ptáte c_i-krát, celkový čas strávený procházením stromu je minimální. Plný počet bodů jenom za řešení v Ο(N²), za Ο(N³) je 2.5 bodů, za horší alespoň 1.5 bodu.
22. října 2008	Úkoly můžete odevzdávat do 19. listopadu 2008, 15:30.
ssrt	3	Napište funkci `ssort : string array -> unit`, která dostane na vstupu N řetězců o celkovém počtu P písmen, a setřídí je v čase Ο(P + A), kde A je velikost abecedy (tj. 256 pro nás teď není konstanta). Složitost Ο(P A)* dostane dva body, horší bod.
rost	2.5	Napište funkci `rost : 'a list -> 'a list`, která pro danou posloupnost najde nejdelší rostoucí podposloupnost (ne nutně souvislou) a tu vrátí. Plný počet bodů za Ο(N log N) řešení, za Ο(N²) 1.5 bodu a za ostatní polynomiální řešení bod. Hint: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
maxis	2.5	Mějme obecné stromy typu `type 'a tree = Node of 'a * 'a tree list`. Napište funkci `maxis : 'a tree -> 'a list`, která najde libovolnou největší možnou množinu vrcholů takovou, že mezi těmito vrcholy nevede žádná hrana, a vrátí hodnoty v těchto vrcholech.
rsam	2	Napište funkci `rsamodules : int -> int list`, která vrátí daný počet nejmenších RSA modulů. Číslo je RSA modul, pokud je to součin dvou prvočísel. Plný počet bodů jenom za lepší řešení než Ο((N log N)^1.5), za pěkné nebo velmi rychlé řešení může být bonus.
29. října 2008	Úkoly můžete odevzdávat do 26. listopadu 2008, 15:30.
cenzor	2.5	Napište funkci `cenzor : string -> string -> string`, která ze druhého zadaného slova vymaže všechny výskyty prvního slova. Pozor na to, že smazáním jednoho slova může vzniknout další zakázané slovo, třeba `cenzor "bug" "bububuggg"`. Hint: KMP (http://mj.ucw.cz/vyuka/0708/ads2/ads2.ps strana 26) a po smazání slov se "vrátit" o dost zpět.
median	2.5	Napište funkci `median : int list -> int`, která spočítá medián dané nesetříděné posloupnosti. Za lineární složitost dostanete plný počet bodů, za průměrně lineární složitost dostanete 1.5 bodu a za horší složitost bod. Hint: http://mj.ucw.cz/vyuka/0607/ads1/ads.ps strana 14.
med2	2	Napište funkci `med2 : int array -> int array -> int`, která dostane dvě setříděná pole a vrátí medián jejich sjednocení. Body dostanete podle složitosti, ale za lineární složitost jich určitě moc nebude. Hint: Binární vyhledávání :)
psrt	3	Napište funkci `psrt : int list -> int list`, která setřídí danou posloupnost. Předpokládejte, že daná posloupnost je skoro setříděná v tom smyslu, že každý prvek je nejvýš o k pozic mimo (tedy pro každý prvek je rozdíl jeho indexů v zadané a setříděné posloupnosti nejvýš k). Optimalizujte časovou složitost, tj. Ο(n log k) za tři body, Ο(nk) za dva a zbytek za jeden. Hodnotu k přirozeně neznáte. Hint: Ο(nk) je bubblesort, na Ο(n log k) stačí použít třídění haldou omezené velikosti. Velikost haldy zkoušet 2, 4, 16, 256, tj. 2^2ⁱ, dokud se to nepovede.
05. listopadu 2008	Úkoly můžete odevzdávat do 03. prosince 2008, 15:30.
rmq	2.5	Napište funkci, která dostane pole čísel A a vyrobí z něj vhodným předzpracováním nějakou datovou strukturu, která bude umět odpovídat na dotazy "jaké je maximum z hodnot A[i .. j] pro dané i a j". Předzpracování musíte zvládnout v lineárním čase, na dotazy musíte umět odpovídat alespoň v Ο(log n). Za Ο(1) na dotaz je nemalý bonus, ale pozor, je to docela těžké a pracné. Hint: Nad polem si vyrobte vhodný vyvážený binární strom a v každém vrcholu si poznamenejte maximum ze všech jeho synů. Daný interval pak rozložte tak, aby stačilo šáhnout o řádově log N vrcholů v tomto stromě.
mul	2.5	Napište funkci `mul : int array -> int array -> int array`, která násobí dvě daná dlouhá čísla. Dlouhá čísla si reprezentujte jak chcete, jenom typ této reprezentace musí být `int array`. Triviální řešení v Ο(N²) za bod, lepší než kvadratické za dva a půl (a šílená řešení mohou dostat i bodů víc :–). Hint: http://en.wikipedia.org/wiki/Karatsuba_algorithm
maxpath	2	Mějme obecné stromy typu `type 'a tree = Node of 'a * 'a tree list`. Napište funkci `maxt : 'a tree -> 'a list`, která dostane strom a vrátí jednu z nejdelších cest v tomto stromě. Cestu vraťte jako seznam hodnot typu `'a`. Hint: Jedno procházení do hloubky, v každém vrcholu si spočtěte dvě nejdelší cesty z něj dolů do listů. Nakonec si vyberte vrchol, ve kterém je součet těchto dvou cest maximální.
perm	2.5	Napište funkce `rank : int array -> int` a `unrank : int -> int -> int array`. Funkce `rank` dostane permutaci a vrátí její pořadové číslo, funkce `unrank` dostane délku permutace, její pořadové číslo a vrátí tuto permutaci. Samozřejmě jsou `rank` a `unrank` inverzní, ale jinak může být očíslování permutací libovolné (nemusí být například lexikografické). Předpokládejte, že se pořadové číslo permutace vejde do `int`u. Plný počet bodů jenom za lineární složitost obou funkcí. Hint: http://citeseer.ist.psu.edu/myrvold00ranking.html
12. listopadu 2008	Úkoly můžete odevzdávat do 10. prosince 2008, 15:30.
short01	2	Napište funkci `short01 : int -> byte list`, která dostane číslo N a najde takové nenulové přirozené číslo, které má v desítkovém zápisu jenom nuly a jedničky, je dělitelné číslem N a jeho desítkový zápis je nejkratší možný. Toto číslo vraťte po cifrách v seznamu, v pořadí od nejméně důležité cifry (od jednotek). Body podle složitosti. Hint: Prohledávání do šířky. Vrcholy jsou zbytek po dělení N (na začátku jsem ve vrcholu s hodnotou 1), hrany jsou přidání nuly nebo jedničky na konec čísla. Hledám nejkratší cestu do nuly.
min1	2	Napište funkci `min1 : int -> byte list`, která dostane číslo N a najde takové nenulové přirozené číslo, které má v desítkovém zápisu jenom nuly a jedničky, je dělitelné číslem N a jeho desítkový zápis obsahuje nejmenší možný počet jedniček. Toto číslo vraťte po cifrách v seznamu, v pořadí od nejméně důležité cifry (od jednotek). Body podle složitosti. Hint: Jako minulá úloha, jenom musíme chytřeji provádět prohledávání grafu (hrany odpovídající přidání nuly jsou zadarmo).
zs	4	Pouze F# Mějme čísla x₁, x₂, ..., x_N a definujme hodnoty z_i jako součin všech x_j kromě x_i, takže z_i = Π_j<>i x_j. Vaším úkolem bude spočítat všechny z_i, přičemž nesmíte používat žádné jiné operace než násobení (speciálně ne dělení). Napište tedy funkci `zs : int [] -> seq<int>`. Tato funkce dostane na vstupu hodnoty x_i a vytvoří sekvenci, která vrátí postupně hodnoty z₁, z₂, ..., z_N. Vaším úkolem je co nejvíce šetřit časem a pamětí, přičemž uvažujeme časovou a paměťovou složitost pro spočtení všech z_i. Čas Ο(N) a paměť Ο(N): +1 bod Čas Ο(N) a paměť Ο(√N): +1 bod Čas Ο(N log N) a paměť Ο(log N): +2 body Řešení můžete poslat několik a body se sčítají podle toho, co splníte. Všimněte si, že pokud splníte druhou variantu, splnili jste automaticky i první variantu. Hint: Předpočítáním si pro každé i součin x_ix_i+1...x_N od konce dostanu první variantu. Pokud si z těchto hodnot pamatuji pouze každou √N-tou, dostanu √N bloků. Každý vyřeším tak, že si hodnoty v něm spočtu z oné jedné zapamatované hodnoty do pomocné paměti o velikosti √N. Variantu s log N pamětí neporadím :)
19. listopadu 2008	Úkoly můžete odevzdávat do 17. prosince 2008, 15:30.
grep	1.5	Napište program, který jako parametr dostane regulární výraz, zpracovává standardní vstup a vypisuje ty řádky, které tomuto výrazu odpovídají. Umožněte ještě, aby bylo možno před regulárním výrazem zadat swištík `-v`, který způsobí, že se budou vypisovat řádky, které nevyhovují. Hint: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regex_members.aspx
hist	2	Napište program, který načte řádky ze standardního vstupu a vypíše jejich histogram (tj. informace `řádka vstupu` a `její četnost`) setříděný od nejčastějších řádek. Takže program dělá přibližně to, co `sort \| uniq -c \| sort -nr`. Hint: Hešování nebo stromečky :–)
sed	2.5	Pouze F# Napište program, který jako první parametr dostane v jazyce F# zdrojový kód nějaké funkce typu `string -> string`. Program pak načítá řádky standardního vstupu, na každý spustí tuto funkci a pokud vrátí neprázdný řetězec, vypíše ho na standardní výstup. Tahle úloha je dost technická, ale pokud by vás bavila, můžete začít třeba zde http://msdn.microsoft.com/en-us/library/system.codedom.compiler.codedomprovider_members.aspx nebo přímo v FSharp.Compiler.CodeDom.dll nebo FSharp.Compiler.dll.
dehash	3	Mějme nějakou funkci `f : int -> int`, přičemž víme, že posloupnost 0, f(0), f(f(0)), ..., je periodická, takže nějaké f^N(0) je rovno nějaké předchozí hodnotě. Vaším cílem je, když dostanete libovolnou takovou funkci f, provést nějaké předzpracování a pak umět odpovídat na otázky "když dostanu x, pro jaké y je f(y) = x"? Přičemž pro x, které jsou v posloupnosti 0, f(0), f(f(0)), ..., musíte odpovědět vždy správně, a pro x, která nejsou, řekněte, že nevíte. Napište tedy funkci typu `dehash : (int -> int) -> (int -> int option)`. Pro plný počet bodů musí předzpracování trvat Ο(N), musí si vystačit s ostře méně než Ο(N) paměti a odpovídat na otázky musíte umět také ostře lépe než v čase Ο(N). Hint: Hodnoty funkce f tvoří ocásek a pak cyklus. Na ocásku i cyklu si pamatujte každou odmotnintou hodnotu a u každé si pamatujte, jaká odmocnintá hodnota je před ní. Když poté hledáte vzor x, jděte z x pořád dál, než narazíte na uloženou hodnotu, skočte na jejího předchůdce a jděte směrem k x.
26. listopadu 2008	Úkoly můžete odevzdávat do 07. ledna 2009, 15:30.
upword	2	Napište funkci `upword : string -> string -> string`, která dostane a a b a vrátí co nejkratší slovo, jehož jsou a i b (ne nutně souvislá) podslova. Hint: http://en.wikipedia.org/wiki/Shortest_common_supersequence_problem
decrypt	2.5	Máme zprávu, která se skládá ze znaků `'a'`..`'z'`, které si očíslujeme 0..25. Posun písmene i o k je písmeno (i+k) mod 26 a posun celé zprávy o k je posun všech jejích písmen o k. Napište funkci `decrypt : string -> string -> string`, která dostane zprávu posunutou o neznámou hodnotu k. Dále dostane nějaký text v jazyce, ve kterém je zašifrovaná zpráva. Cílem je vrátit jeden z posunů dané zašifrované zprávy, a to ten nepravděpodobnější. Pravděpodobnost nějaké zprávy můžete měřit například frekvencí jednotlivých znaků ('e' je v češtině nejpravděpodobnější, 'w' velmi málo pravděpodobné atd.). Hint: http://en.wikipedia.org/wiki/Frequency_analysis
cmprs	5	Napište konzolové programy `cmprs` a `uncmprs`. Tyto programy dostanou na příkazové řádce právě jedno jméno souboru, který zabalí/rozbalí. Kompresní metoda by měla být jedna z následujících: Huffmanovo kódování nebo aritmetické kódování (případně i s BWT za dva bonusové body) či nějaká varianta LZ*. Koncovku zabaleného souboru si vyberte sami. Mělo by to být celé v `F#`, rozumně efektivní a na plný počet bodů byste měli i testovat integritu rozbaleného souboru (spočítat si nějaké CRC při zabalování a to po rozbalení zkontrolovat).
03. prosince 2008	Úkoly můžete odevzdávat do 14. ledna 2009, 15:30.
abcd	3	Abeceda ztraceného národa Atlantiďanů se skládala z nějaké podmnožiny Unicode znaků. Bohužel už není známo uspořádání těchto znaků, ale víte, že bylo lineární. Získali jste kus slovníku, tedy několik slov, která jsou lexikograficky setříděná. Předpokládejte, že písmena těchto slov tvoří kompletní atlantidskou abecedu. Vaším úkolem je nalézt lineární uspořádání písmen v abecedě, případně říct, že ho z daných slov nejde stanovit. Napište tedy funkci \|abcd::string list -> char list option\|, která dostane lexikograficky setříděná slova a pokud je možné určit jednoznačné lineární uspořádání všech písmen v těchto slovech, vrátí ho, jinak vrátí `None`. Můžete předpokládat, že data jsou konzistentní.
diff	4	Napište konzolový program `diff`, který dostane na příkazové řádce dva soubory (pokud jeden chybí, tak je to standardní vstup) a najde diff, tj. nejmenší počet řádek, které je třeba odstranit či přidat, aby se z prvního souboru stal druhý. Na výstup (jako diff -u) vypište nezměněné řádky s mezerou na začátku, odstraněné s - na začátku a přidané s + na začátku. Program musí fungovat se složitostí Ο(délka_delšího_souboru velikost_diffu), za nic jiného body nejsou (složitost Ο(délka_jednoho * délka_druhého)* je totiž pro velké soubory s malým počtem změn nepoužitelná).
10. prosince 2008	Úkoly můžete odevzdávat do 22. února 2009, 23:59.
volume	4.5	Obdélkík, jehož strany jsou rovnoběžné s osamy, můžeme reprezentovat souřadnicemi dvou protilehlých rohů jako `float * float * float * float`. Napište funkci `volume : (float * float * float * float) list -> float`, která dostane několik obdélníku, jejichž strany jsou rovnoběžné s osami, a spočte obsah jejich sjednocení. Za kvadratické řešení je 2.5 bodu, za Ο(N log N) je plný počet 4.5 bodu.
eval	3	Napište funkci `eval : string -> float`, která dostane na vstupu řetězec obsahující výraz a vrátí jeho hodnotu. Musíte umět celá a desetinná čísla, binární operátory `+`, `-`, `*`, `/`, `^` včetně priorit, funkce `exp` a `log` a závorky. Daný výraz může obsahovat libovolné počty mezer. Hint: Můžete použít parsování z hodiny, ale také libovolné jiné.
deriv	1.5	Pokud vyřešíte úlohu `eval`, napište funkci `diff : string -> string`, která zderivuje daný výraz. Oba výrazy jsou v již popsaném formátu, jenom smí obsahovat ještě proměnnou `x`. Výsledný výraz nemusí být nijak zjednodušen, ale je možné za to přidělit body navíc.
vareval	1.5	Pokud vyřešíte úlohu `eval`, napište funkci `vareval : string -> float`. Výraz na vstupu je v popsaném formátu, jenom může obsahovat konstrukci `let prom = a in b`, kde `prom` je řetězec malých písmen, `a` a `b` jsou výrazy a ve výrazu `b` se může objevit proměnná `prom`, která bude mít hodnotu výrazu `a`. Oba výrazy `a` a `b` mohou uvnitř samozřejmě obsahovat další `let`y, například jako `1 + let a = 3 * let b = 3 in 1+b in a^2`. Výraz za `in` parsujte nejdelší možný (takže je ukončen jenom jiným `in` nebo pravou závorkou).
17. prosince 2008	Úkoly můžete odevzdávat do 22. února 2009, 23:59.
crawler	4	Napište webový crawler. To je konzolový program, který dostane seznam dvojic (url, regexp) a číslo S. Crawler stáhne všechny stránky na seznamu. Z každé stránky vyextrahuje odkazy a ty, které matchují danému regexpu, opět stáhne, a odkazy na nich, které matchují danému regexpu, opět rekurzivně stáhne... V jednom časovém okamžiku stahujte najednou S stránek a jedno konkrétní url stahujte nanejvýš jednou.
web	3	Napište jednoduchý webserver. Webserveru při spuštění dáte port a adresář, ze kterého má obsluhovat. Webserver pak sedí na daném portu. Když se ho někdo zeptá, obslouží ho, a obsluhovat zvládne libovolně lidí najednou. Implementujte HTTP 0.9, přičemž byste měli v adresách umět dekódovat "%xy", viz zde. Mělo by to fungovat natolik, aby se se serverem dokázaly mé prohlížeče (Opera, Firefox) bavit.
chat	3	Napište jednoduchý chatovací server. Server by měl poslouchat na zadaném portu. Připojit se může libovolný počet lidí. Když se někdo připojí, tak na první řádce napíše svůj nickname. Každá dalšá řádka od něj se pošle všem ostatním připojeným (těm, kteří už poslali nickname) ve formátu "nickname: řádka".

Stav (25. 05. 2018)

Jméno	Odevzdané úkoly	Body

Zpět