Nyckelbegrepp

Svensk-engelsk ADK-ordlista Här är 50 facktermer i ADK-kursen som inte har en uppenbar direktöversättning.

algoritm algorithm approximationskvot approximation ratio approximerbarhet approximability beräkningsbarhet computability beräkningsmodell computational model beslutsproblem decision problem beständig datastruktur persistent data structure bitkostnad bit cost datastruktur data structure dekomposition divide and conquer delmängdssumma subset sum dynamisk programmering dynamic programming enhetskostnad unit cost girig algoritm greedy algorithm grafgenomgång graph traversal grannlista adjacency list grannmatris adjacency matrix heuristisk/heuristik heuristic hörn vertex ickedeterministisk non-deterministic kant edge kantmatris incidence matrix komplexitet complexity konjunktiv normalform conjunctive normal form konstruktionsproblem constructionalsearch problem källa source latmanshashning lazy hashing målfunktion objective function mängdpartitionering partition problem mästarsatsen Master theorem NP-fullständig NP-complete oavgörbar undecidable oberoende mängd independent set optimeringsproblem optimization problem polynomisk reduktion polynomial reduction polynomisk tid polynomial time prioritetskö priority queue probleminstans problem instance rekursivt uppräknelig recursively enumerable restkapacitet residual capacity rimlig tid feasible time räknesortering counting sort satisfierbar satisfiable simulerad härdning simulated annealing slumpeliminering derandomization spännande träd spanning tree totalsökning exhaustive search tuff motståndare adversary undre gräns lower bound utlopp sink verifierbar verifiable övre gräns upper bound