Diff for ''

Revision 10
Author:
black
Time:
2022-10-10 00:41
Revision 9
Time:
2024-09-18 21:04
Comment:
Automatizovaná konverze z MediaWiki do Markdownu
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
{{Předmět|Základy složitosti a vyčíslitelnosti|Petr Kučera|NTIN090}}

Úvodní kurz do složitosti a vyčíslitelnosti. Lze nahradit předměty [Vyčíslitelnost I](Vyčíslitelnost%20I) a [Složitosti I](Složitost%20I). 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).

# Zápisky #

[Řešené otázky NTIN090](Řešené%20otázky%20NTIN090)

# 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](Konstrukce%20PRF%20z%20axiomů%20a%20odvozovacích%20pravidel)
    * Ú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.

# Zdroje #

* [Stránka předmětu](http://ktiml.mff.cuni.cz/%7Ekucerap/NTIN090/)
* [Poznámky z cvičení](http://forum.matfyz.info/download/file.php?id=546)
* [Emulátor primitivně rekurzivních funkcí](http://forum.matfyz.info/download/file.php?id=553)
* [Johančiny pohádky z vyčíslitelnosti](http://web.archive.org/web/20100626015101/http://atrey.karlin.mff.cuni.cz/%7Ejohanka/vyuka/pohadky_vycislitelnost.html)