|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
南京信息工程大學博士研究生招生入學考試
《算法設計與分析》考試大綱
科目代碼：2006
科目名稱：算法設計與分析
第一部分 課程評價目標
一、課程目標
算法設計與分析，主要使學生掌握算法設計的常用方法，提高學生算法
設計與復雜性分析的素質和能力，為學生能夠獨立進行算法的設計和計算復
雜性的分析奠定比較堅實的基礎，以便使學生在將來從事計算機領域或其它
有關領域的研究中，能夠運用這些方法來設計解決一些常用的或較為復雜的
實際問題的算法，并力爭做到快捷、有效，從而提高程序的質量并較好地解
決科學研究與實際應用中所遇到的問題。
二、基本要求
要求學生掌握計算機科學技術領域中的一些常用的、經典的算法設計技
術，學會分析算法、估計算法的時空復雜性，在非數值計算的層面上，具備
把實際問題抽象描述為數學模型的能力，同時能針對不同的問題對象設計有
效的算法，用典型的方法來解決科學研究及實際應用中所遇到的問題。并且
具備分析算法效率的能力，能夠科學地評估有關算法和處理方法的效率。
三、評價目標
1．掌握算法的基本概念和分析算法的基本方法；
2．掌握分治、動態規劃、貪心算法、分支限界法、圖的遍歷、隨機算法、
近似算法、NP 完全性問題的基本原理。
3．熟練掌握求解典型問題的算法設計思想和實現方法，能夠有效運用，以
能高效解決新的問題。
4．具有較強的算法設計和分析能力，具備設計出解決實際應用與科學研究
問題的有效算法。
5．了解算法研究領域的現狀與發展。
第二部分 考查要點
1．基本概念
算法的基本定義、基本性質，算法復雜度分析的基本方法。
2．遞歸算法設計技術
遞歸算法的實現機制，設計和分析遞歸算法的一般方法；歸納法等基本方法
的運用。
3．分治法
分治法的基本原理，典型問題如二分檢索、合并排序、快速排序、矩陣乘法、
大整數乘法、最近點對問題等的算法設計原理、實現技術及其應用。
4．貪心方法
圖和貪心方法的基本原理和性質，貪心解的最優性證明；典型問題如最短路
徑問題、最小耗費生成樹、文件壓縮等的算法設計原理、實現技術及其應用。
5．動態規劃
動態規劃的基本原理和方法、最優性原理、無后效性、狀態轉移方程；典型
問題如最長公共子序列問題、矩陣鏈相乘、所有點對的的最短路徑、背包問題等
的算法設計原理、實現技術及其應用。
6．圖的遍歷
廣度優先搜索、深度優先搜索的原理、性質和異同；回溯法的原理和技術、
分支－限界法的原理和技術；典型問題如 8 皇后問題、3 著色問題等的算法設計
原理、實現技術及其應用。
7．隨機算法和近似算法
隨機算法、近似算法的原理和方法；關于典型問題如 Las Vegas 方法、Monte
Carlo 方法、TSP 問題、裝箱問題、頂點覆蓋、子集和問題等問題的近似算法討
論。
8．NP 完全問題
NP 完全性的概念、可滿足性、NP 完全性證明；了解典型 NP 完全問題如頂點
覆蓋、獨立集、團集問題等。
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
