Cvičení z algoritmů a datových struktur I, TIN060


Cvičení se koná v pondělí v 12:20 v S6.

Podmínky k získání zápočtu

Zápočet získáte za odevzdání dvou časově omezených úkolů a vypracování zápočtové práce. Ta by měla obsahovat popis některého zajímavého a netriviálního algoritmu, ať už z přednášky nebo odjinud. Takový text by měl obsahovat to, jak algoritmus funguje, proč funguje a jakou má časovou a paměťovou složitost. Co přesně musíte udělat:
  1. V termínu odevzdat první a druhý domácí úkol. Úkoly budou oznámeny na cvičení a na webových stránkách alespon s měsíčním předstihem.
  2. Domluvit se se mnou do konce semestru, tj. do 27. 5. 2011 mailem na tématu zápočtové práce. Inspirace například v seznamu Martina Mareše. Pokud jsme nějaké téma dopodrobna rozebrali na cvičení, tak se mi nejspíš nebude líbit. Jedno téma je nanejvýš pro 3 lidi, aby se témata moc neopakovala.
  3. Poslat mi zápočťák. Většinou po krátké iteraci dostanete zápočet, ale mohu požadovat i osobní předvedení.

Témata by se neměla moc opakovat, takže jedno téma povoluji nanejvýš třem lidem.

Seznam domácích úkolů

Domácí úkoly se odevzdávají v CodExu, ve skupině ADS1-Straka. Do této skupiny vás mohu přiřadit jenom já, takže až budete mít v CodExu účet, napište mi mail, přiřadím vás do ní. Úkoly řešte jednotlivě, takže neodevzdávejte cizí řešení, protože je budu ručně kontrolovat. Pokud na nějaké zkopírované narazím, nikomu z účastníků nedám zápočet.

Načítání vstupu v C# v CodExu

Pro načítení vstupu v C#, který se skládá z mnoha čísel, je možné použít třídu Reader.cs. Tu najdete v CodExu v sekci 'Uvítací stránka'. V CodExu je váš program s touto třídou kompilován automaticky, stačí přidat using CodEx, doma ji musíte přikompilovávat ručně. Pomocí ní můžete načíst další číslo ze standardního vstupu jako Reader.Console().Int(). Kromě čísel jde načítat ještě Char, Double, Word a Line.

Seznam přidělených zápočtových prací.

Obsah cvičení (03. 10. 2011)

DatumObsah
21. února 2011Řešené příklady:
  • Definice asymptotické časové složitosti, symbolu Ο a Θ.
  • Určete, co dělají následující funkce a jak dlouho jim to trvá:
    f(x,y) = if x==0 then y
                     else f((x AND y) * 2, x XOR y)
    g(x,y) = if y==0 then 0
                     else 2 * g(x, y/2) + x * (y AND 1)
    h(x,y) = if x<y then (0,x)
             else (a,b) <- 2 * h(x/2, y) + (0, x AND 1)
                  if b≥y then (a+1, b-y) else (a, b)
28. února 2011Řešené příklady:
  • Máme v vajíček a panelák o N patrech. Cílem je najít na co nejméně pokusů nejnižší patro, ze kterého když hodíme vajíčko, tak se rozbije [v * N1/v pokusů].
  • V matici s nulami a jedničkami najděte největší podmatici složenou za samých nul [Ο(NM)].
7. března 2011Řešené příklady:
  • Mějme čísla x1, x2, ... xN a definujme hodnoty zi jako součin všech xj kromě xi, takže zi = Πj<>i xj. Vaším úkolem bude spočítat všechny zi, přičemž nesmíte používat operaci dělení (tj. jenom násobení). Snažte se co nejvíce šetřit pamětí (čas Ο(N) a paměť Ο(N), čas Ο(N) a paměť Ο(√N), čas Ο(N log N) a paměť Ο(log N)).
  • Pokud byste mohli s libovolně dlouhými celými čísly pracovat v konstantním čase, navrhněte algoritmus na vynásobení dvou matic v čase Ο(n2).
  • Pomocí rekurze vynásobte dvě celá n-bitová čísla v čase Ο(nlog2 3).
14. března 2011Řešené příklady:
  • Čtverečkové bludiště, vy, poklad, stěny a prázdná políčka. Najděte nejkratší cestu k pokladu.
  • Čtverečkové bludiště, vy, poklad, stěny, prázdná políčka a pasti. Pastí jdete třikrát tak dlouhou dobu jako normálním políčkem. Najděte nejkratší cestu k pokladu.
  • Čtverečkové bludiště, vy, poklad, stěny a prázdná políčka. Máte krumpáč, kterým jde prokopnout libovolná stěna. Najděte nejkratší cestu k pokladu, na které prokopnete minimum stěn.
  • Čtverečkové bludiště, vy, poklad a zdroje radioaktivity – každé políčko má konkrétní úroveň radioaktivity. Nalezněte nejkratší cestu k pokladu, na které je maximální úroveň radioaktivity co nejmenší.
  • Čtverečkové bludiště, vy, poklad, stěny, prázdná políčka, dveře tří barev (R, B, Y), klíče tří barev (r, b, y). Dveře nemůžete projít, když nemáte klíč odpovídající barvy. Najděte nejkratší cestu k pokladu.
  • Čtverečkové bludiště, vy, poklad, stěny, prázdná políčka, Minotaurus a libovolný počet mečů. Minotaurus se hýbe poté, co se pohnete vy, a jde nahoru/nikam/dolu, aby se vám přiblížil; poté jde doleva/nikam/doprava, aby se vám přiblížil. Když jít nemůže, stojí. Najděte nejkratší cestu k pokladu, na které se nepotkáte s Minotaurem, aniž byste měli meč.
21. března 2011Řešené příklady:
  • V daném ohodnoceném grafu najděte kružnici délky 3 s minimálním součtem ohodnocení hran. [Ο(NM)]
  • V daném ohodnoceném grafu najděte kružnici délky 4 s minimálním součtem ohodnocení hran. [Ο(NM)]
  • V daném ohodnoceném grafu najděte kružnici délky 5 s minimálním součtem ohodnocení hran. [Ο(NM)]
  • V neohodnoceném stromě najděte nejdelší cestu.
  • V neohodnoceném stromě najděte největší housenku. Housenka je cesta, na kterou se připojují nožičky a její velikost se měří počtem jejích hran.
  • Království je strom s ohodnocenými vrcholy. Umistěte posádky do některých vrcholů tak, aby součet ohodnocení vrcholů s posádkami byl co největší a zároveň každá souvislá skupina posádek byla velikosti nanejvýš 3.
28. března 2011Řešené příklady:
  • Zuřivý robot Čenda má v paměti P instrukcí (vpřed, vlevo vbok, vpravo vbok), které pořád dokola opakuje. Pro dané bludiště NxN je vaším cílem pro každé políčko spočítat, za jak dlouho se Čenda dostane z bludiště ven, když začne na tomto políčku provádět od začátku svůj program.
  • Dostanete neorientovaný graf. Najděte všechny mosty, což jsou hrana, kterou když z grafu odstraníte, stane se nesouvislým.
  • Dostanete neorientovaný graf. Najděte všechny artikulace, což je vrchol, který když z grafu odstraníte, stane se nesouvislým.
  • Podobným algoritmem, tj. procházením orientovaného grafu do šířky, najděte komponenty silné souvislosti.
  • Obarvěte daný rovinný graf šesti barvami.
4. dubna 2011Řešené příklady:
  • Obarvěte daný rovinný graf šesti barvami.
  • Obarvěte daný rovinný graf pěti barvami.
  • Zorientujte hrany daného neorientovaného grafu tak, aby se v každém vrcholu lišil vstupní a výstupní stupeň nanejvýš o jedna.
  • Dostanete neorientovaný graf. Rozhodněte, zda ho lze nakreslit jedním tahem a pokud ano, najděte takový tah.
11. dubna 2011Řešené příklady:
  • Popište implementaci Dijkstrova algoritmu a určete jeho složitost při použití pole, binární haldy a k-regulární haldy. [Ο(N2), Ο(M log N), Ο(M logM/N N) pro k=m/n]
  • Definovali jsme amortizovanou složitost a ukázali binomiální haldy a Fibonacciho haldy.
  • Navrhněte, jak do Dijkstrova algoritmu zapojit zeměpisné souřadnice, pokud hledáte nejkratší cestu mezi městy.
18. dubna 2011Řešené příklady:
  • Najděte graf se zápornými hranami ale bez záporných cyklů, na kterém nefunguje Dijkstrův algoritmus správně.
  • Rozmyslete si, že když záporné hrany odstraníte přičtením konstanty, nejkratší cesty nezůstanou zachovány.
  • Dostali jste ohodnocení H(v) pro každý vrchol grafu takové, že pro každou hranu vzdálenost(u, v) - H(u) + H(v)≥0. Graf s ohodnoceními vzdálenost(u, v) - H(u) + H(v) tedy nemá žádné záporné hrany. Ukažte, že nejkratší cesty zůstanou v tomto grafu zachovány.
  • Dokažte funkčnosti Bellman-Fordova algoritmu.
  • Mějme gragf G s hranami ohodnocenými přirozenými čísly≤K. Implementujte Dijkstrův algoritmus se složitostí Ο(kN + m).
  • Mějme N měn, můžeme je převádět každou na každou, kurz výměny z i-té na j-tou měnu je rij. Zjistěte, zda lze měněním měn něco vydělat.
  • Dokažte funkčnosti Floyd-Warshallova algoritmu.
25. dubna 2011Velikonoce
2. května 2011Řešené příklady:
  • Popište Jarníkův algoritmus pro hledání minimální kostry, a to jeho implementace se složitostmi Ο(N2), Ο(M log N), Ο(N log N + M).
  • Popište Kruskalův algoritmus se složitostí Ο(M log N), případně Ο(M * α(M)) pokud jsou hrany již setříděné.
  • Upravte algoritmus pro hledání minimální kostry, aby fungoval inkrementálně – v grafu postupně přibývají hrany a vy po každém přidání musíte říci, jak v tuto chvíli vypadá minimální kostra [Ο(N) na přidání hrany].
  • Nalezněte druhou nejlepší minimální kostru [Ο(N2 + M)].
  • V posloupnosti nezáporných čísel a1, ..., aN najděte souvislý úsek se součtem rovným danému K.
9. května 2011Řešené příklady:
  • V posloupnosti celých čísel a1, ..., aN najděte souvislý úsek se součtem rovným danému K.
  • V daném stromě s hranami ohodnocenými celými čísly ai najděte souvislou cestu se součtem rovným danému K.
  • Zjistěte, zda se v dané posloupnosti nějaké číslo vyskytuje víckrát. [Ο(N+K) jsou-li hodnoty v rozsahu 1..K, Ο(N log N) pomocí třídění, Ο(N log N) pomocí vyvážených vyhledávacích stromů.]
  • Dostanete číslo K a potom postupně N hodnot. Po načtení hodnoty vypište velikost minimálního rozdílu mezi K posledně zadanými prvky. [Ο(N log K)]
16. května 2011cvičení odpadá
23. května 2011Řešené příklady:
  • V jeskyni je drak a přistihl vás, jak mu kradete poklad. Nyní si s ním musíte zahrát o život následující hru. Drak si myslí číslo od nuly do milionu. Vy smíte na papír napsat nejakou množinu čísel a drak vám řekne, jestli v té množině je to číslo, které si myslí. Drak ovšem může nejvýš jednou zalhat. Vymyslete řešení na co nejméně dotazů [26].
  • Z daných bodů v rovině najděte dva nejbližší [Ο(N log N)].
  • Bleší turnaj probíhá na svislé stěně, na které jsou vodorovné plošinky. Závod probíhá tak, že blecha padá, až dopadne na plošinku. Pak se rozhodne, zda půjde doleva nebo doprava, a jde, dokud nedojde na konec plošinky. Z ní pak seskočí a zase padá, dokud se nedostane na podlahu. Vítězí blecha, která přistane na podlaze jako první. Ovšem je nutné, aby žádná blecha nespadla z větší výšky než v blechometrů, jinak se totiž zarazí nožičkami do plošínky a v závodě končí. Najděte pro danou sadu plošinek nejkratší cestu [Ο(N log N)].

Zápočtové práce (27. 09. 2011)

Výsledky úkolů se aktualizují z CodExu jednou nočně.

JménoÚkol 1Úkol 2SpecifikaceZápočťákZápočet
Jaroslav Bažant100100Split červenočerných stromůOKOK
Jan Čurda100100Split červenočerných stromů
Adam Dominec100100Průsečíky mnohoúhelníka se sebou samýmOKOK
Jakub Hajič100100Isomorfismus stromůOKOK
Martin Holeček100100Kostkové šachyOKOK
Andrej Hraško100100Porovnání tříděníOKOK
Adam Juraszek100100JednotažkyOKOK
Jana Kasáková0
David Kolibáč
Miroslav Kratochvíl100100Fibonacciho soustavaOKOK
Lukáš Langer100100Fibonacciho soustava
Kateřina Nevolová100100AVL stromyOKOK
Tomáš Novella100100Porovnání tříděníOKOK
Roman Palkoci100100Dijkstrův algoritmus
Jan Pešek100100Dijkstrův algoritmusOKOK
Pavel Pilař100100Přihrádkové třídění řetězcůOKOK
Pavol Rohár100100Zápisky k přednášceOKOK
Adam Řepka
Jiří Smejkal
Jakub Suchý100100A*OKOK
Jan Šrogl100100AVL stromyOKOK
Marek Tlustý100100Červenočerné stromyOKOK
Jan Tomášek100100
Petra Vacková0Červenočerné stromy
Ivana Valchova100100AVL stromyOKOK
Jakub Velkoborský100100
David Vondrák100100Obsah a obvod sjednocení obdélníkůOKOK
Petr Vyhlas100100Červenočerné stromyOKOK
Hujer100100Otázka života, vesmíru a vůbecOKOK

Pokud byste něco potřebovali, napište mi na fox {zavináč} ucw {tečka} cz.


Zpět