GATE計算機科學與資訊科技考試大綱

---

---

科目程式碼：CS

課程結構

課程大綱

A節：工程數學

單元1：離散數學

• 命題邏輯和一階邏輯
  • 集合
  • 關係
  • 函式
  • 偏序
  • 格
• 群
• 圖 -
  • 連通性
  • 匹配
  • 著色
• 組合學 -
  • 計數
  • 遞推關係
  • 生成函式

單元2：線性代數

• 矩陣
• 行列式
• 線性方程組
• 特徵值和特徵向量
• LU分解

單元3：微積分

• 極限、連續性和可微性
• 最大值和最小值
• 中值定理
• 積分

單元4：機率論

• 隨機變數
• 均勻分佈、正態分佈、指數分佈、泊松分佈和二項分佈
• 均值、中位數、眾數和標準差
• 條件機率
• 貝葉斯定理

B節：數字邏輯

• 布林代數
• 組合電路和時序電路
• 最小化。數
• 表示和計算機算術（定點和浮點）

C節：計算機組成與結構

• 機器指令和定址方式
• 算術邏輯單元、資料通路和控制單元
• 指令流水線
• 儲存層次結構 -
  • 快取
  • 主存和輔助儲存器
  • I/O介面（中斷和DMA模式）

D節：程式設計與資料結構

• C語言程式設計

• 遞迴

• 陣列、堆疊、佇列、連結串列、樹、二叉搜尋樹、二叉堆、圖

E節：演算法

• 搜尋、排序、雜湊
• 漸近最壞情況時間和空間複雜度
• 演算法設計技術 -
  • 貪心演算法
  • 動態規劃
  • 分治法
• 圖搜尋、最小生成樹、最短路徑

F節：計算理論

• 正則表示式和有限自動機
• 上下文無關文法和下推自動機
• 正則語言和上下文無關語言，泵引理
• 圖靈機和不可判定性

G節：編譯器設計

• 詞法分析、語法分析、語法制導翻譯
• 執行時環境
• 中間程式碼生成

H節：作業系統

• 程序、執行緒、程序間通訊、併發和同步

• 死鎖

• CPU排程

• 記憶體管理和虛擬記憶體

• 檔案系統

I節：資料庫

• ER模型
• 關係模型 -
  • 關係代數
  • 元組演算
  • SQL
• 完整性約束，正規化
• 檔案組織，索引（例如，B樹和B+樹）
• 事務和併發控制

J節：計算機網路

• 分層概念
• 區域網技術（乙太網）
• 流控和差錯控制技術，交換
• IPv4/IPv6，路由器和路由演算法（距離向量，鏈路狀態）
• TCP/UDP和套接字，擁塞控制
• 應用層協議（DNS、SMTP、POP、FTP、HTTP）
• Wi-Fi基礎知識
• 網路安全 -
  • 身份驗證
  • 公鑰和私鑰加密基礎知識
  • 數字簽名和證書
  • 防火牆

下載pdf 點選此處。