2.2.2 Computational Methods Flashcards
What is a computational problem?
A problem that has an algorithm that can solve it in a finite number of steps
When is a problem theoretically unsolvable?
When the problem can technically be solved but it would take so long that it would make no practical sense.
e.g. brute forcing a 10 character password will take too long to get any benefit from it.
What methods can be used to solve a problem?
Decomposition.
Abstraction.
Calculations.
Storage of Data.
Enumeration.
What is enumeration?
Trying all possible solutions to a problem until the correct one is found - bruteforce
What is Divide and Conquer?
A way of reducing the number of possibilities each iteration.
How does Divide and Conquer work?
Splitting the data set into two (dividing) with each iteration. This happens until the problem is decomposed.
Then each subroutine is solved (conquered).
The solutions to all the problems are then recombined in the merge stage to form the final product.
What is problem recognition?
Working out what the actual problem is.
Stakeholders typically give requirements of the finished product and the inputs and outputs needed. You have to work out the problem at hand.
What is problem decomposition?
Breaking down the problem into smaller problems. This continues until each sub problem can be represented as a self contained sub-routine.
Where is Divide and Conquer used?
Problems where the problem can be reduced by half at every iteration.
e.g. binary search
How is divide and conquer used in binary search?
The middle value of the sorted list is compared to the value to be found. If it is less, then you know to look to the right. If it is more then you know to look to the left.
The other half of the list is discarded.
This repeats until the item is found, or there is one item left - not the one to be found - so the item isn’t in the list.
What is the advantage of using Divide and Conquer?
The size of the problem is halved with each iteration. This greatly simplifies complex problems.
What strategies can be used to solve problems?
Backtracking.
Data Mining.
Heuristics.
Performance Modeling.
Pipelining.
Visualisation.
What is backtracking?
Going so far down a certain route and then backtracking to see if there is a better route. It works methodically, visiting each path and and building a solution based on the paths found to be correct. If an incorrect path is found it goes back to the previous stage and goes down a different path.
e.g. Depth-first-Search
How can backtracking be visualised?
A maze.
Follow each path until you cant any more. Backtrack to the last point that a decision could be made and go down a different path.
What is Data Mining?
Analysing large volumes of data (Big Data) in order to establish; Patterns, Trends, Successes, Problems and solutions to the problems.
