Problem Solving

HideShow resource information
Abstraction
Simplifying a problem to omit all unnecessary details
1 of 26
Information Hiding
Hiding the complexities of the system behind a simple to use interface
2 of 26
Interface
The boundary between the front end of a system and its impementation
3 of 26
Time Complexity
How long an algorithm takes to complete a task with a given input
4 of 26
Space complexitiy
How much memory an algoritm needs to complete a task with a given inpiut
5 of 26
Order of Growth
How quickly the complexitiy of a function grows with growth input size
6 of 26
Asymptotic behaviour
The behaviour of a function for a very large vaules of n
7 of 26
Non-computable
A problem that does not have an alogirthmic soluttion
8 of 26
Tractable
A problem that has a ploynomial time solution
9 of 26
Intractable
A problem for which no reasonable time solution has yet been found
10 of 26
Undecidable
A decision problem that is not computable
11 of 26
Heuristic solution
A trial and error approach using "informed guesses" or learned knowledge to find a solution to an intractable problem
12 of 26
Mealy Machine
A FSM that determines its outputs from the present state and inputs
13 of 26
Moore Machine
A FSM that determines its outputs fromt the present state only
14 of 26
Determinisitc FSM
Each state has a unique trigger for every transition
15 of 26
Finite Sate Automatron FSA
FSM only output TRUE or FALSE
16 of 26
Principle of Universality
A universal machine is a machine of capable of simulating any other machine
17 of 26
Equivalent Turing Machine
All other types of computing machine are reducible to an equivalent Turing Machine
18 of 26
Power of a Turing Machine
No Physical computing device can be more powerful than a Turing machine. If a Turing machine cannot solve a desision problem, nor can any physical computing device
19 of 26
Natural Language
A real spoken and written language with grammar or syntax rules and ambiguities, such as English and French
20 of 26
Formal Language
A language defined by an ALPHABET and RULES OF SYNTAX
21 of 26
Regular Language
Any language that an FSM will accept
22 of 26
The Travelling Salesman Problem
Intractable problem - Shortested distance between a number of nodes
23 of 26
The Halting Problem
Non-computable - Is it possible to create a program which takes a program as an input and determines if the program will halt or loop infinitely
24 of 26
Nondeterminsistic Finite Automaton NFA
Have two or more finish end states
25 of 26
Deterministic Finite Automaton DFA
All nodes end up going to the same end state
26 of 26

Other cards in this set

Card 2

Front

Hiding the complexities of the system behind a simple to use interface

Back

Information Hiding

Card 3

Front

The boundary between the front end of a system and its impementation

Back

Preview of the back of card 3

Card 4

Front

How long an algorithm takes to complete a task with a given input

Back

Preview of the back of card 4

Card 5

Front

How much memory an algoritm needs to complete a task with a given inpiut

Back

Preview of the back of card 5
View more cards

Comments

No comments have yet been made

Similar Computing resources:

See all Computing resources »See all Fundamentals of computer systems resources »