Název:

Teorie kategorií

Zkratka:TKD
Ak.rok:2012/2013
Semestr:zimní
Studijní plán:
ProgramOborRočníkPovinnost
VTI-DR-4DVI4-volitelný
Vyučovací jazyk:čeština
Ukončení:zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:260000
 zkouškatestycvičenílaboratořeostatní
Body:1000000
Garant:Šlapal Josef, prof. RNDr., CSc., UM OADM
Fakulta:Fakulta strojního inženýrství VUT
Pracoviště:Ústav matematiky - odbor algebry a diskrétní matematiky FSI VUT
 
Cíle předmětu:
Cílem předmětu je seznámit studenty se základy teorie kategorií z hlediska aplikací v informatice. Některé důležité konkrétní aplikace budou probrány podrobněji.
Anotace:
Grafy a kategorie, algebraické struktury jako kategorie, konstrukce na kategoriích (podkategorie a duální kategorie), speciální typy objektů a morfismů, součiny a součty objektů, objekty přirozených čísel, deduktivní systémy, funktory a diagramy, funktorové kategorie, gramatiky a automaty, přirozené transformace, limity a kolimity, adjungované funktory, kartézsky uzavřené kategorie a typovaný lambda-kalkul, kartézsky uzavřená kategorie Scottových domainů.
Požadované prerekvizitní znalosti a dovednosti:
Základní přednášky matematiky na technických universitách
Získané dovednosti, znalosti a kompetence:
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.
Osnova přednášek:
  1. Grafy a kategorie
  2. Algebraické struktury jako kategorie
  3. Konstrukce na kategoriích
  4. Vlastnosti objektů a morfismů
  5. Součiny a součty objektů
  6. Objekty přirozených čísel a deduktivní systémy
  7. Funktory a diagramy
  8. Funktorové kategorie, gramatiky a automaty
  9. Přirozené transformace
  10. Limity a kolimity
  11. Adjungované funktory
  12. Kartézsky uzavřené kategorie a typovaný lambda-kalkul
  13. Kartézsky uzavřená kategorie Scottových domainů
Osnova numerických cvičení:
  1. Relační systémy a univerzální algebry
  2. Množiny, kardinální čísla a kardinální aritmetika
  3. Výroky, výrokové spojky, pravdivostní tabulky, tautologie a kontradikce
  4. Nezávislost logických spojek, axiomy výrokové logiky
  5. Věta o dedukci a dokazování formulí výrokové logiky
  6. Termy a formule predikátové logiky
  7. Interpretace, splnitelnost a pravdivost
  8. Axiomy a odvozovací pravidla predikátové logiky
  9. Věta o dedukci a dokazování formulí v predikátové logice
  10. Převody formulí na prenexní tvar
  11. Teorie 1. řádu a jejich modely
  12. Monadické logiky SkS a WSkS
  13. Intuicionistická, modální a temporální logika, Presburgerova aritmetika
Literatura referenční:
  1. M. Barr, Ch. Wells: Category Theory for Computing Science, Prentice Hall, New York, 1990
  2. B.C. Pierce: Basic Category Theory for Computer Scientists, The MIT Press, Cambridge, 1991
  3. R.F.C. Walters, Categories and Computer Science, Cambridge Univ. Press, 1991
Literatura studijní:
  1. J. Adámek, Matematické struktury a kategorie, SNTL, Praha, 1982
  2. B.C. Pierce, Basic Category Theory for Computer Scientists, The MIT Press, Cambridge, 1991
  3. R.F.C. Walters, Categories and Computer Science, Cambridge Univ. Press, 1991
Kontrolovaná výuka:
Zpracovaní a obhájení eseje.