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

Kapitoly z matematiky pre informatikov (1)

Zimný semester 2024/2025

Časy prednášok:

Pondelok, 12:20 – 13:50, akvárium M-XI

Utorok, 17:20 – 18:50, akvárium M-V

Kontakt:

Peter Kostolányi

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

miestnosť: M-227

Skriptá:

• Predbežná verzia skrípt k predmetu.

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

Skriptá nemajú byť vernou kópiou prednášok. Ich zámerom je predovšetkým poskytnúť „dokumentáciu” k detailom vynechaným na prednáške a takisto aj zbierku odkazov na súvisiacu literatúru.

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.

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

Hodnotenie predmetu:

Sylaby prednášok:

Prednáška č. 1 (23. septembra 2024)

• Ú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á: oddiel 1.1 a začiatok oddielu 1.2 (po príklad 1.2.4).

Prednáška č. 2 (24. septembra 2024)

• Pokračovanie príkladov kombinatorických interpretácií mocniny a iterácie matice. Polokruhy, úplné a spočítateľne úplné polokruhy.
• Skriptá: zvyšok oddielu 1.2 a oddiely 1.3 a 1.4.

Prednáška č. 3 (30. septembra 2024)

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

Prednáška č. 4 (1. októbra 2024)

• 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 (7. októbra 2024)

• Formálne mocninové rady o jednej premennej. Vytvárajúce funkcie a ich jednoduché použitie.
• Skriptá: vybrané časti oddielu 2.1, oddiel 2.2.

Prednáška č. 6 (8. októbra 2024)

• Formálne mocninové rady o niekoľkých komutatívnych premenných. Formálne mocninové rady o niekoľkých nekomutatívnych premenných. Matice formálnych mocninových radov.
• Skriptá: oddiely 2.3 až 2.5.

Prednáška č. 7 (14. októbra 2024)

• Identity pre iteráciu súčtu a iteráciu súčinu. Automaty s váhami nad polokruhom.
• Skriptá: oddiely 2.6 až 3.2 a začiatok oddielu 3.3.

Prednáška č. 8 (15. októbra 2024)

• Automaty s váhami (pokračovanie). Odepsilonovanie automatov s váhami nad spočítateľne úplnými polokruhmi. Racionálne výrazy s váhami a racionálne mocninové rady.
• Skriptá: zvyšok oddielu 3.3, oddiely 3.4 a 3.5.

Prednáška č. 9 (21. októbra 2024)

• 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 časť 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 č. 10 (22. októbra 2024)

• Rozhodovanie minimálnosti automatov s váhami nad poľom.
• Skriptá: zvyšok oddielu 3.7.

Prednáška č. 11 (28. októbra 2024)

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

Prednáška č. 12 (29. októbra 2024)

• Unárne racionálne rady nad poľom. Rozhodovacie problémy pre automaty s váhami nad poľom. Využitie automatov s váhami na kódovanie obrazu.
• Skriptá: oddiely 3.10 až 3.12.

Prednáška č. 13 (4. novembra 2024)

• Vlastné čísla a vlastné vektory.
• Skriptá: väčšina oddielu 4.1 (po tvrdenie 4.1.16).

Prednáška č. 14 (5. novembra 2024)

• 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 (11. novembra 2024)

• Ukážkové aplikácie diagonalizácie. Mocniny lineárnych zobrazení. Zovšeobecnené vlastné vektory.
• Skriptá: oddiely 4.3, 4.4 a väčšia časť oddielu 4.5 (po dôsledok 4.5.8).

Prednáška č. 16 (12. novembra 2024)

• Zovšeobecnené vlastné vektory (pokračovanie). Jordanov kanonický tvar.
• Skriptá: zvyšok oddielu 4.5 a väčšia časť oddielu 4.6 (po lemu 4.6.8 a jej dôkaz).

Prednáška č. 17 (18. novembra 2024)

• Mocniny matíc v Jordanovom kanonickom tvare. Vplyv niektorých operácií na charakteristický polynóm a spektrum matice. Vandermondove matice a ich determinanty. Hasseho derivácie.
• Skriptá: oddiely 4.7, 4.8 a prvá časť oddielu 5.1 (po tvrdenie 5.1.7 a jeho dôkaz).

Prednáška č. 18 (19. novembra 2024)

• Zovšeobecnená Vandermondova matica a jej determinant.
• Skriptá: zvyšok oddielu 5.1.