交通大學資訊科學與工程研究所學位論文
國立交通大學,正常發行
選擇卷期
- 學位論文
在高效能視訊壓縮（High Efficiency Video Coding，H.265/HEVC）的開發過程中，畫面內線型區塊複製模式（Intra Line Copy，ILC）與字串複製模式（Intra String Copy，ISC）為兩個能有效提升視窗視訊編碼效能的編碼工具。此兩模式皆以無失真資料壓縮之字串匹配演算法為基礎，但其設計與實作卻有相當顯著的差異。於本論文，為了探討畫面內線型區塊複製模式與字串複製模式的優劣，我們將針對兩模式之編碼效能進行評比，內容涵蓋壓縮效率、複雜度與記憶體存取頻寬三項。實驗結果顯示，兩模式之編碼效能相當且互有所長，畫面內線型區塊複製模式能有效提升自然與視窗影像混合視訊的編碼效能，而字串複製模式對於單純視窗視訊則有較佳的編碼表現；當考慮兩模式對於記憶體存取頻寬的影響，區域搜索相對於整張畫面搜尋較易實現於低延遲與即時的應用中。
- 學位論文
我們過去曾發展過一個六子棋程式稱為交大六號(NCTU6)，該程式以及其延伸版本，在所有國內外電腦對局競賽的六子棋項目中均獲得冠軍，也在多次人機競賽中擊敗許多頂尖高段棋士。然而在長時間思考的棋賽中，發現即使每手可計算數小時，卻仍然有些著手明顯不佳，進而造成輸棋。本論文藉由這些不佳著手分析NCTU6與工作層級的弱點，並且提出靜態調整、動態調整、提升走步排序品質與活五處理等改良方法。實驗結果顯示，使用靜態調整、動態調整的版本對原程式勝率達到59.6%。使用提升走步排序品質後，對前面改良過版本勝率達58.95%，且能使NCTU6在某些先前下出不佳著手的盤面中，找出我們認為理想的著手。其它的調整也對不佳著手有所改良。
- 學位論文
近年來「有感」的概念不斷被提及，如政府希望落實的「有感施政」以及「有感經濟」等等。我們常常可以看到政府公布了一些經濟指標數據，如平均薪資提高、就業環境變好等等，但也時常可以見到民眾表示這些數據與他們的實際感受不相符的情況。民眾無法認同指標的情形可能起因於指標本身的建立是站在國家管理的角度，或是社會存在階級差異等等。因此，指標的建立若是能以一般民眾的觀點出發，由日常生活中就會接觸到的事物來建立一套大家都能輕易了解的經濟指標，則對一般大眾而言，指標顯示的結果可能比較會有「有感」的感覺。故本研究以虛擬世界為平台，探討能否在虛擬世界中找出某些商品，它們在市場上的數量會隨著虛擬經濟體的經濟狀況變化而變動，玩家也就能在虛擬世界中透過觀察這些商品在市場上的數量變化，了解所處經濟體當前的經濟狀況，我們將擁有這樣特質的商品稱為「指標商品」，並且討論這樣的指標除了能顯示經濟狀況外，還能讓我們看到玩家哪些特殊的消費行為與偏好。 本研究以《魔獸世界》為研究平台，發現到了在《魔獸世界》的各經濟體中都能夠找到其數量變動能夠反應經濟狀況的指標商品，但各經濟體的指標商品並不存在交集。而《魔獸世界》的指標商品在類型上以裝甲類型為大宗，玩家購買這些裝甲類型指標商品的目的是以「分解」與「塑形」為主。另外，本研究也發現到了不同遊戲型態的伺服器，其指標商品的組成也會有所不同。
- 學位論文
本研究旨在建立一個針對動態語言的通用預先編譯架構。由於動態語言提供使用者較為靈活的設計特性，在特定領域一直受到開發者歡迎，近年來更成為與許多應用的核心語言，因而其執行效能對使用者操作體驗有重大影響。目前已有許多相關研究試圖改善個別語言的執行效能，然而由於動態語言的程式結構與型別資訊須經由直譯器動態解析，因而最佳化與編譯流程需依賴個別直譯器實作，而無法如靜態語言建立一通用編譯分析架構。 本研究實作基於LLVM此一靜態語言編譯分析架構，針對其IR作延伸使其能表現前端動態語言之語意，並且能支援動態型別與物件之程式模型。在此架構上實作型別分析流程，以靜態分析方法將型別資訊紀錄於IR結構上，最後將具有完整型別資訊且能夠被靜態編譯的程式轉換成標準LLVM IR此靜態表現形式，能夠直接應用其他現有最佳化技術。本研究主要貢獻在於將靜態型別分析流程抽象化，使單一分析流程能較容易被應用於其他動態語言。基於一共同架構上，分析流程之實作能夠被重複利用，而不用針對各種語言重複實作。 本研究以JavaScript作為第一個前端語言，並將產生的LLVM IR轉成Asm.js以測試對網頁應用的效能改進，實驗結果顯示在能夠被編譯的benchmark程式中，效能提升最高可達45%。
- 學位論文
Cyber Grand Challenge(CGC)是由美國國防部高等研究計畫署(DARPA)舉辦的全自動化電腦攻防競賽。本論文參考競賽規則，結合模糊測試、錯誤定位、與修補三樣技術，建造一個全自動化的Cyber Reasoning System(CRS)。我們實驗室在自動化攻擊方面已有成果，因此希望結合錯誤定位技術，進一步發展成自動化修補技術，形成一個全自動化的攻防系統。除了競賽題目外，我們嘗試將系統應用在真實程式的漏洞，希望以自動化的方式改善資訊安全，彌補人力無暇顧及的部分。
- 學位論文
本論文主旨是在Xilinx ZedBoard平台建立起Heterogeneous System Architecture (HSA) 整個Runtime執行環境用以實現ARM與GPU的協同運算。 在當前HSA官方提供的原始碼只能適用於AMD官方的x86 APU產品協同運算，無法支援在其它平台下運作。本論文逐一分析了HSA官方的x86實作版本並且把它們各自移植到ZedBoard上的Xilinx Zynq 7020 SoC，由Zynq內的雙核心ARM IPs及Zynq 內的FPGA IP所合成出的Virtual GPU進行協同運作。整體設計上共移植了兩份User-space libraries、一份Kernel-space driver，另外則是在整個流程最後面新建立了一份負責與硬體實際進行溝通的Kernel-space driver。
- 學位論文
影片的高階語意事件辨識已發展成為多媒體搜尋與索引領域最有趣的研究議題之一。因為影片低階特徵與高階事件在語意上距離遙遠，需要提出一個階層式的影片分析架構，利用中階特徵連結低階的聲音視覺特徵和高階語意事件。因此這篇論文提出一個使用中階時間區間特徵相互間時間前後關係的影片事件分類架構。在此架構中，我們提出了一個共同出現符號轉換方法來探勘隱藏式馬可夫模型機率事件分類架構中多種來源特徵間的完整時間關係。另外，資料探勘和頻繁樣式分析已成為從資料中發現新知識很受歡迎的方法，但是卻幾乎沒有被應用到影片語意分析領域，因此這篇論文提出兩種方法整合頻繁樣式分析和多模隱藏式馬可夫模型棒球事件分類，包含利用頻繁樣式訓練的隱藏式馬可夫模型和依照頻繁樣式設計的隱藏式馬可夫模型。除此之外，不同的時間序列編碼方法也被提出來和共同出現符號編碼法比較分類效果。實驗結果證明我們提出來的方法在棒球影片事件分類的優越性以及整合頻繁樣式分析至事件分類架構有助於提升事件分類的效能。
- 學位論文
以布林函數計算複雜度的研究領域而言，多項式次方是重要的測度。在本論文裡，我們針對受n個變數影響的布林函數，證明數個次方下界限。如果對於所有 x,yin{0,1}^{n}，f(x) eq f(y) Rightarrow P(x) otequiv P(y) mod(m)成立，則多項式P(x)in Z_m[x]稱為f(x)佈於Z_m的廣義表示法(generalized representation)}。令m_1與m_2為互質的正整數，而且各自具有s個與t個相異質因數。假設P_1(x)in Z_{m_1}[x]與P_2(x)in Z_{m_2}[x]都是對稱(symmetric)多項式，而且同時是某個對稱函數f的廣義表示法，我們證明 m_1m_2deg(P_1)^sdeg(P_2)^t>n 成立。 如果對於所有xin{0,1}^{n}，f(x)=0 Leftrightarrow Q(x)equiv 0 mod(m)成立，則多項式Q(x)in Z_m[x]稱為f佈於Z_m的單邊表示法(one-sided representation)。則考慮與前述結果相同的條件之下，並令Q(x)與widetilde{Q}(x)in Z_{m_2}[x]分別是對稱函數f與 eg f的單邊表示法。我們證明 m_1m_2deg(P_1)^sdeg(Q)^t>n 與 m_1m_2deg(P_1)^sdeg(widetilde{Q})^t>n 至少有一個會成立。請注意Q(x)與widetilde{Q}(x)可以是非對稱多項式。 接著考慮f(x)是非對稱(non-symmetric)布林函數。令Pin Z_{m_1}[x]是f的一個廣義表示法 ，而且Q(x),widetilde{Q}(x)in Z_{m_2}[x]是 eg f的一個單邊表示法。我們證明幾乎必然(almost always) m_1m_2deg(P_1)^sdeg(Q)^t>log_2{n}-O(1) 與 m_1m_2deg(P_1)^sdeg(widetilde{Q})^t>log_2{n}-O(1) 至少一個會成立。 假設f與表示法裡出現的n個變數都有關，則稱為非退化(nondegenerate)函數。我們證明針對任何非退化的函數f，都存在一個變數x_i，使得f|_{x_i=0}與f|_{x_i=1}這兩個限制子函數之中，至少有一個仍然與剩下的n-1個變數有關。可以進一步推論得知，針對任何k是1到n-1間的任意整數，存在留有k個自由變數(free variable)的部分賦值(partial assignment) ho，使得子函數f|_{ ho}與k個變數有關。
- 學位論文
隨著製成的演進，以及製成的規範越趨嚴謹，完全依靠人力來處理佈局圖已漸漸無法負荷。尤其在繞線方面，因為繞線的空間越來越小，且佈局圖的架構也不斷的改變之下，繞線已經變得非常複雜。此篇論文主要是改進傳統的繞線流程達到更好的可繞度，並且把細部繞線演算法應用於標準元件的繞線當中。實驗結果顯示，許多的基本標準元件必須使用新的流程才能產生。同時，部分較複雜的標準元件也因為使用細部繞線演算法而順利完成，且能達到與業界相匹配的品質。
- 學位論文
行動網路的流量隨著智慧型行動裝置的普及而快速成長，為了要因應快速成長的流量，異質網路整合被視為一個可行的解決方法。透過異質網路(如長期演進技術網路與Wi-Fi無線網路)覆蓋範圍的重疊，行動電信營運商可以使用卸載服務(如Wi-Fi網路卸載)來減少網路壅塞。因此，需要一個合適的網路協調機制來達到Wi-Fi網路的負載平衡。在本論文中，我們使用存取網路搜尋與選擇功能來建議使用者裝置存取合適的基地台(如長期演進技術的演進節點B與Wi-Fi網路基地台)以達到負載平衡。我們整合存取網路搜尋與選擇功能和體定義網路來讓此整合式網路具備可程式化，彈性與可動態管理的特性。此外我們也提供一個省電的演算法來適當地配置網路資源給使用者裝置，以節省Wi-Fi網路基地台的電力。經由所提之模擬模型與效能評估結果顯示，當網路流量不平衡的時後，我們提出的演算法與以往的研究相比，能夠因應幾乎同樣數量的使用者裝置資源請求，且我們提出的演算法可以省下15.62%的Wi-Fi基地台電力。