Uniwersytet Warszawski, Wydział Fizyki - Centralny System Uwierzytelniania
Strona główna

Teoria obliczeń

Informacje ogólne

Kod przedmiotu: 3800-KOG-MS1-TO
Kod Erasmus / ISCED: 08.1 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0223) Filozofia i etyka Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Teoria obliczeń
Jednostka: Wydział Filozofii
Grupy: Przedmioty obowiązkowe, kognitywistyka, studia stacjonarne, pierwszego stopnia
Punkty ECTS i inne: 4.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
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
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin, 40 miejsc więcej informacji
Wykład, 30 godzin, 40 miejsc więcej informacji
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
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski, Wydział Fizyki.
ul. Pasteura 5, 02-093 Warszawa tel: +48 22 5532 000 https://www.fuw.edu.pl/ kontakt deklaracja dostępności USOSweb 7.0.3.0 (2024-03-22)