# zkouška 31.1. - Hric

<{ForumPost(poster="cathack", timestamp=2007-01-31 10:51:15)}>
1) Indukcí podle m dokažte, že pro velikost sluč. sítě Mm šířky 2m konstruované metodou sudá-lichá platí:  
s(Mm) = m log m + 1  
  
2) Popište efektivní algoritmus hledání toku ve vrstvené síti. Odhadněte složitost a zdůvodněte.  
  
3) Pomocí rozšířeného Euklidova algoritmu najděte mult. inverzní prvek k 5 v Z13 (i s mezivýsledky algoritmu).  
  
4) Dokažte, že problém vrcholového pokrytí je NP-úplný pomocí problému kliky a nějakých převodů... nebo tak něco. Už nepamatuji.
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2007-01-31 18:50:44)}>
pozor, nestaci na druhou otazku jen popsat DINIC.  
  
dulezity je tam dukaz, proc ma slozitost F(N,M) a proc se muzou poskrtavat hrany, ktere DINIC poskrta :)
<{/ForumPost}>

<{ForumPost(poster="melda3", timestamp=2007-02-07 16:04:14)}>
Pls popsal byste nekdo jak najit ten inverzni prvek k 5 v Z13 pomoci rozsireneho eukleidova algoritmu?  
  
Dik
<{/ForumPost}>

<{ForumPost(poster="Petaa", timestamp=2007-02-07 17:28:34)}>

 > melda3 wrote:Pls popsal byste nekdo jak najit ten inverzni prvek k 5 v Z13 pomoci rozsireneho eukleidova algoritmu?  
 >   
 > Dik

Pojedes presne podle toho algoritmu, jak ma Hric v tom pdfku na svych strankach. ;)  

    volani RozE(13,5)
      
      - vola se RozE(5,3)
    
      -  - vola se RozE(3,2)
    
      -  -  - vola se RozE(2,1)
    
      -  -  -  - vola se RozE(1,0)
    
      -  -  -  -  -  *konec rekurze, 2. parametr=0*
      -  -  -  -  -  vrati se (1,1,0)
    
      -  -  -  - (d',x',y') = (1,1,0)
      -  -  -  - y = 1 - (2 div 1) * 0 = 1
      -  -  -  - vrati se (d,x,y) = (1,0,1)
    
      -  -  - (d',x',y') = (1,0,1)
      -  -  - y = 0 - (3 div 2) * 1 = -1         // mohlo by se prevest na 12, ale takhle se to lip pocita
      -  -  - vrati se (d,x,y) = (1,1,-1)
    
      -  - (d',x',y') = (1,1,-1)
      -  - y = 1 - (5 div 3) * (-1) = 2
      -  - vrati se (d,x,y) = (1,-1,2)
    
      - (d',x',y') = (1,-1,2)
      - y = -1 - (13 div 5)*2 = -5
      - vrati se (d,x,y) = (1,2,-5)
    
    - to d a x nas nezajima, dulezity je ten y - a protoze jsem v telese Z13, tak tu minus petku prevedu na kladny cislo:  -5 --> 8
    

takze inverzni prvek k 5 v Z13 je 8 :)
<{/ForumPost}>

<{ForumPost(poster="melda3", timestamp=2007-02-07 18:03:47)}>
Diky moc!
<{/ForumPost}>

<{ForumPost(poster="hippies", timestamp=2007-02-07 22:00:23)}>
Takhle je to intuitivnější [http://www.karlin.mff.cuni.cz/~zemlicka ... algi_1.htm](http://www.karlin.mff.cuni.cz/~zemlicka/cvic4-5/algi_1.htm) .. druhá  část 1. příkladu
<{/ForumPost}>

<{ForumPost(poster="Myshaak", timestamp=2007-02-08 20:55:46)}>

 > hippies wrote:Takhle je to intuitivnější [http://www.karlin.mff.cuni.cz/~zemlicka ... algi_1.htm](http://www.karlin.mff.cuni.cz/~zemlicka/cvic4-5/algi_1.htm) .. druhá  část 1. příkladu

No mne osobne prijde rekursivni varianta "viditelnejsi" nez iterativni...  
...ale kazdemu sedne neco jineho, toz dobre je je to tu oboje. Tak! :)
<{/ForumPost}>