計(jì)算機(jī)科學(xué)的本史元春-資料下載頁(yè)
2025-05-12 22:19本頁(yè)面
【正文】 Computational Complexity ? 常見(jiàn)的復(fù)雜度 ， 按照復(fù)雜度排序 ? O(1) :常數(shù)時(shí)間 ? O(logn) :次線(xiàn)性時(shí)間 ? O(n) :線(xiàn)性時(shí)間 ? O(nlogn):對(duì)數(shù)時(shí)間 ? O(n2 ) :平方時(shí)間 ? O(n3 ) :立方時(shí)間 ? 稱(chēng)需要 O(nk)時(shí)間 （ k是一個(gè)常數(shù)）的問(wèn)題為多項(xiàng)式復(fù)雜度問(wèn)題（ polynomial plexity） ? O(2n ) : 指數(shù)時(shí)間 （ exponential plexity） ? 一個(gè)問(wèn)題求解算法的時(shí)間復(fù)雜度大于多項(xiàng)式時(shí)間（如指數(shù)時(shí)間）時(shí)，算法的執(zhí)行時(shí)間將隨 n的增加而急劇增長(zhǎng)，以致即使是中等規(guī)模的問(wèn)題也不能求解出來(lái)，稱(chēng)為難解問(wèn)題 ? 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ù)運(yùn)算 – 布爾代數(shù)是邏輯電路的數(shù)學(xué)工具 – 能得到多強(qiáng)的計(jì)算裝置？可否計(jì)算所有問(wèn)題？ 可計(jì)算性問(wèn)題（ Computability） ? Alan Turing – Turing Machine： 可計(jì)算性 ＝ 圖靈可計(jì)算性 – 計(jì)算的復(fù)雜性 問(wèn)題 （現(xiàn)實(shí)的可計(jì)算性） – Turing Test： 機(jī)器可 否 模擬人的智力 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 ? 計(jì)算科學(xué)的本質(zhì)： – 我國(guó)古代：對(duì)于一個(gè)數(shù)學(xué)問(wèn)題，只有當(dāng)確定了其可用算盤(pán)解算它時(shí)，這個(gè)問(wèn)題才算可解決。 ——“能性行”問(wèn)題 – 圖靈用形式化的方法成功地表述了計(jì)算這一過(guò)程的本質(zhì)：計(jì)算就是計(jì)算者（人或機(jī)器）對(duì)一條兩端可無(wú)限延長(zhǎng)的紙帶上的一串 0和1執(zhí)行命令，一步步改變紙帶上的 0或 1，經(jīng)過(guò)有限步驟，最后得到一個(gè)滿(mǎn)足預(yù)先規(guī)定的符號(hào)串的過(guò)程 – 圖靈的描述是關(guān)于數(shù)值計(jì)算的；字母、漢字、圖等均可用數(shù)表示；圖靈機(jī)同樣可以處理非數(shù)值計(jì)算 ? The Essential Issue of Computer Science： 什么能被（有效地）自動(dòng)進(jìn)行 – 能行問(wèn)題的討論對(duì)象都是離散對(duì)象：計(jì)算學(xué)科依賴(lài)“離散結(jié)構(gòu)” – 計(jì)算學(xué)科所有分支領(lǐng)域的根本任務(wù)就是進(jìn)行計(jì)算，其實(shí)質(zhì)就是進(jìn)行字符串的變換 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. 計(jì)算機(jī)科學(xué)學(xué)位課程 – 計(jì)算機(jī)主要用于數(shù)值計(jì)算： 使用計(jì)算機(jī)僅僅是編程？ ? 計(jì)算機(jī)科學(xué)能否作為一門(mén)學(xué)科？ – 是工科還是理科？ – 只是一門(mén)技術(shù)？ ? 1985， ACM和 IEEE CS， 開(kāi)始對(duì)“計(jì)算作為一門(mén)學(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 計(jì)算學(xué)科是對(duì)描述和變換信息的算法過(guò)程，包括對(duì)其理論、分析、設(shè)計(jì)、效率、實(shí)現(xiàn)和應(yīng)用等進(jìn)行的系統(tǒng)研究。它來(lái)源于對(duì)算法理論、數(shù)理邏輯、計(jì)算模型、自動(dòng)計(jì)算機(jī)器的研究，并與存儲(chǔ)式電子計(jì)算機(jī)的發(fā)明一起形成于 20世紀(jì) 40年代初。 計(jì)算學(xué)科的研究，包括從算法與可計(jì)算性的研究到根據(jù)可計(jì)算硬件和軟件的實(shí)際實(shí)現(xiàn)問(wèn)題的研究。計(jì)算學(xué)科不但包括總體上對(duì)算法和信息處理過(guò)程進(jìn)行研究的內(nèi)容，也包括滿(mǎn)足給定規(guī)格要求的有效而可靠的軟硬件設(shè)計(jì) ——包括所有科目的理論研究、實(shí)驗(yàn)方法和工程設(shè)計(jì)。 Computing as a Discipline 知識(shí)體系 概率與統(tǒng)計(jì) 正則語(yǔ)言 與自動(dòng)機(jī) 數(shù)理邏輯 圖論 微積分 離散數(shù)學(xué) 線(xiàn)性代數(shù) 計(jì)算機(jī)原理 編譯原理 操作系統(tǒng) 算法研究 高級(jí)程序設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu) 人工智能 程序設(shè)計(jì) Software 計(jì)算機(jī)網(wǎng)絡(luò) 體系結(jié)構(gòu) 數(shù)字邏輯與數(shù)字電路 普通物理 電子電路 Math 計(jì)算機(jī)科學(xué) Hardware
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1