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

Kapitoly z matematiky pre informatikov (2)

Letný semester 2018/2019

Rozvrh:

Pondelok, 14:00 – 17:00, miestnosť M-IX

• Prednáška plánovaná na 25. marec sa presúva na utorok 19. marca, 15:40 do miestnosti M-VIII.
• Prednáška plánovaná na 8. apríl sa presúva na piatok 22. marca, 14:00 do miestnosti M-X.
• V pondelky 18. marca a 1. apríla budú prednášky vo zvyčajnom čase.

Kontakt:

Peter Kostolányi

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

miestnosť: M-227

Minulý semester:

• Stránka prvej časti tohto predmetu.

Sylaby prednášok:

Prednáška č. 1 (18. februára 2019)

• Möbiova inverzia na čiastočne usporiadaných množinách a klasická Möbiova inverzia. Enumerácia cyklických slov.
• Odporúčané čítanie:
  • Brualdi, R.: Introductory Combinatorics, 5. vydanie. Pearson, 2009 (oddiel 6.6).
  • Hall, M.: Combinatorial Theory, 2. vydanie. Wiley, 1986 (kapitola 2).

Prednáška č. 2 (25. februára 2019)

• Súvis klasickej Möbiovej inverzie s Dirichletovými radmi. Aplikácie Möbiovej inverzie. Príklady na súvis bezkontextových gramatík a algebraických systémov nad polokruhom formálnych jazykov (príprava na Ginsburgovu-Riceovu vetu).
• Odporúčané čítanie:
  • Bender, E. A.; Goldman, J. R.: On the Applications of Mobius Inversion in Combinatorial Analysis. The American Mathematical Monthly, ročník 82, č. 8, 1975: s. 789–803.

Prednáška č. 3 (4. marca 2019)

• Úplné čiastočne usporiadané množiny (CPO). Ginsburgova-Riceova veta. Spojité polokruhy a algebraické systémy nad nimi.
• Odporúčané čítanie:
  • Davey, B. A.; Priestley, H. A.: Introduction to Lattices and Order, 2. vydanie. Cambridge University Press, 2002 (kapitola 8).

Prednáška č. 4 (11. marca 2019)

• Ordinálne čísla.
• Odporúčané čítanie:
  • Balcar, B.; Štěpánek, P.: Teorie množin, 2. vydanie. Academia, 2000 (oddiely 1.5 a 2.1).

Prednáška č. 5 (18. marca 2019)

• Ordinálna aritmetika. Transfinitná indukcia. Charakterizácia CPO ako usporiadaných množín so suprémami reťazcov. Minimálne deterministické konečné automaty ako automaty kvocientov. Rôzne varianty pumpovacej lemy pre racionálne jazyky.
• Odporúčané čítanie:
  • Balcar, B.; Štěpánek, P.: Teorie množin, 2. vydanie. Academia, 2000 (koniec oddielu 2.1 a oddiel 2.3).
  • Markowsky, G.: Chain-Complete Posets and Directed Sets with Applications. Algebra Universalis, ročník 6, č. 1, 1976: s. 53–68.
  • Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, 2009 (oddiely I.1.3.3, I.3.3 a I.3.4).

Prednáška č. 6 (19. marca 2019)

• Ramseyova veta. Dôkaz Ehrenfeuchtovej-Parikhovej-Rozenbergovej pumpovacej lemy.
• Odporúčané čítanie:
  • Matoušek, J.; Nešetril, J.: Kapitoly z diskrétní matematiky, 3. vydanie. Karolinum, 2007 (oddiely 11.1 a 11.2).
  • Diestel, R.: Graph Theory, 5. vydanie. Springer, 2017 (oddiel 9.1).
  • Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, 2009 (oddiel I.3.4).

Prednáška č. 7 (22. marca 2019)

• Racionálne jazyky a MSO logika na konečných slovách.
• Odporúčané čítanie:
  • Kumar, K. N.: Notes on Automata, Logic, Games and Algebra.

Prednáška č. 8 (1. apríla 2019)

• Deskriptívna zložitosť a Faginova veta. Chomského-Schützenbergerova veta o reprezentácii.
• Odporúčané čítanie:
  • Immerman, N.: Descriptive Complexity. Springer, 1999.
  • Kozen, D.: Automata and Computability. Springer, 1997 (prednáška G).

Prednáška č. 9 (15. apríla 2019)

• Základy kombinatoriky na slovách.
• Odporúčané čítanie:
  • Lothaire, M.: Combinatorics on Words. Cambridge University Press, 1983 (kapitoly 1 a 2).

Prednáška č. 11 (29. apríla 2019)

• Pokračovanie kombinatoriky na slovách. Parikhova veta.
• Odporúčané čítanie:
  • Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, 2002 (kapitola 3).
  • Lothaire, M.: Combinatorics on Words. Cambridge University Press, 1983 (kapitola 3).
  • Kozen, D.: Automata and Computability. Springer, 1997 (prednáška H).

Prednáška č. 12 (6. mája 2019)

• Banachova veta o pevnom bode a jej aplikácia na systémy rovníc nad jazykmi a formálnymi mocninovými radmi. Wechlerova veta.
• Odporúčané čítanie:
  • Brabec, J.; Hrůza, B.: Matematická analýza II. SNTL, 1986 (oddiel I.7).
  • Autebert, J.-M.; Berstel, J.; Boasson, L.: Context-Free Languages and Pushdown Automata.

Prednáška č. 13 (13. mája 2019)

• Opakovanie.