DOA - begrepp

Alla Inga Spara

• Position En referens till en plats i en Lista. Positioner blir odefinierade så fort listans struktur ändras (efter Insert() eller Remove()). En Position kan bara användas i sin egen lista.
• Index En referens till en plats i ett Fält. Ett index kan användas i vilket fält som helst, så länge värdet ligger inom fältets gränser (fältets struktur ändras aldrig).
• Element vs. elementvärde Element = en plats i strukturen. Elementvärde = det värde som lagras där. En struktur kan ha fler element än elementvärden (dubbletter), men aldrig fler elementvärden än element.
• Fält (Array) Sammansatt, homogen, ordnad datatyp med fast storlek. Antal giltiga index n = High(a) − Low(a) + 1. Lägsta index är inte nödvändigtvis 0 (det är C-specifikt, ej krav på abstrakta Fält).
• Lista Sammansatt, homogen, ordnad datatyp. En lista med n element har alltid n+1 giltiga positioner (den extra positionen ligger efter sista elementet).
• Post (Record) Sammansatt och heterogen (olika fält kan ha olika typer) samt oordnad (ordningen på fältnamnen spelar ingen roll).
• Tabell Homogen datatyp bestående av nyckel-värde-par. Själva paret kan vara heterogent, men tabellen som helhet räknas som homogen. Lämplig för snabb sökning via en nyckel, t.ex. en hashtabell.
• Kö (Queue) FIFO-struktur — hanterar element i den ordning de kom in.
• Stack LIFO-struktur — det senast tillagda elementet hanteras först.
• DList / Riktad lista (gränssnitt) Abstrakt datatyp med funktionerna Empty, Isempty, First, Next, Isend, Inspect, Insert, Remove, Kill (samt ibland Copy). Alla funktioner utom Copy har komplexitet O(1); Copy har O(n).
• Multiplicitet Antalet gånger ett givet värde förekommer i en lista. Multiplicity() har komplexitet O(n); Max-multiplicity() blir O(n²) om Multiplicity() anropas för varje element.
• Stabil sorteringsalgoritm Bevarar den inbördes ordningen mellan element som är lika stora. Krävs för att sortera efter flera nycklar i tur och ordning (sortera på sekundärnyckel först, sedan primärnyckel).
• Bredden-först (BFS) Besöker noder nivå för nivå, från vänster till höger på varje nivå.
• Djupet-först, pre-order Nod → vänster delträd → höger delträd.
• Djupet-först, in-order Vänster delträd → nod → höger delträd. Ger sorterad ordning i ett BST.
• Djupet-först, post-order Vänster delträd → höger delträd → nod.
• Binärt sökträd (BST) Byggs enligt en ordningsrelation R. Enbart insättning utan balansering kan ge skev höjd. In-order ger noderna i R:s ordning.
• Trädets höjd (optimal) Minsta möjliga höjd för ett träd med n noder. Att minimera höjden minimerar den längsta kodsträngen i ett Huffman-träd.
• Hög (Heap) Specialfall av binärt träd. Partiellt sorterad: varje förälder kommer före sina barn enligt R (hierarkisk ordning). Inget krav på minimal höjd.
• Prioritetskö Sammansatt och sorterad (därmed ordnad) datatyp. Kan konstrueras som t.ex. en Hög, en Lista eller en Sorterad lista — implementationen påverkar inte de logiska egenskaperna.
• Prioritetskö komplexitet per implementation
• Som Hög Insert/Delete-first/Update: O(log n). Inspect-first: O(1).
• Som osorterad Lista Insert: O(1). Inspect-first/Delete-first: O(n). Update: O(1).
• Som Sorterad lista Insert: O(n). Inspect-first/Delete-first: O(1). Update: O(n).
• Dijkstras algoritm Kortaste vägen från en startnod till alla andra, icke-negativa vikter. Använder prioritetskö och relaxerar avstånd till grannoder.
• Kruskals algoritm Bygger MST genom att gå igenom bågar i stigande viktordning och lägga till en båge om den inte skapar en cykel. Antal varv = antal bågar m.
• Prims algoritm Bygger MST genom att växa ett träd från en startnod, lägga till billigaste bågen till en ny nod i taget.
• Floyds algoritm Kortaste vägen mellan alla par av noder. Ger avståndsmatris M och föregångarmatris P.
• Sammanhängande komponent Delmängd av en graf där det finns en väg mellan alla par av noder inom delmängden, men inte till noder utanför.
• DAG (Directed Acyclic Graph) Riktad graf utan cykler. En oriktad graf är aldrig en DAG.
• Bubble sort Värsta fall O(n²), bästa fall O(n) (redan sorterad). Stabil, in-place O(1) minne.
• Merge sort Rekursiv, O(n log n) i både värsta och medelfallet. Kräver extra minne, men är stabil.
• Quick sort Rekursiv, använder pivåelement. Medel O(n log n), värsta fall O(n²). Ej stabil.
• Sortering efter flera nycklar Sortera på sekundärnyckeln först, sedan på primärnyckeln (omvänd prioritetsordning). Kräver stabil algoritm.
• Ordo-notation, definition (c, n0) T(n) ≤ c·g(n) för alla n ≥ n0. Man väljer c och söker lägsta n0.
• Tillväxthastigheter, stigande ordning O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
• Beräkningsbar men ohanterlig O(2ⁿ) är superpolynomiellt; problemet går att lösa men är ohanterligt i praktiken.
• Binärsökning Halverar sökintervallet i varje steg, kräver sorterat fält. Komplexitet O(log n).
• Huffman-algoritmen Kombinerar de två lägst viktade träden till ett nytt, ger prefixfri kod. Minimera höjden för att minimera längsta kodsträngen.
• LZ78 Bygger upp en tabell av redan sedda delsträngar. Trie för kodning, Tabell för avkodning.

Alla Inga Spara