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