請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/19846
標題: | 由程式動態行為偵測所使用之演算法 Detect Algorithm Used From Program Execution Trace |
作者: | Pi-Hsun Shih 時丕勳 |
指導教授: | 鄭卜壬(Pu-Jen Cheng) |
關鍵字: | 程式碼,演算法相似度, Source code,Algorithm level similarity, |
出版年 : | 2015 |
學位: | 碩士 |
摘要: | 本論文主要目的在於處理競賽程式中,程式碼在演算法層面的相似度的問題。計算程式間演算法層面的相似度可以被用在程式碼的檢索以及分類,但過去相關的方法多半不能被用在找出演算法層面的相似度上。為了解決這問題,我們在程式執行時的變數數值變化中,找出一些我們稱為 “核心值” (core values) 的,與其使用的演算法有強烈相關的數值。本論文提出了四種不同的方法來找出這些核心值,並且提出了在這些核心值序列上加上權重的方法。我們標記了一個有十八個演算法,約四百五十個程式的測試資料集,並且用此資料集測試了提出的方法的性能。測試結果顯示我們找到的相似度,確實能反映出程式是否使用相同的演算法。 This thesis address the problem of detecting algorithm similarity of source codes from competitive programming. Detecting algorithm similarity can be applied to retrieval and clustering task for codes on algorithm level, and most past works can’t be applied to finding algorithm level similarity of programs. We solve the problem by extracting some important runtime value that characterise the algorithm used, called core values. We proposed four different methods to extract core values, and a scheme of adding weight to core values. We have labelled a dataset consist of 18 algorithms and about 450 programs, and evaluate the proposed schemes on this dataset. The results show that our approaches are effective to detect similar algorithm. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/19846 |
全文授權: | 未授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-104-1.pdf 目前未授權公開取用 | 449.88 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。