od mathemage » 29. 6. 2011 17:54
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"
Tak dneska se vymyslilo nasledujici zadani:
[quote]
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).
[/quote]
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