|
|
Linje 1: |
Linje 1: |
| {{citat|Nej tak, vi har [[alle]] de algoritmer, vi kan spise!|Albert Einstein|sin reaktion på et besøg af [[Jehovas Vidner]]}}<br /> | | {{citat|Nej tak, vi har [[alle]] de '''algoritmer''', vi kan spise!|Albert Einstein|sin reaktion på et besøg af [[Jehovas Vidner]]}}<br /> |
|
| |
|
| [[Fil:Tumblr mqpq4kt2DA1qfmbszo1 500.gif|thumb|500px|right|'''Algoritmen''' [[her]][[over]] [[vis]]er [[os]], hvordan det lykkedes for ''John Ogden Nash'' at [[komme]] i lag med [[Hende den lækre fra parallelklassen|Jennifer]] [[Marilyn Monroe|Con]]nelly (<small>hvis du prøver at kigge [[op]] [[under]] [[Celine Dion|Jennifers]] [[Trusser|skørter]] i over fem minutter, vil din [[hjerne]] blive forvandlet til [[chokolade]]mousse</small>)]] | | [[Fil:Tumblr mqpq4kt2DA1qfmbszo1 500.gif|thumb|555px|right|'''Algoritmen''' [[her]][[over]] [[vis]]er [[os]], hvordan det [[lykke]]des [[for]] [[den]] [[kedelig]]e [[matematik]][[professor]] ''John Ogden Nash'' at [[komme]] i [[lag]] med [[Hende den lækre fra parallelklassen|Jennifer]] [[Marilyn Monroe|Con]]nelly <ref>(<small>hvis du prøver at kigge [[op]] [[under]] [[Celine Dion|Jennifers]] [[Trusser|skørter]] i ''over'' fem minutter, vil din [[hjerne]] blive [[for]][[vand]][[let]] [[til]] [[chokolade]]mousse</small>)</ref>]] |
|
| |
|
| En '''algoritme''' beskriver, hvordan [[alle]] [[ting]] og [[menneske]]r træffer beslutninger. Fx befinder du [[dig]] på ''[[Eiffel Bar|Kakadu Bar]]'' og er godt [[Visitationszone|vissen]], da resterne af dit periferale [[ud]]syn [[op]]dager to [[dame]]r ved [[Barbie|baren]]. Din berusede [[hjerne]] går alligevel - [[helt]] af [[eg]]en drift - i gang med en ''separations-algoritme'': [[Patter|Bryster]], tjek. [[Tal]]je, tjek. [[Røv]], tjek. [[Lang]]e [[ben]], tjek osv.<br />I løbet af få [[sekund]]er vil din [[in]]tok[[si]]kerede [[bevidsthed]] - ud fra [[tusind]]er af forprogrammerede [[Paradigme|parametre]] - være i stand til at udvælge, hvilken af [[damer]]ne, du skal gå efter. Se, dét er en ''algoritmisk'' funktion! | | En '''algoritme''' beskriver, hvordan [[alle]] [[ting]] og [[menneske]]r træffer beslutninger. Fx befinder du [[dig]] på ''[[Eiffel Bar|Kakadu Bar]]'' og er blevet godt [[Visitationszone|vissen]], da resterne af dit [[Krog|perifer]]ale [[ud]]syn svagt registrerer to mulige [[dame]]objekter ved [[Barbie|baren]]. Din berusede [[hjerne]] går alligevel - på trods af din tilstand og [[helt]] af [[eg]]en [[Liderlig|drift]] - i gang med en ''separations-algoritme'': [[Patter|Bryster]], tjek. [[Tal]]je, tjek. [[Røv]], tjek. [[Lang]]e [[ben]], tjek osv.<br />I løbet af få [[sekund]]er vil din [[in]]tok[[si]]kerede [[bevidsthed]] - ud fra [[tusind]]er [[af]] [[for]]pro[[gram]]merede [[Paradigme|parametre]] - være i stand til at udvælge, hvilken af [[damer]]ne, du skal gå efter. Se, dét er en ''algoritmisk'' funktion! |
| ==Køretid== | | ==Køretid== |
| Beregningskompleksiteten af en ''algoritme'' beskriver, hvor [[lang]] [[tid]] det [[Teori|teoretisk]] vil [[tag]]e at løse et [[problem]] af en given [[stør]]relse. Man taler om, at en ''algoritme'' kører i tid ''<math>O(n2)</math>'' for at løse et problem i [[stør]]relsen ''<math>n</math>''. Det vil [[her]] sige, at køretiden af ''algoritmen'' vil være [[Kvadratrod|kvadratisk afhængig]] af de [[in]]d[[da]]terede [[da]]tas [[stør]]relse. ''[[Sort]]eringsalgoritmen'' er [[noget]] mere avanceret og vil køre i ''<math>O(n * lg(n))</math>'' tid. Når [[tid]]en er udløbet, siger ''algoritmen'' "[[pi]]ng!", så du véd, at den er færdig. | | [[Svær|Beregningskompleksiteten]] af en ''algoritme'' beskriver, hvor [[lang]] [[tid]] det [[Teori|teoretisk]] vil [[tag]]e at løse et [[problem]] af en given [[stør]]relse. Man taler om, at en ''algoritme'' kører i tid ''<math>O(n2)</math>'' for at løse et problem i [[stør]]relsen ''<math>n</math>''. Det vil [[her]] sige, at køretiden af ''algoritmen'' vil være [[Kvadratrod|kvadratisk afhængig]] af de [[in]]d[[da]]terede [[da]]tas [[stør]]relse.<ref>= flere [[tal]]: længere [[regn]]tid</ref> ''[[Sort]]eringsalgoritmen'' er [[noget]] mere avanceret og vil køre i ''<math>O(n * lg(n))</math>'' tid. Når [[tid]]en så er udløbet, siger ''algoritmen'' "'''[[pi]]ng!'''", så du véd, at den er færdig.<ref>[[Her]]efter åbner du lågen og [[tag]]er ''[[al]]goritmen'' [[ud]]. Lad den køle af et par minutter på et [[Fedt|fr]][[ost]][[fri]]t [[under]][[lag]]</ref> |
| | ==Kvantogoritmer== |
| | I [[kvantecomputer]]e bor der såkaldt ''qubits'',<ref>svarer til de [[gammel]]dags [[bi]]ts, bare med et par ekstra [[bogstav]]er</ref> og [[derfor]] skal man også bruge en slags ''algoritmer'' til [[dem]]. Men i stedet for at kalde dem for [[kvant]]emekaniske [[Algebra|alg]]oritmer, så enedes [[forsker]]ne om det mere [[mund]]rette [[Kvantum-zeno effekten|''kvantetogoritmer'']] (eller blot ''kvitmer'' <ref>hvis det skal være [[rig]]tig [[Julefrokost|løssluppent]]</ref>). [[Den]] [[før]]ste [[1994|algoritme]] til [[for]][[mål]]et blev udtænkt af [[Eric Schon|''Peter Schohr'']], og den kaldes af samme grund for ''Schohrs Algoritme''.<ref>For at indregne et heltal N, kører ''Schohrs algoritme'' i ''[[pol]]yn[[om]]iel [[tid]]'' (den forløbne tid er ''polynomial'' i log ''N'', hvilket samtidig er den givne [[stør]]relse [[af]] [[in]][[put]]tet).<br />[[Kvant]]egates af størrelsen <math>O ((log N) 2 (log log N)</math> (log log log N)) bruger en hurtig multiplikation, der [[vis]]er, at [[primtal]][[so]]pløsnings[[problem]]et ''kan'' løses, og dermed befinder ''algoritmen'' sig i [[Fremmedord|kompleksitetet]]s[[klasse]]n [[Akronym|CPQ]]. Dette er en [[milliard]] [[gang]]e [[Hurra|hur]][[tiger]]e end den mest effektive [[klassisk]]-[[Fake news|fakt]]o[[ris]]e[[ren]]de ''algoritme'', ''[[den]] [[gener]][[el]][[le]] [[tal]]-[[felt]]-[[si]]'', som [[jo]] [[arbejde]]r i [[Jægerstenalderen|sub-eksponentiel tid]] - om <math>O (e1.9 (log N) 1/3 (log log N) 2/3)</math> - Effektiviteten af ''Schohrs algoritme'' skyldes [[Kvantemekanik|kvante-Fouriertransf]][[orm]]at[[ion]]en, samt [[mod]]ulær [[eks]]ponentialitation ved de mange og hyppigt [[Deja vu|gentagne divisioner]], som man kan få [[lov]] at [[lav]]e [[på]] [[en]] [[kvantecomputer]]</ref> 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''.<ref>hvilket [[jo]] [[er]] [[Gangster|ganske]] [[Nem|let]], [[da]] [[42|''N'']] [[er]] [[et]] [[bog]][[stav]], ''Mission completed!''</ref> |
| ==Hvem bruger algoritmer?== | | ==Hvem bruger algoritmer?== |
| *[[Mig]] | | *[[Atom]][[fysik]]ere |
| *[[Dig]] | | *<s>[[Dig]]</s> |
| *[[Ingen]] | | *[[Spion|Efterretningstjenester]] |
| | *[[Cern]] |
| *[[Commodore 64|Computere]] | | *[[Commodore 64|Computere]] |
| *[[Oculus|Cyberspacebriller]] | | *[[Oculus|Cyberspacebriller]] |
| *[[Fremmed]][[ord]][[bog]]s[[forfatter]]e | | *[[Fremmed]][[ord]][[bog]]s[[forfatter]]e |
| | *[[Ingen]] |
| | *[[Kvantecomputer]]e |
| | *[[Matematik]]ere |
| | *[[Mig]] |
| | ==Polynominel tid og primtalsopløsningsproblemet i noteform== |
| | <references> |
| [[Kategori:Ting som almindelige mennesker ikke fatter en brik af]][[Kategori:Matematik]][[Kategori:Spændende ord]] | | [[Kategori:Ting som almindelige mennesker ikke fatter en brik af]][[Kategori:Matematik]][[Kategori:Spændende ord]] |
Nej tak, vi har alle de algoritmer, vi kan spise!
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 intoksikerede bevidsthed - ud fra tusinder af forprogrammerede 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 for at løse et problem i størrelsen . Det vil her sige, at køretiden af algoritmen vil være kvadratisk afhængig af de inddaterede datas størrelse.[2] Sorteringsalgoritmen er noget mere avanceret og vil køre i tid. Når tiden så er udløbet, siger algoritmen "ping!", så du véd, at den er færdig.[3]
Kvantogoritmer
I kvantecomputere bor der såkaldt qubits,[4] 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 [5]). Den første algoritme til formålet blev udtænkt af Peter Schohr, og den kaldes af samme grund for Schohrs Algoritme.[6] 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.[7]
Hvem bruger algoritmer?
Polynominel tid og primtalsopløsningsproblemet i noteform
<references>
- ↑ (hvis du prøver at kigge op under Jennifers skørter i over fem minutter, vil din hjerne blive forvandlet 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 frostfrit underlag
- ↑ 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 polynomiel tid (den forløbne tid er polynomial i log N, hvilket samtidig er den givne størrelse af inputtet).
Kvantegates af størrelsen (log log log N)) bruger en hurtig multiplikation, der viser, at primtalsopløsningsproblemet kan løses, og dermed befinder algoritmen sig i kompleksitetetsklassen CPQ. Dette er en milliard gange hurtigere end den mest effektive klassisk-faktoriserende algoritme, den generelle tal-felt-si, som jo arbejder i sub-eksponentiel tid - om - Effektiviteten af Schohrs algoritme skyldes kvante-Fouriertransformationen, 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 bogstav, Mission completed!