Teoria obliczeń 3800-KOG-MS1-TO
W trakcie wykładu zostaną omówione następujące zagadnienia. Większość z poniżej wymienianych twierdzeń zostaje przedstawiona 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 Języki rekurencyjne i rekurencyjnie przeliczalne
– 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.
4 Języki nierekurencyjne
– Nierozstrzygalność problemu stopu. Dwa pojęcia redukowalności.
– Stopnie Turinga i ich podstawowe własności. Twierdzenie Friedberga-Muchnika.
– I i II Twierdzenie Godla. Nierozstrzygalność Entscheidungsproblem.
– Języki algorytmicznie wyuczalne.
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.
Rodzaj przedmiotu
Założenia (opisowo)
Koordynatorzy przedmiotu
W cyklu 2023L: | W cyklu 2024L: |
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, 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.
K_W02, K_W08, K_W14, K_W25, K_W38
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.
K_U02, K_U07, K_U13
Nabyte kompetencje społeczne:
- Umie precyzyjnie przedstawiać swoje argumenty.
- Umie analizować argumentację innych osób.
- Umie uważnie słuchać innych.
K_K01, K_K02, K_K07, K_K09
Kryteria oceniania
ćwiczenia: regularne kartkówki (40%) oraz kolokwium na koniec semestru (60%). Dodatkowe kolokwium ratunkowe podczas sesji (przed egzaminem) oraz kolejne podczas sesji poprawkowej – można z niego dostać maksymalnie 50%, co przekłada się na ocenę 3.
wykład: egzamin ustny składający się z trzech pytań. Pierwsze dwa pytania dotyczą w znacznym stopniu materiału z wykładu, trzecie pytanie jest praktyczne i polega na zaklasyfikowaniu języka do którejś ze znanych z zajęć kategorii i uzasadnieniu tej klasyfikacji. Wszystkie pytania są punktowane w sposób równy.
Studenci, który uzyskali z ćwiczeń ocenę 5 albo 5!, są zwolnieni z odpowiedzi na trzecie pytanie (automatycznie uzyskują z niego maksymalną możliwą liczbę punktów). Studenci, którzy uzyskali niższą ocenę, mogą zrezygnować z odpowiedzi na nie (przed zapoznaniem się z pytaniem) i wówczas dostają za to pytanie liczbę punktów proporcjonalną do wyniku z ćwiczeń.
Skala ocen: 5! – 95% pkt., 5 (bdb.) – od 90%, 4+ (db. plus) – od 82%, 4 (db.) – od 75%, 3+ (dst. plus) - od 60%, 3 – (dst.) od 50%, 2 – (ndst.) mniej niż 50%.
Dopuszczalna liczba nieobecności podlegających usprawiedliwieniu: 2
Literatura
● 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
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: