Algoritme

Nej tak, vi har alle de algoritmer, vi kan spise!

— Albert Einstein om sin reaktion på et besøg af Jehovas Vidner ^[1]

**Algoritmen** her over viser os, hvordan det lykkedes for den kedelige matematik professor *John Ogden Nash* at komme i lag med Jennifer Connelly ^[2]

En algoritme beskriver, hvordan alle ting og mennesker træffer beslutninger. Fx befinder du dig på Kakadu Bar og er blevet godt vissen, da resterne af dit periferale udsyn svagt registrerer to mulige dameobjekter ved baren. Din berusede hjerne går alligevel - på trods af din tilstand og helt af egen drift - i gang med en separations-algoritme: Bryster, tjek. Talje, tjek. Røv, tjek. Lange ben, tjek osv.
I løbet af få sekunder vil din intok sikerede bevidsthed - ud fra tusinder af forpro grammerede parametre - være i stand til at udvælge, hvilken af damerne, du skal gå efter. Se, dét er en algoritmisk funktion!

Køretid

Beregningskompleksiteten af en algoritme beskriver, hvor lang tid det teoretisk vil tage at løse et problem af en given størrelse. Man taler om, at en algoritme kører i tid $O(n2)$ for at løse et problem i størrelsen $n$ . Det vil her sige, at køretiden af algoritmen vil være kvadratisk afhængig af de ind daterede datas størrelse.^[3]
Sorteringsalgoritmen er noget mere avanceret og vil køre i $O(n*lg(n))$ tid. Når tiden så er udløbet, siger algoritmen "ping!", så du véd, at den er færdig.^[4]

Kvantogoritmer

I kvantecomputere bor der såkaldt qubits,^[5] og derfor skal man også bruge en slags algoritmer til dem. Men i stedet for at kalde dem for kvantemekaniske algoritmer, så enedes forskerne om det mere mundrette kvantetogoritmer (eller blot kvitmer ^[6]). Den første algoritme til for målet blev udtænkt af Peter Schohr, og den kaldes af samme grund for Schohrs Algoritme.^[7] Den handler i al sin enkelhed om at finde ud af, hvilke to primtal, der skal multipliceres, for at finde et givent tal, fx N.^[8]

Hvem bruger algoritmer?

Polynominel tid og primtalsopløsningsproblemet i noteform

↑ De ville have ham til at ab onnere på UFO-Nyt
↑ (hvis du prøver at kigge op under Jennifers skørter i over fem minutter, vil din hjerne blive for vand let til chokolademousse)
↑ = flere tal: længere regntid
↑ Herefter åbner du lågen og tager algoritmen ud. Lad den køle af et par minutter på et fr ost frit under lag
↑ svarer til de gammeldags bits, bare med et par ekstra bogstaver
↑ hvis det skal være rigtig løssluppent
↑ For at indregne et heltal N, kører Schohrs algoritme i polyn omiel tid (den forløbne tid er polynomial i log N, hvilket samtidig er den givne størrelse af in puttet).
Kvantegates af størrelsen $O((logN)2(loglogN)$ (log log log N)) bruger en hurtig multiplikation, der viser, at primtal sopløsnings problemet kan løses, og dermed befinder algoritmen sig i kompleksitetets klassen CPQ. Dette er en milliard gange hur tigere end den mest effektive klassisk-fakto rise rende algoritme, den gener el le tal-felt-si, som jo arbejder i sub-eksponentiel tid, som det ses her: $O(e1.9(logN)1/3(loglogN)2/3)$ . Effektiviteten af Schohrs algoritme skyldes kvante-Fouriertransf ormat ionen, samt modulær eksponentialitation ved de mange og hyppigt gentagne divisioner, som man kan få lov at lave på en kvantecomputer
↑ hvilket jo er ganske let, da N er et bog stav, Mission completed! ^[9]
↑ Når jeg ellers ikke er alt for be ruset, eller af en eller anden grund har for meget spyt i munden, så bruger jeg også udtrykket "mission accomplished", når jeg med succes skal forklare for skellen på bogstaver og binære tal

[1] De ville have ham til at ab onnere på UFO-Nyt

[2] (hvis du prøver at kigge op under Jennifers skørter i over fem minutter, vil din hjerne blive for vand let til chokolademousse)

[3] = flere tal: længere regntid

[4] Herefter åbner du lågen og tager algoritmen ud. Lad den køle af et par minutter på et fr ost frit under lag

[5] svarer til de gammeldags bits, bare med et par ekstra bogstaver

[6] vis det skal være rigtig løssluppent

[7] For at indregne et heltal N, kører Schohrs algoritme i polyn omiel tid (den forløbne tid er polynomial i log N, hvilket samtidig er den givne størrelse af in puttet).
Kvantegates af størrelsen $O((logN)2(loglogN)$ (log log log N)) bruger en hurtig multiplikation, der viser, at primtal sopløsnings problemet kan løses, og dermed befinder algoritmen sig i kompleksitetets klassen CPQ. Dette er en milliard gange hur tigere end den mest effektive klassisk-fakto rise rende algoritme, den gener el le tal-felt-si, som jo arbejder i sub-eksponentiel tid, som det ses her: $O(e1.9(logN)1/3(loglogN)2/3)$ . Effektiviteten af Schohrs algoritme skyldes kvante-Fouriertransf ormat ionen, samt modulær eksponentialitation ved de mange og hyppigt gentagne divisioner, som man kan få lov at lave på en kvantecomputer

[8] vilket jo er ganske let, da N er et bog stav, Mission completed! ^[9]

[9] Når jeg ellers ikke er alt for be ruset, eller af en eller anden grund har for meget spyt i munden, så bruger jeg også udtrykket "mission accomplished", når jeg med succes skal forklare for skellen på bogstaver og binære tal

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Spademanns Leksikon

Algoritme

Indholdsfortegnelse