Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/119577
|
| Title: | 應用ASP於演算法課程的測試題目生成
Applying Answer Set Programming to the Generation of Testing Problems on the Course of Algorithm |
| Authors: | 郭峻瑋
Kuo, Chun-Wei |
| Contributors: | 陳正佳
Chen, Cheng-Chia
郭峻瑋
Kuo, Chun-Wei |
| Keywords: | 演算法
題目生成
Answer Set Programming |
| Date: | 2018 |
| Issue Date: | 2018-08-27 14:45:45 (UTC+8) |
| Abstract: | 使用試題測試學生對於學習內容的了解程度，是學習過程常見且有效的方法。然而現今試題主要來源不外乎教師自行設計，使用書商或第三者所製作的題庫內容，其衍生的問題包括:人工試題，耗費老師過多時間；題目過少，易於重複以及制式化試題不一定符合需求等。本研究針對演算法學科的特定解題演算法，例如排序問題、最長公共子序列、霍夫曼樹最佳編碼、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. |
| Reference: | [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/ |
| Description: | 碩士
國立政治大學
資訊科學系
104753030 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0104753030 |
| Data Type: | thesis |
| DOI: | 10.6814/THE.NCCU.CS.008.2018.B02 |
| Appears in Collections: | [資訊科學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| 303001.pdf | 5821Kb | Adobe PDF2 | 371 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
