222-computational-methods Flashcards
Computational thinking
- The ability to think systematically about a problem and apply techniques for solving it
- techniques: data mining, heuristics, visualisation, backtracking, pipelining, performance modelling
data mining
- looks through vast quantities of unconnected data, finding a correlation between data that may not be obvious
- There may no predetermined matching criteria
- Pattern matching algorithms/brute force approach possible with high speed computers/ big data analysis software
- parallel processing to speed up
data mining applications
- increasing response rates/sales/profits
- improve marking
- target more accurately to customer needs
- anticipating resource demands
- detecting fraud and cybersecurity issues
-finding hidden connections between seemingly unconnected events, - predict n plan future trends/events
- used for business modelling
Limitations of data mining -
- powerful computers and vast processing requirements
- privacy concerns, personal data, GDPR, transparency, consent
- misuse
- inaccurate information can produce false results
- bias
Challenges in producing a solution to a computational problem
- algorithm must be correct and work for all possible inputs
- algorithm must be efficient
- algorithm can solve it within finite steps in realistic time
- limitations: hardware, memory & time requirement, big o complexity
Programming standards why
for modules to be reusable they need to conform to these so it’s easy to use for other programmers + maintainability
Programming standards what
- naming conventions: consistent, understandable names. Easier for developers to know their purpose, and reduce chance of duplication (reusing). camel Case variables, Pascal Case classes, upper case constants
- clear documentation: preconditions, classes and functions expected behaviour comments, explain nonobvious logic
- code length: function no longer than a page: reduce complexity, focused, manageable
- each function single-entry points with exit point: consistent starting execution (e.g if statement making it nest start at different places violates), and not premature/inconsistent multiple points of return e.g return in loops
- Restrict variable scope - avoid global, local isolation
Backtracking when
- each decision leads to new choices (generation)
- more than one sequence could be a solution (combinations & permutations, crosswords, puzzles)
- pathfinding (maze)
- uncertainity on optimal (maximise/minimise, allocation, exploration)
- searching/traversing (graphs/trees)
- predict outcomes (games)
- constraint satisfication (sudoku)
Backtracking
recursive algorithm.
takes one path as far as possible. when node does not have any nodes to visit (dead end)/ abandons each partial success if determined that it cant be completed
returns to previous node (decision point) and checks for further nodes to visit/aternative solution
- Repeats until solution is found.
- suitable for route problems, depth first search
Returning to a previously successful result to find an alternative solution
Abandons each partial success as soon as it determines that the partial solution cannot possibly be completed
- finds all (or some) solutions
Heuristics
- problem is complex to that perfect solution would be very difficult/impossible to find
- So can get a solution that is good enough, no guarantee of being most optimum for practical purposes
- purpose: Finding a reasonable solution in a reasonable time.
- may involve using extra knowledge to reduce time complexity
- approx solution to intraceable problems
Heuristics example
A* algorithm.
Crow’s path heuristic
- difficult to calculate all the possible routes from gas flow to London on a car sat nag so pathfinding algorithm is led in the general direction to save time and processing power. Or when crossing the road: don’t gather all data about vehicle speeds, we scan the data most likely to help us and make a judgement based on experience
performance modelling
- ## computational modelling (simulation) using mathematical approximation and data provided to test system behaviour (performance) and capabilities in scenarios/workloads-reduce extensive true performance testing reliance (expense, time, no loss, safer)
- testing how system will respond to normal (load), and heavy load (stress) and traffic/weaknesses/conditions
- validation, early error detection, risk management, resource allocation
enumeration algorithm
an algorithm that performs an exhaustive search, attempts all solutions until correct one is found
theoretical approach
representing a problem using mathematical equations
simulation
using computer system to model real life situation to attempt to understand its behaviour
makes use of abstraction
e.g climate change, financial risk analysis
