2.2.2 Flashcards
features of a problem
First step of a problem is identifying whether a problem can be solved using computational methods.
Problems called computable if they can be solved within a finite, realistic amount of time, consist of inputs, outputs and calculations.
computational methods
problem rec
problem dec
divide and conquer
abstraction
problem recognition
Identify there is a problem to be solved // what the problem is
There may be requirements when defining a problem:
- Analysing strengths and weaknesses with the current way this problem is being solved
- Considering types of data involved including inputs, outputs, stored data and amount of data
Example
Road junction with traffic lights, algorithm work fine with traffic lights but there is traffic, a problem that requires attention.
Variables:
We could change the algorithm for traffic lights to alter their timings
Add extra lanes
Build a bypass around the area to ease traffic.
problem decomposition
Splitting down a problem into sub-problem
This continues until each subproblem can be represented as a self-contained subroutine.
Aims to reduce the complexity of the problem by splitting it up into smaller sections which are easier to understand.
ADV:
By identifying subproblems, programmers may find that certain sections of the program can be implemented using pre-coded modules or libraries which saves time.
Makes the project easier to manage, as different software development teams can be assigned separate sections of the code according to their specialisms.
Enables multiple parts of the project to be developed in parallel, making it possible to deliver projects faster.
This technique makes debugging simpler and less-time consuming, as it is easier to identify, locate and mitigate errors in individual modules.
Without problem decomposition, testing can only be carried out once the entire application has been produced therefore making it hard to pinpoint errors.
divide and conquer
Problem-solving technique that reduces size of a problem with each successive iteration, can be broken down into three parts: divide, conquer and merge.
1. Take a problem, or data set
2. Apply some rules
3. Based on the outcome of those rules, discard any data that doesn’t match
4. Repeat the process with the data that is left
‘Divide’ involves halving the size of the problem with every iteration. Each individual subproblem is solved in the ‘Conquer’ stage, often recursively. The solutions to the subproblems are then recombined during the ‘Merge’ stage to form the final solution to the problem
(this is a recap of how binary works, so no, its not necessary to learn here but is in 2.3 as well)
One common use of divide and conquer is in binary search, in which the middle value of the sorted list to be searched is compared to the value to be found. If this value is smaller than the search value, the lower half of the list is discarded and the upper half of the list is recursively searched using the same technique: the midpoint is found and half of the list is discarded. If the middle value is found to be larger than the search value, the upper half of the list is discarded and the lower half is recursively searched. This continues until either the search value is found or the list is broken down until it contains one element, which means that the value does not exist in the list.
ADV:
The size of the problem is halved with each iteration which simplifies complex problems. This means that as the size of a problem grows, the time taken to solve it will not grow as significantly.
DIS:
As divide and conquer mostly makes use of recursion, it faces the problem: stack overflow will cause the program to crash and large programs are very difficult to trace.
backtracking
The process of incrementally building towards a solution, abandoning partial success when the solution can’t be completed and going back to a previously successful match.
Depth-first graph traversals are an example of backtracking.
Advantages: It is a step-by-step representation of a solution to a problem = very easy to understand.
easy to write the code, and also to debug.
Disadvantages: slow compared to other solutions, possibility to perform a very large search with Backtracking and at the end don’t find any match to your search, high computational cost, Backtracking is a recursive algorithm that consumes a lot from the memory and from the processor.
use of abstraction
Abstraction is the process of separating ideas from reality, hiding unnecessary detail and only showing those important in that context.
Often, problems may be reduced down until they form problems that have already been solved which allows pre-programmed modules and libraries to be used rather than coding from scratch.
- allows programmers to focus on the core aspects required of the solution rather than worrying about unnecessary details.
- Using levels of abstraction allows a large, complex project and its functionality to be split up into simpler component parts.
- Individual components can then be dealt with by different teams, with details about other layers being hidden. This technique makes projects more manageable.
- Abstraction by generalisation may also be used to group together different sections of the problem with similar underlying functionality. This allows for segments to be coded together and reused, so saves time.
data mining
Data mining searches large amounts of data turning it into useful info, searches for relationships between
facts/components/events that may not be obvious and finds patterns
* May include pattern matching
algorithms
* May involve anomaly detection algorithms
* Used for business modelling
* Used to plan for future eventualities
ADV:
-useful tool in assisting business and marketing decisions, to increase profits.
-may uncover which products are bought at certain points of the year and this information can help shops prepare enough stock in advance.
- used to reveal insights about people’s shopping habits and preferences based on their personal information. insights can be used to inform marketing techniques.
Can use to introduce new features
* Increase use from users
* Increase revenue by selling features
used more often
* Make the game more appealing
* Remove features people don’t use
* Use to target advertising
DIS:
involves handling of personal data, it is crucial dealt with in accordance with the present legislation regarding data protection.
* Privacy concerns from users
* Misuse of information
how can data mining be used
Identify customer trends: To identify items to sell/offers to send customers
Which items are not selling well
To replace them with other items
heuristics
Approach to solving problems that allow or encourage us to make use of our experience and find a solution that can be considered good enough, non-optimal, used to find an approximate solution to a problem when the standard solution is unreasonably time-consuming or resource-intensive to find. Rule of thumb.
The solution found is not perfectly accurate or complete; however, the focus is on finding a quick solution that is ‘good enough’ and heuristics provide a shortcut to this.
- Used to provide an estimated solution for intractable problems such the A* algorithm.
performance modelling
Simulate/test the behaviour of the system before it is used
Eliminates the need for true performance testing by providing mathematical methods to test a variety of loads on different operating systems.
- provides a cheaper, less time-consuming or safer method of testing applications. This is useful for safety-critical computer systems, such as those used on an airplane, where it is not safe to do a real trial run before the system can be implemented.
- The results of performance modelling can help companies judge the capabilities of a system, how it will cope in different environments and assess whether it is safe to implement.
how can performance modelling be used
Testing it with a large number of simultaneous orders
Testing it with a large number of
customers/items/orders
visualising
Allows us to create a mental image of what the program will look like/work as. Data can be presented in a way that is easier for us to understand using visualisation.
- This makes it possible to identify trends that were not otherwise obvious, particularly amongst statistical data.
- Depending on the type of data, data may be represented as graphs, trees, charts and tables.
- Technique that is used by businesses to pick up on patterns which can be used to inform business decisions.
Visualisations present the information in a simpler
form to understand
Visualisations can best explain complex situation
pipelining
Pipelining is a process that allows for projects to be
delivered faster, as modules are divided into individual
tasks, with different tasks being developed in parallel.
Traditionally, the output of one process in pipelining
becomes the input of another, resembling a production line.
concurrent processing
- Multiple processes being executed at the same time // appearing to happen simultaneously
- Giving processes a slice of the processor time
- Having multiple processors each carrying out a different process
adv: could have large number of requests to the server at a time … server needs to respond in reasonable time - … having multiple processors handling the different requests would increase response
time - Users could override each other’s changes
- … e.g. needs to handle if someone updates their circus while someone else is visiting
- …use record locking to stop edits if someone else has access to data
- Different users will have different response times
- …therefore the processor can still handle other requests
- …so that the performance for other users is not affected
