Theory of Computations

General data

Course ID:	3501-KOG-MS1-TO
Erasmus code / 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) Philosophy and ethics The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title:	Theory of Computations
Name in Polish:	Teoria obliczeń
Organizational unit:	Institute of Philosophy
Course groups:
ECTS credit allocation (and other scores):	(not available) Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. view allocation of credits
Language:	Polish
Prerequisites (description):	(in Polish) Wymagane jest obycie z podstawowymi pojęciami matematycznymi oraz praktyczna znajomość pojęcia dowodu matematycznego.
Short description:	Lecture's main obective is to discuss the basic mathematical models of computation and classes of languages used in logic and theoretical computer science. This include definitions and basic properties of regular, context-free, computable and computably enumerable languages together with models of computations capturing them (inter alia deterministic and nondeterministic finite automata, context-free grammars, pusdown automata, Turing machines). The proofs of fundamental „limitative” results will be given, including the I-st Godel's theorem, Tarski's undefinability of truth theorem, undecidability of the halting problem and Entscheidungsproblem, pumping lemmas for regular and context-free languages. The last lectures present basic classes of time and space complexity, including the statement of the P vs NP problem.
Full description:	(in Polish) 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ść.
Bibliography:	(in Polish) 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.
Learning outcomes:	(in Polish) 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.
Assessment methods and assessment criteria:	(in Polish) 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%

This course is not currently offered.

Course descriptions are protected by copyright.
Copyright by University of Warsaw.