| Název předmětu | Počítače a programování 2 |
|---|---|
| Kód předmětu | KIV/PPA2 |
| Organizační forma výuky | Přednáška + Cvičení |
| Úroveň předmětu | Bakalářský |
| Rok studia | nespecifikován |
| Semestr | Letní |
| Počet ECTS kreditů | 5 |
| Vyučovací jazyk | Čeština |
| Statut předmětu | nespecifikováno |
| Způsob výuky | Kontaktní |
| Studijní praxe | Nejedná se o pracovní stáž |
| Doporučené volitelné součásti programu | Není |
| Vyučující |
|---|
|
| 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ředpoklady |
| Odborné znalosti |
| orientovat se v základních imperativních řídících strukturách jazyka 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 |
| orientovat se v primitivních datových typech používaných v jazyce Java |
| Odborné dovednosti |
| na základní uživatelské úrovni používat některé z běžných vývojových prostředí Javy |
| provádět základní matematická odvození a výpočty |
| 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 |
| 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 |
| 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ů |
| vyjmenovat a popsat nejrozšířenější abstraktní datové typy, možnosti jejich implementace a z toho plynoucí vlastnosti |
| 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 |
| vyjmenovat a popsat nejpoužívanější algoritmy řazení a analyzovat jejich vlastnosti |
| Odborné dovednosti |
| implementovat základní algoritmy zpracování stromových datových struktur, tj. preorder, inorder a postorder procházení |
| implementovat základní algoritmy zpracování grafů, tj. prohledávání do šířky a do hloubky a topologické řazení |
| analyzovat a provnávat algoritmy z hlediska třídy výpočetní a paměťové složitosti |
| 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 |
| implementovat složitější algoritmy zpracovávající dynamické datové struktury |
| 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), |
| E-learning, |
| Hodnotící metody |
| Průběžné hodnocení, |
| Písemná zkouška, |
| Test, |
| Seminární práce, |
| Doporučená literatura |
|
| Studijní plány, ve kterých se předmět nachází |
| Fakulta | Studijní plán (Verze) | Kategorie studijního oboru/specializace | Doporučený semestr |
|---|