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 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 2018/2019

Týden Datum Téma Průsvitky
1. 22.2. Úvod do problematiky. 01
2. 1.3. Techniky návrhu algoritmů. 02
3. 8.3. Strukturované datové typy, funkce, reference. 03
4. 15.3. Základy řazení. 04
5. 22.3. 1.Test příklad a řešeni
6. 29.3. Randomizované algoritmy. 05
7. 5.4. Pokročilé řazení. 07
8. 12.4. Abstraktní datové typy. 08
9. 19.4. Odpadá, svátek
10. 26.4. Abstraktní datové typy II. 10a 10b
11. 3.5. 2.Test příklad a řešeni
12. 10.5. Vyhledávání. 11a 11b
13. 17.5. Dynamické programování. 13
14. 24.5. NP-úplnost a ostatní. 14

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 22.3. 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 v pátek 3.5. 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ň 5 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: Pondělí, 15. únor 2019, 19:20

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: 2019/02/17 12:40 by richta