u1 Flashcards
computational problem
a problem that is expressed sufficiently precisely that it is possible to attempt to build an algorithm to solve it
algorithm
a solution to a problemthat consists of a precisely stated, step-by-step list of instructions.
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
decidable
decision problem that is computable
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
abstraction
a simplification, with irrelevant details removed.
abstraction as modelling,
Model->ignores detail of->part of reality
Reality->modelled by-> model
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
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
data structure
When an ADT is implemented