Skuskovy test, 28/01/2010
(1) Ukazte, ze mnozina P = {p | p je prvocislo} ma primitivne rekurzivnu charakteristicku funkciu. Pri odvodzovani mozete vyuzit toho, ze scitanie, odcitanie, nasobenie, delenie, <, >, = su PRF a PRP
(2) Dokazte, ze existuje n, pre ktore plati, ze
(3) Rozhodnete, zda nasledujici verze halting problemu je algoritmicky rozhodnutelna. Je dan kod programu a ptame se, zda se tento program zastavi na pocitaci, ktery mame na stole.
(4) Ukazte, ze nasledujuci problem je NP-uplny:
i: Mnozina X, |X| = 3q a mnozina trojic C z X x X x X
p: Existuje C' z C taka, ze kazdy prvok z X sa vyskytuje v prave jedne trojici z C'?
(5) Popiste polynomialny algoritmus pre 2SAT (Formula v KNF, kde kazda klauzula ma prave 2 literaly)
[NTIN090] Základy složitosti a vyč. - Zk 28.1.2010
- Lada
- Donátor
- Příspěvky: 165
- Registrován: 9. 1. 2005 10:17
- Typ studia: Informatika Bc.
- Bydliště: Slaný / zácpa na Evropské
Re: [NTIN090] Základy složitosti a vyč. - Zk 28.1.2010
sakra, nekdo me predbehl:)
tak pridam jen poznamky:
3. byl chytak - odpoved je ze halting problem JE zastavitelny (nas stolni PC ma omezenou pamet, disk, registry atd -> E jen konecne mnozstvi jeho ruznych konfiguraci -> lze detekovat zacykleni)
5. lze udajne najit nekde na webu v minulych pisemkach ze Slozitosti
jinak na ustni prevod CRF -> TS a 3 SAT je NP uplny -
celkova uspesnost byla podle me docela vysoka, videl jsem 2x 4, hodne jednicek, semtam 2 nebo 3...
Hodne stesti ostatnim
Lada
tak pridam jen poznamky:
3. byl chytak - odpoved je ze halting problem JE zastavitelny (nas stolni PC ma omezenou pamet, disk, registry atd -> E jen konecne mnozstvi jeho ruznych konfiguraci -> lze detekovat zacykleni)
5. lze udajne najit nekde na webu v minulych pisemkach ze Slozitosti
jinak na ustni prevod CRF -> TS a 3 SAT je NP uplny -
celkova uspesnost byla podle me docela vysoka, videl jsem 2x 4, hodne jednicek, semtam 2 nebo 3...
Hodne stesti ostatnim
Lada
Hail to you, champion:o)
-
- Matfyz(ák|ačka) level I
- Příspěvky: 2
- Registrován: 21. 12. 2007 19:56
- Typ studia: Informatika Bc.
Re: [NTIN090] Základy složitosti a vyč. - Zk 28.1.2010
ja len dodam, ze ten 2SAT nevyriesil nik, tak ho ani nepocital, na ustnej som dostal dokaz Riceovej vety pomocou 1 prevoditelnosti a dokaz vety 17.8 ... skusal na chodbe, dost vela casu stravil v kancelarii.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 5
- Registrován: 21. 11. 2007 20:18
- Typ studia: Informatika Mgr.
Re: [NTIN090] Základy složitosti a vyč. - Zk 28.1.2010
Ahoj, nevíte někdo, jak řešit příklad (2). Zkoušel jsem větu o rekurzi, pak i její verzi s parametrem, ale zatím se mi nepodařilo dospět k výsledku. Myslím si, že přes tu větu o rekurzi to nějak musí jít. Mám problém s tím číslem k. To vypadá jako sjednocení množin přes všechna k. Ale nekonečné sjednocení asi nebude obecně rekurzivní. Díky. Pokud se mi podaří to vyřešit, řešení pošlu.