zkouška 31.1. - Hric

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.

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 :)

Pls popsal byste nekdo jak najit ten inverzni prvek k 5 v Z13 pomoci rozsireneho eukleidova algoritmu?

Dik

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 :)

Diky moc!

Takhle je to intuitivnější http://www.karlin.mff.cuni.cz/~zemlicka ... algi_1.htm .. druhá část 1. příkladu

hippies wrote:Takhle je to intuitivnější http://www.karlin.mff.cuni.cz/~zemlicka ... 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! :)