Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

b6b36dsa -- Datové struktury a algoritmy

Diskusní fórum Brute - odevzdávací systém Výsledky Popis předmětu na FEL Rozvrh na FEL


Předměty B6B36DSA a BD6B36DSA mají společné stránky.

Plán přednášek LS 2019/2020

Týden Datum Téma Průsvitky
1. 21.2. Úvod do problematiky. 01
2. 28.2. Techniky návrhu algoritmů. 02
3. 6.3. Složitost algoritmů. 03
4. 27.3. Základy řazení. 04
5. 3.4. Randomizované algoritmy. 05 Příklady
8. 10.4. Odpadá, svátek
7. 17.4. 1.Test příklad a řešeni
6. 17.4. Pokročilé řazení. 07
9. 24.4. Abstraktní datové typy. 08 10a 10b
10. 24.4. Vyhledávání. 11a 11b
11. 1.5. Odpadá, svátek
12. 5.5. Dynamické programování. 13
13. 8.5. Odpadá, svátek
14. 15.5. NP-úplnost a ostatní. 14
15. 22.5. 2.Test příklad a řešeni

Domácí úkoly

Během semestru bude zadáno 6 domácích úkolů. Zadání úkolů je vyvěšeno na stránkách předmětu a budou se odevzdávat do odevzdávacího systému (Squeezer), kde budou automaticky hodnoceny.

Pro získání zápočtu je nutné úspěšně a včas odevzdat nejméně 5 domácích úkolů (získat alespoň 5 bodů). Úlohy je třeba odevzdat v každém případě, pokud jsou odevzdány v zadaném termínu, postačí odevzdat jen 5 úkolů. Pozdní odevzdání bude penalizováno nutností odevzdat i šestý úkol.

Upozornění: práce na domácích úkolech je samostatná. Studenti, kterým odhalíme duplicitní řešení, automaticky ztrácí nárok na zápočet a hrozí jim disciplinární řízení. Samozřejmě je normální (a žádoucí) o domácích úlohách diskutovat s kolegy, nicméně kód si musí každý napsat sám.

Další informace o domácích úkolech najdete v sekci Domácí úkoly.

Testy v semestru

Tento rok se budou psát dva testy v semestru. Oběma musíte projít, jinak ztrácíte nárok na zápočet. Celkový počet příkladů vyřešených v testech v semestru se při zkoušce nezohledňuje.

Každý test můžete opakovat pouze jednou! Pokud neuspějete u obou testů tak ztrácíte nárok na zápočet.

První test

První test v semestru se bude psát na přednášce v pátek dle aktuální situace. Bude mít pět příkladů hodnocených 0-2 body (2 body - zcela správně, 1 bod - částečně správně). Na úspěšný průchod bude potřeba získat alespoň 5 bodů. Pokrývá následující témata:

  1. Rekurze
  2. Asymptotická složitost kódu
  3. Množiny omikron, omega a theta
  4. Správnost kódu, invarianty
  5. Složitost algoritmů

Zadání a stručný náznak řešení

Druhý test

Druhý test v semestru se bude psát na přednášce dle aktuální situace. Opět bude mít pět příkladů hodnocených 0-2 body (2 body - zcela správně, 1 bod - částečně správně). Na úspěšný průchod bude potřeba získat alespoň 6 bodů. Témata příkladů:

  1. Randomizované algoritmy
  2. Důkaz pomocí matematické indukce (např. důkaz funkčnosti procedury Partition začínající v učebnici na straně 171),
  3. Kombinatorika, pravděpodobnost (např. výpočet složitost bucket sortu začínající v učebnici na straně 202),
  4. Formalizace přirozeného jazyka (např. definice výběru n-tého prvku (selection problem) v učebnici na straně 213),
  5. Počítání (např. analýza počtu kroků řazení vkládáním začínající v učebnici na straně 26) a
  6. Programování (zjevné, doporučujeme zopakovat si zejména práci se spojovými strukturami).

Částečné zadání a řešení

Naposledy změněno: Středa, 7. duben 2020, 21:40

Materiály

Další odkazy

Odkaz na stránky předmětu Introduction to Algorithms z Open Courseware MIT

Introduction to Algorithms on MIT

Odkaz na stránky předmětu Introduction to Algorithms z Open Courseware MIT (2011)

Introduction to Algorithms on MIT (2011)

courses/b6b36dsa/start.txt · Last modified: 2020/04/29 15:15 by richta