Theory of Computation

Theory of Computation

1. Finite State Machines

   • A finite state machine is a model of computation used to design programs and sequential logic circuits

2. Regular Expression

3. Regular Language

   • A language is called regular if it can be represented by a regular expression
   • It can also be defined as any language that a finite state machine will accept

4. Backus-Naur Form

   • Meta-Languages
     • In order for a computer language to be translated into machine code, all rules of the language must be defined unambiguously
     • Backus-Naur Form is an example of one such meta-language. Many constructs that could be written using a regular expression can be expressed more succinctly using BNF

5. Big-O Notation

6. Limits of computation

   • Tractable problems
     • Tractable problems are problems which a computer can solve but it would take a complexity of time
     • O(n^k)
     • O(n)
     • O(n log n)
     • O(n^10)
   • Intractable problems
     • Is a problem which does not have a polynomial-time solution.
     • O(2^n)
     • O(n!)

7. Heuristic Methods

   • Solving a problem which uses an algorithm or method which is not guaranteed to be optimal or perfect but is sufficient for the purpose
   • It won't solve all the problems but it must solve most/many
   • Virus scanners use this approach

8. The Halting Problem

   • The Halting problem is the problem of determining whether for a given input, a program will finish running or continue forever.
   • The Halting problem demonstrates that there are some problems that cannot be solved by a computer.

9. Turing Machine

   • It consists of an infinitely long strip of tape divided into squares. It has a read/write head that can read symbols from the tape and make decisions about wha to do based on the contents of the cell and its state

Bilder und Dateien der Mindmap