====== b6b36dsa -- Datové struktury a algoritmy ======

[[https://cw.felk.cvut.cz/forum/forum-1394.html|Diskusní fórum]]
[[https://cw.felk.cvut.cz/brute/|Výsledky]]
[[http://www.fel.cvut.cz/cz/education/bk/predmety/31/30/p3130306.html|Popis předmětu na FEL]]
[[http://www.fel.cvut.cz/cz/education/rozvrhy-ng.B162/public/html/predmety/31/30/p3130306.html|Rozvrh na FEL]]
---------------

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

~~NOTOC~~


====== Plán přednášek LS 2017/2018 ======

^ Týden  ^ Datum            ^  Téma         ^  Průsvitky    ^
|  **1.**  |  23.2. | Úvod do problematiky. | {{:courses:b6b36dsa:dsa-1-úvod.pdf|01}} |
|  **2.**  |  2.3. | Techniky návrhu algoritmů. | {{:courses:b6b36dsa:DSA-2-TechnikyNávrhuAlgoritmů.pdf|02}} |
|  **3.**  |  9.3. | Strukturované datové typy, funkce, reference. | {{:courses:b6b36dsa:DSA-3-SložitostAlgoritmů.pdf|03}} |
|  **4.**  |  16.3. | Základy řazení. | {{:courses:b6b36dsa:DSA-4-Řazení.pdf|04}} |
|  **5.**  |  23.3. | Randomizované algoritmy. | {{:courses:b6b36dsa:DSA-5-Randomized.pdf|05}} |
|  **6.**  |  30.3. | //Odpadá, svátek// | -- | 
|  **7.**  |  6.4. | **1.Test** | {{:courses:b6b36dsa:1-test-2018-04-06-reseny.pdf| reseni}} |
|  **8.**  |  13.4. | Pokročilé řazení. | {{:courses:b6b36dsa:DSA-7-PokrocileRazeni.pdf | 07}} |
|  **9.**  |  20.4. | Abstraktní datové typy. | {{:courses:b6b36dsa:DSA-8-AbstrakniDatoveTypy.pdf | 09}} |
|  **10.**  |  27.4. | Abstraktní datové typy II. | {{:courses:b6b36dsa:DSA-9-AbstraktniDatoveTypyII.pdf | 10a}} {{:courses:b6b36dsa:DSA-9-Stromy.pdf | 10b}} |
|  **11.**  |  4.5. | Vyhledávání. | {{:courses:b6b36dsa:DSA-10-vyhledavani.pdf | 11a}}{{:courses:b6b36dsa:DSA-11-PokrocileVyhledavani.pdf | 11b}} |
|  **12.**  |  11.5. | **2.Test** | {{:courses:b6b36dsa:2-test-2018-05-11-reseny.pdf| reseni}} |
|  **13.**  |  18.5. | Dynamické programování. | {{:courses:b6b36dsa:DSA-12-DynamickeProgramovani.pdf|13}} |
|  **14.**  |  25.5. | NP-úplnost a ostatní. | {{:courses:b6b36dsa:DSA-13-NP-Uplnost.pdf|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.

Další informace o domácích úkolech najdete v sekci [[courses:b6b36dsa:ukoly|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 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:

  -     Rekurze
  -     Asymptotická složitost kódu
  -     Množiny omikron, omega a theta
  -     Správnost kódu, invarianty
  -     Složitost algoritmů

{{:courses:b6b36dsa:test1answers.pdf|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ů:

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

{{:courses:b6b36dsa:test3answers.pdf|Částečné zadání a řešení}}

Naposledy změněno: Pondělí, 15. leden 2018, 19:20

===== Materiály =====
[[http://ressources.unisciel.fr/algoprog/s00aaroot/aa00module1/res/%5BCormen-AL2011%5DIntroduction_To_Algorithms-A3.pdf|Cormen Thomas H. et al.: Introduction to Algorithms, 3rd Edition, MIT Press, 2009]]