3-1-5 Intractable Problems

Types of Problems:

• (1) Algorithmic & (2) Non-Algorithmic

(1) These can be solved using rules or a series of steps. e.g. baking a cake
(2) These cannot be solved using rules or a series of steps. e.g. who would win in a fight between batman and superman

• (1) Finite & (2) Infinite

(1) Finite set of inputs and are solvable.
(2) Infinite set of inputs and are not necessarily solvable.

• (1) Computable & (2) Non-Computable

(1) Where there is an algorithm to solve a computer-based problem. e.g. Can we work out if an arbitrary set of patterned tiles can be used to tile a floor?
(2) Where there is not an algorithm that exists that can solve a computer-based problem.

• (1) Decidable & (2) Undecidable

(1) A decision problem that has a Yes/No answer.
(2) A decision problem that is non-computable. e.g. "This statement is false."

• (1) Tractable & (2) Intractable

(1) A problem that has a reasonable (Polynomial) time solution as the size of the inputs increases. e.g. add up a row of numbers.
(2) A problem for which no reasonable (Polynomial) time solution has been found. e.g. Travelling Salesman Problem.

Heuristic Approach
This uses the know-how and experience to make guesses which help solve an intractable algorithmic problem in reasonable (polynomial) time. e.g. 'common sense'

3-1-4 Turing Machine

A Turing machine is an FSM that controls one or more tapes, where at least one tape is of unbounded length (i.e. infinitely long)

Background

• In the early twentieth century, mathematicians were trying to find a universal machine – a mathematical model that consisted of a small number of basic operations and a machine that could perform all these operations.
• The machine would then be able to run any algorithm.
• This model would be a precise definition of the term algorithm. The hope was to find algorithms that would be able to solve all mathematical problems.

 Solvable and unsolvable problems

• Alan Turing was a British Mathematician who, in 1936, wrote a paper called ‘On Computable Numbers’.
• This paper introduced the concept of the Turing machine – a universal machine capable of solving any problem that can be represented algorithmically.
• He used his machine to show that it is not possible to determine if any given problem has a solution, or not. This has serious implications in computing. It means that it may not always be possible to determine if a particular problem is unsolvable, or if it has just not been solved yet.

Turing Machine

• It consisted of:

1. An input alphabet.
2. A tape that is infinitely long.
3. An output alphabet that can be printed on the tape.
4. A tape head that is used to read/write to the cells.
5. A finite set of states, including a start state.
6. A program (set of instructions)

• A Turing machine describes an algorithm.
• A computer uses a computer program that is basically an algorithm.
• Turing machines therefore can be used to run and look at algorithms independent of the architecture of a particular machine.
• An algorithm running on a particular machine will have had to make decisions about how to store values (e.g. the precision of how to store a real number).
• This does not happen on a Turing machine, meaning a Turing machine is a more general representation of the algorithm.

Transition Rules for a Turing Machine

Overview of a Turing Machine

3-1-3 Finite Machines

A Finite State Machine accepts input and processes output.

Examples:

• Traffic Light Control Systems
• Specifiying Computer Language
• Programs for Spell Checking
• Networking Protocols

State Transition Diagrams is used to show a FSM as a picture. Like this:

Finite State Automata (FSA) has a finishing state and only produces yes or no outputs based on the final state.

State 2 is a yes and any other state is a no.

FSM's with outputs:

• Mealy Machine - output on transitions (arrow)

0|A     Input = 0     Output = A

• Moore Machine - output on states (nodes)

C is an output on state 1.

There are two ways to show transitions and states in a FSM.

•  Transition Table - shows transitions and states in table format 



 

• Transition Function - shows transitions and states as a series of functions.

(Input symbol, Current state) -> (Output symbol, Next state)

Deterministic FSA - one and only transition for each input.
Non-Deterministic FSA - multiple transitions for an input.
Halting state - a state with no outputs.
Trigger - input which triggers an action.

3-1-2 Comparing Algorithms

Problems with different time complexities

• Constant Complexity O(1) - takes the same amount of time no matter how big the problem is. (Sort the first ten records in file)
• Linear Complexity O(n) - as the size of the problem increases, the time taken to solve the problem grows at the same rate. (Cutting the grass)
• Logarithmic Complexity O(log n) - as the size of the problem grows, the time taken to solve it grows faster, but can be solved in a reasonable amount of time, but a slower rate. (Binary Search)
• Polynomial Complexity O(n^k) - as the size of the problem grows, the time taken to solve it grows faster, but can be solved in a reasonable amount of time. (Shaking hands with everyone in a room)
• Exponential Complexity O(k^n) - as the size of the problem grows, the time taken to solve it grows by larger and larger amounts. Only small size versions of these problems can be solved in a reasonable amount of time. (Emperor's chess board problem)
• Factorial Complexity O(n!) - even worse than exponential, cannot be solved in a reasonable time. (The travelling salesman problem)

Graph of the different time complexities

Key Terms:

Algorithm: a sequence of unambiguous instructions for solving a problem.

Computational complexity of an algorithm: measures how economical the algorithm is with time and space.

Time complexity of an algorithm: indicates how fast an algorithm runs.

Space complexity of an algorithm: indicates how much memory an algorithm needs.

Complexity of a problem: taken to be the worst-case complexity of the most efficient algorithm which solves the problem.

Basic operation: the operation contributing the most to the total running time.

Order of growth: assesses by what factor execution time increases when the size of the input is increased.

Asymptotic behaviour of f: the behaviour of the function f(n) for the very large values of n.

O(g): called big O of g, represents the class of functions that grow no faster than g.

Order of complexity: of a problem is its big O complexity.

3-1-1 Information Hiding and Abstraction

Hiding the design complexity of a system to simplify it for a user.

Levels of Abstraction

1. Application (Word)
2. High Level Programming Language
3. Machine Code
4. Electronics

Examples of Abstraction


• This does not show the actual distance from different stops on the underground.
• It only shows train stops and nothing else, e.g. road maps or landmarks.
• Some stops are not actually a straight line.



















The human brain is an exceptional piece of biological machinery capable of recognising objects when most of their detail has been removed. In this case it is a dachshund (weiner dog).

 
Key Terms

Interface: a boundary between the implementation of a system and the world that uses it. It provides an abstraction of the entity behind the boundary thus separating the methods of eternal communication from internal operation

Abstraction: representation that is arrived by removing unnecessary details.

Information hiding means hiding design details behind a standard interface.

There are several reasons for information hiding. Different objects can have identical interfaces. Sharing a common interface among many different objects means that users of the objects do not need to be retrained when changing from using one object to using another. To use a module or object, a user needs to have no knowledge of its internal design. The internal design can be kept secret. One moudle may be replaced by another module with an identical interface but a different internal design or manner in which the module's function is carried out. Changes are made easier because changes are local to modules.

Find a common representation of a problem, then find an algorithm to solve problems so represented. Learn to transform other problems into this representation.