計算機概論 - HackMD

# 計算機概論 ## 115級資工 ==有錯誤可以留言== ## Computer Science An Overview ### 13^th^ Edition, Global Edition ![](https://i.imgur.com/gjiKaXA.png) ## Chapter 1 : Data Storage (數據儲存) ==補== ## Chapter 2 : Data Manipulation ==補== ## Chapter 3 : Operating Systems ==補== ## Chapter 4 : Networking and the Internet (網路與互聯網) ### 4.1 Network Fundametals (網路基礎) - 網路軟體允許使用者交換訊息與共享資源 #### Network Classifications (網路分類) - Scope (範圍) 由小到大 -Personal Area Network (RAN) : 短距離 -Local Area Network (LAN) : 建築or校園 -Metropolitan Area Network (MAN) : 社區 -Wide Area Network (WAN) : 更遠的距離 - Ownership (所有權) -封閉 versus 開放 - Topology (拓撲) -Bus(乙太網) -Star(帶有Access Point的無線網路) ![](https://i.imgur.com/iB1iFhV.png =200x150)![](https://i.imgur.com/gm8KCbW.png =200x150) #### Protocols (協議) - 在網路上進行活動的規則 -需要避免所有機器同時傳輸 - 允許供應商構建與其他供應商兼容的產品 :::info Protocols for Transmitting Messages(傳輸訊息的協議) ==CSMA/Collision Detection(碰撞偵測) :== - 使用於乙太網 - 兩台機器都停止並等待一個獨立且隨機的時間 ==CSMA/Collision Avoidance(碰撞避免) :== - 使用於WiFi - 有利於已經等待的機器 [More->](https://zh.wikipedia.org/zh-tw/%E8%BD%BD%E6%B3%A2%E4%BE%A6%E5%90%AC%E5%A4%9A%E8%B7%AF%E8%AE%BF%E9%97%AE) ::: --- ### 4.2 ==補== ___ ### 4.3 World Wide Web (全球資訊網) - 由 URLs 標識並使用 HTTP 傳輸 #### Hypertext (超文字) 是一種可以顯示在電腦顯示器或其他電子裝置上的文字，普遍以電子文件的方式存在，其中的超文字包含可以連結到其他檔案/檔案頁面的 Hyperlinks (超連結)，允許從當前閱讀的文字直接切換到超連結所指向的所有文字。 #### Browsers versus Webservers - Browsers (瀏覽器) : 向用戶呈現網頁的內容 - Webservers (網路伺服器) : 提供文檔的存取 :::info #### ==URL (Uniform Resource Locator) (網址)== Server 端的 Local 路徑協定://持有文件的主機助記名/目錄路徑/文件名稱 ![](https://i.imgur.com/KlEXFng.png =500x300) [More->](https://zh.wikipedia.org/zh-tw/%E7%BB%9F%E4%B8%80%E8%B5%84%E6%BA%90%E5%AE%9A%E4%BD%8D%E7%AC%A6) ::: #### Hypertext Markup Language (HTML) - 是一種用於建立網頁的標準標記語言 - 含有與 Browser 溝通的成對 tags 學習連結->[W3Schools](https://www.w3schools.com/) #### Extensible Markup Language (XML) - 一種與 HTML 架構相似的標記語言 #### Client Side Versus Server Side - Client-side (用戶端) -Browser -例:Javascript, Java applets, Macromedia Flash - Server-side (伺服器端) -Webserver -例 : Common Gateway Interface (CGI), Servlets, JavaServer Pages (JSP) / Active Server Pages (ASP), PHP --- ### 4.4 Internet Protocols (互聯網協議) - 控制訊息在互聯網上的傳輸方式 - 需存在於互聯網上的每台設備 - 多層次結構 :::info #### ==Internet Software Layers (互聯網軟體層)== - Application Layer (應用層) : 建構帶有地址的訊息 - Transport Layer (傳輸層) : 將訊息切割成封包 - Network Layer (網絡層) : 透過互聯網處理路由 - Link Layer (連結層) : 處理封包的實際傳輸 ![](https://i.imgur.com/Odwnzto.png =600x400) ::: #### TCP/IP Protocol Suite - Transport Layer -Transmission Control Protocol (TCP) -User Datagram Protocol (UDP) - Network Layer -Internet Protocol (IP) : IPv4 (32bits) / IPv6 (128bits) - 比較 | Protocol | TCP (傳輸控制協議)| UDP (用戶數據報協議)| | -------- | -------------- | ---------------- | | 介紹 |是一種面向連接的協議，設備用於在網絡上進行通信，提供錯誤檢測和糾正功能。此外，TCP 確保數據包以它們發送的相同順序到達。|是一種無連接協議，沒有錯誤檢測和糾正服務。取而代之的是，無論是否收到數據包，都會不斷地將數據包發送給接收方。| |可靠性|較高|較低| |效率|差|優| --- ### 4.5 Simple Client Server Program (簡單的客戶端伺服器程式) #### Socket (插座) - Socket 是一個網路上的通訊端點，使用者或應用程式只要連接到 Socket 便可以和網路上任何一個通訊端點連線，Socket 之間通訊就如同作業系統內程序（Process）之間通訊一樣。 - 需要知道對方的 IP number + TCP port --- ### 4.6 Cybersecurity (網路安全) - 攻擊形式: -Malware (惡意軟體) (viruses, worms, Trojan horses, spyware, phishing software) -Denial of service (阻斷服務) (DoS) : 產生多個連線使 Server 超過負載 -DDoS : 分散式 DoS ，不特定來源 botnet (殭屍網路) -Spam (垃圾郵件) (common medium for delivering malware) - 防範方法: -Firewalls (防火牆) : 外到內，內到外，過濾 IP Port 無法過濾病毒 -Spam filters (垃圾郵件過濾器) : 關鍵字過濾/ Server 驗證 -Proxy Servers (代理伺服器) -Antivirus software (防毒軟體) : 須持續更新，易誤判 #### Cryptography (密碼學) - HTTPS 用於安全互聯網存取 - 金鑰協定 : 每個使用者保管兩把 (公 + 私) ，需事先知道用哪把金鑰，且不讓第三者知道 - Public-key Encryption (公鑰加密) (asymmetric) (非對稱) -Public key (公鑰) : 用於 encrypt (加密)訊息 -Private key (私鑰) : 用於 decrypt (解密) 訊息 - Certificate Authorities (憑證機構) -受託維護公鑰列表 -取得公鑰->要求認證 - 數位簽章 -需用自己的 Private key - 攻擊方式 -替換 Public key 為自己的 - 實際操作 -加密 : 接收者公鑰 -解密 : 接收者私鑰 ![](https://i.imgur.com/u8lhxrY.png =400x300) #### Legal Approaches to Network Security (網路安全的法律途徑) - 電子簽章法 : 賦予數位簽章效力 - 個資保護法 : 蒐集個資需事先告知 --- ## Chapter 5 : Algorithms (演算法) --- ### 5.1 The concept of an Algorithm (演算法的概念) :::info #### ==Formal Definition of Algorithm(演算法的正式定義) :== - An ordered set of unambiguous, executable steps that defines a terminating process 將數個清楚且可執行的步驟組成一個有順序性的集合，並由該集合定義一個終止狀態 ::: - 處理排序問題方法 : -Linear (1, 2, 3, ...) : 最常見的方式，照順序 -Parallel(multiple processors) : 多工處理，可同時執行多個步驟 -Cause & Effect(circuits) : 原因造成的結果，邏輯性 - 終止狀態 : -Terminating Process : 有產生結果 -Non-terminating Process : 不產生結果 :::info #### ==The Abstract Nature of Algorithms (演算法的抽象本質)== - A Program is a representation of an Algorithm 程式是用來敘述(表達)演算法 - A Process is the activity of executing an Algorithm 步驟是執行演算法的活動 ::: --- ### 5.2 Algorithm Representation (演算法表示) - 使用定義完整的 Primitives (原式) 表達 -一組原式構成一種 Programming language (程式語言) - 使用 Pseudocode (偽代碼) 非正式的表達 -介於口語與程式語言 #### Designing a Pseudocode Language (設計偽代碼語言) 1. 選擇一種通用的程式語言 2. 放寬一些語法規則 3. 允許使用一些口語 4. 使用一致、簡潔的符號 #### Pseudocode Primitives (偽代碼原式) - Assignment (賦值) ```python= name = expression ``` - Conditional selection (條件選擇) ```python= if (condition): activity1 else: activity2 ``` - Repeated execution (重複執行) ```python= while (condition): body ``` - Indentation shows nested conditions (使用縮排表示巢狀情形) ```python= if (condition1): if (condition2): activity1 else: activity2 else: activity3 ``` - Define a function (定義函式) ```python= def name(): ``` - Executing a function (執行函式) ```python= if(condition): name1() else: name2() ``` - Using parameters (使用參數) ```python= def name(parameter): ``` --- ### 5.3 Algorithm Discovery (發現演算法) #### Polya’s Steps in the Context of Program Development 1. 理解問題 2. 了解演算法如何解決問題 3. 制定演算法並以程式表達 4. 評估解決方案的準確性及其作為解決其他問題的工具的潛力 #### 處理問題的方法 - 嘗試從 backwards (反面) 解決問題 - 從較簡單的相關問題解起 : -放寬一些問題約束 -先解決問題的一部分 (bottom up methodology) - Stepwise refinement (逐步化簡) : 將問題分解成更小的問題 (top-down methodology) --- ### 5.4 Iterative Structures (重複的結構) - 以循環方式重複的指令集合 :::info #### ==The sequential search (循序搜尋) algorithm expressed in pseudocode== ```python= def Search (List, TargetValue): if (List is empty): Declare search a failure else: Select the first entry in List to be TestEntry while (TargetValue > TestEntry and entries remain): if (TargetValue == TestEntry): Declare search a success else: Declare search a failure ``` ::: #### Components of repetitive control - Initialize (初始化), Test (測試), Modify (修改) #### Iterative Structures (重複結構) - Pretest loop (先測試迴圈) : ==Condition = True -> 進入 Body== ```python= while (condition): body ``` ![](https://i.imgur.com/HwSwwaL.png =200x200) - Posttest loop (後測試迴圈) : ==Condition = True -> 離開 Body== ```python= repeat: body until (condition) ``` ![](https://i.imgur.com/qXIG07L.png =200x200) :::info #### ==The insertion sort (插入排序) algorithm expressed in pseudocode== ```python= def Sort(List): N = 2 while (N <= length of List): Pivot = Nth Entry in List Remove Nth Entry leaving a hole in List while (there is an Entry above the hole and Entry > Pivot): Move Entry down into the hole leaving a hole in the List above the Entry Move Pivot into the hole N = N + 1 ``` ::: --- ### 5.5 Recursive Structures (遞迴結構) - 將指令集作為自身的子任務重複 - 形成程序的多個激活，除其中一個被激活外，所有激活都在等待其他激活完成 :::info #### ==The binary search (二元搜尋法) algorithm in pseudocode== ```python= def Search(List, TargetValue): if (List is empty): Report that the search failed else: TestEntry = middle Entry in the List if (TargetValue == TestEntry): Report that the search succeeded if (TargetValue < TestEntry): Sublist = portion of List preceding TestEntry Search(Sublist, TargetValue) if (TargetValue < TestEntry): Sublist = portion of List following TestEntry Search(Sublist, TargetValue) ``` ::: #### Recursive Control (遞迴控制) - 基本情況下，需要初始化、修改和終止測試 - 造成以伸縮方式動態創建函數的多個副本的錯覺 - 在給定時間實際上只有一個副本在運行，其他副本正在等待 --- ### 5.6 Efficiency and Correctness (效率和正確性) - Correctness -演算法的正確性是由正式推理所決定的，而不是通過測試其表現來決定的 - Efficiency -以執行的指令數衡量 -使用 big theta![reference link](https://i.imgur.com/m9RHrOT.png =20x25) 表示法 -結合最佳、最差和平均案例分析 ![](https://i.imgur.com/NXa69OT.png)![](https://i.imgur.com/m9RHrOT.png =20x25)(n^2^) ![](https://i.imgur.com/9RIeJ99.png)![](https://i.imgur.com/m9RHrOT.png =20x25)(log~2~n) #### Software Verification (軟體驗證) - 正確性證明（使用形式邏輯） -Assertions (斷言) : Preconditions (前提條件) / Loop invariants (迴圈不變量) - 測試更常用於軟體驗證 - 測試僅證明程式對於所使用的測資是正確的 ![](https://i.imgur.com/MzOpQeS.png) --- ## Chapter 6 : Programming Languages (程式語言) --- ### 6.1 Historical Perspective (歷史的角度) #### 低階語言 - Gen1^st^ : Machine Language (機器語言) - Gen2^nd^ : Assembly Language (組合語言) -表示機器指令的助記系統 -程序變量或標識符：存儲器位置的描述性名稱，由程序員選擇 #### 高階語言 - Gen3^rd^ : Machine Independent Language / Beyond-More Powerful abstractions #### Assembly Language Characteristics (組合語言的特性) - 機器指令和組合指令一一對應 -程序員必須像機器一樣思考 - 本質上依賴於機器 - 通過 ==assembler (組譯器)== 轉換為機器語言 ![](https://i.imgur.com/RU6Umjt.png) #### Third Generation Language (第三代語言) - 使用高級原式 - 大部分為機器獨立語言 - 例：FORTRAN、COBOL - 每個原式對應一系列機器語言指令 - 通過 ==compiler (編譯器)== 轉換為機器語言 #### Generations of programming languages (程式語言的世代) ![](https://i.imgur.com/pZyeMZt.png) #### The evolution of programming paradigms (程式的演變) ![](https://i.imgur.com/patfqhE.png) --- ### 6.2 Traditional Programming Concepts (傳統編程概念) #### 典型命令式程式或程式單元的組成 ![](https://i.imgur.com/Me9Nc9F.png =400x300) #### Data Types (資料型態) - Integer (整數) : Whole numbers - Real (float) (浮點數) : Numbers with fractions - Character (字元) : Symbols - Boolean (布林數) : True / False #### Data Structure (資料結構) - 資料的概念形狀或排列 - Array 是一個常見的資料結構 #### Comments (註解) - 程式中的解釋性語句 - 人類閱讀程式時很有幫助 - 被編譯器忽略 ```cpp= /*This is a comment in C / C++ / Java.*/ //This is a comment in C / C++ / Java. ``` --- ### 6.3 Procedural Units (程序單元) - 術語 -Subprogram, subroutine, procedure, method, function - 種類 -fruitful function : 有回傳值 -procedure : 無回傳值 #### The flow of control involving a function (涉及函數的控制流) ![](https://i.imgur.com/rnZ2xSa.png =400x300) #### Local (區域) versus Global (全域) Variables - 區域變數離開函式就不能使用 #### Executing the function Demo and passing parameters by value (傳值) ![](https://i.imgur.com/p8LRKwk.png =400x600) #### Executing the function Demo and passing parameters by reference (傳址) ![](https://i.imgur.com/NwmjAda.png =400x600) --- ### 6.4 Language Implementation (語言實現) - 將使用高級語言編寫的程式轉換為機器可執行形式的過程 - Lexical Analyzer (詞法分析器) -將字符序列轉換為記號（token）序列的過程 [More->](https://zh.wikipedia.org/zh-tw/%E8%AF%8D%E6%B3%95%E5%88%86%E6%9E%90) - Parser (解析器) -將標記分組到語句中，使用語法圖來製作 parse trees (解析樹) - Code Generator (代碼生成器) -建構機器語言指令來實現語句 #### The translation process(翻譯過程) ![](https://i.imgur.com/DO07b8p.png) #### An object-oriented approach to the translation process (物件導向翻譯過程的方法) ![](https://i.imgur.com/Ss1UwsP.png) --- ### 6.5 Object-Oriented Programming (物件導向程式) - 先有 Class 再產生 Object, Object 是 Class 的實例 - Object (物件) : 包含數據和過程的活動程序單元 - Class (類別) : 建構物件的模板 #### Components of an Object (物件的組件) - Instance Variable (實例變數) -保存物件訊息 - Method (方法) -物件的功能 - Constructor (建構元) -首次建構時用於初始化新物件的方法 #### Object Integrity (物件完整性) - Encapsulation (封裝) : 限制存取物件內部組件的方法 -Private : 不能被外部存取 -Public : 能被外部存取 #### Additional Object-oriented Concepts (其他物件導向的概念) - Inheritance (繼承) : 允許根據 defined class 來定義 new class - Polymorphism (多型化) : 讓多個成員方法在同樣命名的情況下，呈現不同實作細節的機制 --- ### 6.6 Programming Concurrent Activities (編程同步活動) - Parallel (or concurrent) processing (平行與同步處理) : 多個進程同時執行 -真正的同步處理需要多個 CPU -可以使用單個 CPU 的 time-sharing (分時) 來模擬 #### Spawning threads (生成線程) ![](https://i.imgur.com/exA8TDh.png) #### Controlling Access to Data (控制對資料的存取) - Mutual Exclusion (互斥) : 確保資料一次只能被一個進程存取 - Monitor (監視) : 控制對其自身存取的能力 --- ### 6.7 Declarative Programming (宣告式編程) - Resolution : 將多個陳述組合起來產生一個新陳述（原始陳述的邏輯結果） -Resolvent : 通過 Resolution 推導出的新語句 -Clause form : 其基本組件由 OR 連接的語句 - Unification : 為變量賦值，使兩個語句變得“兼容” ![](https://i.imgur.com/FMoJCBR.png) --- ## Chapter 7 : Software Engineering --- ==沒教=.= 哭哭== --- ## Chapter 8 : Data Abstractions (資料抽象) --- ### 8.1 Basic Data Structures (基本資料結構) - Arrays (陣列) - Aggregates (聚合) - Lists (串列) -Stacks (堆疊) -Queues (佇列) - Trees (樹) ![](https://i.imgur.com/7qeBSEV.png) #### Terminology for Arrays (陣列術語) - Array : 矩形資料塊且每個資料都具有相同的型別 - 二維陣列包含數列與數行其位置是兩個索引值標示 #### Terminology for Aggregates (聚合術語) - Aggregate : 可能具有不同類型和大小的資料塊 - 在資料塊中的資料通常稱為 field (欄位) - 聚合資料的欄位通常以欄位名稱存取而非數值形式 #### Terminology for Lists (串列術語) - List : 一群有序的資料串 - 串列的起點位置稱為串列的 head (頭部) 而另一端稱為 tail (尾部) #### Terminology for Stacks (堆疊術語) - Stack : 只能在頭部進行新增與刪除的串列 - 一般將堆疊的頭部稱為 top (頂部) 而尾部稱為 bottom (底部) 或 base (基底) - 頂部新增一個資料的動作稱為 pushing (推入) 而在頂部移除一個資料的動作稱為 popping (彈出) - ==LIFO : Last-in-first-out== #### Terminology for Queues (佇列術語) - Queue : 只能在頭部移除資料並只能在尾部新增資料的串列 - ==FIFO: First-in-first-out== #### Terminology for a Tree (樹術語) - Tree : 一群有階層組織的資料項 - 樹中的每個位置稱為 Node (節點) - 頂部的節點稱為 root node (根節點)，而最底層的節點稱為 terminal node (終端節點) 或 leaf node (葉節點) - Parent : 緊鄰的上層結點 - Child : 緊鄰的下層節點 - Siblings : 具有相同 Parent 的其他節點 - Binary tree (二元樹) : 樹中每個父節點最多只能有兩個子節點 - Depth (深度) : 從根節點到葉節點的最長路徑 - Subtree (子樹) : 某個節點下的所有節點也具有樹的結構 ![](https://i.imgur.com/MksIiSh.png) --- ### 8.2 Related Concepts (資料相關概念) - Abstraction (抽象化) : 電腦中的主記憶體並非如陣列, 串列, 堆疊, 佇列和樹的結構，他的組織方式是連續的記憶體儲存單元，因此必須要靠模擬的方式來產生所有其他的結構，所以資料結構是抽象化的工具，以便使用者可以以更便利的形式存取資訊而不用在意資料實際儲存的方式。 - Static vs. Dynamic Structure (靜態與動態結構) : 資料結構的大小會不會隨時間有所變動，一般來說靜態結構會比動態結構還要好處理，若結構是靜態的就只需要提供一種方式來存取各項資料，或提供另一種方式來更改指定資料的儲存值，但如果是動態的話就必須要處理新增與刪除資料的問題，以尋找所需要的記憶體空間以擴大資料結構。 - Pointer (指標) : 用來記錄資料儲存的位置，所以指標總是指向某一筆資料或是空的記憶體 --- ### 8.3 Implementing Data Structures (資料結構實作) - 高階語言提供某些資料結構作為原式 - 資料結構被轉換成機器語言指令來處理儲存在主記憶體的資料 #### Storing Arrays (陣列儲存) - 主記憶體中會保留一個==固定大小==的連續儲存空間 - ==Row major order== (以列為優先法) versus ==Column major order== (以行為優先法) - address polynomial (地址多項式) : ==x + (c * (i - 1)) + (j - 1)== -在 Row major order 情況下， x 為起始位置， c 代表陣列行數，第 i 列與 j 行資料的位置 #### Storing Aggregates (聚合儲存) - field (欄位) 可以一個接一個地存儲在連續的資料塊中 -可以計算每個 field 的存儲單元地址 - field 可以存儲在由 pointer (指針) 標識的個別位置 #### Storing Lists (串列儲存) - Contiguous list (連續串列) : 將整個串列儲存在一個很大的記憶體區塊中，每個資料項都相繼的儲存於連續的記憶體儲存單元中 - Linked list (鏈結串列) : 設定字元數多一位，多出來的位元作為指標，指向下一個名稱的記憶體位置，串列就可以散佈在整個記憶體中而不用一定要連續存放 -Head pointer (頭部指標) : 儲存第一筆資料的位置 -Null point (空指標) : 標記串列的尾端，屬於特殊位元的字串 ![](https://i.imgur.com/XomSMGy.png) - Deleting (刪除) an entry from a linked list ![](https://i.imgur.com/MkghX91.png) - Inserting (插入) an entry into a linked list ![](https://i.imgur.com/OOo59i1.png) #### Storing Stacks and Queues (堆疊與佇列儲存) - Stacks : 需要保留一塊足夠大的記憶體空間以應付最大的堆疊情況，當有資料被 pushing 或 popping 時，頂部位置會跟著在記憶體區塊的儲存單元中來回移動，因此當有新資料被 pushing 進來頂部位置，就必須要移動到最新資料的記憶體位置上，相對的如果 popping 了，那麼頂部就需要移動到下一筆資料的記憶體位置上 -Stack pointer (堆疊指標) : 指向堆疊頂部的指標 ![](https://i.imgur.com/2zFjhnJ.png) - Queues : 同樣需要保留一塊夠大的記憶體空間以應付最大的佇列，隨著資料的增加與刪除會讓整個佇列在記憶體中不斷移動，因此通常為 Circular Queue (環形佇列) -Circular Queue (環形佇列) : 當列的尾部達到記憶體區塊的末端時，把之後新增的資料存在記憶體另一端空白的區域(因為佇列尾部指標會隨著資料刪除而往前移動)，這樣就可以讓頭部指標重新指回記憶體區塊的初始位置 ![](https://i.imgur.com/qtsfVWl.png) -Head pointer (頭部指標) : 指向頭部的指標 -Tail pointer (尾部指標) : 指向尾部後一位元的指標 ![](https://i.imgur.com/kfZuJjI.png) #### Storing Binary Trees (二元樹儲存) - Linked structure (鏈接結構) : 需要有一塊足夠大的記憶體區塊，二元樹的資料結構會有三個元素：資料，指向該節點的第一個子輩節點，指向該節點的第二個子輩節點，通常會將第一個指標當作左子輩指標 (left child point) 而另一個稱為右子輩指標 (right child point)，如果沒有子輩節點的話要把它指定為 Null (空值) (表示這個節點是終端節點) ，還需要預留一個記憶體位置用於儲存跟節點的位置，稱為根指標 (root pointer) ![](https://i.imgur.com/T3TKmK6.png) ![](https://i.imgur.com/J3Ik6sz.png) - Contiguous array structure (連續陣列結構) : 儲存在連續的記憶體儲存空間中，將根節點儲存於第一個位置，接著將根節點的左子輩與右子輩儲存在第二與第三個記憶體中，接著每個節點的子輩的左右子輩分別存於 2n 和 2n+1 個儲存位置，而記憶體中沒有儲存的位置會以特殊位元字串表示該位置沒有資料 ![](https://i.imgur.com/TO5wzxm.png) #### Manipulating Data Structures (操作資料結構) - 理想情況下，資料結構應僅由預定的函式操作 - A function for printing a linked list (輸出鏈結串列的函式) ```python= def PrintList (List): CurrentPointer = List.Head while (CurrentPointer is not None): print(CurrentPointer.Value) CurrentPointer = CurrentPointer.Next ``` --- ### 8.4 A Short Case Study (簡短的案例研究) - Problem : Construct an abstract tool consisting of a list of names in alphabetical order along with the operations : search, print, and insert. - The binary search as it would appear if the list were implemented as a linked binary tree ```python= def Search (Tree, TargetValue): if (Tree is None): return None # Search failed elif (TargetValue == Tree.Value): return Tree # Search succeeded elif (TargetValue < Tree.Value): # Continue search in left subtree return Search(Tree.Left, TargetValue) elif (TargetValue > Tree.Value): # Continue search in right subtree return Search(Tree.Right, TargetValue) ``` - A function for printing the data in a binary tree ```python= def PrintTree (Tree): if (Tree is not None): PrintTree(Tree.Left) print(Tree.Value) PrintTree(Tree.Right) ``` - A function for inserting a new entry in a list stored as a binary tree ```python= def Insert(Tree, NewValue): if (Tree is None): # Create a new leaf with NewValue Tree = TreeNode() Tree.Value = NewValue elif (NewValue < Tree.Value): # Insert NewValue into the left subtree Tree.Left = Insert(Tree.Left, NewValue) elif (NewValue > Tree.Value): # Insert NewValue into the right subtree Tree.Right = Insert(Tree.Right, NewValue) else: # Make no change return Tree ``` --- ### 8.5 Customized Data Types (自定義資料型態) - 原始型態 : -integer, float, character, Boolean - 程序員可以自定義資料型態以滿足特定應用程式的需要 #### Abstract Data Type (抽象資料型態) - 用戶定義的資料型態，可以同時包含資料（表示）和函式（行為） --- ### 8.6 Classes and Objecs (類別和物件) #### 複習 -> 6.5 Object-Oriented Programming (物件導向程式) --- ### 8.7 Pointers in Machine Language (機器語言中的指標) - Immediate addressing (立即尋址) : 指令中包含要存取的資料 - Direct addressing (直接尋址) : 指令中包含要存取的資料的地址 - Indirect addressing (間接尋址) : 指令中包含要存取的資料地址的位置 --- ## Chapter 9 : Database Systems (資料庫系統) --- ### 9.1 Database Fundamentals (資料庫基礎) - Database : 結構化的資訊或資料的集合，其條目之間的內部鏈接使信息可以從各種角度訪問 [More ->](https://zh.wikipedia.org/zh-tw/%E6%95%B0%E6%8D%AE%E5%BA%93) ![](https://i.imgur.com/ajrRhyG.png) #### The Role of Schemas (架構的功用) - Schemas (架構) : 描述資料庫內中的表格結構、欄位格式以及記載每個表格中的關聯 - Subschemas (子架構) : 與特定用戶需求相關資料庫的部分，用於防止敏感資料被未經授權的人員存取 [More ->](https://zh.wikipedia.org/zh-tw/%E7%B6%B1%E8%A6%81_(%E8%B3%87%E6%96%99%E5%BA%AB)) #### Database Management Systems (資料庫管理系統) - Database Management System (資料庫管理系統) (DBMS) : 操縱與管理資料庫的軟體層，對資料庫進行統一管理，以確保資料庫的安全與完整性 - Distributed Database (分散式資料庫): 一個資料庫儲存在多台機器上 -DBMS 會向使用者隱藏這種組織細節 [More ->](https://zh.wikipedia.org/zh-tw/%E5%88%86%E5%B8%83%E5%BC%8F%E6%95%B0%E6%8D%AE%E5%BA%93) - Data independence (資料獨立性) : 應用程式與資料結構之間相互獨立，無需更改使用它的應用程式軟體即可更改資料庫組織的能力 - The conceptual layers of a database implementation (資料庫實現的概念層) ![](https://i.imgur.com/Jq4isDH.png) #### Database Models (資料庫模型) - 資料庫的概念圖 -Relational database mode (資料庫關聯模式) -Object-oriented database mode (物件導向資料庫模式) [More ->](https://en.wikipedia.org/wiki/Database_model) --- ### 9.2 The Relational Model (關聯模型) - Relation (關係) : 長方形的表格 -Attribute (屬性) : 表格中的一行 -Tuple (元組) : 表格中的一列 #### Issues of Relational Design (關聯設計的問題) - 避免一個關聯中的多個概念 -可能導致冗餘資料 -刪除一個元組也可能刪除掉必要但不相關的信息 #### Improving a Relational Design (改進關聯設計) - Decomposition (分解) : 將關聯的行分成兩個或多個關聯，複製保持關聯所需的那些行 –Lossless or nonloss decomposition (無損分解) : 不丟失任何信息的“正確”分解 #### Relational Operations (關聯操作) - SELECT : 選擇列 ![](https://i.imgur.com/7pnhHoj.png) - PROJECT : 選擇行 ![](https://i.imgur.com/Uh5Bgg2.png) - JOIN : 從兩個或多個關聯中組合信息 ![](https://i.imgur.com/VDs4AgP.png) #### Structured Query Language (SQL) - 操作元組 -INSERT : 將記錄輸入到資料表中 -UPDATE : 修改既有資料表中的資料 -DELETE : 刪除資料表中的資料 -SELECT : 選擇資料表 --- ### 9.3 Object-oriented Databases (物件導向數據庫) - 應用物件導向建構的數據庫 -每個實體都儲存為一個持久物件 -物件之間的鏈接表示關聯 -DBMS 維護物件間鏈接 #### Advantages of Object-oriented Databases (物件導向數據庫的優點) - 匹配物件導向應用程式的設計範式 - 智能可以內置到 attribute handlers - 可以處理奇異資料型態 -如 : 多媒體 --- ### 9.4 Maintaining Database Integrity (維護資料庫完整性) - Transaction : 必須同時發生的一系列操作 - Transaction log : 每個 Transaction 活動的非易失性記錄，在允許執行 Transaction 之前建立 -Commit point : Transaction 已記錄在log中的點 -Roll-back : 撤銷 Transaction 的過程 - 同時存取問題 -摘要不正確問題 -更新丟失問題 - Locking : 防止其他人存取 Transaction 正在使用的資料 -Shared lock (共享鎖) : 讀取資料時使用 -Exclusive lock (獨享鎖) : 更改資料時使用 --- ### 9.5 Traditional File Structures （傳統文件結構） #### Sequential file (循序文件) - 內容只能按順序讀取的文件 -閱讀器必須能夠檢測文件結束（EOF） -資料可以儲存在邏輯記錄中，按關鍵字段排序，提高了批量更新的速度 ![](https://i.imgur.com/a7TenQq.png) #### Indexed Files (索引文件) - index (索引) : 鍵值列表及其關聯記錄的位置 -快速識別所需記錄位置的有效方法 -索引儲存為單獨的文件 #### Opening an indexed file (開啟索引文件) ![](https://i.imgur.com/3JkqFGS.png) #### Hash Files (雜湊文件) - 每條記錄都有一個 key field - 存儲空間被劃分成 buckets - hash function (雜湊函數) 為每個 key value 計算一個 bucket number - 每條記錄被儲存在其 key 散列對應的 bucket 中 #### The rudiments of a hashing system (雜湊系統的基本原理) ![](https://i.imgur.com/hrM1clV.png) #### Collisions in Hashing (雜湊中的碰撞) - 兩個 key 散列到同一個 bucket 的情況 -table 超過75%滿時的主要問題 -解決方案：增加 bucket 數並重新散列所有資料 --- ### 9.6 Data Mining ==補== --- ### 9.7 Social Impact of Database Technology ==補==