第七章常見的演算法 目的：解決問題 遞迴演算法 （一）從程式語言的角度來看：就是程序自 己呼叫自己的情況。 （二）從演算法的特性來看：就是大問題分成 小問題，或回歸基礎問題。 （三）從演算法的角度來看：就是比較有系統 的分析解決問題的方式。

陣列的應用 陣列元素的型式 陣列的多維性 動態陣列(dynamic array) ： 使陣列大小彈 性變動 。

遞迴函數 (recursive function) 會呼叫啟動自己執行，意思是函數在執 行過程中會再度啟動本身的程式碼執 行。 直接遞迴 (direct recursion) : 遞迴函數自己呼叫自己執行的情況。 間接遞迴 (indirect recursion) : 遞迴函數A呼叫函數B執行，函數B呼叫 函數C執行，最後會有函數再呼叫遞迴函數A執行的情況。

遞迴式思考 三階段 呼叫 遞迴呼叫 主程式 副程式 撰寫與測試遞迴程式 實際的應用 紙上作業

階乘(factorial) 求5! 求4! 5!=5x4! 求3! 4!=4x3! 求2! 3!=3x2! 結果 5!=120 2!=1x2 1!=1 2!=2x1=2 3!=3x2x1=6 求5! 5!=5x4! 連續呼叫 求4! 4!=4x3! 傳回 4!=24 求3! 求2! 傳回 3!=6 3!=3x2! 結果 5!=120 依序傳回值 傳回 2!=2 2!=1x2 1!=1 傳回 1!=1

遞迴演算 寫出來的程式比較整潔 占用系統資源比較多 一種結構化設計

排序 排序 排序的時候有兩個主要的操作 : • 比較關鍵值的大小。 • 移動資料項目。 　　資料結構與資料庫衍生出來的大量資料常有排序的需要 ，例如字典、電話簿與人事資料等，資料本身通常都具有某種結構，所以排序的時候可能會依據資料中的某種值，例如字母順序或是身分證字號等，我們把這種值稱為關鍵值 排序的時候有兩個主要的操作 : •  比較關鍵值的大小。 •  移動資料項目。

排序 排序的方法很多，學習的時候可以把握 下面幾個要點 : •了解排序法屬於內部排序還是外部排序。 •認識排序法的原理與演算。 •嘗試實作。 •比較各種排序法的效率。

排序 內部排序法 資料量不大，排序的資料放在主記憶 體裡頭 外部排序法 (external sort) 資料量很大，無法全部放到主記憶體 中，必須倚賴輔助記憶體

排序 直接排序法 1.計數排序 2.氣泡排序 3.選擇排序 執行效能不理想 平均執行時間 O(n2)

排序 進階排序法 1.合併排序 2.快速排序 3.堆積排序 4.樹狀排序 執行效能比較好 平均執行時間 O(n log n)

搜尋 線性搜尋 1.最單純的搜尋方式 2.資料本身不需要先排列 3.不適用於資料量大 4.線性串列 (linear list) 常用來當 　 1.最單純的搜尋方式 2.資料本身不需要先排列 3.不適用於資料量大 4.線性串列 (linear list) 常用來當 成搜尋的實例

搜尋 二分搜尋法 1.資料本身需先排列 2.樹 (tree) 是常見的搜尋結構 3.在搜尋的效率上，有很多搜尋樹 (search 4.最佳化的二元搜尋樹 (optimal binary search tree) ，就是要尋求搜尋成本最小的 二元搜尋樹 5.其他的搜尋樹還包括 : •AVL tree •2-3 tree •2-3-4 tree •Red-black tree

演算法的型式 分割克服法 攤還法 貪心法 動態設計法 回溯法 分歧設限法

分割克服法(divide-and-conquer) 模組化 利用遞迴設計效率不錯演算法 大問題分割小問題，找出小問題解法 再合併 快速排序、選擇排序、合併排序都是 使用分割克服法

攤還法(amortization) 分析工具 平均狀況分析 攤還執行時間 一系列的操作中以最糟執行時間來 除以操作的數目 圖型追蹤演算法

貪心法(greedy method) 分階段找出最適化解法 每階段中必須做出決定 選出該階段最佳方法

動態設計法(dynamic programming) 難度較高方法 以最適化為原則 每一個最適化決定形成的最適化形 成序列所含的次序列也是最適化的

回溯法(backtracking) 尋求解決時採用系統化方法 訂出可能解法形成的解決空間 解決空間通常會形成樹或圖型結構 依據選出表示法,檢視評估各解法 檢視過程好像回溯一樣 深度優先搜尋方式

分歧設限法(branch and bound) 與回溯法很相似 採用廣度優先搜尋方式 最低成本搜尋方式 在空間需求上較回溯法為高

二元搜尋問題 演算法的選擇 程式設計的技巧 系統資源的使用狀況 系統執行的環境與架構 成本效益

第八章運算理論基本觀念 三個傳統的領域 自動機(automata) 運算性(computability) 複雜度(complexity)

自動機(automata) 探討運算的數學模式 應用於 1.文字處理 2.編譯器 3.硬體設計 4.上下文無關文法 5.程式語言 6.人工智慧

運算性理論 (theory of computation) 探討電腦硬體、軟體 各種應用的數學特性 幫助我們了解電腦運算能解決與不能解 決的問題加以分類 運算的快慢、需要的記憶體空間，以及 使用的運算模型 下推自動機用來描述記憶體無限運 算機器但能用於LIFO

杜寧機器(turing machine) 1936 強大模型 記憶體無限 相當精確的模型 可以完成任何真正電腦可以完成的 工作

運算性(computability) 自動機與 turing machine差異 2.讀寫頭可以左右移動 3.磁帶是無限長的 4.產生的接受或拒絕的狀態有立即的效應

turing machine 的實例 q10000 ㄩq5x0xㄩ ㄩxq5xxㄩ ㄩq2000 q5ㄩx0xㄩ ㄩq5xxxㄩ ㄩx0q40 ㄩxq20xㄩ ㄩq2xxxㄩ ㄩx0xq3ㄩ ㄩxxq3xㄩ ㄩxq2xxㄩ ㄩx0q5xㄩ ㄩxxxq3ㄩ ㄩxxxq2ㄩ ㄩxq50xㄩ ㄩxxq5xㄩ ㄩxxxㄩq accept

turing machine 的實例 q5 q3 q1 q2 q4 Q reject Q accept 0 L x L ㄩ L x R

Turing machine 雖然我們一直在探討Turing machine，真正的重點其實還是在於演算法，Turing machine只是用來描述演算法的一種精確的模型，演算法才是解決問題的重點，不過要記得Turing machine有辦法描述各式各樣的演算法。至於對於演算法的描述，可能有不同的層次。下面列出3種情況 : 1.以完整的Turing machine的正式定義來描述演算法，這是 最詳細的描述方式，稱為formal description。 2.描述Turing machine移動head的方式，以及對於tape資料 的處理，但是沒有詳細描述狀態與狀態變化，這種描述方 式稱為implementation description。 3.只使用一般的說明來描述演算法，也稱為high-level description。

運算性(computability) 各種語言類別之間的關係 Turing-recognizable decidable Context-free regular

複雜度的理論(complexity theory) 目的 了解運算問題在時間、記憶體與資源方面需求 複雜度是可以測量的 最糟情況分析 以某個長度的所有字串輸入最長執行時間來考量 平均情況分析 以某個長度的所有字串輸入的平均執行時間來考量

時間複雜度(time complexity) 演算法精確執行時間不易表示,只能估計 對大的輸入分析演算法的執行時間，只考 慮高次項，係數可省略（漸進式分析）。 對語言分類可依照時間上需求來區分 令 F:N N為一個函數,時間複雜度類別,TIME(t(n)) 可定義: Time(t(n))={LlL是一個可以由turing machine花o(t(n))時間 決定的語言} 。

時間複雜度(time complexity) 三種模型 1.single-tape Turing machine 2.multitape Turing machine 3.nondeterministic Turing machine

CLASS P 的運算問題 多項式級的執行時間差異不大但指數級 執行時間差異就可觀 多項式級的執行時間差異不大但指數級 執行時間差異就可觀 對於跟deterministic single-tape Turing machine相等的所有運算模型來說，P是不 變的，所以在數學上p是健全的，不會因為運算模型的不同而異。 Class P的運算問題基本上是真正的電腦能夠解決的問題，這是跟實際情況相關的。

CLASS NP 的運算問題 nondeterministic polynomial time problem Satisfiability problem 是一種 NP-complete problem

空間複雜度 EXPTIME PSPACE NP P

第九章自動機理論(Automata) 一個系統的數學模型 極為有限記憶體的電腦 1 0 1 1 q2 q2 q2 q1 q2 Σ={0.1} Σ可以用表格描述 q1為開始狀態 F＝｛q2｝ 1 0 1 1 q2 q2 q2 q1 q2 q1 q3 q2 q3 q1 q2 q3 0,1

形式語言(regular language) 能被某種有限自動機辨識 (recognize)的語言也稱為形式語言(regular language) 形式語言時通常都會聯想到形式表示法(regular expressions)，在字串處理上經常會用到 形式語言也可以透過所謂的regular 　operations來擴充 regular operations是用來處理語言的

形式語言(regular language) 設計辨識語言有限自動機 1.先了解需哪些資訊來判斷，然後以有限可能　 　性來表示資料 ２、將個別狀態分配給各種可能性 ３、讀取符號後各種狀態之間可能發生轉換 ４、決定無輸入時開始狀態

形式語言(regular language) １、０ ０ １ ０ ０ １ q001 q q0 q00 １ 1.還沒看到００１的任何一部份 2.看到一個０ 3.看到００ 4.看到００１

不定性（ Nondeterminism ) 可以視為比determinism更通化的概念 每一個DFA(determinism finite automaton)也可能看成是一 NFA(nondeterminism finite automaton) 在NFA也都可有0個、1個、或多個向外的箭 頭

DFA與NFA在運算中之差異 Deterministic computation start Accept or reject …………. start Accept or reject nondeterministic computation Accept ………….

形式表示法(regular expressions) 形式表示法的值則是一個語言 (０Ｕ１）０＊所代表的語言以０.1起頭，後 　面接任意數目的０ regular expressions在電腦科學領域中有許 　多應用 常用來描述字串的型式，做為比對與搜尋的 　基礎 不能被任何有限自動機辨識的語言則可歸屬 　於非形式語言(nonregular language)，

與上下文法無關的語言 context-free grammar所描述的context- free languages可以用pushdown 　automata來辨識 每一個regular languages都是context-free 　languages 程式由符號組合而成 符號就是由各種字元組合而成

文法四種主要成分 終結符號　（字元或字串形成） 非終結符號　 產生規則 目標符號

ＢＮＦ（backus-naur Form ) 描述程式語言文法方式（中介語言） ＢＮＦ不適合描述一般自然語言 BNF表示法 ＜goal＞::=i-<verb>-<person>-{<amount>}[-dollars]. <verb>::=owe l lend <person>::=you l her l him <amount>::=1l2l3l4l5

下推自動機（pushdown automata) 可以將符號寫入推疊(stack），隨後再 　讀回 寫入動作把其他符號往下推 推疊頂端符號可以隨時被讀取或移除 因記憶體有限自動機無法辨識語言,理論 　上推疊沒有此限制

第10章多媒體領域方面的理論基礎 多媒體的五大元素 1.文字：文字是人類世界中，最重要的媒介，因為它 可以精確表達、記錄資訊。 2.音訊：聲音是人們接收資訊的重要來源之一，它能 夠快速、且直接地提供資訊給人。 3.影像：一圖勝千言，影像資訊的呈現是電 腦科學中 的一個重要里程碑。 4.視訊：視訊是動態的影像，主要由攝影機拍攝真實 世界的景象所構成。 5.動畫：電腦動畫是應用電腦高速運算的優勢下的產 物。

多媒體元素的異同 影像和視訊有何差別？ 視訊和動畫有何差別？ 文字和音訊間有什麼關聯性？ 文字和影像間有什麼關聯性？

相似的特性方面： 具有時間特性：音訊、視訊、動畫 具有視覺特性：影像、視訊、動畫 具有聽覺特性：音訊、視訊、動畫 能精確表達資訊：文字

文字 文字的表示與儲存方式 1.ASCII碼：以8個位元來表示一個字元，故其 2.Big-5碼： Big-5碼為常用的中文字碼，以16 表示資料的能力為28種變化。 2.Big-5碼： Big-5碼為常用的中文字碼，以16 位元表示一個字。 文字輸入 1.鍵盤輸入 2.手寫辨識 3.語音輸入 4.光學字元辨識 文字字型：向量字型 TTF

音 訊 音訊是由聲音構成的媒體。 音訊資料稱為波形音訊。 音訊數位化 間隔時間的長短稱為取樣率，記錄取樣值的精 確度稱為解析度。 音　訊 音訊是由聲音構成的媒體。 音訊資料稱為波形音訊。 音訊數位化 1.電腦透過音源的輸入裝置接收到類比形式的音訊。 2.進行取樣，依固定的時間間隔讀取所測到的聲音內容 間隔時間的長短稱為取樣率，記錄取樣值的精 確度稱為解析度。 音訊資料的查詢與檢索方面較為困難。 常見的CD音樂，是一種品質很好的音訊，其取 樣方式為：取樣率44.1KHz（每秒取樣44100次），解析度16位元。

影 像 影像數位化是將畫面縱橫切割為棋盤狀的方格小點，這些小點稱為像素，每一像素以一個顏色表示以構成完整的影像。 影像色彩目前使用的格式為全彩格式，全彩影像中每個像素點使用了24個位元，對應到色光的三原色紅、綠、藍各使用8個位元。 影像資料所需的儲存空間亦遠大於文字。以像素記錄影像內容的格式稱為點矩陣影像。

視 訊 視訊格式 視訊亦是由動態的影像畫面所構成 從媒體的格式來說，電視所看到的節目、電影院放映的影片都是視訊。 視　訊 視訊格式 視訊亦是由動態的影像畫面所構成 從媒體的格式來說，電視所看到的節目、電影院放映的影片都是視訊。 以訊號的標準而言，視訊以美規(NTSC)與歐規(PAL)為主。 我國電視使用的是NTSC規格，NTSC規格視訊，每秒鐘為30個畫面、每個畫面為525條掃瞄線。 視訊每秒中必須播放約25~30個畫面，每一個畫面即是一張影像，因此視訊所需的儲存空間又遠大於像。

動 畫 影像的靜態，動畫是將畫面以動態的方式呈現。 動　畫 影像的靜態，動畫是將畫面以動態的方式呈現。 Flash為一種2D動畫製作軟體，而3D Studio MAX、Maya則為3D動畫製作軟體。 電腦動畫用於純粹動畫影片製作外，也應用於電影、廣告等影片之製作。 動畫取代真實場景的拍攝而大量減少了影片中因特技所需的道具製作、演員的危險動作。

多媒體資料壓縮 電腦資料壓縮技術無疑是提高電腦資料儲存量與減少資料傳輸負擔的一項重要技術。 音訊資料的數位格式為波形音訊，也就是WAVE格式，而MP3 則可說是目前最為普及的一種音訊壓縮方式。它是 MPEG-1 視訊壓縮標準中的一部分。 AAC則是比MP3更新的音訊壓縮標準，它是MPEG-2中Part 7的音訊規格，提供了48個聲道及16個低頻輔助聲道，有16個資料串，壓縮效率要比MP3高30%。

多媒體資料壓縮 視訊資料壓縮：視訊壓縮以 MPEG 系列標準主。 視訊媒體的播放規格，在 MPEG-1 規格中，制定 可應用於 VCD的視訊規格與壓縮方法，格式為每秒 30 個352 ×240的影像畫面。 MPEG-2 應用於 DVD，格式為 720 ×480 之影像畫面，每秒最高可達60個畫面；MPEG-4 規格可應用於網路上的視訊傳送，格式為 320 ×240之影像畫面，每秒的畫面數為可依網路頻寬配合調整變動。

多媒體壓縮技術發展產生的影響 降低儲存多媒體資料所需的空間。 　多媒體壓縮技術發展產生的影響 降低儲存多媒體資料所需的空間。 減少多媒體在播放的時候從儲存體讀出來的資料量。間接地使播放多媒體對於儲存資料的裝置的資料存取速度的要求降低。 電腦必須能在讀取壓縮格式的媒體資料後馬上解壓縮為原始的格式以便能夠播放，這些工作或由 CPU 或由特殊的解壓縮卡完成。

多媒體處理技術與應用 音訊處理技術 1.音訊處理 2.語音識別 3.聲紋比對 影像處理技術 1.數位暗房2.影像識別 3D繪圖技術 1. 3D影像與動畫2. 3D繪圖速度 視訊處理 1.視訊後製作2.動態偵測  

內涵式多媒體查詢 1.萃取多媒體資料中的內涵作為索引 2.設計查詢方法：依所能萃取出的索 引，建立能提供使用者便利查詢的 方法，讓使用者可以描述所要找的多 媒體資料之內容。 3.查詢處理：多媒體查詢處理的重要挑 戰為多媒體資料本身內容龐大，內涵 資訊亦豐富。  

第十一章其他相關的理論基礎 密 碼 學 1.加密 2.解密 種類： 密 碼 學 1.加密　 2.解密 種類： 1.對稱式加密 (symmetric encryption): DES、AES是對稱式加密法，屬於block cipher，不過DES的安全性堪虞。RC4是stream cipher，曾應用於無線區域網路的WEP協定中。 2.非對稱式加密 (asymmetric encryption) RSA就是一種非對稱式加密的方法。

編碼理論 處理與傳送大量資料精確性要求 錯誤問題的解決 編碼 ENCODING MESSAGE CODEWORD WORD DECODING 解碼

密碼學 安全要求 加密的基本理論（KEY1與KEY2相同則為「對稱式加密」） １、私密性 ２、完整性 ３、辨識 key1 傳送 key2 ２、完整性　 ３、辨識 加密的基本理論（KEY1與KEY2相同則為「對稱式加密」） key1 傳送 key2 加密 解密 明文 原來的明文 發送端 接收端

數位簽章 有效解決電子交易安全問題 私鑰２ 公鑰２ hash 明文 明文 加密 解密 數位簽章 數位簽章 hash 公鑰１ 解密 加密 比對 MESSAGE DIGEST 數位簽章 hash 公鑰１ 解密 加密 MESSAGE DIGEST 比對 MESSAGE DIGEST 私鑰１

加密與解密 方法分類 １、傳統加密解法 位元層次上加密法（ＤＥＳ） 字元層次上加密法 ２、公鑰加密解密法 ＲＳＡ 明文 明文 　　位元層次上加密法（ＤＥＳ） 　　字元層次上加密法 ２、公鑰加密解密法 ＲＳＡ 明文 明文 C=p kp mode N P=c ks mode N 密文 解密 加密

通訊理論 資訊可以透過改變電壓或電流等物理特性的方法在傳輸線材上傳送 用物理特性與時間關係f(t)可以描述訊號的行為以數學來進行分析 傅立葉級數 頻寬加倍時資料也加倍

薛南容量 訊號雜訊比即訊號與雜訊的能量比值 (SNR)db=10log10 signalpower/noise power=10 log10 SNR SNR 值越高表示訊號品質越高 增加訊號強度或頻寬都會增加資料速率 頻寬都會增加會使white noise 增加，但SNR值變小。 數位訊號是由無數組成頻率訊號合成故頻寬是無限的

分貝(decibel) 分貝(decibel)與對數用來描述訊號強度的增益與衰減，計算上與實際的應用上很方便。 Ndb = 10 log10 p2/p1 Ndb：分貝數 p1：輸入強度 p2：輸出強度

謝 謝 聆 聽