|
Vyučující
|
-
Pinc Jiří, doc. Ing. Ph.D.
|
|
Obsah předmětu
|
1. Problém, algoritmus, program. Program a programovací jazyk. Vykonání programu. Objekt, třída. 2. Spojové datové struktury. Správnost programů. Analýza programů. 3. Abstraktní datový typ. Zásobník a fronta. 4. Seznam. Příklady rekurze. Rekurzivní programy. 5. Rekurze a zásobník. Stromy, základní pojmy. Binární stromy. Binární vyhledávací stromy. 6. Grafy a jejich implementace. Prohledávání grafu. Topologické řazení. 7. Tabulka s přímým adresováním. Rozptylové tabulky se zřetězením. Rozptylovací funkce. 8. Prioritní fronta. Halda. Řazení použitím prioritní fronty. 9. Problém řazení. Řazení haldou. Shellovo řazení. Řazení dělením. Řazení slučováním. 10.Generičnost. Dědičnost. Rozhraní. 11. Abstrakce problému. Algoritmická řešitelnost problémů. Dolní omezení pro porovnávací řazení. Klasifikace problémů. 12. NP-úplné problémy. Splnitelnost logického obvodu. Dokazování NP-úplnosti. 13. Použití algoritmů na vybrané problémy.
|
|
Studijní aktivity a metody výuky
|
Přednáška s diskusí, Přednáška s demonstrací, Cvičení
- Příprava na dílčí test [2-10]
- 8 hodin za semestr
- Projekt individuální [40]
- 40 hodin za semestr
- Kontaktní výuka
- 65 hodin za semestr
- Příprava na zkoušku [10-60]
- 30 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| orientovat se v základních imperativních řídících strukturách jazyka Java |
| orientovat se v primitivních datových typech používaných v jazyce Java |
| popsat principy programování v imperativních jazycích, zejména základních řídících struktur |
| popsat principy základních způsobů reprezentace dat v počítači |
| prokazovat znalosti základních pojmů a metod z matematiky |
| Odborné dovednosti |
|---|
| provádět základní matematická odvození a výpočty |
| na základní uživatelské úrovni používat některé z běžných vývojových prostředí Javy |
| vytvářet jednoduché programy v jazyce Java |
| Obecné způsobilosti |
|---|
| bc. studium: vytváří hypotézy, navrhuje postupné kroky, zvažuje využití různých postupů při řešení problému nebo ověřování hypotézy, |
| Výsledky učení |
|---|
| Odborné znalosti |
|---|
| interpretovat výroky o složitosti problémů, porozumět výrokům o třídách složitosti P, NP a NP-C |
| vyjmenovat a popsat nejpoužívanější algoritmy řazení a analyzovat jejich vlastnosti |
| interpretovat výroky o složitosti algoritmů a složitostních třídách O, Theta a Omega |
| vyjmenovat a popsat nejrozšířenější abstraktní datové typy, možnosti jejich implementace a z toho plynoucí vlastnosti |
| popsat způsob vykonání programu v jazyce Java, zejména z hlediska alokace paměti v zásobníku a na hromadě a vytváření zásobníkových rámců |
| určit výpočetní složitost operací nad konkrétními implementacemi abstraktních datových struktur, zejména u standardních implementací v knihovně jazyka Java |
| Odborné dovednosti |
|---|
| implementovat základní algoritmy zpracování stromových datových struktur, tj. preorder, inorder a postorder procházení |
| implementovat složitější algoritmy zpracovávající dynamické datové struktury |
| vytvářet složitější datové struktury podle konkrétních zadání, zejména s ohledem na volbu vhodné a efektivní abstraktní datové struktury a její implementace |
| implementovat programy využívající základní principy objektového programování v jazyce Java |
| analyzovat a provnávat algoritmy z hlediska třídy výpočetní a paměťové složitosti |
| implementovat základní algoritmy zpracování grafů, tj. prohledávání do šířky a do hloubky a topologické řazení |
| Obecné způsobilosti |
|---|
| bc. studium: samostatně získávají další odborné znalosti, dovednosti a způsobilosti na základě především praktické zkušenosti a jejího vyhodnocení, ale také samostatným studiem teoretických poznatků oboru, |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Samostatná práce studentů, |
| Přednáška s demonstrací, |
| Přednáška s diskusí, |
| Cvičení (praktické činnosti), |
| Hodnotící metody |
|---|
| Průběžné hodnocení, |
| Písemná zkouška, |
| Test, |
| Seminární práce, |
|
Doporučená literatura
|
-
Cormen, Thomas H. Introduction to algorithms. Cambridge : MIT Press, 2001. ISBN 0-262-03293-7.
-
Lafore, Robert. Data structures & algorithms in Java. Corte Madera : Waite Group Press, 1998. ISBN 1-57169-095-6.
-
Sedgewick, Robert. Algorithms in Java. Pts. 1-4, Fundamentals, data structures, sorting, searching. 3rd ed. Boston : Addison-Wesley, 2003. ISBN 0-201-36120-5.
-
Šafařík, Jiří. Počítače a programování 2. ZČU, 2005.
|