《计算理论导论(英文版)前言.ppt》由会员分享，可在线阅读，更多相关《计算理论导论(英文版)前言.ppt（15页珍藏版）》请在三一办公上搜索。
1、1,1 History of computation and computational models,For thousands of years,computing was done with pen and paper,chalk and slate,or even mentally,sometimes with the aid of tables.The theory of computation began early in the twentieth century(the 1930s),before modern electronic computers had been inv
2、ented.At that time,mathematicians were trying to find which math problems could be solved by simple methods and which could not.The 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.,2,computational models,Several diffe
3、rent computational models were devised by these early researchers.One model,the Turing 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 num
4、bers.The lambda calculus uses a similar approach.Still others,including Markov algorithms and Post systems,use grammar-like rules to operate on strings.All of these formalisms were shown to be equivalent in computational power-that is,any computation that can be performed with one can be performed w
5、ith any of the others.They are also equivalent in power to the familiar electronic computer,if one pretends that electronic computers have unbounded memory.Indeed,it is widely believed that all proper formalizations of the concept of algorithm will be equivalent in power to Turing machines;this is k
6、nown as the Church-Turing thesis.In general,questions of what can be computed by various machines are investigated in computability theory.,3,What is theory of computation,The phrase theory of computation refers to the study of the mathematical foundations of computation:what is an appropriate mathe
7、matical model of a computer,what types of computations are possible in the model,what types are not,the inherent complexity of certain computations,so on and so forth.Perhaps surprisingly,many concepts from the theory of computation are of fundamental importance in other areas of computer science,su
8、ch as computational linguistics,compiler design,hardware design,object-oriented design,cryptography,and even the syntax of some UNIX commands.,4,2 What the course is about,In this course we will investigate various models of computation.Along the way,the intimate connection between computation and l
9、anguage recognition will be developed.We 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 Prob
10、lem.,5,What the course is about,The 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 capabilit
11、ies and limitations of computers?,6,COMPLEXITY THEORY,What makes some problems computationally hard and others easy?This is the central question of complexity theory.Researchers have discovered an elegant scheme for classifying problems according to their computational difficulty.It is analogous to
12、the periodic table(元素)周期表for classifying elements according to their chemical properties.,7,When you confront a problem that appears to be computationally hard,Alter it more easily solvableTo settle for less than a perfect solution to the problem-finding approximate solutionSome problems are hard on
13、ly in the worst case situation,but easy most of the timeConsider alternative types computation,such as randomized computation,8,One applied area-cryptography,Complexity theory has pointed cryptographers in the direction of computationally hard problems around which they have designed revolutionary n
14、ew codes.,9,COMPUTABILITY THEORY,Certain basic problems cannot be solved by computers.The problem of determining whether a mathematical statement is true or false.,What can computers do and what not?,10,One of profound results of COMPUTABILITY THEORY,The development of ideas concerning theoretical m
15、odels of computers that eventually would help lead to the construction of actual computers.,11,AUTOMATA THEORY,AUTOMATA THEORY deals with the definitions and properties of mathematical models of computation.These models play a role in several applied areas of computer science.Finite automation text
16、processing,compilers,hardware designContext-free grammar programming languages,artificial intelligence.,12,3 Course materials,The book for this class is Theory of Computation by Michael Sipser.proof idea proof exercises are similar to the worked out examples,and can be solved by following one of the
17、 presented examples,algorithms or theorems,problems require significant expository writing and deeper insight.http:/www-math.mit.edu/sipser/Massachusetts Institute of Technology(MIT)This term,we will use the textbook,as well as other books that students in the course have found useful in the past,su
18、ch as Elements of the Theory of Computation by Harry R.Lewis&Christos H.Papadimitriou.,13,4 Prerequisites,We assume that you have taken some mathematics for Computer Science,such as discrete mathematics.Not on real numbers and continuous variables,but on finite sets and sequencesand we assume that y
19、ou are reasonably facile with mathematical concepts.In particular,we assume that you are comfortable with formal mathematical proofs,and can write them up properly.,14,6 Student survey,Major in computer scienceThe design and analysis of algorithmsDiscrete mathematics,15,7 What can we get from the co
20、urse,the mathematical foundations of computation3creditsElseEnglish,GRE Subject Test 即GRE(Graduate Record Examination)专项考试，其测试内容为考试者在某一学科领域或专业领域内所获得的知识和技能以及能力水平的高低，从而帮助院校更好地了解申请人在某一学科领域的能力情况。生物Biology，生化Biochemistry，化学Chemistry，计算机Computer Science，英语文学Literature In English，数学Math，物理Physics，心理学Psychology.,
