Równania w Słowach

Wykład: wtorek, 14–16, sala 140
Ćwiczenia: wtorek, 16–18, sala 5

Listy zadań, notatki.

Lista zadań, notatki

Punktacja

Punkty.

Plan wykładów

Plan jest mocno orientacyjny, jeden temat powinien odpowiadać jednemu wykładowi, choć czasem zapewne będzie to więcej.
  1. Równania w słowach: historia, podstawowe własności. SLP. Prosty algorytm używający SLP.
  2. Algorytm działający w PSPACE.
  3. Wykładnik periodyczności: wstęp i dowód dla słów jednoliterowych.
  4. Okresowość, słowa prymitywne. Wykładnik periodyczności: ogólny przypadek.
  5. Równania kwadratowe. Powody. Algorytm Plotkina. Uwaga o równaniach kwadratowych w grupie wolnej.
  6. Równania z jedną zmienną. Algorytm kombinatoryczny o czasie działania O(n log n).
  7. Równania z jedną zmienną: kombinatoryczny algorytm o czasie działania O(n + #X log n).
  8. Równania z jedną zmienną: algorytm o czasie działania O(n + #X log n) oparty o kompresję.
  9. Równania z dwoma zmiennymi. Czemu, własności. Informacja o algorytmie wielomianowym.
  10. Nieparametryzowalność zbioru wszystkich rozwiazań.
  11. Równania w grupie wolnej: redukcja do równań w słowach z inwersją i więzami regularnymi.
  12. Skończona reprezentacja wszystkich rozwiązań.
  13. Nierozstrzygalność teorii równań w słów. Informacja o rozstrzygalności dla grupy wolnej. Rozstrzygalność teorii pozytywnej dla grupy wolnej.
  14. Monadyczna unifikacja drugiego rzędu: jej związki z równaniami w słowach i przynależność do NP.
W zależności od zainteresowań słuchaczy, pozostałe wykłady mogą być poświęcone powiązanym tematom z teorii grup albo algorytmiki albo termom.

Notatki

Do wykładu będą notatki, ale niestety po angielsku i nie należy oczekiwać, że będą idealnie zredagowane i "równe" — niektóre części są wyraźnie lepiej napisane, niż inne. Tu jest poprzednia wersja notatek.

Egzamin

Jeśli grupa będzie liczyła ≤ 15 osób, egzamin będzie ustny, w przeciwnym przypadku: pisemny. Egzamin poprawkowy, który mam nadzieję nie będzie konieczny, będzie ustny.