Detail předmětu

Teorie kategorií v informatice

TKD Ak. rok 2024/2025 letní semestr

Malé a velké kategorie, algebraické struktury jako kategorie, konstrukce na kategoriích (volné kategorie, podkategorie a duální kategorie), speciální typy objektů a morfismů, součiny a součty objektů, kategorie se součiny a logické obvody, kategorie se součty a vývojové diagramy, distributivní kategorie a imperativní programy, aritmetika reálných čísel a datové typy (zásobníky, pole, binární stromy, fronty, ukazatele), Turingovy stroje, funktory a funktorové kategorie, orientované grafy a regulární gramatiky.

Okruhy otázek k SDZ:

  1. Malé a velké kategorie - definice a příklady.
  2. Volné kategorie, duální kategorie.
  3. Iniciální a terminální objekty, součiny a sumy.
  4. Kategorie se součiny a logické obvody.
  5. Kategorie se sumami a vývojové diagramy.
  6. Distributivní kategorie, imperativní programy.
  7. Typy dat zásobníky, pole a binární stromy.
  8. Typy dat fronty a ukazatele, Turingovy stroje.
  9. Funktory a funktorové kategorie.
  10. Kategorie orientovaných grafů a regulární gramatiky.

 

  

Garant předmětu

Šlapal Josef, prof. RNDr., CSc. (ÚM OAAG)

Koordinátor předmětu

Pavlík Jan, Mgr., Ph.D. (ÚM OAAG)

Jazyk výuky

česky, anglicky

Zakončení

zkouška (písemná)

Rozsah

  • 26 hod. přednášky

Bodové hodnocení

  • 100 bodů závěrečná zkouška

Zajišťuje ústav

ÚM-odbor algebry a diskrétní matematiky (ÚM OAAG)

Cíle předmětu

Cílem předmětu je seznámit studenty se základy teorie kategorií se zaměřením na aplikace v informatice. Jednotlivé kategoriální pojmy a výsledky jsou diskutovány z hlediska jejich významu a využití v informatice.
Studenti budou obeznámeni se základními principy teorie kategorií a s možnostmi aplikací těchto principů v informatice. Získané vědomosti pak budou moci využít při řešení konkrétních problémů ve svojí specializaci.

Požadované prerekvizitní znalosti a dovednosti

Základní přednášky matematiky na technických universitách

Literatura studijní

  • J. Adámek, Matematické struktury a kategorie, SNTL, Praha, 1982
  • B.C. Pierce: Basic Category Theory for Computer Scientists, The MIT Press, Cambridge, 1991
  • R.F.C. Walters, Categories and Computer Science, Cambridge Univ. Press, 1991

Osnova přednášek

  1. Malé a velké kategorie, příklady 
  2. Algebraické struktury jako kategorie
  3. Konstrukce na kategoriích
  4. Vlastnosti objektů a morfismů
  5. Součiny a součty objektů
  6. Kategorie se součiny a logické obvody
  7. Kategorie se součty a vývojové diagramy
  8. Distributivní kategorie
  9. Imperativní programy
  10. Typy dat zásobník, pole a binární strom
  11. Typy dat fronta a ukazatel, Turingovy stroje 
  12. Funktory a funktorové kategorie
  13. Gramatiky a automaty

 

Průběžná kontrola studia

Předmět je hodnocen na základě výsledku závěrečné zkoušky, ke složení zkoušky je třeba získat nejméně 50 z celkového počtu 100 bodů.

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

  • Program DIT, libovolný ročník, povinně volitelný skupina T
  • Program DIT, libovolný ročník, povinně volitelný skupina T
  • Program DIT-EN (anglicky), libovolný ročník, povinně volitelný skupina T
  • Program DIT-EN (anglicky), libovolný ročník, povinně volitelný skupina T
  • Program VTI-DR-4, obor DVI4, libovolný ročník, volitelný
  • Program VTI-DR-4, obor DVI4, libovolný ročník, volitelný
  • Program VTI-DR-4 (anglicky), obor DVI4, libovolný ročník, volitelný
Nahoru