學(xué)計(jì)算機(jī)基礎(chǔ)課件分解

1、Chapter 9高 級(jí) 主 題CS, ZJU10/11/2022Chapter 9高 級(jí) 主 題CS, ZJUOverview高性能計(jì)算人工智能虛擬現(xiàn)實(shí)自動(dòng)機(jī)理論可計(jì)算理論信息安全信息社會(huì)Overview高性能計(jì)算9.1 高性能計(jì)算高性能計(jì)算HPC ，High Performance Computing是計(jì)算機(jī)科學(xué)的一個(gè)分支，旨在研究復(fù)雜體系結(jié)構(gòu)、算法和開(kāi)發(fā)相關(guān)軟件，致力于開(kāi)發(fā)高性能計(jì)算機(jī)并行計(jì)算分布式計(jì)算集群計(jì)算云計(jì)算9.1 高性能計(jì)算高性能計(jì)算HPC ，High Perfor1.并行計(jì)算并行計(jì)算（Parallel Computing）傳統(tǒng)意義上是指計(jì)算資源應(yīng)包括一臺(tái)配有多處理機(jī)（并行處理

2、）的計(jì)算機(jī)具有超級(jí)計(jì)算能力的計(jì)算機(jī)系統(tǒng)，這是獲得高性能計(jì)算的重要手段今天，并行計(jì)算也是指一個(gè)通過(guò)網(wǎng)絡(luò)連接的計(jì)算機(jī)群，或者兩者結(jié)合使用在過(guò)去很長(zhǎng)一段時(shí)間內(nèi)，并行計(jì)算幾乎就是HPC的代名詞 1.并行計(jì)算并行計(jì)算（Parallel Computing）并行計(jì)算1980年代，并行計(jì)算機(jī)系統(tǒng)（多處理器同時(shí)對(duì)一組數(shù)據(jù)進(jìn)行同一個(gè)操作）達(dá)到了鼎盛時(shí)期90年代，超大規(guī)模并行計(jì)算（Massively Parallel Processing，MPP）開(kāi)始占主導(dǎo)地位對(duì)稱(chēng)多處理器（Symmetric Multi-Processor，SMP）結(jié)構(gòu)的并行系統(tǒng)1993年成立的Top500機(jī)構(gòu)開(kāi)始進(jìn)行全球高性能計(jì)算機(jī)系統(tǒng)排名并

3、行計(jì)算1980年代，并行計(jì)算機(jī)系統(tǒng)（多處理器同時(shí)對(duì)一組數(shù)據(jù)并行計(jì)算據(jù)2005年11月Top500公布的數(shù)據(jù)排名第一的Blue Gene /L系統(tǒng)IBM公司處理速度達(dá)到280.6 TFlop/s（每秒萬(wàn)億次浮點(diǎn)運(yùn)算），系統(tǒng)有131,072個(gè)處理器我國(guó)曙光公司生產(chǎn)的曙光4000A超級(jí)計(jì)算機(jī)，在2004年Top500中躋身前十名，標(biāo)志著我國(guó)高性能計(jì)算進(jìn)入世界先進(jìn)水平中國(guó)聯(lián)想集團(tuán)生產(chǎn)的深騰6800高性能計(jì)算機(jī)系統(tǒng)也達(dá)到了10TFlop/s級(jí)并行計(jì)算據(jù)2005年11月Top500公布的數(shù)據(jù)曙光5超級(jí)計(jì)算機(jī) 百萬(wàn)億次/秒曙光5超級(jí)計(jì)算機(jī) 百萬(wàn)億次/秒%中國(guó)天河計(jì)算機(jī)日本“京”計(jì)算機(jī)%中國(guó)天河計(jì)算機(jī)日本“京

4、”計(jì)算機(jī)世界超級(jí)計(jì)算機(jī)排名據(jù)國(guó)外媒體報(bào)道，在兩年一次的世界上最強(qiáng)力的超級(jí)計(jì)算機(jī)排名中,中國(guó)仍然占據(jù)著榜首排名中的所有500臺(tái)超級(jí)計(jì)算機(jī)，總的計(jì)算能力達(dá)到每秒250千萬(wàn)億次的浮點(diǎn)運(yùn)算速度，其中排名前17的超級(jí)計(jì)算機(jī)的計(jì)算能力就占了一半，并且有31臺(tái)超級(jí)計(jì)算機(jī)的計(jì)算速度達(dá)到了1千萬(wàn)億次以上世界超級(jí)計(jì)算機(jī)排名據(jù)國(guó)外媒體報(bào)道，在兩年一次的世界上最強(qiáng)力的天河二號(hào)2013.11.20：“天河二號(hào)”超級(jí)計(jì)算機(jī)的每秒33.86千萬(wàn)億次的浮點(diǎn)計(jì)算能力，是第二名美國(guó)泰坦超級(jí)計(jì)算機(jī)接近2倍遺憾只有18的CPU是自主知識(shí)產(chǎn)權(quán)（超算CPU非常多）其余的是購(gòu)買(mǎi)的進(jìn)口產(chǎn)品，但是值得關(guān)注的是采用了國(guó)產(chǎn)麒麟系統(tǒng)天河二號(hào)2013

5、.11.20：“天河二號(hào)”超級(jí)計(jì)算機(jī)的每秒3天河二號(hào)天河二號(hào)IBM公司64枚處理器芯片的計(jì)算機(jī)主板IBM公司64枚處理器芯片的計(jì)算機(jī)主板2.分布式計(jì)算 分布式系統(tǒng)研究組件的異構(gòu)性、開(kāi)放性、安全性和可伸縮性、并發(fā)性、透明性及故障處理分布式計(jì)算的主題是多種多樣的，包括分布式硬件結(jié)構(gòu)和分布式軟件設(shè)計(jì)一個(gè)分布式系統(tǒng)是為解決單個(gè)問(wèn)題而緊密結(jié)合在一起工作的多處理機(jī)的集合Or，一個(gè)分布式系統(tǒng)可能意味著一個(gè)由地理上分散的、各自獨(dú)立的計(jì)算機(jī)組成的網(wǎng)絡(luò)，這些計(jì)算機(jī)連接在一起以實(shí)現(xiàn)對(duì)不同資源的共享2.分布式計(jì)算 分布式系統(tǒng)研究組件的異構(gòu)性、開(kāi)放性、安全分布式計(jì)算分布式系統(tǒng)這個(gè)詞義方面的混亂源于對(duì)物理的分布和邏輯的分

6、布的區(qū)分分布式技術(shù)和網(wǎng)絡(luò)技術(shù)之間的相互滲透和交融更多的觀點(diǎn)認(rèn)為，分布式系統(tǒng)：邏輯或物理分布的部件或機(jī)器，以網(wǎng)絡(luò)連接的形式組成的一個(gè)（計(jì)算機(jī)）系統(tǒng)并行意義的根本是將兩臺(tái)以上的機(jī)器（處理器）連接起來(lái)解決一些計(jì)算問(wèn)題 分布式計(jì)算分布式系統(tǒng)這個(gè)詞義方面的混亂3.集群計(jì)算集群計(jì)算（Cluster Computing）也是基于并行系統(tǒng)和網(wǎng)絡(luò)的它作為并行計(jì)算和網(wǎng)絡(luò)技術(shù)在高性能計(jì)算機(jī)體系結(jié)構(gòu)中最為成功的集成和運(yùn)用，也是目前性?xún)r(jià)比最好的系統(tǒng)在2005年11月的Top500中，集群系統(tǒng)占到了70以上3.集群計(jì)算集群計(jì)算（Cluster Computing）集群系統(tǒng)集群系統(tǒng)是以高速網(wǎng)絡(luò)（如光纜局域網(wǎng)）連接起來(lái)的高性

7、能工作站或微機(jī)組成集群系統(tǒng)在運(yùn)行中像一個(gè)統(tǒng)一的整合資源，所有節(jié)點(diǎn)使用單一的界面本質(zhì)上說(shuō)，集群是一種并行或者分布式系統(tǒng) 集群的同義詞是工作站網(wǎng)絡(luò)（Network of Workstation，NOW） 集群系統(tǒng)集群系統(tǒng)是以高速網(wǎng)絡(luò)（如光纜局域網(wǎng)）連接起來(lái)的高集群系統(tǒng)集群系統(tǒng)最廉價(jià)的高性能計(jì)算機(jī)系統(tǒng)主要原因：（1）微機(jī)或工作站的性能越來(lái)越強(qiáng)（2）LAN特別是高速光纖LAN延遲越來(lái)越小，網(wǎng)絡(luò)帶寬增加（3）工作站網(wǎng)絡(luò)易于集成，和現(xiàn)有的網(wǎng)絡(luò)更容易整合（4）相比大型并行系統(tǒng)，微機(jī)或工作站的開(kāi)發(fā)工具更成熟，而且更易于被大批專(zhuān)業(yè)人員掌握（5）工作站和微機(jī)系統(tǒng)標(biāo)準(zhǔn)化程度高（6）集群系統(tǒng)采用的平臺(tái)便宜而且易于獲得

8、，如Unix、Linux和Windows Server都可以作為集群系統(tǒng)的平臺(tái)集群系統(tǒng)集群系統(tǒng)最廉價(jià)的高性能計(jì)算機(jī)系統(tǒng)4.云計(jì)算分布式計(jì)算、網(wǎng)格計(jì)算、普適計(jì)算發(fā)展而來(lái)云計(jì)算（無(wú)處不在的計(jì)算）云因特網(wǎng)效用計(jì)算計(jì)費(fèi)，像電網(wǎng)的用電付費(fèi)云產(chǎn)業(yè)（云軟件、云平臺(tái)、云設(shè)備）計(jì)算機(jī)基礎(chǔ)科學(xué)184.云計(jì)算分布式計(jì)算、網(wǎng)格計(jì)算、普適計(jì)算發(fā)展而來(lái)云計(jì)算（9.2人工智能人工智能作為計(jì)算機(jī)研究的重要領(lǐng)域，已經(jīng)成為計(jì)算機(jī)科學(xué)和技術(shù)發(fā)展的一個(gè)目標(biāo)。圖靈測(cè)試-計(jì)算機(jī)能夠象人一樣思考嗎 ？中國(guó)屋思考實(shí)驗(yàn)-反駁圖靈測(cè)試推理：知識(shí)表達(dá)語(yǔ)義網(wǎng)絡(luò)搜索樹(shù)-深藍(lán)9.2人工智能人工智能作為計(jì)算機(jī)研究的重要領(lǐng)域，已經(jīng)成為1.圖靈測(cè)試:“計(jì)算機(jī)

9、能夠象人一樣思考嗎？”圖靈測(cè)試黑盒測(cè)試測(cè)試者和被測(cè)者之間用幕布隔開(kāi)，發(fā)問(wèn)者不知道對(duì)面回答問(wèn)題的人是誰(shuí)圖靈測(cè)試本身也被人提出了疑問(wèn) 中國(guó)屋思考試驗(yàn)塞爾認(rèn)為：機(jī)器不能思考，它只是一個(gè)工具，符號(hào)識(shí)別不能夠滿(mǎn)足語(yǔ)義，只有大腦能引起思考 現(xiàn)在還沒(méi)有機(jī)器通過(guò)圖靈測(cè)試，關(guān)于機(jī)器思考的爭(zhēng)論還在持續(xù)，但計(jì)算機(jī)科學(xué)家并沒(méi)有停止或者放棄對(duì)AI的研究，相反地這種爭(zhēng)論促進(jìn)了AI的研究進(jìn)展1.圖靈測(cè)試:“計(jì)算機(jī)能夠象人一樣思考嗎？”圖靈測(cè)試黑盒學(xué)計(jì)算機(jī)基礎(chǔ)課件分解2. 推理：知識(shí)表達(dá)人工智能一直在研究計(jì)算機(jī)的推理能力 人類(lèi)智能是基于行為的進(jìn)化而不是復(fù)雜程序的執(zhí)行 解決問(wèn)題需要有效信息，有效信息還需要有效表達(dá) 計(jì)算機(jī)使用符

10、號(hào)語(yǔ)言科學(xué)家們?cè)噲D在人類(lèi)的自然語(yǔ)言和機(jī)器的符號(hào)處理之間找到一種關(guān)系，使得機(jī)器能夠具有人類(lèi)的推理能力語(yǔ)義網(wǎng)絡(luò)是一種知識(shí)表達(dá)法定義它非常困難相比語(yǔ)義網(wǎng)絡(luò)，搜索樹(shù)易于實(shí)現(xiàn) 2. 推理：知識(shí)表達(dá)人工智能一直在研究計(jì)算機(jī)的推理能力 3.專(zhuān)家系統(tǒng)一種智能計(jì)算機(jī)軟件系統(tǒng)，像領(lǐng)域?qū)＜夷菢酉蛴脩?hù)提供解決問(wèn)題的方法四個(gè)要素：應(yīng)用于某專(zhuān)門(mén)領(lǐng)域 擁有專(zhuān)家級(jí)知識(shí) 能模擬專(zhuān)家的思維 能達(dá)到專(zhuān)家級(jí)水平 3.專(zhuān)家系統(tǒng)一種智能計(jì)算機(jī)軟件系統(tǒng)，像領(lǐng)域?qū)＜夷菢酉蛴脩?hù)提供4.神經(jīng)網(wǎng)絡(luò)由大量處理單元（神經(jīng)元、處理元件、電子元件、光電元件等）廣泛互連的網(wǎng)絡(luò)高度非線(xiàn)性的超大規(guī)模的連續(xù)時(shí)間動(dòng)力系統(tǒng)具有大規(guī)模并行分布處理及學(xué)習(xí)能力具有非線(xiàn)性動(dòng)

11、力系統(tǒng)的共性具有不可預(yù)測(cè)性、吸引性、耗散性、不可逆性、高維性、廣泛連接性和自適應(yīng)性等特點(diǎn)4.神經(jīng)網(wǎng)絡(luò)由大量處理單元（神經(jīng)元、處理元件、電子元件、光電神經(jīng)網(wǎng)絡(luò)25人工神經(jīng)元模型 其中： xi為輸入信號(hào)，ui表示神經(jīng)元的內(nèi)部狀態(tài)，i為閾值。si為外部輸入信號(hào)，si可對(duì)神經(jīng)元ui進(jìn)行控制 神經(jīng)網(wǎng)絡(luò)25人工神經(jīng)元模型 其中： xi為輸入信號(hào)，ui表示5.機(jī)器人綜合了人和機(jī)器特長(zhǎng)的一種擬人化的電子機(jī)械裝置，它既有人對(duì)環(huán)境狀態(tài)的快速反應(yīng)和分析判斷能力，又有機(jī)器可長(zhǎng)時(shí)間持續(xù)工作、精確度高、抗惡劣環(huán)境的能力“大腦”：嵌入式處理器機(jī)器人視覺(jué)系統(tǒng)接近覺(jué)傳感器機(jī)器人語(yǔ)言265.機(jī)器人綜合了人和機(jī)器特長(zhǎng)的一種擬人化的

12、電子機(jī)械裝置，它既Robot機(jī)器人裝有所需要的傳感器視覺(jué)傳感器，為機(jī)器人移動(dòng)進(jìn)行導(dǎo)航接近覺(jué)系統(tǒng)，探測(cè)自身與周?chē)矬w之間相對(duì)位置和距離的傳感器機(jī)器人語(yǔ)言 ，實(shí)現(xiàn)與人的聯(lián)系智能機(jī)器人在研究階段 Robot機(jī)器人裝有所需要的傳感器6.自然語(yǔ)言處理語(yǔ)音識(shí)別自然語(yǔ)言理解語(yǔ)音合成最新的進(jìn)展：IBM公司的智能計(jì)算機(jī)“沃森”6.自然語(yǔ)言處理語(yǔ)音識(shí)別自然語(yǔ)言處理嘗試使用自然語(yǔ)言和計(jì)算機(jī)對(duì)話(huà)IBM的Voice系統(tǒng) 依據(jù)規(guī)則進(jìn)行處理 最困難的是自然語(yǔ)言的理解 自然語(yǔ)言特有的二義性 理解單詞的意義需要根據(jù)上下文 理解自然語(yǔ)言，人類(lèi)需要依賴(lài)他們所具有的知識(shí)和聯(lián)想記憶力 自然語(yǔ)言理解需要進(jìn)行語(yǔ)法分析、語(yǔ)義分析和上下文分析

13、自然語(yǔ)言處理研究的另一個(gè)方面是整個(gè)文件而不是一個(gè)句子 機(jī)器翻譯 ？自然語(yǔ)言處理嘗試使用自然語(yǔ)言和計(jì)算機(jī)對(duì)話(huà)學(xué)計(jì)算機(jī)基礎(chǔ)課件分解7.人工智能的研究困難圖靈機(jī)的啟示計(jì)算機(jī)博奕的困難 自動(dòng)定理證明及其局限 模式識(shí)別的困惑 自動(dòng)程序設(shè)計(jì)的困難 317.人工智能的研究困難圖靈機(jī)的啟示319.3虛擬現(xiàn)實(shí)虛擬現(xiàn)實(shí)（VR）或稱(chēng)虛擬環(huán)境（VE） ：由計(jì)算機(jī)生成的、使人具有身臨其境感覺(jué)的計(jì)算機(jī)模擬環(huán)境，它是一種全新的人機(jī)交互系統(tǒng)虛擬環(huán)境能對(duì)介入者人產(chǎn)生各種感官刺激，如視覺(jué)、聽(tīng)覺(jué)、觸覺(jué)、嗅覺(jué)等，同時(shí)人能以自然方式與虛擬環(huán)境進(jìn)行交互操作VR強(qiáng)調(diào)作為介入者人的親身體驗(yàn)，要求虛擬環(huán)境是可信的，即虛擬環(huán)境與人對(duì)其理解相一致

14、9.3虛擬現(xiàn)實(shí)虛擬現(xiàn)實(shí)（VR）或稱(chēng)虛擬環(huán)境（VE） ：由虛擬現(xiàn)實(shí)虛擬現(xiàn)實(shí)的概念模型可看做“顯示檢測(cè)”模型顯示是指虛擬環(huán)境系統(tǒng)向用戶(hù)提供各種感官刺激信號(hào)，包括光、聲、力、嗅、味等各種刺激信號(hào)檢測(cè)是指虛擬環(huán)境系統(tǒng)監(jiān)視用戶(hù)的各種動(dòng)作，檢測(cè)并辨識(shí)用戶(hù)的視點(diǎn)變化，頭、手、肢體和身軀的動(dòng)作虛擬現(xiàn)實(shí)虛擬現(xiàn)實(shí)的概念模型可看做“顯示檢測(cè)”模型9.4自動(dòng)機(jī)理論自動(dòng)機(jī)理論是對(duì)抽象（計(jì)算）機(jī)和它們能解決的問(wèn)題的研究。多種自動(dòng)機(jī)模型：有限自動(dòng)機(jī)：基于離散系統(tǒng)的抽象數(shù)據(jù)模型圖靈機(jī)：圖靈提出的一個(gè)自動(dòng)機(jī)模型，用于解釋機(jī)器的計(jì)算能力及其局限性。是算法研究的重要工具細(xì)胞自動(dòng)機(jī)：離散模型，在自動(dòng)機(jī)理論、數(shù)學(xué)及理論生物學(xué)方面有其研

15、究和應(yīng)用。源于科學(xué)家對(duì)生物細(xì)胞的自我復(fù)制的模仿，馮諾依曼提出。9.4自動(dòng)機(jī)理論自動(dòng)機(jī)理論是對(duì)抽象（計(jì)算）機(jī)和它們能解決的有限自動(dòng)機(jī)基于離散系統(tǒng)的抽象數(shù)據(jù)模型計(jì)算機(jī)中的加法器、計(jì)數(shù)器、操作系統(tǒng)等活動(dòng)過(guò)程都是離散系統(tǒng)的實(shí)例有限自動(dòng)機(jī)主要研究系統(tǒng)的綜合和分析，給出具體的功能要求，設(shè)計(jì)能夠?qū)崿F(xiàn)其功能的有限自動(dòng)機(jī)，分析有限自動(dòng)機(jī)的功能描述、時(shí)間復(fù)雜性和故障傳播與檢測(cè)等有限自動(dòng)機(jī)基于離散系統(tǒng)的抽象數(shù)據(jù)模型9.5可計(jì)算理論可計(jì)算問(wèn)題計(jì)算機(jī)能做什么，計(jì)算機(jī)不能做什么？可計(jì)算函數(shù)哥德?tīng)枖?shù)計(jì)算復(fù)雜性停機(jī)問(wèn)題9.5可計(jì)算理論可計(jì)算問(wèn)題1.可計(jì)算函數(shù)計(jì)算是與算法關(guān)聯(lián)的，可計(jì)算理論算法理論算法實(shí)質(zhì)的研究對(duì)算法概念的精確

16、化研究把計(jì)算機(jī)看作抽象的機(jī)器，算法就是執(zhí)行的程序可計(jì)算問(wèn)題能夠被抽象計(jì)算機(jī)計(jì)算其值的問(wèn)題可計(jì)算函數(shù)是其中研究的一個(gè)方面如果函數(shù)能夠通過(guò)算法得到函數(shù)值，則稱(chēng)函數(shù)是可計(jì)算的(Computable)1.可計(jì)算函數(shù)計(jì)算是與算法關(guān)聯(lián)的，可計(jì)算理論算法理論2.哥德?tīng)枖?shù)哥德?tīng)枺↘urt Godel）是繼牛頓之后的最偉大的數(shù)學(xué)家和邏輯學(xué)家哥德?tīng)柌煌陚涠ɡ砀绲聽(tīng)枖?shù)程序設(shè)計(jì)語(yǔ)言的符號(hào)被能夠分配一個(gè)對(duì)應(yīng)的無(wú)符號(hào)數(shù)，這個(gè)數(shù)就是哥德?tīng)枖?shù)計(jì)算機(jī)語(yǔ)言是復(fù)雜的，已經(jīng)證明：只要簡(jiǎn)單的3條語(yǔ)句就可以描述所有的程序Incr(加1運(yùn)算)、decr(減1運(yùn)算)、while(循環(huán))轉(zhuǎn)換：程序哥德?tīng)枖?shù)2.哥德?tīng)枖?shù)哥德?tīng)枺↘urt Gode

17、l）是繼牛頓之后的最偉哥德?tīng)枖?shù) 程序設(shè)計(jì)語(yǔ)言的符號(hào)能夠被分配一個(gè)對(duì)應(yīng)的無(wú)符號(hào)數(shù)符號(hào)十六進(jìn)制數(shù)符號(hào)十六進(jìn)制數(shù)符號(hào)十六進(jìn)制數(shù)符號(hào)十六進(jìn)制數(shù)004488whileC115599D2266incrAE3377decrBXF1程序轉(zhuǎn)換為哥德?tīng)枖?shù) 例：incr(X) incrX AFH 175 2哥德?tīng)枖?shù)轉(zhuǎn)換為程序 例：3058 BF2H decrX2 decr(X2) 哥德?tīng)枖?shù) 程序設(shè)計(jì)語(yǔ)言的符號(hào)能夠被分配一個(gè)對(duì)應(yīng)的無(wú)符號(hào)數(shù)符哥德?tīng)枖?shù) P.1831程序轉(zhuǎn)換為哥德?tīng)枖?shù) while x1 /如果x1不等于0，則執(zhí)行下面的循環(huán)decr x1 incr x2 CF1DBF1AF2EH14232916700974

18、2哥德?tīng)枖?shù)轉(zhuǎn)換為程序 例：13622270CFDBFEH while xdecr x / 將變量x置0哥德?tīng)枖?shù) P.1831程序轉(zhuǎn)換為哥德?tīng)枖?shù)阿克曼函數(shù)遞歸函數(shù)，計(jì)算機(jī)中許多算法都可以歸結(jié)為遞歸問(wèn)題原始遞歸函數(shù)可以通過(guò)有限次的、可計(jì)算的函數(shù)，在原始遞歸函數(shù)和某些程序設(shè)計(jì)語(yǔ)言之間存在對(duì)應(yīng)關(guān)系.阿克曼函數(shù)是一種非原始遞歸函數(shù)，使用兩個(gè)自然數(shù)作為輸入值，輸出也是一個(gè)自然數(shù)，輸出值隨著輸入值增大而急劇增大。 n+1 若m=0A(m,n)= A(m-1,1) 若m0且n=0 A(m-1,A(m,n-1) 若m0且n0雙重遞歸阿克曼函數(shù)遞歸函數(shù)，計(jì)算機(jī)中許多算法都可以歸結(jié)為遞歸問(wèn)題3.計(jì)算復(fù)雜性復(fù)雜性的度

19、量定量描述算法的復(fù)雜程度完成計(jì)算（算法）所需要的時(shí)間和存儲(chǔ)器資源大O表示法：主要考慮其數(shù)量級(jí)而不是精確值對(duì)于n個(gè)輸入的算法 C，復(fù)雜性表示為： f(n,C)=n2+2n當(dāng)n足夠大時(shí)2n可忽略O(shè)(n)表示有n個(gè)輸入的算法，執(zhí)行 n 次運(yùn)算O(n2)表示有n個(gè)輸入的算法，執(zhí)行 n2 次運(yùn)算3.計(jì)算復(fù)雜性復(fù)雜性的度量計(jì)算復(fù)雜性大O表示法選擇法排序，復(fù)雜度 O(n2) n個(gè)數(shù)排序的次數(shù)為 n(n-1)/2，即0.5n2-0.5n快速排序法，復(fù)雜度為 O(nlogn)比較 n=1 000 000，使用運(yùn)算速度為每秒100萬(wàn)次的計(jì)算機(jī)O(logn)O(n)O(n2)Times: 6 s Times: 1

20、000 000 s Times: 1012 s 1s277h計(jì)算復(fù)雜性大O表示法Times: 6 s 1s277h計(jì)算復(fù)雜性在計(jì)算機(jī)科學(xué)領(lǐng)域，將問(wèn)題分為：不可解問(wèn)題的確無(wú)解，如停機(jī)問(wèn)題雖然有解，但時(shí)間復(fù)雜度很高可解問(wèn)題P問(wèn)題（多項(xiàng)式問(wèn)題）NP問(wèn)題（非確定性多項(xiàng)式問(wèn)題）計(jì)算復(fù)雜性在計(jì)算機(jī)科學(xué)領(lǐng)域，將問(wèn)題分為：計(jì)算復(fù)雜性P問(wèn)題有多項(xiàng)式的時(shí)間解可在多項(xiàng)式表達(dá)的有限時(shí)間內(nèi)解決算法的復(fù)雜度大O值是輸入數(shù)量n的多項(xiàng)式如：O(n2) O(nlogn)P問(wèn)題包含大量的已知的自然問(wèn)題如：判斷素?cái)?shù)、計(jì)算最大公約數(shù)、計(jì)算PI值、計(jì)算e值、排序問(wèn)題、二維匹配問(wèn)題P問(wèn)題是是可解的，是區(qū)別問(wèn)題是否可以被計(jì)算機(jī)求解的一個(gè)重

21、要標(biāo)志計(jì)算復(fù)雜性P問(wèn)題計(jì)算復(fù)雜性P問(wèn)題算法的復(fù)雜度不能使用確定的多項(xiàng)式來(lái)表示通常它們的時(shí)間復(fù)雜度是指數(shù)變量如：O(10n)O(n!)最短路徑問(wèn)題，O(2n)，n是途經(jīng)城市的數(shù)量通俗地稱(chēng)所有復(fù)雜度為多項(xiàng)式時(shí)間的問(wèn)題為易解的問(wèn)題類(lèi)，否則為難解(Intractable)的問(wèn)題計(jì)算復(fù)雜性P問(wèn)題4.停機(jī)問(wèn)題（Halting problem）停機(jī)問(wèn)題：是否有一個(gè)程序T能夠預(yù)測(cè)任何一個(gè)程序的執(zhí)行是否會(huì)停機(jī)結(jié)論：沒(méi)有一個(gè)程序T能夠測(cè)試用哥德?tīng)枖?shù)表示的程序是否會(huì)終止，也就是說(shuō)，預(yù)測(cè)程序是否被終止是不可能的停機(jī)問(wèn)題是不可計(jì)算的while x incr x;如果存在一個(gè)停機(jī)函數(shù)，那么這個(gè)函數(shù)是不可計(jì)算的4.停機(jī)問(wèn)題

22、（Halting problem）停機(jī)問(wèn)題：是否9.6 信息安全信息安全工程 研究各種防止安全事故的發(fā)生和各種攻擊、入侵事件的發(fā)生。前者需要的是一種有效的組織管理進(jìn)制，而后者的主要研究?jī)?nèi)容是安全協(xié)議。 核心：安全協(xié)議的研究建立有效的組織機(jī)制9.6 信息安全信息安全工程計(jì)算機(jī)與安全威脅計(jì)算機(jī)安全的主要因素：災(zāi)難系統(tǒng)缺陷病毒黑客攻擊等 計(jì)算機(jī)與安全威脅計(jì)算機(jī)安全的主要因素：1.計(jì)算機(jī)安全工程計(jì)算機(jī)和網(wǎng)絡(luò)安全所依賴(lài)的技術(shù)基礎(chǔ)主要是密碼學(xué)、可靠性技術(shù)、安全印刷和認(rèn)證、審計(jì)等 安全工程的本質(zhì)在于了解系統(tǒng)的潛在威脅，然后選擇適當(dāng)?shù)拇胧﹣?lái)控制這些威脅因素 安全工程的核心是安全協(xié)議的研究計(jì)算機(jī)安全工程中的重要

23、基礎(chǔ)是口令 1.計(jì)算機(jī)安全工程計(jì)算機(jī)和網(wǎng)絡(luò)安全所依賴(lài)的技術(shù)基礎(chǔ)計(jì)算機(jī)系統(tǒng)風(fēng)險(xiǎn)硬件風(fēng)險(xiǎn)容錯(cuò)的計(jì)算機(jī)系統(tǒng)Fault-tolerant Computer System軟件風(fēng)險(xiǎn)軟件測(cè)試Software Testing計(jì)算機(jī)系統(tǒng)風(fēng)險(xiǎn)硬件風(fēng)險(xiǎn)2.計(jì)算機(jī)病毒計(jì)算機(jī)病毒(Computer Virus) “編制或者在計(jì)算機(jī)程序中插入的破壞計(jì)算機(jī)功能或者破壞數(shù)據(jù)，影響計(jì)算機(jī)使用并且能夠自我復(fù)制的一組計(jì)算機(jī)指令或者程序代碼?！?中華人民共和國(guó)計(jì)算機(jī)信息系統(tǒng)安全保護(hù)條例這種程序代碼或指令段具有傳染性、破壞性、潛伏性以及自我復(fù)制能力，類(lèi)似于微生物學(xué)中的病毒故而得名。2.計(jì)算機(jī)病毒計(jì)算機(jī)病毒(Computer Virus

24、) 病毒種類(lèi)常見(jiàn)的計(jì)算機(jī)病毒：宏病毒一種寄存在文檔或模板的宏中的計(jì)算機(jī)病毒 寄生型病毒一種感染可執(zhí)行文件的程序 蠕蟲(chóng)病毒能夠自我復(fù)制的計(jì)算機(jī)程序，雖然它并不感染其他文件，通過(guò)分布式網(wǎng)絡(luò)來(lái)擴(kuò)散傳播特定的信息或錯(cuò)誤，使網(wǎng)絡(luò)流量大大增加進(jìn)而造成網(wǎng)絡(luò)服務(wù)遭到拒絕并發(fā)生死鎖黑客病毒一種能夠散布病毒蠕蟲(chóng)或其他惡意程序的計(jì)算機(jī)程序。 25/53病毒種類(lèi)常見(jiàn)的計(jì)算機(jī)病毒：25/533.反病毒軟件的機(jī)制反病毒軟件發(fā)展歷程：簡(jiǎn)單的病毒掃描（Scan）程序啟發(fā)式的掃描程序行為陷阱全方位的保護(hù)主要技術(shù)：尋找病毒的特征碼 3.反病毒軟件的機(jī)制反病毒軟件發(fā)展歷程：4.黑客現(xiàn)在黑客常指專(zhuān)門(mén)利用計(jì)算機(jī)犯罪的人防御手段：實(shí)體安

25、全防范，包括機(jī)房、網(wǎng)絡(luò)服務(wù)器、線(xiàn)路和主機(jī)等對(duì)系統(tǒng)進(jìn)行全天候的動(dòng)態(tài)監(jiān)控加強(qiáng)基礎(chǔ)安全防范，主要包括授權(quán)認(rèn)證、數(shù)據(jù)加密和信息傳輸加密，防火墻設(shè)置等4.黑客現(xiàn)在黑客常指專(zhuān)門(mén)利用計(jì)算機(jī)犯罪的人5.防火墻為了防止非法訪問(wèn)而設(shè)置的“屏障”；通過(guò)硬件實(shí)現(xiàn)；通過(guò)軟件實(shí)現(xiàn)；5.防火墻為了防止非法訪問(wèn)而設(shè)置的“屏障”；9.7 信息社會(huì)社會(huì)影響自第一臺(tái)計(jì)算機(jī)誕生至今，它為社會(huì)帶來(lái)了巨大的經(jīng)濟(jì)效益，同時(shí)也給人類(lèi)社會(huì)生活帶拉了現(xiàn)實(shí)的和潛在的問(wèn)題。9.7 信息社會(huì)社會(huì)影響1.社會(huì)問(wèn)題對(duì)于個(gè)人隱私的威脅計(jì)算機(jī)安全與計(jì)算機(jī)犯罪知識(shí)產(chǎn)權(quán)保護(hù)自動(dòng)化威脅傳統(tǒng)就業(yè)信息時(shí)代的貧富差距依賴(lài)復(fù)雜技術(shù)帶來(lái)的社會(huì)不安全因素1.社會(huì)問(wèn)題對(duì)于個(gè)人隱

26、私的威脅2.計(jì)算機(jī)與法律計(jì)算機(jī)犯罪因計(jì)算機(jī)技術(shù)和知識(shí)起了基本作用而產(chǎn)生的非法行為（美國(guó)司法部）在自動(dòng)數(shù)據(jù)處理過(guò)程中任何非法的違反職業(yè)道德的未經(jīng)批準(zhǔn)的行為（歐洲經(jīng)濟(jì)合作與發(fā)展組織）2.計(jì)算機(jī)與法律計(jì)算機(jī)犯罪計(jì)算機(jī)犯罪與法律 我國(guó)刑法認(rèn)定的幾類(lèi)計(jì)算機(jī)犯罪包括以下幾種（1）違反國(guó)家規(guī)定，侵入國(guó)家事務(wù)、國(guó)防建設(shè)、尖端科學(xué)技術(shù)領(lǐng)域的計(jì)算機(jī)信息的行為；（2）違反國(guó)家規(guī)定，對(duì)計(jì)算機(jī)信息系統(tǒng)功能進(jìn)行刪除、修改、增加、干擾，造成計(jì)算機(jī)信息系統(tǒng)不能正常運(yùn)行；（3）違反國(guó)家規(guī)定， 對(duì)計(jì)算機(jī)信息系統(tǒng)中存儲(chǔ)處理或者傳輸?shù)臄?shù)據(jù)和應(yīng)用程序進(jìn)行刪除、修改、增加操作；（4）故意制作和傳播計(jì)算機(jī)病毒等破壞性程序，影響計(jì)算機(jī)系統(tǒng)正

27、常運(yùn)行計(jì)算機(jī)犯罪與法律 我國(guó)刑法認(rèn)定的幾類(lèi)計(jì)算機(jī)犯罪包括以下幾種3.隱私保護(hù)隱私權(quán)是指公民享有的個(gè)人生活不被干擾的權(quán)利和個(gè)人資料的支配控制權(quán)在信息網(wǎng)絡(luò)時(shí)代，個(gè)人隱私權(quán)侵犯六種情形侵害個(gè)人通信內(nèi)容收集他人私人資料賺錢(qián)散播侵害隱私權(quán)的軟件侵入他人系統(tǒng)以獲取資料不當(dāng)泄露他人資料網(wǎng)上有害信息3.隱私保護(hù)隱私權(quán)是指公民享有的個(gè)人生活不被干擾的權(quán)利和個(gè)人軟件版權(quán)和自由軟件知識(shí)產(chǎn)權(quán)（Intellectual Property）是指由個(gè)人或組織創(chuàng)造的無(wú)形資產(chǎn)，依法享有專(zhuān)有權(quán)利盜版軟件的非法復(fù)制版權(quán)的合理性自由軟件使用者可以自由的運(yùn)用，拷貝，分發(fā)，學(xué)習(xí)，改變改善該軟件 共享軟件 軟件版權(quán)和自由軟件知識(shí)產(chǎn)權(quán)（In

28、tellectual Pr1.軟件版權(quán)及其保護(hù)盜版軟件的非法復(fù)制會(huì)受到法律訴訟“軟件版權(quán)”賦予一個(gè)程序作者唯一享有復(fù)制、發(fā)布、出售、更改軟件等諸多權(quán)利許可證（License）保護(hù)：軟件許可證是一種具有法律效力的合同商業(yè)軟件版權(quán)保護(hù)享有許可證保護(hù)1.軟件版權(quán)及其保護(hù)盜版軟件的非法復(fù)制2.自由軟件軟件版權(quán)合理嗎？最早的軟件“隨機(jī)銷(xiāo)售”，不存在版權(quán)FreeBSD最早的自由軟件伯克利發(fā)布第一個(gè)免費(fèi)的Unix版本又叫“源代碼開(kāi)放軟件”，GUN/Linux全球前500名超級(jí)計(jì)算機(jī)中，有91%運(yùn)行Linux自由軟件和LINUX無(wú)處不在2.自由軟件軟件版權(quán)合理嗎？自由軟件和LINUX無(wú)處不在3.共享軟件又叫“試用軟件”，微軟最早提出介于商業(yè)軟件和自由軟件之間的一種形式也受著作權(quán)保護(hù)發(fā)行方式：復(fù)制品可以通過(guò)網(wǎng)絡(luò)在線(xiàn)服務(wù)、BBS或者從一個(gè)用戶(hù)傳給另一個(gè)用戶(hù)等途徑自由傳播測(cè)試