|
Vyučující
|
-
Červenka Martin, Ing.
-
Mautner Pavel, Ing. Ph.D.
|
|
Obsah předmětu
|
1. Složitost a řešitelnost úloh - opakování a prohloubení znalostí. Abstraktní datové typy 2. Řazení, vyhledávání, třídění - mediány, quantily, bucket sort, radix sort, porovnání řadicích algoritmů 3. Datové struktury I - zásobník, fronta, seznam, slovník, invertovaný seznam, 4. Datové struktury II - speciální vyhledávací stromy (AVL, RB, B), hashovací tabulky, grafy, množiny 5. Grafové algoritmy - nejkratší cesta (Dijkstra, Prim, Kruskal), bipartitní grafy, 6. Množinové algoritmy - generování permutací, podmnožin 7. Textové algoritmy - shoda řetězců, přibližná shoda řetězců, nejdelší a nejkratší společný řetězec 8. Komprese dat I - bezztrátové algoritmy (RLE, LZW, Huffman, aritmetické kódování) 9. Komprese dat II - ztrátové metody (JPEG, waveletová komprese, fraktálová komprese) 10. Kryptografie - úvod, základní algoritmy 11. Praxe programátora - vhodnost užívání různých datových struktur v konkrétních situacích, vliv cache na běh programu, floating point implementace reálných čísel a její důsledky na výpočty
|
|
Studijní aktivity a metody výuky
|
Seminární výuka, Přednáška
- Kontaktní výuka
- 65 hodin za semestr
- Vypracování seminární práce v bakalářském studijním programu [5-40]
- 30 hodin za semestr
- Příprava na zkoušku [10-60]
- 40 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| algoritmizovat jednoduché problémy |
| programovat v některém ze základních programovacích jazyků (Java, C, Pascal) |
| Odborné dovednosti |
|---|
| analyzovat zadání jednoduché úlohy |
| vytvořit jednoduchý program v základním programovacím jazyce |
| napsat a odladit jednoduchý program ve vývojovém prostředí pro daný jazyk |
| vytvořit uživatelskou a programátorskou dokumentaci pro vytvořený program |
| Obecné způsobilosti |
|---|
| bc. studium: své učení a pracovní činnost si sám plánuje a organizuje, |
| Výsledky učení |
|---|
| Odborné znalosti |
|---|
| analyzovat problém a zvolit vhodné datové struktury a algoritmy |
| vyjmenovat a použít a implementovat základní datové struktury používané v informatice (zásobník, fronta, speciální vyhledávací stromy, slovníky, hashovací tabulky, množiny, grafy) |
| používat a implementovat základní algoritmy řazení a vyhledávání, grafové algoritmy (nejkratší cesta, minimální kostra grafu, toky v sítích) |
| používat a implementovat algoritmy zpracování textů, kombinatorické algoritmy a algoritmy komprese dat |
| vyjmenovat a vysvětlit základní algoritmy používané v kryptografii |
| Odborné dovednosti |
|---|
| analyzovat problém a zvolit vhodné datové struktury a algoritmy |
| vytvořit program v některém ze základních programovacích jazyků |
| vytvořit uživatelskou a programátorskou dokumentaci pro řešený problém |
| zhodnotit řešení problému, popř. navrhnout možné modifikace řešeného problému, které se nepodařilo realizovat |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Přednáška založená na výkladu, |
| Cvičení (praktické činnosti), |
| Odborné dovednosti |
|---|
| Cvičení (praktické činnosti), |
| Samostatná práce studentů, |
| Obecné způsobilosti |
|---|
| Cvičení (praktické činnosti), |
| Samostatná práce studentů, |
| Hodnotící metody |
|---|
| Odborné znalosti |
|---|
| Písemná zkouška, |
| Seminární práce, |
| Odborné dovednosti |
|---|
| Písemná zkouška, |
| Demonstrace dovedností (praktická činnost), |
| Seminární práce, |
| Obecné způsobilosti |
|---|
| Demonstrace dovedností (praktická činnost), |
| Seminární práce, |
| Individuální prezentace, |
|
Doporučená literatura
|
-
Cormen, Thomas H. Introduction to algorithms. MIT Press, 2009. ISBN 978-0262033848.
-
Goodrich, Michael T.; Tamassia, Roberto. Data structures and algorithms in Java. John Wiley & Sons, 2005. ISBN 0-471-73884-0.
-
McConnell, Steve. Dokonalý kód : umění programování a techniky tvorby software. Vyd. 1. Brno : Computer Press, 2005. ISBN 80-251-0849-X.
-
Sedgewick, Robert. Algorithms in Java. Pts. 1-4, Fundamentals, data structures, sorting, searching. 3rd ed. Boston : Addison-Wesley, 2003. ISBN 0-201-36120-5.
-
Skiena, Steven S. The algorithm design manual. 2nd ed. New York : Springer, 2008. ISBN 978-1-848-00-069-.
-
Töpfer, Pavel. Algoritmy a programovací techniky. 1. vyd. Praha : Prometheus, 1995. ISBN 80-85849-83-6.
|