Paper 2 Flashcards
(17 cards)
Describe a depth-first search
- goes to left node when it can
- if there is no left child it goes to the right child
- when there are no child nodes the algorithm visits it and backtracks to the parent node
- uses a stack
Describe a breadth first search
- visits all nodes connected directly to start node
- visits all nodes directly connected to each of those nodes
- uses a queue
What is a computable problem?
A problem that can be solved using an algorithm within a finite, realistic amount of time
What are the limits to algorithms ?
- processing power
- processing speed
- memory size
- time
What is a tractable problem?
A problem that can be solved in polynomial time or better (n^2)
What is the purpose of abstraction and decomposition?
To simplify the complexity of a problem
Define enumeration
Designing an algorithm that performs an exhaustive search and attempts all possible solution until the correct one is found
Define a theoretical approach
Problems that can be easily represented using mathematical equations
Define simulation
designing a model of a real system in attempt to understand its behaviour
define automation
building problem-solving models and putting them into action
define performance modelling
process of approximating how well models perform using mathematics
Describe he benefits of performance modelling
- inexpensive
- safe
- less time consuming
define pipelining
splitting a large task into manageable chunks and overlapping these small processes to speed up the overall process
define visualisation
Creating a mental image of what a program will do or how it will work
what is the benefit of visualisation
helps identify trends that were not otherwise obvious
define data mining
analysing vast amounts of data gathered from a variety of sources to discover new information and trends
define heuristics
an approach to solving problems that allow us to make use of our experience to find a solution that can be considered good enough
