Detail předmětu

Data Structures and Algorithms

FEKT-MPA-TINAk. rok: 2022/2023

1. Reprezentace informace - objektově orientovaný návrh
2. Reprezentace informace – úvod do datových struktur, abstraktní datové typy
3. Spočítatelnost a složitost, deterministické a nedeterministické automaty
4. Reprezentace informace - lineární datové struktury
5. Reprezentace informace – stromové datové struktury
6. Reprezentace informace – grafy
7. Zpřístupnění informace - Kostra grafu
8. Zpřístupnění informace - hledání cesty v grafu
9. Zpřístupnění informace – dolování znalostí z báze dat
10. Zpřístupnění informace – Optimalizace
11. Zpřístupnění informace – prohledávání stavového prostoru, genetické algoritmy
12. Procesy, vlákna a paralelní výpočty
13. Paralelní, sekvenční a náhodné algoritmy. Distribuované algoritmy

Jazyk výuky

angličtina

Počet kreditů

5

Výsledky učení předmětu

Absolventi jsou schopni návrhu a implementace různých forem abstraktních datových typů a jeho aplikaci na řešení konkrétních problémů. Pro jejich řešení si umí použít lineární, stromové a grafové datové struktury, dále pak vyhledávat v datových strukturách a využít genetické algoritmy pro prohledávání stavového prostoru a optimalizaci.

Prerekvizity

Jsou požadovány znalosti na úrovni bakalářského studia.

Plánované vzdělávací činnosti a výukové metody

Metody vyučování zahrnují přednášky, cvičení na počítači a laboratoře. Předmět využívá e-learning (Moodle). Student odevzdává jeden samostatný projekt.

Způsob a kritéria hodnocení

závěrečná zkouška

Osnovy výuky

Přednášky:
1. Reprezentace informace, objektově orientovaný návrh.
2. Reprezentace informace, úvod do datových struktur.
3. Spočitatelnost, složitost a teorie automatů.
4. Reprezentace informace - lineární datové struktury a řazení.
5. Reprezentace informace - stromové datové struktury.
6. Reprezentace infomace - teorie grafů.
7. Zpřístupnění informace - kostra grafu.
8. Zpřístupnění informace - hledání cesty v grafu.
9. Zpřístupnění informace - dolování znalostí z báze dat.
10. Zpřístupnění informace - rozhodovací stromy.
11. Zpřístupnění informace - genetické algoritmy.
12. Zpřístupnění informace - genetické algorithmy II.
13. Vícevláknové výpočty, paralelizace.

Cvičení na počítači:
1. Úvod do OON.
2. Reprezentace informace I.
3. Reprezentace informace II.
4. Lineární datové strukury.
5. Binární vyhledávací stromy.
6. Teorie grafů.
7. Prohledávání grafů.
8. Půlsemestrální zkouška.
9. Prohledávání grafů - Disktrův algoritmus.
10. Analýza dat - rozhodovací stromy.
11. Optimalizace - genetické algoritmy.

Učební cíle

Cílem kurzu je seznámit studenty s teorií informace, variantami reprezentace informace, metodami zpřístupnění informace a způsoby dolování informací z dat s využitím výpočetních systémů.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Vymezení kontrolované výuky a způsob jejího provádění stanoví každoročně aktualizovaná vyhláška garanta předmětu.

Základní literatura

GOODRICH, T.M., TAMASSIA, R. Data Structures and Algorithms in Java. 2000. (EN)

eLearning

Zařazení předmětu ve studijních plánech

  • Program MPA-CAN magisterský navazující, 1. ročník, zimní semestr, povinný
  • Program MPAD-CAN magisterský navazující, 1. ročník, zimní semestr, povinný
  • Program MPA-TEC magisterský navazující, 1. ročník, zimní semestr, povinně volitelný
  • Program MPAJ-TEC magisterský navazující, 1. ročník, zimní semestr, povinně volitelný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Osnova

1. Reprezentace informace, objektově orientovaný návrh.
2. Reprezentace informace, úvod do datových struktur.
3. Spočitatelnost, složitost a teorie automatů.
4. Reprezentace informace - lineární datové struktury a řazení.
5. Reprezentace informace - stromové datové struktury.
6. Reprezentace infomace - teorie grafů.
7. Zpřístupnění informace - kostra grafu.
8. Zpřístupnění informace - hledání cesty v grafu.
9. Zpřístupnění informace - dolování znalostí z báze dat.
10. Zpřístupnění informace - rozhodovací stromy.
11. Zpřístupnění informace - genetické algoritmy.
12. Zpřístupnění informace - genetické programování.
13. Vícevláknové výpočty, paralelizace.

Cvičení na počítači

26 hod., povinná

Vyučující / Lektor

Osnova

1. Úvod do OON.
2. Reprezentace informace I.
3. Reprezentace informace II.
4. Lineární datové strukury.
5. Binární vyhledávací stromy.
6. Teorie grafů.
7. Prohledávání grafů.
8. Půlsemestrální zkouška.
9. Prohledávání grafů - Disktrův algoritmus.
10. Analýza dat - rozhodovací stromy.
11. Optimalizace - genetické algoritmy.

eLearning