算法设计与分析复习

作者: zju_dream | 来源:发表于2019-01-08 23:05 被阅读0次

[toc]

题型

判断题，对了得分，错了倒扣
简答题
- 概念、什么是平衡二叉树、什么是有向连通图
- 给一个AVL树、SPlay，画出计算过程
- 给一个函数判断是不是递归、这个递归有没有什么问题
  - 是否少了边界条件或者递归条件
- P是不是NP的子集、你能解释是为什么吗？分别说出他们的概念
- 解释什么是Worse-case和平均情况、什么时候用WC什么时候用AC、AC和平均分摊之间有什么区别
- 排序算法的basic操作
- 给一个数据写一下最近邻
- 给一个图写出MST
- 红黑树的判断、构造一个红黑树（只要写过程、不用实现）
- splay tree 的时间复杂度

Lecture 1-2

P19.Optimizing and heuristic algorithms

最优解（优化算法）和启发式的区别、原因

相关知识点

有关optimization的三个定义
- optimization problem: can be described as the problem of finding the best solution from the set of all feasible solutions in some real or imagined scenario.
- optimization model: can be described as a mathematical representation of optimization problem. It consists of parameters, decision variables, objective function and constraints.
- optimization method: is an algorithm that is applied in order to solve an optimation problem.

最优解和启发式的区别

Optimizing and heuristic alogirithms
- There are two categories of algorithms for sloving optimization problems
  - Optimizing: Guarantees to find the optimal solution
  - Heuristic: Does not guarantee to find the optimal solution, but usually generates a "good" solution within a reasonable amount of time.
- Typically, heuristics can be stated as rules of thumb(经验法则) and they are often designed for a specific problem.

P20.Why heuristics?

为什么要选择启发式

得到最优解要消耗大量计算资源
- An optimizing algorithm might consume too much resources.
输入可能不是很准确，而启发式算法有较强的鲁棒性，能够找到一个不错的解
- Input to algorithm might be inaccurate and a heuristically good solution might be good enough.
启发式算法更容易理解
- For a non-expert, it might be easier to uderstand a heuristic rather than an optimizing algorithm.

P22.Constructive heuristics(建设性启发式)

均匀分布，在某个范围内等概率生成某些数
步骤、过程，step0-2、了解一下流程图

定义

A constructive heuristic is a method that iteratively "builds up" a solution.（迭代地构建解决方案）

怎么构建

Assuming that a solution consists of solution components, it starts with nothing and adds one value of exactly one variable(恰好一个变量的值) in each iteration.
详细描述
Let $x = (x_1, x_2, x_n)$ denote a solution to our problem
- 对应上面的Assuming a solution consists of solution components
step0: Initialization: Begin with all free solution $x^{(0)} = (-, ..., -)$ and set solution index t = 0
- 对应上面的start with nothing
step1: Termination criteria: If t = n, then break with approximate optimum (近似最优) $x = x^{(t)}$
- 对应下方的终止条件
setp2: Choose a solution component $x_p$ and a value for $x_p$ that plausibly(似真的) leads to a good feasible solution at termination.
Set $x^{(t+1)}$ = $x^{t}$ but with fixed variable $x_p$
Set solution index t = t+1, and go to step1
- 选择一个解决方案组件xp，并为xp选择一个值，该值似乎可以在终止时提供一个良好的可行解决方案。
- 对应于上面的adds one value of exactly one variable in each iteration

结束条件

The algorithm ends when all variables have been assigned a value.

用途

... are used to generate a feasible starting solution which can be improved by other algorithm later on.

P24.Greedy algorithm

构造启发式的一种自然且常见的类型是贪婪算法

A natural, and common type of constructive heuristics is greedy algorithms.
- Each variable fixings(变量固定值) is choosen as the variable that locally improve the objective most.
- Of course, variable fixings are choosen without breaking feasibility.

P26-.Huffman’s algorithm

哈夫曼编码、文字压缩
Huffman's algorithm - A greedy, constructive, algorithm for text compression.
Huffman's algorithm is a greedy algorithm that identifies the optimal code for a particular character set and text to code.(只需记住它是一种贪婪算法)

P29.Graph

图的定义

A graph is a set of objects that are connected to each other through links.

P31.Binary tree

什么是树

两种定义方式
- A tree is an undirected graph where each pair of vertices is connected by exactly one path.
- A tree connected with n vertices and n-1 edges.

什么是二叉树

A binary tree is a rooted tree in which no node has more than two children.

P35.Tries(prefix trees)

什么是Tries

Character codes can be represented using a special type of tree.
In a tries, each node is associated with a string and each edge is labeled with a sequence of characters.
The root is an empty node.
The value of a node is concatenating the value of its parent with the character sequence on the edge connecting it with the parent.

P36.Definition - Prefix

什么是前缀、后缀

A prefix can be described as a starting of a word.

举例：zhuyun的前缀
zhuyun
zhuyu
zhuy
zhu
zh
z

什么是前缀码

No character code is a prefix of another character code. This type of encoding is called prefix code.

给出字符串、能够写出前缀后缀、注意不止一个、是有一系列的前缀(上方的举例中有)

P42-.Huffmans’s algorithm

给一个例子，然后画出过程，构建huffman🎄

P43~P50中有例子

P58.Neighborhood search

用来求解背包问题(18年新题目)、把背包问题描述成数学的形式、自己写一遍算法、写出计算步骤

定义邻居
- 如果是在一维坐标轴上的实数
  - $N ( \overline { x } ) = \left\{ x \in \mathbb { R } ^ { 1 } : | x - \overline { x } | \leq 1 \right\}$
- 如果是二维坐标
  - $N ( \overline { x } , \overline { y } ) = \left\{ ( x , y ) \in \mathbb { R } ^ { 2 } : \sqrt { ( x - \overline { x } ) ^ { 2 } + ( x - \overline { y } ) ^ { 2 } } \leq 1 \right\}$
背包问题
- Parameters:
  - n: The number of items
  - l: {1, ..., n} Index set over the n items
  - $p_i$ : The value of item i
  - $w_i$ : The weight of item i
  - W: The weight capacity of the knapsack
- Decision variables:
  - $x _ { i } \in \{ 0,1 \}$
  - $x_i = 1$ if the item is chosen
  - $x_i = 0$ if the item is not chosen
- Objective function:
  - Maximize $\sum _ { i \in 1 } p _ { i } x _ { i }$
- Constraints:
  - $\sum _ { i \in l } w _ { i } x _ { i } \leq W$
  - $x _ { i } \in \{ 0,1 \} \quad \forall i \in l$
Example:
- Maximize:
  - $\sum _ { i = 1 } ^ { 4 } 4 x _ { 1 } + 10 x _ { 2 } + 5 x _ { 3 } + 8 x _ { 4 }$
- Subject to:
  - $\sum _ { i = 1 } ^ { 4 } 3 x _ { 1 } + 9 x _ { 2 } + 4 x _ { 3 } + 6 x _ { 4 } \leq 12$
  - $x _ { i } \in \{ 0,1 \} \quad \forall i \in \{ 1,2,3,4 \}$

构建数学模型
- Parameters:
  - n: 4
  - l: {1, 2, 3, 4}
  - p: {4, 10, 5, 8}
  - w: {3, 9, 4, 6}
  - W: 12
- Decision variables:
  - $x _ { i } \in \{ 0,1 \}$
- Subjective function:
  - MAX $\sum _ { i = 1 } ^ { 4 } 4 x _ { 1 } + 10 x _ { 2 } + 5 x _ { 3 } + 8 x _ { 4 }$
- Constraints:
  - $\sum _ { i = 1 } ^ { 4 } 3 x _ { 1 } + 9 x _ { 2 } + 4 x _ { 3 } + 6 x _ { 4 } \leq 12$
求解

x(0) = [0 0 1 0]T      Z = 5

N(x(0))  [1 0 1 0]T      Z = 9

            [0 1 1 0]T      infeasible

            [0 0 0 0]T      Z = 0

            [0 0 1 1]T      Z = 13

x(1) = [0 0 1 1]T

N(x(1))  [1 0 1 1]T     infeasible

            [0 1 1 1]T      infeasible

            [0 0 0 1]T      Z = 8

            [0 0 1 0]T      Z = 5

break

x(1) is local optimal

P89.Tabu search （不确定会考）

哪些要、哪些不要

x(0) = [0 0 1 0]T      Z = 5               tabu:None

N(x(0))  [1 0 1 0]T      Z = 9

            [0 1 1 0]T      infeasible

            [0 0 0 0]T      Z = 0

            [0 0 1 1]T      Z = 13

x(1) = [0 0 1 1]T                             tabu: x(0)

N(x(1))  [1 0 1 1]T     infeasible

            [0 1 1 1]T      infeasible

            [0 0 0 1]T      Z = 8

            [0 0 1 0]T      Z = 5 (不选，this is tabu)



x(2) = [0 0 0 1]                                tabu:x(1)

N(x(2))  [1 0 0 1]   Z = 12

             [0 1 0 1]   infeasible

             [0 0 1 1]   tabu

             [0 0 0 0]    Z = 0

...

P108.Recursion

定义

A function that is defined in terms of itself is called recursive.
Recursive functions require at least one base case
- A base case is an input value for which the function can be calculated without recursion.
- Without a base case it is not possible to terminate the calculation of a recursion function.
- 什么是base case（考点）：base case是一个(输入)值，不需要递归就可以为其计算函数。

举例

Example: f(x) = 2f(x -1) , where f(0) = 0 (x >= 0), f(0)=0为base case

递归的基本规则

Fundamental rules of recursion:
- Base cases: There needs to be at least one base case, which can be solved whithout recursion.
- Progress: For the cases that are solved using recursion, recursive calls must progress towards a base case.

P119.Mergesort

先分解再合并排序的过程
写出每步步骤

分治divide-and- conquer

Divide-and-conquer is an algorithm design technique based on recursion.
分治是一种基于递归的算法设计技术。
Divide: Smaller problems are solved recursively
Conquer: The solutions to the original problem is found by combining the solutions to the (smaller) subproblems.
- 原问题的解是由(较小的)子问题的解的组合得到的。

P133.Dynamic Programming

动态规划找出最优解、相比贪心算法的优点

P138

不选、选、画出图、动态规划要掌握该图
背包问题的动态规划图

Lecture 3-4

P4-

连通图、有向图、计算出度入度

P8.Cycle in directed graph

回路存在即不能进行拓扑排序

P10.Connected undirected graph

概念判断、什么是强连通图、连通图、判断这个图是不是强连通的、判断是不是完全图
完全的无向图里面的边数的关系

P15.Tree

什么是树、判断是不是树

P18.Graph representation

图的两种存储方式、把选择的那一种画出来
各自的优缺点
- 矩阵索引快，但是空间消耗大
- 链表慢，但是节省空间，没有无效存储、多次搜索（不知道是否正确具体参考ppt？）

P33.Prim’s algorithm

根据这两个算法、画出MST、会画就可以了

P35.Topological ordering

找出拓扑排序、并且解释为什么不能有环、彼此是彼此的依赖结点

Lecture 5-6

P2.What is complexity analysis?

什么是算法复杂度

P4-5.Basic operations of an algorithm & What is a basic operation?

不同算法的。。。排序中的遍历过程、merge比较

P7.Complexity as a function of the input - Examples

常见算法的复杂度、最好的情况、最坏的情况、在什么情况下最好

P20.Average and Worst case analysis

掌握最坏的情况、不用掌握平均的

P23.Relative growth rate of functions

给出一个表达式，可以用Big O的形式表达出来、去掉常数项和低次项还有系数

P29.Example: O(n3), Ω(n3), and Θ(n3)

上下界、O的上界、Ω的下界、Θ的确界

P36.P and NP

NP中N 的含义、NP是否等于P、一般是不等、说明原因

P46.How to show that a problem is N P complete I

过于具体、可以简化

P47.How to show that a problem is N P complete II

具体证明步骤、会证明
把第二条分成两点

P48.Amortized analysis - Initial example

只需要掌握基本概念、 a sequence of operations是关键词

P53.Amortized vs average-case analysis

两者并不一样、AC是发生的概率，并不考虑多个步骤再平均

Lecture 7-8

P4.Binary tree

二叉树的基本操作

P5.Binary search tree

什么是balance search tree、大小关系、给出一个不平衡的->平衡

P20.Tree balance

如何判断一棵树是否平衡

P29.Inserting

要会操作、和splay tree 两个考一个

P30.Splay trees

考步骤、会插入删除

P58.Red-black trees

掌握四条定义、会判断是否是红黑树

算法设计与分析复习

题型

Lecture 1-2

P19.Optimizing and heuristic algorithms

P20.Why heuristics?

P22.Constructive heuristics(建设性启发式)

P24.Greedy algorithm

P26-.Huffman’s algorithm

P29.Graph

P31.Binary tree

P35.Tries(prefix trees)

P36.Definition - Prefix

P42-.Huffmans’s algorithm

P58.Neighborhood search

P89.Tabu search （不确定会考）

P108.Recursion

P119.Mergesort

P133.Dynamic Programming

P138

Lecture 3-4

P4-

P8.Cycle in directed graph

P10.Connected undirected graph

P15.Tree

P18.Graph representation

P33.Prim’s algorithm

P35.Topological ordering

Lecture 5-6

P2.What is complexity analysis?

P4-5.Basic operations of an algorithm & What is a basic operation?

P7.Complexity as a function of the input - Examples

P20.Average and Worst case analysis

P23.Relative growth rate of functions

P29.Example: O(n3), Ω(n3), and Θ(n3)

P36.P and NP

P46.How to show that a problem is N P complete I

P47.How to show that a problem is N P complete II

P48.Amortized analysis - Initial example

P53.Amortized vs average-case analysis

Lecture 7-8

P4.Binary tree

P5.Binary search tree

P20.Tree balance

P29.Inserting

P30.Splay trees

P58.Red-black trees

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读