|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/approximation-algorithms
课程评论：没有评论
课程名称：近似算法 课程概述：许多现实世界中的算法问题无法通过传统的算法工具有效解决，例如因为这些问题是NP难的。本课程的目标是熟悉处理这些问题所需的重要算法概念和技术。这些技术在我们不要求某些问题的最优解时尤为适用，而是要求一个接近最优解的近似解。我们将学习如何有效地寻找这样的近似解。 课程前置知识： 成功完成本课程，您需要具备一定的算法和数学基础。以下是您应该了解的内容： - O-符号、Ω-符号、Θ-符号；算法分析 - 基础微积分：求和、解决递归、对数运算等 - 基础概率论：事件、概率分布、随机变量、期望值等 - 基础数据结构：链表、栈、队列、堆 - （平衡）二叉搜索树 - 基础排序算法，如归并排序、插入排序、快速排序 - 图的术语、图的表示（邻接表和邻接矩阵）、基本图算法（广度优先搜索、深度优先搜索、拓扑排序、最短路径） 本课程的材料基于资源标签下的课程笔记。我们不会涵盖课程笔记中的所有内容。这些课程笔记供那些没有完全理解讲座的学生和希望深入学习的学生使用。 视频讲座中有一些非常小的错误。这些错误的列表可以在资源下的“勘误表”文档中找到。如果您认为发现了错误，请点击讲座或测验底部的方形标志以报告问题。 课程大纲： - 名称：近似算法简介 描述：在该模块中，我们将介绍学习近似算法的动机。我们将讨论什么是优化问题，启发式算法与近似算法之间的区别。最后，我们将介绍近似比的概念，该概念在评估近似算法的质量时起着核心作用。 - 名称：负载平衡问题 描述：在这个模块中，我们将研究负载平衡问题的各种近似算法。该问题要求将一组具有特定处理时间的作业分配给若干台机器。目标是让所有作业尽快完成。我们将使用上一篇讲座中提到的rho-近似概念分析所计算的解的质量。在此分析中，我们将看到最优解的下界在分析中起着至关重要的作用（或者对于最大化问题而言：上界）。 - 名称：线性规划松弛 描述：在本模块中，我们将介绍线性规划松弛技术以设计近似算法，并解释如何分析基于线性规划松弛的算法的近似比。我们将以（加权）顶点覆盖问题为例。在解释线性规划松弛技术之前，我们将首先为无权顶点覆盖问题提供一个简单的2-近似算法。 - 名称：多项式时间近似方案 描述：在本模块中，我们将介绍多项式时间近似方案（PTAS）的概念，这是一种可以无限接近最优解的算法。我们将描述设计PTAS的通用技术，并将其应用于著名的背包问题。最后，我们将看到如何分析使用该通用技术设计的PTAS。
Name:Introduction to Approximation algorithms
Description:In the module the motivation for studying approximation algorithms will be given. We will discuss what optimization problems are, and what the difference between heuristics and approximation algorithms is. Finally, we will introduce the concept of approximation ratio, which plays a central role in the analysis of the quality of approximation algorithms.
Name:The Load Balancing problem
Description:In this module we will study various approximation algorithms for the load balancing problem. This problems asks to distribute a given set of jobs, each with a certain processing time, over a number of machine. The goal is to do this such that all jobs are finished as soon as possible. We will analyze the quality of the computed solutions computed using the concept of rho-approximation, which we saw in the previous lecture. In this analysis we will see that lower bounds on the optimal solution play a crucial role in the analysis (or, for maximization problems: upper bounds).
Name:LP Relaxation
Description:In this module we will introduce the technique of LP relaxation to design approximation algorithms, and explain how to analyze the approximation ratio of an algorithm based in LP relaxation. We will do this using the (weighted) Vertex Cover problem as an example. Before we explain the technique of LP relaxation, however, we first give a simple 2-approximation algorithm for the unweighted Vertex Cover problem.
Name:Polynomial-time approximation schemes
Description:In this module we will introduce the concept of Polynomial-Time Approximation Scheme (PTAS), which are algorithms that can get arbitrarily close to an optimal solution. We describe a general technique to design PTASs, and apply it to the famous Knapsack problem. Finally we will see how to analyze PTASs that are designed with the general technique.
Many real-world algorithmic problems cannot be solved efficiently using traditional algorithmic tools, for example because the problems are NP-hard. The goal of this course is to become familiar with important algorithmic concepts and techniques needed to effectively deal with such problems. These techniques apply when we don't require the optimal solution to certain problems, but an approximation that is close to the optimal solution. We will see how to efficiently find such approximations. Prerequisites: In order to successfully take this course, you should already have a basic knowledge of algorithms and mathematics. Here's a short list of what you are supposed to know: - O-notation, Ω-notation, Θ-notation; how to analyze algorithms - Basic calculus: manipulating summations, solving recurrences, working with logarithms, etc. - Basic probability theory: events, probability distributions, random variables, expected values etc. - Basic data structures: linked lists, stacks, queues, heaps - (Balanced) binary search trees - Basic sorting algorithms, for example MergeSort, InsertionSort, QuickSort - Graph terminology, representations of graphs (adjacency lists and adjacency matrix), basic graph algorithms (BFS, DFS, topological sort, shortest paths) The material for this course is based on the course notes that can be found under the resources tab. We will not cover everything from the course notes. The course notes are there both for students who did not fully understand the lectures as well as for students who would like to dive deeper into the topics. The video lectures contain a few very minor mistakes. A list of these mistakes can be found under resources (in the document called "Errata"). If you think you found an error, report a problem by clicking the square flag at the bottom of the lecture or quiz where you found the error.
