算法设计与分析

随堂模式

  • 什么是随堂模式?

    随堂模式课程一般为每学期一轮次,课程每周更新,作业、考试有截止时间,由课程提供方老师、助教指导,课程完结,成绩由老师确认后,统一发放证书。

  • 什么是自主模式?

    自主模式课程常年开放加入,课件全部开放,作业、考试无截止时间,有学堂在线招募选拔的助教指导,考核通过即可自动获得证书。

来自于: 清华大学 | 分类: 计算机(666)数学(270)

课程描述

信息时代,算法为王,和我一起进入算法的世界。

什么是认证证书?
免费学习
认证学习
名师签名
实名认证
权威性
纸质证书
付费购买
免费赠送

课程简介

     本课程系统介绍算法设计与分析的方法和理论,包括算法基础、图、贪婪算法、分治、动态规划、网络流、计算复杂性初步、近似算法及随机算法等。同时,本课程还包含算法领域的一些前沿课题和最新进展。本课程可以作为数学、计算机等相关专业的研究生和高年级本科生关于算法理论的基础课程。

      算法设计与分析是计算机科学及运筹学的一门基础性课程,在清华大学数学系已经开设了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
课件00
课件01
2 Basics of Algorithm Analysis
问卷调查(学堂在线平台调研)
2.1 Computational Tractability
2.2 Asymptotic Order of Growth
2.3 A Survey of Common Running Times
Homework2
课件02
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
课件03
4 Greedy Algorithms
4.1 Coin Changing
4.2 Interval Scheduling
4.3 Interval Partitioning
4.4 Scheduling to Minimize Lateness
4.5 Optimal Caching
4.6 Shortest Paths in a Graph
4.7 Minimum Spanning Tree
4.8 Correctness of Algorithms
4.9 Clustering
Homework4
课件04
课件04MST
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
课件05
课件05FFT
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
课件06
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
课件07
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
课件08Intractability
课件08NPC
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
课件09
10 Local Search
10.1 Landscape of an Optimization Problem
10.2 Maximum Cut
10.3 Nash Equilibria
10.4 Price of Stability
Homework10
课件10
11 Randomized Algorithms
11.1 Contention Resolution
11.2 Linearity of Expectation
11.3 MAX 3-SAT
11.4 Chernoff Bounds
Homework11
课件11
Exam
Exam

授课教师

  • 王振波 清华大学 数学科学系 副教授

    王振波,清华大学数学科学系副教授,2006年在清华大学数学科学系获得博士学位,留校任教。主要研究方向为算法设计与分析。曾获清华大学优秀博士后,清华大学先进工作者,清华大学研究生精品课课程负责人,清华大学教学成果一等奖,北京青年优秀科技论文奖,中国运筹学会青年科技奖提名奖等。主持国家自然科学基金项目3项,发表论文30余篇。讲授《线性代数》、《数学实验》等本科课程,及《算法设计与分析》、《计算复杂性理论》、《网络优化》等研究生课程,深受学生喜爱,教学评估优秀。负责本课程的全面工作。

精华笔记

精华笔记正在评选中,去看看全部笔记

常见问题

目前还没有常见问题哟!