Problem solving

Problem solving

1. Backus-Naur Form

   • It is a way of expressing syntax's in computing. The BNF is put into a list and the syntax is compared to it to see if it is valid.
   • To represent the syntax symbols are used, these are:
   • : := means is defined as
   • | is or
   • <> category names
   • An example is <Parent Expression> ::= <Child Expression 1> | <Child Expression 2> This means that parent expression is made up of child expression 1 or child expression 2. The child expressions would then have to be defined.

2. Reverse Polish Notation

   • Is a way of representing mathematical equations in a for that is easier for machines to understand. Brackets are not needed as the layout helps the machine determine the order.
   • The normal notation we use is infix where the operator is between numbers but this is when the operator is after the numbers called post-fix
   • An example is 56* which is 5*6.

3. Symbols:

   • | means or
   • ? means 0 or one
   • * means zero or more
   • + means one or more
   • [] means one character allowed withing the brackets. For example [ab] is a or b [a-z] means and letter from a to z.
   • () groups what is in the brackets so (ab)+ is ab or abab or ababab etc
   • \ this indicates that the subsequent character is to be treated as a literal character so if you wanted to use * then you would put *\
   • [^] matches everything but what's inside the brackets
   • ^ shows the start of the string
   • $ shows the end of the string
   • . matches a single character so .an could be ban, pan, dan etc.

4. Finite State Machines

   • No output finite state automata input|input where| is or
     • Processors an input string changing states while doing so, if the final state is the halting state it outputs YES otherwise it outputs NO.
       • Accepting/Final State-The state where the string is accpeted
       • Halting State-The state with no outward trnasititons
   • With output input|output
     • Mealy Machine
       • The data is outputted on transition between the states
     • Moore Machine
       • The data is outputted on arrival to the state. This means that no matter the input to get to the state or the previous state the output is always the same.
     • Deterministic
       • From a state one input is matched by one transition between states
     • Non-deterministic
       • From a state one input has more than one transition between states i.e. there is an element of choice
       • Any problem represented as a non-deterministic FSA can also be represented as a deterministic FSA (DFSA) but more steps may be required.
   • Made up of a: input alphabet, output alphabet, finite set of states, transitions between states.

5. Turing Machine

   • A theoretical machine that can solve any problems that a modernd day computer can solve.
   • Consist of 6 things:
     • 1. Input alphabet
     • 2. Output alphabet
     • 4. Infinitely long tape going to the right
     • 3. Finite set of states
     • 5. Tape head that moves along the tape reading from and writing to it
     • 6. A program/set of instruction that tell us how to move from state to state, what to output, where to move the reader based on the input and current state
   • General or formal model of computation and can be used to show weather a task is computable or not.
   • # separates the data  represent an empty cell
   • A state transition diagram can be drawn which shows the separate states and what input is required to transition between them and the matching output and head movement. This can then be turned into a table. It can also be represented as transition functions written in a formal language in the form (Current State,input symbol)=(Next State,output symbol,movement) if no output then keep the output symbol the same as the input one.
   • Universal Turing Machine: Can execute other Turing machines by simulating the behaviour of any other Turing Machine.

6. Computational complexity

   • Size Complexity: The amount of memory required by the algorithm
   • Time complexity: The time it takes to run the algorithm
   • Best Case Complexity: The input that would take the least amount of time
   • Worst Case Complexity: The input that would take the most amount of time this is taken to be the complexity of a problem
   • Average Case Complexity: The average of the times it would take for every input
   • Order of growth: Is the effect on the time as the input size increases
     • Big O notation is used to represent this
     • O(1) Constant complexity: The time stays the same no matter how big the input gets. Fore example sorting the first 10 numbers of a list,.
     • O(n) Linear Complexity: The time and number of items are directly proportional, they increase at the same rate. For example a linear search 10 items in list 10 comparisons, 12 items 12 comparisons.
     • O(Log n) Logarithmic Complexity: If n is small then increasing n will have quite a big effect on the time but as n gets massive not as much of an effect, think of the graph. Example is binary search.
     • O(n^k) Polynomial Complexity: The time increases at a rate greater than the rate of which the input increse. An example is bubble sort.
     • O(K^n) Exponential Complexity: This can only be used for small values of n as when n gets bigger the time will get massive. Chinese emporer
     • O(n!) Factorial Complexity: Can only be used for very small values of n as the time will get bigger very very quickly. An example is the brute force method for travelling salesperson.
   • Non-computable problems: These are problems which it is impossible to create an algorithm for, cannot do a Turing machine for. For a computer scientist it is very important to know if a problem is non-computable or intractable.
     • Halting Problem is an example of a non-computable problem. Turing proved that it is impossible to write an algorithm in which you give it another algorithm and it will tell you if it will stop or not. Most programs are complex so this cannot be seen by looking at them so the most obvious thing is to run it and see if its stops. The problem with this though is if it doesn't stop there is no way of knowing if it is never going to stop or just hasn't stopped yet. Turing used a proof by contradiction to show it was not possible in which you assume something is true and then find a contradiction so it cannot be true.
   • Intractable Problem: These are problems for which there is an algorithm but it does not take a reasonable amount of time, exponential or factorial order. It is difficult to prove if a problem is intractable as ther could be a better algorithm not yet discovered TSP.