北京大學(xué)《計(jì)算概論》課件：ch

北京大學(xué)《計(jì)算概論》課件歡迎來(lái)到北京大學(xué)《計(jì)算概論》課程。本課程將帶您深入了解計(jì)算機(jī)科學(xué)的基礎(chǔ)知識(shí)，從硬件到軟件，從算法到編程語(yǔ)言。讓我們一起開(kāi)啟這段激動(dòng)人心的學(xué)習(xí)之旅。計(jì)算機(jī)發(fā)展歷程1機(jī)械計(jì)算時(shí)代從算盤(pán)到差分機(jī)，人類(lèi)開(kāi)始探索機(jī)械計(jì)算的可能性。2電子計(jì)算機(jī)誕生ENIAC的出現(xiàn)標(biāo)志著電子計(jì)算機(jī)時(shí)代的到來(lái)。3個(gè)人計(jì)算機(jī)興起蘋(píng)果和IBM推動(dòng)了個(gè)人計(jì)算機(jī)的普及。4互聯(lián)網(wǎng)時(shí)代全球信息互聯(lián)互通，計(jì)算機(jī)成為日常生活的一部分。計(jì)算機(jī)的硬件組成中央處理器（CPU）計(jì)算機(jī)的大腦，負(fù)責(zé)執(zhí)行指令和數(shù)據(jù)處理。內(nèi)存（RAM）臨時(shí)存儲(chǔ)數(shù)據(jù)和程序的地方，速度快但容量有限。存儲(chǔ)設(shè)備如硬盤(pán)，用于長(zhǎng)期存儲(chǔ)數(shù)據(jù)和程序。輸入輸出設(shè)備如鍵盤(pán)、鼠標(biāo)、顯示器等，用于人機(jī)交互。CPU的工作原理取指令從內(nèi)存中獲取下一條要執(zhí)行的指令。譯碼解釋指令的含義，確定需要執(zhí)行的操作。執(zhí)行執(zhí)行指令指定的操作，如算術(shù)運(yùn)算或數(shù)據(jù)移動(dòng)。寫(xiě)回將操作結(jié)果存儲(chǔ)到指定的位置。存儲(chǔ)設(shè)備介紹內(nèi)存（RAM）速度快，容量小，斷電數(shù)據(jù)丟失。主要用于臨時(shí)存儲(chǔ)正在運(yùn)行的程序和數(shù)據(jù)。硬盤(pán)（HDD/SSD）容量大，速度相對(duì)較慢，可長(zhǎng)期保存數(shù)據(jù)。用于存儲(chǔ)操作系統(tǒng)、軟件和用戶(hù)文件。光盤(pán)（CD/DVD）便于攜帶和分發(fā)，容量適中，主要用于數(shù)據(jù)備份和多媒體存儲(chǔ)。輸入設(shè)備鍵盤(pán)用于輸入文字、數(shù)字和命令的主要設(shè)備。鼠標(biāo)用于控制光標(biāo)，選擇和操作圖形界面元素。麥克風(fēng)用于語(yǔ)音輸入和音頻錄制。攝像頭用于圖像和視頻輸入。輸出設(shè)備輸出設(shè)備將計(jì)算機(jī)處理的結(jié)果以可感知的形式呈現(xiàn)給用戶(hù)。常見(jiàn)的輸出設(shè)備包括顯示器、打印機(jī)、投影儀、音箱和繪圖儀等。程序的基本概念指令序列程序是一系列按特定順序排列的計(jì)算機(jī)指令。自動(dòng)執(zhí)行程序能夠被計(jì)算機(jī)自動(dòng)執(zhí)行，無(wú)需人工干預(yù)。數(shù)據(jù)處理程序可以處理輸入數(shù)據(jù)，產(chǎn)生期望的輸出結(jié)果?？芍貜?fù)使用同一程序可以多次執(zhí)行，處理不同的輸入數(shù)據(jù)。算法的基本概念1問(wèn)題定義明確要解決的問(wèn)題。2輸入規(guī)范確定算法的輸入數(shù)據(jù)。3處理步驟設(shè)計(jì)解決問(wèn)題的具體步驟。4輸出規(guī)范定義算法的預(yù)期輸出。5效率考慮優(yōu)化算法的執(zhí)行效率。算法的基本特性有限性算法必須在有限步驟內(nèi)完成。確定性每個(gè)步驟必須有明確的定義。輸入算法有零個(gè)或多個(gè)輸入。輸出算法有一個(gè)或多個(gè)輸出。算法的基本表達(dá)自然語(yǔ)言用日常語(yǔ)言描述算法步驟，易于理解但可能存在歧義。流程圖用圖形符號(hào)表示算法流程，直觀但不適合復(fù)雜算法。偽代碼結(jié)合自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言的特點(diǎn)，既易讀又較為精確。程序代碼用特定編程語(yǔ)言編寫(xiě)，最精確但需要編程知識(shí)。算法的時(shí)間復(fù)雜度分析1O(1)常數(shù)時(shí)間，最優(yōu)復(fù)雜度。2O(logn)對(duì)數(shù)時(shí)間，如二分查找。3O(n)線性時(shí)間，如遍歷數(shù)組。4O(nlogn)線性對(duì)數(shù)時(shí)間，如快速排序。5O(n^2)平方時(shí)間，如簡(jiǎn)單排序算法。程序設(shè)計(jì)語(yǔ)言概述機(jī)器語(yǔ)言直接由計(jì)算機(jī)執(zhí)行的二進(jìn)制代碼，效率高但編寫(xiě)困難。匯編語(yǔ)言使用助記符表示機(jī)器指令，比機(jī)器語(yǔ)言更易讀。高級(jí)語(yǔ)言接近自然語(yǔ)言，如C++、Java、Python等，易學(xué)易用。腳本語(yǔ)言如JavaScript、Python，通常用于快速開(kāi)發(fā)和自動(dòng)化任務(wù)。數(shù)據(jù)類(lèi)型基本數(shù)據(jù)類(lèi)型整數(shù)（int）浮點(diǎn)數(shù)（float）字符（char）布爾（bool）復(fù)合數(shù)據(jù)類(lèi)型數(shù)組結(jié)構(gòu)體類(lèi)基本運(yùn)算符算術(shù)運(yùn)算符+、-、*、/、%（加、減、乘、除、取余）關(guān)系運(yùn)算符==、!=、>、<、>=、<=（等于、不等于、大于、小于等）邏輯運(yùn)算符&&（與）、||（或）、!（非）位運(yùn)算符&、|、^、~、<<、>>（按位與、或、異或、取反、左移、右移）控制流程語(yǔ)句順序結(jié)構(gòu)按照語(yǔ)句的先后順序依次執(zhí)行。選擇結(jié)構(gòu)if-else、switch-case等條件判斷語(yǔ)句。循環(huán)結(jié)構(gòu)for、while、do-while等重復(fù)執(zhí)行語(yǔ)句。跳轉(zhuǎn)語(yǔ)句break、continue、return等控制程序流程。函數(shù)與過(guò)程1定義函數(shù)指定函數(shù)名、參數(shù)列表和返回值類(lèi)型。2函數(shù)體編寫(xiě)實(shí)現(xiàn)函數(shù)功能的代碼。3參數(shù)傳遞可以通過(guò)值傳遞或引用傳遞。4返回結(jié)果使用return語(yǔ)句返回函數(shù)結(jié)果。數(shù)組一維數(shù)組線性排列的同類(lèi)型數(shù)據(jù)集合，如intarr[5]。二維數(shù)組表格形式的數(shù)據(jù)結(jié)構(gòu)，如intmatrix[3][3]。數(shù)組操作元素訪問(wèn)遍歷排序搜索字符串操作長(zhǎng)度計(jì)算獲取字符串的字符數(shù)。連接將兩個(gè)或多個(gè)字符串合并。子串提取字符串的一部分。比較判斷兩個(gè)字符串是否相等或大小關(guān)系。文件讀寫(xiě)操作打開(kāi)文件指定文件名和打開(kāi)模式（讀/寫(xiě)/追加）。讀取/寫(xiě)入從文件讀取數(shù)據(jù)或向文件寫(xiě)入數(shù)據(jù)。移動(dòng)文件指針調(diào)整讀寫(xiě)位置。關(guān)閉文件完成操作后釋放文件資源。面向?qū)ο蟪绦蛟O(shè)計(jì)1封裝將數(shù)據(jù)和方法捆綁在一起。2繼承子類(lèi)繼承父類(lèi)的屬性和方法。3多態(tài)同一接口，不同實(shí)現(xiàn)。面向?qū)ο缶幊淌且环N程序設(shè)計(jì)范式，它將數(shù)據(jù)和操作數(shù)據(jù)的函數(shù)綁定在一起，形成一個(gè)獨(dú)立的對(duì)象。這種方法有助于提高代碼的可重用性和可維護(hù)性。類(lèi)與對(duì)象類(lèi)類(lèi)是對(duì)象的模板，定義了對(duì)象的屬性和方法。它是一種抽象的數(shù)據(jù)類(lèi)型。對(duì)象對(duì)象是類(lèi)的實(shí)例，具有類(lèi)定義的屬性和方法。它是程序中的具體實(shí)體。成員變量類(lèi)中定義的變量，用于存儲(chǔ)對(duì)象的狀態(tài)。成員函數(shù)類(lèi)中定義的函數(shù)，用于操作對(duì)象的數(shù)據(jù)。繼承與多態(tài)繼承子類(lèi)繼承父類(lèi)的屬性和方法，實(shí)現(xiàn)代碼重用。多態(tài)同一方法在不同對(duì)象上有不同的行為。重寫(xiě)子類(lèi)重新定義父類(lèi)的方法。接口定義方法的契約，但不實(shí)現(xiàn)。異常處理try塊包含可能拋出異常的代碼。catch塊捕獲并處理特定類(lèi)型的異常。throw語(yǔ)句手動(dòng)拋出異常。finally塊無(wú)論是否發(fā)生異常都會(huì)執(zhí)行的代碼。泛型編程類(lèi)型參數(shù)化使用占位符類(lèi)型定義類(lèi)或方法。代碼重用一份代碼可以用于多種數(shù)據(jù)類(lèi)型。類(lèi)型安全編譯時(shí)類(lèi)型檢查，減少運(yùn)行時(shí)錯(cuò)誤。性能優(yōu)化避免類(lèi)型轉(zhuǎn)換，提高運(yùn)行效率。網(wǎng)絡(luò)基本概念協(xié)議定義數(shù)據(jù)如何在網(wǎng)絡(luò)上傳輸。IP地址標(biāo)識(shí)網(wǎng)絡(luò)上的設(shè)備。端口區(qū)分同一設(shè)備上的不同服務(wù)。數(shù)據(jù)包網(wǎng)絡(luò)傳輸?shù)幕締挝?。?yīng)用層協(xié)議應(yīng)用層協(xié)議定義了應(yīng)用程序如何在網(wǎng)絡(luò)上交換數(shù)據(jù)。常見(jiàn)的應(yīng)用層協(xié)議包括HTTP（網(wǎng)頁(yè)）、FTP（文件傳輸）、SMTP（電子郵件）、DNS（域名解析）和MQTT（物聯(lián)網(wǎng)通信）等。傳輸層協(xié)議TCP面向連接，可靠傳輸，適用于要求數(shù)據(jù)完整性的應(yīng)用。UDP無(wú)連接，快速傳輸，適用于實(shí)時(shí)性要求高的應(yīng)用。網(wǎng)絡(luò)層協(xié)議IP負(fù)責(zé)數(shù)據(jù)包的尋址和路由。ICMP用于發(fā)送錯(cuò)誤消息和操作信息。ARP將IP地址轉(zhuǎn)換為物理地址。OSPF動(dòng)態(tài)路由協(xié)議，用于路由器間通信。數(shù)據(jù)鏈路層協(xié)議以太網(wǎng)最常用的局域網(wǎng)技術(shù)。