ÚVOD / Studijní obory / Sylaby / Analýza dat a jejich vizualizace

Matematika a algoritmy pro data mining

Cílem předmětu je představit potřebnou matematickou výbavu nutnou pro pochopení jednotlivých postupů v datové analýze. K tomuto účelu jsou probírány témata z oblasti lineární algebry, teorie informace a složitosti algoritmů.

Sylabus předmětu

Lineární algebra
  1. Opakování lineární algebry - vektorové prostory, matice a soustavy lineárních rovnic, normy
  2. Vlastní čísla matice - charakteristický polynom, vlastní čísla a jejich výpočet, definitní a semi-definitiní matice
  3. Maticové rozklady - rozklady matic, Choleského, QR rozklad, SVD rozklad
  4. Úvod do úloh optimalizace - představení obecné úlohy optimalizace, ukázka na lineárním a kvadratickém programování
Složitost algorimů
  1. Kombinatorika a grafy - opakování pojmů z kombinatoriky a grafů, odpovídající charakteristiky a algorimy k jejich určení
  2. Složitost algoritmů - algoritmická složitost, definice tříd P a NP, základní příklady algoritmů a jejich složitosti, Cookova věta a její důsledky
  3. Řešení složitých problémů - ukázky problémů a jejich aproximačního řešení, metoda větví a mezí, lokální prohledávání a další.
  4. Aproximační řešení problémů relaxací 
Teorie informace a závislosti veličin
  1. Úvod do teorie informace - Úvod do teorie informace, náhodná veličina, náhodný proces, Markovův řetězec, míra informace a entropie
  2. Sdružené veličiny - sdřužená míra entropie a informace, vzájemná informace a její stanovení, podmíněná vzájemná informace
  3. Autoregresní model - definice autoregresního modelu a jeho použití, chyba autoregresního modelu
  4. Kauzalita - Grangerova kauzalita, podmíněná vzájemná informace, úvod do Bayesovských sítí

Organizace výuky

Prezenční forma

Výuka probíhá ve 12 přednáškách po 1,5 hodině a 12 seminářích po 3 hodinách.

Doporučená literatura

Základní:
  • Papadimitriou, C. H. Computational Complexity. Theoretical computer science. Addison-Wesley, 1994
  • Gambosi, G., Spaccamela, A. M. 'Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties'. Springer, 2003 
  • Studený, M. Struktury podmíněné nezávislosti. Matfyzpress, 2014.
  • Cover, T. M. Thomas, J. A. Elements of Information Theory. John Wiley & Sons, 2012.
  • Strang, G. Introduction to Linear Algebra, Fifth Edition, Wellesley-Cambridge Press, 2016.
  • Bican, L. Lineární algebra a geometrie, Academia, Praha 2000.
  • Černý, M. Výpočty I, II, III. Professional Publishing. 2011. 
Doporučená:
  • Hladík, M. Lineární algebra (nejen) pro informatiky. Dostupné online [html]