NEŠTRUKTÚROVANÉ ROZPRAVY O ŠTRUKTÚRACH:

Kapitoly z matematiky pre informatikov (1)

Zimný semester 2018/2019

Rozvrh:

Pondelok, 16:30 – 18:00, miestnosť M-XI

Streda, 14:00 – 15:30, miestnosť M-XII

Kontakt:

Peter Kostolányi

e-mail: kostolanyi zavináč fmph a tak ďalej

miestnosť: M-227

Skriptá:

Počas semestra bude vznikať predbežná verzia skrípt k predmetu. Tieto skriptá nemajú byť vernou kópiou prednášok – pôjde o technickejšie spracovanie rovnakého materiálu. Ambíciou je predovšetkým poskytnúť „dokumentáciu” k zrejmým (avšak často nepríjemným) formálnym detailom vynechaným na prednáške a takisto aj zbierku odkazov na súvisiacu literatúru.

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é.

• Predbežná verzia prvých štyroch kapitol na stiahnutie (zvyšné kapitoly pribudnú niekedy časom).

Sylaby prednášok:

Prednáška č. 1 (24. septembra 2018)

• Úvod do predmetu. Orientované grafy, ohodnotené orientované grafy a ich matice susednosti. Príklady na kombinatorický význam mocniny a iterácie matice susednosti ohodnoteného grafu nad rôznymi štruktúrami.
• Skriptá: oddiely 1.1 a 1.2.

Prednáška č. 2 (26. septembra 2018)

• Polokruhy, úplné a spočítateľne úplné polokruhy, konečné automaty nad spočítateľne úplným polokruhom.
• Skriptá: oddiely 1.3, 1.4 a 1.5.

Prednáška č. 3 (1. októbra 2018)

• Algoritmus na výpočet iterácie štvorcovej matice, vzorce pre iteráciu blokovej matice, normálny tvar konečných automatov nad spočítateľne úplnými polokruhmi, racionálne výrazy nad polokruhmi a racionálne prvky polokruhu.
• Skriptá: oddiely 1.6, 1.7 a 1.8.

Prednáška č. 4 (3. októbra 2018)

• Formálne mocninové rady o jednej premennej z.
• Skriptá: oddiel 2.1.

Prednáška č. 5 (8. októbra 2018)

• Aplikácie mocninových radov v kombinatorike, formálne mocninové rady o niekoľkých komutatívnych a nekomutatívnych premenných.
• Skriptá: oddiely 2.2, 2.3 a 2.4.

Prednáška č. 6 (10. októbra 2018)

• Identity pre iteráciu súčtu a iteráciu súčinu, úvod do automatov s váhami.
• Skriptá: oddiely 2.5 a 2.6.

Prednáška č. 7 (15. októbra 2018)

• Normálne tvary automatov s váhami, racionálne mocninové rady.
• Skriptá: oddiely 2.7 a 2.8.

Prednáška č. 8 (17. októbra 2018)

• S-reprezentácie, začiatok teórie automatov s váhami nad poľom.
• Skriptá: oddiel 2.9 a začiatok oddielu 2.10 (po vetu 2.10.13).

Prednáška č. 9 (22. októbra 2018)

• Pokračovanie teórie automatov s váhami nad poľom.
• Skriptá: stred oddielu 2.10 (od definície 2.10.14 po vetu 2.10.21).

Prednáška č. 10 (24. októbra 2018)

• Minimalizácia automatov s váhami nad poľom.
• Skriptá: koniec oddielu 2.10 (od poznámky 2.10.22).

Prednáška č. 13 (5. novembra 2018)

• Použitie automatov s váhami na kódovanie obrazu. Stručne o niektorých ďalších témach súvisiacich s automatmi s váhami.
• Skriptá: oddiely 2.11 a 2.12.

Prednáška č. 14 (7. novembra 2018)

• Vlastné čísla a vlastné vektory.
• Skriptá: oddiel 3.1 a začiatok oddielu 3.2 (po tvrdenie 3.2.6).

Prednáška č. 15 (12. novembra 2018)

• Ekvivalentné charakterizácie diagonalizovateľných matíc a ukážkové aplikácie diagonalizácie.
• Skriptá: zvyšok oddielu 3.2 (od tvrdenia 3.2.7) a oddiel 3.3.

Prednáška č. 16 (14. novembra 2018)

• Zovšeobecnené vlastné vektory a úvod k Jordanovmu kanonickému tvaru matice.
• Skriptá: oddiel 3.4 a začiatok oddielu 3.5 (po poznámku 3.5.6).

Prednáška č. 17 (19. novembra 2018)

• Pokračovanie Jordanovho kanonického tvaru, Vandermondova a zovšeobecnená Vandermondova matica, enumerácia sledov v multigrafe.
• Skriptá: zvyšok oddielu 3.5 (za poznámkou 3.5.6) a oddiely 4.1 a 4.2.

Prednáška č. 18 (21. novembra 2018)

• Enumerácia slov v racionálnom jazyku a úvod do Perronovej-Frobeniovej teórie.
• Skriptá: oddiel 4.3 a začiatok oddielu 4.4 (po dôsledok 4.4.10).

Prednáška č. 19 (26. novembra 2018)

• Pokračovanie Perronovej-Frobeniovej teórie.
• Skriptá: stred oddielu 4.4 (od lemy 4.4.11 po vetu 4.4.15).

Prednáška č. 20 (28. novembra 2018)

• Záver Perronovej-Frobeniovej teórie.
• Skriptá: záverečná časť oddielu 4.4, okrem normálneho tvaru reducibilnej matice (od vety 4.4.16 po vetu 4.4.19).

Prednáška č. 21 (3. decembra 2018)

• Normálny tvar reducibilnej matice. Primitívne matice a aperiodické grafy. Prvá z aplikácií Perronovej-Frobeniovej teórie.
• Skriptá: koniec oddielu 4.4 (od definície 4.4.20), oddiel 4.5 a začiatok oddielu 4.6 (príklad 4.6.1).

Prednáška č. 22 (5. decembra 2018)

• Pokračovanie aplikácií Perronovej-Frobeniovej teórie. Diferenčné rovnice.
• Skriptá: zvyšok oddielu 4.6 (počnúc príkladom 4.6.2) a oddiel 4.7.
• Diferenčné rovnice zatiaľ v skriptách spísané nie sú. Odporúčané čítanie k nim: Elaydi, S.: An Introduction to Difference Equations. New York: Springer, tretie vydanie, 2005 (predovšetkým kapitoly 2 a 3).

Prednáška č. 23 (10. decembra 2018)

• Základy spektrálnej teórie grafov (spektrálne vlastnosti symetrických matíc, Rayleighove podiely, regulárnosť a obyčajné spektrum, súvislosť a laplaceovské spektrum).
• Odporúčané čítanie: Cvetković, D.; Rowlinson, P.; Simić, S.: An Introduction to the Theory of Graph Spectra. Cambridge: Cambridge University Press, 2010.
• Ďalšie odporúčané čítanie: Godsil, C.; Royle, G.: Algebraic Graph Theory. New York: Springer, 2001.
• Kurz spektrálnej teórie grafov z Yale University.

Prednáška č. 24 (12. decembra 2018)

• Enumerácia kostier grafu pomocou Laplaceovej matice, Cayleyho vzorec. Úvod do univerzálnej algebry (algebry, homomorfizmy algebier, podalgebry, súčiny algebier, kongurencie, faktorové algebry).
• Odporúčané čítanie k enumerácii kostier: Godsil, C.; Royle, G.: Algebraic Graph Theory. New York: Springer, 2001.
• Odporúčané čítanie ku Cayleyho vzorcu: Matoušek, J.; Nešetril, J.: Kapitoly z diskrétní matematiky. Karolinum: Praha, tretie vydanie, 2007.
• Odporúčané čítanie k univerzálnej algebre: Almeida, J.: Finite Semigroups and Universal Algebra. World Scientific: Singapur, 1994.
• Ďalšie odporúčané čítanie k univerzálnej algebre: Pultr, A.: Matematické struktury. Učebný text MFF UK v Prahe, 2005.

Prednáška č. 25 (17. decembra 2018)

• Pokračovanie univerzálnej algebry (prvá veta o izomorfizme, algebry termov, variety algebier, voľné algebry, Birkhoffova veta o varietach).

Prednáška č. 26 (19. decembra 2018)

• Prechodový monoid deterministického konečného automatu, rozoznateľné jazyky a ich ekvivalencia s racionálnymi. Syntaktický monoid a Myhillova-Nerodova veta. Neformálne o varietach formálnych jazykov.
• Odporúčané čítanie o prechodových a syntaktických monoidoch: Sakarovitch, J.: Elements of Automata Theory. Cambridge: Cambridge University Press, 2009.
• Odporúčané čítanie o varietach formálnych jazykov: Pin, J.-E.: Varieties of Formal Languages. Londýn: North Oxford Academic Publishers, 1986.
• Ďalšie odporúčané čítanie: Pin, J.-E.: Mathematical Foundations of Automata Theory, 2018.