u1 Flashcards Preview

m269 > u1 > Flashcards

Flashcards in u1 Deck (10)
Loading flashcards...
1

computational problem

a problem that is expressed sufficiently precisely that it is possible to attempt to build an algorithm to solve it

2

algorithm

a solution to a problemthat consists of a precisely stated, step-by-step list of instructions.

3

computable

if it is possible to build an algorithm that solves in a finite number of steps every instance of the problem that might arise

4

decidable

decision problem that is computable

5

effective procedure

If a decision problem is decidable then an algorithm exists which solves every instance of that problem: such an algorithm is called an effective procedure

6

abstraction

a simplification, with irrelevant details removed.

7

abstraction as modelling,

Model->ignores detail of->part of reality
Reality->modelled by-> model

8

abstraction as encapsulation

Implementation-> hides detail from->Interface
Interface->Depends on-> implementation.
the interface is the layer users interact with
the implementation is the layer that implements the model

9

abstract data type

a logical description of the data used to solve a problem. An ADT is a description of a data structure purely in terms of the operations that can be carried out on it.AnADT provides an encapsulation of the data;the datais hidden inside the ADTcan only be accessed through the operations it offers —its interface

10

data structure

When an ADT is implemented