Computational methods
No description yet. This curated deck is ready for daily study.
Card preview (19)
What is meany by a computable problem?
A problem that can be solved using an algorithm
Give 3 limiting factors to computable problems
• Processing power • Processor speed • Computer memory • Time
State 2 factors which may be considered during the problem definition phase
• Strengths and weaknesses of current solution - Volume/type/frequency/nature of: inputs, outputs, stored data
What is the name given to the process in which problems are continually broken down until each subproblem can be represented as a subroutine?
Problem decomposition
State 2 purposes of problem decomposition
• Identify sections which can make use of pre-coded modules or libraries • Save time coding • Simplify project management • Simplify testing and maintenance • Faster project delivery • Develop sections in parallel
Describe how the divide and conquer technique works
• The problem size if halved with every iteration • Each individual subproblem is then solved recursively • The solutions to the subproblems are then recombined to form the final solution to the problem
Give 2 applications of divide and conquer
• Merge sort • Binary search • Quick sort
Which programming construct do many problems solve using divide and conquer use?
Recursion
What is representational abstraction?
A computational technique in which excessive details are removed to simplify a problem
What type of abstraction is used to group together sections of the problem based on their functionality?
Abstraction by generalisation
State 2 problem solving techniques
• Backtracking • Data mining • Abstraction • Divide and conquer • Visualisation • Performance modelling • Pipelining
What is meant by heuristics?
Heuristics are a non-optimal, ‘rule-of-thumb’ approach to problem-solving which are used to find an approximate solution to a problem when the standard solution is unreasonably time-consuming or resource-intensive to find
What is meant by performance modelling?
• Provides mathematical methods to test a variety of loads on different operating systems • Performance modelling provides a cheaper, less time-consuming, safer method of testing applications
Describe how backtracking works
• The backtracking algorithm works by methodically visiting each path and building a solution based on the paths found to be correct • If a path is found to be invalid at any point. it backtracks to the previous stage and visits an alternate path
When might heuristics be used in problem-solving?
When the standard way to solve the problem is unreasonably time-consuming or resource-intensive
State 2 advantages of using performance modelling
• Safe • Relatively inexpensive • Less time-consuming
What is pipelining?
• A process in which tasks are developed in parallel - The output of one process in pipelining becomes the input of another, resembling a production line
What is the name given to the technique used to identify patterns and trends in large sets of data?
Data mining
What is meany by data mining?
• Data mining is a technique used to identify patterns or outliers in large sets of data, termed big data • Data mining is used in software designed to spot trends or identify correlations between data which are not immediately obvious