香婷婷一区二区视频,粉嫩喷水视频

[toc]

題型

判斷題，對了得分，錯了倒扣
簡答題
- 概念、什么是平衡二叉樹、什么是有向連通圖
- 給一個AVL樹、SPlay，畫出計算過程
- 給一個函數(shù)判斷是不是遞歸、這個遞歸有沒有什么問題
  - 是否少了邊界條件或者遞歸條件
- P是不是NP的子集、你能解釋是為什么嗎？分別說出他們的概念
- 解釋什么是Worse-case和平均情況、什么時候用WC什么時候用AC、AC和平均分攤之間有什么區(qū)別
- 排序算法的basic操作
- 給一個數(shù)據(jù)寫一下最近鄰
- 給一個圖寫出MST
- 紅黑樹的判斷、構(gòu)造一個紅黑樹（只要寫過程、不用實現(xiàn)）
- splay tree 的時間復(fù)雜度

Lecture 1-2

P19.Optimizing and heuristic algorithms

最優(yōu)解（優(yōu)化算法）和啟發(fā)式的區(qū)別、原因

相關(guān)知識點

有關(guān)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.

最優(yōu)解和啟發(fā)式的區(qū)別

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(經(jīng)驗法則) and they are often designed for a specific problem.

P20.Why heuristics?

為什么要選擇啟發(fā)式

得到最優(yōu)解要消耗大量計算資源
- An optimizing algorithm might consume too much resources.
輸入可能不是很準確，而啟發(fā)式算法有較強的魯棒性，能夠找到一個不錯的解
- Input to algorithm might be inaccurate and a heuristically good solution might be good enough.
啟發(fā)式算法更容易理解
- For a non-expert, it might be easier to uderstand a heuristic rather than an optimizing algorithm.

P22.Constructive heuristics(建設(shè)性啟發(fā)式)

均勻分布，在某個范圍內(nèi)等概率生成某些數(shù)
步驟、過程，step0-2、了解一下流程圖

定義

A constructive heuristic is a method that iteratively "builds up" a solution.（迭代地構(gòu)建解決方案）

怎么構(gòu)建

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
- 對應(yīng)上面的Assuming a solution consists of solution components
step0: Initialization: Begin with all free solution $x^{(0)} = (-, ..., -)$ and set solution index t = 0
- 對應(yīng)上面的start with nothing
step1: Termination criteria: If t = n, then break with approximate optimum (近似最優(yōu)) $x = x^{(t)}$
- 對應(yīng)下方的終止條件
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選擇一個值，該值似乎可以在終止時提供一個良好的可行解決方案。
- 對應(yīng)于上面的adds one value of exactly one variable in each iteration

結(jié)束條件

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

構(gòu)造啟發(fā)式的一種自然且常見的類型是貪婪算法

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.

給出字符串、能夠?qū)懗銮熬Y后綴、注意不止一個、是有一系列的前綴(上方的舉例中有)

P42-.Huffmans’s algorithm

給一個例子，然后畫出過程，構(gòu)建huffman??

P43~P50中有例子

P58.Neighborhood search

用來求解背包問題(18年新題目)、把背包問題描述成數(shù)學(xué)的形式、自己寫一遍算法、寫出計算步驟

定義鄰居
- 如果是在一維坐標軸上的實數(shù)
  - $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 \}$

構(gòu)建數(shù)學(xué)模型
- 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是一個(輸入)值，不需要遞歸就可以為其計算函數(shù)。

舉例

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

遞歸的基本規(guī)則

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.
分治是一種基于遞歸的算法設(shè)計技術(shù)。
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

動態(tài)規(guī)劃找出最優(yōu)解、相比貪心算法的優(yōu)點

P138

不選、選、畫出圖、動態(tài)規(guī)劃要掌握該圖
背包問題的動態(tài)規(guī)劃圖

Lecture 3-4

P4-

連通圖、有向圖、計算出度入度

P8.Cycle in directed graph

回路存在即不能進行拓撲排序

P10.Connected undirected graph

概念判斷、什么是強連通圖、連通圖、判斷這個圖是不是強連通的、判斷是不是完全圖
完全的無向圖里面的邊數(shù)的關(guān)系

P15.Tree

什么是樹、判斷是不是樹

P18.Graph representation

圖的兩種存儲方式、把選擇的那一種畫出來
各自的優(yōu)缺點
- 矩陣索引快，但是空間消耗大
- 鏈表慢，但是節(jié)省空間，沒有無效存儲、多次搜索（不知道是否正確具體參考ppt？）

P33.Prim’s algorithm

根據(jù)這兩個算法、畫出MST、會畫就可以了

P35.Topological ordering

找出拓撲排序、并且解釋為什么不能有環(huán)、彼此是彼此的依賴結(jié)點

Lecture 5-6

P2.What is complexity analysis?

什么是算法復(fù)雜度

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

不同算法的。。。排序中的遍歷過程、merge比較

P7.Complexity as a function of the input - Examples

常見算法的復(fù)雜度、最好的情況、最壞的情況、在什么情況下最好

P20.Average and Worst case analysis

掌握最壞的情況、不用掌握平均的

P23.Relative growth rate of functions

給出一個表達式，可以用Big O的形式表達出來、去掉常數(shù)項和低次項還有系數(shù)

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是關(guān)鍵詞

P53.Amortized vs average-case analysis

兩者并不一樣、AC是發(fā)生的概率，并不考慮多個步驟再平均

Lecture 7-8

P4.Binary tree

二叉樹的基本操作

P5.Binary search tree

什么是balance search tree、大小關(guān)系、給出一個不平衡的->平衡

P20.Tree balance

如何判斷一棵樹是否平衡

P29.Inserting

要會操作、和splay tree 兩個考一個

P30.Splay trees

考步驟、會插入刪除

P58.Red-black trees

掌握四條定義、會判斷是否是紅黑樹

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

算法設(shè)計與分析復(fù)習(xí)

題型

Lecture 1-2

P19.Optimizing and heuristic algorithms

P20.Why heuristics?

P22.Constructive heuristics(建設(shè)性啟發(fā)式)

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

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av