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

Kapitoly z matematiky pre informatikov (1)

Zimný semester 2020/2021

Časy prednášok:

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

Streda, 16:30 – 18:00, miestnosť M-X

Od 5. októbra výučba na univerzite opäť prechádza do online režimu.

• Všetci študenti zapísaní na predmet boli pridaní do tímu „FMFI-Neštruktúry1-2-INF-275-2020/21” v univerzitnom MS Teams.
• Prednášky budú podľa dohody prebiehať formou videí, ktoré budú zapísaným študentom postupne zverejňované v MS Teams. Video každej z prednášok pribudne najneskôr do pôvodne plánovaného termínu konania prednášky.
• Otázky sa možno pýtať priebežne mailom. V prípade záujmu je možné (mailom) dohodnúť termín konzultácie prostredníctvom videohovoru.

Kontakt:

Peter Kostolányi

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

miestnosť: M-227

Skriptá:

Počas semestra budú postupne pribúdať kapitoly predbežnej verzie 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 skrípt na stiahnutie.

Domáce úlohy:

V priebehu semestra budú zverejnené dve sady domácich úloh. Na zisk pozitívneho hodnotenia je nutné správne vyriešiť celkom aspoň 10 úloh. V prípade nesprávnych alebo neúplných riešení je možné každú úlohu odovzdať aj opakovane. Termín odovzdania úloh je ohraničený iba posledným termínom skúšky, je však odporúčané riešiť ich priebežne a na každý opravný pokus treba počítať aspoň jeden týždeň.

• 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 (21. septembra 2020)

• Ú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 (23. septembra 2020)

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

Prednáška č. 3 (28. septembra 2020)

• Algoritmus na výpočet iterácie štvorcovej matice, vzorce pre iteráciu blokovej matice. Konečné automaty nad polokruhmi, normálny tvar týchto automatov. Začiatok racionálnych výrazov nad polokruhmi.
• Skriptá: od oddielu 1.5 po približne polovicu oddielu 1.8.

Prednáška č. 4 (30. septembra 2020)

• Pokračovanie racionálnych výrazov nad polokruhmi, racionálne prvky spočítateľne úplného polokruhu. Formálne mocninové rady o jednej premennej z s koeficientmi v polokruhu.
• Skriptá: zvyšok oddielu 1.8 a začiatok oddielu 2.1 (po definíciu 2.1.8).

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

• Formálne mocninové rady o jednej premennej s komplexnými koeficientmi. Aplikácie mocninových radov v kombinatorike. Formálne mocninové rady o niekoľkých komutatívnych premenných.
• Skriptá: zvyšok oddielu 2.1 a oddiely 2.2 a 2.3.

Prednáška č. 6 (7. októbra 2020)

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

Prednáška č. 7 (12. októbra 2020)

• Konečné automaty s váhami a ich normálne tvary.
• Skriptá: oddiely 3.1 až 3.4.

Prednáška č. 8 (14. októbra 2020)

• Racionálne mocninové rady. S-reprezentácie.
• Skriptá: oddiely 3.5 a 3.6.

Prednáška č. 9 (19. októbra 2020)

• Automaty s váhami nad poľom.
• Skriptá: oddiel 3.7.

Prednáška č. 10 (21. októbra 2020)

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

Prednáška č. 11 (26. októbra 2020)

• Použitie automatov s váhami na kódovanie obrazu. Conwayovské a čiastočné conwayovské polokruhy.
• Skriptá: oddiely 3.10 a 3.11.

Prednáška č. 12 (28. októbra 2020)

• Vlastné čísla a vlastné vektory.
• Skriptá: oddiel 4.1.

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

• Spektrum, algebraická a geometrická násobnosť vlastných čísel. Ekvivalentné charakterizácie diagonalizovateľných matíc. Ukážkové aplikácie diagonalizácie.
• Skriptá: oddiely 4.2 až 4.4.

Prednáška č. 14 (4. novembra 2020)

• Zovšeobecnené vlastné vektory.
• Skriptá: oddiely 4.5 a 4.6.

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

• Jordanov kanonický tvar matice.
• Skriptá: oddiely 4.7 a 4.8.

Prednáška č. 16 (11. novembra 2020)

• Vandermondove a zovšeobecnené Vandermondove matice. Enumerácia sledov v multigrafe a slov v racionálnom jazyku.
• Skriptá: oddiely 5.1 až 5.3.

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

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

Prednáška č. 18 (18. novembra 2020)

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

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

• Primitívne matice a aperiodické grafy.
• Skriptá: oddiel 5.5.

Prednáška č. 20 (25. novembra 2020)

• Aplikácie Perronovej-Frobeniovej teórie.
• Skriptá: oddiely 5.6 a 5.7.

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

• Diferenčný počet a všeobecná teória diferenčných rovníc.
• Skriptá: oddiely 6.1 a 6.2.

Prednáška č. 22 (2. decembra 2020)

• Systémy lineárnych diferenčných rovníc prvého rádu a lineárne diferenčné rovnice k-teho rádu.
• Skriptá: oddiely 6.3 až 6.5.

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

• Neorientované grafy a ich matice susednosti. Spektrálne vlastnosti reálnych symetrických matíc.
• Skriptá: oddiely 7.1 a 7.2.

Prednáška č. 24 (9. decembra 2020)

• Rayleighove podiely, Rayleighov princíp a Courantova-Fischerova veta. Cauchyho veta o prepletaní vlastných čísel. Spektrálna charakterizácia regulárnych grafov.
• Skriptá: oddiely 7.3 až 7.5.

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

• Kladne semidefinitné matice. Laplaceova matica grafu a jej základné vlastnosti. Enumerácia kostier grafu.
• Skriptá: oddiely 7.6 až 7.8.

Prednáška č. 26 (16. decembra 2020)

• Algebraický stupeň súvislosti grafu. Fiedlerove vektory.
• Skriptá: oddiely 7.9 a 7.10.