Matematické struktury v informatice

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra aplikované matematiky

Anotace:

Matematická sémantika programovacích jazyků.

Datové typy jako spojité svazy, Scottova topologie.

Procedury jako spojitá zobrazení.

Model lambda-kalkulu, vazba na funkcionální jazyky.

Základy teorie kategorií.

Požadavky:

Základní kurs programování, základní kurs algebry.

Osnova přednášek:

1. Motivace a úvod; sémantika jazyků. Uspořádání.

2. Uspořádání, svazy, úplné svazy.

3. Monotónní zobrazení, pevné body.

4. Topologie na množině. Okolí a uzávěr. Báze a subbáze.

5. Oddělování. Konvergence. Spojitost.

6. Datové typy jakožto spojité svazy. Scottova topologie.

7. Procedury jako spojitá zobrazení mezi datovými typy.

8. Složené datové typy. Typy funkcí.

9. Spojité svazy jako injektivní prostory.

10. Inverzní limity. Svazový model lambda-kalkulu.

11. Kategorie: objekty a morfismy. Mono- a epimorfismy.

12. Produkty, sumy, ekvalizéry. Diagramy a limity.

13. Exponenty, eval, kartézsky uzavřené kategorie.

Osnova cvičení:

1. Motivace a úvod; sémantika jazyků. Uspořádání.

2. Uspořádání, svazy, úplné svazy.

3. Monotónní zobrazení, pevné body.

4. Topologie na množině. Okolí a uzávěr. Báze a subbáze.

5. Oddělování. Konvergence. Spojitost.

6. Datové typy jakožto spojité svazy. Scottova topologie.

7. Procedury jako spojitá zobrazení mezi datovými typy.

8. Složené datové typy. Typy funkcí.

9. Spojité svazy jako injektivní prostory.

10. Inverzní limity. Svazový model lambda-kalkulu.

11. Kategorie: objekty a morfismy. Mono- a epimorfismy.

12. Produkty, sumy, ekvalizéry. Diagramy a limity.

13. Exponenty, eval, kartézsky uzavřené kategorie.

Cíle studia:

Studijní materiály:

S. Abramsky, A. Jung, Domain Teory

A. Asperti, G. Longo, Categories, Types and Structures

M. A. Arbib, E. G. Manes, The Categorial Imperative

G. Birkhoff, Lattice Theory

L. S. Bobrow, M. A. Arbib, Discrete Mathematics

H. Herrlich, G. E. Strecker, Category Theory

E. G. Manes, Categorial Theory Applied to Computation and Control

S. Mac Lane, G. Birkhoff, Algebra

S. Mac Lane, Categories for the Working Mathematician

B. C. Pierce, Basic Category Theory for Computer Scientists

D. Scott, Data types as lattices

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/MI-MSI/

Další informace:

https://courses.fit.cvut.cz/MI-MSI/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Bc. program Informatika, pro fázi studia bez oboru, 2015-2020 (volitelný předmět)
• Bc. obor Bezpečnost a informační technologie, 2015-2020 (volitelný předmět)
• Bc. obor Teoretická informatika, 2015-2020 (volitelný předmět)
• Bc. obor Počítačové inženýrství, 2015-2020 (volitelný předmět)
• Bc. obor Informační systémy a management, 2015-2020 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2015-2020 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2015-2020 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Počítačová grafika, 2015-2020 (volitelný předmět)
• Bc. obor Znalostní inženýrství, 2018-2020 (volitelný předmět)
• Mgr. specializace Počítačová bezpečnost, 2020 (volitelný předmět)
• Mgr. specializace Návrh a programování vestavných systémů, 2020 (volitelný předmět)
• Mgr. specializace Počítačové systémy a sítě, 2020 (volitelný předmět)
• Mgr. specializace Manažerská informatika, 2020 (volitelný předmět)
• Mgr. specializace Softwarové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2020 (volitelný předmět)
• Mgr. specializace Webové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Znalostní inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2020 (volitelný předmět)
• Mgr. program, pro fázi studia bez specializace, ver. pro roky 2020 a vyšší (volitelný předmět)
• Bc. specializace Informační bezpečnost, 2021 (volitelný předmět)
• Bc. specializace Manažerská informatika, 2021 (volitelný předmět)
• Bc. specializace Počítačová grafika, 2021 (volitelný předmět)
• Bc. specializace Počítačové inženýrství, 2021 (volitelný předmět)
• Bc. program, pro fázi studia bez specializace, 2021 (volitelný předmět)
• Bc. specializace Webové inženýrství, 2021 (volitelný předmět)
• Bc. specializace Umělá inteligence, 2021 (volitelný předmět)
• Bc. specializace Teoretická informatika, 2021 (volitelný předmět)
• Bc. specializace Softwarové inženýrství, 2021 (volitelný předmět)
• Bc. specializace Počítačové systémy a virtualizace, 2021 (volitelný předmět)
• Bc. specializace Počítačové sítě a Internet, 2021 (volitelný předmět)
• Study plan for Ukrainian refugees (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2023 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2023 (volitelný předmět)
• Bc. specializace Informační bezpečnost, 2024 (volitelný předmět)
• Bc. program, pro fázi studia bez specializace, 2024 (volitelný předmět)
• Bc. specializace Manažerská informatika, 2024 (volitelný předmět)
• Bc. specializace Počítačová grafika, 2024 (volitelný předmět)
• Bc. specializace Softwarové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Webové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Počítačové sítě a Internet, 2024 (volitelný předmět)
• Bc. specializace Počítačové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Počítačové systémy a virtualizace, 2024 (volitelný předmět)
• Bc. specializace Umělá inteligence, 2024 (volitelný předmět)
• Bc. specializace Teoretická informatika, 2024 (volitelný předmět)