政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/119577

政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/119577

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | 全文筆數/總筆數 : 113648/144635 (79%)
造訪人次 : 51659164 線上人數 : 562

RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

搜尋範圍

查詢小技巧：

您可在西文檢索詞彙前後加上"雙引號"，以獲取較精準的檢索結果

若欲以作者姓名搜尋，建議至進階搜尋限定作者欄位，可獲得較完整資料

進階搜尋

主頁 ‧ 登入 ‧ 上傳 ‧ 說明 ‧ 關於政大典藏 ‧ 管理

到手機版

政大機構典藏 > 資訊學院 > 資訊科學系 > 學位論文 > Item 140.119/119577

請使用永久網址來引用或連結此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/119577

題名:	應用ASP於演算法課程的測試題目生成 Applying Answer Set Programming to the Generation of Testing Problems on the Course of Algorithm
作者:	郭峻瑋 Kuo, Chun-Wei
貢獻者:	陳正佳 Chen, Cheng-Chia 郭峻瑋 Kuo, Chun-Wei
關鍵詞:	演算法題目生成 Answer Set Programming
日期:	2018
上傳時間:	2018-08-27 14:45:45 (UTC+8)
摘要:	使用試題測試學生對於學習內容的了解程度，是學習過程常見且有效的方法。然而現今試題主要來源不外乎教師自行設計，使用書商或第三者所製作的題庫內容，其衍生的問題包括:人工試題，耗費老師過多時間；題目過少，易於重複以及制式化試題不一定符合需求等。本研究針對演算法學科的特定解題演算法，例如排序問題、最長公共子序列、霍夫曼樹最佳編碼、Dijkstra最短路徑等等演算法問題進行分析，找尋其演算法特徵，並對其演算法進行試題生成，產生符合需求的試題。本研究採用ASP (Answer set programming)編寫試題生成程式。ASP是一種邏輯程式語言，具有宣告式程式(Declarative programming)的特性，我們只需對試題的需求進行分析並編寫出適當的邏輯編碼，ASP便可以窮舉出所有符合條件的試題數據。這樣的特性非常適合本研究所期望的生產大量符合需求的試題。本研究建構一個網頁介面供使用者輸入資料，選擇自己所需要的演算法以及試題特性，接下來伺服器端即可利用ASP程式產生試題數據，並對這些數據進行包裝，產生試題文字或圖形，最後呈現於客戶端網頁並可依需要供使用者儲存。試題生成完後，除了提供試題文字與圖形供使用者下載外，也提供生成圖形的數據給予使用者。使用者可以使用自己的方式處理數據來生成他們所期望的圖形，或是對數據使用本研究設置的置換功能。使用置換功能將對原數據進行更動，這會導致生成的圖片與原本生成的圖形有差異性，但是不會對計算過程或是試題難易度產生更動。使用者將可利用這些功能產生多個具有多樣性又難易度不變的試題，提高試題生成的品質。 During the learning process of a subject, providing abundant test problems to examine or grade students` understanding of studied contents is a common and effective approach. At present the main source of test problems is nothing more than the teacher`s own design, or test banks provided by booksellers or a third party. However, all these sources have their drawbacks. For instance, it may take too much time for a teacher to manually design all test problems, most sources do not classify problems appropriately and/or lack sufficient number of problems such that it is not easy to select enough questions meeting the need of all tests. The goal of this thesis is to provide a system for the automatic generation of test questions for various algorithms found in the course of algorithm. The considered algorithms include various sorting algorithms, binary search, longest common subsequence, optimal Huffman code, Dijkstra shortest path and minimal spanning tree, etc. In order to produce reliable and valid problem instances enabling the assessment of the students` understanding of the whole tested algorithm, we analyze each considered algorithm and identify some classifying features on problem instances reflecting the spirit of the algorithm. Afterwards, all testing problems are generated and classified according to these features. The core of our system was developed using answer-set programming(ASP). It is a declarative logical programing paradigm employed in many applications and is very suitable for the generation of testing problems. Its generate-define-test programming feature allows us to encode the specification of a test problem together its classifying features as an ASP program from which an ASP solver can generate one or more test problems as its results. Our system also provides a web interface allowing users to select one among many studied algorithms and specify requirements of the desired test problem. The server then accepts these inputs, uses the corresponding ASP program to generate one or more solutions meeting all requirements, and decodes the ASP solutions to generate test problems in textual or graphical format. Finally, it is presented on the user`s browser for the user to view or store. Not only can our system generate test problems, but it can also produce solutions to all generated test problems. Moreover, after generating a test problem, our system provides the optional facility to generate multiple problem instances of the same difficulty and testing features. This allows the instructor to offer different sets of test problems to students in an examination and prevent possible cheating or plagiarism.
參考文獻:	[1]Appserv Retrieved February(2018).From https://www.appserv.org/en/ [2]PHP Retrieved February(2018).From http://www.php.net/ [3]What Is Answer Set Programming? Vladimir Lifschitz Retrieved February(2018).From https://www.cs.utexas.edu/users/vl/papers/wiasp.pdf [4]Non-monotonic logic Retrieved February(2018).From https://en.wikipedia.org/wiki/Non-monotonic_logic [5]DLV Retrieved February(2018).From https://en.wikipedia.org/wiki/DLV [6]Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Marius Lindauer, Max Ostrowski, Javier Romero, Torsten Schaub, Sven Thiele. (2017) Potassco User Guide 2.10 From https://potassco.org/ [7]ASPeRiX Retrieved February(2018).From http://www.info.univ-angers.fr/pub/claire/asperix/ [8]Potassco Trophy Retrieved February(2018).From https://potassco.org/trophies/ [9]Graphviz Retrieved February(2018).From https://www.graphviz.org/ [10]Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed. Fundamentals of Data Structures (pp. 279-310, pp. 333-355) [11]Introduction to Algorithms, Third Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein(pp.16~29, 151~162, 390~397,428~437, 631~633, 658~664) [12]LCS (longest common subsequence problem) Retrieved February(2018).From https://en.wikipedia.org/wiki/Longest_common_subsequence_problem [13]Huffman coding Retrieved February(2018).From https://en.wikipedia.org/wiki/Huffman_coding [14]Binary search algorithm Retrieved May(2018).From https://en.wikipedia.org/wiki/Binary_search_algorithm [15]Apache Retrieved June(2018).From https://httpd.apache.org/ [16]NETCRAFT February 2018 Web Server Retrieved June(2018).From https://news.netcraft.com/archives/2018/02/13/february-2018-web-server-survey.html [17]OpenDSA Retrieved June(2018).From https://opendsa-server.cs.vt.edu/
描述:	碩士國立政治大學資訊科學系 104753030
資料來源:	http://thesis.lib.nccu.edu.tw/record/#G0104753030
資料類型:	thesis
DOI:	10.6814/THE.NCCU.CS.008.2018.B02
顯示於類別:	[資訊科學系] 學位論文

文件中的檔案:

檔案	大小	格式	瀏覽次數
303001.pdf	5821Kb	Adobe PDF2	371	檢視/開啟

在政大典藏中所有的資料項目都受到原著作權保護.

社群 sharing

著作權政策宣告 Copyright Announcement

1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.

DSpace Software Copyright © 2002-2004 MIT & Hewlett-Packard / Enhanced by NTU Library IR team Copyright © - 回饋