Základy složitosti a vyčíslitelnosti - NTIN090

• Anglický název: Introduction to Complexity and Computability
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• Semestr: zimní
• E-Kredity: 4
• Rozsah, examinace: zimní s.:2/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Garant: prof. RNDr. Ondřej Čepek, Ph.D.; RNDr. Petr Kučera, Ph.D.
• Vyučující: RNDr. Petr Kučera, Ph.D.; Mgr. Vladan Majerech, Dr.
• Třída: Informatika Mgr. - učitelské studium informatiky; Informatika Mgr. - Softwarové systémy; Informatika Mgr. - Matematická lingvistika; M Mgr. MSTR; M Mgr. MSTR > Povinně volitelné
• Kategorizace předmětu: Informatika > Teoretická informatika
• Záměnnost : {Složitost I a Vyčíslitelnost I}, NTIX090
• Neslučitelnost : NTIN062, NTIX090
• Je neslučitelnost pro: NTIX090
• Je prerekvizitou pro: NTIN064
• Je záměnnost pro: NTIN062, NTIX090

Anotace

čeština

Přednáška seznamující se základy teorie algoritmů, efektivní vyčíslitelnosti a teorie složitosti. První část přednášky je věnována základům vyčíslitelnosti: Turingovy stroje. RAM. Rekurzivní a rekurzivně spočetné jazyky a množiny. Algoritmicky nerozhodnutelné problémy. Druhá část přednášky je věnována studiu tříd časové a prostorové složitosti: Ekvivalence PSPACE a NPSPACE. Věty o hierarchiích. Třída NP. Polynomiální převoditelnost problémů. Důkazy NP-úplnosti. Aproximační algoritmy a schémata.

Poslední úprava: T_KTI (28.04.2015)

angličtina

This is a basic course on the theory of algorithms, computability and computational complexity. Roughly the first half of the course is devoted to the introduction to computability theory: Turing machines. Computable functions. Recursive and recursively enumerable languages and sets. Undecidable problems. The second half of the course is devoted to the study of space and time complexity classes: Equivalence of PSPACE and NPSPACE. Deterministic hierarchy theorems. Class NP. Polynomial reducibility among problems. Proofs of NP- completeness. Approximation algorithms and approximation schemes.

Poslední úprava: T_KTI (28.04.2015)

Cíl předmětu

čeština

Naučit základy teorie složitosti a vyčíslitelnosti.

Poslední úprava: T_KTI (23.05.2008)

angličtina

To teach basics of complexity theory and theory of computation.

Poslední úprava: Kučera Petr, RNDr., Ph.D. (04.09.2014)

Podmínky zakončení předmětu

čeština

Ke splnění předmětu je nutné získat zápočet a následně složit zkoušku. K získání zápočtu je potřeba získat požadovaný počet bodů za domácí úkoly řešené během semestru. V případě nedostatečného počtu bodů na konci semestru je možno některé z domácích úkolů nahradit řešením doplňkových domácích úkolů. Vzhledem k povaze kontroly studia předmětu nejsou náhradní termíny zápočtu přípustné. K zapsání na zkoušku je nutné mít zápočet. Zkouška je ústní, přičemž ústní části může předcházet písemná. S ohledem na situaci může zkouška proběhnout distančně.

Poslední úprava: Kučera Petr, RNDr., Ph.D. (18.09.2020)

angličtina

To finish the subject it is necessary to get the credit and then to pass the exam. To get get the credit, it is necessary to acquire a given number of points for homework which are being solved during the semester. In case a student does not have enough points at the end of semester, it is possible to get some additional points for additional homework. Due to the nature of conditions for getting the credit it is not possible to have substitute dates of obtaining the credit. It is necessary to have the credit before coming to exam. Exam is oral although the oral part may be preceded with a written test. Depending on the current situation, it is possible that the exam will proceed remotely.

Poslední úprava: Kučera Petr, RNDr., Ph.D. (18.09.2020)

Literatura

čeština

• Stránky k předmětu (kde je možno najít prezentaci z přednášky a skripta): http://ktiml.mff.cuni.cz/~kucerap/NTIN090

• Sipser, M. Introduction to the Theory of Computation. Vol. 2. Boston: Thomson Course Technology, 2006.

• Demuth O., Kryl R., Kučera A.: Teorie algoritmů I, II. SPN, 1984, 1989

• Soare R.I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987

• Odifreddi P.: Classical recursion theory, North-Holland, 1989

• Garey, Johnson. Computers and intractability - a guide to the theory of NP-completeness, W.H. Freeman 1978

• Arora S., Barak B.: Computational Complexity: A Modern Approach. Cambridge University Press 2009 (Draft ke stažení online).

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (25.05.2022)

angličtina

• Lecture web pages (lecture presentation can be found there): http://ktiml.mff.cuni.cz/~kucerap/NTIN090/index-en.html

• Sipser, M. Introduction to the Theory of Computation. Vol. 2. Boston: Thomson Course Technology, 2006.

• Demuth O., Kryl R., Kučera A.: Teorie algoritmů I, II. SPN, 1984, 1989 (Only in Czech)

• Soare R.I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987

• Odifreddi P.: Classical recursion theory, North-Holland, 1989

• Garey, Johnson. Computers and intractability - a guide to the theory of NP-completeness, W.H. Freeman 1978

• Arora S., Barak B.: Computational Complexity: A Modern Approach. Cambridge University Press 2009 (Draft available online).

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (25.05.2022)

Požadavky ke zkoušce

čeština

Zkouška sestává z písemné a ústní části. Písemná část předchází části ústní, její nesplnění znamená, že celá zkouška je hodnocena známkou nevyhověl(a) a ústní částí se již nepokračuje. Nesložení ústní části znamená, že při příštím termínu je nutno opakovat obě části zkoušky, písemnou i ústní. Známka ze zkoušky se stanoví na základě bodového hodnocení písemné i ústní části.

Písemná část bude sestávat ze tří příkladů z témat, která korespondují se sylabem přednášky a současně odpovídají tomu, co bylo procvičováno na cvičení.

Požadavky u ústní části zkoušky odpovídají sylabu předmětu v rozsahu, který byl prezentován na přednášce. Seznam možných otázek bude zveřejněn před začátkem zkouškového období na stránkách k předmětu.

Poslední úprava: Kučera Petr, RNDr., Ph.D. (08.10.2017)

angličtina

The exam has two parts, the written part and the oral part. The written part precedes the oral part and in case when a student fails to pass the written part, the exam does not continue with the oral part. In case the exam is finished due to failing the oral part, it is necessary to pass both the written part and the oral part at the next exam. Grade depends on the number of points given for both parts.

The written part consists of three assignments which correspond to the lecture syllabus. These assignments are similar to the exercises which are given during the practicals.

The requirements of the oral part correspond to the lecture syllabus to extent which was presented on the lecture during the semester. A list of possible questions is published at the web pages related to the subject before the exam period starts.

Poslední úprava: Kučera Petr, RNDr., Ph.D. (08.10.2017)

Sylabus

čeština

• 1. Turingovy stroje a jejich varianty. Churchova-Turingova teze

• 2. Halting problém a další nerozhodnutelné problémy

• 3. RAM a jeho ekvivalence s Turingovými stroji. Algoritmicky vyčíslitelné funkce

• 4. Rozhodnutelné a částečně rozhodnutelné jazyky a jejich vlastnosti

• 5. m-převoditelnost a m-úplné jazyky

• 6. Riceova věta

• 7. Nedeterministické Turingovy stroje, základní třídy složitosti, třídy P, NP, PSPACE, EXP

• 8. Savičova věta

• 9. Věty o deterministické prostorové a časové hierarchii

• 10. Polynomiální převoditelnost problémů, pojmy NP-těžkosti a NP-úplnosti

• 11. Cook-Levinova věta, příklady NP-úplných problémů, důkazy NP-úplnosti

• 12. Třídy co-NP a #P

• 13. Parametrizované algoritmy, třída FPT

• 14. Hypotézy o exponenciálním čase (ETH, SETH) a podmíněné dolní odhady.

• 15. Složitost a kryptografie

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (25.05.2022)

angličtina

• 1. Turing machines and their variants, Church-Turing thesis

• 2. Halting problem and other undecidable problems

• 3. RAM and their equivalence with Turing machines. Algorithmically computable functions

• 4. Decidable and partially decidable enumerable languages and their properties

• 5. m-reducibility and m-complete languages

• 6. Rice's theorem

• 7. Nondeterministic Turing machines, basic complexity classes, classes P, NP, PSPACE, EXP.

• 8. Savitch's theorem

• 9. Deterministic space and time hierarchy theorems

• 10. Polynomial reducibility among problems, NP-hardness and NP-completeness

• 11. Cook-Levin theorem, examples of NP-complete problems, proofs of NP-completeness

• 12. Classes co-NP and #P

• 13. Paremeterized algorithms, class FPT

• 14. Exponential time hypothesis (ETH, SETH) and conditional lower bounds

• 15. Complexity and cryptography

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (25.05.2022)