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

Kapitoly z matematiky pre informatikov (1)

Zimný semester 2022/2023

Časy prednášok:

Utorok, 14:00 – 15:30, miestnosť M-213

Streda, 14:50 – 16:20, miestnosť M-213

Kontakt:

Peter Kostolányi

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

miestnosť: M-227

Skriptá:

Počas semestra bude postupne pribúdať 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 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 skrípt na stiahnutie.

Domáce úlohy:

V priebehu semestra budú zverejnené dve sady domácich úloh. Na zisk pozitívneho hodnotenia je nutné najneskôr do skúšky správne vyriešiť aspoň 6 úloh z každej sady.

• Prvá sada úloh.
• Druhá sada úloh.

Každú nájdenú podstatnejšiu chybu v najnovšej verzii skrípt možno uznať namiesto jednej úlohy (rovnako pre niekoľko drobných chýb alebo preklepov).

Sylaby prednášok:

Prednáška č. 1 (20. septembra 2022)

• Ú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 algebrami.
• Skriptá: oddiely 1.1 a 1.2.

Prednáška č. 2 (21. septembra 2022)

• Polokruhy, úplné a spočítateľne úplné polokruhy.
• Skriptá: oddiely 1.3 a 1.4.

Prednáška č. 3 (27. septembra 2022)

• Algoritmus na výpočet iterácie štvorcovej matice, vzorce pre iteráciu blokovej matice.
• Skriptá: oddiel 1.5.

Prednáška č. 4 (28. septembra 2022)

• Konečné automaty nad polokruhmi, ich normálny tvar a ekvivalencia s racionálnymi výrazmi nad polokruhmi.
• Skriptá: oddiely 1.6 až 1.8.

Prednáška č. 5 (4. októbra 2022)

• Formálne mocninové rady o jednej premennej.
• Skriptá: prvá časť oddielu 2.1 (po príklad 2.1.15).

Prednáška č. 6 (5. októbra 2022)

• Podiely formálnych mocninových radov. Vytvárajúce funkcie a ich jednoduché použitie. Formálne mocninové rady o niekoľkých komutatívnych premenných. Úvod do formálnych mocninových radov o niekoľkých nekomutatívnych premenných.
• Skriptá: tvrdenie 2.1.17, oddiely 2.2 a 2.3, úvod oddielu 2.4 (po definíciu 2.4.1).

Prednáška č. 7 (11. októbra 2022)

• Formálne mocninové rady o niekoľkých nekomutatívnych premenných. Matice formálnych mocninových radov. Identity pre iteráciu súčtu a súčinu.
• Skriptá: oddiely 2.4 až 2.6.

Prednáška č. 8 (12. októbra 2022)

• Automaty s váhami a ich normálne tvary.
• Skriptá: oddiely 3.1 až 3.4.

Prednáška č. 9 (18. októbra 2022)

• Racionálne výrazy s váhami a racionálne mocninové rady.
• Skriptá: oddiel 3.5.

Prednáška č. 10 (19. októbra 2022)

• Lineárne reprezentácie. Kvocienty racionálnych jazykov a minimálne deterministické konečné automaty. Úvod do automatov s váhami nad poľom.
• Skriptá: oddiel 3.6 a začiatok oddielu 3.7 (po vetu 3.7.12).
• Čítanie k odbočke do teórie jazykov: J. Sakarovitch, Elements of Automata Theory, Cambridge University Press, 2009: oddiel I.3.3.

Prednáška č. 11 (25. októbra 2022)

• Pokračovanie automatov s váhami nad poľom.
• Skriptá: zvyšok oddielu 3.7.

Prednáška č. 12 (26. októbra 2022)

• Ľavé a pravé inverzné matice. Minimalizácia automatov s váhami nad poľom.
• Skriptá: Oddiely 3.8 a 3.9.

Prednáška č. 13 (2. novembra 2022)

• Vlastné čísla a vlastné vektory.
• Skriptá: Oddiel 4.1 (po tvrdenie 4.1.16).

Prednáška č. 14 (8. novembra 2022)

• Priame súčty podpriestorov. Spektrum, algebraická násobnosť a geometrická násobnosť. Ekvivalentné charakterizácie diagonalizovateľnosti matice.
• Skriptá: Zvyšok oddielu 4.1 a oddiel 4.2.

Prednáška č. 15 (9. novembra 2022)

• Ukážkové aplikácie diagonalizácie. Mocniny lineárnych zobrazení.
• Skriptá: Oddiely 4.3 a 4.4.

Prednáška č. 16 (15. novembra 2022)

• Zovšeobecnené vlastné vektory.
• Skriptá: Oddiel 4.5.

Prednáška č. 17 (16. novembra 2022)

• Jordanov kanonický tvar. Mocniny matíc v Jordanovom kanonickom tvare.
• Skriptá: Oddiely 4.6 a 4.7.

Prednáška č. 18 (22. novembra 2022)

• Vplyv niektorých operácií na charakteristický polynóm a spektrum matice. Vandermondove a zovšeobecnené Vandermondove matice a determinanty. Enumerácia sledov v multigrafe a slov v racionálnom jazyku.
• Skriptá: Oddiely 4.8 až 5.3.

Prednáška č. 19 (23. novembra 2022)

• Perronova-Frobeniova teória nezáporných matíc, 1. časť.
• Skriptá: začiatok oddielu 5.4 (po vetu 5.4.14).

Prednáška č. 20 (29. novembra 2022)

• Perronova-Frobeniova teória nezáporných matíc, 2. časť.
• Skriptá: druhá časť oddielu 5.4 (od vety 5.4.15 po vetu 5.4.19).

Prednáška č. 21 (30. novembra 2022)

• Normálny tvar reducibilnej matice. Primitívne matice a aperiodické grafy. Aplikácie Perronovej-Frobeniovej teórie.
• Skriptá: zvyšok oddielu 5.4 a oddiely 5.5 až 5.7.

Prednáška č. 22 (6. decembra 2022)

• Diferenčné rovnice.
• Skriptá: kapitola 6.

Prednáška č. 23 (7. decembra 2022)

• Matice susednosti neorientovaných grafov. Spektrálne vlastnosti reálnych symetrických matíc. Rayleighove podiely, Rayleighov princíp a Courantova-Fischerova veta. Cauchyho veta o prepletaní vlastných čísel.
• Skriptá: oddiely 7.1 až 7.4.

Prednáška č. 24 (13. decembra 2022)

• Spektrálna charakterizácia regulárnych grafov. Kladne semidefinitné matice. Laplaceova matica grafu.
• Skriptá: oddiely 7.5 až 7.7.

Prednáška č. 25 (14. decembra 2022)

• Enumerácia kostier grafu. Algebraický stupeň súvislosti a Fiedlerove vektory.
• Skriptá: oddiely 7.8 až 7.10.