Unit 10 - Computational Thinking Flashcards
define computational thinking
‘the ability to think logically about a problem and apply techniques for solving it’
define abstraction
separating the logical and physical aspects of a problem
what is computer science
using mathematical principles to solve problems, learning to think computationally and applying the principles of abstraction
define abstraction by generalisation
the grouping by common charcateristics to arrive at a hierarchical relationship
when is abstraction by generalisation usually used
OOP - classes and sub-classes
define data abstraction
involves creating a representation for data that separates the interface from the implementation so a programmer or user only has to understand the interface, the commands to use, and not how the internal structure of the data is represented and/or implemented
when is data abstraction commonly used
high-level languages
define problem abstraction
involves removing details until the problem reduces to one which has already been solved
when is problem abstraction used
you need to use problem abstraction to remove details until the problem can be represented in a way that is possible to solve because it reduces to one that has already been solved. e.g. using a database. timetabling and schedules are very common problems with well-defined solutions.
what is modelling and simulation and why is it used
- building a model of a real world object or phenomenon may be used to help solve a particular problem
- computer scientists have to decide what details are relevant to the problem and discard anything else
- algorithms and data structures can then be designed to solve a problem
- the algorithm is then implemented in program code and executed
define procedural decomposition
means breaking a problem into several sub-problems, so that each sub-problem accomplishes an identifiable task. the sub-problems may themselves be further subdivided
what is the simple diagram that represents a computational problem
define input
the information relevant to the problem, which could for example be passed as parameters to a subroutine
define output
the solution to the problem, which could be passed back from a subroutine
advantages of identifying inputs and outputs
there is no ambiguity in what must be supplied to the sub-routine
what are the two major challenges in producing a solution to a computational problem
- the algorithm must be correct - it must work for all possible inputs
- the algorithm must be efficient - often, a problem involves huge amounts of data
define precondition
a condition that must be fulfilled before other things can happen or be done
advantages of specifying preconditions
- documentation - the user knows what checks must be carried out before calling the subroutine
- no preconditions - user can be confident that necessary checks will be carried out in the subroutine itself, thus saving unnecessary coding
- reusable subroutine
structure for thinking ahead situations
Name:
Inputs:
Outputs:
Preconditions:
define caching
the temporary storage of data and instructions
examples of data that is cached
last few instructions of a program to be executed, the result of an earlier computation, or data used may be stored in memory so they can be quickly retrieved
define web caching
storing HTML pages and images recently looked at
advantages of web caching
- faster access to cached resources
- saving on costly use of bandwidth
- reduced load on web services in a client-server environment
disadvantages of caching
- slower performance if the resource isn’t found in the cache
- being given a stale copy of a resource when an up-to-date copy is needed
- for example, you access a database to get a list of available products, which is then cached
- you make a few other queries, then a few minutes later you have to make your original query again
- if the query results have been cached, you may see the same available products… but in fact, they have already been sold in the meantime
define prefetching
the loading of a resource before it is required - to decrease the time waiting for that resource.
examples of prefetching
instruction prefetching where a CPU caches data and instruction blocks before they are executed, or a web browser requesting copies of commonly accessed web pages
what does prefetching use
cache
define procedural abstraction
using a procedure to carry out a sequence of steps for achieving some task
define procedure interface
how it is called, what arguments are required, what data type each one is and what order they must be written in
define structured programming
aims to improve the clarity and quality of a program. it is a method of writing a computer program which uses:
1. modularization for program structure and organisation
2. structured code for the individual modules
3. recursion
example of modularization for program structure and organisation
breaking the problem down into subroutines
define structured code
sequence, selection, iteration
define recursion
when a function calls itself
what is the top-down technique/design
breaking down a problem into the major tasks to be performed; each of these tasks is then further broken down into seperate subtasks, and so on until each subtask is sufficiently simple to be written as a self-contained module or subroutine
how does the hierarchy chart structure work
- each logical process is broken down into smaller components until it cannot be broken down any further
- execution takes place from left to right, always at lowest level component
- selection and iteration are not shown in a hierarchy chart
advantages of problem decomposition
- easier to write
- simpler to test and maintain
- modules are self-contained and well documented with inputs, outputs and preconditions specified so it is easy to change modules without affecting the rest of the program
what is a hierarchy chart
a tool for representing the structure of a program, showing how the modules relate to each other to form the complete solution
benefits of modularisation
- programs are more easily and quickly written
- programs are more reliable and have fewer errors
- programs take less time to test and debug
how is ‘programs are more easily and quickly written’ a benefit of modularisation
- large programs are broken down into subtasks/subroutines that are easier to program and manage
- each subroutine (i.e. module) can be individually tested
- modules can be re-used several times in a program
- frequently used modules can be saved in a library and used by other programs
- several programmers can simultaneously work on different modules development time
how is ‘programs are more reliable and have fewer errors’ a benefit of modularisation
it is easier to find errors in small self-contained modules
how is ‘programs take less time to test and debug ‘ a benefit of modularisation
- programs are easier to maintain
- a well-organised, modular program is easier to follow
- it is easier to find which module needs to be changed
- self-contained modules mean that the change should not affect the rest of the program
- new features may be added by adding new modules
examples of good programming practice
- use meaningful identifiers
- define and document the inputs, outputs and preconditions for each sub-procedure
- add lost of meaningful comments withing the program
- at the bottom level, each sub-procedure should perform a single task
- keep each sub-procedure self-contained by passing parameters and using local variables
what features make a good algorithm
- clear and precisely stated steps that produce the correct output for any set of valid inputs
- should allow for invalid inputs
- must always terminate
- execute efficiently, in as few steps as possible
- designed so that other people will be able to understand and modify it if necessary
what are the tools for designing algorithms
- hierarchy charts – useful for identifying the major task, and breaking down into subtasks
- flowcharts – useful for getting down initial ideas for individual subroutines
- pseudocode – will easily translate into program code
define hand-tracing algorithms
using a trace table to write down the contents of each variable as it changes during execution. if the program contains a loop, a helpful technique to put the loop condition as the first column in the trace table, even if the other variables have been defined before it.
what is hand-tracing algorithms useful for
figuring out how an algorithm works; finding out why an algorithm is not working properly
define parallel processing
requires multiple processors each executing different instrutions simultaenously, with the goal of speeding up computations. it is impossible on a single processor
- when more than one processor is executing separate instructions at the same time
define concurrent processing
takes place when several processes are running, with each in turn being given a slice of processor time. this gives the appearance that several tasks are being performed simultaneously, even though only one processor is being used
advantages of concurrent processing
- increased program throughput - the number of tasks completed in a given time is increased
- time that would be wasted by the processor waiting for the user to input data or look at the output is used on another task
disadvantages of concurrent processing
- if a large number of users are all trying to run programs, and some of these invove a lot of computation, these programs will take longer to complete
advantages of parallel processing
- parallel processors enable several tasks to be performed simultaneously by different processors. it can speed up processing enormously when repetitive calculations need to be performed on large amounts of data
- graphics processors can quickly render a 3-D object by working simultaneously on individual components of the graphic
- a browser can display several web pages in seperate windows and one processor may be carrying out a lengthy search or query while processing continues in other windows
disadvantages of parallel processing
- there is an overhead in coordinating the processors and some tasks may run faster with a single processor than the multiple processors
define problem recognition
the ability to recognise or acknowledge that an issue exists or that a situation needs attention in an existing process or program
what is a computable program
a problem where there is an algorithm that can solve every instance of it in a finite number of steps. some problems are theoretically computable, but if they take millions of years to solve, they are insolvable in a practical sense
what are the 4 methods of problem solving
- enumeration
- simulation
- theoretical approach
- creative solution
define enumeration
solving problems by exhaustive search - trying all possible solutions until one correct one is found
limiation of enumeration
inefficient - the number of possible solutions increases expenentially as the size of the problem increases
define 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 operation
examples of simulation
- financial risk analysis
- population predictions
- queueing problems
- climate change problems
- engineering design problems
how does simulating a system work
makes use of abstraction to reduce the problem to its essentails, removing all unnecessary details. it can also involve building a physical model so that its behaviour can be studied - useful hwn it would be too expensive, dangerous or impractical to carry out tests on the real thing. a model can be used to evaluate performance or test outcomes
what are the three strategies for problem solving
- divide and conquer
- problem abstraction
- automation
what is the ‘divide and conquer’ technique
reduces the size of the problem with every iteration
what is problem abstraction
involves removing details until the problem is represented in a way that it is possible to solve because it reduces to one that has already been solved
what is automation
deals with building and putting into action models to solve problems
what are the 5 solutions you can apply to a problem
- visualisation
- backtracking
- data mining
- heuristics
- performance modelling
- pipelining
what is visualisation
using an image to display the problem rather than a written description
what is backtracking
a methodical way of trying out different sequences until you find one that leads to the solution
what is data mining
the process of collecting and then analysing huge amounts of data. many organisations collect billions of bytes of data about people. they can then analyse or ‘mine’ the data to find connections and associations. a range of modelling techniques are used to help to identify patterns in data.
applications of data mining
- increasing response to marketing campaigns by being able to target them more accurately to the needs of the customer
- anticipating resource demands
- deleting fraud and cybersecurity crimes
- finding connections between unconnected events
define ‘big data’
it implies that huge amounts of data are collected and stored.
what is ‘big data’ defined by
it is defined by three major features, known as the 3Vs: Volume, Variety and Velocity
what type of computing is important when collecting ‘big data’
parallel computing
what is an intractable problem
although an algorithm may exist for their solution, it would take an unreasonably long to find the solution
what are heuristic methods
a heuristic method is used to rapidly find a solution that is ‘good enough’, even though it might not be the optimal solution
applications of heuristic methods
- routing messages across the Internet
- building circuit boards
- transportation
- virus checking
- DNA analysis
- artificial intelligence
what is performance modelling
the process of simulating different user and system loads on a computer using a mathematical approximation
disadvantage of performance modelling
expensive compared to performance testing
advantage of performance modelling
the output may then be used to help with planning a new system which is suited to the requirements of the organisation
what is big-O notation
this measures the suitability of algorithms in terms of execution time and space
what is pipelining
an implementation technique where tasks are split into smaller parts and then the processing of each task is overlapped. instructions enter the ‘pipeline’ at one end, and at each stage part of the instruction is completed and moves to the next stage while another instruction enters the pipeline – rather like an assembly line
