Cvičení z Algoritmů a datových struktur II.

Zde budou informace pro studenty Algoritmů a datových struktur II. (2017/2018), páteční cvičení od 9:00 v učebně S11 k přednáškám J. Hrice.

Studijní materiály:

Doporučuji skripta Martina Mareše a Tomáše Vally, jakož i další literaturu, jež odkazuje Martin Mareš na svých stránkách. Dále pak doporučuji videozáznam z přednášek roku 2014.

Co se dělalo na cvičení:

  • 1. hodina (T. Gavenčiak): Vyhledávání v textu. Naivní hlednání může trvat Omega(S*T) a i u rychlého algoritmu může vypisování trvat dlouho (pokud hledám a vypisuju výskyty n slov v textu délky n, tak až n^3).
  • 2. hodina (formou osobní konzultace): Příklady z knížky ke kapitolám 13.2 a 13.3 (KMP a Aho-Corasiková).
  • 3. hodina (formou osobní konzultace): Příklady z knížky ke kapitolám 13.4 a 13.5 (Rabin-Karp).
  • 4. hodina: Úlohy na vyhledávání v textu. Zadána první série domácích úkolů.
  • 5. hodina: Úvod do toků, příklady na FF-algoritmus (14.1, 14.2, 14.3).
  • 6. hodina: Dokončení toků: Příklad sítě pro kterou FF-algoritmus ani nekonverguje k správnému řešení. Dinic (14.4), s vylepšením Tří indů a další formulační úlohy (14.7).
  • Státní svátek 17.11 Zadána druhá série domácích úkolů.
  • 7. hodina: Hradlové sítě (15.1) a Binární sčítání/násobení (15.2).
  • 8. hodina: Dokončení Hradlových sítí --- třídící sítě (15.3) Zadána třetí série domácích úkolů.
  • 9. hodina: Těžké problémy: (19.1), (19.2) a (19.3). Zadána čtvrtá série domácích úkolů.
  • 10. hodina: Velká písemka v učebně S10.
  • 11. hodina: Plán Těžké problémy: (19.5) a (19.6). Zadána pátá série domácích úkolů.
  • 12. hodina (M. Opler): Rychlá Fourierova transformace (FFT).
  • 13. hodina (M. Opler): Geometrické algoritmy: Konvexní obal, persistentní datové struktury. 6. série DU bude zadána na vyžádání, pokud by někdo ještě potřeboval získat body.

Požadavky na zápočet:

Podmínky budou velice podobné ostatním cvičením, přestože se mohou trochu lišit. Na mém cvičení vás bude čekat:

  • 1 velká písemka za 30 bodů,
  • a dále domácí úkoly 6 sérií à 10 bodů.
Kromě toho budete moci získávat bonusové body za vyřešení některých úloh na cvičení. Bonusové body lze započítat do libovolné kategorie.

Zápočet lze získat za splnění všech následujících podmínek:

  • Alespoň 15/30 bodů z písemky.
  • Alespoň 30/60 bodů z úkolů.

Pokud někdo o trochu (musí mít alespoň 30 bodů celkem) nesplní požadavky, tak přesto může dostat zápočet při ústním dozkoušení s předchozí doplňkovou písemkou, která bývá zpravidla poslední týden semestru, či až v průběhu zkouškového. Tato možnost bývá typicky těžší a kromě toho vám to sebere čas při učení se na zkoušky, takže bych doporučoval získat zápočet klasickým způsobem v semestru. Počet úloh v doplňkové písemce bude záviset na počtu bodů, chybějících do regulérního splnění podmínek.

Písemky:

Velká písemka bude na celé cvičení. Bude obsahovat 3 příklady z témat která jste probírali na cvičeních.

Domácí úkoly:

Na vyřešení domácích úkolů bude vždy alespoň 14 dní. Úkoly můžete odevzdávat na cvičení či posílat emailem v rozumném formátu.

Při vymýšlení úkolů můžete spolupracovat, chtěl bych ale abyste řešení sepsali každý sám.

  • 1.úkol odevzdávejte do 9:00 dne 10/11/2017
  • 2.úkol odevzdávejte do 9:00 dne 8/12/2017
  • 3.úkol odevzdávejte do 9:00 dne 15/12/2017
  • 4.úkol odevzdávejte do 9:00 dne 22/12/2017
  • 5.úkol odevzdávejte do 9:00 dne 12/1/2018
  • 6. série bude zadána na vyžádání, pokud by někdo ještě potřeboval získat body.

Obecně:

Všechny kroky se snažte pečlivě zdůvodnit, je to důležitější než mít správný výsledek. Naopak můžete používat cokoli z přednášek či cvičení bez důkazu, jen vždy uveďte, kterou větu či tvrzení používáte a jakým způsobem pokud to není zřejmé. Ještě bych rád upozornil, že bodové hodnocení u jednotlivých příkladů nemusí vždy odpovídat jejich obtížnosti.

Pokud budete chtít přijít na konzultaci, rád si na vás najdu čas po předchozí emailové domluvě.

Výsledky a nárok na zápočet:

Pokud nechcete mít zveřejněny iniciály na webu používejte k podpisům ještě navíc přezdívku.

Dosavadní výsledky v google dokumentu.

masarik<a>mimuw.edu.pl



CENT building room 03.111, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 1650, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 8514, Department of Mathematics, Simon Fraser university, 8888 University Drive, Burnaby, V5A 1S6, Canada
Room 320, KAM MFF, Malostranské náměstí 25, Praha 1, 11800, Czech Republic