zkouška 31.1. - Hric

Uživatelský avatar
cathack
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 31. 1. 2006 14:18
Typ studia: Informatika Bc.

zkouška 31.1. - Hric

Příspěvek od cathack »

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.
Návštěvník

Příspěvek od Návštěvník »

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 :)
melda3
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 29. 1. 2007 17:39

Příspěvek od melda3 »

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

Dik
Petaa

Z13

Příspěvek od Petaa »

melda3 píše: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. ;)

Kód: Vybrat vše

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 :)
melda3
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 29. 1. 2007 17:39

Příspěvek od melda3 »

Diky moc!
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

Takhle je to intuitivnější http://www.karlin.mff.cuni.cz/~zemlicka ... algi_1.htm .. druhá část 1. příkladu
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 162
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

Příspěvek od Myshaak »

hippies píše: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! :)
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Odpovědět

Zpět na „2006“