Datastruktur och algoritmer begrepp

All None Speichern

• Algoritm Abstrakta program oberoende något specifikt programspråk. En noggrann plan, en ändlig uppsättning regler som bestämmer en följd av operationer för att lösa en specifik typ av uppgift. Noll eller flera indata, ett eller flera utdata.
• Element Har ett värde och en position, alltså ett visst läge i strukturen.
• Datatyp = objekt + operationer En datatyp styrs dels genom sin objektmängd, men även vilka möjligheter som finns till att hantera dessa objekt; jämföra, kombinera, manipulera. Dessa hanteringsmöjligheter kallar vi för operationer.
• Enkel datatyp En datatyp som inte är sammansatt, till exempel heltal.
• Diskret linjärt ordnad datatyp En datatyp med före-efter-relation
• Gles Matris De flesta värdena i grafen är noll, alltså att de inte har några värden. Typ ett excel ark, kan va att föredra att implementera som ett fält.
• Komplett graf Där är alla grannar till alla, där n stycken noder finns n stycken bågar.
• Hanterbara problem Om man känner till lösningen där resursanspråken begränsas av polynomfunktioner av uppgiftens storlek n, för stora n.
• Traversering Att man systematiskt besöker alla element i ett dataobjekt som är “naturligt” för datatypen och dess karakteristiska struktur. Två sätt att traversera: från början till slutet eller tvärtom.
• Sökning Ett av syftena med traversering, man traverserar datatypen tills det första elementet som uppfyller ett bestämt villkor. Traverseringen avbryts när ett sådant element dyker upp.
• Modell för en datatyp(mental) Vardaglig förteelse som kan vara som en förebild eller metafor för en datatyp. Vardagligt objekt som kan representera en datatyp - schackbräde
• Struktur hos dataobjekt Ett dataobjekt av en sammansatt datatyp består av element som är ordnade på ett speciellt sätt. Struktur hos ett dataobjekt är vad man har kvar om man bortser från alla elementvärden.
• Informell specifikation av en gränsyta axiom. Urskiljer vilka operationer och parametrar av vilka typer som ska användas. Operationerna beskrivs informellt men så exakt som möjligt.
• Beräkningsbar Om och endast om det finns en turingmaskin som löser problemet (beräknar uppgiften). En turingmaskin är en tänkt abstrakt maskin.
• Ohanterliga problem Är problem som saknar kända algoritmer av polynomisk komplexitet. För sådana problem känner man ofta inte till någon bättre lösningsansats än att prova alla tänkbara möjligheter tills dess att man hittar en lösning. Lösningen har en tids- eller rumskomplexitet som är superpolynomisk.
• Hashfunktion Funktion som avbildar den jättestora indextypen A till en inte fullt så stor (och definitivt ändlig) indextyp B. Omvandlar alltså en godtycklig datamängd till en hashsumma av samma storlek. Med andra ord, en algoritm som omvandlar ett mindre heltal som kan fungera som ett index.
• Fyllnadsgrad Antalet upptagna platser i en statisk datatyp. Kvoten mellan antalet insatta element och antal platser i tabellen.
• Position Ett visst läge i strukturen hos det sammansatta objekt som elementet ingår i.
• Index Position i en mängd. Ett fältelements fullständiga koordinater.

All None Speichern