---
# System prepended metadata

title: IOI學習大綱

---

# 數學
## 算術和幾何
- [x] 整數、運算（包括求冪）、比較
- [x] 整數的基本性質（符號、奇偶性、整除性）
- [x] 基本模運算：加法、減法、乘法
- [x] 質數
- [x] 分數、百分比
- [x] 直線、線段、角度、三角形、長方形、正方形、圓形
- [x] 平面內的點、向量、座標
- [ ] 多邊形（頂點、邊、凹多邊形、凸多邊形、內部、面積）
- [ ] 歐幾裡得距離
- [ ] 勾股定理
## 離散結構（DS）
### DS1。函數、關係和集合
- [ ] 函數（射射、射射、逆函數、合成）
- [ ] 關係（自反性、對稱性、傳遞性、等價關係、總/線性順序關係、字典順序）
- [ ] 集（包含/排除、補集、笛卡兒積、冪集）
### DS2。基本邏輯
- [ ] 一階邏輯
- [ ] 邏輯連接詞（包括其基本屬性）
- [ ] 真值表
- [ ] 通用和存在量化（注意：語句應盡可能避免使用嵌套量詞的定義。）
- [ ] 設定模式和刪除模式
- [ ] 範式
### DS3。證明技術
- [ ] 蘊含、逆向、逆向、反證、否定和矛盾的概念
- [ ] 直接證明，證明方式：反例、對立、矛盾
- [ ] 數學歸納法
- [ ] 強感應（又稱完全感應）
- [ ] 遞歸數學定義（包括相互遞歸定義
### DS4。計數基礎知識
- [ ] 計算參數（求和與乘積規則、算術和幾何級數、斐波那契數）
- [ ] 排列組合（基本定義）
- [ ] 階乘函數、二項式係數
- [ ] 包含排除原則
- [ ] 鴿巢原理
- [ ] 帕斯卡恆等式、二項式定理
### DS5。圖和樹
- [ ] 無向圖（頂點/節點、邊、度、鄰接、頂點和邊標籤）
- [ ] 有向圖（入度、出度）
- [ ] 多重圖、具有自循環的圖
- [ ] 圖中的路徑（無向和有向路徑、循環、遊覽、步行；歐拉遊覽；哈密頓路徑/循環）
- [ ] 可達性（連接組件、最短距離）
- [ ] 樹木（葉、直徑、中心、質心、森林）
- [ ] 有根樹（根、父樹、子樹、祖先、子樹）
- [ ] 生成樹（子圖）
- [ ] 遍歷策略
- [ ] 第二部圖
- [ ] 有向無環圖
- [ ] 平面圖
- [ ] 圖的基本組合屬性9 
### DS6。離散機率
- [ ]  一切都是有限的應用（因此關於機率的論證可以很容易地變成組合論證），更複雜的是✗。
# 資訊工程
## 程式設計基礎知識（PF）
### PF1。基本程式結構（針對抽象機）
- [x] 高級語言的基本語法和語義（至少一種 IOI 上可用的特定語言，如比賽規則對於那個 IOI）
- [ ] 變數、型別、表達式和賦值
- [ ] 簡單的輸入/輸出
- [ ] 條件和迭代控制結構
- [ ] 函數和參數傳遞
- [ ] 結構化分解
### PF2。演算法和問題解決
- [ ] 解決問題的策略（理解-計劃-執行-檢查、關注點分離、概括、專業化、案例區分、逆向工作等）
- [ ] 演算法在問題解決過程中的作用
- [ ] 演算法的實現策略（另見§7SE1)
- [ ] 調試策略（另見§7SE3)
- [ ] 演算法的概念和性質（正確性、效率）
### PF3。基本資料結構
- [ ] 基本型別（布林值、有符號/無符號整數、字元）
- [ ] 數組（包括多列維數組）
- [ ] 字串和字串處理
- [ ] 靜態和堆疊分配（基本自動記憶體管理）
- [ ] 連結結構
- [ ] 圖和樹的實現策略
- [ ] 選擇正確資料結構的策略
- [ ] 實數在數值穩定任務中的基本應用
- [ ] 實數的浮點表示，存在精度問題。
- [ ] 指針和參考
- [ ] 記憶體中的資料表示，
- [ ] 堆分配，
- [ ] 運行時儲存管理，
- [ ] 使用分數進行精確計算。
### PF4。遞迴
- [ ] 遞歸的概念
- [ ] 遞迴數學函數
- [ ] 簡單的遞歸過程（包括相互遞歸）
- [ ] 分而治之的策略
- [ ] 遞迴的實現
- [ ] 遞迴回溯
### PF5。事件驅動程式設計
一些競賽任務可能涉及與反應性環境的對話。與所提供的環境實現這樣的互動是✓q。
與反應式任務的實施不直接相關的所有內容都是？。
## 演算法和複雜性（AL）
### AL1。基礎演算法分析
- [ ] 演算法規格、前置條件、後置條件、正確性、不變量
- [ ] 複雜性上限的漸近分析（如果可能的話，非正式的）
- [ ] 大O表示法
- [ ] 標準複雜度類別：常數、對數、線性、氧（n紀錄n)、二次、三次、指數等。
- [ ] 演算法中的時間和空間權衡
- [ ] 經驗性能測量。
- [ ] 識別最佳、平均和最壞情況行為之間的差異，
- [ ] 小 o、Omega 和 Theta 表示法，
- [ ] 調整參數以減少運行時間、記憶體消耗或其他效能指標
### AL2。演算法策略
- [ ] 簡單的循環設計策略
- [ ] 暴力演算法（窮舉搜尋）
- [ ] 貪心演算法
- [ ] 分而治之
- [ ] 回溯（遞歸和非遞歸）、分支定界
- [ ] 動態規劃13 
- [ ] 啟發式
- [ ] 尋找機器學習任務的良好特徵14 
- [ ] 離散逼近演算法
- [ ] 隨機演算法。
### AL3a。演算法
- [ ] 涉及整數的簡單演算法：基數轉換、EuCLID 演算法，素性測試氧（√n) 試除法、埃拉托斯特尼篩法、因式分解（經試除法或篩選法）、高效求冪
- [ ] 任意精確度整數的簡單運算（加法、減法、簡單乘法）15 
- [ ] 簡單的陣列操作（填充、移位、旋轉、反轉、調整大小、最小/最大、前綴和、直方圖、桶排序）
- [ ] 簡單的字串演算法（例如，簡單的子字串搜尋）
- [ ] 順序處理/搜尋和二分搜索
- [ ] 快速排序和快速選擇來查找k-第一個最小的元素。
- [ ] 氧（n紀錄n）最壞情況排序演算法（堆排序、合併排序）
- [ ] 有序樹的遍歷（前序、中序和後序）
- [ ] 深度優先和廣度優先遍歷
- [ ] 深度優先遍歷樹的應用，例如拓樸邏輯排序和歐拉路徑/循環
- [ ] 尋找連通組件和傳遞閉包。
- [ ] 最短路徑演算法（Dijkstra、Bellman-Ford、Floyd Warshall）
- [ ] 最小生成樹（Jarn´ık-Prim 和 Kruskal 演算法）
- [ ] 氧（維E）計算最大二分匹配的時間演算法。
- [ ] 無向圖中的雙連通性（橋、連接點）。
- [ ] 有向圖中的連通性（強連通分量）。
- [ ] 組合博弈論基礎知識、獲勝與失敗位置、最佳遊戲的極小極大演算法
### AL3b。資料結構
- [ ] 堆疊和佇列
- [ ] 圖的表示（鄰接表、鄰接矩陣）
- [ ] 二元堆資料結構
- [ ] 不相交集的表示：並查資料結構。
- [ ] 靜態平衡二元搜尋樹。這種情況的實例包括二元索引樹（也稱為 Fenwick 樹）和線段樹（也稱為區間樹和錦標賽樹）。
- [ ] 平衡二元搜尋樹 
- [ ] 增強二元搜尋樹
- [ ] 氧(紀錄n）用於回答靜態根樹中最低常見的 cestor 查詢的時間演算法。
- [ ] 靜態樹的分解（重光分解、質心分解等分離器結構）
- [ ] 透過路徑複製建立持久性資料結構。
- [ ] 資料結構的嵌套，例如具有集合序列。
- [ ] 嘗試
### AL4。分散式演算法
- [ ] 整個部分是 ? 。
### AL5。基本可計算性
所有與可計算性相關的主題都是✗。這包括以下內容： 易於處理和棘手的問題；不可計算的函數；停機問題；不可計算性的影響。
但是，請參閱 AL7 以了解基本計算模型。 
### AL6。複雜度等級 P 和 NP
與非確定性、NP 難度證明（約簡）相關的主題，以及所有相關的內容✗。
請注意，本節僅涵蓋本科生和研究生課程中通常包含的關於形式語言和計算複雜性的結果。這些主題的分類為✗並不意味著 NP 難問題不能出現在 IOI 處。
### AL7。自動機和語法
- [ ] 理解巴科斯-諾爾形式的簡單文法
- [ ] 有限狀態機的正式定義與屬性，
- [ ] 上下文無關語法和相關重寫系統，
- [ ] 常用表達
### AL8。先進的演算法分析
- [ ] 攤銷分析。
- [ ] 線上演算法
- [ ] 隨機演算法
### AL9。密碼演算法
整個部分是？。
### AL10。幾何演算法
- [ ] 表示點、向量、直線、線段。
- [ ] 檢查共線點、平行/正交向量和順時針旋轉（例如，透過使用點積和叉積）。
- [ ] 兩條線的交點。
- [ ] 根據多邊形頂點的座標計算多邊形的面積。19 
- [ ] 檢查（一般/凸）多邊形是否包含點。
- [ ] 座標壓縮。
- [ ] 氧（n紀錄n) 凸包的時間演算法
- [ ] 掃線法
### AL11。平行演算法
整個部分是？。
## 計算機科學的其他領域
除 GV（如下指定）外，所有區域均✗。
AR。架構和組織
作業系統.作業系統
數控。以網路為中心的運算（又稱雲端運算）PL。程式設計語言
HC。人機交互
GV。圖形和視覺計算
處理圖形資料的基本面是？，其他一切（包括OpenGL等圖形庫的使用）都是✗。
是。智慧系統
我是。資訊管理
SP。社會和專業問題
CN.計算科學
# 軟體工程（SE）
在 IOI 競賽中，軟體工程的應用涉及在時間壓力下對小型、一次性、單一開發人員專案使用輕量級技術。所有包含的主題都是✓p。
### SE1。軟體設計
- [ ] - [ ] 基本設計概念與原則
- [ ] - [ ] 設計模式
- [ ] - [ ] 結構化設計
特別是，參賽者可能會被期望
– 將抽象演算法轉換為以允許的程式語言之一表達的具體、高效的程序，可能使用標準或特定於競賽的庫。
– 讓他們的程式按照規定的簡單格式從文字檔案讀取資料並向其中寫入數據
### SE2。使用API
- [ ] API（應用程式介面）程式設計 特別是，參賽者可能需要
– 依照提供的規格使用競賽專用函式庫。
### SE3。軟體工具和環境
- [ ] 程式設計環境，包括IDE（整合開發環境）
特別是，參賽者可能會被期望
– 使用提供的程式編輯器之一編寫和編輯程式文字。
– 編譯並執行自己的程式。
– 調試自己的程式。
### SE4。軟體流程
- [ ] 軟體生命週期和流程模型
特別是，參賽者可能會被期望
– 了解解決方案開發過程的各個階段並選擇適當的方法。
### SE5。軟體要求和規範
- [ ] 功能性和非功能性需求
- [ ] 形式化規範技術的基本概念
特別是，參賽者可能會被期望
– 將精確的自然語言描述（有或沒有數學形式主義）轉化為計算模型方面的問題，包括對效率要求的理解。
### SE6。軟體驗證
- [ ] 測試基礎知識，包括測試計劃創建和測試用例生成
- [ ] 黑盒和白盒測試技術
- [ ] 單元、整合、驗證和系統測試
- [ ] 檢查
特別是，參賽者可能會被期望
– 應用能夠最大限度地提高發現常見錯誤的機會的技術（例如，透過結構良好的程式碼、程式碼審查、內建測試、測試執行）。
– 測試他們自己的程式（部分）。
### SE8。軟體專案管理
- [ ] 專案調度（尤其是時間管理）
- [ ] 風險分析
- [ ] 軟體組態管理
特別是，參賽者可能會被期望
– 管理花在各種活動的時間。
– 在選擇替代方法時權衡風險。 
– 在開發解決方案時追蹤各種版本及其狀態。
### SE10。形式化方法
- [ ] 形式方法概念（正確性證明的概念，變體）
- [ ] 前後斷言
特別是，參賽者可能會被期望
– 推理演算法和程式的正確性和效率。
# 電腦知識
本節的正文是✓p。
參賽者應了解並了解電腦的基本結構和操作（CPU、記憶體、I/O）。他們期望能夠使用具有圖形使用者介面的標準電腦、具有支援應用程式的作業系統以及提供的程式開發工具來解決競賽任務。特別是，一些文件管理技能（建立資料夾、複製和移動文件）很有幫助。
這些設施的詳情將在比賽規則特定 IOI 的值。通常，某些服務可透過標準 Web 瀏覽器取得。可能會提供一些特定於競賽的工具，並附有單獨的文檔。
通常情況下，會提供許多等效的工具。參賽者不需要了解所有這些工具的所有功能。他們可以根據自己認為最適合的方式做出自己的選擇。
以下主題全部？：計算器、文字處理器、電子表格應用程式、資料庫管理系統、電子郵件用戶端、圖形工具（繪圖、繪畫）。



