Try   HackMD

課程資訊

(2024/3/4更新)

前言

大家好，這是中央大學數學系MCL辦的課程，目的是讓數學系的同學在資訊能力有所提升，而目前最有公信力的不外乎就是CPE了，也成了許多大學資工系的畢業門檻，以及碩士班入學招生參考標準之一，考試主要以資料結構、演算法為主。

檢定不像是一般學科，儘管都是做題目，但仍然有著與其他學科的差別在。其最明顯的差異就是 ── 即時回饋! 立刻送出程式，立刻回傳裁判結果，在比賽結束後通常也能立即得知自己的狀況。

最公平的是，不存在「評審的看法」，測試資料都是事先就完成的，除非測資本身出錯，不然在大家都用同樣測資的情況下，絕對不會出現因為哪個評審覺得如何就特別高分的情況!

當然除了 CPE檢定 以外，也歡迎大家參加大大小小的比賽，像是NCPC，TOPC，ICPC。

課程 Discord

對了對了，趕快加入discord吧~大家一起討論一起進步!!希望中央數學的程式越來越強!!
還在等什麼? 快繼續往下看吧

CPE是什麼

介紹

大學程式能力檢定 (Collegiate Programming Examination, 簡稱CPE)旨在提升大專學生與相關人員的程式設計能力，由考生透過線上程式設計，利用電腦自動評判，以檢測程式設計能力。

CPE 的目標是做為全台灣「程式能力檢定」的標準，有如英文的多益或全民英檢。CPE希望藉由考試檢定的手段，提升全台灣學生的程式設計能力。有些大學已將 CPE 成績採計為碩士班入學招生參考標準之一；有些大學採計 CPE 成績為大學部學生畢業門檻。

源起

ICPC (International Collegiate Programming Contest，國際大學程式競賽，原名 ACM ICPC) 自從 1970 年代開創以來，經過四十多年的發展，已經成為全球電腦界中歷史最悠久且最具影響力的程式競賽。以 2021-2022 年為例，參加各地區域賽的隊伍超過一萬隊，涵蓋 111 個國家以及超過 2500 個大學。程式競賽(各地區域賽、世界總決賽)之後，歷次的比賽題目全部收錄於 Online judge 網站(2020 以前稱為 UVA Online judge)，目前累積超過 4500 題，成為各國學生提升程式能力的練習網站。

特色

  • 各大學資訊相關學系畢業檢定。CPE 成績已被採計或可抵免為學士班畢業門檻之學校如下：
    中山大學、中正大學、中央大學、元智大學、台北大學、台北市立大學、陽明交通大學、金門大學、東華大學、虎尾科技大學、屏東大學、逢甲大學…等

  • 研究所入學考參考標準。已將 CPE 成績採計為碩士班入學招生參考標準之一的學校如下：
    中山大學、中正大學、中央大學、中興大學、台中教育大學、台北大學、交通大學、清華大學、高雄大學、高雄科技大學、雲林科技大學

  • 廠商徵才。

  • 提升個人程式設計能力。

  • ICPC名額

例子: 醫學系資訊組招生簡介

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

考試方式

正式考試時間 3 小時。以 ACM-ICPC 評分方式進行排名，有客觀的成績排序，有助於考生瞭解自己程式設計的能力。本檢定每年辦理四次。

  1. 試題以英文命題，總共7題。
  2. 題目採用 ICPC(International Collegiate Programming Contest)題型格式，輸入與輸出資料全為純文字資料，每套輸入資料可能包含多組測試資料。程式必需讀取測試資料，並依規定，將結果輸出。
  3. 題目可能取自 UVA online judge 題目庫或類似題目。
  4. 考生所設計之程式由電腦自動評判其正確性。

ACM-ICPC 評分規則與排名規則：凡送繳評判的答案，將會有「通過」、「不通過」兩種結果。考生以答對的題數作為評定名次的主要依據；答對題數相同者，以答對題數所耗費時間之總和，作為排名次的依據。答對題目耗費的時間總和，是指考試開始至送繳答案所經過的時間，以分鐘為單位，再加上該題送繳後但被評判為錯誤的次數乘以 20 分鐘。答錯的題目所耗費之時間不計。

最近考試時間 2024 (暫)

2024/03/26 CPE
2024/03/12 (二) 14:25 報名開始
2024/03/22 (五) 18:00 報名截止

目標考試時間

2024/5/21 (考試)

PS：CPE很難報名，網站會卡爛

報名費免費

大專學生考試免費。申請成績單100元

考試內容

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

排行

總共7題

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

規劃

演算法？

演算法是非常重要的，它無處不在，像是我們常常聽到的FB演算法，YT演算法，甚至演算法的研究是計算機科學的核心，而今天的課程所教的演算法，都是最基礎中的基礎，很多學問都建立在這之上，像是密碼學，AI，目前很夯的chatgpt等等。

演算法可以視為資訊科技、電腦科學的發展基礎，廣義來說，如果沒有演算法就不會有所謂的『程式』，程式的運行基礎就是建立在各式各樣不同的演算法上。學習演算法可以幫助了解到在不同的情境下，有一些基礎且標準的演算法可以用來解決難題，甚至可以自己設計出新的演算法並分析這個新演算法的執行效率來進行調整與優化。

David Harel：「演算法學不只是電腦科學其中的一個分支，更是電腦科學的核心觀念，甚至可應用到其他科學、科技與商業行為上」因此演算法除了應用在電腦科學領域之外，還可以在其他領域中實現演算法的一些概念，進而解決問題與困境，所以演算法一直都存在於我們的生活中，只是平常不會意識到罷了。

而演算法的重要性在於運算的速度，在目標資料的數量不龐大的情況下，演算法看似可有可無，可是只要數量來到上萬筆，那這運算速度的問題就會凸顯出來了；如同一開始只是拿一把斧頭去砍樹枝，還算應付的來，速度可能也還能接受，但如果還是只拿一把斧頭去砍樹?，樹還是可以被砍斷，只是所花費的時間會大幅增加。或許在開發小系統或小專案中不太會去思考運算速度的問題，可是對於一些大型系統而言，其運算速度可能攸關公司的運作，例如電商的搜尋引擎，假設你輸入關鍵字要找某一類的產品，結果網頁一直在轉圈圈，估計你下一個動作就是把網頁關掉，然後去用其他的電商平台了?

因此，學演算法的目的是在有限的步驟內精準地解決問題，而透過了解演算法的步驟，試著進一步對演算法或程式進行優化，來達到最佳的執行效率。

教學大綱

對象：數學系學生，為免費課程
授課內容：C++、演算法 (資料結構、排序搜尋、貪婪、分治、DP)
目的：提升數學系程式能力，取得 CPE 檢定成績，有利於升學與工作
時間：每週四 晚上 7:00 ~ 10:00 (第一次上課時間 3/7)
地點：數學系 MCL 電腦教室(201-3)
助教：馬沅辰、鐘仕翔
獎金：每年以 CPE 成績進行排行

期中期末大比拚

期中期末的時候會舉行小比賽，當然也會有獎勵，敬請期待XDD

獎勵辦法

排行榜獎勵辦法

規則:

  • 須數學系本系學生
  • 可以使用 C++, Python兩種程式語言
  • 按照解出的等地，在按照排名百分比排序
  • 第一，二名須達到A等級以上 (4~5題)
  • 第三名須達到 A-等級以上 (3題)
  • 若達不到得以從缺

(2024)時間: CPE (3/26) (5/21) (11/?)

成績取最好的那一次

第一名: 10,000 (需
A級以上 4~5題)

第二名: 8,000 (需
A級以上 4~5題)

第三名: 7,000 (需
A−級以上 3題)

課程須知

online Judge

檢定要如何練習呢?最直接的方法就是上網找線上的評審系統 (Online Judge)，最近 judge興起，網路上已經囤積了無數道題目可供練習了。

較常用的有：

  • codeforce(全英文)：
    codeforces很大的特點就是題目很多，什麼難度等級的題目都可以找到。並且題目很有意思，思維題很多。對於資料結構以及演算法的考察相對弱一些，更多的時候往往是告訴你用什麼演算法你也不知道怎麼做……
    codeforces另外一個很大的特點就是它有自己的上分系統，基本上每週會舉辦一到兩次線上的演算法比賽。一般的比賽時長是兩個小時，只要註冊賬號就可以免費參加。由於參加的選手水平實力強度不一，所以它開設了好幾個檔次(div)，不同層次的選手面對的題目難度也不一樣，這樣保證了大家都可以愉快地參賽。
    (備註)：NCPC那些是用codeforce去報名的!!

  • leetcode(全英文)：
    這個很少會拿來這裡用，但是在面試的時候很多人會拿去刷，理由是它不採用IO，只需要寫solve並回傳一個值，其他地方都不需要改。不過競賽以及檢定都是需要IO的，所以在這裡比較不適用。

  • CSES(全英文)：
    這裡的題目比較簡單，適合剛入門的新手，測資公開透明，很方面debug，包括各類超級經典的題目，題目很優質，建議刷完，題目很少，只有大概 300 題。

  • Zerojudge高中生解題網(中文)：
    雖然叫做高中生解題網，但裡面的題目有高達快3千題，大賽的題目或是檢定的題目都會被放進來，優點是中文很容易理解，題目適中，缺點是沒有做好分類，題目品質參差不齊，很多水題。

還有很多很多的judge，像是UVA(最老的online judge)。這裡就不一一列舉了。

上課會用自己架設的online judge

https://ncuma-oj.math.ncu.edu.tw/

編輯器

雖然可以用VScode之類的，不過有點麻煩。
線上有一款非常方便的編譯器，所以建議用這個，考試也是類似長這樣 不需要自己 compile。
online c++ compiler - online editor

題目長怎樣，要怎麼寫？

這邊拿CSES的題目舉個例子，讓大家比較好了解這之間的運作過程

首先會看到一個題目會有敘述->輸入->輸出->係數大小->範例輸入->範例輸出。在其他小地方會有時間限制，跟記憶體限制。時間限制以及係數大小就是讓你了解演算法大概要寫多好才會過，記憶體限制通常不用理它，因為很難會爆…(除非你亂開陣列)

舉例

題目要求輸入一個數字，並且遵循以下敘述直到數字變成1，如果數字為奇數就乘3加1，偶數就除以2。

看到

1<=n<=106，程式來說1秒差不多可執行
108 ~
109，之後會在提到時間複雜度來去判斷怎麼寫才會好，但這邊的敘述很簡單所以就照寫就好。

此時就可以打開online compiler，清空上面的敘述快樂的打程式了

在按下download code

到submit的地方繳交剛剛的程式碼，選擇c++

出現以下的訊息就是結果正確啦~

常見judge結果

如果還有任何問題可以詢問，或者直接到 DC 問問題

演算法競賽宣傳

課程資訊

如果對於基本演算法，也就是上述課程提到的那些，還有另外圖論的基礎都很熟悉的話，歡迎參加中央NCU競程開的課程，會教更深入的演算法

https://www.facebook.com/groups/418934332075523

也可以一起打比賽(3人一組)，很有趣的!!

比賽資訊

通常不可跨校，多數比賽三人一組
從大一到碩一(修課未滿九學期)都可參加
題目都英文敘述
語言C/C++,java,有些有python,TOPC、ICPC有kotlin
通常比賽可以帶20 or 25 頁的codebook(程式模板)

北區程式設計競賽

  • 資格：大學生(初階組：大一，進階組：大二以上)
  • 時間：5-6月
  • 地點：台北商業大學
  • 獎項：兩組各前三名、佳作數名

NCPC 初賽

  • 地點：北部台師大 南部中山(去年因為疫情改線上各校自己開場地)
  • 規格：至少4題(似乎都6-7題左右)，3小時
  • 主要在9~10月

NCPC 決賽

  • 資格：初賽至少AC一題且每校最多六隊(初賽校內前六)
  • 地點：北部台師大 南部中山
  • 時間：通常為初賽後兩周，約為十月初
  • 規格：9~15題，五小時
  • 參加贈品：資料夾
  • 獎項：第一名一隊，第二名兩隊，第三名三隊，佳作取約30~40隊
  • 備註：點心很好吃

TOPC

ICPC Asia Taiwan Online Programming Contest

  • ICPC前導賽，為線上賽
  • 資格不限，有報名就可以參加
  • 時間：八月底~十月初之間
  • 規格：3小時，至少七題

ICPC

國際大學生程式設計競賽
分為regional跟world final
台灣區可以打全部太平洋賽區的regional如果有錢出國的話XDD

taiwan ICPC regional

比賽有兩天，第一天開幕、測機，第二天比賽、頒獎、晚宴

台灣最高規格的比賽

  • 時間：11月多
  • 地點：連三年北商(2019-2021)，桃園龍潭 武漢國中(2022-2023)
  • 資格：
    • NCPC決賽取前40隊
    • TOPC取前40隊
    • NCTU，NCPU各取10隊
    • CPE錄取 10 隊，但每校不得超過兩隊。
    • TOPC 補滿
  • 費用：3000-4000(台灣大比賽中唯一需要費用的)
  • 規格：9~13題，五小時
  • 參加贈品：T-shirt跟包包
  • 獎項(獎項依主辦單位決定，至少2019-2021年是依照這個規則)：
    • 1~10 金牌
    • 11~30 銀牌
    • 31~60 銅牌
      (台清交加起來約30隊 能進銀牌線 代表有台清交實力)

ICPC world final

大學競賽程式最高殿堂

  • 時間：5,6月舉行
  • 資格：各regional賽區取前1 ~ 2名晉級
  • 獎項：前4金牌，5 ~ 8銀牌，9 ~ 12銅牌

各項檢定

CPE 大學程式能力檢定

  • 時間：每學期兩次，學期初、末各一次
  • 費用：大學生、碩博士免費。
  • 題數：7題3小時
  • 檢定時間：晚上6:30

ITSA 程式能力線上自我評量

  • 時間：兩個月一次，1,3,5,7,9,11月
  • 題數：九題3小時
  • 檢定時間：晚上6:00

日常

帳號都會有rating，每場比賽之後會依照比賽表現調整帳號積分。可以當成lol的積分在打

codeforces ：

  • 3-4天有一場
  • 有牌位，可以看到自己的名稱顏色改變

leetcode ：

  • 每周日早上10:30
  • 隔周六晚上10:30
  • 一場 90 分鐘 四題
tags: 演算法
Last changed by 
 
河馬
大家好，我是河馬，很高興認識各位。
0
1643
Published on HackMD