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.
zkouška 31.1. - Hric
Z13
Pojedes presne podle toho algoritmu, jak ma Hric v tom pdfku na svych strankach.melda3 píše:Pls popsal byste nekdo jak najit ten inverzni prvek k 5 v Z13 pomoci rozsireneho eukleidova algoritmu?
Dik
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
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
Takhle je to intuitivnější http://www.karlin.mff.cuni.cz/~zemlicka ... algi_1.htm .. druhá část 1. příkladu
- Myshaak
- Matfyz(ák|ačka) level III
- Příspěvky: 162
- Registrován: 18. 1. 2006 22:29
- Typ studia: Informatika Mgr.
- Login do SIS: michp5am
No mne osobne prijde rekursivni varianta "viditelnejsi" nez iterativni...hippies píše:Takhle je to intuitivnější http://www.karlin.mff.cuni.cz/~zemlicka ... algi_1.htm .. druhá část 1. příkladu
...ale kazdemu sedne neco jineho, toz dobre je je to tu oboje. Tak! :)
"Go for the eyes Boo, go for the eyes! Yeahh!!"