Zkouska Mares 29.6.2011

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Zkouska Mares 29.6.2011

Příspěvek od mathemage »

Tak dneska se vymyslilo nasledujici zadani:
A1. Jarníkův algoritmus a řezové lemma.
A2. Třídění n čísel z množiny {1, …, n^4}.
B1. Byla jednou jedna směnárna, která obchodovala s N měnami podle matice kursů K (Ki,j říká, kolik jednotek měny j získáme za jednotku měny i). Lze na směňování vydělat? (Tedy lze začít s jednotkou nějaké měny a skončit s větším částkou v téže měně?)
B2. Jak setřídit posloupnost, víme-li, že každý prvek se nachází ve vzdálenosti nejvýše K od své správné polohy? (K je mnohem menší než počet prvků.)
C. Najděte dvě funkce f, g takové, že neplatí ani f=O(g), ani g=O(f).
A1. Klasika - viz skripta. U rezoveho lemma mozna stoji za zminku, zda-li nejlehci hrana rezu patri do vsech minimalnich koster nebo jen nejake dotycne. Odpovedel jsem, ze by melo patri do vsech minimalnich koster, pac v dukazu nam jde jen o soucet vah hran kostry, ktery je takto stejny (i kdyz diky Jarnik. alg. se dokaze, ze existuje jen 1 minimalni kostra, to vsak v dane fazi dukazu jeste nejde pouzit)
A2. RadixSort, ciselny zaklad o zakladu n. Cas i pamet v O(N).
B1. Prevede se na grafovy problem - potrebuji najit cyklus, jehoz soucin hran je > 1. Ekvivalentne: součet opačných hodnot logaritmů vah hran je < 0. Zaporne cykly v grafu s takto upravenymi hranami lze nalezt pomoci treba Bellman-Fordova algoritmu (pusti se na konci jeste jednou, pokud se nekde zmenilo ohodnoceni, je pritomen zaporny cyklus). Vse v case O(n.m), v pameti O(n+m), vzhledem k tomu, ze zmineny graf je uplnak, vyjde to O(n^3) a O(n^2).
B2. Nevim, jestli se mi na todle koukl, mozna, ze uz mi to predtim stacilo, ale prejel to asi behem 1,5 vteriny a dal mi rovnou znamku. Bud pres vyvazeny BVS ci (coz da asi min prace) haldu si pamatuji vzdy poslednich K hodnot a vzdy davam ExtractMin a Insert dalsiho prvku ze vstupu. Casove to vyjde O(N log K), pametove O(N+K), coz je vzhledem ke K << N v podstate linearni :)
C. Nedelal jsem, ale jednou jsem se s tim setkal snad na cvikach z Kombagry I - je to neco, co je neco neporovnatelny, ale jejich logaritmy uz porovnatelny jsou. Snad jsem vas tim vic nezmatl, ale ted si opravdu nevzpomenu :(

Dostal jsem jednicku, byla to snad nejrychlejsi zkouska od zacatku roku, po asi 100 minutach si ke mne sedl, asi 2 a pul minuty to cetl a diskutoval se mnou a pak mi znenadani zcistajasna:) dal za jedna. MJ je jako zkousejici nakonec hodne v pohode, sice priklady nejsou zrovna trivialni na vymysleni, ale jsem rad, ze i na matfyzu se delaj takovyhle zkouskovy "rychlovky" :D
Carpe Diem!
PetrK
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 7. 2. 2011 22:41
Typ studia: Informatika Bc.

Re: Zkouska Mares 29.6.2011

Příspěvek od PetrK »

mathemage píše:Tak dneska se vymyslilo nasledujici zadani:
C. Najděte dvě funkce f, g takové, že neplatí ani f=O(g), ani g=O(f).
f(x) = x
g(x) = 1 pro licha, x^2 pro suda

treba tahle by na to mohla sedet
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“