Zkouska 2010-02-04

jkt · Příspěvek od **jkt** » 4. 2. 2010 18:30

Verze F:

1) Rozhodnete, zda mnozina $S = \{ e | W_e \text{ obsahuje nejake prvocislo} \}$ je rekurzivni, sve rozhodnuti zduvodnete.

2) Ukazte, ze mnozina S z predchoziho prikladu je rekurzivne spocetna.

3) Ukazde, ze $DSPACE(\log_2 n) \subseteq P$ .

4) Ukazte, ze nasledujici problem je polynomialne resitelny:

Omezeny soucet podmnoziny

Instance: Mnozina n prvku A, s kazdym prvkem $a \in A$ asociovana velikost $v(a) \in \{0,\ldots,n\}$ , cislo $B \ge 0$ .
Otazka: Existuje mnozina prvku $A' \subseteq A$ , pro niz plati, ze $\sum_{a \in A'} v(a) = B$ ?

5) S pomoci nektereho problemu probiraneho na prednasce ukazte, ze nasledujici problem je NP-uplny:

Nejvetsi spolecny podgraf

Instance: Grafy $G_1 = (V_1, E_1)$ a $G_2 = (V_2, E_2)$ , prirozene cislo $k \ge 0$ .
Otazka: Existuji mnoziny hran $E'_1 \subseteq E_1$ a $E'_2 \subseteq E_2$$, $$ |E'_1| = |E'_2| \ge k$ , pro nez jsou grafy $G'_1 = (V_1, E'_1)$ a $G'_2 = (V_2, E'_2)$ izomorfni? (Izomorfni = "vypadaji stejne").

jkt · Příspěvek od **jkt** » 4. 2. 2010 18:43

K tomu rovnou reseni:

1) Rovnou z Riceovy vety (snad se ani nemuselo ukazovat, ze to neni trivialni trida funkci).
2) ja to psal jak odukaz prevodu z K, coz bylo spatne.
3) Snadno, viz odhad, ze TS v case $n^i$ popise max. $n^i$ pasky, takze $\rarrow DSPACE(n^i) \subseteq DTIME(n^i)$ a zaroven $\exists i \in \mathbb{N}: \log_2 n \le n^i$ ; slo by ukazat i presneji pres odhad poctu konfiguraci: $\text{pocet konfiguraci} \le |Q| \times |\Sigma| \times \log_2 n$ , coz projdem nejhur v case $2^{c' \times \log_2 n}$ .
4)

Kód: Vybrat vše

b := array [0..B] of Bool; // vyznam "uz jsme na vaze [index]"
b[0] := True;
b[zbytek] := false;

for a in A:
  for i := B to 0:
    if i + v(a) <= B && b[i]:
      b[ i + v(a)] := true;
  if b[B]:
    return Nalezeno;
return Nelze

To jiste probehne v O(nB), jiste $B <= n^2$ -> je to v O(n^3). Je to korektni -- kazdou vec pouzijeme nejvys jednou, pokud dojdem na pozadovanou vahu, vrati OK, pokud nedojdem umre.

5) Po cca. hodinovem premysleni

jsem to dokazal uplnost za tri minuty prevodem z HK (+diskuse, ze je to z NP) -- chci ukazat, ze v G=(V,E) je HK <=> G1, G2 maji izomorfni podgraf. Polozim tedy G1 = G, G2 = kruznice nad |V| vrcholy. Tecka

.

Opet Kucerova poznamka, kterou jiz najdete ve foru ze vcerejska. Navic pry byl dnes stejny zapoctovy test jako vcera.

lukas.hermann · Příspěvek od **lukas.hermann** » 5. 2. 2010 12:23

Doplním řešení úlohy č. 2:

Stačí si definici té množiny přepsat jako: $S=\{e, (\exists p)(prime(p) \land \varphi_e(p)\downarrow)\}=\{e, (\exists p)(\exists s)(prime(p) \land \varphi_{e,s}(p)\downarrow)\}$ .

Platí, že S je rekurzivně spočetná právě tehdy, když ex. PRP $P(e, p, s)$ takový, že $S=\{e, (\exists p)(\exists s)P(e, p, s)\}$ . Stačí tedy říct (nemuselo se to dokazovat), že $P(e, p, s)=(prime(p) \land \varphi_{e,s}(p)\downarrow)$ je PRP (první se dá odvodit a to druhé plyne z definice).

Ještě k úloze č. 4:

Pokud se někomu (jako třeba mně) nechtělo vymýšlet s algoritmem, stačilo ukázat, že se dá úloha polynomiálně převést na Batoh(s, c, B) (s(a):=v(a), c(a):=v(a)) a že úloha má řešení právě tehdy, když Batoh vrátí předměty o ceně přesně B. Jelikož Batoh má složitost $O(nV \log_2(B+V))$ a jelikož $B\le V\le n^2$ , pak celá úloha má složitost $O(n^3 \log n)$ .

Betlista · Příspěvek od **Betlista** » 5. 2. 2010 20:09

jkt píše:K tomu rovnou reseni:

1) Rovnou z Riceovy vety (snad se ani nemuselo ukazovat, ze to neni trivialni trida funkci).

Jo, to říkal Kučera po zkoušce a stejně nevím jak. Bylo mi to jasné i na zkoušce, že tam bude něco na Rice'ovu větu a vycházelo to jedině na tohle, ale stejně - "ani obraz ani zvuk" :-/

jkt píše:3) Snadno, viz odhad, ze TS v case $n^i$ popise max. $n^i$ pasky, takze $\rarrow DSPACE(n^i) \subseteq DTIME(n^i)$ a zaroven $\exists i \in \mathbb{N}: \log_2 n \le n^i$ ;

Tak přesně tohle jsem napsal i já, ale nebylo to dobře, podle lemmatu 12.2 je to přesně naopak, tedy $DTIME(f(n)) \subseteq DSPACE(f(n))$

jkt píše:slo by ukazat i presneji pres odhad poctu konfiguraci: $\text{pocet konfiguraci} \le |Q| \times |\Sigma| \times \log_2 n$ , coz projdem nejhur v case $2^{c' \times \log_2 n}$ .

To bude asi lepší přístup

jkt píše: 4)
Kód: Vybrat vše
b := array [0..B] of Bool; // vyznam "uz jsme na vaze [index]"
b[0] := True;
b[zbytek] := false;

for a in A:
  for i := B to 0:
    if i + v(a) <= B && b[i]:
      b[ i + v(a)] := true;
  if b[B]:
    return Nalezeno;
return Nelze
To jiste probehne v O(nB), jiste -> je to v O(n^3). Je to korektni -- kazdou vec pouzijeme nejvys jednou, pokud dojdem na pozadovanou vahu, vrati OK, pokud nedojdem umre.

Wow, tak toto je geniálne a mňa to nenapadlo, potom som sa do toho zaplietol a už som to nedal...

jkt píše: 5) Po cca. hodinovem premysleni jsem to dokazal uplnost za tri minuty prevodem z HK (+diskuse, ze je to z NP) -- chci ukazat, ze v G=(V,E) je HK <=> G1, G2 maji izomorfni podgraf. Polozim tedy G1 = G, G2 = kruznice nad |V| vrcholy. Tecka .

Aké jednoduché

Fórum studentů MFF UK

Zkouska 2010-02-04

Zkouska 2010-02-04

Re: Zkouska 2010-02-04

Re: Zkouska 2010-02-04

Re: Zkouska 2010-02-04