b6b36dsa -- Datové struktury a algoritmy

Odevzdávací systém Diskusní fórum 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 2016/2017

Týden Datum Téma Průsvitky
1. 24.2. Úvod do problematiky. 01
2. 3.3. Techniky návrhu algoritmů. 02
3. 10.3. Strukturované datové typy, funkce, reference. 03
4. 17.3. Základy řazení. 04
5. 24.3. Randomizované algoritmy. 05
6. 31.3. 1.Test reseni
7. 7.4. Pokročilé řazení. 07
8. 14.4. Odpadá, svátek
9. 21.4. Abstraktní datové typy. 09
10. 28.4. Abstraktní datové typy II. 10a 10b
11. 5.5. Vyhledávání. 11a 11b
12. 12.5. 2.Test reseni
13. 19.5. Dynamické programování. 13
14. 26.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 nebo Upload Systém), 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 odevzdání 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.

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 31.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 12.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í, 8. květen 2017, 19.20

 
Groups:
courses/b6b36dsa/start.txt · Last modified: 2017/05/13 11:13 by richta