Course 0 課程介紹 Introduction

 Outline 了解本課程授課重點、目標及課程設計 了解本課程評分標準 課前重點 資料結構 v.s. 演算法 資料結構概念基礎複習

 教材 Text Book Reference Book 蔡宗翰, 演算法: 使用C++ 虛擬碼, 碁峰圖書, 2004. 講義下載處: http://www.csie.ntu.edu.tw/~d92005 Reference Book R. E. Neapolitan and K. Naimipour, Foundations of Algorithms: Using C++ Pseudocode, 3/e, Jones, 2004. (Textbook原文本) 李家同教授, Computational Biology, 全文電子書第二章. 洪逸, 洪捷, 演算法-名校攻略密笈, 鼎茂圖書. 洪逸, 資料結構(含精選試題), 鼎茂圖書.

 課程重點 前置觀念 演算法：效率，分析與量級 (Algorithms: Efficiency, Analysis, and Order) 遞迴 (Recursion) 排序 (Sort) 搜尋 (Search) 解題策略 Divide-and-Conquer (切割與征服) Dynamic Programming (動態規劃) The Greedy Approach (貪婪法則) Backtracking (回溯) Branch-and-Bound (分枝與限制) NP問題 An Introduction to the Theory of NP

 評分標準 期中考：35% 期末考：35% 平時考：20% 平時成績：10% 加分程式題：10%~20%

▓ 資料結構 v.s. 演算法 資料結構 演算法 ADT Array Linked List Stack Queue Tree Graph Divide-and-Conquer Dynamic Programming The Greedy Approach Backtracking Branch-and-Bound 複雜度分析 搜尋 (Search) 排序 (Sort) 高等樹 (Advanced Tree) 基礎 高階 Theory of NP: P Problem NP Problem NP Complete Problem NP Hard Problem ADT

資料結構概念基礎複習

▓ Array Def: 為表示有序的線性串列之一種方式 其佔用連續性的記憶體空間 各元素型態皆需相同 (一致) 支援Sequential及Random Access 插入、刪除元素較為麻煩 ∵需挪移其它元素 不易動態增刪空間大小

Array種類 一維陣列 二維陣列 三維陣列 N維陣列

▓ Linked List Def: 由一組節點 (Node)所組成的有序串列，各Node除了Data欄之外，另外有 ≥ 1 個Link欄 (或稱 Pointer)，用以指向其它Node之位址。 有一個指標變數 (Pointer variable) 用來指出鏈結串列中的第一個節點之所在。指標變數的名字可用來做為其所指向之鏈結串列的名字。

Linked list的特質: 各Node不一定要佔用連續的Memory空間 各Node之型態 (Data Type) 不一定要相同 僅支援Sequential Access Insert/Delete Node 容易

Linked List 種類 nil F C

▓ Stack Def: 具有LIFO (last in-first out)或FILO (first in-last out) 性質的有序串列。 插入元素的動作稱為Push, 刪除元素的動作稱為Pop. Push/Pop的動作皆發生在同一端，此端稱為Top.

▓ Queue (佇列) Def: 具有FIFO (first in-first out) 性質的有序串列。其插入元素的動作稱為發生在Rear (尾)端, 刪除元素的動作發生在Front (前)端.

▓ Tree Def: Tree是由1個以上的Nodes所組成的有限集合，滿足: 至少有一個Node，稱為Root 其餘的Nodes分成T1, T2, …, Tn個互斥集合，稱為Subtree

▓ Binary Tree (二元樹) Def: Binary Tree為具有 ≥ 0 個nodes所構成的有限集合。 若不為空的樹，則具有Root及左, 右子樹，且左, 右子樹亦是Binary Tree。

二元樹之三個基本定理 [定理一]: 二元樹中，第i個level的node個數最多有 2i-1 個。 [定理二]: 高 (深) 度為k的二元樹，其node個數最多有 2k-1 個。 [定理三]: 非空二元樹若leaf個數為 n0 個，degree為2的node個數為n2個，則 n0 = n2+1。

二元樹的種類 Skewed Binary Tree Full Binary Tree Complete Binary Tree

Skewed Binary Tree Def: 可分為 Left-Skewed Binary Tree: 每個non-leaf node皆只有左子集 Right-Skewed Binary Tree: 每個non-leaf node皆只有右子集

Full Binary Tree Def: 具有最多Node個數的二元樹稱之 即: 高度為d，其node個數必為2d-1 具有n個nodes的Full B.T. ，其高度必為: 課本將之命名為: complete binary tree (7.6.1節)

Complete Binary Tree Def: 若二元樹高度為d，node個數為n，則 2d-1-1 < n < 2d-1 n個node之編號與高度d的full binary tree之前的n個node編號一一對應，不能跳號。 課本將之命名為: essentially complete binary tree (7.6.1節)

▓ Graph Def: A Graph is a collection of nodes, called vertices, and a collection of line segments, called edges, that connecting pairs of vertices. In other words, a graph consists of two sets a set of vertices a set of lines.

Graph may be either directed or undirected: Directed graph (或稱 Digraph) Each line has a direction to its successor. G = (V, E), 其中V為頂點集合，E為邊集合。<vi, vj> ≠ <vj, vi>。 Undirected graph Each line has no direction. G = (V, E), 其中V為頂點集合，E為邊集合。<vi, vj> = <vj, vi>。

▓ Data Type and Abstract Data Type Def: A data type consists of two parts a set of data the operations that can be performed on the data. For example: Integer Data: -∞, …, -2, -1, 0, 1, …, ∞ (沒有小數的數值集合) Operations: +, -, , , %, , , ==, !=, ++, --, … Floating point Data: -∞, …, -1.9, …, 0.0, …, ∞ Operations: +, -, , , %, , , ==, !=, … Character Data: ‘A’, ‘B’, …, ‘a’, ‘b’, … Operations: <, >, …

ADT (Abstract Data Type; 抽象資料型態) Def: ADT是一種Data Type，且要滿足： “資料的規格與操作的規格” 獨立於 “資料的實際表示方式與操作的實際製作方式.” User Request Designer Spec. of Data Objects Representation of Data Ex: a. b. c. … Spec. of Operations Implementation of Operations Ex: 1. 2. 3. … Hidden (隱藏)