3-1 Problem Solving

3-1-1 - Information Hiding & Abstraction
3-1-2 - Comparing Algorithms
3-1-3 - Finite State Machines
3-1-4 - Turing Machines
3-1-5 - Intractable Problems
3-1-6 - Regular Expressions, BNF & RPN

3.1.5 - Intractable problems

• Algorithmic problems - Such as making a Cake or searching & sorting

• Non - algorithmic problem - Who would win in a fight between batman and spiderman

• Algorithmic problems can be divide into:

• Finite Problems - Finite set of inputs & are solvable

•  Infinite problems - Infinite set of problem & are not neccessarily solvable

• Non computable problem

A problem that has no algortithm to solve it (Not possible to compute)

• Decision problems

Two outputs only "Yes" or "No" algorithm

• Decidable problem

I has an answer and can be solved

• Undecideable problem

A decision type algorithm problem that is non- computeable

• eg. 'This statement is false'  or 'I always lie'

• Tractable problem

A problem that has a reasonable (Polynomial) time solution as the size of the input increases

• eg. Adding up a row of numbers

• Intractable

A problme for which no reasonable (Polynomial) time solution has bee found

• eg. The Traveling Salesman Problem

• The Heuristic Approach (common sense)

Common sense is used to help solve intractable glorithmic porblems in a reasonable amount of time (Polynomial) 

 

 

 

 

 

 

 

 

 

3.2.6 - Sorting Techniques

Why is efficient sorting so important?

Sorting is very important, it enables us to carry out efficient binary searches on large databases.

 Bubble Sorting

¢Start at the beginning of the list.

¢Compare each pair of items.

¢If they are not in order swap them.

¢Work through the list n-1 times.

A working example would be like this:

Insertion Sort

In an Insertion Sort each element in turn is inserted into it’s correct place in the sorted list.

Advantage 

- Faster than bubble sort

Disadvantage

- More complex to code

A worked example is shown below:

The next element to be inserted into the correct place is shown in red.  The sorted part of the list is green.

3.2.6 - Searching Techniques

Why is efficient searching for data important?

Most data stored by organisations will be in a database format. Some Databases have millions of records.

Interactive systems, such as google or cash machines, rely on data being retrieved from these systems quickly, therefore efficient searching techniques are needs to process all the data quickly and efficiently.

Linear Search

¢Start at the beginning of the list.

¢Compare each item in the list with the search item.

¢Stop when the item is found or when the end of the list is reached.

Advantages.....

¢This technique is very simple to code.

¢A Linear Search works with an unsorted list.

Disadvantage.....

¢Linear Searches are slow, especially with large lists.

Binary Search

1.Find the Middle Item of the Current Search List.

2.Check if the Current Item is the Search Item.

3.If not then make the Current Search List either the Higher Half or the Lower Half of the list.

4.Go to Step 1

Advantage.....

¢Much Faster than a Linear Search, especially as the List increases in size.

Disadvantages.....

¢The List needs to be Sorted.
¢A Binary Search is more Complex to Code.

3.1.4 - Turing Machines

Background

In the early twentieth century, mathmaticians were trying to create a universal machine. 

This consisted of a small number of operations and a machine that could perform all these operations.

This machine would be able to run any algorithm, and would be the precise definition of term algorithm.

The hope was to find algorithms that would be able to solve all mathmatical problems.

1930 -

Kurt Godel showed that there are mathmatical statements that it will never be possible to either prove or disprove.

Alan Turing showed that it would not be possible to write an algorithm which could determine if a problem is solvable or unsolvable.

1936 -

Turing machine invented & showed that you cannot determine if it is solvable or not.

Relevance to computing

•   Computers where based on turning machine. 
• IT showed that anything a computer can do a turing machine (on paper) can do. 

 Turing Machine

1.An input alphabet.

2.A tape that is infinitely long.

3.An output alphabet that can be printed on the tape.

4.A tape head that is used to read/write to the cells.

5.A finite set of states, including a start state.

6.A program (set of instructions).

Anoter way of looking at this is a Deterministic finite state machine together with an infinitely long tape.

3.1.3 - Finite State Machines

• An FSM accepts input and processes an output.

Examples of where they are used would be things such as:
- Traffic Light Control System
- Programs for spell checking
- Networking Protocols

• A State Transition Diagram

These are used to show the FSM as a picture where the plain arrow is the starting state#

• Finite State Automata (FSA)

This type of FSM has a finishing state and produces only a YES or No , depending on the final state. for exmple S2 in the diagram below would give Yes any other state would give No.

• There are Two types of FSM:

- Mealy Machines

   - This gives an output on the Transitions (Arrows)

- Moore Machines

   - This gives an output on the states (Cricles)

• FSM Transition Table

A Transition Table shows the states and Tranistion in a FSM in table format, as shown above.

• Transition Functions

These show the sates and tranistions as a serious or written functions:

(Input Symbol, Current State)  -> (Output Symbol, Next State)

this can be taken and used to generate a program to show the operation of the FSA

• Deterministic and Non - Deterministic FSA

A Deterministic FSA has one and only one transition (arrow) for each input.

A Non- Deterministic FSA can have multiple transitions for and input. Meaning there is more than  one possible route around the State Transition Diagram

Halting States - These are states with no outputs

• Summary:

1. Finite State Machines (Input, Process, Output)
2. Sate Transition Diagram (Shows FSM as picture)
3. Finite State Automata (Gives only Yes on a finishing state or a No as an output)
4. Mealy Machine (Output on Transitions)
5. Moore Machine ( Output on State)
6. Transition Table ( Table showing States and Transitions in an FSM)
7. Transition Function (Shows transitions in a series of functions)
8. Deterministic and Non- Determisnitc FSA (Output with one and Output with more than on)
9. Halting State (No Outputs)

3.1.2 - Comparing Algorithms

Problems with different time complexities

Constant Complexity O(1) - This algorithm takes the same amount of time no matter how big the problem is.

Linear Complexity O(n) - As the size of the problem increases, the time taken to solve the problem grows at the same rate. (Proportional) Less efficient

Logarithmic Complexity O(log n) - As the size of the problem grows, the time take to solve the problem increases, but at a slower rate.

Polynomial Complexity O(nk) - As the size of the problem grows, the time taken to solve it grows faster, but can be solved in a reasonable amount of time.

Expotential Complexity O(kn) - As the size of the problem grows, the time taken to solve it grows by larger and larger amounts, Only small size version of these problems can be solved in a reasonable amount of time

Factorial Complexity O(n!) - Even worse than exponential. cannot be solved in a reasonable amount of time.

3.1.1 - Information Hiding & Abstraction

Information Hiding - Hiding the design complexity of a  system to simplify it for the user

• e.g. Windows - unaware of the underlying complexity behind the system

Abstraction - This is where any unnecessary details are removed from the system (Information Hiding)

• e.g. Tube maps - no relation to real life distances at all

Generalisation -  In computing this would be wear only the main principles of a computer system is shown and not the rest of the program, for example a top down design.

Representation - Simplifying a complex system such as phone masts that do not have numbers, distances etc.

Levels of abstraction:

1. Application (Word processing) - High levels of abstraction.
2. High level programming languages (VB) - hides low level commands such as what the IF statement does.
3. Machine Code - Hides the complexity of the underlying electronics behind a machine code commands.
4. Electronics - Hides the physical process of atoms & neutrons with basic electronics components.