Zkouska 15.6.

Tak tedy, dnes bylo na zkousce zadani nasledujici:
Mejme souvisly neorientovany graf. Plati, ze mnozina lehkych hran pres vsechny rezy tvori kostru grafu? Odpoved je obecne NE.

Triatlonovy graf je takovy, jehoz kazda hrana reprezentuje usek trati absolvovatelne na kole, bezmo nebo plavmo. Mejme startovni vrchol x a v case theta(n+m) zjisteme vsechny mista, kam se jde dostat z vrcholu x pomoci nula a vice plavani, dale nula a vice jezdeni na kole a dale nula a vice bezeni. Hrany mohou byt i kombinovane (jakakoliv kombinace je OK), jedine co se nesmi je zprehazet poradi plavby, kola a behani. Reseni jednoduse pomoci BFS.

A prvni priklad byl nejaky algoritmus na nalezeni k-teho prvku z n a to jinou metodou nez Blum et al, ale velmi podobnou. Bylo za ukol zjistit T(n), po mensi analyze problemu to slo lehce prevest na MT.

Kolem a kolem byla pisemka tak stredni s tim, ze priklad s triatlonem byl za deset minut hotovy, priklad s cisly za trosku dele a dukaz / vyvraceni toho grafu bylo na delsi dobu.

Hladanie k teho prvku...:
a) vyber pivot z n prvkov (pravdepodobnost vyberu kazdeho je 1/n)
b) rozdel prvky podla pivota na mnozinu A mensich nez pivot a B vacsich nez pivot, (|A|+|B| + 1 =n), ak je pivot hladany prvok(|A| + 1 = k), tak konci
c) aj A a B maju najviac c.n prvkov, tak hladaj rekurzivne v tej, kde je pivot, ak jeden z A alebo B ma viac nez c.n prvkov, tak vyber ineho pivota a zacni od a)

..bola zadana funkcia: T(n)=Theta(n).S(n) + T(c.n), kde S(n) je zlozitost pre najdenie spravneho pivota

ULOHA: vypocitat asymptoticke zlozitosti T(n) a S(n) pre c=1/2 a c=3/4

...no mne sa tato pisomka rozhodne lahka, alebo 'lahsia' vobec nezdala :(

Hmmmm, muzete nekdo upresnit, jak by mela vypadat ona S(n)? Je mi jasny, ze by to tak nejak melo byt 3/2, resp. 2-1/n, ale jak konkretne.... Diky

Tuhle písemku jsme měli dneska, takže je stále aktuální ;)

Ten první příklad se řeší vždycky pro průměrný případ, protože v nejhorším případě to ani nemusí doběhnout.

Pro to první zadání, kde c = 1/2, tak z těch prvků jako pivot vyhovuje jenom jeden nebo dva prvky. To znamená, že v průměru je potřeba vyzkoušet n/2 (nebo n/4) náhodných výběrů, takže S(n) patří do Theta(n).

Takže pak T(n) = Theta(n^2) + T(n/2) a podle MT: T(n) patří do Theta(n^2).

Pro c = 3/4 ti jako pivot vyhovuje cokoliv, co je větší než n/4 nejmenších prvků a menší než n/4 největších prvků, takže šance, že bude náhodně vybranej pivot vyhovovat, je zhruba 1:1. Takže S(n) patří do Theta(1), což když se dosadí, tak:

T(n) = Theta(n) + T(3n/4) a to dává podle MT: T(n) patří do Theta(n).