Základy složitosti a vyčíslitelnosti
Z ωικι.matfyz.cz
| Základy složitosti a vyčíslitelnosti | ||||
|
Úvodní kurz do složitosti a vyčíslitelnosti. Lze nahradit předměty Vyčíslitelnost I a Složitosti I. Na zkoušku se lze přihlásit pouze po úspěšném absolvování zápočtového testu. Ten se zpravidla píše na posledním cvičení, případně na kterékoliv zkoušce (na test se není nutné se hlásit předem, stačí přijít).
Obsah
Zápisky
Zápočtový test
- 4 příklady z látky probrané na cvičeních (obtížnost nebývá odlišná)
- pro úspěšné splnění je třeba mít aspoň 3 příklady správně z následujících okruhů
- Konstrukce TS rozpoznávající nějaký jazyk
- Konstrukce PRF z axiomů a odvozovacích pravidel
- Úloha na s-m-n větu
- Převod jedné úlohy na druhou
- je znám případ, kdy Kučera dovolil nahlédnutí do slajdů z přednášky
10. 1. 2011
- Varianta A
- Napište TS, který rozpoznává následující jazyk: $ 1^{x+1}01^{x+2} $
- Ukažte, že $ f(x):=x! $ je PRF
- Ukažte, že existuje $ n $, pro které $ W_n=\{k*n|k\in\mathbb{N}\} $. (Pokud použijete nějakou primitivně rekurzivní nebo částečně rekurzivní funkci, zdůvodněte, proč jde o primitivně nebo částečně rekurzivní funkci.)
- Ukažte, že problém existence přípustného řešení 0-1 celočíselného lineárního programování je NP-úplný
- Varianta B
- Napište TS, který rozpoznává jazyk $ 1^{2^x}, x >= 0 $. Stačil popis/postup.
- Ukažte, že $ 2^x, x>=0 $ je PRF. (odvození)
- Ukažte, že existuje $ n $, pro které $ W_n=\{n^k | k \in\mathbb{N}\} $.
- Ukažte, že rozvrhování je NPC.
8.2.2010
- Predpokladejte, ze M je TS s obousmerne nekonecnou paskou. Popiste, jak z M vytvorite TS s jednosmerne nekonecnou paskou, ktery "dela totez" co M. (stacil slovni popis bez instrukci)
- Odvodte, ze funkce faktorial g(x)=x! je primitivne rekurzivni (za predpokladu, ze funkce nasobeni je PRF).
- Popiste 2-aproximacni algoritmus pro obchodniho cestujiciho s trojuhelnikovou nerovnosti, ktery pouziva minimalni kostru. Ukazte, ze skutecne dany algoritmus dosahuje zmineho aprox. pomeru.
- Ukazte, ze problem rozvrhovani je NP-uplny. (soucasti zadani byl popis problemu rozvrhovani z poznamek k cviceni)
4.2.2010
- Popsat TS pro jazyk $ 1^{k}01^{k^2} $.
- Ukázat, že div je PRF. +, sign, - a * lze použít bez odvozování.
- Ukázat, že existuje n, pro které $ W_n = \{0,..,n\} $.
- Za pomoci nějakého problému z přednášky ukázat, že klika je NP úplný problém.
28.1.2010
- Popište TS, který počítá funkci sčítání
- Ukažte, že $ x^y $ je PRF (můžete předpokládat, že sčítání a násobení PRF jsou)
- Za pomoci některého problému, jehož těžkost jsme si ukazovali na přednášce, ukažte, že batoh je NP-uplný.
- Definujeme-li problém DNF-SAT jako problém splnitelnosti formule v disjunktivně normální formě (DNF), jaká je složitost tohoto problému? Je to NP-úplný nebo patří do P?
27.1.2010
- Popiste TS pre jazyk L={a^{i}b^{i}c^{i}; i z N}
- Ukazke ze sign(x) je PRF
- Za pomoci nektereho problemu z prednasky dokazte, ze Hamiltonovska cesta HC(s,t) je NP-uplny problem
- Ukazte, ze pre hornovsku KNF existuje polynomialny algoritmus, ktory najde splnujuce ohodnotenie
13.1.2010
- popsat TS, ktery prijima jazyk { 1 na ( 2 na x), x >=0}
- odvodit ze x-1 je PRF
- pokud mam blackbox ktery resi rozhodovaci SAT (ANO/NE) jak pomoci nej sestrojim algoritmus ktery najde dane ohodnoceni promennych
- dokaz ze celociselne programovani je NP-uplne
Zkouška
- zkouška probíhá písemně s následnou debatou nad řešením.
- v každé písemce je příklad na Riceovu větu
- všechny příklady na převody bere Kučera z doporučené literatury, konkrétně - Garey, Johnson: Computers and intractability - a guide to the theory of NPcompleteness, W.H. Freeman 1978. Bere pouze ty jednodušší ze začatku. Není problém zapůjčit tuto knihu v knihovně, je tam prý v několika výtiscích.
