Oferta dydaktyczna Instytutu Informatyki

Poniższa lista przedstawia przedmioty, które są uczone w Instytucie Informatyki, niektóre z nich co roku, niektóre z mniejszą częstotliwością Każdy student Instytutu Informatyki studiuje wg indywidualnego toku studiów, wybierając (zgodnie z pewnymi zasadami) z tej listy swoje przedmioty.

Jeżeli zastanawiasz się nad studiami u nas, jeżeli chcesz wiedzieć, czy na Uniwersytecie można zostać inżynierem, jeżeli interesuje Cię 1000 zł stypendium miesięcznie - zapraszamy na naszą stronę główną

Równania w słowach

Nazwa angielska (title in English):
Prowadzący (lecturer): Antoni Kościelski
Liczba punktów (ECTS): 9
Liczba punktów 2007 (ECTS since 2007): 6
Rodzaj (type): zaawansowany
Rodzaj od 2007 (type since 2007): informatyczny.I2
Liczba godzin (hours in semester):
wykład:30
ćwiczenia:30
Egzamin (exam): tak
Możliwe zajęcia w języku angielskim (can be taught in English): nie
Przedmiot zostal uaktualniony na biezacy rok (updated): nie
Semestr (semester): zimowy

Wymagania (prerequisites)

Opis (description)

Badania nad równaniami w słowach rozpoczął zespół kierowany przez rosyjskiego matematyka, prof. A. A. Markowa. Wydawało się, że za ich pomocą można rozwiązać dziesiąty problem Hilberta dotyczący rozstrzygalności problemu niesprzeczności równań diofantycznych (równań w liczbach naturalnych). Mimo że to się nie udało, badania doprowadziły jednak do rozwiązania problemu Hilberta (wynik Matjasiewicza) i opracowania przez Makanina algorytmu rozwiązującego problem istnienia rozwiązań (problem niesprzeczności) równań w słowach.

Danymi dla problemu niesprzeczności równań w słowach są dwa słowa, np. xax i baxab zapisane przy użyciu dwóch rodzajów liter: stałych (a i b) oraz zmiennych (x). Rozwiązując problem niesprzeczności odpowiadamy na pytanie, czy zmiennym można przypisać słowa nad alfabetem stałych, które podstawione w danych spowodują, że słowa te staną się identyczne (w rozważanym przykładzie tak będzie: równość xax=baxab zachodzi np. dla x=bab). Zauważmy też, że problem wyszukiwania wzorca redukuje się do podanego problemu niesprzeczności z bardzo prostymi równaniami.

Problem niesprzeczności równań w słowach jest naturalnym problemem dotyczącym najważniejszej struktury informatycznej, jest dobrze osadzony w matematyce i informatyce. Algorytm Makanina dowodzi, że należy do klasy NEXPTIME. Przypuszcza się, że należy do NP. Ma on duże znaczenie dla informatyki. Badane jest też kilka jego uogólnień. Głównym celem wykładu jest przedstawienie, jak badano dotychczas badano ten problem i dlaczego. Wykład w niewielkim stopniu korzysta z wiedzy przekazywanej na innych przedmiotach.

Program (program)

  1. Problem niesprzeczności jako przykład problemu unifikacji.
  2. Zbiór słów z algebraicznego punktu widzenia.
  3. Trochę ciekawych własności zbioru słów
  4. Algebraiczne metody rozwiązywania równań w słowach.
  5. Nie warto rozważać układów równań.
  6. Powody badania równań w słowach związane z logiką.
  7. Algorytmy Plotkina i Chmielewskiego.
  8. Nieparametryzowalność równań z dwoma zmiennymi i dwoma stałymi.
  9. Równania uogólnione i algorytm Makanina.
  10. Oszacowanie długości minimalnego rozwiązania.
  11. NP-trudność problemu.
  12. Górne oszacowania złożoności, twierdzenie Gutierreza.
  13. Równania z więzami regularnymi, twierdzenie Schulza.
  14. Metoda Plandowskiego.
  15. Informacja o równaniach w grupach wolnych.

Literatura (references)

Jeżeli jesteś zainteresowany studiowaniem w naszym instytucie, zapraszamy na stronę poświęconą tegorocznej rekrutacji.

Nazwa użytkownika (user name):
Hasło (password):