第一講認(rèn)識(shí)acmppt課件(編輯修改稿)
2025-03-20 15:48 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ?Combination 組合數(shù)學(xué) ?Search Techniques 搜索技術(shù) ?Dynamic Programming 動(dòng)態(tài)規(guī)劃 ?Graph Theory 圖論 ?Simulation 模擬題 ?String Management 字符串處理 ?Matching 匹配 ?Other ? ACM程序設(shè)計(jì)大賽 16 相關(guān)的知識(shí) ? ACM程序設(shè)計(jì)大賽 17 ACM需要哪些數(shù)學(xué)知識(shí) 離散數(shù)學(xué) 作為計(jì)算機(jī)學(xué)科的基礎(chǔ)，離散數(shù)學(xué)是競(jìng)賽中涉及最多的數(shù)學(xué)分支，其重中之重又在于圖論和組合數(shù)學(xué)，尤其是圖論。 圖論之所以運(yùn)用最多是因?yàn)樗淖兓疃?，而且可以輕易地結(jié)合基本數(shù)據(jù)結(jié)構(gòu)和許多算法的基本思想，較多用到的知識(shí)包括連通性判斷、 DFS和 BFS，關(guān)節(jié)點(diǎn)和關(guān)鍵路徑、歐拉回路、最小生成樹(shù)、最短路徑、差分約束、二部圖匹配和網(wǎng)絡(luò)流等等。這部分的比重很大 ，往往也是競(jìng)賽中的難題所在。競(jìng)賽中設(shè)計(jì)的組合計(jì)數(shù)問(wèn)題大都需要用組合數(shù)學(xué)來(lái)解決，組合數(shù)學(xué)中的知識(shí)相比于圖論要簡(jiǎn)單一些，但有一部分知識(shí)要先對(duì)代數(shù)結(jié)構(gòu)中的群論有初步了解才能進(jìn)行學(xué)習(xí)。 ? ACM程序設(shè)計(jì)大賽 18 數(shù)論 以素?cái)?shù)判斷和同余為模型構(gòu)造出來(lái)的題目往往需要較多的數(shù)論知識(shí)來(lái)解決，這部分在競(jìng)賽中的比重并不大，但難度很高。素?cái)?shù)判斷和同余最常見(jiàn)的是在以密碼學(xué)為背景的題目中出現(xiàn)，在運(yùn)用密碼學(xué)常識(shí)確定解答過(guò)程之后，核心算法往往要涉及數(shù)論的內(nèi)容。 計(jì)算幾何 計(jì)算幾何相比于其它部分來(lái)說(shuō)是比較獨(dú)立的，就是說(shuō)它和其它的知識(shí)點(diǎn)很少有過(guò)多的結(jié)合，較常用到的部分包括 ——線(xiàn)段相交的判斷、多邊形面積的計(jì)算、內(nèi)點(diǎn)外點(diǎn)的判斷、凸包等等。 線(xiàn)性代數(shù)、概率論 、高等數(shù)學(xué) ? ACM程序設(shè)計(jì)大賽 19 最常見(jiàn)題型 Dynamic Programming(動(dòng)態(tài)規(guī)劃 ) Greedy(貪心 ) Complete Search(窮舉 ) Flood Fill (種子填充 ) Shortest Path (最短路徑 ) Recursive Search Techniques (回溯）
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1