Zadání druhého zápočtového projektu Základy algoritmizace, 2005 Jiří Dvorský 2. května 2006
Obecné pokyny • Celkem je k dispozici 8 zadání příkladů. Každý student obdrží jedno zadání. • Vzhledem k tomu, že odpadly pondělní cvičení, majáles atd. a tudíž část z Vás by mohla vybrané zadaní nahlásit cvičícímu až dost pozdě, rozhodl jsem se, že příklady Vám budou přiděleny. Z čísla Vašeho loginu vezmete koncové trojčíslí resp. dvojčíslí, z něho spočítáte zbytek po dělení 8. Tím dostanete číslo v rozmezí 0 až 7. K němu pak přičtete 1 a dostáváte číslo příkladu. Pro Vaší informaci, tato jednoduchá metoda rozděluje příklady mezi Vás zhruba stejně dobře jako složitá hašovací funkce. Příklad: já mám login dvo26, takže 26 modulo 8 je 2 plus 1 je 3. Takže bych měl příklad číslo 3. • Příklady proberu na přednášce 9. a 10. května. • Na mém webu jsou k dispozici ke každému příkladu testovací vstupy. Na těchto vstupech bude příslušný cvičící Vaše programy testovat. • Abyste měli kontrolu, zda Váš program funguje správně, jsou zde i výstupy z mých kontrolních programů. Tudíž si můžete sami výsledek Vašeho programu porovnat (u příkladu 8 se může stát, že se Vaše výstupy budou díky zaokrouhlovacím chybám lišit na posledních desetinných místech, neměly by se však lišit zásadně – třeba o desetiny). • Z předchozího bodu plyne, že jsem všechny příklady naprogramoval. Z toho dále plynou, že: 1. doba běhu žádného z osmi programů nepřekročila cca minutu, dvě (Pentium 4, 2.4 GHz), 2. napsání žádného programu mi netrvalo více než hodinku – s rezervou na kafe. Tudíž Vám by to nemělo zabrat déle než odpoledne či dvě. Nejsou to žádné „nevyřešitelné příklady.
1
1. příklad – Sjednocení dvou množin Jsou dány dvě množiny A = {a1 , a2 , . . . , an } a B = {b1 , b2 , . . . , bm }, kde ai , bi , n, m ∈ N . Napište program, který sestrojí sjednocení C = A ∪ B.
Ukázka Jestliže A = {2, 3, 5} a B = {1, 3, 4, 5} pak C = A ∪ B = {1, 2, 3, 4, 5}
2. příklad – Průnik dvou množin Jsou dány dvě množiny A = {a1 , a2 , . . . , an } a B = {b1 , b2 , . . . , bm }, kde ai , bi , n, m ∈ N . Napište program, který sestrojí průnik C = A ∩ B.
Ukázka Jestliže A = {2, 3, 5} a B = {1, 3, 4, 5} pak C = A ∩ B = {3, 5}
3. příklad – Rozdíl dvou množin Jsou dány dvě množiny A = {a1 , a2 , . . . , an } a B = {b1 , b2 , . . . , bm }, kde ai , bi , n, m ∈ N . Napište program, který sestrojí rozdíl C = A − B.
Ukázka Jestliže A = {2, 3, 5} a B = {1, 3, 4, 5} pak C = A − B = {2}.
Poznámky k příkladům 1 až 3 • Vstupem do programu budou dva textové soubory, které budou obsahovat sekvence čísel, na každém řádku jedno číslo. Čísla budou v rozsahu 0 ≤ x < 108 , čísla se mohou (a určitě budou) opakovat. Počet čísel bude v obou souborech shodný – 106 . • Jak už to v životě bývá, data přicházející od uživatelů většinou nebývají ve formě, kterou bychom mohli ihned zpracovat. Množiny se kterými se bude pracovat je nutné nejprve z daných sekvencí vytvořit - odstranit duplicity. • Výstupem z programu bude textový soubor, na každém řádku bude jedno číslo z Vaší výsledné množiny. Čísla budou seřazena vzestupně. • Jména vstupních souborů a výstupního souboru se budou zadávat jako argumenty z příkazové řádky ve tvaru: VasProgram Vstup1 Vstup2 Vystup • Vzhledem k rozsahu množin není možné využít naivní algoritmus, spočívající v porovnání „každého prvku s každým. Složitost tohoto algoritmu je O(n2 ), což pro n = 106 činí 1012 ! Výsledku byste se taky nemuseli dočkat.
2
4
d
2 1
6 3
f
b a
5
(a) Strom T1
c
e
(b) Strom T2
4 2 1
β
6 3
7
(c) Strom T3
α
γ
(d) Strom T4
Obrázek 1: Ukázky stromů • Klíčem k úspěchu je využití některého ze třídících algoritmů nebo datových struktur, možností řešení je relativně mnoho. Při některých způsobech řešení není dokonce nutné vytvářet množinu (odstraňování duplicit atd.) dopředu, je možné zpracovávat přímo sekvenci čísel ze vstupních souborů.
4. příklad – Struktura stromů Na vstupu jsou dány dva binární vyhledávací stromy A a B. Napište program, který rozhodne, zda dané dva stromy mají shodnou strukturu. Struktura stromu je nezávislá na datech ve stromu uložených, jde pouze o existenci či neexistenci uzlů a hran mezi nimi.
Ukázka Uvažujme stromy na obrázku 1. Shodnou strukturu se stromem T1 má strom T2 , přestože obsahují různá data. Strom T1 a strom T3 nemají shodnou strukturu – z uzlu označeném číslem 6 vede v jednom případě hrana doleva v druhém případě vede doprava (lhostejno, že jeden uzel obsahuje číslo 5 a druhý 7). Pochopitelně, každý strom má shodnou strukturu sám se sebou.
Poznámky • Předpokládejte, že oba stromy nebudou prázdné. • Stromy budou obsahovat pouze celá čísla (typ int). • Stromy budou zadány ve formě textového souboru jako posloupnost čísel, na každém řádku bude pouze jedno číslo. • Stromy ze souborů získáte tak, že čísla načítaná postupně z textového souboru budete vkládat, pomocí obvyklého algoritmu, do binárního vyhledávacího stromu (jednoduchá, nevyvážená varianta).
3
• Jména dvou vstupních souborů se stromy budou zadána jako parametr příkazové řádky ve tvaru: VasProgram Vstup1 Vstup2 • Výsledek vypíše Váš program na konzolu ve tvaru „Stromy maji/nemaji shodnou strukturu, žádná jiná informace se nepožaduje. • V tomto příkladě máte opět několik možností řešení. Jednak můžete vhodným způsobem systematicky projít oba dva stromy, výsledky průchodů si uložit nejlépe lineárním způsobem a tuto lineární formu obou stromů pak navzájem porovnat. Druhou možností je systematicky procházet oba stromy najednou a porovnávat je „on-line. • Uvědomte si, že data uložená v uzlech Vás vlastně ani nemusí zajímat. Data načítaná ze vstupních souborů slouží jen k tomu, aby se dal binární strom nějakým (opakovatelným) způsobem poskládat.
5. příklad – Podstromy Na vstupu jsou dány dva binární vyhledávací stromy A a B. Napište program, který rozhodne, kolikrát se daný strom B vyskytuje ve stromu A jako podstrom. Stejně jako v předchozím příkladu je struktura stromu je nezávislá na datech ve stromu uložených, jde pouze o existenci či neexistenci uzlů a hran mezi nimi.
Ukázka Uvažujme stromy na obrázku 1. Předpokládejme, že jako podstrom budeme uvažovat strom T4 . Ve stromu T1 se jako podstrom vyskytuje pouze jednou: α ↔ 1, β ↔ 2, γ ↔ 3. Protože strom T2 má shodnou strukturu jako strom T1 je počet výskytů stejný: α ↔ b, β ↔ d, γ ↔ f . Pochopitelně, každý strom je sám sobě podstromem s počtem výskytu 1. V obou stromech jsou možné další dva výskyty podstromu: • α ↔ 2, β ↔ 4, γ ↔ 6 • α ↔ a, β ↔ b, γ ↔ c V tomto případě si ale neodpovídají hrany u uzlů α, γ a 2, 6 resp. b, f . U uzlů α a γ hrany vedoucí dál neexistují, u uzlů 2, 6 resp. b, f existují hrany vedoucí dále. Proto tento výskyt neuvažujte – uvažujte jen výskyty přesně odpovídající danému podstromu.
Poznámky • Předpokládejte, že oba stromy nebudou prázdné. • Stromy budou obsahovat pouze celá čísla (typ int). • Stromy budou zadány ve formě textového souboru jako posloupnost čísel, na každém řádku bude pouze jedno číslo.
4
n-gram a b c d r
četnost 5 2 1 1 2
Tabulka 1: Výsledné 1-gramy • Stromy ze souborů získáte tak, že čísla načítaná postupně z textového souboru budete vkládat, pomocí obvyklého algoritmu, do binárního vyhledávacího stromu (jednoduchá, nevyvážená varianta). • Jména dvou vstupních souborů se stromy budou zadána jako parametr příkazové řádky ve tvaru: VasProgram SouborSeStromem SouborSPodstromem • Výsledek vypíše Váš program na konzolu ve tvaru „Pocet vyskytu podstromu: nnnnn, žádná jiná informace se nepožaduje. • V tomto příkladě je asi nejlepším řešením nějakým vhodným způsobem systematicky projít oba dva stromy, výsledky průchodů si uložit nejlépe lineárním způsobem a potom určit kolikrát se lineární forma podstromu vyskytuje ve „velkém stromu. • Uvědomte si, že data uložená v uzlech Vás vlastně ani nemusí zajímat. Data načítaná ze vstupních souborů slouží jen k tomu, aby se dal binární strom nějakým (opakovatelným) způsobem poskládat.
6. příklad – Četnost n-gramů Na vstupu je dán řetězec délky m, A = a1 a2 . . . am . Sestavte tabulku četnosti všech n-gramů obsažených v řetězci A. n-gram je definován jako řetězec B = b1 b2 . . . bn délky n, který je podřetězcem řetězce A. Výslednou tabulku n-gramů setřiďte podle abecedy a spolu s jejich četnostmi vypište do textového souboru ve tvaru: n-gram četnost n-gram četnost .. .. . . n-gram
četnost
Ukázka Mějme řetězec A = abracadabra. Výsledek pro n = 1 je uveden v tabulce 1, pro n = 2 v tabulce 2 a pro n = 3 pak v tabulce 3.
Poznámky • Řetězec A bude uložen ve vstupním textovém souboru.
5
n-gram ab ac ad br ca da ra
četnost 2 1 1 2 1 1 2
Tabulka 2: Výsledné 2-gramy n-gram abr aca ada bra cad dab rac
četnost 2 1 1 2 1 1 1
Tabulka 3: Výsledné 3-gramy • Vstupní text je v angličtině, psán pouze malými písmeny, znaky s diakritikou se nebudou vyskytovat. V textu se mimo písmen mohou vyskytovat pouze mezery. Mezera se bere do úvahy při vytváření n-gramů z daného textu. • Parametr n předpokládejte v intervalu 1 ≤ n ≤ 100. • Jméno vstupního souboru, parametru n, jméno výstupního souboru bude zadáno jako parametr příkazové řádky ve tvaru: VasProgram Vstup n Vystup • Pro úspěšné vyřešení tohoto příkladu je nutné navrhnout datovou strukturu, jednak pro rychlé vkládání nových n-gramů a jednak pro rychlé vyhledávání již nalezených n-gramů (těm se pouze inkrementuje četnost výskytu). Uvědomte si, že n-gramy nemusí být v průběhu zpracování textu ve Vaší datové struktuře nezbytně nutně setříděny. Abecední setřídění všech nalezených n-gramů lze provést až nakonec. Lze ovšem navrhnout datovou strukturu, která bude n-gram rovnou i třídit.
7. příklad – Četnost slovních kontextů Je dán textový soubor. Spočtěte četnost všech dvojic sousedních slov tj. dvojic slov, které spolu v textu bezprostředně sousedí. Výsledný seznam dvojic slov setřiďte sestupně (od největšího k nejmenšímu) podle četnosti výskytu dvojic slov a vypište do textového souboru ve tvaru:
6
Dvojice slov mouse mouse mouse monitor computer mouse monitor computer
Četnost 2 2 2 1
Tabulka 4: Tabulka četností dvojic slov první slovo dvojice první slovo dvojice .. .
druhé slovo dvojice druhé slovo dvojice .. .
četnost četnost .. .
první slovo dvojice
druhé slovo dvojice
četnost
Ukázka Je dán tento vstupní text: computer mouse monitor. computer, mouse; mouse mouse monitor. V textu se tedy vyskytují slova: monitor, mouse a computer. Dvojice slov jsou tyto: computer mouse, mouse monitor, monitor computer, computer mouse, mouse mouse, mouse mouse, mouse monitor. Výsledkem je tabulka 4.
Poznámky • Vstupní text je v angličtině, psán pouze malými písmeny, znaky s diakritikou se nebudou vyskytovat. • Slovo je definováno jako souvislá posloupnost znaků z množiny {a, . . . , z}. • Za dvojice sousedních slov se považují i ty dvojice, které jsou odděleny konci řádků, interpunkčními znaménky atd. • Položky seznamu jsou setříděny nejprve podle četnosti. Položky které mají stejnou četnost se třídí dále podle prvního slova ve dvojici a pokud je i první slovo stejné, třídí se nakonec podle druhého slova. Ve všech případech se třídí sestupně. • Jméno vstupního textového souboru, jméno výstupního souboru bude zadáno jako parametr příkazové řádky ve tvaru: VasProgram Vstup Vystup • Pro úspěšné vyřešení tohoto příkladu je nutné navrhnout datovou strukturu, jednak pro rychlé vkládání nových dvojic slov a jednak pro rychlé vyhledávání již nalezených dvojic slov (těm se pouze inkrementuje četnost výskytu). • Setřídění podle četnosti výskytu je možné provést až nakonec, kdy už jsou známy konečné hodnoty jednotlivých četností.
7
Slovo computer mouse monitor
Četnost 3 4 2
Pravděpodobnost 3/9 4/9 2/9
Entropie [bity] 1,584962501 1,169925001 2,169925001
Tabulka 5: Výpočet entropie mouse computer monitor
1,169925001 1,584962501 2,169925001
Tabulka 6: Výsledek výpočtu entropie
8. příklad – Entropie slov v textu Je dán textový soubor. Vypočtěte entropii všech různých slov, které se v textu vyskytují. Výsledný seznam slov setřiďte vzestupně podle entropie a vypište do textového souboru ve tvaru: slovo slovo .. .
entropie entropie .. .
slovo
entropie
Entropie H(A) jevu A, který nastane s pravděpodobností pA je definována jako: H(A) = − log2 pA Jednotkou entropie je jeden bit. V našem případě jsou za jevy považována všechna různá slova v textu. Pravděpodobnost určíme jako podíl četnosti daného slova ku celkové četnosti všech slov.
Ukázka Je dán tento vstupní text: computer mouse monitor. computer, mouse; mouse mouse monitor. computer V textu se vyskytují tato unikátní slova: monitor, mouse a computer. Celková četnost všech slov je 9. Jednotlivé kroky výpočtu jsou uvedeny v tabulce 5. Výsledný seznam slov je uveden v tabulce 6.
Poznámky • Vstupní text je v angličtině, znaky s diakritikou se nebudou vyskytovat. • Slovo je definováno jako souvislá posloupnost znaků z množiny {a, . . . , z}. • Jméno vstupního textového souboru, jméno výstupního souboru bude zadáno jako parametr příkazové řádky ve tvaru: VasProgram Vstup Vystup 8
• Pro úspěšné vyřešení tohoto příkladu je nutné navrhnout datovou strukturu, jednak pro rychlé vkládání nových slov a jednak pro rychlé vyhledávání již nalezených slov (těm se pouze inkrementuje četnost výskytu). • Výpočet entropie a setřídění výsledků podle této veličiny je možné provést až nakonec, kdy už jsou známy konečné hodnoty jednotlivých četností.
9
