Wednesday, November 4, 2009

Online Judge System 起源與由來

起源與由來

Association for Computing Machinery (ACM) 」是一個致力於電腦科學教育的協會,出版大量專業期刊、文獻,舉辦重大的計算機科學會議,在資訊界舉足輕重、名聞遐邇。

ACM 每年度都會舉辦一次「 The ACM-ICPC International Collegiate Programming Contest (ACM/ICPC) 」,是一個給全世界大專院校學生參加的演算法程式設計比賽,比賽目的在於考驗選手臨場時的演算法設計能力、程式編寫能力。 ACM 首先在世界各地舉辦初賽,然後從各個賽區選拔出表現優秀的隊伍,角逐世界總決賽。台灣主要大專院校近十幾年來不遺餘力,積極爭取到台灣賽區的舉辦權和承辦權,並鼓勵學生參與比賽。另外台灣教育部也創辦了類似的「全國大專電腦軟體設計競賽」,藉此發掘優秀的選手,賦予為國爭光的使命。

ACM/ICPC 帶動了演算法程式設計的風氣。世界上許多大專院校的資訊系所,仿照 ACM/ICPC 的比賽模式,紛紛自行開發出即時線上比賽系統,能夠自動批改、評分、計時、統計。學生不必齊聚一堂,就可以相互切磋程式設計技巧。比賽結束之後,便將比賽題目編列題庫,並開放線上批改程式的功能,供學生賽後練習檢討。這套系統大家一般稱之為「 Online Judge System 」,或直接稱為「 Online Judge (OJ) 」。

最古老、也是最有知名度的 OJ ,是由西班牙知名的瓦雅多利大學「 Universidad de Valladolid (UVa) 」開發的「 UVa Online Judge 」。 UVa Online Judge 是台灣人最熟悉的一個 OJ :資訊相關科系的學生,常利用它來磨鍊程式設計技巧;教師將它當作課程教材使用;有許多個人網站從事題目翻譯,提供測試資料集等等。

UVa Online Judge 亦和 ACM 合作,成為 ACM 推廣的一個 OJ ,藉此向大眾提倡程式設計。因此, UVa Online Judge 除了收集自行舉辦的比賽的題目,也嘗試收錄世界各地重大程式設計比賽的題目,以臻豐富完整。有趣的是,歷年來大家口耳相傳、以訛傳訛,便將 UVa Online Judge 誤植為 ACM 了,把 UVa Online Judge 的題庫稱作「 ACM 題目」,利用 UVa Online Judge 訓練程式設計技巧時稱作「寫 ACM 」,約定成俗。

這個網頁有更詳盡的說明: http://1001ml.blogdriver.com/1001ml/589835.html

知名的 Online Judge System

Online Judge - Problem Sets
http://uva.onlinejudge.org/

Sphere Online Judge
http://www.spoj.pl/

高中生程式解題系統 ZeroJudge

http://zerojudge.tw/

由高師大附中所開發的 Online Judge System ,是第一個使用繁體中文介面的系統,實乃台灣人之福。請大家記得懷著感恩的心,謝謝系統設計者。

國際大專院校程式競賽推廣與培訓計劃

http://ptc.moe.edu.tw/

http://140.122.185.166/ZeroJudge/

由台灣師範大學成立的 Online Judge System ,每月定期舉辦線上比賽,歡迎大專院校學生組隊參與。

NTU Online Judge

http://acm.csie.ntu.edu.tw/

台灣大學的 Online Judge System 。目前只用於培訓校內的 ACM/ICPC 參賽選手,並未對校外人士開放。不過各位還是可以在其公開的題庫中,找到許多優質的演算法程式設計問題。

UVa Online Judge

http://icpcres.ecs.baylor.edu/onlinejudge/

http://online-judge.uva.es/board/

西班牙 Valladolid 大學的 Online Judge System 。是最古老也是最知名的 Online Judge ,題庫目前約有 2500+ 題。

PKU JudgeOnline

http://acm.pku.edu.cn/JudgeOnline/

中國北京大學的 Online Judge System ,是中國規模最大的一個 Online Judge ,不乏不少好題目,討論區的牛人也是相當多的。

Timus Online Judge

http://acm.timus.ru/

俄國 Ural 大學的 Online Judge System ,是俄國最大的 Online Judge 。

The 2000's ACM-ICPC Live Archive Around the World

http://acmicpc-live-archive.uva.es/nuevoportal/

此站專門收集 ACM/ICPC 在 2001 年之後的比賽題目,依照賽區地點來做編錄。可惜的是題庫尚未收集完整。

值得一提的是,有些特定賽區的題目特別簡單(如南太平洋區);有些題目會跟 UVa Online Judge 重複;每個賽區都會有一兩題很困難的題目。

起先, Live Archive 的題庫是跟 UVa Online Judge 的題庫捆在一起的,並且共用一套 OJ 。後來,在 2003 年的聖誕節,站方決定將 Live Archive 獨立出來成為一個網站,原因不明。雖然現在兩個網站各自運作,但實際上兩者都是 UVa Online Judge 的小組在維護的。

USACO Training Program Gateway

http://ace.delos.com/usacogate/

USACO = USA Computing Olympiad 美國資訊奧林匹克。這個網頁是美國訓練用來 IOI 選手的網頁,同時亦開放給大眾使用。(我不甚了解 IOI ,有待網友補充。)

這個網站非常有趣!首先註冊一個帳號,進入網站後,會看到一個任務表,完成前面的任務,才會開啟後面的任務──循序漸進,學習更精深的課題。有些任務是只是一些文字資料,講述方法或概念,只要讀完,就算是解決了任務。讀完資料後,接下來的任務,通常都是一連串程式設計的題目,正好學以致用。

有些困難的題目,都會貼心的附帶提示,讓使用者不至於無所適從。每當解決了一個問題之後,便可以觀看該題的解析、解法、解答,讓自己有檢討和進步的空間。這個網站可說是一個非常完整的教學網站!

Project Euler

http://projecteuler.net/

這個網站專門提供能用程式計算出答案的數學問題。每個問題都有固定一個答案,自己撰寫程式計算出解答後,只要在題目下方的表單中將答案輸入進去、上傳答案,就可以看到解題結果了。

TopCoder

http://www.topcoder.com/

這個網站是現下最流行的程式設計相關網站。網站功能眾多,其中有一項是程式設計比賽(跟本站較有關聯)。這個網站目前在台灣鮮為人知,還需要大力推廣。

其他相關網站

ACM ICPC TW Council

http://acm.nctu.edu.tw/

由交通大學主導的一個協會,旨在推動基礎程式設計之學習,提升大專生、高中生之程式解題能力,培育 ACM/ICPC 之選手。

ACMSolver

http://www.acmsolver.org/

這個網站專門收集程式設計比賽的人事物,以及世界上各個 OJ 的最新消息,面面俱到。另外也提供了簡單的演算法教學文章。

No comments: