Theory of Computation
Last updated 1/12/20
What is this course about?
Copyright By PowCoder代写 加微信 powcoder
This course is about the fundamental capabilities and limitations of computers/computation
This course covers 3 areas, which make up the theory of computation:
Automata and Languages Computability Theory
Complexity Theory
Automata and Languages
Introduces models of computation
We will study finite automata and context free grammars
Each model determines what can be expressed, as we will see in Part I of this course
Will allow us to become familiar with simple models before we move on to more complex models like a Turing machine
Given a model, we can examine computability and complexity
Computability Theory
A major mathematical discovery in 1930s
Certain problems cannot be solved by computers
That is, they have no algorithmic solution
We can ask what a model can and can’t do
As it turns out, a simple model of a computer, A Turing machine, can do everything that a computer can do
So we can use a Turing machine to determine what a computer can and can’t do (i.e., compute)
Complexity Theory
How hard is a problem?
You already should know a lot about this
You should know how to determine the time complexity of most simple algorithms
You should know the Big O notation. We can say that a problem is O(n2) and that is harder than an O(n) problem
We take one step forward and study NP-completeness A first course in theory of computation generally stops there
and hence we will not cover Chapters 8, 9, or 10 of the text
About this Course
Theory of Computation traditionally considered challenging I expect (and hope) that you will find this to be true!
A very different kind of course
In many ways, a pure theory course
But very grounded (the models of computation are not abstract at all)
Proofs are an integral part of the course, although I and the text both rely on informal proofs
But the reasoning must still be clear
The only way to learn this material is by doing problems
You should expect to spend several hours per week on homework
You should expect to read parts of the text 2-4 times
You should not give up after 5 minutes if you are stumped by a problem
The best way to prepare for the exams is to put significant effort into the homework
Mathematical
Preliminaries Chapter 0
A review of discrete math with some new material
Mathematical Preliminaries
We will now very quickly review discrete math
You should know most of this from 1100/1400
Reading Chapter 0 of the text should help you review
Ask me for help if you have trouble with some of this
Mathematical Notation Sets
Sequences and Tuples
Functions and Relations
Strings and Languages (not covered previously) Boolean Logic
Proofs and Types of Proofs
A set is a group of objects, order doesn’t matter The objects are called elements or members
Examples:
{1, 3, 5}, {1, 3, 5, …}, or {x|xZ and x mod 2 ≠ 0}
You should know these operators/concepts Subset (A B or A B)
Cardinality: Number elements in set (|A| or n(A)) Intersection () and Union (), Complement
What do we need to know to determine complement of set A? : can be used to visualize sets
Power Set: All possible subsets of a set IfA = {0, 1} then what is P(A)?
In general, what is the cardinality of P(B)?
Sequences and Tuples
A sequence is a list of objects, order matters Example: (1, 3, 5) or (5, 3, 1)
In this course we will use term tuple instead (1, 3, 5) is a 3-tuple and a k-tuple has k elements
Sequences and Tuples II
Cartesian product (x) is an operation on sets but yields a set of tuples
Example: if A = {1, 2} and B = {x, y, z} A x B = {(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)}
If we have k sets A1, A2, …, Ak, we can take the Cartesian product A1 x A2 … x Ak which is the set of all k-tuples (a1, a2, …, ak) where ai Ai
We can take Cartesian product of a set with itself Ak represents A x A x A … x A where there are k A’s.
The set Z2 represents Z x Z all pairs of integers, which can be written as {(a,b)|aZ and bZ}
Functions and Relations
A function maps an input to a (single) output f(a) = b, f maps a to b
The set of possible inputs is the domain and the set of
possible outputs is the range f: D R
Example 1: for the abs function, if D = Z, what is R? Example 2: sum function
Can say Z x Z Z
Functions can be described using tables
Example: Describe f(x) = 2x for D={1,2,3,4}
A predicate is a function with range {True, False} Example: even(4) = True
A (k-ary) relation is a predicate whose domain is a set of
k-tuples A x A x A … x A
If k =2 then binary relation (e.g., =, <, ...)
Can just list what is true (even(4))
The text represents the beats relation in Example 0.10 (page 9)
using a table and a set
Relations have 3 key properties: reflexive, symmetric, transitive
A binary relation is an equivalence relation if it has all 3 Try =, <, friend
A graph is a set of vertices V and edges E G= (V ,E) and can use this to describe a graph
V = {A, B, C, D} C
E = {(A,B), (A,C), (C,D), (A,D), (B,C)}
Definitions:
The degree of a vertex is the number of edges
touching it
A path is a sequence of nodes connected by edges
A simple path does not repeat nodes
A path is a cycle if it starts and ends at same node
A simple cycle repeats only first and last node
A graph is a tree if it is connected and has no simple cycles
Strings and Languages
This is heavily used in this course
An alphabet is any non-empty finite set
Members of the alphabet are alphabet symbols
1 = {0,1}
2 = {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z} 3 = {0,1,a,b,c}
A string over an alphabet is a finite sequence of symbols from the alphabet
0100 is a string from 1 and cat is a string from 2
Strings and Languages II
The length of a string w, |w| is its number of symbols
The empty string, ε, has length 0
If w has length n then it can be written as w1w2... wn, where wi
Strings can be concatenated
ab is string a concatenated with string b
a string x can be concatenated with itself k times This is written as xk
A language is a set of strings
Boolean Logic
Boolean logic is a mathematical system built around True and False or 0 and 1
Below are the boolean operators, which can be defined
by a truth table
(and/conjunction)
(or/disjunctions) (not)
(implication)
(equality)
1 1 = 1; else 0 0 0 = 1; else 1
1 = 0 and 0 = 1 1 0 = 0; else 1
1 1 = 1; 0 0 =1
Can prove equality using truth tables DeMorgan’s law and Distributive law
Proofs are a big part of this class
A proof is a convincing logical argument
Proofs in this class need to be clear, but not very formal
The books proofs are often informal, using English, so it isn’t just
that we are being lazy Types of Proofs
A B means A if and only if B Prove A B and prove B A
Proof by counterexample (prove false via an example)
Proof by construction (main proof technique we will use) Proof by contradiction
Proof by induction
Proofs: Example 1
Prove for every graph G sum of degrees of all nodes is even Take a minute to prove it or at least convince yourself it is true
The book does not really say it, but this is a proof by induction
Their informal reasoning: every edge you add touches two vertices and increases the degree of both of these by 1 (i.e., you keep adding 2)
See Example 0.19 p18 and Theorem 0.21 p20
A proof by induction means showing 1) it is true for some base case and then 2) if true for any n then it is true for n+1
So spend a minute formulating the proof by induction
Base case: 0 edges in G means sum-degrees=0, is even
Induction step: if sum-degrees even with n edges then show even with n+1 edges
When you add an edge, it is by definition between two vertices (but can be the same). Each vertex then has its degree increase by 1, or 2 overall
even number + 2 = even (we will accept that for now)
Proofs: Example 2
For any two sets A and B, (A B)′ = A′ B′ (Theorem 0.20, p 20)
Where X′ means the complement of X
We prove sets are equal by showing that they have the same elements
What proof technique to use? Any ideas? Prove in each direction:
First prove forward direction then backward directions Show if element x is in one of the sets then it is in the other
We will do in words, but not as informal as it sounds since we are really using formal definitions of each operator
Proof: Example 2
(A B)′ = A′ B′
Forward direction (LHSRHS):
Assume x (A B)′
Then x is not in (A B) [defn. of complement] Then x is not in A and x is not in B [defn. of union] So x is in A′ and x is in B′ and hence is in RHS
Backward direction (RHSLHS) Assume x A′ B′
So x A′ and x B′
So x A and x B
So x not in union (A B)
So x must be its complement
So we are done!
[defn. of intersection] [defn. ofcomplement] [application of union]
[defn. of complement]
Proofs: Example 3
For every even number n > 2, there is a 3-regular graph with n nodes (Theorem 0.22, p 21)
A graph is k-regular if every node has degree k We will use a proof by construction
Many theorems say that a specific type of object exists. One way to prove it exists is by constructing it.
May sound weird, but this is by far the most common proof technique we will use in this course
We may be asked to show that some property is true. We may need to construct a model which makes it clear that this property is true
Proof: Example 3 continued
Can you construct such a graph for n=4, 6, 8? Try now.
If you see a pattern, then generalize it and that is the proof.
Hint: place the nodes into a circle Solution:
Place the nodes in a circle and then connect each node to the ones next to it, which gives us a 2-regular graph.
Then connect each node to the one opposite it and you are done. This is guaranteed to work because if the number of nodes is even, the opposite node will always get hit exactly once.
The text describes it more formally.
Note that if it was odd, this would not work.
Proof: Example 4
Jack sees Jill, who has come in from outside. Since Jill is not wet he concludes it is not raining (Ex 0.23, p 22)
This is a proof by contradiction.
To prove a theorem true by contradiction, assume it is false and show that leads to a contradiction
In this case, that translates to assume it is raining and look for contradiction
If we know that if it were raining then Jill would be wet, we have a contradiction because Jill is not wet.
That is the process, although not a very good example (what if she left the umbrella at the door!)
This case is perhaps a bit confusing. Lets go to a more mathematical example …
Prove Square Root of 2 Irrational
Proof by contradiction, assume it is rational
Rational numbers can be written as m/n for integer m, n Assume with no loss of generality we reduce the fraction
This means that m and n cannot both be even If so, 2 goes into both so reduce it
Then do some math 2 = 𝑚𝑛
2n2 = m2
This means that m2 is even and thus m must be even Since odd x odd is odd
Prove Square Root of 2 Irrational
So 2n2 = m2 and m is even
Any even number can be written as 2k for some integer k, so:
2n2 = (2k)2 = 4k2 Then divide both sides by 2
n2 = 2k2
But now we can say that n2 is even and hence n must be even
We just showed that m and n must both be even, but since we started with a reduced fraction, that is a contradiction.
Thus it cannot be true that 2 is rational
More on Proof by Induction
Worth going over one more example since some of you may not have used this technique before
Please ignore Theorem 0.25, p 24 in text which is how the book explains proof by induction
complicated induction proof which is not very illustrative
You have a proof by induction for HW1, so the next example should help
Another Proof by Induction Example
Prove that n2 ≥ 2n for all n 2, 3, …
Base case (n=2): 22 ≥ 2×2? Yes.
Assume true for n=m and then show it must also be true for n=m+1
So we start with m2 ≥ 2m and assume it is true
we must show that this requires (m+1)2 ≥ 2(m+1) Rewriting we get: m2+2m+1 ≥ 2m+2
Simplifying a bit we get: m2 ≥ 1.
So, we need to show that m2 ≥ 1 given that m2 ≥ 2m If 2m ≥ 1, then we are done. Is it?
Yes, since m itself ≥ 2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com