第一篇：音频分类总结(算法综述)
总结音频分类的算法
刚开始对音频分割还有特征提取有些自己的想法，感觉应该能够分清楚，但是当开始查阅文献的时候，发现对他们两个的概念越来越模糊。很多时候他们是重叠的。后来我在一篇文献里找到这句话。觉得应该是这个道理：
音频数据的分类是一个模式识别的问题，它包括两个基本方面：特征选择和分类。
音频分割是在音频分类的基础上从音频流中提取出不同的音频类别，也就是说在时间轴上对音频流按类别进行划分。分类是分割的前提和基础。对音频流的准确分割是最终的目的。
于是我找了一下比较典型的分类算法
比较典型的音频分类算法包括最小距离方法、支持向量机、神经网络、决策树方法和隐马尔可夫模型方法等。
1．最小距离法。(典型的音频分类算法)最小距离分类法的优点是概念直观，方法简单，有利于建立多维空间分类方法的几何概念。在音频分类中应用的最小距离分类法有k近邻(k—Nearest Neighbor，简称K—NN)方法和最近特征线方法(Nearest Feature，简称NFL))等。
k近邻方法的思想是根据未知样本X最近邻的k个样本点的类别来确定X的类别。为此，需要计算X与所有样本x。的距离d(x，x。)，并且从中选出最小的k个样本作为近邻样本集合KNN，计算其中所有属于类别Wj的距离之和，并且按照以下判别规则进行分类：C(x)argminC{W1,...,Wn}
d(x,xi),其中，C为类别集合由于k近邻方法利用了更多的样本信息确定它的类别，k取大一些有利于减少噪声的影响。但是由于k近邻方法中需要计算所有样本的距离，因此当样本数目非常大的时候，计算量就相当可观。取k=l时，k近邻方法就退化为最近邻方法。
最近特征线方法是从每一类的样本子空间中选取一些原型(Prototype)特征点，这些特征点的两两连线称为特征线(Feature Line)，这些特征线的集合用来表示原先每一类的样本子空间。
设类C的原型特征点集合:,其中Nc为类C的原型特征点数目，则对应的特征线的数目为Sc，而类C的特征线集合
{|XicXjc|1i,jNc，ij} i≠jl构成类C的特征线空间，它是类C的特征子空间。—般所选取的原型特征点的数目比较少，因此特征线的数目也比较少。未知样本X与特征线XicXjc的距离定义为x在XicXjc上的投影距离，如图4所示，而X与类别C的距离为X与类C的特征线空间中的所有特征线的最短距离。
2．神经网络(Neural Network)。
在使用神经网络进行音频分类时，可以令输入层的节点与音频的特征向量相对应，而输出层的节点对应于类别Ci。，如图5所示。在训练时，通过对训练样本集中的样本进行反复学习来调节网络，从而使全局误差函数取得最小值。这样，就可以期望该网络能够对新输入的待分类样本T输出正确的分类Ci。
3．支持向量机(support Vector Machine，简称为SVM)。
支持向量机是Vapnik等人提出的以结构风险最小化原理(Stuctural Risk Minimization Principle)为基础的分类方法。该方法最初来自于对二值分类问题的处理，其机理是在样本空间中寻找—个将训练集中的正例和反例两类样本点分割开来的分类超平面，并取得最大边缘(正样本与负样本到超平面的最小距离)，如图6所示。该方法根据核空间理论将低维的输入空间数据通过某种非线性函数(即核函数)映射到—个高维空间中，并且线性判决只需要在高维空间中进行内积运算，从而解决了线性不可分的分类问题。
根据不同的分类问题，可以选用不同的核函数，常用的核函数有三种：
① 项式核函数:
② 径向基核函数:
③ Sigmoid核函数：
SVM训练算法主要有三类：二次规划算法，分解算法，增量算法。
4．决策树方法
决策树是一种结构简单、搜索效率高的分类器。这类方法以信息论为基础，对大量的实例选择重要的特征建立决策树，如图7所示。
最优决策树的构造是一个NP完全(NPComepleteness)问题，其设计原则可以形式化地表示为
其中T为特定的决策树结构，F和d分别为分枝结,为在数据集合点的特征子集和决策规则，D为所有的训练数据，D上选取特征集合F和决策规则d训练得到的结构为T的决策树的分类错误的条件概率。因此，决策树的构造过程可以分为三个问题：选取合适的结构，为分枝结点选取合适的特征子集和决策规则。常用的决策树构造方法有非回溯的贪心(Greedy)算法和梯度上升算法。
5.隐马尔可夫模型(Hidden Markov Model，简HMM)方法。
隐马尔可夫模型(HMM)的音频分类性能较好，它的分类对象是语音(speech)、音乐(music)以及语音和音乐的混合(speech+music)共3类数据，根据极大似然准则判定它们的类别，最优分类精度可达90.28％。
HMM本质上是一种双重随机过程的有限状态自动机(stochastic finite-state automata)，它具有刻画信号的时间统计特性的能力。双重随机过程是指满足Markov分布的状态转换Markov链以及每一状态的观察输出概率密度函数，共两个随机过程。HMM可以用3元组来表示：入；(A，B，)，其中A是状态Si到Sj的转换概率矩阵，B是状态的观察输出概率密度，是状态的初始分布概率。
第二篇：分类算法总结
分类算法
数据挖掘中有很多领域，分类就是其中之一，什么是分类，分类就是把一些新得数据项映射到给定类别的中的某一个类别，比如说当我们发表一篇文章的时候，就可以自动的把这篇文章划分到某一个文章类别，一般的过程是根据样本数据利用一定的分类算法得到分类规则，新的数据过来就依据该规则进行类别的划分。
分类在数据挖掘中是一项非常重要的任务，有很多用途，比如说预测，即从历史的样本数据推算出未来数据的趋向，有一个比较著名的预测的例子就是大豆学习。再比如说分析用户行为，我们常称之为受众分析，通过这种分类，我们可以得知某一商品的用户群，对销售来说有很大的帮助。
分类器的构造方法有统计方法，机器学习方法，神经网络方法等等。常见的统计方法有knn算法，基于事例的学习方法。机器学习方法包括决策树法和归纳法，上面讲到的受众分析可以使用决策树方法来实现。神经网络方法主要是bp算法，这个俺也不太了解。文本分类，所谓的文本分类就是把文本进行归类，不同的文章根据文章的内容应该属于不同的类别，文本分类离不开分词，要将一个文本进行分类，首先需要对该文本进行分词，利用分词之后的的项向量作为计算因子，再使用一定的算法和样本中的词汇进行计算，从而可以得出正确的分类结果。在这个例子中，我将使用庖丁分词器对文本进行分词。目前看到的比较全面的分类算法,总结的还不错.2.4.1 主要分类方法介绍解决分类问题的方法很多[40-42]，单一的分类方法主要包括：决策树、贝叶斯、人工神经网络、K-近邻、支持向量机和基于关联规则的分类等；另外还有用于组合单一分类方法的集成学习算法，如Bagging和Boosting等。（1）决策树
决策树是用于分类和预测的主要技术之一，决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的实例中推理出以决策树表示的分类规则。构造决策树的目的是找出属性和类别间的关系，用它来预测将来未知类别的记录的类别。它采用自顶向下的递归方式，在决策树的内部节点进行属性的比较，并根据不同属性值判断从该节点向下的分支，在决策树的叶节点得到结论。
主要的决策树算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT算法等。它们在选择测试属性采用的技术、生成的决策树的结构、剪枝的方法以及时刻，能否处理大数据集等方面都有各自的不同之处。（2）贝叶斯 贝叶斯（Bayes）分类算法是一类利用概率统计知识进行分类的算法，如朴素贝叶斯（Naive Bayes）算法。这些算法主要利用Bayes定理来预测一个未知类别的样本属于各个类别的可能性，选择其中可能性最大的一个类别作为该样本的最终类别。由于贝叶斯定理的成立本身需要一个很强的条件独立性假设前提，而此假设在实际情况中经常是不成立的，因而其分类准确性就会下降。为此就出现了许多降低独立性假设的贝叶斯分类算法，如TAN（Tree Augmented Na?ve Bayes)算法，它是在贝叶斯网络结构的基础上增加属性对之间的关联来实现的。
（3）人工神经网络
人工神经网络（Artificial Neural Networks，ANN）是一种应用类似于大脑神经突触联接的结构进行信息处理的数学模型。在这种模型中，大量的节点（或称”神经元”，或”单元”）之间相互联接构成网络，即”神经网络”，以达到处理信息的目的。神经网络通常需要进行训练，训练的过程就是网络进行学习的过程。训练改变了网络节点的连接权的值使其具有分类的功能，经过训练的网络就可用于对象的识别。目前，神经网络已有上百种不同的模型，常见的有BP网络、径向基RBF网络、Hopfield网络、随机神经网络（Boltzmann机）、竞争神经网络（Hamming网络，自组织映射网络）等。但是当前的神经网络仍普遍存在收敛速度慢、计算量大、训练时间长和不可解释等缺点。（4）k-近邻
k-近邻(kNN，k-Nearest Neighbors)算法是一种基于实例的分类方法。该方法就是找出与未知样本x距离最近的k个训练样本，看这k个样本中多数属于哪一类，就把x归为那一类。k-近邻方法是一种懒惰学习方法，它存放样本，直到需要分类时才进行分类，如果样本集比较复杂，可能会导致很大的计算开销，因此无法应用到实时性很强的场合。（5）支持向量机
支持向量机（SVM，Support Vector Machine）是Vapnik根据统计学习理论提出的一种新的学习方法[43]，它的最大特点是根据结构风险最小化准则，以最大化分类间隔构造最优分类超平面来提高学习机的泛化能力，较好地解决了非线性、高维数、局部极小点等问题。对于分类问题，支持向量机算法根据区域中的样本计算该区域的决策曲面，由此确定该区域中未知样本的类别。
（6）基于关联规则的分类
关联规则挖掘是数据挖掘中一个重要的研究领域。近年来，对于如何将关联规则挖掘用于分类问题，学者们进行了广泛的研究。关联分类方法挖掘形如condset→C的规则，其中condset是项(或属性-值对)的集合，而C是类标号，这种形式的规则称为类关联规则（class association rules，CARS）。关联分类方法一般由两步组成：第一步用关联规则挖掘算法从训练数据集中挖掘出所有满足指定支持度和置信度的类关联规则；第二步使用启发式方法从挖掘出的类关联规则中挑选出一组高质量的规则用于分类。属于关联分类的算法主要包括CBA[44]，ADT[45]，CMAR[46] 等。（7）集成学习（Ensemble Learning）
实际应用的复杂性和数据的多样性往往使得单一的分类方法不够有效。因此，学者们对多种分类方法的融合即集成学习进行了广泛的研究。集成学习已成为国际机器学习界的研究热点，并被称为当前机器学习四个主要研究方向之一。集成学习是一种机器学习范式，它试图通过连续调用单个的学习算法，获得不同的基学习器，然后根据规则组合这些学习器来解决同一个问题，可以显著的提高学习系统的泛化能力。组合多个基学习器主要采用（加权）投票的方法，常见的算法有装袋[47]（Bagging），提升/推进[48, 49]（Boosting）等。
有关分类器的集成学习见图2-5。集成学习由于采用了投票平均的方法组合多个分类器，所以有可能减少单个分类器的误差，获得对问题空间模型更加准确的表示，从而提高分类器的分类准确度。
图2-5：分类器的集成学习
以上简单介绍了各种主要的分类方法，应该说其都有各自不同的特点及优缺点。对于数据库负载的自动识别，应该选择哪种方法呢？用来比较和评估分类方法的标准[50] 主要有：（1）预测的准确率。模型正确地预测新样本的类标号的能力；（2）计算速度。包括构造模型以及使用模型进行分类的时间；（3）强壮性。模型对噪声数据或空缺值数据正确预测的能力；（4）可伸缩性。对于数据量很大的数据集，有效构造模型的能力；（5）模型描述的简洁性和可解释性。模型描述愈简洁、愈容易理解，则愈受欢迎。
最初的数据挖掘分类应用大多都是在这些方法及基于内存基础上所构造的算法。目前数据挖掘方法都要求具有基于外存以处理大规模数据集合能力且具有可扩展能力。下面对几种主要的分类方法做个简要介绍：
（1）决策树
决策树归纳是经典的分类算法。它采用自顶向下递归的各个击破方式构造决策树。树的每一个结点上使用信息增益度量选择测试属性。可以从生成的决策树中提取规则。
(2)KNN法(K-Nearest Neighbor)
KNN法即K最近邻法，最初由Cover和Hart于1968年提出的，是一个理论上比较成熟的方法。该方法的思路非常简单直观：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。另外还有一种Reverse KNN法，能降低KNN算法的计算复杂度，提高分类的效率。
该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
(3)SVM法
SVM法即支持向量机(Support Vector Machine)法，由Vapnik等人于1995年提出，具有相对优良的性能指标。该方法是建立在统计学习理论基础上的机器学习方法。通过学习算法，SVM可以自动寻找出那些对分类有较好区分能力的支持向量，由此构造出的分类器可以最大化类与类的间隔，因而有较好的适应能力和较高的分准率。该方法只需要由各类域的边界样本的类别来决定最后的分类结果。
支持向量机算法的目的在于寻找一个超平面H(d),该超平面可以将训练集中的数据分开，且与类域边界的沿垂直于该超平面方向的距离最大，故SVM法亦被称为最大边缘(maximum margin)算法。待分样本集中的大部分样本不是支持向量，移去或者减少这些样本对分类结果没有影响，SVM法对小样本情况下的自动分类有着较好的分类结果。
(4)VSM法
VSM法即向量空间模型(Vector Space Model)法，由Salton等人于60年代末提出。这是最早也是最出名的信息检索方面的数学模型。其基本思想是将文档表示为加权的特征向量：D=D(T1，W1；T2，W2；…；Tn，Wn)，然后通过计算文本相似度的方法来确定待分样本的类别。当文本被表示为空间向量模型的时候，文本的相似度就可以借助特征向量之间的内积来表示。
在实际应用中，VSM法一般事先依据语料库中的训练样本和分类体系建立类别向量空间。当需要对一篇待分样本进行分类的时候，只需要计算待分样本和每一个类别向量的相似度即内积，然后选取相似度最大的类别作为该待分样本所对应的类别。
由于VSM法中需要事先计算类别的空间向量，而该空间向量的建立又很大程度的依赖于该类别向量中所包含的特征项。根据研究发现，类别中所包含的非零特征项越多，其包含的每个特征项对于类别的表达能力越弱。因此，VSM法相对其他分类方法而言，更适合于专业文献的分类。
(5)Bayes法
Bayes法是一种在已知先验概率与类条件概率的情况下的模式分类方法，待分样本的分类结果取决于各类域中样本的全体。
设训练样本集分为M类，记为C=｛c1，…，ci，…cM}，每类的先验概率为P(ci)，i=1，2，…，M。当样本集非常大时，可以认为P(ci)=ci类样本数/总样本数。对于一个待分样本X，其归于cj类的类条件概率是P(X/ci)，则根据Bayes定理，可得到cj类的后验概率P(ci/X)：
P(ci/x)=P(x/ci)・P(ci)/P(x)(1)若P(ci/X)=MaxjP(cj/X)，i=1，2，…，M，j=1，2，…，M，则有x∈ci(2)式(2)是最大后验概率判决准则，将式(1)代入式(2)，则有：
若P(x/ci)P(ci)=Maxj［P(x/cj)P(cj)］，i=1，2，…，M，j=1，2，…，M，则x∈ci 这就是常用到的Bayes分类判决准则。经过长期的研究，Bayes分类方法在理论上论证得比较充分，在应用上也是非常广泛的。
Bayes方法的薄弱环节在于实际情况下，类别总体的概率分布和各类样本的概率分布函数(或密度函数)常常是不知道的。为了获得它们，就要求样本足够大。另外，Bayes法要求表达文本的主题词相互独立，这样的条件在实际文本中一般很难满足，因此该方法往往在效果上难以达到理论上的最大值。
（6）神经网络
神经网络分类算法的重点是构造阈值逻辑单元，一个值逻辑单元是一个对象，它可以输入一组加权系数的量，对它们进行求和，如果这个和达到或者超过了某个阈值，输出一个量。如有输入值X1, X2,..., Xn和它们的权系数：W1, W2,...,Wn，求和计算出的 Xi*Wi，产生了激发层 a =(X1 * W1)+(X2 * W2)+...+(Xi * Wi)+...+(Xn * Wn)，其中Xi 是各条记录出现频率或其他参数，Wi是实时特征评估模型中得到的权系数。神经网络是基于经验风险最小化原则的学习算法，有一些固有的缺陷，比如层数和神经元个数难以确定，容易陷入局部极小，还有过学习现象，这些本身的缺陷在SVM算法中可以得到很好的解决。
第三篇：2018高考分类-算法
（2018北京3）.执行如图所示的程序框图，输出的s值为 A.B.C.D.，设计了下面的程序框图，则在空白框中应填入
D.（2018全国2）7.为计算A.B.C.（2018北京3）
（2018全国2）
（2018天津3）.阅读右边的程序框图，运行相应的程序，若输入N的值为20，则输出T的值为
A.1
B.2
C.3
D.4
（2018江苏）4.一个算法的伪代码如图所示，执行此算法，最后输出的S的值为________．
（2018江苏）
（2018天津3）
第四篇：alsa音频总结
Linux音频驱动总结
参考文章：http://blog.csdn.net/droidphone/
http://blog.chinaunix.net/uid/22917448.html
分析只列出部分重要代码，具体请参考linux3.0内核代码。
Alsa架构整体来说十分复杂，但对于驱动移植来说我们仅仅只需要关心ASOC就足够了。在学习asoc之前我们先了解一些专业术语：
ASoC currently supports the three main Digital Audio Interfaces(DAI)found on SoC controllers and portable audio CODECs today, namely AC97, I2S and PCM.ASoC现在支持如今的SoC控制器和便携音频解码器上的三个主要数字音频接口，即AC97，I2S，PCM（与pcm音频格式注意区分，前者是一种音频接口，后者是一种输入声卡的音频格式）。
AC97 AC97 ====
AC97 is a five wire interface commonly found on many PC sound cards.It is now also popular in many portable devices.This DAI has a reset line and time multiplexes its data on its SDATA_OUT(playback)and SDATA_IN(capture)lines.The bit clock(BCLK)is always driven by the CODEC(usually 12.288MHz)and the frame(FRAME)(usually 48kHz)is always driven by the controller.Each AC97 frame is 21uS long and is divided into 13 time slots.AC97是一种个人电脑声卡上常见的五线接口。现在在很多便携设备中也很流行。这个数字音频接口有一个复位线，分时在SDATA＿OUT（回放）和SDATA＿IN（捕获）线上传送数据。位时钟常由解码器驱动（通常是12.288MHz).帧时钟（通常48kHz)总是由控制器驱动。每个AC97帧21uS,并分为13个时间槽。
I2S I2S ===
I2S is a common 4 wire DAI used in HiFi, STB and portable devices.The Tx and Rx lines are used for audio transmission, whilst the bit clock(BCLK)and left/right clock(LRC)synchronise the link.I2S is flexible in that either the controller or CODEC can drive(master)the BCLK and LRC clock lines.Bit clock usually varies depending on the sample rate and the master system clock(SYSCLK).LRCLK is the same as the sample rate.A few devices support separate ADC and DAC LRCLKs, this allows for simultaneous capture and playback at different sample rates.I2S是一个4线数字音频接口，常用于HiFi，STB便携设备。Tx 和Rx信号线用于音频传输。而位时钟和左右时钟（LRC）用于同步链接。I2S具有灵活性，因为控制器和解码器都可以控制位时钟和左右时钟。位时钟因采样率和主系统时钟而有不同。LRCLK与采样率相同。少数设备支持独立的ADC和DAC的LRCLK。这使在不同采样率情况下同步捕获和回放成为可能。
I2S has several different operating modes:-I2S有几个不同的操作模式：
o I2SMSB is transmitted on transition of LRC.左对齐模式：MSB在LRC传送时传送。
o Right JustifiedMSB is transmitted on falling edge of first BCLK after FRAME/SYNC.模式A－MSB在FRAME/SYNC后第一个BCLK的下降沿传送。
o Mode Busing I2C, 3 Wire(SPI)or both APIs 3)Mixers and audio controls 4)Codec audio operations 1）解码器数字音频接口和PCM配置。
2）解码器控制IO－使用I2C，3总线（SPI）或两个都有。3）混音器和音频控制。4）解码器音频操作。
Optionally, codec drivers can also provide:-解码器驱动可以选择性提供：
5)DAPM description.6)DAPM event handler.7)DAC Digital mute control.5）动态音频电源管理描述。6）动态音频电源管理事件控制。7）数模转换数字消音控制。SoC DAI Drivers 板级DAI驱动 ===============
Each SoC DAI driver must provide the following features:-每个SoC DAI驱动都必须提供如下性能：
1)Digital audio interface(DAI)description 1)数字音频接口描述
2)Digital audio interface configuration 2)数字音频接口配置 3)PCM's description 3）PCM描述
4)SYSCLK configuration 4）系统时钟配置
5)Suspend and resume(optional)5）挂起和恢复（可选的）
以上由君子翻译，本人实在没办法比他描述的更好了，所以把重要的部分提取出来直接copy。在这里对君子表示由衷感谢，赋上君子注。君子注:
您现在所阅读的，是君子阅读Linux音频SoC驱动时，写下的文档译文。
君子写些译文，一方面是作为自己的笔记，帮助记忆，另一方面也希望能对他人有所帮助。如果您能于君子的译文中有所收获，则吾心甚慰
现在我们开始分析ASOC：
ASoC被分为Machine、Platform和Codec三大部分。其中的Machine驱动负责Platform和Codec之间的耦合和设备或板子特定的代码。
看起来挺复杂，其实需要我们做的事情并不多，大部分内核已经完成。下面我们分析哪些是我们需要自己做的：
codec驱动：负责音频解码。这部分代码完全无平台无关，设备原厂提供，我们只需要把它加进内核编译就好了。platform驱动：与处理器芯片相关，这部分代码在该芯片商用之前方案产商提供的demo板已完全确定了，也就是说我们只需要使用就可以了。
machine驱动：好了，到了最关键的地方了，machine驱动是耦合platform和codec驱动，同时与上层交互的代码。由于上层是标准的alsa架构，所以下层接口肯定要做了统一，所以我很负责的告诉你，这部分由machine本身的platform驱动和platform设备组成(请跟asoc的platform驱动区别)，platform驱动内核帮我们完成了，所以你无须过多的关心你的驱动怎么跟上层alsa怎么衍接的问题，我们只需要注册一个machine的platform设备以及完成platform和codec耦合就ok
asoc的关系图如下：（以下适应于linux3.0。linux2.6会有所不同）
上图把asoc架构显示的淋漓尽致，如果你分析了asoc你就会发现上图描述的结构以及函数真的一个都跑不了。
Machie：
Machine platform device:(~/sound/soc/samsung/smdk_wm8994.c)
1.smdk_snd_device = platform_device_alloc(“soc-audio”,-1);2.if(!smdk_snd_device)3.return-ENOMEM;4.5.platform_set_drvdata(smdk_snd_device, &smdk);6.7.ret = platform_device_add(smdk_snd_device);
1.static struct snd_soc_dai_link smdk_dai[] = { 2.{ /* Primary DAI i/f */
3..name = “WM8994 AIF1”, 4..stream_name = “Pri_Dai”, 5..cpu_dai_name = “samsung-i2s.0”, 6..codec_dai_name = “wm8994-aif1”, 7..platform_name = “samsung-audio”, 8..codec_name = “wm8994-codec”, 9..init = smdk_wm8994_init_paiftx, 10..ops = &smdk_ops, 11.}, { /* Sec_Fifo Playback i/f */
12..name = “Sec_FIFO TX”, 13..stream_name = “Sec_Dai”, 14..cpu_dai_name = “samsung-i2s.4”, 15..codec_dai_name = “wm8994-aif1”, 16..platform_name = “samsung-audio”, 17..codec_name = “wm8994-codec”, 18..ops = &smdk_ops, 19.}, 20.};21.22.static struct snd_soc_card smdk = { 23..name = “SMDK-I2S”, 24..owner = THIS_MODULE, 25..dai_link = smdk_dai，26..num_links = ARRAY_SIZE(smdk_dai), 27.};
通过snd_soc_card结构，又引出了Machine驱动的另外两个个数据结构：
snd_soc_dai_link（实例：smdk_dai[]）snd_soc_ops（实例：smdk_ops）
snd_soc_dai_link看名字就知道，很明显它是起耦合链接作用的。它指定了Platform、Codec、codec_dai、cpu_dai的名字，稍后Machine驱动将会利用这些名字去匹配已经在系统中注册的platform，codec，dai。
snd_soc_ops连接Platform和Codec的dai_link对应的ops操作函数，本例就是smdk_ops，它只实现了hw_params函数：smdk_hw_params。
到此为止，最主要的部分machine的平台设备注册我们完成了。
下面我们关注machine平台驱动部分(这部分内核不需要我们实现，但我们需要知道它是怎么工作的）
ASoC的platform_driver在以下文件中定义：sound/soc/soc-core.c。还是先从模块的入口看起：
[cpp] view plaincopy 1.static int __init snd_soc_init(void)2.{ 3.......4.return platform_driver_register(&soc_driver);5.}
soc_driver的定义如下：
[cpp] view plaincopy
1./* ASoC platform driver */
2.static struct platform_driver soc_driver = { 3..driver = {
4..name = “soc-audio”, //确保你注册machine平台设备和它保持一致 5..owner = THIS_MODULE, 6..pm = &soc_pm_ops, 7.}，8..probe = soc_probe, 9..remove = soc_remove, 10.};
初始化入口soc_probe()
soc_probe函数本身很简单，它先从platform_device参数中取出snd_soc_card，然后调用snd_soc_register_card，通过snd_soc_register_card，为snd_soc_pcm_runtime数组申请内存，每一个dai_link对应snd_soc_pcm_runtime数组的一个单元，然后把snd_soc_card中的dai_link配置复制到相应的snd_soc_pcm_runtime中，最后，大部分的工作都在snd_soc_instantiate_card中实现，下面就看看snd_soc_instantiate_card做了些什么： 该函数首先利用card->instantiated来判断该卡是否已经实例化，如果已经实例化则直接返回，否则遍历每一对dai_link，进行codec、platform、dai的绑定工作，下只是代码的部分选节，详细的代码请直接参考完整的代码树。static int soc_probe(struct platform_device *pdev){
struct snd_soc_card *card = platform_get_drvdata(pdev);//别忘记了machine的platform_set_drvdata //取出snd_soc_card
.............ret = snd_soc_register_card(card);//注册............}
下面我们看snd_soc_register_card()函数:
int snd_soc_register_card(struct snd_soc_card *card){
。。。。
card->rtd = kzalloc(sizeof(struct snd_soc_pcm_runtime)*
(card->num_links + card->num_aux_devs)，GFP_KERNEL);//为snd_soc_pcm_runtime数组申请内存，每一个dai_link对应一个snd_soc_pcm_runtime数组单元。。。。
for(i = 0;i < card->num_links;i++)
card->rtd[i].dai_link = &card->dai_link[i];//把snd_soc_card中的dai_link复制到相应的snd_soc_pcm_runtime。。。。
snd_soc_instantiate_cards();//将调用snd_soc_instantiate_card()//最为重要 }
下面我们分析snd_soc_instantiate_card()函数：
static void snd_soc_instantiate_card(struct snd_soc_card *card){
。。。。
if(card->instantiated){ //判断该卡是否已经实例化，如果是就返回
mutex_unlock(&card->mutex);
return;
}
/* bind DAIs */
for(i = 0;i < card->num_links;i++)//否则遍例每一对dai_link，进行codec,flatrom,dai的绑定工作
soc_bind_dai_link(card, i);/* ******************************************************************************************************************************************************************
ASoC定义了三个全局的链表头变量：codec_list、dai_list、platform_list，系统中所有的Codec、DAI、Platform都在注册时连接到这三个全局链表上。soc_bind_dai_link函数逐个扫描这三个链表，根据card->dai_link[]中的名称进行匹配，匹配后把相应的codec，dai和platform实例赋值到card->rtd[]中（snd_soc_pcm_runtime）。经过这个过程后，snd_soc_pcm_runtime：（card->rtd）中保存了本Machine中使用的Codec，DAI和Platform驱动的信息。
*****************************************************************************************************************************************************************/
/* bind completed ? */
if(card->num_rtd!= card->num_links){
mutex_unlock(&card->mutex);
return;
}
。。。。。
/* card bind complete so register a sound card */
ret = snd_card_create(SNDRV_DEFAULT_IDX1, SNDRV_DEFAULT_STR1,card->owner, 0, &card->snd_card)。。。。。
card->snd_card->dev = card->dev;
card->dapm.bias_level = SND_SOC_BIAS_OFF;
card->dapm.dev = card->dev;
card->dapm.card = card;
list_add(&card->dapm.list, &card->dapm_list);//初始化codec缓存，创建声卡实例
。。。。。。。//下面是最重要的probe匹配工作
if(card->probe){
ret = card->probe(card);
if(ret < 0)
goto card_probe_error;
}
。。。。。
ret = soc_probe_dai_link(card, i, order);//主要的耦合链接工作在此函数完成。。。。。
ret = soc_probe_aux_dev(card, i)。。。。。
if(card->late_probe){//最后的声卡初始化工作，ret = card->late_probe(card);
}
。。。。。
ret = snd_card_register(card->snd_card);//然后调用标准的alsa驱动的声卡函数进行声卡注册
。。。。。
}
到这里声卡已经注册好了，声卡可以正常工作了，我们再分析最后一个函数，也就是它们是怎么匹配的 soc_probe_dai_link():
static int soc_probe_dai_link(struct snd_soc_card *card, int num, int order){
。。。。。
/* probe the cpu_dai */
if(!cpu_dai->probed &&
cpu_dai->driver->probe_order == order){
if(!try_module_get(cpu_dai->dev->driver->owner))
return-ENODEV;
if(cpu_dai->driver->probe){
ret = cpu_dai->driver->probe(cpu_dai);
if(ret < 0){
printk(KERN_ERR “asoc: failed to probe CPU DAI %sn”, cpu_dai->name);
module_put(cpu_dai->dev->driver->owner);
return ret;
}
}
cpu_dai->probed = 1;
/* mark cpu_dai as probed and add to card dai list */
list_add(&cpu_dai->card_list, &card->dai_dev_list);
}
/* probe the CODEC */
if(!codec->probed &&
codec->driver->probe_order == order){
ret = soc_probe_codec(card, codec);
if(ret < 0)
return ret;
}
/* probe the platform */
if(!platform->probed &&
platform->driver->probe_order == order){
ret = soc_probe_platform(card, platform);
if(ret < 0)
return ret;
}
/* probe the CODEC DAI */
if(!codec_dai->probed && codec_dai->driver->probe_order == order){
if(codec_dai->driver->probe){
ret = codec_dai->driver->probe(codec_dai);
if(ret < 0){
printk(KERN_ERR “asoc: failed to probe CODEC DAI %sn”, codec_dai->name);
return ret;
}
}
/* mark codec_dai as probed and add to card dai list */
codec_dai->probed = 1;
list_add(&codec_dai->card_list, &card->dai_dev_list);
}
/* complete DAI probe during last probe */
if(order!= SND_SOC_COMP_ORDER_LAST)return 0;
。。。。。
/* create the pcm */
ret = soc_new_pcm(rtd, num);//如果上面都匹配成功将创建标准的alsa的pcm逻辑设备
。。。。。
}
好了，到此为止我们最主要的部分machine部分分析完成了。接着是codec驱动部分：
Codec简介
在移动设备中，Codec的作用可以归结为4种，分别是：
对PCM等信号进行D/A转换，把数字的音频信号转换为模拟信号
对Mic、Linein或者其他输入源的模拟信号进行A/D转换，把模拟的声音信号转变CPU能够处理的数字信号
对音频通路进行控制，比如播放音乐，收听调频收音机，又或者接听电话时，音频信号在codec内的流通路线是不一样的
对音频信号做出相应的处理，例如音量控制，功率放大，EQ控制等等
ASoC对Codec的这些功能都定义好了一些列相应的接口，以方便地对Codec进行控制。ASoC对Codec驱动的一个基本要求是：驱动程序的代码必须要做到平台无关性，以方便同一个Codec的代码不经修改即可用在不同的平台上。以下的讨论基于wolfson的Codec芯片WM8994，kernel的版本3.3.x。
描述Codec的最主要的几个数据结构分别是：snd_soc_codec，snd_soc_codec_driver，snd_soc_dai，snd_soc_dai_driver，其中的snd_soc_dai和snd_soc_dai_driver在ASoC的Platform驱动中也会使用到，Platform和Codec的DAI通过snd_soc_dai_link结构，在Machine驱动中进行绑定连接。
Codec的注册
因为Codec驱动的代码要做到平台无关性，要使得Machine驱动能够使用该Codec，Codec驱动的首要任务就是确定snd_soc_codec和snd_soc_dai的实例，并把它们注册到系统中，注册后的codec和dai才能为Machine驱动所用。以WM8994为例，对应的代码位置：/sound/soc/codecs/wm8994.c，模块的入口函数注册了一个platform driver：
[html] view plaincopy
1.static struct platform_driver wm8994_codec_driver = { 2..driver = { 3..name = “wm8994-codec”, //注意machine device里面和这里保持一致 4..owner = THIS_MODULE, 5.}, 6..probe = wm8994_probe, 7..remove = __devexit_p(wm8994_remove), 8.};9.10.module_platform_driver(wm8994_codec_driver);有platform driver，必定会有相应的platform device，platform device其实在我们之前讲过的machine device注册时已经引入了。
[html] view plaincopy
1.static int __devinit wm8994_probe(struct platform_device *pdev)2.{
3.return snd_soc_register_codec(&pdev->dev, &soc_codec_dev_wm8994, 4.wm8994_dai, ARRAY_SIZE(wm8994_dai));5.}
其中，soc_codec_dev_wm8994和wm8994_dai的定义如下（代码中定义了3个dai，这里只列出第一个）：
[html] view plaincopy
1.static struct snd_soc_codec_driver soc_codec_dev_wm8994 = { 2..probe = wm8994_codec_probe, 3..remove = wm8994_codec_remove, 4..suspend = wm8994_suspend, 5..resume = wm8994_resume，6..set_bias_level = wm8994_set_bias_level, 7..reg_cache_size = WM8994_MAX_REGISTER, 8..volatile_register = wm8994_soc_volatile, 9.};
[html] view plaincopy
1.static struct snd_soc_dai_driver wm8994_dai[] = { 2.{
3..name = “wm8994-aif1”, 4..id = 1, 5..playback = {
6..stream_name = “AIF1 Playback”, 7..channels_min = 1, 8..channels_max = 2, 9..rates = WM8994_RATES, 10..formats = WM8994_FORMATS, 11.}，12..capture = {
13..stream_name = “AIF1 Capture”, 14..channels_min = 1, 15..channels_max = 2, 16..rates = WM8994_RATES, 17..formats = WM8994_FORMATS, 18.}，19..ops = &wm8994_aif1_dai_ops, 20.}, 21.......22.}
可见，Codec驱动的第一个步骤就是定义snd_soc_codec_driver和snd_soc_dai_driver的实例，然后调用snd_soc_register_codec函数对Codec进行注册。
snd_soc_register_codec（）函数是machine driver提供的，只要注册成功后codec提供的操作函数就能正常提供给machine driver使用了。int snd_soc_register_codec(struct device *dev，const struct snd_soc_codec_driver *codec_drv, struct snd_soc_dai_driver *dai_drv, int num_dai){ codec = kzalloc(sizeof(struct snd_soc_codec), GFP_KERNEL)。。。。。。
/* create CODEC component name */ codec->name = fmt_single_name(dev, &codec->id);/*Machine驱动定义的snd_soc_dai_link中会指定每个link的codec和dai的名字，进行匹配绑定时就是通过和这里的名字比较，从而找到该Codec的 */
// 然后初始化它的各个字段，多数字段的值来自上面定义的snd_soc_codec_driver的实例soc_codec_dev_wm8994： codec->write = codec_drv->write;codec->read = codec_drv->read;codec->volatile_register = codec_drv->volatile_register;codec->readable_register = codec_drv->readable_register;codec->writable_register = codec_drv->writable_register;codec->dapm.bias_level = SND_SOC_BIAS_OFF;codec->dapm.dev = dev;codec->dapm.codec = codec;codec->dapm.seq_notifier = codec_drv->seq_notifier;codec->dev = dev;codec->driver = codec_drv;codec->num_dai = num_dai;mutex_init(&codec->mutex);
/* allocate CODEC register cache */ if(codec_drv->reg_cache_size && codec_drv->reg_word_size){ reg_size = codec_drv->reg_cache_size * codec_drv->reg_word_size;codec->reg_size = reg_size;/* it is necessary to make a copy of the default register cache
* because in the case of using a compression type that requires
* the default register cache to be marked as __devinitconst the
* kernel might have freed the array by the time we initialize
* the cache.*/ if(codec_drv->reg_cache_default){ codec->reg_def_copy = kmemdup(codec_drv->reg_cache_default，reg_size, GFP_KERNEL);if(!codec->reg_def_copy){ ret =-ENOMEM;goto fail;} } }
。。。。。。/* register any DAIs */ if(num_dai){ ret = snd_soc_register_dais(dev, dai_drv, num_dai);//通过snd_soc_register_dais函数对本Codec的dai进行注册 if(ret < 0)goto fail;}
mutex_lock(&client_mutex);list_add(&codec->list, &codec_list);/*最后，它把codec实例链接到全局链表codec_list中，并且调用snd_soc_instantiate_cards是函数触发Machine驱动进行一次匹配绑定操作 */
snd_soc_instantiate_cards();mutex_unlock(&client_mutex)。。。。。}
好了，在这里我们的codec驱动也分析完了，其实这部分都是与平台无关代码，一般也不需要改动，这部分我们从设备原厂拿到代码后丢上去就可以了，只是我们在写machine device的时候要注意和这里的名字匹配。接下来是asoc的platform驱动：
Platform驱动的主要作用是完成音频数据的管理，最终通过CPU的数字音频接口（DAI）把音频数据传送给Codec进行处理，最终由Codec输出驱动耳机或者是喇叭的音信信号。在具体实现上，ASoC有把Platform驱动分为两个部分：snd_soc_platform_driver和snd_soc_dai_driver。其中，platform_driver负责管理音频数据，把音频数据通过dma或其他操作传送至cpu dai中，dai_driver则主要完成cpu一侧的dai的参数配置，同时也会通过一定的途径把必要的dma等参数与snd_soc_platform_driver进行交互。
snd_soc_platform_driver的注册
通常，ASoC把snd_soc_platform_driver注册为一个系统的platform_driver，不要被这两个想像的术语所迷惑，前者只是针对ASoC子系统的，后者是来自Linux的设备驱动模型。我们要做的就是：
定义一个snd_soc_platform_driver结构的实例；
在platform_driver的probe回调中利用ASoC的API：snd_soc_register_platform()注册上面定义的实例；
实现snd_soc_platform_driver中的各个回调函数；
以kernel3.3中的/sound/soc/samsung/dma.c为例：
[cpp] view plaincopy
1.static struct snd_soc_platform_driver samsung_asoc_platform = { 2..ops = &dma_ops, 3..pcm_new = dma_new, 4..pcm_free = dma_free_dma_buffers, 5.};6.7.static int __devinit samsung_asoc_platform_probe(struct platform_device *pdev)8.{ 9.return snd_soc_register_platform(&pdev->dev, &samsung_asoc_platform);10.} 11.12.static int __devexit samsung_asoc_platform_remove(struct platform_device *pdev)13.{ 14.snd_soc_unregister_platform(&pdev->dev);15.return 0;16.} 17.18.static struct platform_driver asoc_dma_driver = { 19..driver = { 20..name = “samsung-audio”, 21..owner = THIS_MODULE, 22.}, 23.24..probe = samsung_asoc_platform_probe, 25..remove = __devexit_p(samsung_asoc_platform_remove), 26.};27.28.module_platform_driver(asoc_dma_driver);snd_soc_register_platform()该函数用于注册一个snd_soc_platform，只有注册以后，它才可以被Machine驱动使用。它的代码已经清晰地表达了它的实现过程：
为snd_soc_platform实例申请内存；
从platform_device中获得它的名字，用于Machine驱动的匹配工作； 初始化snd_soc_platform的字段；
把snd_soc_platform实例连接到全局链表platform_list中；
调用snd_soc_instantiate_cards，触发声卡的machine、platform、codec、dai等的匹配工作；
cpu的snd_soc_dai driver驱动的注册
dai驱动通常对应cpu的一个或几个I2S/PCM接口，与snd_soc_platform一样，dai驱动也是实现为一个platform driver，实现一个dai驱动大致可以分为以下几个步骤：
定义一个snd_soc_dai_driver结构的实例；
在对应的platform_driver中的probe回调中通过API：snd_soc_register_dai或者snd_soc_register_dais，注册snd_soc_dai实例；
实现snd_soc_dai_driver结构中的probe、suspend等回调；
实现snd_soc_dai_driver结构中的snd_soc_dai_ops字段中的回调函数；
snd_soc_register_dai 这个函数在上一篇介绍codec驱动的博文中已有介绍
具体不再分析，这个驱动也不需要用户做任务修改，所以只要知道它的作用就已经够了。就像电话机一样，我们只要知道电话怎么打就够了，至于它怎么连接我们并不太需要关心。
第五篇：算法总结
算法分析与设计总结报告
71110415 钱玉明
在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。
下面我将谈谈我对这门课程的心得与体会。
一、数学是算法的基础
经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。
①主定理
本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。
②随机算法中的许多定理的运用
在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。
这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。
二、算法的核心是思想
我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。
①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。
动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。
贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。
周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。
回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。
分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。
②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。
这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。
三、算法与应用紧密相关
我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。
这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。
四、对计算模型和NP问题的理解
由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。
首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。
NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。
最后谈谈对这门课程的建议
①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。
②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。
③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。
点击咨询 