Toto je stránka cvičení předmětu Algoritmy a datové struktury 2, který se koná v ZS 2017/2018.
Cvičení probíhá každé pondělí v 10:40 v S8 (Malostranské náměstí, 1. patro).
Průběh cvičení
Cvičení bude probíhat klasicky, to jest společným řešením příkladů s občasnou nápovědou. Můžeme také občas zopakovat látku z přednášky, pokud o to budete stát.
Účast na samotné hodině není povinná, přesné podmínky zápočtu najdete níže.
Podmínky zápočtu
Abyste dostali zápočet, budete potřebovat:
- alespoň 30 bodů z 3 písemek, z čehož každá bude za 20 bodů.
- alespoň 30 bodů z domácích úkolů, které budou celkem za (alespoň) 60 bodů.
Domácí úkoly budou vydavány co dva týdny. Písemky budou vyhlášeny alespoň 14 dní dopředu emailem a na cvičení.
Studijní materiály
- Zbrusu nová knížka http://pruvodce.ucw.cz/ od Martina Mareše a Toma Vally. Pokrývá velkou část semestru.
- Spoustu domácích úkolů k samořešení najdete na stránkách dřívějších cvičení Martina Mareše.
- Stránky dalších cvičení, kde se dají najít přiklady: Karel a Verča, Tomáš Masařík
Konzultace
Nemám vypsané pevné konzultační hodiny, ale moc rád se s vámi sejdu a pomohu vám individuálně nebo v malých skupinkách s jakýmikoli dotazy k cvičení nebo přednášce. Od druhého týdne semestru tu bude Google formulář, kam se můžete napsat, pokud budete chtít konzultaci.
Kromě přímé konzultace budu dostupný i skrze email.
Co bylo
- 1: Opakování terminologie řetězcových algoritmů, dolní odhad na složitost naivního algoritmu pro hledání v textu, hrátky s rotací.
- 2: Vyhledávání v textu. Byl jsem nemocný, zaskočil loni oceněný nejlepší cvičící Pavel Veselý.
- HW1, termín 24. října, 08:00.
- 3: Suffixove stromy. Uzitecna datova struktura, jejiz pouzitim jde vyresit mnoho retezcovych problemu. Jen ta konstrukce...
- 4: Toky v sitich. Souvislost s linearnimi nerovnicemi, slozitost Ford-Fulkersona s nejkratsimi cestami.
- 5: Dinicův algoritmus. Zlepšování složitosti pro celočíselné hrany, škálování kapacit bit po bitu.
- 6: Aplikace toků, metoda tří Indů..
- HW2, termín 20. listopadu, 08:00.
- 13. 11. byla prvni pisemka. Obsahovala tri priklady na aplikace ci modifikace algoritmu pro toky a retezce.
- 7: Hradlové sítě. Definice a motivace studia hradel. Ekvivalence malých hradel. Důkaz, že existuje Booleovská funkce, která potřebuje exponenciálně hradel.
- 8: Třídící sítě. Z minula: práce s funkcí PARITY, proč je hloubka obvodů důležitá. Nula-jedničkový princip.
- HW3, termín 11 prosince, 08:00.
- 9: Konstrukce hradlových a třídících sítí..
- 10: Geometrické algoritmy. Nedělali jsme příklady na Voronného diagramy a Delaunayho triangulaci.
- HW4, termín 16. ledna, 08:00.
- HW5, termín 16. února, 08:00.
- 8. ledna bude třetí, poslední písemka. Obsahovat bude vše ze semestru, včetně NP-úplných problémů (viz úkol 4).
Body
Proběhla jedna písemka a dvě sady domácích úkolů; body se zde brzy objeví.