• 學位論文

垃圾郵件收集方式有效性評估與樣本減量

• 學位論文

最大有限分支度d集合問題之啟發式演算法設計與分析

在一個無向圖G = (V,E) 中，最大有限分支度d集合問題 (Maximum Bounded-Degree-d Set Problem) 是在點集合V中，找一個最大的子集合S，使得S所形成的導出子圖 (G[S]) 中所有點的degree都小於等於d。最大有限分支度d集合問題 (Maximum Bounded-Degree-d Set Problem) 是一個NP-complete問題。這篇論文中，我們提出了六個啟發式演算法 (heuristic algorithms) 解最大有限分支度d集合問題 (Maximum Bounded-Degree-d Set Problem)，並且實作這些啟發式演算法。我們透過實驗的方式，比較這些啟發式演算法找到的解集合大小。最後，比較我們所實作的啟發式演算法和最佳化軟體IBM ILOG CPLEX Optimizer 在DIMACS圖上解決最大有限分支度d集合問題 (Maximum Bounded-Degree-d Set Problem) 的執行時間，同時也比較Moser等人在real social networks 圖上實作最大有限分支度d集合問題 (Maximum Bounded-Degree-d Set Problem) 的正確解演算法的結果的執行時間。

• 學位論文

藉由改變最少正負號和刪點以平衡完全圖

一個無向有號圖，它的邊可以被標記為正號或負號。 如果有號圖內的每個cycle的負號邊數量皆為偶數，那該圖即為平衡。在此論文中，我們要研究的問題是藉由改最少的正負號和刪點以平衡完全圖。我們設計一個branch-and-bound演算法和heuristic演算法。我們可以藉由實驗結果顯示出branch-and-bound演算法和heuristic演算法是有效的。heuristic演算法使用一個技巧:考慮α 個點去決定一個點。我們也有把該演算法應用在community detection問題上。我們用兩個已知的benchmark去驗證heuristic演算法。

• 學位論文

最大有限分支度一集合問題之啟發式演算法與分支化約演算法研究

有限分支度一集合問題 (1-BDS) ，是指在一張無向圖 G 中找出一個子集合 S，使得 S 在 G 中的誘導子圖 (induced subgraph) 每個點最多只會有一個鄰居，在圖中找出一組點數最多的有限分支度一集合，就是最大有限分支度一集合問題 (Max 1-BDS) 我們針對此問題提出一個新的簡單的分支約化演算法跟幾個啟發式演算法，並且認為會比前人使用較複雜的演算法更好。 從實驗數據中顯示，啟發式演算法可以找到很好的解，而且分支約化演算法在許多例子中比 Moser 等人的實驗結果比較有效率。

• 學位論文

最小三命中集合問題之新啟發式演算法設計與分析

令C 是由有限集合S 的子集合所構成的集合，一個命中集合(hitting set) D 是S 的子集合，使得每個在C 中的集合與D 的交集個數至少是1。令(S,C) 是這個最小d 命中集合問題(minimum d-hitting set problem) 的輸入，並且限制所有在C 中的集合大小最多是d。當d ≥ 2 時, 最小d 命中集合問題(minimum d-hitting set problem) 是一個NP 完全問題(NP-complete)。這篇論文中，我們提出了三個啟發式演算(heuristic algorithms) 解最小三命中集合問題(minimum 3-hitting set problem)，並且實作這些啟發式演算法。我們透過實驗的方式，比較這些啟發式演算法找到的解集合大小。除此之外，我們以Wahlström 提出的正確解演算法(exact algorithm) 為基礎，實作了一個解決最小三命中集合問題(minimum 3-hitting set problem) 的正確解演算法。啟發式演算法找到的解集合大小是最佳解大小的上限(upper bound)，我們利用啟發式演算法找到的解作為正確解演算法中的初始上限(initial upper bound)。我們根據這個正確演算法的特性，設計一個資料結構可以用來減少程式的執行時間。最後，比較我們所實作的正確解演算法和最佳化軟體IBM ILOG CPLEX Optimizer 在解決最小三命中集合問題(minimum 3-hitting set problem) 的執行時間。

• 學位論文

模擬社會網路生成的改進模型

在社會網路分析中，產生一個隨機網路依舊是很重要的研究議題。在本篇論文中，我們提出了一個新的社會網路生成模型，並考慮了真實社會網路中分離的群體以及朋友關係遞移等等的現象。我們模擬真實社會網路的生成，特別改進了先前模擬模型中沒有考慮到真實社會內含的影響因子，使得模擬的結果能更貼近真實。因此，在我們的實驗結果可以發現這些考慮的因子對社會網路各有不同的影響，也可以解釋了一些真實社會網路反映出得特別現象。

• 學位論文

藉由實驗的方式研究圖論上邊修改問題

HASH(0x210fc5e0)

• 學位論文

對社會網路的抽樣方法

現今社會網路的規模，因為Facebook和Twitter等社群網路服務(SNSs)的發展而變得非常巨大，在一個網路中可能有數百萬個甚至數十億的使用者，如果我們用整個網路去做分析的話會變得沒有效率，所以，如何從原圖抽樣出一個好的樣本是很重要的。在這篇論文中，我們檢驗了一些已知的抽樣方法並且提出一個新的方法。

• 學位論文

資料隱寫技術及其應用之研究

隨著近年來網際網路的蓬勃發展，數位資訊傳輸也因此變得更加地頻繁，如何確保數位資料在網際網路傳輸時的安全性也變得越加重要，所以，能夠有效率並且可以保護數位資料的方法是迫切需要的。資訊隱藏就是因應資訊安全需求所產生的一門研究， 其衍生的相關研究技術諸如隱寫學、可回復式資訊隱藏、易碎型浮水印、機密共享......等等。一般著名的資訊隱藏技術，主要是藉由將機密資訊藏入用來偽裝的媒介上，例如影像、影音或者文件， 讓攻擊者不易察覺其特異之處，藉以躲避惡意的攻擊或竄改，達到資訊安全的目的。 在本篇論文裡，我們提出了兩個可回復式資訊隱藏的方法，以及一個易碎型浮水印的方法。其中一個可回復式資訊隱藏的方法利用了兩個直方圖統計的結果來進行資訊隱藏，並且可以避免不足位/溢位的問題。而另外一個則是利用了開發修正方向的方法以及兩張偽裝影像來達到可回復式資訊隱藏。最後我們也提出了一個藉由最高有效位元以及參照位元來分別產生認證位元的易碎型浮水印方法，來提高回復被竄改之後影像的效能。

• 學位論文

針對電子商務應用的一些認證之研究

在現在的社會中，網際網路與電子化的發明，使得電子商務越來越受到歡迎。進行交易的方式已經越來越方便，而無線電射頻辨識與電子現金在電子商務應用中扮演了重要的角色。然而，電子資料在傳輸過程中容易被攔截以及竄改。因此，為了安全的傳輸資料，制訂一套安全的協定或系統是非常的重要的。 本篇論文中，我們提出一個有關於無線電射頻辨識安全驗證的研究和一個安全電子現金系統的研究。在第一個研究中，我們指出現行無線電射頻辨識安全驗證方法中的弱點，提出一個符合EPC Class 1 Generation 2 這個標準的驗證協定。而此驗證協定不只可以抵抗存在於無線電射頻辨識系統的安全威脅，更可以應用在任何的無線電射頻辨識的系統中。另外，在第二個研究中，我們利用了祕密分享跟橢圓曲線密碼學提出一個在雲端環境中的電子現金系統，根據分析的結果顯示。跟許多已存在的研究相比，我們的系統具備了低成本以及安全性。