Języki, automaty i obliczenia

seminaria magisterskie

Tematem seminarium jest szeroko rozumiana teoria automatów.

Omawiamy ciekawe wyniki dotyczące zarówno klasycznej teorii automatów, jak i związanych z nią tematów, czyli: logiki, algorytmicznej teorii gier, teorii obliczeń, a czasem teorii złożoności i innych działów informatyki teoretycznej. Staramy się żeby przedstawiane konstrukcje były interesujące z matematycznego punktu widzenia i żeby były w miarę możliwości związane z zainteresowaniami naukowymi prowadzących. W związku z tym w aktualnej chwili najwięcej referatów dotyczy automatów ze stosem lub licznikami, automatów ważonych oraz gier nieskończonych, przy czym tematyka jest zdecydowanie szersza.

Omawiamy wyniki związane z automatami skończonych wzbogaconymi o różne struktury (stos, liczniki, dane pochodzące z nieskończonego alfabetu, taśmy itd.), czyli innymi słowy z modelami obliczeń. Automaty mogą operować na słowach skończonych, nieskończonych, drzewach, a nawet grafach. Czasem po prostu akceptują daną strukturę (słowo / drzewo / inne), a czasem zwracają liczbę lub inną strukturę. Interesujemy się również zastosowaniami teorii automatów do innych dziedzin, typowym przykładem jest tu logika. Wiele twierdzeń dotyczących logiki opiera się na eleganckich technikach pochodzących z teorii automatów. Inny przykład to gry nieskończone, który w naturalny sposób często pojawiają się przy badaniu automatów. Teoria automatów wiąże się również ze złożonością obliczeniową, bo maszyna Turinga to przecież automat dwukierunkowy z nieskończoną taśmą. Na naszym seminarium czasem pojawiają się również inny ciekawe zagadnienia z informatyki teoretycznej, nawet jeśli nie są bezpośrednio związane z teorią automatów, logiką, ani z obliczeniami maszyn Turinga.

Na seminarium studenci referują polecone przez prowadzących tematy. Zazwyczaj polega to na przeczytaniu wskazanej pracy z czasopisma lub sprawozdania z konferencji poświęconych tej dziedzinie informatyki oraz przygotowaniu slajdów pod opieką jednego z prowadzących.

Współczesna literatura z tej dziedziny, w tym czasopisma naukowe i dane z Internetu. Szczegóły przedstawią prowadzący na pierwszych zajęciach.

Wiedza.

Poznaje wybrane problemy badawcze z głównego nurtu aktualnych badań naukowych w dziedzinie logicznych podstaw informatyki. Podejmuje własne badania, jakie staną się podstawą pracy magisterskiej.

Umiejętności.

1. Potrafi czytać ze zrozumieniem artykuły naukowe.

2. Potrafi komunikować innym wyniki naukowe w zrozumiały i atrakcyjny sposób.

3. Potrafi słuchać w sposób krytyczny i zadawać pytania innym referującym.

Kompetencje.

Zyskuje wiedzę na temat metodologii badań naukowych w dziedzinie logiki informatyce. Zyskuje ogólne rozeznanie w sprawie miejsc publikacji i ich prestiżu naukowego.

Warunkiem zaliczenia seminarium jest staranne przygotowanie i wygłoszenie przynajmniej jednego referatu w semestrze oraz - w zależności od roku - zatwierdzenie tematu pracy magisterskiej lub złożenie pracy.