substantiv
eng. closure

transitiv afslutning

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

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.

substantiv
eng. breadth first search

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

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.

substantiv
eng. depth first search

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.

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

flettesortering

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

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.

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

adjektiv
eng. greedy

• grådig algoritme
• grådig knudefarvning

eng. insertion sort

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.

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.

eng. node

Det danske ord /node/ er noget andet.

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 kø er ligeledes queue (med samme udtale som kø, 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«.

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

eng. linear probing

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

eng. Markov chain

substantiv
eng. query

Alternativ: forespørgsel

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?).

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.

eng. separate chaining eller direct chaining eller bare chaining

eng. Shell sort

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

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

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.

eng. symbol table

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æ

eng. topological sort

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.

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.

eng. selection sort

Alternativer: udvælgesessortering, udtagelsessortering.

eng. path

Dijkstras algorithme finder korteste veje

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

Et alternativ er sti.