what is a computable problem?
a problem where an algorithm can solve every instance of it in a finite number of steps in a realistic amount of time
eg. cracking a 10 character secure password is theoretically possible but would take millions of years so its incomputable
what is exhaustive search?
trying all possible solutions until the correct one is found - very inefficient (exponential time increase)
what is simulation?
the process of designing a model of a real system in order to understand the behaviour of the system and to evaluate various strategies for its operations
what kinds of problems might simulation be used for?
- financial risk analysis
- population predictions
- queueing problems
- climate change predictions
- engineering design problems
- physical models of spacecraft, ships, wind turbines, etc.
what is top-down design?
breaking a large task down into several smaller tasks, which are again broken down until each one is a small manageable subtask
why is problem decomposition so important?
- reduces complexity of the problem
- saves time coding + testing by finding parts that can use pre-coded modules/libraries
- easier to manage project
- different teams code different parts of the project in parallel - faster delivery
- modules are individually designed, developed, tested before being put together
- easier to identify, locate + mitigate errors
what is divide and conquer?
an algorithm that works by recursively breaking down a problem into 2 or more subproblems of the same type , until these become simple enough to be solved directly
eg. binary search, merge sort, quick sort
what are the stages of a divide and conquer algorithm?
- divide - halving the size of the problem every iteration
- conquer - solve each problem individually (recursively)
- merge - recombine solutions to subproblems to form final solution
what are the advantages of divide and conquer?
- problem size halves each iteration - simplifies very complex problems
- time complexity O(log n)
what are the disadvantages of divide and conquer?
- recursive - stack overflow will cause program to crash
- large problems - difficult to trace
what is representational abstraction?
when excessive details are removed to simplify a problem
often reduced down until it forms problems that have already been solved
why is abstraction useful?
- focus on core aspects of program not unnecessary details
- levels of abstraction break down large complex problem into simpler components
- different teams deal with different components + details about other layers are hidden - more manageable
how does abstraction by generalisation helps?
- group together different sections of problem with similar underlying functionality
- saves time - they can be coded together + reused
what is automation?
building and putting into action models to solve problems - can tell you more about the reality you are modelling
what is visualisation and why is it useful?
- presenting data in a way that is easier for humans to understand
- can help identify trends that were not otherwise obvious
- eg. graphs, trees, charts, tables
- can be used by businesses to pick up on patterns to inform business decisions
what is backtracking?
following one solution and following it until you find that it is not the solution that you want and returning to an earlier point and start looking again
eg. a maze
what is data mining?
- the process of collecting + analysing huge amounts of data
- many organisations collect millions of bytes of data about people
- this is then analysed to find connections + associations
- lots of modelling techniques are used to help identify patterns in the data
what are some applications of data mining?
- increasing the response rate to marketing campaigns by being able to target them more accurately to the needs of each customer
- anticipating resource demand
- detecting fraud + cybersecurity issues
- finding connections between seemingly unconnected events
what is big data?
- huge amounts of data that are collected + stored - linked to data mining
- defined by the 3 Vs - volume, variety, velocity
what considerations are required for data mining?
- handles personal data - should be dealt with current data protection legislation eg. GDPR within the EU
what are intractable problems?
although an algorithm would exist for a solution, it would take an unreasonably long amount of time to find the solution
eg. the Travelling Salesman Problem
what is a brute force method?
it is where every combination of routes or solutions to a problem are tested out until the right one is found
what is a heuristic method?
non optimal rule of thumb approach to problem solving, used to find an approximate solution to a problem where the standard solution is unreasonably time consuming or resource intensive to find - not perfectly complete or accurate but quick and good enough
what are some applications of the heuristic method?
- using a familiar route from A to B even if it isnt the most efficient
- selecting a job candidate based on 2 or 3 factors and ignoring other potentially relevant ones
- building circuit boards
- virus checking
- routing messages across the internet
- DNA analysis
- AI
-
Components of a computer58
-
Systems Software82
-
Data Types46
-
Software development39
-
Types of programming languages48
-
Data Structures66
-
Databases68
-
Compression, encryption and hashing33
-
Boolean algebra18
-
Networks62
-
Legal, moral, cultural and ethical issues1
-
Programming techniques52
-
Computational thinking51
-
Computational methods29
-
Algorithms22
-
Computer related legislation13
-
Web technologies32
