algoritme

© SDE/Jens Clausen

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.

algoritme, 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.

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.

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. 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 ... så ... ellers ...), der sammen med hop (gå til ...) kan anvendes ved konstruktion af løkker. Central er også muligheden for at ændre værdien af variable som fx "indeks" i tekstsøgningsalgoritmer.

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.

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 x^k, for eksempel x² og x⁴ — 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)².

For visse problemtyper kan det bevises, at effektive algoritmer ikke eksisterer. For mange praktiske optimeringsproblemer, fx 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 bevisligt 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 "haltingproblemet", dvs. "stopproblemet". Eksistensen af dette og lignende problemer belyser grænserne for problemløsning ved brug af algoritmer og computere.