Algoritme. Rutediagrammet viser en tekstsøgningsalgoritme. Teksten består af en tegnsekvens tb[1], ..., tb[m]; m er et numerisk udtryk for sidste tegn i teksten. Søgeordet består af sekvensen sb[1], ..., sb[n], hvor n udtrykker sidste tegn i søgeordet. Indeks markerer starten på den del af teksten, der på et givet tidspunkt sammenlignes med søgeordet. I eksemplet er søgeordet eller, der skal findes i teksten Modeller er beskrivelser.

.

En algoritme er en forskrift for en følge af beregningstrin, der fra et problems data fører til resultat. Forskriften skal være utvetydig og bestå af grundoperationer, der umiddelbart kan udføres.

Faktaboks

Etymologi
Ordet algoritme kommer af engelsk algorithm, fra latin algorismus, fra arabisk al-Khwarizmi, arabisk matematiker; formen med -tm skyldes association med græsk arithmos 'tal'.

Et problem specificeres ved et sæt data og resultatets sammenhæng med disse. Problemet kan være matematisk som Find det største hele positive tal, der går op i både 60 og 24, men kan også dreje sig om andet, fx tekster: Find det første sted i teksten 'Modeller er beskrivelser', hvor 'eller' forekommer. I det første eksempel er data tallene 60 og 24, og resultatet af beregningen er 12. Problemet kan løses ved brug af Euklids algoritme. I det andet eksempel er data tekst og søgeord, og resultatet er bogstavnumre. Dette problem løses ved en tekstsøgningsalgoritme.

Algoritmer er oftest knyttet til generelle problemtyper. Det konkrete problem ved tekstsøgning er af følgende generelle type: Find i en forelagt tekst den første forekomst af et søgeord. Ved at udforme algoritmer for problemtyper opnår man, at samme algoritme kan anvendes for alle konkrete problemer af en given type. Samtidig bliver det dog sværere at vurdere, om denne er korrekt og effektiv.

Specifikation af algoritmer

Skal et problem løses af en computer, skrives algoritmen i et programmeringssprog, og som en mellemform til et egentligt program beskrives en algoritme ofte i et rutediagram eller i pseudokode: En notation, der minder om et program i et programmeringssprog, men udtrykt på et mere abstrakt niveau end et konkret program. I logikken kaldes udførelsen af en sådan beregning for kalkule.

En af de fundamentale byggesten i konstruktion af algoritmer er gentagelser af samme beregningstrin, en løkke. Løkker udføres et antal gange, der varierer med det konkrete problems data; en udførelse kaldes en iteration. Andre fundamentale elementer er betingede sætninger (hvis ... ... ellers ...), der sammen med hop (gå til ...) kan anvendes ved konstruktion af løkker. Centrale er også rekursion og muligheden for at ændre værdien af variabler, som for eksempel positionstælleren i en tekstsøgningsalgoritme.

Korrekthed og effektivitet

Korrekthed og effektivitet er grundlæggende egenskaber ved algoritmer. En algoritme kaldes korrekt, hvis den, anvendt med data, der overholder specifikationerne i problembeskrivelsen, i løbet af et endeligt antal beregningstrin løser problemet. En fejlbehæftet algoritme giver for et konkret problem enten en forkert løsning eller et uendeligt antal beregningstrin. Det er ofte svært at afgøre, om en algoritme er korrekt, idet man skal argumentere for, at der ikke findes et konkret problem, der fører til en fejlsituation. I det generelle tilfælde er korrekthed faktisk uafgørligt.

Effektiviteten måles ved, hvor hurtigt antallet af simple beregningstrin vokser, når det konkrete løste problems datamængde vokser — dette kaldes asymptotisk kompleksitet. En behersket vækst betyder, at selv problemer med meget store datamængder kan løses af den givne algoritme, uden at regnetiden bliver urimelig stor. Polynomier — bl.a. funktioner af typen xk, for eksempel x2 og x4 — vokser erfaringsmæssigt tilstrækkelig langsomt til, at algoritmer med polynomiel vækst for antallet af beregningstrin som funktion af datamængden regnes for effektive. Disse kaldes polynomielt begrænsede algoritmer. Tekstsøgningsalgoritmen ovenfor er effektiv, idet antallet af bogstavsammenligninger under udførelsen højst er n·(m-n+1), datamængden er (n+m) bogstaver og tegn, og n·(m-n+1) er mindre end (n+m)2. Der findes dog endnu mere effektive algoritmer, hvor antallet af beregningsskridt er begrænset af k·m+n, hvor k er en konstant, der ikke afhænger af n eller m.

For visse problemtyper kan det bevises, at effektive algoritmer ikke eksisterer. For mange praktiske optimeringsproblemer, for eksempel bestemmelse af korteste ruter ved udbringning af varer fra et depot, er der endnu ikke fundet effektive algoritmer, og om dette overhovedet kan lade sige gøre, er et åbent spørgsmål.

Et problem kaldes uafgørligt, hvis det beviseligt ikke kan løses ved hjælp af en algoritme, uanset hvor mange beregningstrin det tillades algoritmen at udføre. Eksempelvis findes der ingen algoritme, der generelt ud fra et computerprogram og programmets inddata kan afgøre, om det med de givne inddata kun udfører et endeligt antal programskridt. Problemet kaldes "standsningsproblemet". Eksistensen af dette og lignende problemer belyser grænserne for problemløsning ved brug af algoritmer og computere.

Asymptotisk kompleksitet og store-O notation

Når man skal beskrive en algoritmes køretid som en funktion af størrelsen af inddata er man primært interesseret i, hvor hurtigt køretiden vokser, når inddata vokser, særligt for store datastørrelser. Dette kaldes asymptotisk kompleksitet. Ligeledes er man ikke interesseret i konstantfaktorer, så en algoritme, der bruger dobbelt så mange beregningsskridt som en anden betragtes som at have den samme asymptotiske kompleksitet. Da små inddata er uinteressante for asymptotisk kompleksitet, ser man kun på de hurtigst voksende dele af køretiden. Hvis, for eksempel, algoritmen for inddata af størrelse n bruger 3n2+17n beregninger, vokser det kvadratiske led meget hurtigere end det lineære led, så det sidste ignoreres, og man siger, at køretiden er O(n2), hvor man udelader både den konstante faktor og det langsomst voksende led. Notationen O(n2) betyder, at der findes en konstant k, så køretiden er mindre end k·n2, når blot n er stort nok. Da 4n2 er større end 3n2+17n, når blot n er mindst 17, er køretiden dermed O(n2).

Læs mere i Den Store Danske

Kommentarer

Kommentarer til artiklen bliver synlige for alle. Undlad at skrive følsomme oplysninger, for eksempel sundhedsoplysninger. Fagansvarlig eller redaktør svarer, når de kan.

Du skal være logget ind for at kommentere.

eller registrer dig