|
Vyučující
|
-
Slánský Vlastimil, doc. Ing. Ph.D.
|
|
Obsah předmětu
|
1. Problém, algoritmus, program. Program a programovací jazyk. Vykonání programu. Objekt, třída. 2. Generické programování, koncept rozhraní, polymorfismus. Rekurzivní programy. 3. Výpočetní složitost, O, Omega a Theta množiny. 4. Řazení. InsertSort, ShellSort, QuickSort, MergeSort. 5. Abstraktní datové typy. Kolekce. Zásobník - implementace polem, implementace spojovou strukturou. 6. Odstranění rekurze uživatelským zásobníkem. Fronta - možné implementace. 7. Seznam, iterátor, možné implementace. 8. Tabulka s přímým adresováním. Rozptylové tabulky. Rozptylová funkce. 9. Stromy, binární vyhledávací stromy, vyvážené stromy. 10. Graf, implementace seznamem sousednosti, implementace maticí sousednosti. Prohledávání do šířky. 11. Topologické řazení, prohledávání do hloubky. 12. Prioritní fronta, halda. 13. Formalizace a klasifikace problémů. Třídy problémů P, NP a NP-C
|
|
Studijní aktivity a metody výuky
|
- Kontaktní výuka
- 52 hodin za semestr
- Příprava na souhrnný test [6-30]
- 13 hodin za semestr
- Příprava na zkoušku [10-60]
- 26 hodin za semestr
- Vypracování seminární práce v bakalářském studijním programu [5-40]
- 39 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| orientovat se v primitivních datových typech používaných pro reprezentaci celých čísel, čísel s plovoucí desetinnou čárkou a znaků v počítači |
| orientovat se v základních imperativních řídících strukturách |
| popsat principy programování v imperativních jazycích, zejména základních řídících struktur |
| prokazovat znalosti základních pojmů a metod z matematiky |
| Odborné dovednosti |
|---|
| na základní uživatelské úrovni používat některé z běžných vývojových prostředí |
| provádět základní matematická odvození a výpočty |
| vytvářet jednoduché programy v imperativním programovacím jazyce |
| Obecné způsobilosti |
|---|
| bc. studium: své učení a pracovní činnost si sám plánuje a organizuje, |
| bc. studium: efektivně využívá různé strategie učení k získání a zpracování poznatků a informací, hledá a rozvíjí účinné postupy ve svém učení, |
| bc. studium: kriticky přistupuje ke zdrojům informací, informace tvořivě zpracovává a využívá při svém studiu a praxi, |
| bc. studium: rozpozná problém, objasní jeho podstatu, rozčlení ho na části, |
| 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 algoritmů a složitostních třídách O, Theta a Omega |
| interpretovat výroky o složitosti problémů, porozumět výrokům o třídách složitosti P, NP a NP-C |
| popsat způsob vykonání programuv počítači, zejména z hlediska alokace paměti v zásobníku a na hromadě a vytváření zásobníkových rámců |
| samostatně určit výpočetní složitost operací nad konkrétními implementacemi abstraktních datových typů, zejména u standardních implementací |
| vyjmenovat a popsat nejpoužívanější algoritmy řazení a analyzovat jejich vlastnosti |
| vyjmenovat a popsat nejrozšířenější abstraktní datové typy, možnosti jejich implementace a z toho plynoucí vlastnosti |
| Odborné dovednosti |
|---|
| analyzovat a provnávat algoritmy z hlediska třídy výpočetní a paměťové složitosti |
| implementovat programy využívající základní principy objektového programování |
| implementovat složitější algoritmy zpracovávající dynamické datové struktury |
| implementovat základní algoritmy zpracování grafů, tj. prohledávání do šířky a do hloubky a topologické řazení |
| implementovat základní algoritmy zpracování stromových datových struktur, tj. preorder, inorder a postorder procházení |
| vytvářet složitější datové struktury podle konkrétních zadání, zejména s ohledem na volbu vhodné implementace abstraktního datového typu |
| vytvářet implementace abstraktních datových typů přizpůsobené konkrétním úlohám |
| 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 |
|---|
| Přednáška založená na výkladu, |
| Přednáška s demonstrací, |
| Přednáška s diskusí, |
| Cvičení (praktické činnosti), |
| E-learning, |
| Samostudium, |
| Kooperativní výuka, |
| Řešení problémů, |
| Samostatná práce studentů, |
| Odborné dovednosti |
|---|
| Přednáška založená na výkladu, |
| Přednáška s demonstrací, |
| Přednáška s diskusí, |
| Cvičení (praktické činnosti), |
| E-learning, |
| Řešení problémů, |
| Kooperativní výuka, |
| Samostudium, |
| Samostatná práce studentů, |
| Obecné způsobilosti |
|---|
| Přednáška založená na výkladu, |
| Přednáška s demonstrací, |
| Cvičení (praktické činnosti), |
| E-learning, |
| Řešení problémů, |
| Samostudium, |
| Samostatná práce studentů, |
| Hodnotící metody |
|---|
| Odborné znalosti |
|---|
| Ústní zkouška, |
| Písemná zkouška, |
| Kombinovaná zkouška, |
| Test, |
| Průběžné hodnocení, |
| Seminární práce, |
| Odborné dovednosti |
|---|
| Ústní zkouška, |
| Písemná zkouška, |
| Kombinovaná zkouška, |
| Test, |
| Průběžné hodnocení, |
| Seminární práce, |
| Obecné způsobilosti |
|---|
| Ústní zkouška, |
| Písemná zkouška, |
| Kombinovaná zkouška, |
| Test, |
| Seminární práce, |
| Průběžné hodnocení, |
|
Doporučená literatura
|
-
Jim Keogh, Ken Davidson. Datové struktury bez předchozích znalostí. 2006.
-
Ryant, Ivan. Algoritmy a datové struktury objektově. Vydání první. 2017. ISBN 978-80-270-1660-0.
|