Pisemka 7.7. 2005

Kaja Marik

Pisemka 7.7. 2005

Příspěvek od Kaja Marik »

Opet 3 priklady, citelnost dobra.

1) Odhadnete slozitost a dukaz provedte substitucni metodou

T(n)=2* T(2/3*n) +T(n/3) + 8

2) Vymyslete algoritmus, ktery v case O(n) najde K prvku nejblize medianu. Na vstupu dostanete tedy mnozinu cisel a cislo K, kde K<N. Jo a v tej mnozine nenajdete 2 stejny prvky.

3) Tak ten uz si nepomatuju, ale zacinalo to Dokazte nebo vyvratte a jednalo se o tvrzeni s lehkyma hranama. Dyztak at me nekdo s lepsi pameti doplni.


Hodne stesti.
Mirek

písemka

Příspěvek od Mirek »

já si to pamatuju takto:
3) Dokažte nebo vyvraťte že to, že všechny řezy v grafu mají právě jednu lehkou hranu, je postačující,ale nikoliv nutná podmínka k tomu,aby graf měl právě jednu minimální kostru
Odpovědět

Zpět na „2004“