Teoria obliczeń
Informacje ogólne
Kod przedmiotu: | 3800-KOG-MS1-TO |
Kod Erasmus / ISCED: |
08.1
|
Nazwa przedmiotu: | Teoria obliczeń |
Jednostka: | Wydział Filozofii |
Grupy: |
Przedmioty obowiązkowe, kognitywistyka, studia stacjonarne, pierwszego stopnia |
Punkty ECTS i inne: |
4.00
|
Język prowadzenia: | polski |
Rodzaj przedmiotu: | fakultatywne |
Założenia (opisowo): | Wymagane jest obycie z podstawowymi pojęciami matematycznymi oraz praktyczna znajomość pojęcia dowodu matematycznego |
Skrócony opis: |
Głównym celem wykładu jest omówienie podstawowych matematycznych modeli obliczeń oraz klas języków wykorzystywanych w logice i informatyce teoretycznej. Omówione zostaną m.in. języki regularne, języki bezkontekstowe, problemy obliczalne i rekurencyjnie przeliczalne, a także podstawowe modele obliczeń im odpowiadające (deterministyczne i niedeterministyczne automaty skończone, gramatyki bezkontekstowe, automaty ze stosem, maszyny Turinga). Szczegółowo omówione zostaną lematy o pompowaniu dla języków regularnych i bezkontekstowych, twierdzenie o nierozstrzygalności problemu stopu. Wspomniane też są podstawowe metalogiczne twierdzenia limitacyjne ( I twierdzenie Godla i twierdzenie o nierozstrzygalności problemu tautologiczności dla logiki pierwszego rzędu). Na koniec zostaną omówione podstawowe klasy złożoności pamięciowej i czasowej, w szczególności problem P vs. NP. |
Pełny opis: |
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. |
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 |
Efekty uczenia się: |
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 |
Metody i 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 |
Zajęcia w cyklu "Semestr letni 2023/24" (w trakcie)
Okres: | 2024-02-19 - 2024-06-16 |
Przejdź do planu
PN WT ŚR CW
CZ PT WYK
CW
|
Typ zajęć: |
Ćwiczenia, 30 godzin, 40 miejsc
Wykład, 30 godzin, 40 miejsc
|
|
Koordynatorzy: | Michał Wrocławski | |
Prowadzący grup: | Michał Wrocławski | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie na ocenę Wykład - Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski, Wydział Fizyki.