Class Note for CMPSCI 311 at UMass
Class Note for CMPSCI 311 at UMass
Popular in Course
Popular in Department
This 17 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 17 views.
Reviews for Class Note for CMPSCI 311 at UMass
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI601 Introduction Lecture 1 What is the subject matter of this course 0 Computability What can be computed in principle 0 Logic How can we express statements and proofs 0 Complexity What can be computed in practice Concrete Mathematical The mathematical method is to form abstractions that capture some important aspects of a realworld phenomenon then operate on those abstractions using formal de ni tion proof and mathematical problemsolving Our realworld target is digital computation Our rst ab straction is say that we have an input a collection of bits and want an output often a single bit The key questions are then 0 How is the input organized 0 What computational operations are allowed 0 Do we have internal memory and how much An answer to these questions gives us a formal model of computation Some Formal Models of Computation 0 Boolean Input bits are undifferentiated we can use boolean operations AND OR NOT and store the results We also express properties of the input using propositional logic 0 Formal Language Theory The input bits are ar ranged in a string of letters We work with one let ter at a time De ning the internal memory gives us models such as the nitestate machine pusna own automaton 0r Turing machine 0 FirstOrder Logic The input bits form a structure made up of relations We express properties of the input using rstorder logic eg quanti ers V and El 0 Recursive Function Theory Input bits are formed into nonnegative integers on which we de ne func tions starting from arithmetic operations 0 Abstract RAM The input and internal memory are formed into words in registers and operations mimic those of realworld sequential computers CMSPSCI 601 Course Requirements Lecture 1 Texts available at Jeffery Amherst College Store BE Jon Barwise and John Etchemendy Language Proof and Logic required new copy needed for homework P Christos Papadimitriou Computational C omplex ity recommended S Michael Sipser Introduction to the Theory of Computation useful lowerlevel reference Prerequisites Mathematical maturity reason abstractly understand and write proofs use bigO notation CMP SCI 250 needed CMPSCI 311 401 helpful Today s material is a good overview of the sort of stuff we will do next lecture we start right in on formal language theory Graded Work 0 Eight problem sets 35 of grade 0 Midterm 30 of grade inclass Monday 29 March 2004 0 Final 35 of grade Cooperation Students should talk to each other and help each other but write up solutions on your own in your own words Sharing or copying a solution could result in a grade of F for the course even on the rst offense If a signi cant part of one of your solutions is due to someone else or something you ve read then you must acknowledge your source When the grader then looks at the source it should be clear from your writeup that you ve understood anything you ve taken from it A good heuristic is not to have the source in front of you when you write up Electronic Grading Most of the homework problems from BE will be graded electronically Your inter action with the software provided will result in a le that you send in and each student must send in a sep arate le from a separate interaction with the software they check CMSPCI 601 On Reserve in Dubois Library Lecturel Mathematical Sophistication 0 How to Read andDo Proofs Second Edition by Daniel Solow 1990 John Wiley and Sons Review of Regular and ContextFree Languages 0 Hopcroft Motwani and Jeffrey D U11manIntroa uc tion to Automata Theory Languages and Computa tion 2001 Chapters 1 6 0 Lewis and Papadimitriou Elements of the Theory of Computation 1998 Chapters 1 3 0 Sipser Introduction to the Theory of Computation 1997 Chapters 1 2 NP Completeness 0 Garey and Johnson Computers and Intractability 1979 Descriptive Complexity 0 Immerman Descriptive Complexity 1999 6 Syllabus will be up soon on the course web site 0 http www cs umass eduNbarringcs6 01 There is a pointer there to the Spring 2003 web site and the syllabus there will be close to what we do here Rough guide 0 Formal Languages and Computability 9 lectures 0 Propositional and FirstOrder Logic 6 lectures 0 Complexity Theory 12 lectures CMPSCI601 Models of Computation Lecture 1 c How is the input organized c What computational operations are allowed 0 Do we have internal memory and how much An answer to these questions gives us a formal model of computation Some Formal Models of Computation Boolean 0 Formal Language Theory starting next lecture c FirstOrder Logic c Recursive Function Theory c Abstract RAM as in an algorithms course Boolean Computation Data Type Booleans true or false 0 or 1 Operations AND OR inclusive NOT can de ne more Variables Inputs 31 acn others yl ym Expressions x1 at 923 etc StraightLine Program y1 2 NOT Xl y2 y1 OR X2 y3 X3 AND x4 y4 y2 AND y3 5 y 2 OR xl return NOT y5 A straightline program is equivalent to a boolean circuit about which more later Each line of the program gate of the circuit has a truth value that is a function ofihe input variables Given a function of the inputs a property we will consider among other things how long a program is needed to compute it in this way Boolean Logic Chapters 18 of BE deal with propositional or boolean logic The main topics are 0 Syntax and semantics for boolean expressions 0 Rules for proving that an expression is a tautology or that one expression follows logically from another 0 A formal proof system encapsulating these rules and implemented as interactive software included with the book The basics of boolean logic should be review but formal proof may not be You will be expected to learn the proof system from the book and software and there will be exercises on it in HW2 At that point we will consider two important properties of the system 0 Soundness everything provable is true 0 Completeness everything true is provable Here everything refers only to statements that can be made within the system 10 FirstOrder Logic We can think of a sequence of boolean variables 30 acn1 as a single object X a function from the set 0 n 1 to 0 1 Thus for any number 239 in the range X is the boolean variable we used to call an X is also called a unary relation a property that each number in the range either has or doesn t have We can also have binary ternary or kary relations For example in a directed graph where the vertices are named 0 n 1 we have a binary relation E where the boolean Ez j is 1 iff there is an edge from 239 to j 11 More FirstOrder Logic A rstorder structure roughly speaking is a universe of base objects and a set of relations over them If one of these relations is the input we can use rstorder logic to de ne properties of the input For example the rstorder sentence Va Ely Eay is true for the graph with edge relation E iff every vertex has outdegree at least one In Chapters 913 of BE we ll see syntax and semantics for rstorder logic a set of proof rules for it and soft ware that lets you play with structures consisting of sets of blocks of different types on a grid We ll prove us ing later chapters of BE that this proof system is also sound and complete 12 Recursive Function Theory Bits can be used to represent numbers by which I gener ally mean nonnegatl ve integers in binary General com putations may be coded as functions from numbers or tuples of numbers to numbers Kleene s recursive function theory de nes a set of partial recursive functions by induction There are base func tions and rules for creating new functions from old ones It turns out that partial recursive corresponds to algo rithmically computable This is a theorem not a de nition l3 Primitive Recursion and Bloop An important subset of the partial recursive functions is the primitive recursive functions We will de ne these in terms of a simple programming language called Bloop My Bloop is based on the language of the same name in Hofstadter s G del Escher Bach but has a different syntax Variables represent numbers nonnegative integers They are declared and initialized to 0 when they rst appear Statements of Bloop consist of assignment statements x 0 the increment operator 0 function declarations and calls callbyvalue no re cursion 0 bounded loops for x B where x is a variable and B is a block of code in which x is not modi ed This code executes B exactly x times 14 thqExanu e declare one x return x declare addxy z x for y z return 2 declare multxy for x addzy return 2 15 Enriching Bloop 0 Use arithmetic expressions like variables 0 Simulate if then if x B means y one for X for y B y 0 This executes B once if x is positive and otherwise does nothing A function is primitive recursive iff it can be implemented by a Bloop program 16 Relations Among The Models Let s look at a single problem Given n input bits we want to know whether exactly two of them are ones This question can be posed in each of our models 0 Boolean There are various ways to build an SLP or circuit which we ll explore on HW1 0 FiniteState Machine Sweep the input string left toright remembering whether we ve seen zero one two or more than two ones 0 FirstOrder Logic 3x ly a yVzlzlt gt zszzzy 0 Numerical Input Is the input the sum of two dis tinct powers of two On HW1 you ll write a Bloop program to decide this 0 Abstract RAM The problem probably defaults to one of the others once we decide on our data repre sentation 17
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'