Algoritmisk fagterminologi
- afslutning
- om strukturer; den mindste omsluttende struktur, der er lukket under en vis operation. Transitiv afslutning, især om grafer; den graf, som indeholder kanten \(uv\) for hvert par af knuder \((u,v)\), for hvilket der er en vej fra \(u\) til \(v\) i den givne graf..
- breddesøgning
- algoritme for gennemsøgning af en graf, hvor knuderne besøges lagvist Breddenummerering, afstandsnummerering af knuderne i en graf fra en kildeknude. Kildeknuden har breddenummer 0, dens naboer har nummer 1, deres naboer har nummer 2, osv. .
- del og hersk
- et paradigme for algoritmisk problemløsning
- dybdesøgning
- algoritme for gennemsøgning af en graf, hvor knuderne besøges efter først til møllen-princippet.
- dynamisk programlægning
- et paradigme for algoritmisk problemløsning
- flette
- sammenføje to ordnede følger til én
- flettesortering
- en sorteringsalgoritme baseset på fletning.
- foranderlig
- om datastrukturer for samlingstyper; en datastruktur er foranderlig, hvis den tillader ændring af elementerne i samlingen.
- forén og find
- en datatype til repræsentation af en familje af disjunkte mængder, med entydige repræsentanter. Operationerne tillader forening af to mængder og fund af repræsentanten for den mængde, som indeholder et givet element. Ofte om en konkret implementation af datatypen som en skov af indtræer. Vægtet forening, en opdateringsstrategi baseret på mængdestørrelse. Rangeret forening, en opdateringsstrategi. Vejforkortning, en opdateringsstrategi.
- grådig
- et paradigme for algoritmisk problemløsning Grådig algoritme, en algoritme, der følger en grådig strategi..
- hakke
- sprede over et udfaldsrum, ofte på en pseudotilfældig måde med henblik på at opnå en ligelig fordeling over udfaldsrummet Hakkefunktion, en funktion, der hakker. Hakkeværdi, den hakkede værdi. Resultatet af en hakkefunktion.. Hakketabel, en tabel af værdier, især om en associativ række, hvor værdiernes indeks er deres hakkeværdi. Kryptografisk hakkefunktion, en hakkefunktion, der er vanskelig at invertere. Afstandsfølsom hakkefunktion, en hakkefunktion fra et metrisk rum, hvor elementer med mindre afstand har højere kollisionssandsynlighed .
- hob
- datastruktur Binærhob, en særlig slags hob. Rækkebaseret hob, implementation af en binærhob baseret på rækker. Hobsortering, en sorteringsalgoritme.
- hægte
- sætte sammen, ofte om sammensætningen af knuder i en datastruktur ved hjælp af pegere
- hægtet liste
- en datastruktur, kan defineres rekursivt som værende enten den tomme liste eller en knude, der indeholder et element og en reference til en hægtet liste
- indsættelsessortering
- en sorteringsalgoritme.
- kant
- relationen mellem knuderne i en graf. Rettet kant, en ikke nødvendigvis symmetrisk binær relation mellem knuder. Urettet kant, en symmetrisk binær relation mellem knuder. Dobbeltkant, en kant mellem samme knudepar som en anden kant. Vægtet kant, en kant med tilknyttet værdi, fx en omkostning eller kapacitet.
- kantfølge
- i en graf; en følge af hosliggende knuder og kanter. Ofte når gentagelse af knuder eller kanter udtrykkeligt er tilladt.
- knude
- element i en graf. En graf består af knuder og kanter mellem knuderne. Knudemængde, mængden af knuder i en graf. Knudeinduceret delgraf, en delgraf \(H\) af grafen \(H\) er knudeinduceret af knudedelmængden \(U\subseteq V(G)\), hvis \(V(H)= U\) og \(uv\in E(H)\) hvis og kun hvis \(u,v\in V(H)\) og \(uv\in E(G)\). . Rodknude, en specifik knude i et rodfæstet træ.
- komplet
- repræsentativ for en problemklasses sværeste problemer
- kviksortering
- En sorteringsalgoritme
- kø
- datastruktur, der understøtter indsættelse af elementer i den ene ende af en liste og fjernelse i den anden. Fifu-kø, en almindelig kø, hvor det først tilføjede element også er det først fjernede.
- kørselstid
- den tid, det tager at udføre en algoritme, ofte i en underforstået abstrakt maskinemodel, i værste fald og som funktion af problemstørrelsen
- linearitmisk
- om funktioner; med samme vækstrate som \(n\log n\).
- lineær sondering
- en datastruktur, der består af en hakketabel med brug af åben adressering, dvs. at værdier ikke nødvendigvis står på den tabelindgang, der er givet af deres hakkeværdi
- markovkæde
- stokastisk model for en følge af afhængige hændelser.
- opslag
- det at slå op i nogen, fx en datastruktur
- ordbog
- en datastruktur
- peger
- en værdi der skal tolkes som en reference til en anden værdi, ofte i termer af værdiens lageradresse
- præfikstræ
- en datastruktur, især brugt til at repræsentere mænge af strenge, kendetegnet ved at elementerne i mængden er implicit repræsenterede som stier fra roden til en knude
- refleksiv
- en relation er refleksiv, hvis hvert element er relateret til sig selv.
- rette
- lade noget pege i en bestemt retning. Især brugt i tillægsmåde, »rettet«. Rettet kant, en orienteret kant. Rettet graf, en graf, hvor hver kant har retning. En rettet graf kaldes »orienteret«, hvis den ikke indeholder et par af knuder, som er forbundet af to kanter i hver sin retning. . Urettet graf, en graf, hvis kanter ikke har retning. . Kredsfri rettet graf, en rettet graf uden (rettet) kreds. En kredsfri rettet graf tillader en topologisk sortering af knuderne..
- rutenøgle
- en værdi, der bruges til navigation i en datastruktur eller opdeling i en algoritme, fx en intern knude i et søgetræ eller ruteelementet i kviksortering
- række
- grundlæggende datastruktur, som tillader vilkårlig adgang til nummererede elementer, ofte af samme type.
- separat kobling
- en datastruktur, der består af en hakketabel, hvis indgange indeholder sammekoblede værdier, fx i en usorteret følge fremstillet som hægtet liste eller dynamisk række
- shellsortering
- en sorteringsalgoritme opkaldt efter Donald Shell.
- spændetræ
- en kredsfri og sammenhængende delgraf af en graf, der indeholder alle grafens knuder Minimalt stændetræ, i en vægtet graf, et spændetræ af minimal total vægt. Spændeskov, en kredsfri delgraf af en graf, der indeholder alle grafens knuder. En sammenhængdende spændeskov er et spændetræ. Udspændende delgraf, en delgraf af en graf, der indeholder alle grafens knuder. En kredsfri udspændende delgraf er en spændeskov..
- stak
- datastruktur, der understøtter indsættelse og fjernelse af elementer i samme ende af listen Stakbaseret sprog, en type programmeringssprog, hvor udtryksevalueringen er stakbaseret. Kaldstak, operativsystemets stak af aktive delrutiner.
- søgetræ
- en datastruktur Binært søgetræ, et søgetræ hvor hver knude har højst to børn. 2-3-søgetræ, et balanceret søgetræ hvor hver knude har to eller tre børn. Rødt-sort søgetræ, et søgetræ, der følger en rød-sort balanceringsstrategi. Top-ned 2-3-4-træ, et søgetræ. Bund-op 2-3-4-træ, et søgetræ.
- topologisk sortering
- nummering af knuderne i en kredsfri rettet graf således at hver kant er rettet fra et mindre nummer til et større.
- ubegrænset række
- en dynamisk datastruktur
- udvalgssortering
- en sorteringsalgoritme.
- vej
- i en graf; en følge af hosliggende knuder og kanter. Ofte om en sådan følge uden gentagelser; da udtrykkeligt som »simpel vej«.
- ækvivalensrelation
- en binær relation, som der symmetrisk, transitiv og refleksiv.
Licensed under CC BY-NC-SA.