【正文】 Computational Complexity ? 常見的復(fù)雜度 ， 按照復(fù)雜度排序 ? O(1) :常數(shù)時間 ? O(logn) :次線性時間 ? O(n) :線性時間 ? O(nlogn):對數(shù)時間 ? O(n2 ) :平方時間 ? O(n3 ) :立方時間 ? 稱需要 O(nk)時間 （ k是一個常數(shù)）的問題為多項式復(fù)雜度問題（ polynomial plexity） ? O(2n ) : 指數(shù)時間 （ exponential plexity） ? 一個問題求解算法的時間復(fù)雜度大于多項式時間（如指數(shù)時間）時，算法的執(zhí)行時間將隨 n的增加而急劇增長，以致即使是中等規(guī)模的問題也不能求解出來，稱為難解問題 ? The origin of Artificial Intelligence ? ―Can machines think?‖ What is a ―machine‖ What is it to ―think‖ ? The Imitation Game Turing Test Player A Computer Player B Human Interrogator Human Room 1 Room 2 ? A human ―talks‖ to something and has to decide if it is a human of machine ? Can a machine simulate a person in a conversation in which other human elements, besides intelligence, are eliminated? ? Gee Boole – Boole提出將邏輯推理變?yōu)榇鷶?shù)運算 – 布爾代數(shù)是邏輯電路的數(shù)學(xué)工具 – 能得到多強的計算裝置？可否計算所有問題？ 可計算性問題（ Computability） ? Alan Turing – Turing Machine： 可計算性 ＝ 圖靈可計算性 – 計算的復(fù)雜性 問題 （現(xiàn)實的可計算性） – Turing Test： 機器可 否 模擬人的智力 Founders of Computing Theory ? History of Computing Machines ? What we can learn from Moore’s Law ? Founders of Computing Theory ? The Essential Issue of Computer Science ? Computing as a Discipline Introduction ? 計算科學(xué)的本質(zhì)： – 我國古代：對于一個數(shù)學(xué)問題，只有當(dāng)確定了其可用算盤解算它時，這個問題才算可解決。 ——“能性行”問題 – 圖靈用形式化的方法成功地表述了計算這一過程的本質(zhì)：計算就是計算者（人或機器）對一條兩端可無限延長的紙帶上的一串 0和1執(zhí)行命令，一步步改變紙帶上的 0或 1，經(jīng)過有限步驟，最后得到一個滿足預(yù)先規(guī)定的符號串的過程 – 圖靈的描述是關(guān)于數(shù)值計算的；字母、漢字、圖等均可用數(shù)表示；圖靈機同樣可以處理非數(shù)值計算 ? The Essential Issue of Computer Science： 什么能被（有效地）自動進行 – 能行問題的討論對象都是離散對象：計算學(xué)科依賴“離散結(jié)構(gòu)” – 計算學(xué)科所有分支領(lǐng)域的根本任務(wù)就是進行計算，其實質(zhì)就是進行字符串的變換 The Essential Issue of Computer Science ? Algorithm: a set of steps that defines how a task is performed The Fundamental Concept of CS: Algorithm ? The major goal is to find a single set of directions that described how any problem of a particular type could be solved The Fundamental Concept of CS: Algorithm ? In the domain of puting machinery, algorithms are represented as programs within puters Algorithms Hardware Software Programs Applications The Central Role of Algorithms in CS Algorithm Languages Software Engineering Data Manipulation OS Data Storage Data Structures File Structures Database Structures AI Theory of Computation ? History of Computing Machines ? What we can learn from Moore’s Law ? Founders of Computing Theory ? The Essential Issue of Computer Science ? Computing as a Discipline Introduction ? 1962, Purdue U. 計算機科學(xué)學(xué)位課程 – 計算機主要用于數(shù)值計算： 使用計算機僅僅是編程？ ? 計算機科學(xué)能否作為一門學(xué)科？ – 是工科還是理科？ – 只是一門技術(shù)？ ? 1985， ACM和 IEEE CS， 開始對“計算作為一門學(xué)科”的存在性證明 ? 1989，《 Communications of ACM》 : Computing as a Discipline Computing as a Discipline A summary is given of a report that had the following goals: ? to describe puter science in a way that emphasizes fundamental questions and significant acplishments。 ? to propose a teaching paradigm for puter science that conforms to traditional scientific standards, emphasizes the development of petence in the field, and harmoniously integrates theory, experimentation, and design。 ? to give a detailed example of an introductory course sequence in puter science that is based on the curriculum model and the disciplinary description. This task was extended to enpass both puter science and puter engineering. Computing as a Discipline 計算學(xué)科是對描述和變換信息的算法過程，包括對其理論、分析、設(shè)計、效率、實現(xiàn)和應(yīng)用等進行的系統(tǒng)研究。它來源于對算法理論、數(shù)理邏輯、計算模型、自動計算機器的研究，并與存儲式電子計算機的發(fā)明一起形成于 20世紀(jì) 40年代初。 計算學(xué)科的研究，包括從算法與可計算性的研究到根據(jù)可計算硬件和軟件的實際實現(xiàn)問題的研究。計算學(xué)科不但包括總體上對算法和信息處理過程進行研究的內(nèi)容，也包括滿足給定規(guī)格要求的有效而可靠的軟硬件設(shè)計 ——包括所有科目的理論研究、實驗方法和工程設(shè)計。 Computing as a Discipline 知識體系 概率與統(tǒng)計 正則語言 與自動機 數(shù)理邏輯 圖論 微積分 離散數(shù)學(xué) 線性代數(shù) 計算機原理 編譯原理 操作系統(tǒng) 算法研究 高級程序設(shè)計 數(shù)據(jù)結(jié)構(gòu) 人工智能 程序設(shè)計 Software 計算機網(wǎng)絡(luò) 體系結(jié)構(gòu) 數(shù)字邏輯與數(shù)字電路 普通物理 電子電路 Math 計算機科學(xué) Hardware