交通大學資訊科學與工程研究所學位論文
國立交通大學,正常發行
選擇卷期
- 學位論文
GPU原為設計用來處理圖形方面應用之處理器，因為其多核心與單指令流多執行緒架構，已有越來越多演算法被平行化並使用GPU來加速。本研究使用GPU來加速電子自動化設計中常需使用到的演算法 – 在以格線為基礎的圖形內的繞線演算法。我們提出了每一個節點由一個執行緒控制為基礎的演算法，並使用三個方法來加速，分別是判斷並只呼叫需要更新的區域、減少分歧路線、避免資料讀取衝突，之後我們將此演算法應用至以下三個問題中 – 全點對最短路徑問題、使用緩衝器ECO來解決時間優化問題、三維全域繞線器。實驗結果指出在全點對最短路徑問題中，GPU最多可加速至CPU的31.2倍，ECO問題亦可透過GPU加速至平均13.7倍，三維全域繞線器與GLADE [1] 比較之結果，可繞出合法解之平均總線長短1.6%，但時間花費為GLADE的9.84倍且解不出的overflow亦比GLADE還要高，但若與CPU相比，GPU的時間比CPU提升了11.52倍。
- 學位論文
在現在的時代裡，付費電視已經變成一個普遍的訂閱服務。為了防止沒有付錢的人非授權的存取電視內容，付費電視的供應商通常會對每一個頻道的內容加密，並把對應的金鑰分配給合法的使用者，如此一來，只有合法的使用者才可以正確解密。用來維持和分配一個共有的解密金鑰給眾多的使用者的方法，通稱為群組金鑰管理。 在這篇論文，我們提出了一個很適合付費電視系統且安全有效率的樹狀架構群組金鑰管理方法。之前的樹狀架構有以下優點，每個使用者只需要存O(logN)個密鑰，每一次群組金鑰更新時伺服器只需傳送O(logN)個訊息，N 為使用者的總數。除了之前的這些優點外，我們的方法還有另外兩個特點：(1)當有使用者加入或離開時，其他的使用者只需要計算一次就可以取得群組金鑰。(2)為了使離線的使用者重新上線時可快速取得最新的金鑰，伺服器只需要在佈告欄存O(N)個公開訊息，而一個離線的使用者只需要解密O(logN)次就可以更新最新的金鑰和群組金鑰，所需的解密次數與離線時間有多少次更新無關。在付費電視系統，這些特點不只最小化群組金鑰更新的延遲時間，並使系統在頻繁的金鑰更新之下更為實際。在最後，我們有討論如何將我們的群組金鑰管理方法用於多個頻道的服務上。
- 學位論文
紋理合成被廣泛的使用在電腦圖學以及影像合成的領域中；然而卻很少有 研究從人類視覺系統(HVS)的方向來評估紋理合成的結果。從人類視覺系統 方向來評估的方法，實際上包含注意力(attention)以及認知(cognition) 這兩個複雜的過程。在實做上，因為注意力是視覺訊息處理的第一步，因 此我們著重在注意力這個部分。我們提出了一個在結構貼圖上的視覺注意 力計算模型，此模型是建立在當人類受測者在評估一張紋理合成貼圖的結 果時的凝視行為。我們的模型模擬了人類視覺系統中自下而上(bottom-up) 的過程以及自上而下(top-down)的過程；其中前者是去提取貼圖中低層次 的結構特徵，而後者是建立在可以學習紋理合成結構特徵以及人類凝視點 之間關聯的類神經網路。我們將我們的成果和被普遍拿來當作自然圖片的 視覺注意力模型的顯著圖(Saliency Map)相比。在44 張受測試的貼圖中， 我們的模型正確的預測了79%的凝視點位置，而顯著圖只預測了55%的凝視 點位置。我們的模型對於紋理合成的算法有很大的幫助，因為它可以有效 的將運算資源分配給比較吸引人類觀察者注意的區域。
- 學位論文
嵌入式裝置上的應用程式於運算時經常受到運算資源和能源上的嚴格限制。然而因資源受限而導致運算時間過長及消耗大量能源是不被使用者接受的，因此應用程式是否能有效利用嵌入式裝置上的資源是一個重要的研究議題。現有的執行時間和耗能分析工具可幫助開發者找出應用程式其效能與耗能的瓶頸，但當這些工具提供詳細資訊給使用者的同時需要大量的記憶體空間來儲存分析過程中所產生的資訊，而記憶體空間在嵌入式裝置上也經常受到嚴格的限制。這篇論文提出一個於移動式裝置產品上可變更設定以切換解析度來多層級剖析耗時與耗電的工具。此工具先插入分析程式碼於所有目標應用程式的原始碼，然後再藉由設定所插入的分析程式碼來切換分析的範圍並過濾掉大量不需分析的資訊以達到減少分析資訊量的目的。分析出的資訊量在瀏覽網頁的情境下比Android的debug class少25倍，且我們工具分析的時間資訊在同樣的瀏覽網頁情境下其數據誤差率比debug class低24倍，這是因為debug class的數據是藉由java methods的進入時間點來計算而造成數據並不精確。另外此工具對於CPU和memory所造成的額外負擔在瀏覽網頁的情境下分別為5%和6.53%。最後，經由我們設計的工具剖析後發現瀏覽網頁的效能瓶頸在於2D繪圖函式是使用CPU來繪畫網頁內容，未使用任何硬體加速導致用繪畫速度很慢。
- 學位論文
典型的動態分析會搭配封閉的網路環境以避免惡意程式在分析過程攻擊到網際網路上的機器。然而，現今的惡意程式大多需要連線到網際網路以運作。由於連線到網際網路的流量被阻擋，搭配封閉網路的分析環境用途遭受限制。我們提出一個系統，允許動態惡意程式分析環境擁有看似無限制的網際網路存取權，並且透明地將惡意流量導向系統內的誘捕器，同時允許無害的控制流量存取網際網路。在2000多隻可疑的惡意程式中，我們首先選擇被四套防毒軟體標記的124隻惡意程式。接著，我們排除那些沒有網路行為或者無法成功連線到它們設計好的機器的惡意程式。最後，我們總共有12隻惡意程式樣本。實驗結果顯示，我們的系統可以看到的網路行為平均是封閉網路的3.35倍，在分析發送垃圾信件的惡意程式的情況下，我們甚至更勝於開放網路環境。同時，網際網路的安全性也會被改善。
- 學位論文
人們的生活中處處充滿了不同的連結行為，例如連上網站漫遊、寄信給朋友或是打電話給友人等。這些連結行為最適合透過演進圖來觀察使用者的連結現象。假設我們有一個持續紀錄使用者連結行為的日誌，則當一個不同的連結對象出現時，我們可能會相當好奇還有那些使用者也會跟這個新的對象建立連結。 在這裡，我們提出了一個預測新連線行為的架構。透過持續紀錄、更新使用者的連結行為履歷，我們可以了解使用者的喜好與興趣，並以此為基準預測新的連線行為。我們的中心想法是：如果使用者與他人有一致的喜好或興趣，則他們有很大的可能會與相同的對象建立連結，當然也包括了新出現的連結對象。在這裡，我們不止紀錄使用者的常態連結行為於其履歷，同時也紀錄了使用者最近才有的、不同以往的連結行為。 我們用了一個現實生活中的連結資料來驗證我們的想法，並與目前最新、最好的方法進行比較。實驗結果顯示，我們的方法不僅比已知最新、最好的方法有更好的效能，而且擁有更少的計算時間，不 會隨著的歷史資料的長度而增加。除此之外，我們了解到預測這類新的連結行為時，觀察使用者最近改變的興趣、喜好，比觀察使用者長久以來的興趣、喜好來得有用。
- 學位論文
隨著時代的演進，手機逐漸成為人們外出時，不可缺少的東西，然而隨著手機的功能越來越強大，不僅僅只適用於通話之中，在日常生活中，常因為各種因素如：宗教信仰(素食、禁止吃牛肉、豬肉或飲酒等)、體質問題(過敏、疾病)以及減重需求需計算每日卡路里的攝取等因素，而這些因素將影響我們對於飲食的需求，因為宗教信仰而不能吃某些食物，因體質問題必須進行飲食控制等，現在我們可以利用手機來協助改善我們外出飲食購物的需求。為此在本論文當中，將提出一套系統-”EZBuy My Product Info”，使用者可以利用該系統，方便地購買符合使用者的喜好和需求的產品，而這套系統將結合網路服務平台與手機軟體應用。透過網路服務平台，使用者需先行註冊個人資訊與特殊需求並進行編輯，例如：宗教信仰、慢性疾病或體質問題，造成在飲食中不能有哪些食物出現，以及查詢歷史購物清單，了解曾經買過哪些產品或是分享所買的東西，如：建議購買的產品、寫出他們對於購買該商品的評價，以及提供飲食控制與健身相關資訊等。而在手機軟體之中，藉由手機裝置上的攝影機，針對所想要購買的產品，掃描上面的條碼資訊，與所提供的網路服務平台進行連線，透過條碼資訊進行產品查詢，取得產品的各種資訊給予使用者參考，如：產品中包含的成分是不是有不符合特殊因素需求，例如包含：牛肉、豬肉或是素食等、有哪些疾病者可能需要注意這些產品可能對你會有所影響或是該產品中所包含的卡路里有多少等各種資訊。然而根據使用者使用本系統後進行調查每位使用者對於該系統的功能是否可協助他們的需求，，本系統對於使用者而言可以提供一個方便的查詢他們對於購物時的參考資訊來源。在另外一方面，也將針對實作系統所需之條碼讀取技術進行探討。
- 學位論文
樂譜縮編(Score Reduction)是一個透過縮編樂譜來達成為單一樂器編曲的過程。在本篇論文中，我們提出了一個使用樂譜縮編方法的編曲架構，此架構可以自動化為一樣樂器進行編曲。根據樂譜縮編的方法，我們要盡可能地包含原曲的每一個部份，並同時滿足目標樂器可彈奏性的限制，使得編曲出來的音樂聽起來和原曲相同。在本架構的第一個步驟中，我們分析原始曲目的音樂編曲元素(Arrangement Element)。接著，將音樂中的每個樂句辨識出來，並且根據音樂編曲元素分析的結果與樂句的特性，來分配每個樂句的重要程度。最後，我們將音樂編曲轉換成一個最佳化的問題並設計一個演算法來解決這個問題。藉由挑選適當的樂句並且同時考量目標樂器的可彈奏性，來完成編曲。在實驗中，我們使用這個編曲架構來實作一個鋼琴編曲的系統。許多的實驗被設計來評估我們系統所產生出來的音樂。為了避免主觀的影響，我們採用了一個類似圖林測試(Turing Test)的方法來評估這個系統的好壞。實驗的結果證明我們的系統有能力編寫出具品質且可彈奏的曲子。 此外，為了捕捉到原始音樂的特色，我們介紹了一種新的樣式－多音重覆樣式，並提出兩個演算法－A-PRPD (Apriori-based Polyphonic Repeating Pattern Discovery) and D-PRPD (Depth-first-search based Polyphonic Repeating Pattern Discovery)，從原始音樂中探勘多音重覆樣式。再者，我們設計了位元方法(bit approach)用於我們所提出的兩個演算法上加速運算。實驗結果顯示，我們提出的演算法是有效率與效果的，並且D-PRPD演算法加上位元方法在大多數的情況下是最有效率的演算法。此探勘出的重覆樣式可以被使用在此音樂編曲架構中的功能性分配的步驟中，使得具有原始音樂特色的樂句較容易被挑選到。
- 學位論文
Menger在1972證明「圖G中任兩個相異點都存在著k條不相交的路徑若且為若圖G的是k連通」。如果圖G任兩個相異點都存在著k條不相交的路徑，同時此k條不相交的路徑會通過圖G所有的點，則稱圖G為k*連通。圖G的生成連通度*(G)是最大的整數k，使得對所有不大於k的值w，圖G為w*連通。我們將針對一部分的交換網路與圖形研究其生成連通度。 在圖形理論的研究中，圈嵌入和路徑嵌入的問題一直是重要的研究議題。圖G的一個漢米爾頓圈C可以依經過的次序描述為< u1, u2, …, un(G), u1 >。因此，我們稱u1為C的起始點而稱ui為C的第i個點。假如圖G的兩個漢米爾頓圈 C1 = < u1, u2, …, un(G), u1 > 和C2 = < v1, v2, …, vn(G), v1 > 的起始點相同且除了起始點和最後一個點之外彼此的第i個點都不相同，則稱這兩個漢米爾頓圈彼此獨立。假如圖G的漢米爾頓圈的集合{ C1, C2, …, Ck }之中的漢米爾頓圈兩兩獨立，則稱這個集合為互相獨立。圖G任給一個點u作為起始點至少都能找到的互相獨立的漢米爾頓圈的個數的最大值，稱為圖G的互相獨立漢彌爾頓度。我們將探討一部分的交換網路與圖形的互相獨立漢彌爾頓度。