Informační systém Vysoké školy polytechnické Jihlava
IS VŠPJ
Datové struktury a algoritmy
Studijní plán: Aplikovaná informatika - kombi, platný od ZS 2024/2025
| Předmět | Datové struktury a algoritmy (DSA) |
|---|---|
| Garantuje | Katedra technických studií (KTS) |
| Garant | doc. Dr. Ing. Jan Voráček, CSc.( voracek@vspj.cz ) |
| Jazyk | česky |
| Počet kreditů | 5 |
| Prezenční studium | |
|---|---|
| Přednáška | 2 h |
| Cvičení | 2 h |
| Kombinované studium | |
| Tutoriál / přednáška | 4 h |
| Cvičení | 10 h |
| Studijní plán | Typ | Sem. | Kred. | Ukon. |
|---|---|---|---|---|
| Aplikovaná informatika - kombi, platný od ZS 2024/2025 | P | 3 | 5 kr. | Z,ZK |
| Aplikovaná informatika - platný od ZS 2024/2025 | P | 3 | 5 kr. | Z,ZK |
Anotace
Studenti získají přehled o efektivních algoritmech a datových strukturách pro řešení standardních úloh, především typu vyhledávání a řazení nad dynamicky se měnícími vstupními údaji. Podrobně se seznámí se základními kontejnery (úložišti dat) jako jsou vektor, pole, zásobník, fronta, seznam, množina a tabulka. S jejich pomocí se naučí implementovat
a využívat vybrané problémově orientované dynamické datové struktury, jako např. rozptylovací tabulky, vyhledávací stromy, vyvažované vyhledávací stromy, haldy, či B-stromy. Kontextové povědomí získají také o grafových a optimalizačních algoritmech.
Znalosti: Student zná základní algoritmy zpracování časově i strukturně heterogenních dat zejména z oborů řazení a vyhledávání včetně odpovídajících základních kontejnerů (úložišť dat) a forem jejich implementace.
Dovednosti: Student umí specifikovat řešený problém, zvolit pro něj nejvýhodnější reprezentaci dat a navrhnout algoritmy požadovaných operací. Úlohu je schopen naprogramovat v jazyce C++ a zhodnotí paměťovou a operační složitost své implementace.
Obecné způsobilosti: Student umí účinně analyzovat a z hlediska výpočetního času i paměťového prostoru optimalizovat obecnou problematiku, řešenou s využitím výpočetní techniky.
Sylabus
- Základní datové struktury pole a seznam
- Operační a paměťová složitost algoritmů
- Algoritmy řazení a jejich operační složitost
- Algoritmy asociativního a adresního vyhledávání a jejich operační složitost
- Specifikace a implementace datových typů zásobník, fronta, pole, množina, seznam, mapa, tabulka, strom, graf
- Knihovna STL, kontejnery a algoritmy knihovny STL
- Vybrané typové algoritmy: extrémy funkcí a optimalizace, dynamické programování, P a NP problémy
Doporučená literatura
- HUDEC, Bohuslav. Algoritmy v C++: Studijní opora. 1. vyd., 7. revize. Jihlava: VŠP Jihlava, 2025. ISBN: nemá.
- Studijní opora v LMS Moodle.
- MAREŠ, Martin a VALLA, Tomáš. Průvodce labyrintem algoritmů. CZ.NIC. Praha: CZ.NIC, z.s.p.o., 2022. ISBN 9788088168669.
- CORMEN, Thomas H.; LEISERSON, Charles Eric; RIVEST, Ronald L. a STEIN, Clifford. Introduction to algorithms. Fourth edition. Cambridge, Massachusett: The MIT Press, [2022]. ISBN 9780262046305.
- GOODRICH, Michael T., TAMASSIA, Roberto a MOUNT, David M. Data Structures and Algorithms in C++, 2nd Edition, Wiley, 2011. ISBN 978-0-470-38327-8.