Unit 2 - Problem solving and theory of computation Flashcards
What is Structured programming?
Structured programming is a method of writing a computer program which uses:
Top-down analysis for problem-solving.
Modularization for program structure and organisation.
Structured code for the individual modules.
What is top-down analysis?
The program is divided into modules, which are called from the main program.
Any of the modules may be further broken down into smaller sub-tasks, with the smallest modules performing a single function.
A hierarchy chart may be used to show the overall program structure.
How does a hierarchy chart work?
Execution takes place from left to right, always at the lowest level component.
Selection and iteration are not shown in a hierarchy chart.
Any module shown below another module is part of the module above.
What are some benefits of structured programming?
Programs are more easily and quickly written:
Large programs are broken down into subtasks that are easier to program and manage.
Each module can be individually tested.
Modules can be re-used several times in a program.
Programs are more reliable and have fewer errors:
It is easier to find errors in small self-contained modules.
Programs take less time to test and debug.
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.
What is modular programming?
Subdividing a computer program into separate sub-programs
Why do we use modular programming?
Modular design and programming techniques are most useful for large, complex programs.
Some programs have thousands or even millions of lines of code.
What is the aim of structured programming?
Can be thoroughly tested and proved to be error free.
Are easy to understand and maintain.
Minimise duplication of effort.
Why are hierarchy charts used?
They’re a useful design tool for breaking down a large program into manageable chunks.
They’re useful for documentation purposes.
What is computational thinking?
The ability to think logically about a problem and apply techniques for solving it
What are some methods of problem solving?
Simulation
Enumeration – list all cases
Trial and error
Theoretical approach
Creative solution
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 operation.
What are the properties of a good algorithm?
Has clear and precisely stated steps that produce the correct output for any set of valid inputs.
Should allow for invalid inputs.
Must always terminate at some point.
Should execute efficiently, in as few steps as possible.
Should be designed in such a way that other people will be able to understand it and modify it if necessary.
What are some useful tools for designing algorithms?
Hierarchy charts – useful for identifying the major task, and breaking these down into subtasks
Flowcharts – useful for getting down initial ideas for individual subroutines
Pseudocode – will translate easily into program code
What are some examples of sorting algorithms?
Bubble sort and Merge sort.
How does bubble sort work?
To sort an array of n items, n-1 passes are made through the array, with each item being compared with the adjacent item and swapped if necessary.
What does ‘divide and conquer’ mean?
This involves finding a solution to a sequence of smaller, related problems until the instance is small enough to be solved directly.
How does a merge sort work?
Divide the unsorted list into n sublists, each containing one element
Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This is the sorted list.
An example of a ‘divide and conquer’ algorithm.
What are some examples of searching algorithms?
Linear search and binary search.
How does a linear search work?
Starts at the beginning of the list and examines every item.
How does a binary search work?
Uses the “divide and conquer” strategy to halve the search area each time an item is examined.
Can only be used if the list is ordered.
What is the purpose of testing?
The purpose of testing software is to reveal errors.
A good test is one which uncovers an error in the program.
What are the different stages of testing?
Module testing
Program testing
System testing
What does module testing do?
Make sure each subroutine works correctly.
What does Program testing do?
Make sure each program in the system works correctly.
What does system testing do?
Make sure the whole system works as expected, and does what the original specification required.
What is normal data?
Typical, sensible data that the program should accept and be able to process.
What is boundary data?
Valid data that falls at the boundary of any possible ranges, sometimes known as extreme data.
What is erroneous data?
Data that the program cannot process and should not accept.
What is information hiding?
Means
hiding design details behind a
standard interface.
The process of hiding all details of an object that do not contribute to its essential characteristics.
What is abstraction?
Removing unnecessary details of a problem to make it more manageable and easier to solve.
What is representational abstraction?
An abstraction arrived at by removing unnecessary details.
What is abstraction by generalisation?
Means grouping by common characteristics to arrive at a hierarchical relationship of the ‘is a kind of’ type.
What is automation in terms of abstraction?
Refers to building models of real world objects or phenomena in order to solve a particular problem.
What is procedural abstraction?
Refers to the mechanisms in computer programming that enable and enforce the abstraction of operations.
What is functional abstraction?
Referring to the practice of identifying and expressing a task, or function, in a manner that separates what the task accomplishes from how it’s accomplished.
What is data abstraction?
A specific type of abstraction that involves simplifying data structures in order to make them easier to work with.
What is problem abstraction?
Details are removed until it becomes possible to represent the problem in a way that is possible to solve.
What is procedural decomposition?
Breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task.
What is composition?
The opposite of decomposition.
It is the process of combining procedures to form a compound procedure.
Combining data objects to form compound data objects such as a tree or stack.
What is a finite state machine?
It is an abstract representation of how something changes from one state to another in response to a condition or event.
What is a transition in a finite state machine?
A change from one state to another in response to an event or condition.
What are some applications of FSM’s?
Robotics.
Video games industry.
Design of digital hardware systems.
Design of compilers and network protocols.
What is a finite state automaton?
A FSM which has no output.
They have an initial state and one or more accepting or goal states.
It simply runs through the input sequence of symbols, one by one, changing state or not as a result of the current state
and the current symbol from the input it sees.
On reaching the end of the input, it stops and, depending on which state it stopped in, accepting state or a non-accepting state, it is able to decide whether the input sequence has met the criteria or not - accepted or not accepted.
How can you avoid a FSM having to report an error?
Ensure that for each state there is an outgoing transition for every symbol in the machine’s input alphabet.
What is a state transition table?
A state transition table shows the effect of particular inputs on the
current state of an FSM with no output.
Why are finite state machines useful?
Finite state machines (FSMs) are used extensively in applications in computer science. For example, finite state machines are the basis for
* Any kind of controller, e.g. traffic lights
* Specifying a language, e.g. given any string, an FSM determines if
that string is in the language or not
* Programs for:
– spell checking
– grammar checking
– indexing or searching large bodies of text
– recognising speech
– processing text containing mark-up languages such as XML
and HTML
* networking protocols that specify how computers communicate.
