Teoria obliczeń 3501-KOG-MS1-TO
OD 2020/2021
W trakcie wykładu zostaną omówione następujące zagadnienia. Każde z poniżej wymienianych twierdzeń zostaje przedstawione przynajmniej ze szkicem dowodu.
-1 Języki regularne
– Definicja deterministycznych i niedeterministycznych automatów ze stosem. Twierdzenie o równoważności obydwu modeli.
– Własności domknięcia klasy języków regularnych.
– Algebraiczna charakteryzacja języków regularnych. Twierdzenie Myhilla-Nerode'a.
– Wyrażenia regularne. Równoważność wyrażeń regularnych i automatów skończonych.
– Lemat o pompowaniu dla języków regularnych.
-2 Języki bezkontekstowe
– Hierarchia Chomsky'ego i klasy gramatyk.
– Twierdzenie o postaci normalnej Chomsky'ego.
– Lemat o pompowaniu dla języków bezkontekstowych.
– Automaty ze stosem. Równoważność automatów ze stosem i gramatyk bezkontekstowych.
– Deterministyczne języki bezkontekstowe. Domknięcie deterministycznych języków bezkontekstowych na dopełnienia.
-3 Teoria obliczeń
– Definicja maszyn Turinga i języków rekurencyjnie przeliczalnych. Równoważność różnych typów maszyn (wielotaśmowe, niedeterministyczne, z ograniczoną taśmą).
– Całkowite maszyny Turinga i problemy rozstrzygalne. Własności domknięcia języków rekurencyjnych i rekurencyjnie przeliczalnych. Pojęcie funkcji rekurencyjnej.
– Kodowanie zbiorów skończonych w liczbach naturalnych. Definiowalność w liczbach naturalnych a rekurencyjna przeliczalność. Twierdzenie Posta.
– Nierozstrzygalność problemu stopu. Dwa pojęcia redukowalności.
-4 Twierdzenie Godla
– Reprezentowalność zbiorów rekurencyjnych w Q.
– Lemat przekątniowy.
– I i II Twierdzenie Godla. Nierozstrzygalność Entscheidungsproblem.
– Twierdzenie Tarskiego o niedefiniowalności prawdy.
-5 Złożoność obliczeniowa
– Definicja klas złożoności czasowej. Pojęcie problemu zupełnego dla danej klasy. Twierdzenie Cooke'a. Przykłady problemów NP-zupełnych.
– Definicja klas złożoności pamięciowej. Twierdzenie Savitcha.
DO 2019/2020
Pierwsza część kursu odpowiada skróconej wersji wprowadzenia do lingwistyki matematycznej. Zawiera więc wprowadzenie do teorii gramatyk, omówienie hierarchii Chomskiego, oraz przegląd najważniejszych urządzeń odpowiadających najważniejszym klasom gramatyk. Omówione zostaną więc języki regularne i automaty skończone, równoważność deterministycznych i niedeterministycznych automatów skończonych. Szerzej przedstawione zostaną języki bezkontekstowe i automaty ze stosem, ze szczególnym uwzględnieniem roli determinizmu i wieloznaczności składniowej. Omówione zostaną lematy o pompowaniu dla języków regularnych i bezkontekstowych oraz przykłady języków nie mieszczących się w tych klasach.
Druga część poświęcona jest ogólnemu pojęciu obliczalności. Podstawowe rozważane modele obliczeń, to: maszyny Turinga (– jako wzmocnienie pojęcia automatu) oraz maszyny RAM (– jako model obliczeń najbliższy doświadczeniu programistycznemu). Języki rozstrzygalne (rekurencyjne) i rekurencyjnie przeliczalne zdefiniowane zostaną w terminach maszyn RAM. Omówiona zostanie Teza Churcha, jej najważniejsze interpretacje i możliwe sposoby jej uzasadniania. Podana zostanie konstrukcja predykatu Kleene'ego i uniwersalnej maszyny RAM. Pokazana zostanie też nierozstrzygalność problemu stopu.
Trzecia część poświęcona jest związkom pomiędzy arytmetyczną definiowalnością a obliczalnością i rekurencyjną przeliczalnością.
Czwarta część poświęcona jest algorytmicznej wyuczalności w sensie Golda i Putnama. Omówione zostaną też zastosowania tego podejścia do problemu uczenia się języka.
Piąta część poświęcona jest zagadnieniom związanym z praktyczną obliczalnością. W szczególności omówiona zostanie teza Edmonds'a utożsamiająca klasy praktycznie obliczalne z klasą PTIME. Omówione zostanie też pojęcie NP-zupełności oraz pokazana zostanie NP-zupełność problemu spełniania. Tylko informacyjnie już niestety omówione zostaną pamięciowe klasy złożoności: LOGSPACE, NLOGSPACE, PSPACE. Omówiona zostanie też idea szyfrowania z kluczem publicznym na przykładzie metody RSA.
Pierwsza część pełni podwójną rolę. Zawiera ona wprowadzenie matematycznych narzędzi użytecznych przy opisie języków naturalnych i rozmaitych języków sztucznych. Drugą rolą tej części jest wprowadzenie matematycznych technik stosowanych w teorii obliczeń.
Pozostałe cztery części skoncentrują się na najważniejszych poznawczych granicach związanych z pojęciami obliczeniowymi. W szczególności więc wyeksponowane zostaną takie pojęcia jak: praktyczna obliczalność, obliczalność (rekurencyjność), rekurencyjna przeliczalność i algorytmiczna wyuczalność.
Założenia (opisowo)
Efekty kształcenia
Nabyta wiedza:
- Zna definicje i granice wyrażalności podstawowych matematycznych modeli obliczeń.
- Wie jaka jest różnica pomiędzy deterministycznymi i niedeterministycznymi modelami obliczeń. Wie, dla których klas języków modele deterministyczne i niedeterministyczne są równoważne.
- Rozumie znaczenie podstawowych twierdzeń limitacyjnych: I i II twierdzenie Godla, twierdzenie Tarskiego o niedefiniowalności prawdy i twierdzenie Turinga o nierozstrzygalności problemu stopu.
- Zna definicje podstawowych klas złożoności czasowej i pamięciowej. Wie na czym polega problem P vs. NP.
Nabyte umiejętności:
- Umie dowodzić (w typowych przypadkach), że dany język jest regularny/bezkontekstowy/rekurencyjny/rekurencyjnie przeliczalny. Zna kilka równoważnych modeli odpowiadającym powyższym klasom. Umie sprawdzić minimalność automatu skończonego.
- Umie dowodzić wyników negatywnych: potrafi pokazać (w typowych przypadkach), że dany język jest zbyt trudny, by rozpoznać go za pomocą danego modelu obliczeń.
- Potrafi szacować złożoność czasową i pamięciową typowych problemów.
Nabyte kompetencje społeczne:
- Umie precyzyjnie przedstawiać swoje argumenty.
- Umie analizować argumentację innych osób.
- Umie uważnie słuchać innych.
Kryteria oceniania
OD 2020/2021
wykład: egzamin pisemny + egzamin ustny (dla chętnych, umożliwający poprawienie oceny), ćwiczenia: częste i krótkie kartkówki sprawdzające bieżące opanowanie materiału + 2 kolokwia.
Dopuszczalna liczba nieobecności podlegających usprawiedliwieniu: wykład 3, ćwiczenia 3
DO 2019/2020
warunek przystąpienia do egzaminu: końcowe pisemne kolokwium
egzamin – 100%
Literatura
OD 2020/2021
M. Sipser – Introduction to the Theory of Computation, PWE Publishing Co., 1997
J. E. Hopcroft, R. Motwani i J. D. Ullman – Wprowadzenie do teorii automatów, języków i obliczeń, PWN 2003.
Ch. Papadimitriou - Złożoność obliczeniowa, WNT, Warszawa 2002.
Tobert I. Soare -Turing Computability, Springer 2016
DO 2019/2020
J. R. Shoenfield - Recursion Theory, Lecture Notes in Logic, Springer, 1991.
J. E. Hopcroft i J. D. Ullman – Wprowadzenie do teorii automatów, języków i obliczeń, PWN 2003.
Gold, E. Mark - Limiting Recursion, The Journal of Symbolic Logic, 1965.
Gold, E. Mark – Language identification in the limit, Information and Control, 1967.
Putnam, Hilary - Trial and error predicates and the solution to a problem of Mostowski , The Journal of Symbolic Logic, 1965.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: