Detail předmětu

Teorie kategorií v informatice

FIT-TKDAk. rok: 2017/2018

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.

 

  

Jazyk výuky

čeština

Garant předmětu

prof. RNDr. Josef Šlapal, CSc.

Zajišťuje ústav

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

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

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.

Prerekvizity

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

Způsob a kritéria hodnocení

Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.

Osnovy výuky

    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

     
    Osnova numerických cvičení:
     

Učební cíle

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.

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

Zpracovaní a obhájení eseje.

Základní literatura

M. Barr, Ch. Wells: Category Theory for Computing Science, Prentice Hall, New York, 1990 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

Doporučená literatura

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

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

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, zimní semestr, volitelný