課程簡介
Course Introduction
教學大綱
Teaching Syllabus
《ACM程序設(shè)計》教學大綱
一、 課程基本信息
課程編號:
課程英文名稱:ACM programming
授課對象:計算機科學與技術(shù)專業(yè)
課程類型（指公共基礎(chǔ)課,、專業(yè)必修課,、專業(yè)選修課等）:專業(yè)選修課
建議學時:48
學分:3
與相關(guān)課程的銜接:數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學,、高級程序設(shè)計
考核方式:考查
二,、 教學目標和要求
《ACM程序設(shè)計》是專門培養(yǎng)ACM國際大學生程序設(shè)計競賽思想，課程詳細講解了ACM國際大學生程序設(shè)計競賽(ACM/ICPC)編程,、調(diào)試方法,，以及提高時間、空間性能的策略,。第1章講解了ACM程序設(shè)計入門知識,；第2章講解了字符串處理問題；第4章講解了簡單數(shù)學問題的處理,；第8章講解了高級數(shù)據(jù)結(jié)構(gòu)并查集,；第3,、5、6,、7章分別講解了常用的ACM程序設(shè)計基本編程技巧,，包括蠻力、貪心,、分治遞歸、動態(tài)規(guī)劃等,；配備了原版ACM競賽題的解題思路,、編程參**和英文題目中文翻譯。
通過本學科的教學,，使學生能掌握ACM競賽的基本知識,，掌握與了解計算機專業(yè)英語、高級數(shù)據(jù)結(jié)構(gòu),、離散數(shù)學,、初等數(shù)論、數(shù)值計算,、計算機算法,、人工智能、時空權(quán)衡,、圖算法,、計算幾何等等內(nèi)容。并能綜合運用這些知識,，利用程序語言進行ACM競賽題目的設(shè)計與編寫,。
三、 教學內(nèi)容,、教學方式與課時分配
（一）ACM程序設(shè)計概述
教學基本內(nèi)容:
1,、ACM競賽
2、GDCPC競賽
3,、藍橋杯大賽
4,、信息學奧賽
5、入門基礎(chǔ)與技巧
教學方式:多媒體教學,、講授演示,、討論啟發(fā)及課后OJ練習
（二）字符串處理
教學基本內(nèi)容:
1、字符串函數(shù)
2,、字符串操作
3,、字符串匹配
教學方式:多媒體教學、講授演示,、討論啟發(fā)及課后OJ練習
（三）蠻力法與簡單模擬
教學基本內(nèi)容:
1,、蠻力法的基本原理
2,、查找問題中的蠻力法
3、排序問題中的蠻力法
4,、圖論問題中的蠻力法
5,、簡單模擬問題
教學方式:多媒體教學、講授演示,、討論啟發(fā)及課后OJ練習
（四）簡單數(shù)學問題處理
教學基本內(nèi)容:
1,、數(shù)學模擬
2、數(shù)論
3,、幾何
4,、組合
教學方式:多媒體教學、講授演示,、討論啟發(fā)及課后OJ練習
（五）貪心算法
教學基本內(nèi)容:
1,、貪心法基本原理
2、背包問題
3,、圖論問題中的貪心法
教學方式:多媒體教學,、講授演示、討論啟發(fā)及課后OJ練習
（六）分治與遞歸法
教學基本內(nèi)容:
1,、分治基本思想
2,、遞歸基本思想
3、排序問題中的分治遞歸
4,、查找問題中的分治遞歸
教學方式:多媒體教學,、講授演示、討論啟發(fā)及課后OJ練習
（七）動態(tài)規(guī)劃法
教學基本內(nèi)容:
1,、動態(tài)規(guī)劃法的基本思想
2,、圖論問題中的動態(tài)規(guī)劃法
3、查找問題中的動態(tài)規(guī)劃法
教學方式:多媒體教學,、講授演示,、討論啟發(fā)及課后OJ練習
（八）并查集
教學基本內(nèi)容:
1、并查集基本原理
2,、并查集基本操作
3,、并查集的優(yōu)化
4、圖論問題中的并查集
教學方式:多媒體教學,、講授演示,、討論啟發(fā)及課后OJ練習
四、 實踐環(huán)節(jié)
按照人才培養(yǎng)計劃,，本課程在學時內(nèi)無實踐環(huán)節(jié),。但本課程實踐性較強，需要學生在課外OJ平臺進行在線練習,。
五,、 教材
吳濤,，張立敏，《ACM程序設(shè)計基礎(chǔ)講義》,，自編教材講義,，2014.12。
六,、 參考資料
（1）郭嵩山,，崔昊，吳漢榮,，陳明睿著,，《國際大學生程序設(shè)計競賽輔導(dǎo)教程》，北京大學出版社,，2001年12月第1版。
（2）俞經(jīng)善,，《ACM程序設(shè)計競賽基礎(chǔ)教程》,，清華大學出版社，2010年10月第1版,。
七,、 必要的說明
① 本課程選用教材為自編文字教材講義，是學生學習的主要用書,，它是教和學的主要依據(jù),。
② 為確保本課程教學活動正常有效地開展，保證課程的教學質(zhì)量,，組織由開設(shè)本課程的教師開展教研活動,，不斷提高教學質(zhì)量。布置課程的教學任務(wù),，研究落實課程實施方案,。
③ 本課程是一門實踐性較強、內(nèi)容有深度的綜合課程,，因此,，要求教師認真鉆研教學大綱，認真?zhèn)湔n,，仔細批改作業(yè)并對作業(yè)中存在的問題認真講解,。
④ 本課程由于學時所限，特別沒有設(shè)置實踐學時,，因此,，學生必須多做練習題來加深理解和掌握，從而達到消化,、掌握所學知識的目的,。
