Report

Introduction Chapter 0 Three Central Areas 1. Automata 2. Computability 3. Complexity Complexity Theory • Central Question: What makes some problems computationally hard and other easy? – Sorting (easy) – Computers can easily sort a billion items in seconds. – Scheduling (hard) – With real constraints scheduling a thousand courses to avoid room and instructor conflicts can take years of computation. • Cryptography (secret encryption) depends on the existence of sufficiently hard problems. Computability • Based on the work of Kurt Gödel, Alan Turing, and Alonzo Church. • Some very basic problems cannot be solved by computers. – Example: Determining if a mathematical statement is true or false. • Instead of hard vs. easy, Computability centers on solvable vs. unsolvable problems. Automata Theory • We construct a simple, formal and precise model of a computer. – The precision and formality allow us to prove the computability of problems • Three types of computer machines 1. Finite Automata 2. Pushdown Automata 3. Turing Machine Sets {7, 57, 7, 7, 21, 7} = {21, 7, 57} Order does not matter Repetition is not a factor Infinite Sets Subsets Set Descriptions Set Operations Venn Diagrams Venn Diagrams Venn Diagrams Venn Diagrams • What would A-B look like? B A Sequences (Tuples) Order and repetition matter (7, 21, 57) different than (57, 21, 7) (4,3) ordered pair, whereas {4,3} set of size 2 (11, 21, 3, 24, 57) is a 5-tuple Functions (Relations) Domain & Range Example Binary Function (two inputs) g(x,y) = z where x, y and z are in {0,1,2,3} Predicate • function whose range is {True, False} • Example: f(a,b) = a Beats b f(scissors,paper) = scissors Beats paper = TRUE Binary Relation • Predicate whose domain is a set of ordered pairs P: A x A {True False} Example: A = {paper, stone, scissors} (scissors, stone) False (stone, scissors) True Predicates can be described as sets S= { (scissors,stone), (paper, stone), (stone, scissors) } Equivalence Relation Binary Relation that is 1. Reflexive: f(x,x) is always true 2. Symmetric: if f(x,y) is true then f(y,x) is true 3. Transitive: if f(x,y) and f(y,z) are both true then f(x,z) is true. Example f(a,b) = a Beat b; • Not reflexive: f(paper,paper) = false • Not symmetric: f(paper, stone) = true, but f(stone, paper) = false • Not transitive: f(paper, stone) and f(stone, scissors) is true, but f(paper, scissors) is false Example f(a, b) true if a <= b, otherwise false f(a, b) a <= b R = {(a,b) | a <= b} • Always reflexive: (a,a) is always true for all a’s • Not always symmetric: If (a,b) is true then (b,a) might be false. • Always transitive: (a,b) and (b,c) imply (a,c) Question • Is this an equivalence relation (i.e., reflexive, symmetric, and transitive)? f(a,b) a != 1 AND b != 1 R = {(a,b) | a != 1 AND b != 1} Equivalence Relations • f: S x S {True, False} • S = {s1, s2, s3, s4, s5} f s1 s2 s1 True True s2 True True s3 s4 s5 s3 True True True s4 True True True s5 True True True Equivalence Relations & Automata • We are interested in functions that can separate a set of items into disjoint classes. • {{s1, s2}, {s3, s4, s5}} • In automata theory, the items will be languages. • The functions will be automata and Turing machines • The classes will be – Regular languages – Context-free languages – Context-sensitive languages Equivalence & Automata Theory The theoretical “heart” of computation • Inputs, outputs and algorithms can all be encoded as strings of a language • Solving problems can be reduced to defining languages (set of strings) that correspond to correct solutions to a problem. • Then, solving a problem reduces to creating an automata that can recognize if a string is in a particular language – i.e., is a string a solution to the encoded problem? Graph Theory Terminology: • Nodes/vertices • Edges • Degree • Self-loop • Directed vs. Undirected Graphs • Labeled Graph • Subgraph Graph Theory • • • • Paths, cycles, trees Outdegree, Indegree Directed path Strongly connected Meaningful graphs • Directed graphs can show relations Equivalence Relations as Graphs • Example to be drawn Strings & Languages • Defining alphabets (symbol domain) String terminology • Length w = abc, |w| = 3 • Empty string ɛ • Reverse w = abc, wR = cba • Substrings of w = {ɛ, a, b, c, ab, bc, abc} – ba, cb, ca, cba, and ac are not substrings of w, but they are subsets if w were considered a set – ac is not a substring, but it is subsequence (confusing) • Lexicographic order {ɛ , 0, 1, 00, 01, 10, 11, 000, … } Language • A language is a set of strings • Languages can be explicitly described Animals = {cat, dog, cow, …} {w | an, n > 1} = {a, aa, aaa, aaaa, … } • Languages can also be described using – grammar rules and – automata that can recognize strings in the language. Boolean Logic • Review on your own, but Boolean Logic Proof by Construction • State your claim. Be very specific and describe an object you claim exists • Construct the object. Show details and describe parameters • Conclusion. Restate your goal in constructing the object. Example Proof By Contradiction • Assume that the theorem is false – Even though you know it to be true • Show that this assumption leads to a contradiction with something that has already been proven true Example • Prove that • First, assume that it is rational, i.e., • Where m and n are integers • Also, m/n is reduced, so one of them has to be even. Example • Prove that • Do some algebra • We know that m must be even. Why? Example • Prove that • We know that n must be even. Why? • Thus, m and n are even. Why is this a contradiction?