|
Vyučující
|
-
Schlecht Miroslav, doc. Ing. Ph.D.
|
|
Obsah předmětu
|
- Posuzování algoritmů, časová a paměťová složitost. Master theorem. - Často se vyskytující zbytečné, časově náročné operace v kódu a jejich eliminace. - Robustnost algoritmů, singulární případy, přesnost numerických výpočtů. - Maticové a vektorové operace (Strassen formula, skalární a vektorový součin). Řešení soustav lineárních i nelineárních rovnic (včetně přeurčených soustav). - Správa paměti. Alokace a dealokace paměti, garbage collector, úniky paměti. Příliš velká data (nevejdou se do paměti). - Cache v současných počítačích a její efektivní využití (technika bricking) - Rozděl a panuj. Binární vs. interpolační hledání, Medián. Dělení prostoru. - Práce s velkými daty. Redukce dimenze problému. Redukce dat vzorkováním, Sobolovy sekvence. Vlastní správa paměti. Komprese. Checksums (LUHN, CRC, Adler32, MD5). - Reprezentace grafů, algoritmy Dijkstra a Floyd-Warshall. - Heuristické přístupy k řešení. Stavový automat, prořezávání stavů. Problém optimálního přiřazení - Hungarian marriage.
|
|
Studijní aktivity a metody výuky
|
Přednáška s aktivizací, Individuální konzultace, Seminární výuka, Samostatná práce studentů
- Projekt individuální [40]
- 40 hodin za semestr
- Kontaktní výuka
- 26 hodin za semestr
- Příprava na zkoušku [10-60]
- 30 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| popsat principy vykonávání programu počítačem |
| popsat principy programování v imperativních jazycích, tj. řídící struktury, cykly, metody, aj. |
| orientovat se v matematických pojmech na úrovni středoškolské matematiky |
| Odborné dovednosti |
|---|
| vytvořit počítačový program v libovolném programovacím jazyce pro řešení jednoduchého problému (např. rozhodnutí, zda v poli čísel se nachází duplicity) |
| Obecné způsobilosti |
|---|
| bc. studium: své učení a pracovní činnost si sám plánuje a organizuje, |
| Výsledky učení |
|---|
| Odborné znalosti |
|---|
| posuzování časové a paměťové složitosti rekurentních i nerekurentních algoritmů |
| základních principů užívaných pro návrh efektivního algoritmu (např. řazení, rozděl a panuj, dělení prostoru) |
| základních principů využívaných pro zvýšení efektivity nebo robustnosti implementace (např. eliminace konstatních výpočtů v cyklu, zarovnání dat pro lepší využití cache, komprese dat, apod.) |
| Odborné dovednosti |
|---|
| navrhnout algoritmus řešící zadaný netriviální problém (např. volba optimálního umístění obchodů ve městě) |
| posoudit očekávanou složitost navrženého algoritmu |
| Obecné způsobilosti |
|---|
| bc. studium: používají své odborné znalosti, odborné dovednosti a obecné způsobilosti alespoň v jednom cizím jazyce, |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Přednáška s aktivizací studentů, |
| Samostatná práce studentů, |
| Individuální konzultace, |
| Seminární výuka (badatelské metody), |
| Odborné dovednosti |
|---|
| Přednáška s aktivizací studentů, |
| Samostatná práce studentů, |
| Obecné způsobilosti |
|---|
| Přednáška s aktivizací studentů, |
| Diskuse, |
| Individuální konzultace, |
| Hodnotící metody |
|---|
| Odborné znalosti |
|---|
| Písemná zkouška, |
| Seminární práce, |
| Odborné dovednosti |
|---|
| Písemná zkouška, |
| Seminární práce, |
| Obecné způsobilosti |
|---|
| Písemná zkouška, |
| Seminární práce, |
|
Doporučená literatura
|
-
Alsuwaiyel, M. H. Algorithms: Design Techniques and Analysis (Revised Edition). 2016. ISBN 978-981-4723-64-0.
-
Alsuwaiyel, M. H. Algorithms: design techniques and analysis. 1st pub. Singapore : World Scientific, 1999. ISBN 981-02-3740-5.
-
McConnell, Jeffrey. Analysis of algorithms: an active learning approach. Jones & Bartlett Publishers, 2007. ISBN 978-0763707828.
|