# Zkouska 2010-02-04

<{ForumPost(poster="jkt", timestamp=2010-02-04 18:30:50)}>
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").
<{/ForumPost}>

<{ForumPost(poster="jkt", timestamp=2010-02-04 18:43:33)}>
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 $$\rightarrow 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)   

    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.
<{/ForumPost}>

<{ForumPost(poster="lukas.hermann", timestamp=2010-02-05 12:23:27)}>
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)$$.
<{/ForumPost}>

<{ForumPost(poster="Betlista", timestamp=2010-02-05 20:09:31)}>

 > jkt wrote: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 wrote:3) Snadno, viz odhad, ze TS v case $$n^i$$ popise max. $$n^i$$ pasky, takze $$\rightarrow 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 wrote: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 wrote:
 > 4)   
 > 
 > 
 > 
 > 
 > 
 >     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.

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

 > jkt wrote:
 > 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é ;-)
<{/ForumPost}>