算法設計與分析

隨堂模式

  • 什么是隨堂模式?

    隨堂模式課程一般為每學期一輪次,課程每周更新,作業、考試有截止時間,由課程提供方老師、助教指導,課程完結,成績由老師確認后,統一發放證書。

  • 什么是自主模式?

    自主模式課程常年開放加入,課件全部開放,作業、考試無截止時間,有學堂在線招募選拔的助教指導,考核通過即可自動獲得證書。

來自于: 清華大學 | 分類: 計算機(654)數學(269)

課程描述

信息時代,算法為王,和我一起進入算法的世界。

什么是認證證書?
免費學習
認證學習
名師簽名
實名認證
權威性
紙質證書
付費購買
免費贈送

課程簡介

     本課程系統介紹算法設計與分析的方法和理論,包括算法基礎、圖、貪婪算法、分治、動態規劃、網絡流、計算復雜性初步、近似算法及隨機算法等。同時,本課程還包含算法領域的一些前沿課題和最新進展。本課程可以作為數學、計算機等相關專業的研究生和高年級本科生關于算法理論的基礎課程。

      算法設計與分析是計算機科學及運籌學的一門基礎性課程,在清華大學數學系已經開設了10幾年的時間,一般在秋季學期開設,4學分64課時,有來自數學系,計算機系,工業工程,經管學院及一些工科院系的研究生和高年級本課程選課,選課學生比較踴躍,課容量多次擴大,目前選課人數在50人以上。學生普遍反映課程內容精彩、有用、有趣。在算法廣泛應用和飛速發展的時代,學生通過對這門課程的學習,進入了算法領域,掌握其基本理論和方法,提升思維方式,為今后的學習、科研和工作打下堅實基礎。

展開

課程章節

1 Introduction of Algorithm
1.1 Introduction
1.2 A First Problem: Stable Matching
1.3 Gale-Shapley Algorithm
1.4 Understanding Gale-Shapley Algorithm
Homework1
2 Basics of Algorithm Analysis
2.1 Computational Tractability
2.2 Asymptotic Order of Growth
2.3 A Survey of Common Running Times
Homework2
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Traversal
3.3 Testing Bipartiteness
3.4 Connectivity in Directed Graphs
3.5 DAG and Topological Ordering
Homework3
4 Greedy Algorithms
4.1 Coin Changing
4.2 Interval Scheduling
4.3 Interval Partitioning
4.4 Scheduling to Minimize Lateness
4.5 Optimal Cashing
4.6 Shortest Paths in a Graph
4.7 Minimum Spanning Tree
4.8 Correctness of Algorithms
4.9 Clustering
Homework4
5 Divide and Conquer
5.1 Mergesort
5.2 Counting Inversions
5.3 Closest Pair of Points
5.4 Integer Multiplication
5.5 Matrix Multiplication
5.6 Convolution and FFT
5.7 FFT
5.8 Inverse DFT
Homework5
6 Dynamic Programming
6.1 Weighted Interval Scheduling
6.2 Segmented Least Squares
6.3 Knapsack Problem
6.4 RNA Secondary Structure
6.5 Sequence Alignment
6.6 Shortest Paths
Homework6
7 Network Flow
7.1 Flows and Cuts
7.2 Minimum Cut and Maximum Flow
7.3 Ford-Fulkerson Algorithm
7.4 Choosing Good Augmenting Paths
7.5 Bipartite Matching
Homework7
8 NP and Computational Intractability
8.1 Polynomial-Time Reductions
8.2 Basic Reduction Strategies I
8.3 Basic Reduction Strategies II
8.4 Definition of NP
8.5 Problems in NP
8.6 NP-Completeness
8.7 Sequencing Problems
8.8 Numerical Problems
8.9 co-NP and the Asymmetry of NP
Homework8
9 Approximation Algorithms
9.1 Load Balancing
9.2 Center Selection
9.3 The Pricing Method: Vertex Cover
9.4 LP Rounding: Vertex Cover
9.5 Knapsack Problem
Homework9
10 Local Search
10.1 Landscape of an Optimization Problem
10.2 Maximum Cut
10.3 Nash Equilibria
10.4 Price of Stability
Homework10
11 Randomized Algorithms
11.1 Contention Resolution
11.2 Linearity of Expectation
11.3 MAX 3-SAT
11.4 Chernoff Bounds
Homework11
Exam
Exam

授課教師

  • 王振波 清華大學 數學科學系 副教授

    王振波,清華大學數學科學系副教授,2006年在清華大學數學科學系獲得博士學位,留校任教。主要研究方向為算法設計與分析。曾獲清華大學優秀博士后,清華大學先進工作者,清華大學研究生精品課課程負責人,清華大學教學成果一等獎,北京青年優秀科技論文獎,中國運籌學會青年科技獎提名獎等。主持國家自然科學基金項目3項,發表論文30余篇。講授《線性代數》、《數學實驗》等本科課程,及《算法設計與分析》、《計算復雜性理論》、《網絡優化》等研究生課程,深受學生喜愛,教學評估優秀。負責本課程的全面工作。

精華筆記

精華筆記正在評選中,去看看全部筆記

常見問題

目前還沒有常見問題喲!

17500乐彩网排三走势