《计算机科学概论 课件Chap 12》由会员分享，可在线阅读，更多相关《计算机科学概论 课件Chap 12（19页珍藏版）》请在金锄头文库上搜索。
1、1-1 12-1 Chapter 12: Theory of Computation 1-2 12-2 Chapter 12: Theory of Computation 计算理论计算理论 12.1 Functions and Their Computation 12.2 Turing Machines 12.3 Universal Programming Languages 12.4 A Noncomputable Function 12.5 Complexity of Problems 12.6 Public-Key Cryptography 1-3 12-3 12.1 Functions
2、 and Their Computation Function(函数函数): A correspondence between a collection of possible input values and a collection of possible output values so that each possible input is assigned a single output 1-4 12-4 Functions (continued) Computing a function: Determining the output value associated with a
3、 given set of input values Noncomputable function: A function that cannot be computed by any algorithm 1-5 12-5 Figure 12.1 An attempt to display the function that converts measurements in yards into meters 1-6 Computable vs noncompulable the computation of these functions lies beyond the abilities
4、of any algorithmic system. These functions are said to be noncompulable, whereas the functions whose output values call be determined algorithmically from their input values are said to be computable. The study of computable and noncomputable functions is an important undertaking in computer science
5、. 12-6 1-7 12-7 12.2 Turing Machines 图灵机图灵机 Turing machines - are conceptual devices for studying the power of algorithmic processes. A Turing machine consists of a control unit that can read and write symbols on a tape The machine must be in one of a finite number of states(状态), start/halt states.
6、1-8 12-8 Figure 12.2 The components of a Turing machine 1-9 12-9 Turing Machine Operation Inputs at each step Current state Value at current tape position Actions at each step Write a value at current tape position Move read/write head Change state 1-10 12-10 Figure 12.3 A Turing machine for increme
7、nting a value Inputs Actions 1-11 12-11 Church-Turing Thesis The functions that are computable by a Turing machine are exactly the functions that can be computed by any algorithmic means. 1-12 12-12 12.5 Complexity of Problems 问题复杂性问题复杂性 Time Complexity: The number of instruction executions required
8、 Unless otherwise noted, “complexity” means “time complexity.” 1-13 12-13 Figure 12.11 Graphs of the mathematical expressions n, lg n, n lg n, and n2 1-14 Roadmap to Computer Science Study 计算机科学计算机科学与与技术技术（一级学科）（一级学科） 计算机系统结构（二级学科）计算机系统结构（二级学科） 计算机软件与理论（二级学科）计算机软件与理论（二级学科） 计算机应用技术（二级学科）计算机应用技术（二级学科）
9、 12-14 1-15 Roadmap to Computer Science Study Fundamental courses: Physics 物理学 Mathematics 数学 Advanced Mathematics 高数 Linear Algebra 线性代数 Probability Theory & Mathematical Statistics 概率与数理统计 Discrete Mathematics 离散数学 Abstract Algebra 抽象代数 Introduction to Computer Science 12-15 1-16 Roadmap to Comput
10、er Science Study Hardware: Fundamental Electronics 电子技术 Logic Design 数字逻辑 Digital System Design 系统设计 Computer Architecture. 计算机组成 System Embedded System 嵌入式系统 Microprocessors 微处理器 VLSI design. 超大规模集成电路设计 Storage Technology 存储技术 12-16 1-17 Roadmap to Computer Science Study Software: Fundamental: Prog
11、ramming Methodology 程序设计方法学 Data Structure 数据结构 Algorithm 算法分析与设计 Software Engineering 软件工程 Modeling 建模 Languages: Assembly Language 汇编语言 Programming Language (C) C+ JAVA XML 12-17 1-18 Roadmap to Computer Science Study Theory: Formal Language 形式化语言 Theory of Computation 计算理论 Database 数据库理论 Software
12、 Test 软件测试 System: Operating System 操作系统 Compiler 编译 Networking 网络 Embedded OS 嵌入式操作系统 Security 安全 12-18 1-19 Roadmap to Computer Science Study Applications: Wireless 无线网络 Multimedia 多媒体 E-business Platform 电子商务平台 Database Application 数据库应用 Education 计算机辅助教育 Artificial Intelligence 人工智能 Image Processing 图像处理 Graphics 图形学 Pattern Recognition 模式识别 Data Mining 数据挖掘 Bioinformatics 生物信息学 And more! 12-19
