Thore Husfeldt

Dansk algoritmeterminologi

with 4 comments

This post in Danish.

Coddled egg on hash, letkogt æg på biksemad. Kilde: Wikimedia Commons.

Formålet med denne oversigt er at sammenfatte (og til en vis grad foreslå) dansk fagterminologi for algoritmer og datastrukturer. Movitationen er dels at lette oversættelsen af fagtermer både mellem og inden for begge sprog, dels at stille dansk terminologi til rådighed for dem, der måtte have behov for at udtrykke sig skriftligt eller i formidlingsøjemed uden for snævre fagkrede.

Blandt fagfæller vil man i de fleste mundtlige situationer kunne gøre sig bedst forståelig ved at anvende de engelske termer med tillempet dansk-engelsk udtale og syntaks (»til sidst merger du /arraysene/«). Denne tilgang kan også anbefales, hvis man primært er interesseret i at signalere tilhørighed til fagfællesskabet.

Jeg har stor sympati for den angelsaksiske tradition for at finde fagtermer som er både kødfulde og ofte lidt latterlige (mouse, bubble sort, stack), dels fordi det skaber nyttige analogier i en ellers fremmedgørende digital virkelighed, dels fordi uhøjtideligheden nedbryder den benovelse, men ellers kan føle i mødet med fagterminologi. Desværre går begge disse effekter tabt, når mindre gængse engelske ord (merge, browse, hash, array) bruges uoversatte.

Der findes mig bekendt intet trykt dansksproget material i algoritmer og datastrukturer ud over Schmidt og Scharzbachs noter »Programmeringsteori og datastrukturer« og »Grafalgoritmer og algoritmisk problemløsningsteknik« fra Aarhus Universitet fra 1990erne og Polyteknisk forlags »Find formlen – algoritmer og datastrukturer« fra 2007. Deres terminologi er medtaget her. Jeg er taknemmelig for
at blive gjort opmærksom på dokumenterede forekomster af ord jeg måtte have overset. Nogle af konstruktionerne forneden er dog helt mine egne forslag; jeg har markeret dem med et advarende udråbstegn.

afslutning

substantiv
eng. closure

transitiv afslutning

»et endeligt dimensionalt kompakt Hausdorffrum, der er afsluttet i primidealrummet mht. hylster-kerne topologien«

spredefunktion (!)

eng. hash function

spredeværdi (eng. hash value)

spredetabel (eng. hash table)

universel spredning (eng. universal hashing)

Kommentarer:

Den udbredte danske terminologi er at anvende det engelske ord hash i tillempet dansk udtale ([hasj]), som i hashfunktion, hashværdi, hashtabel, at hashe.

På engelsk betegner substantivet hash en blandet ret typisk baseret på genopvarmede rester fra i går, og to hash betyder at hakke. I den rige teoridannelse bag spredefunktioner findes der sågar et »leftover hash lemma«. Desværre forbinder vi på dansk ikke hash med biksemad, men med det arabiske ord for hamp, hashish, et udbredt rusmiddel.

Har man lyst til at bruge et ord på dansk, der holder den engelske metafor i live, kan man forsøge sig med hakkefunktion, som også morfologisk ligger tæt op ad originalet. (Min ordbog informerer mig om at hash kommer til engelsk fra de franske hacher, som også er rod til hatchet, mens det danske hakke har plattyske rødder.) Mere spændende er rodefunktion. Jeg har i en periode
sagt biksefunktion (bikseværdi, universalbiks, gøgebiks) til mig selv, som indeholder både det rodede og det kulinariske perspektiv. Jeg er meget splittet i denne sag og kommer formentlig på bedre tanker engang.

bredde først-søgning

substantiv
eng. breadth first search

Bemærk tegnsætning, jf. først til mølle-princip.

del og hersk

substantiv
eng. divide and conquer

»den hurtige fouriertransformation er en del og hersk-algoritme«

Alternativer: del og kombinér (brugt ved AU).

Bemærk tegnsætningen, jf. gør det selv-mand.

dybde først-søgning

substantiv
eng. depth first search

dynamisk programmering

substantiv
eng. dynamic programming

Kommentarer: Ordet programmering er i denne sammenhæng lige så misvisende på dansk som det er på engelsk. Betydningen er »at lægge en plan«, som på dansk er kendt fra 1959 ifølge DDO, ikke »at skrive instruktionerer til en maskine«. Metoden blev formaliseret og
navngivet af Bellman i 1950erne, som beskriver baggrunden for terminologien i sin selvbiografi Eye of the Hurricane, 1984.

flette

verbum
-r, -de, -t
eng. merge

flettesortering

Vi kan flette to sorterede lister in lineær tid.

komplet

eng. complete

Et problem er NP-komplet, hvis det tilhører NP og er NP-hårdt.

Alternativet er fuldstændig, som bruges ved AU. Komplet ligger morfologisk nærmere det gængse engelske begreb.

graf

I matematikken henviser betegnelsen graf både til tegningen af en matematisk funktion, og til en kombinatorisk struktur. Dette uheldige begrebssammenfald optræder på både engelsk (graph) og tysk (Graph), hvor terminologien blev skabt i 1930erne. Grafens elementer hedder hjørner (eng. vertices, ty. Ecken), knuder (eng. nodes, ty. Knoten), eller bare punkter (eng. points).
Elementerne er forbundet med kanter (eng. edges, ty. Kanten), eller bare linjer. Når grafen er rettet (eng. directed), hedder kanterne ofte buer (eng. arcs, ty. Bögen) eller rettede kanter (eng. directed edges). En internt knudedisjunkt vej med samme hovede og hale er en
kreds (eng. circuit) eller cykel. Hvis grafen udgør et træ, kaldes elementerne ofte for knuder på dansk.

Se: rettet graf, knude

grådig

adjektiv
eng. greedy

  • grådig algoritme
  • grådig knudefarvning

indsættelsessortering

eng. insertion sort

hob

substantiv, fælleskøn
-en, -ene
eng. heap.

Mads sætter et element i hoben. Lise fjerner et element fra hoben. Det mindst element ligger øverst i hoben.

binærhob eller binær hob (eng. binary heap).

rækkebaseret hob (eng. array based heap).

hobsortering (eng. heap sort)

Alternativer til hob er bunke (som anvendes ved AU) eller dynge, som begge ligger bedre i munden. Men hob ligger nærmere den etablerede engelske betegnelse heap og optræder ved både KU, SDU og DTU.

hægtet liste

eng. linked list

Bruges ved KU, RUC og DTU. Ved AU bruges betegnelsen kædet liste. Man kan også støde på lænket liste, som kan være attraktiv fordi den ligger morfologisk (men ikke inholdsmæssigt) nærmere den engelske terminologi.

dobbelthægtet liste

En hægtet liste er en rekursiv datastruktur som er enten tom eller en reference til en knude bestående af et element og en reference til en hægtet liste.

knude

eng. node

Det danske ord /node/ er noget andet.

kviksort

eng. quicksort

Et udbredte alternativ er at bruge engelsk stavning og en tillempet engelsk udtale af quicksort, jf. kviksølv, kviksand, men quickstep. Algoritmen blev navngivet af C. A. R. Hoare og kunne sagtens hedde hoaresortering i stedet.

Se splitelement

substantiv, fælleskøn
-en, -ene
eng. queue, fra fransk queue

Søren stiller et element i køen. Metter fjerner et element fra
køen.

Først ind-først ud-kø.

prioritetskø (eng. priority queue)

Forældet dansk stavemåde for er ligeledes queue (med samme udtale som , jf. stavemåden bøf for beuf).

Almindelig ved alle danske læreanstalter. De engelske verber for indsættelse og fjernelse, enqueue og dequeue, er så lidt mundrette for danske sprogbrugere, at de sjældent anvendes, selv i engelsk-præget talesprog. Svensk har det praktiske verbum att köa for at stille sig i kø, og det ligger nært at bruge att avköa for dequeue, men på dansk virker det kluntet at bruge »Søren køer elementet« og »Mette afkøer elementet«.

linearitmisk

adjektiv
-, -e
eng. linearithmic.
[lineɑˈʁidmisg]

Neologisme, sammentrækning af lineær og logaritmisk. Funktionstilvækst proportional med $Nlog N$.

  • flettesortering kører i linearitmisk tid

lineær probering

eng. linear probing

Probere og probering er blevet brugt på dansk i århundreder inden for metallurgien i samme betynding som eng. probe.

markovkæde

eng. Markov chain

opslag

substantiv
eng. query

Alternativ: forespørgsel

rettet graf (!)

eng. directed graph, no. rettet graf, sv. riktad graf.

urettet graf

rettet kant, rettet cykel, rettet vej

Der er ikke mig bekendt nogen vedtaget terminologi for rettede grafer på dansk andet end betegnelsen orienteret graf og uorienteret eller ikke-orienteret graf. Desværre betyder oriented graph på engelsk er noget andet. Betegnelserne rettet og urettet undgår den mulige misforståelse, er kortere, mundrette (ha!), og gængse ord i dansk både som adjektiv og verbum, jf. »ensrettet vej« og »rette et våben mod nogen«.

Jørgen Bang-Jensen fra SDU, som har forfattet standardreferencen om rettede grafer, siger digraf på dansk (og digraph på engelsk), hvilket jeg finder både fikst og mundret. Ordet digraf findes allerede på dansk og er betegner i retskrivningen to bogstaver, der sammen repræsenterer én lyd. Bemærk at denne terminologi dog ikke giver noget forslag til rettet kant (dikant?) eller problemet med at betegne en graf som urettet (udigraf?).

række (!)

eng. array

På DTU bruges tabel, hvilket kan kollidere med anvendelser som symboltabel (eng. symbol table, som ikke er en række), engelske ord som hash table og brugen af tabel (eller table) for todimensionelle rækker. Række ligger tættere op ad den engelske array, frem for alt i betydningen »ordnet opstilling«, fx »the soldiers were arrayed in the yard«.

En anden dansk tradition, brugt fx ved AU, er at bruge vektor for array. Det giver matematisk god mening; i nogle år kolliderede denne brug med datatypen Vector i Java, som var Javas standardimplementation af den fordoblingsbaserede dynamiske række. Brugen af Vector er blevet overskygget af collectionspakken, så ordet er sådan set ledigt igen.

separat hægtning

eng. separate chaining eller direct chaining eller bare chaining

shellsortering

eng. Shell sort

Sorteringsmetoden er opkaldt efter Donald Shell. Bemærk stavemåden med lille begyndelsesbogstav, jf. dieselmotor.

splitelement

eng. partition element eller pivot element

Visse kilder (men hverken Sedgewick lærebog, Hoares originalartikel eller Knuths bøger) kalder splitelementet for pivoteringselement (eng. pivot element), fra fransk pivot: »tap hvorom noget drejer sig«. Jeg har ikke været i stand til at finde en god begrundelse for denne terminologi – jeg har en mistanke om, at den henviser til
pivotering i militærformationer og er muligvis skabt af Cormen, Leiserson og Rivests lærebog. Betegnelsen er direkte misvisende, idet de andre elementer ikke pivoterer omkring splitelementet, som forresten heller ikke står stille. Nytten af at introducere mystificerende terminologi, hvad enten det er på engelsk eller dansk, for en ganske gemen opdelingsproces har aldrig åbenbaret sig for mig. (I forbindelse med simpleksalgoritmen i lineær programmering giver pivotering derimod god mening.)

Alternativer: pivoteringselement, opdelingselement

stak

substantiv, fælleskøn
-ken, -ke, -kene
eng. stack, fra oldnordisk stakkr.

Søren trykker (eng. push) et element på stakken. Mette popper staktoppen.

Først ind/sidst ud-kø

*staktop (eng. stack top)

Indsættelsesoperationen hedder ofte push på engelsk, som oversættes med tryk bedre end med skub, hvis man vil bevare analogien til en fjederstøttet tallerkenstak. Der er ikke noget farverigt danskt ord for eng. pop, og »poppe op« og »pop op-bog« forekommer allerede på dansk. Man kan selvfølgeligt helt forlade push og pop-metaforerne og blot »lægge på stakken« og »fjerne fra stakken«, hvilket er både klart og ukontroversielt og derfor måske den mest anbefalelsesværdige løsning. Vil man lægge sig nærmere op ad den oprindelige tyske terminologi, kan man forsøge sig med kælderlager, indkældre og udkældre, som i for sig er kraftige og mundrette ord, men (så vidt jeg ved) helt uetablerede ved danske læreanstalter.

symboltabel

eng. symbol table

søgetræ

eng. search tree

binært søgetræ
2-3-søgetræ, jf. 1-0-føring
rødt-sort søgetræ, jf. sort-hvidt tv
top-ned 2-3-4-træ
bund-op 2-3-4-træ

topologisk sortering

eng. topological sort

trie

substantiv, fælleskøn
-en, -er, -erne
eng. trie

Det engelske trie er en neologisme som betegner en træ-lignende datastruktur navngivet efter midterstavelsen i retrieval, men udtales alligevel mest som try, ikke som tree. Man kan på dansk more sig med at finde en overstættelse som holder ordspillet i live, men det er vanskeligt og – givet triers relative sjældenhed – unødvendigt. Trie bør vel opføre sig som de danske substantiver die og gie, dvs. fælleskøn og med diftong.

udspændende træ

eng. spanning tree

letteste, udspændende træ

Et udbredt alternativ for letteste, udspændende træ er minimalt, udspændende træ. Bemærk dog, at i »minimalt udspændende træ« (i talesprog eller skriftligt uden komma) er minimalt et adverbium, og bekriver (ganske meningsløst) graden af udspændthed, i stedet for træets totale vægt.

udvalgssortering

eng. selection sort

Alternativer: udvælgesessortering, udtagelsessortering.

vej

eng. path

Dijkstras algorithme finder korteste veje

Det er NP-hårdt at finde en hamiltonvej i en graf

Et alternativ er sti.

Advertisements

Written by thorehusfeldt

March 29, 2011 at 11:49

Posted in Uncategorized

4 Responses

Subscribe to comments with RSS.

  1. Udmærket! Jeg synes selv bedre om gøgespredning end gøgebiks. Om end ordet leder tankerne hen på dette.

    Rasmus Pagh

    March 29, 2011 at 18:27

  2. Hvis man ser i “Forslag til tilføjelser til EDB-ordbog Dansk Standard DS 2049-1970” er “hashed key” oversat til “jævnet nøgle”. Det er vel ikke helt ved siden af.

    DS 2049-1970 oversætter i øvrigt “array” til “sæt”. Men jeg synes, at der er for stor risiko for forveksling med det engelske “set” (mængde). Jeg foretrækker “tabel”, da det på dansk bruges om både en- og todimensionale “ting”, man kan slå op i. hvor dit forslag “række” kun bruges om en dimension. Hvis du er ked af “tabel”, kan jeg foreslå “geled”, som kan bruges også om en todimensional opstilling (jævnfør også din millitære metafor).

    Jeg foretrækker “forespørgsel” som oversættelse af “query”, da “opslag” lyder som tabelopslag.

    Til “directed graph” foretrækker jeg “ensrettet graf” (og det modsatte en “ikke-rettet graf”).

    Man trykker ikke noget på en stak, man skubber eller stakker det. Og man popper det ikke af, man hiver eller afstakker det. Jeg foretrækker selv stakke/afstakke som verber.

    Torben Mogensen

    March 30, 2011 at 13:42

  3. Mange tak, Torben!

    Dine stakforslag er rigtig gode.

    En »ensrettet graf« dur ikke for grafen med E = {(u,v), (v,u), (u,w)}, synes jeg. »Ikke-rettet« har jeg sådan set intet imod, men finder »urettet« mere mundret.

    thorehusfeldt

    March 30, 2011 at 14:12

  4. Jeg blev gjort opmærksom på denne lille parlør: Algoritmikbegreber, som dokumenterer den etablerede terminologi ved nogle af de østdanske læreanstalter.

    thorehusfeldt

    March 30, 2011 at 14:17


Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: