Kuten aiemmin mainitsin, sain pari ropoa, joten lähden Oxfordiin syksyllä. Reissusta tulee tynkä, tosin nyttemmin avautui eräs toinen mahdollisuus, sillä isäntälaitos siellä päässä hakee vuoden pestiin post doc työntekijää, jonka karakterisointi on suunnilleen niinkuin minä, mutta enemmän nörtti. Mitä ikinä se sitten tarkoittaakin. Laitan kuitenkin hakemuksen vetämään.
Olen ottanut yhä enemmän etäisyyttä maallisiin asioihin, perhettä lukuunottamatta. Tämä on jokin ikäkausijuttu, lokeroita ei aivossa ole niin montaa, että niitä jaksaisi pitää erillään. On siis työ, abstraktiot ja perhe. Jälkimmäiseen lasken kaikenlaiset remonttihankkeet ja yleisen heeboilun puutarhassa, kun lapset leikkivät hiekkalaatikolla. Sillä rintamalla alkoi eilen kesäkausi, kun vanhemman pojan futistreenit lähtivät taas käyntiin. Todellinen yhteiskunta koostuu ihmisistä, siis lapsiaan jalkapallotreeneihin kuskaavista vanhemmista, grillaavista naapureista, lenkkikavereista, purjehdusseurojen aktiiveista jne.
Kompleksisuusteoriassa ns. Nick's Class koostuu päätöstehtävistä, jotka voidaan ratkaista polylogaritmisessa ajassa, kunhan käytettävissä on riittävästi rinnakkaisia prosessoreita. Esimerkiksi n-alkioisen taulukon järjestäminen kuluttaa aikaa O(n log n) [käytän tässä O() tarkkana rajana, koska en jaksa tunkea kreikkaa joka paikaan, tm. huom.] Jos meillä kuitenkin on riittävästi prosessoreita, voidaan taulukko järjestää ajassa O(log n).
Toinen mielenkiintoinen luokka on P-täydellisten päätöstehtävien luokka. DFS-numeroinnin oikeellisuus on yksi tämän luokan tehtävistä. Yleisesti uskotaan, että NC ei ole sama kuin P, joten P-täydellinen ongelma ei tämän uskomuksen mukaan rinnakkaistu kätevästi.
Koska etsin työkseni silmukoita graafeista, ja koska DFS-algoritmi on kanoninen silmukoiden etsimseen tarkoitettu algoritmi, olen joutunut miettimään tätä kysymystä. Tosin lähtökohtani ei ole ollut kysymys "NC = P?" vaan oikeastaan silmukan etsiminen ilman DFS-algoritmia. Keksinkin yhden algoritmin, jonka uskoin olevan n log n- aikainen - järjestämisen tapaan - mutta NC:ssä, eli rinnakkaistuva aina logaritmiseen asti.
Idea on tavattoman yksinkertainen: Meillä on kokoelma puita, {x1, ... , xn}. Kukin puu on rakenteeltaan sellainen, että kaaria seuraamalla pääsee juureen; samastamme tässä juurisolmun ja puun. Yksinkertaisuuden vuoksi oletamme, että puita on tarkalleen saman verran kuin käytössolevia prosessoreita, joten kukin prosessori käsittelee yhtä puuta.
Prosessi toimii siten, että puu kasvaa juurestaan "alaspäin". Tutkimme vielä tutkimatta
olevan juuresta lähtevän kaaren, jonka päässä on solmu:
1. Jos löydetty solmu on uusi, siitä tulee puun uusi juuri.
2. Jos solmu kuuluu johonkin puuhun, puut "kytketään". Kytkemisen jälkeen puita on yksi vähemmän, ja prosessi voi perustaa uuden puun valitsemalla jonkin tutkimattoman solmun. Kytkettäessä täytyy tarkistaa, onko löydetty solmu itseasiassa samassa puussa: jos se nimittäin on, niin olemme löytäneet silmukan. (Harjoitustehtävä 1: miksi se on silmukka?)
3. Jos solmu on vanha, eikä enää missään puussa, täytyy tutkia seuraava kaari.
Kun kaikki kaaret on tutkittu, juuri vanhenee. Vanhetessaan juuri poistetaan puusta. Tämän lisäksi täytyy jokainen tähän solmuun kytketty puu nyt erottaa omaksi puukseen.
Miksi tämä löytää silmukan: Oletetaan, että meillä on silmukka u1,...,uk (missä uk = u1). Koska jokainen solmu löydetään joskus, niin jokainen silmukan solmu on jossakin vaiheessa oman puunsa juuri. Tällöin esimerkiksi kaari u2->u3 tutkitaan jossakin vaiheessa. (voi toki olla, että tutkimme vaikka ensin kaaren u2-->u5, mutta tällöin löydämme lyhyemmän silmukan; voi myös olla, että löydämme u2 -> z1 -> ...->zx -> u3, mutta tällöin löydämme pidemmän silmukan) Näinollen seuraavasta solmusta tulee edellisen puun juuri, ja jossakin vaiheessa tutkimme kaaren, joka vie puusta siihen itseensä. (Tämä ei ole kunnollinen todistus, mutta algoritmi toimii kyllä)
Päällisin puolin rinnakkaistuminen näyttää selvältä. Ongelmaa ei myöskään tule lukkojen tms. kanssa, koska uuden solmun jyvittäminen ensiksi sen löytäneelle ei ole ongelma, siihen on toimiva protokolla. Ongelma tulee puiden kytkemisessä ja erottamisessa. Kytkeminen voidaan tehdä niin, että silmukat (so. samaan puuhun kuuluminen) voidaan todeta O(log n) ajassa - ja tasatusti jopa liki vakioajassa Erillisten joukkojen tietorakenteen avulla, mutta mainittu tietorakenne ei tue nopeaa erottelua.
Itseasiassa löysin patologisen tapauksen, jossa ainakin toinen, samaan puuhun kuulumisen tai erottelun aika, on O(n), kun puussa on n solmua, joten algoritmi ei toimi. Tai siis toimii, muttei ole tehokas.
3 kommenttia:
Täysin asian vierestä mutta tämä oli lähin blogi avautua.
Kerropa muuten minulle miksi Krugmanin tapainen Nobel-palkittu taloustieteilijä jaksaa selittää tämmöisiä:
Now, if Greece had its own currency, it could try to offset this contraction with an expansionary monetary policy — including a devaluation to gain export competitiveness. As long as it’s in the euro, however, Greece can do nothing to limit the macroeconomic costs of fiscal contraction.
http://krugman.blogs.nytimes.com/2010/05/01/why-devalue/
Vaikuttaa jotenkin käsittämättömältä, että tulonsiirto tuontiteollisuudelta vientiteollisuudelle on muka joku järkevä asia.
Kreikasta CATO ehti jo kirjoittamaankin:
http://www.cato.org/pub_display.php?pub_id=11736
Krugman on ns. devalvaatiohaukka, enkä ole kyllä samaa mieltä hänen kanssaan, mutta argumentti on silti pääosin täysin solidi.
Perusteena on se, että Kreikan tuotannollinen tehokkuus ei vastaa sen nominaalisia palkkoja ja nominaalista kulutusta, so. Kreikka elää velaksi. Työntekijät on vaikea saada hyväksymään palkkojen leikkauksia, ja nominaalipalkat mukautuvat epätasaisesti: kaikkein lakkoherkimmät ja ne, jotka ovat samalla kyvykkäimmät pistämään maan polvilleen, saavat jarrutettua nominaalista sopeutumista ja velkaantuminen jatkuu pidempään.
Jos Kreikka voisi devalvoida, sen suhteellinen palkkojen kustannusrakenne pysyisi (hetkellisesti) samana, mutta absoluuttiset vientiteollisuuden palkkakustannukset putoaisivat. Lisäksi tuonti - siis se, jonka vuoksi Kreikka viime kädessä kokonaisuutena velkaantuu - tyrehtyisi, kun ulkomaiset tuotteet kallistuisivat rajusti.
Vaikuttaa jotenkin käsittämättömältä, että tulonsiirto tuontiteollisuudelta vientiteollisuudelle on muka joku järkevä asia.
Devalvaatio on tällainen tulonsiirto vain pitkällä aikavälillä. Lyhyellä aikavälillä se muuttaa viennin ja tuonnin suhteellisia hintoja.
Itse en usko, että Kreikan ongelmat paranisivat jos sillä olisi oma valuutta, koska jos se olisi taloudellisesti riippumaton ja kykenevä päättämään omasta valuutastaan, valuutta olisi jo muuttunut täysin arvottomaksi. Tosin se ei olisi voinut ylläpitää kepulikonsteilla nykyisenkaltaista epätasapainoa, vaan valuutan arvon putoamisesta johtuva inflaatio olisi jyrännyt sen talouden sileäksi jo aiemmin.
Perusteena on se, että Kreikan tuotannollinen tehokkuus ei vastaa sen nominaalisia palkkoja ja nominaalista kulutusta, so. Kreikka elää velaksi. Työntekijät on vaikea saada hyväksymään palkkojen leikkauksia, ja nominaalipalkat mukautuvat epätasaisesti: kaikkein lakkoherkimmät ja ne, jotka ovat samalla kyvykkäimmät pistämään maan polvilleen, saavat jarrutettua nominaalista sopeutumista ja velkaantuminen jatkuu pidempään.
Kreikkalaisten pitäisi ymmärtää toimia pitkän aikavälin kansallisen edun mukaisesti. Muuten voi seurata sekasorto ja valtaan nousee taas jokin everstijuntta. Välimeren (Ranskaa lukuun ottamatta) maiden ottaminen valuuttaunioinin jäseniksi oli mielestäni iso virhe.
Lähetä kommentti