信息學

信息學

信息學是研究信息的獲取,處理,傳遞和利用的規律性的一門新興學科。

  • 中文名稱
    信息學
  • 又    名
  • 舊    稱
  • 類    型
    綜合性學科

綜述

信息學是研究信息的獲取,處理,傳遞和利用的規律性的一門新興學科。信息學(信息為研究對象,以電腦等技術為研究工具,擴展人類的信息功能為主要目標的一門綜合性學科。又稱信息科學,舊稱情報學(和製漢字)。主要是指利用電腦及其程式設計來分析問題、解決問題的學問。與圖書館學有密切的關系。

研究內容

信息學的主要內容包括信息加工學、信息資源管理學、信息安全學、信息傳播學及電腦科學等等。

技術發展

伴隨記憶和運算工具的飛速發展,特別是以電腦為代表的信息加工和運算設施,加速了人類掌握信息技術的發展。

信息化

任何組織機構,為了應對瞬息萬變的世界,必須建立信息系統和資源管理系統,以應對日益復雜的信息文明和短缺的資源。

套用

國際競爭和商業競爭的演化,直接演繹競爭情報的飛速發展,特別是軍事競爭情報。

學科競賽

競賽種類

信息學奧林匹克(Olympiad in Informatics)簡稱IOI是聯合國教科文組織支持的學科競賽之一。我國已經建立起一組相對完善的選拔機製,選手比賽成績優異全部獲得金牌。

ACM國際大學生程式設計競賽(英文全稱:ACM International Collegiate ProgrammingContest(ACM-ICPC或ICPC)是由美國電腦協會(ACM)主辦的,一項旨在展示大學生創新能力、團隊精神和在壓力下編寫程式、分析和解決問題能力的年度競賽。經過近30多年的發展,ACM國際大學生程式設計競賽已經發展成為最具影響力的大學生電腦競賽。

NOI(全國青少年信息學奧林匹克競賽)

NOIP(全國青少年信息學奧林匹克聯賽/分區聯賽)在每年十一月的第三個星期六舉行

WC(Winter Camp) 全國信息學冬立營。

CTSC(Chinese Team Selection Contest) IOI中國代表隊選拔賽 暨全國信息學精英賽

APIO(亞洲與太平洋地區信息學奧林匹克競賽(Asia-Pacific Informatics Olympiad)

POI(Polish Olympiad in Informatics) 波蘭高中信息學編程競賽,在世界上影響很大。

CEOI 中歐信息學競賽(Central European Olympiad in Informatics),中歐的高中信息學編程競賽,在世界上影響很大。

BOI 波羅的海國家信息學奧林匹克競賽

知識體系

數學離散數學集合論 關系 代數系統 數理邏輯 圖論

組合數學排列組合 母函式 群論 遞回與遞歸

數學規劃線性 動態 整數

高等數學向量 行列式與矩陣 微積分初步

概率統計

初等數論素數 整數理論 同餘與模線性方程

計算幾何

資料結構存儲結構線性表

(一級結構)靜態:數組 堆 佇列 廣義表 字元串

動態:指針 鏈表 動態數組

(二級結構)表示法(靜態、動態) 二叉樹 森林

(三級結構)表示法(矩陣、鄰接表、三元組)

特殊結構散列表(HASH表) 並查集 線段樹 尾碼樹 哈夫曼樹與哈夫曼編碼 地址表 Bit圖 捲動數組 棋盤圖 邊頂置換圖 二分點圖(網路流)

常用方法遍歷樹 圖 前/中/後序優先

轉化拓撲排序(三級結構轉一級結構) 最小生成樹 最小樹形圖(三級結構轉二級結構) 逆遍歷

壓縮路徑樹的線索化

壓縮存儲

查找線性直接 折半 Fab

樹形二叉查找樹 平衡二叉樹B+樹 B-樹 線索二叉樹索引表

排序插入排序直接排序、折半排序、2-路排序

交換排序冒泡排序 快速排序 歸並排序

堆排序

基數排序鏈式基數排序 桶排序

代碼素養代碼的編寫速度和準確性 誤碼率

演算法實現

演算法最佳化

調試 查錯 測試

習慣變數名 注解 縮進 模組化

基本演算法數學高精度計算(模擬計算)

表達式處理括弧 前/中/尾碼表達式 表達式樹

排列組合求值 嵌套控製

高斯消元法

篩選素數素數表

分數處理

基本操作實現大量資料賦值與移動Fillchar fillword move等函式

處理實數比較大小 高精度

字元串處理基本函式 KMP演算法

圖論

(顯示圖搜尋)路徑問題

(邊集)連通性測試傳遞閉包演算法 極大強連通子圖 最小點基

最短路問題標號法 第k小路 減半最短路Dijkstra演算法 floyd演算法bellman-ford演算法 Warshall演算法

特殊路徑歐拉路及回路 哈密爾頓路及回路

圖的中心和重心

生成樹Kruskal演算法 Prim演算法

(頂點集)覆蓋集

獨立集

支配集

割頂和塊

網路流容量有上下界的網路最大 / 小流

容量有上下界的網路最小費用最大 / 小流

頂容量網路最大流

供求約束可行流

二分圖匹配匈牙利演算法

關鍵路徑

搜尋

(隱式圖搜尋)深度優先搜尋

(回溯法)剪枝最佳化

預處理

記憶化搜尋

可變下界的深度優先搜尋

隨機化搜尋

廣度優先搜尋雙向廣搜 *多向廣搜

啓發式搜尋(A演算法)

分枝定界

多階段決策貪心演算法

動態規劃

其他構造法窮舉

模擬

信息學

相關詞條

相關搜尋

其它詞條