NEŠTRUKTÚROVANÉ ROZPRAVY O ŠTRUKTÚRACH:
Kapitoly z matematiky pre informatikov (2)
Letný semester 2024/2025
Časy prednášok:
Pondelok, 12:20 – 13:50, akvárium M-VIII
Streda, 9:50 – 11:20, skleník
Kontakt:
Peter Kostolányi
e-mail: kostolanyi zavináč fmph a tak ďalej
miestnosť: M-227
Skriptá:
Keďže je predbežná, môže momentálne zverejnená verzia skrípt obsahovať väčšie množstvo chýb. Každé upozornenie na ne je vítané.
Domáce úlohy:
Minulý semester:
Sylaby prednášok:
Prednáška č. 1 (17. februára 2025)
Prednáška č. 2 (19. februára 2025)
Prednáška č. 3 (24. februára 2025)
- Úvod do metrických priestorov (definícia, príklady). Minkowského nerovnosť.
- Skriptá: oddiel 1.1.
Prednáška č. 4 (26. februára 2025)
- Základy topológie metrických priestorov (okolia, otvorené a uzavreté množiny, hromadné body, uzáver, vnútro a hranica množiny). Limita postupnosti bodov metrického priestoru. Pojem cauchyovskej postupnosti. Limita zobrazenia medzi metrickými priestormi.
- Skriptá: oddiely 1.2 a 1.3.
Prednáška č. 5 (3. marca 2025)
- Úplné metrické priestory. Súčinové metriky. Veta o zúplnení.
- Skriptá: oddiel 1.4.
Prednáška č. 6 (5. marca 2025)
- Spojité zobrazenia medzi metrickými priestormi. Topologická a lipschitzovská ekvivalencia metrík.
- Skriptá: oddiely 1.5 a 1.6.
Prednáška č. 7 (10. marca 2025)
- Kompaktné metrické priestory.
- Skriptá: oddiel 1.7.
Prednáška č. 8 (12. marca 2025)
- Banachova veta o pevnom bode a jej aplikácie.
- Skriptá: oddiely 1.8 a 1.9.
Prednáška č. 9 (17. marca 2025)
- Prekladá sa na ďalší pondelok.
Prednáška č. 10 (19. marca 2025)
- Úvod do univerzálnej algebry.
- Skriptá: oddiel 2.1 a začiatok oddielu 2.2 (po príklad 2.2.11).
Prednáška č. 11 (24. marca 2025)
- Podalgebry, homomorfizmy a priame súčiny algebier. Kongruencie a faktorové algebry.
- Skriptá: zvyšok oddielu 2.2 a prvá časť oddielu 2.3 (po tvrdenie 2.3.13).
Prednáška č. 11 a pol (náhrada za prednášku č. 9, 24. marca 2025)
- Súvis kongruencií a surjektívnych homomorfizmov, prvá veta o izomorfizme.
- Skriptá: zvyšok oddielu 2.3.
Prednáška č. 12 (26. marca 2025)
- Algebry termov. Uzáverové operátory na triedach algebier. Variety algebier. Charakterizácia variety generovanej triedou algebier.
- Skriptá: oddiely 2.4 a 2.5.
Prednáška č. 13 (31. marca 2025)
- Identity a Birkhoffova veta o varietach.
- Skriptá: oddiel 2.6.
Prednáška č. 14 (2. apríla 2025)
- Podvariety. Voľné algebry. Niekoľko príkladov voľných algebier.
- Skriptá: oddiely 2.7, 2.8 a začiatok oddielu 2.9 (po príklad 2.9.5).
Prednáška č. 15 (7. apríla 2025)
- Pokračovanie príkladov voľných algebier. Definícia prezentácií algebier. Roznávanie jazykov homomorfizmami do monoidov, rozoznateľné jazyky a ich ekvivalencia s racionálnymi. Rozoznávanie jazykov pologrupami.
- Skriptá: zvyšok oddielu 2.9, začiatok oddielu 2.10, oddiely 3.1 a 3.2.
Prednáška č. 16 (9. apríla 2025)
- Študentská vedecká konferencia.
Prednáška č. 17 (14. apríla 2025)
- Charakterizácia rozoznateľných jazykov pomocou kongruencií a pravých kongruencií. Syntaktická kongruencia a pravá syntaktická kongruencia. Myhillova-Nerodova veta. Syntaktický homomorfizmus, syntaktický monoid a minimálny automat. Izomorfizmus prechodového monoidu minimálneho automatu so syntaktickým monoidom.
- Skriptá: oddiely 3.3 až 3.5.
Prednáška č. 18 (16. apríla 2025)
- Rozoznávanie jazykov usporiadanými monoidmi a usporiadanými automatmi. Syntaktické predusporiadanie a usporiadaný syntaktický monoid. Deterministické konečné automaty ako unárne algebry, súvis minimalizácie automatov s kongruenciami na takýchto algebrách. Automaty na konečných stromoch.
- Skriptá: oddiel 3.6.
- Čítanie k stromovým automatom: C. Löding, W. Thomas: Automata on Finite Trees. In: J.-É. Pin (ed.), Handbook of Automata Theory, vol. 1, ch. 7, pp. 235–264. EMS, 2021.
Prednáška č. 19 (21. apríla 2025)
Prednáška č. 20 (23. apríla 2025)
- Úvod do štrukturálnej teórie pologrúp. Greenove relácie na všeobecných pologrupách.
- Odporúčané čítanie: M. Kunc: Pologrupy a formální jazyky, oddiely 2.1 až 2.3.1.