1.5 Intractable Problems
Types of Problems
We know that some problems can be solved using algorithms and some can’t.
Variety of different types of problem:
• Algorithmic & Non-Algorithmic,
• Finite & Infinite,
• Computable & Non-Computable,
• Decidable & Undecidable,
• Tractable & Intractable.
Algorithmic Problems
· These can be solved using rules or a series of steps.
· For example; making a cake
Non-Algorithmic Problems
· These cannot be solved using rules or a series of steps.
· For example – who would win in a fight between Batman and Superman?
Algorithmic Problems can be divided into…
FINITE PROBLEMS
• Finite set of inputs and are SOLVABLE.
INFINITE PROBLEMS
• Infinite set of inputs and are NOT NECESSARILY SOLVABLE.
Non-Computable Problem
- A problem that has no algorithm to solve it. Not possible to compute.
More Problem Types
Decision Problems
• a Yes/No Algorithmic Problem
Decidable Problems
• a Decision Problem that has a Yes/No Answer.
Undecidable Problems
• a Decision type Algorithmic Problem that is Non-Computable
Example –
‘This Statement is False’
• This statement is Contradictory therefore it is Undecidable!
Tractable Problems
• A problem that has a reasonable (Polynomial) time solution as the size of the inputs increases.
• Example – add up a row of numbers.
Intractable Problems
• A problem for which no reasonable (Polynomial) time solution has been found.
• Example – Travelling Salesman Problem.
The Heuristic Approach
The Heuristic Approach uses know-how and experience to make guesses which help solve an Intractable Algorithmic Problem in reasonable (Polynomial) time.
The ‘Common Sense’ Approach
A variety of different types of problems:
• Algorithmic & Non-Algorithmic,
• Finite & Infinite,
• Computable & Non-Computable,
• Decidable & Undecidable,
• Tractable & Intractable.
No comments:
Post a Comment