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>kam.mff.cuni.cz


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
Room 1650, MIMUW, Banacha 2, Warsaw, 02-097, Poland
tel +420 22191 4294

Profile for TarkenCZE-Maso sDýní