Mellem to ord

I dag havde jeg en projektgruppe på 1. semester til eksamen; deres projekt handlede om detektering af plagieret tekst, og de havde i deres projekt implementeret en algoritme, der kan beregne den såkaldte Levenshtein-afstand. Levenshtein-afstanden er en velkendt form for redigeringsafstand, dvs. en metrik (i sædvanlig forstand) over mængden af tekststrenge. Hvis D(s,t) = k, er det mindste antal redigeringsoperationer, der kan omskrive strengen s til strengen t det hele tal k. En redigeringsoperation er her enten en sletning af et tegn, en tilføjelse af et tegn eller en substitution af et tegn for et andet. Man kan nemt definere D(s,t) rekursivt i s og t, men en effektiv algoritme til beregning af D vil benytte dynamisk programmering.

Levenshteins algoritme er fra 1966 og er eksempel på et af de fundamentale bidrag til datalogi, som kommer fra Rusland (eller Sovjetunionen, som det jo var dengang). Russerne haltede bagefter amerikanerne hvad angår computernes formåen – da jeg var i Rusland (dvs. Sovjetunionen) i 1989, kunne jeg få bekræftet dette. Men hvad angår russernes videnskabelige præstationer, har de leveret meget vigtige bidrag.

Et andet velkendt eksempel er AVL-træerne, der skyldes Adelson-Velskii (der blev 90 år i år, og det endda på min fødselsdag) og Landis, som desværre ikke er mere. Et tredje velkendt eksempel er Leonid Levins opdagelse af NP-fuldstændighed uafhængigt af Steve Cook fra Canada. Adelson-Velskii bor i dag i Israel, Levin rejste til USA – men Levenshtein blev i Rusland, hvor han i en menneskealder har været tilknyttet Keldysh-Instituttet for Anvendt Matematik i Moskva. Billedet ovenfor forestiller ham.

Og så må jeg endelig ikke glemme at nævne Andrei Ershov, der opfandt det i programmeringssprogsteori vigtige begreb partiel evaluering uafhængigt af (og samtidig med) Yoshihiko Futamura fra Japan, eller Yuri Ershov (mig bekendt ikke i familie med Andrei), der har ydet vigtige bidrag inden for logik i datalogi.

En vigtig pointe i alt dette er at datalogi er andet og mere end en samling teknologier; en god matematisk indsigt er guld værd.