problem recognition Flashcards
computable problems
a problem where there is an ALGORITHM that can solve EVERY instance of it within a FINITE number of steps (can be theoretically solvable but practically unsolvable/insoluble if takes millions of yrs to solve)
ways of problem solving
enumeration
simulation
theoretical approach
creative solution
enumeration
solve problems by exhaustive search (eg finding owner of DNA in database) - trying all possible solutions. Once insoluble are now soluble bc power of computers. BUT inefficient, and as size of problem inc, number of poss solutions inc exponentially. eg magic squares
simulation
process of designing a model for a real system to understand the behaviour of the system and evaluate various strategies for its operation. Model used to evaluate performance or test outcomes.
problems for simulation
financial risk analysis population predictions climate change predictions queue problems engineering design problems
abstraction in simulation
removes unnecessary details, reducing problems to essentials
eg of queuing problems
number of queues on toll roads, or checkouts at supermarkets or number of people on helplines for software support
simulation: real life models
build physical model of eg spacecraft to study behaviour. When impractical, dangerous, expensive to do tests on real thing. Used to evaluate performance and test outcomes
strategies for problem solving
top down design: good for breaking down into small, manageable subtasks
divide and conquer: technique that reduces size of problem with every iteration eg binary search (halves problem with each iteration), not always as fast as binary search
problem abstraction
problem abstraction
removing details until problem is represented in a way that it is possible to solve because reduced to one that has already been solved
graph unfolding
a method of solving a problem: eg for knights problem on p279, number squares then draw node graphs with edges to all possible moves. then open it up to a circle
eg the knights problem is a …
REDUCTION to a more general problem that has already been solved in the same way
automation
building and putting into action models to solve problems. Includes: what are you gonna put in the model and what assumptions you are going to make, create and implement algorithms, execute and test results
automating the abstraction
tells us more about the reality we are modelling/physical scenario
physical world scenario–> mathematical model
abstraction is created
mathematical model is automated to
an automaton
automaton tells us more about
physical world scenario
important factor in finding a solution to a problem
visualisation of algorithms: how problem is presented eg computers work with binary numbers but humans prefer visual images
eg of visualisation
binary tree flow diagram vs data in a table, a map, graph
backtracking
methodical way of trying out different sequences until you find one that leads to a solution. go as far down one route as possible before backtracking to last decision point and go down next route as far as possible again.
when is backtracking used
when you don’t have enough info to know which is the best choice
when each decision leads to a new set of choices
one or more of the sequences may be a new solution to the problem
eg backtracking
mazes, depth first traversal of a graph
big data
large sets of data that cannot be easily handled in a traditional database
data mining
process of digging through big data sets to discover hidden connections and predict future trends: often involving the use of different kinds of software packages eg analytical tools
intractable problems
although an algorithm may exist for their solution, the program may take an unreasonable amount of time to find the optimal solution eg Travelling Salesman Problem
TSP and applica\tions
Given a list of towns and distances between each pair, what is the shortest possible route that the salesman can use to visit each town exactly once and return to the starting point: planning, logistics, manufacture of microchips and DNA sequencing
TSP: num of possible routes with 5 cities. number you’d examine by brute force
4!
methods to solve intractable problems
brute force: inefficient
finding an approximate answer or finding a solution with a high probability of being correct or solving simpler/restricted versions to give insights into possible solutions
heuristic solution
employs an algorithm not guaranteed to be optimal or perfect or accurate, but is sufficient for the purpose and is completed in a reasonable time frame.
performance modelling
process of simulating different user and system loads on a computer using a mathematical approximation, rather than actual performance testing (e.g. expensive and difficult.) Output from performance model can then be used to help plan a new system suited to the requirements of an organisation.
e.g. of performance modelling
test performance of a network under different conditons
