4.4.1 Theory of Computation Flashcards
What are the strategies for Problem Solving?
1) Exhaustive Search: Going through every possible combination until the problem is solved
2) Divide and Conquer: Splitting up the problem into the middle and other sections and solving off size
Define Algorithm?
A sequence of steps that can be followed to complete a task and that always terminates
What is Abstraction by Generalisation?
Simplifying by grouping common characteristics of a problem together to arrive at a hierarchical relationship
What is Representational abstraction?
Simplifying a problem by only taking into consideration necessary details required to obtain a solution leaving a representation without any unnecessary details
What is Information Hiding?
1) The Process of hiding all details of an object that do not contribute to its essential characteristics
What is Procedural abstraction?
1) Simplifying a problem by breaking it down into a series of procedures or subroutines that are generalised with variable parameters
What is Functional abstraction?
1) A mapping from one set of values to another, the result of this mapping is unique to a given set of inputs and a value must always be returned
What is Data Abstraction?
1) Data abstraction is the isolation of how a compounds data object is used from the details of how it is constructed
2) E.g. Stack implemented as an array and a pointer for the top of the stack
What is Problem reduction?
1) Removing the details until the problem is represented in a way that is possible to solve
What is Procedural Decomposition?
1) Breaking down a problem into a number of sub-problems each of which performs an identifiable task
2) These identifiable tasks can be further subdivided
How can Procedural Decomposition be achieved?
1) Top-down Problem: Look at a problem as a whole and break down its components systematically until you reach the basic building blocks of the solution
2) Divide and Conquer: Recursion is used to repeatedly divide or ‘unfold’ a task into subtasks until an easy task is produced
What is Composition?
1) Combining procedures to form compound procedures or combining objects to form compound data such as records, trees, lists etc
2) Compound data primitives can be combined to form compound data structures
What is Automation?
1) The process of taking a model (abstraction of real-world objects) and implementing a solution to solve problems
How can Automation be carried out?
1) Creating Algorithms
2) Implementing Algorithms
3) Implementing the models in data structures
4) Executing code
