NEŠTRUKTÚROVANÉ ROZPRAVY O ŠTRUKTÚRACH:
Kapitoly z matematiky pre informatikov (2)
Letný semester 2020/2021
Rozvrh:
Videá prednášok a materiály k prednáškam budú postupne zverejňované v MS Teams (tím FMFI-Neštruktúry2-2-INF-276-2020/21, študijné materiály v kanáli General).
Kontakt:
Peter Kostolányi
e-mail: kostolanyi zavináč fmph a tak ďalej
miestnosť: M-227
Minulý semester:
Sylaby prednášok:
Prednáška č. 1 (15. februára 2021)
- Úvod do metrických priestorov (definícia, príklady). Minkowského nerovnosť.
Prednáška č. 2 (16. februára 2021)
- 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.
Prednáška č. 3 (22. februára 2021)
- Úplné metrické priestory. Súčinové metriky. Veta o zúplnení.
Prednáška č. 4 (23. februára 2021)
- Spojité zobrazenia medzi metrickými priestormi. Rovnomerná spojitosť. Topologická a lipschitzovská ekvivalencia metrík.
Prednáška č. 5 (1. marca 2021)
- Kompaktné metrické priestory.
Prednáška č. 6 (2. marca 2021)
- Banachova veta o pevnom bode a jej aplikácie.
Prednáška č. 7 (8. marca 2021)
- Základné pojmy univerzálnej algebry.
Prednáška č. 8 (9. marca 2021)
- Kongruencie a faktorové algebry. Súvis kongruencií a surjektívnych homomorfizmov, prvá veta o izomorfizme.
Prednáška č. 9 (15. marca 2021)
- Algebry termov. Uzáverové operátory na triedach algebier. Variety algebier. Charakterizácia variety generovanej triedou algebier.
Prednáška č. 10 (16. marca 2021)
- Identity a Birkhoffova veta o varietach.
Prednáška č. 11 (22. marca 2021)
- Podvariety. Voľné algebry a ich príklady.
Prednáška č. 12 (23. marca 2021)
- Ďalšie príklady voľných algebier. Prezentácie algebier. Súvis prezentácií monoidov s prepisovacími systémami.
Prednáška č. 13 (29. marca 2021)
- Roznávanie jazykov homomorfizmami do monoidov, rozoznateľné jazyky a ich ekvivalencia s racionálnymi. Rozoznávanie jazykov pologrupami. Charakterizácia rozoznateľných jazykov pomocou kongruencií a pravých kongruencií.
Prednáška č. 14 (30. marca 2021)
- 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.
Prednáška č. 16 (6. apríla 2021)
- Rozoznávanie jazykov usporiadanými monoidmi a usporiadanými automatmi. Syntaktické predusporiadanie a usporiadaný syntaktický monoid.
Prednáška č. 17 (12. apríla 2021)
- Úvod do štrukturálnej teórie pologrúp. Greenove relácie na všeobecných pologrupách.
Prednáška č. 18 (13. apríla 2021)
- Greenove relácie na konečných a periodických pologrupách.
Prednáška č. 19 (19. apríla 2021)
Prednáška č. 20 (20. apríla 2021)
- Hlavné faktory konečných pologrúp. Reesove maticové pologrupy a reprezentácia 0-jednoduchých pologrúp pomocou nich.
Prednáška č. 21 (26. apríla 2021)
- „Bezhviezdičkové” jazyky, aperiodické monoidy a prvá z implikácií Schützenbergerovej vety.
Prednáška č. 22 (27. apríla 2021)
- Druhá z implikácií Schützenbergerovej vety. Jazyky rozoznávané konečnými grupami.
Prednáška č. 23 (3. mája 2021)
- Pseudovariety konečných monoidov.
Prednáška č. 24 (4. mája 2021)
- Variety rozoznateľných jazykov a Eilenbergova korešpondencia.
Prednáška č. 25 (10. mája 2021)
- Implicitné operácie, pseudoidentity a Reitermanova veta pre monoidy.
Prednáška č. 26 (11. mája 2021)
- Jazyky rozoznávané R-triviálnymi monoidmi, v krátkosti o súvise J-triviálnych monoidov s jazykmi testovateľnými po častiach a o kladných varietach jazykov.
Odporúčaná literatúra k jednotlivým témam:
Základy teórie metrických priestorov:
- G. F. Simmons: Introduction to Topology and Modern Analysis. McGraw-Hill, 1963.
- I. Kaplansky: Set Theory and Metric Spaces 2nd ed. AMS, 2001.
Banachova veta o pevnom bode:
- J. Brabec, B. Hrůza: Matematická analýza II. SNTL, 1986.
Univerzálna algebra:
- J. Almeida: Finite Semigroups and Universal Algebra. World Scientific, 1994.
- P. M. Cohn: Universal Algebra. D. Reidel Publishing Company, 1981.
Súvis prezentácií monoidov s prepisovacími systémami:
- V. Diekert et al.: Discrete Algebraic Methods. De Gruyter, 2016.
Základy algebraickej teórie jazykov:
Štrukturálna teória pologrúp:
- M. Kunc: Pologrupy a formální jazyky.
- J. M. Howie: Fundamentals of Semigroup Theory. Clarendon Press, 1995.
- G. Lallement: Semigroups and Combinatorial Applications. John Wiley & Sons, 1979.
Pseudovariety konečných pologrúp:
Algebraická teória a variety formálnych jazykov: