计算理论导论(英文版)前言.ppt

11 History of computation and computational modelsnFor thousands of years,computing was done with pen and paper,chalk and slate,or even mentally,sometimes with the aid of tables.nThe theory of computation began early in the twentieth century(the 1930s),before modern electronic computers had been invented.nAt that time,mathematicians were trying to find which math problems could be solved by simple methods and which could not.nThe first step was to define what was meant by a simple method for solving a problem,implying a need for a formal model of computation.2computational modelsnSeveral different computational models were devised by these early researchers.nOne model,the Turing machineTuring machine,stores characters on an infinitely long tape,with one square at any given time being scanned by a read/write head.Another model,recursive functions,uses functions and function composition to operate on numbers.The lambda calculus uses a similar approach.Still others,including Markov algorithms and Post systems,use grammar-like rules to operate on strings.nAll of these formalisms were shown to be equivalent in computational power-that is,any computation that can be performed with one can be performed with any of the others.They are also equivalent in power to the familiar electronic computer,if one pretends that electronic computers have unbounded unbounded memory.nIndeed,it is widely believed that all proper formalizations of the concept of algorithm will be equivalent in power to Turing machines;this is known as the Church-Turing thesis.nIn general,questions of what can be computed by various machines are investigated in computability theory.3What is theory of computationnThe phrase theory of computation refers to the study of the mathematical foundations of computation:nwhat is an appropriate mathematical model of a computerer,what types of computations are possible in the model,what types are not,the inherent complexity of certain computations,so on and so forth.nPerhaps surprisingly,many concepts from the theory of computation are of fundamental importance in other areas of computer science,such as computational linguistics,compiler design,hardware design,object-oriented design,cryptography,and even the syntax of some UNIX commands.42 What the course is aboutnIn this course we will investigate various models of computation.Along the way,the intimate connection between computation and language recognition will be developed.nWe will study several classes of abstract machines including finite automata,push-down automata and Turing machines,along with several classes of languages such as context-free languages.In addition we will examine some of those problems,such as the Halting Problem.5What the course is aboutThe theory of computation represents a fascinating landscape that intersects交叉computer science and mathematics and can be roughly divided into three overlapping areas:AUTOMATA AND LANGUAGES,COMPUTABILITY THEORY,and COMPLEXITY THEORY.What are the fundamental What are the fundamental capabilitiescapabilities and and limitations limitations of computers?of computers?6COMPLEXITY THEORYnWhat makes some problems computationally hard and others easy?nThis is the central question of complexity theory.nResearchers have discovered an elegant scheme for classifying problems according to their computational difficulty.nIt is analogous to the periodic table(元素)周期表for classifying elements according to their chemical properties.7When you confront a problem that appears to be computationally hardnAlter it more easily solvablenTo settle for less than a perfect solution to the problem-finding approximate solutionnSome problems are hard only in the worst case situation,but easy most of the timenConsider alternative types computation,such as randomized computation8One applied area-cryptographynComplexity theory has pointed cryptographers in the direction of computationally hard problems around which they have designed revolutionary new codes.9COMPUTABILITY THEORYnCertain basic problems cannot be solved by computers.nThe problem of determining whether a mathematical statement is true or false.nWhat can computers do and what not?10One of profound results of COMPUTABILITY THEORYnThe development of ideas concerning theoretical models of computers that eventually would help lead to the construction of actual computers.11AUTOMATA THEORYnAUTOMATA THEORY deals with the definitions and properties of mathematical models of computation.nThese models play a role in several applied areas of computer science.nFinite automation text processing,compilers,hardware designnContext-free grammar programming languages,artificial intelligence.123 Course materialsnThe book for this class is Theory of Computation by Michael Sipser.nproof idea proof nexercises are similar to the worked out examples,and can be solved by following one of the presented examples,algorithms or theorems,nproblems require significant expository writing and deeper insight.nhttp:/www-math.mit.edu/sipser/nMassachusetts Institute of Technology(MIT)nThis term,we will use the textbook,as well as other books that students in the course have found useful in the past,such as Elements of the Theory of Computation by Harry R.Lewis&Christos H.Papadimitriou.134 PrerequisitesnWe assume that you have taken some mathematics for Computer Science,such as discrete mathematics.nNot on real numbers and continuous variables,but on finite sets and sequencesnand we assume that you are reasonably facile with mathematical concepts.nIn particular,we assume that you are comfortable with formal mathematical proofs,and can write them up properly.146 Student surveynMajor in computer sciencenThe design and analysis of algorithmsnDiscrete mathematics 157 What can we get from the coursenthe mathematical foundations of computationn3creditsnElsenEnglishGRE Subject Test 即即GRE(Graduate Record Examination)专项考试专项考试，其测试内容为考试者在某一学科领域或专业领域内所获得的知识和技能以及能力水平的高低，从而帮助院校更好地了解申请人在某一学科领域的能力情况。生物Biology，生化Biochemistry，化学Chemistry，计算机Computer Science，英语文学Literature In English，数学Math，物理Physics，心理学Psychology.