PředmětyPředměty(verze: 962)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
Základy složitosti a vyčíslitelnosti - NTIX090
Anglický název: Introduction to Complexity and Computability
Zajišťuje: Studijní oddělení (32-STUD)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2022
Semestr: zimní
E-Kredity: 5
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
Způsob výuky: prezenční
Způsob výuky: prezenční
Je zajišťováno předmětem: NTIN090
Další informace: http://ktiml.mff.cuni.cz/~kucerap/NTIN090
Garant: prof. RNDr. Ondřej Čepek, Ph.D.
RNDr. Petr Kučera, Ph.D.
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
Prerekvizity : {NXXX007, NXXX008, NXXX009, NXXX010, NXXX011, NXXX012, NXXX013, NXXX019, NXXX020, NXXX021, NXXX026, NXXX027, NXXX028, NXXX029, NXXX032, NXXX034, NXXX035, NXXX036, NXXX037, NXXX038, NXXX039, NXXX040, NXXX051, NXXX052, NXXX053, NXXX056, NXXX066, NXXX067}
Záměnnost : {Složitost I a Vyčíslitelnost I}, NTIN090
Neslučitelnost : NTIN062, NTIN064, NTIN090
Je neslučitelnost pro: NTIN090
Je záměnnost pro: NTIN090
Anotace -
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)
Cíl předmětu -

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

Poslední úprava: T_KTI (23.05.2008)
Podmínky zakončení předmětu -

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)
Literatura -

  • 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)
Požadavky ke zkoušce -

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)
Sylabus -
  • 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)
 
Univerzita Karlova | Informační systém UK