Section 2 - Problem solving and theory of computation Flashcards
Examples of high-level procedural languages?
Python
C#
In high-level procedural languages we can use algorithms to implement…
Sequence
Selection
Iteration
What is a sequence?
one or more statements following one after the other
How do we implement selection in a program?
Implemented using an IF…THEN…ELSE statements
Define iteration
Iteration means repeated execution of a set of statements
Most high-level languages have three main iterative structures, can you name these?
WHILE, FOR, REPEAT
What are the 2 types of strategies when problem solving?
Exhaustive search
divide and conquer
What is the general ‘rule’ when looking at logic problems.
All problems can be solved with an algorithm
Define an exhaustive search, when problem solving
Trying every combination possible to gain an end result.
Requires little knowledge, essentially trial and error.
Can take a lot of time
Define ‘divide-and-conquer’ when problem solving
Use of binary search, split things in half.
Search one half then repeat.
Define abstraction.
The removal of information, in turn making data easier to understand by the user.
Aims to remove complexity
Representational abstraction?
The removal of unnecessary information.
What are finite state machines?
A model of computation used to design computer programs and sequential logic circuits.
Not an actual machine. An abstract model of how a machine would react to an external event.
The machine can be in one of a finite number of states and changes from one state to the next when triggered by some condition or input
When are FSM’s often used?
The modeling of hardware, compilers and network protocols.
e.g. vending machines, traffic lights, lifts, combination locks, communication protectors
