Erilaisia logaritmeja esiintyy yllättävän usein kompleksisuuksien yhteydessä. Oikeastaan en ole informaatioteorian ja kompleksisuuden (ja algoritmien analyysin) ulkopuolella joutunut pahemmin logaritmia koskaan käyttämään. Klassisissa insinööritieteissä sillä on oma roolinsa, tietysti, mutta ainakaan heti ei tule mieleen esimerkiksi yhtään mekaniikan ongelmaa, jossa logaritmi nousisi esiin. (Varmaan sellaisia on, ja arvostan kommenteissa esimerkkejä)
Tyypillinen tilanne, jossa logaritmi esiintyy on mikä tahansa sellainen poissulkumenetelmä, jossa onnistuneesti voidaan eliminoida jokin osuus &alpha kokonaisuudesta pois (tämän osuuden pitää olla alhaalta rajattu jollakin vakiolla) Klassinen esimerkki on puolitushaku. Samasta syystä myös erilaiset tasapainotettujen binääripuiden operaatiot ovat tyypillisesti logaritmisia.
Logaritmi esiintyy myös usein silloin, kun meillä on jokin hierarkia, jossa operoimme. Esimerkiksi voimme ajatella rekursiivisen algoritmin, joka pilkkoo ongelman tasaisesti pienempiin osiin, kuten vaikka Merge-sort. Timsortin yksityiskohtiin en vielä ole tutustunut, se on käsittääkseni pythonin "listojen" järjestämiseen käyttämä algoritmi.
Logaritminen suoritusaika tuottaa mielenkiintoisen ilmiön, joka voidaan palauttaa logaritmien algebraan, ja tulon logaritmiin, log(xy) = log x + log y. Esimerkiksi binäärihakupuun koon kymmenkertaistaminen lisää hakuoperaation suoritusaikaa muutamalla askeleella. Nykyaikaiset tietokoneet ovat niin käsittämättömän nopeita, että käytännössä logaritminen operaatio on aina yksinään hurjan nopea.
Tämä ei tietystikään tarkoita, etteikö logaritmisella kertoimella olisi väliä. Kyllä sillä usein on. Ensiksikin, esiintyessään sen kyljessä on usein melko suuri vakiokerroin - joka analyysissä jätetään huomiotta. Toiseksi, logaritmisuus tulee esiin yleensä kun yksittäinen operaatio suoritetaan useampaan kertaan. Esimerkiksi, jos hakupuusta haetaan miljoonia alkioita, alkaa logaritminen kerroin olla jo olennainen: kaksikantainen logaritmi miljoonasta on noin 20, ja jos haku tapahtuu vaikkapa klassiselta pyörivältä kovalevyltä, hakuun liittyy vielä korkeahkoja vakioita. Miljoona - tai jopa 100 miljoonaa - yksinkertaista laskennallista operaatiota toki tapahtuu nykyisillä koneilla kirjaimellisesti silmänräpäyksessä.
Logaritmi on tosiasiallisesti mukana infomraatioteoreettisista syistä kaikessa mitä tietokoneella voi tehdä. Esimerkiksi muistin osoittamiseksi tarvitaan aina logaritminen määrä bittejä. Jos haluamme tallentaa taulukkoon n erisuuruista alkiota, jo näiden alkioiden identifioiminen vaatii logaritmisen määrän bittejä jokaista alkiota kohden. Jos tarkkuudesta voidaan tinkiä, niin on olemassa tekniikoita, joilla logaritminen määrä voidaan kiertää yleisessä tapauksessa. Ja tietysti, jos alkioiden määrä ja esitys tiedetään tarkalleen (so. esitystavan mahdollistama joukko on (suunnilleen) sama kuin todella esiintyvä joukko), niin voidaan vain varata yksi bitti jokaiselle alkiolle. Yleisessä tapauksessa tämä ei ole mahdollista, koska esitystapa sallii usein mielipuolisen suuria joukkoja: esimerkiksi, jos oletamme, että jokaisella ihmisellä on uniikki nimi, joka koostuu 20 merkistä normaaleja aakkosia (29 aakkosta), niin syntaktisesti mahdollisia nimiä on 2920, joka on suuruusluokkaa 1029. Ihmisiä on maapallolla luokkaa 1010.
7 kommenttia:
Aina kun joudutaan integroimaan 1/x tarvitaan logaritmeja tai jos integroidaan funktio muotoa u(x)`/u(x).
Logaritmit antavat myös selvästi isomorfismin ryhmien (R_*,x) ja (R,+) välille.
Analyytikolle logaritmin tärkein omainaisuus on että se on eksponenttifunktion käänteisfunktio. Eksponenttifunktio on taas valtavan tärkeä koska se on derivaattaoperaattorin ainoa ominaisfunktio (modulo vakiot)
Vielä kaksi juttua, kun luku kasvaa niin luulisin, että sen n-kantainen esitys kasvaa kuin n kantainen logaritmi. Ja vielä luulisin että harmoninen sarja ~ ln(n). (Tämän jälkimmäisen voisi ehkä päätellä tuosta integraalistakin, mutta ei jaksa ajatella, tänään.)
Siitä mekaniikan esimerkistä. Näin akkiseltään ajateltuna sen saa kun vain ajattelee että joku tekee työtä esimerkiksi välillä [1,10] vakiosuuntaista voimaa vastaan jonka voimakkuus on 1/x pisteessä x ja laskee kulutetun energian. Insinööritieteistä löytyy varmaan paljon luonnollisempia esimerkkejä.
Jatkoa edelliseen, ajatellaan että kappale A tulee välille [1,10] vasemmalta alkunopeudella v ja kohtaa v:tä vastakkaisuuntaisen voiman jonka voimakkuus (ottaen A:n massa huomioon) on 1/x. Pitääkseen vauhtinsa samana A:n täytyy kumota tuo voima eli A käyttää energiaa välillä [0,1] integral[1,10] 1/x dx = ln(10) - ln(1) = ln(10) yksikköä.
No huonostippa on maailmaa katsellut, jos ei logaritmiin ole törmännyt :-)
Ihminenhän hahmottaa lähtökostaisesti maailman logaritmien läpi. Klassinen esimerkkihän on äänen desibeliasteikko, mutta sama ilmiö toimii myös muissa aisteissa (tosin niissä havaintoalueen dynamiikka on yleensä merkittävästi pienempi, joten tuo ei nouse samalla tavoin esiin).
Nähdäkseni ihminen hahmottaa myös muut ilmiöt logaritmisesti: esimerkiksi 5 vuotta on ajallisesti paljon pidempi aika 10 vuotiaalle kuin 30 vuotiaalle. Ja sehän nyt on jo klassikko, etteivät poliitikot tiedä, montako nollaa on miljoonassa...
Tällä on seurauksia myös esimerkiksi taloustieteisiin. Otetaan nyt vaikka väestönkasvu tai markkinapenetraatio (http://en.wikipedia.org/wiki/Logistic_function) tai valintatilanteet (http://en.wikipedia.org/wiki/Logit).
Ja sitten on tietenkin tämä sähkömagnetiikka, jossa ei paljon muun kanssa puljatakaan kuin logaritmien (tai eksponenttien) kanssa...
Tarkoitin yllä sitä, että en ole koskaan klubiaskin kanteen laskelmia tehdessäni törmännyt logaritmiin missään muualla kuin kompleksisuuslaskelmissa.
Tietysti tiedän, että se esiintyy vaikka missä teorioissa. Ja siis, olen lukenut tilastomatematiikkaa sen verran, että toki logaritmit ovat tuttuja sieltä puolelta, samoin kuin taloustieteestä. Esimerkiksi jos estimoidaan Cobb-douglas-funktion parametreja, niin se tehdään ottamalla datasta ensin logaritmit.
(Mekaniikasta en kyllä ihan hahmota missä tilanteessa voima on muotoa 1/x, jos sitä ei suoraan näin postuloida.)
Missään nimessä en väittänyt, että logaritmia ei esiintyisi tai ettei siihen törmäisi, ainoastaan, että se tulee aivan elementaarisista ongelmista heti pintaan lähinnä kompleksisuuksissa, jossa se on aivan keskiössä. Puolitushaku ja sorttaus ovat tyyliin ensimmäisiä algoritmeja, joita opiskelijoille opetetaan.
"Tarkoitin yllä sitä, että en ole koskaan klubiaskin kanteen laskelmia tehdessäni törmännyt logaritmiin missään muualla kuin kompleksisuuslaskelmissa."
Jaa, no aika monessa insinööritieteessä tuota itseasiassa käytetään aika "klubiaskin" kanteen tyylisissä arvioissa epäsuorasti: luetaan/piirretään käppyröitä logaritmisille papereille - ainakin akustiikkasuunnittelussa ja sähköpiirien suunnittelussa tuo on ihan peruskauraa (tyyliin ensimmäisiä asioita, joita insseille opetetaan). Mutta kuten joku täällä totesikin lähinnä se useimmiten tulkitaan (luonnollisen-) logaritmin käänteisfunktiona, eikä asiaan sen kummemmin kiinnitetä huomiota.
Mutta joo, eipä minullekaan tule mieleen, että luokkaa "lukiossa opetettavat luonnontieteet" -tasoisissa ongelmissa noita olisi juurikaan (paitsi matematiikassa, tietenkin).
Lähetä kommentti