algoritme

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 ... så ... 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 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 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)². 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.

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 3n²+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(n²), hvor man udelader både den konstante faktor og det langsomst voksende led. Notationen O(n²) betyder, at der findes en konstant k, så køretiden er mindre end k·n², når blot n er stort nok. Da 4n² er større end 3n²+17n, når blot n er mindst 17, er køretiden dermed O(n²).

• beregnelighed
• Euklids algoritme
• kompleksitet