(ZT) some important algorithms

下面是一些比较重要的算法，原文罗 列了32个，但我觉得有很多是数论里的，和计算机的不相干，所以没有选取。下面的这些，有的我们经常在用，有的基本不用。有的很常见，有的很偏。不过了解 一下也是好事。也欢迎你留下你觉得有意义的算法。（注：本篇文章并非翻译，其中的算法描述大部份摘自Wikipedia，因为维基百科描述的很专业了）

A*搜寻算法

俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。

Beam Search

束 搜索(beam search)方法是解决优化问题的一种启发式方法，它是在分枝定界方法基础上发展起来的，它使用启发式方法估计k个最好的路径，仅从这k个路径出发向下 搜索，即每一层只有满意的结点会被保留，其它的结点则被永久抛弃，从而比分枝定界法能大大节省运行时间。束搜索于20 世纪70年代中期首先被应用于人工智能领域,1976 年Lowerre在其称为HARPY的语音识别系统中第一次使用了束搜索方法，他的目标是并行地搜索几个潜在的最优决策路径以减少回溯，并快速地获得一个 解。

二分取中查找算法一 种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者 小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。这种搜索算法每一次比较都使搜索范围缩小一半。

Branch and bound

分支定界(branch and bound)算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

数据压缩

数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度，达到增大数据密度，最终使数据的存储空间减少的技术。数据压缩在文件存储和分布式系统领域有着十分广泛的应用。数据压缩也代表着尺寸媒介容量的增大和网络带宽的扩展。

Diffie�Hellman密钥协商Diffie�Hellman key exchange，简称"D�H"，是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。

Dijkstra's 算法迪 科斯彻算法（Dijkstra）是由荷兰计算机科学家艾兹格・迪科斯彻（Edsger Wybe Dijkstra）发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行 经的距离，迪科斯彻算法可以用来找到两个城市之间的最短路径。

动态规划

动 态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子 问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。比较著名的应用实例有：求解最短路径问题，背包问题，项目 管理，网络流优化等。这里也有一篇文章说得比较详细。

欧几里得算法

在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

最大期望（EM）算法在 统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量 （Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二 步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。

快速傅里叶变换(FFT)快 速傅里叶变换（Fast Fourier Transform，FFT），是离散傅里叶变换的快速算法，也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用，如数字信号处理、计算大 整数乘法、求解偏微分方程等等。本条目只描述各种快速算法，对于离散傅里叶变换的性质和应用，请参见离散傅里叶变换。

哈希函数

HashFunction 是一种从任何一种数据中创建小的数字"指纹"的方法。该函数将数据打乱混合，重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组 成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。

堆排序

Heapsort是指利用堆积树（堆）这种数据结构所设计的一种排序算法。堆积树是一个近似完全二叉树的结构，并同时满足堆积属性：即子结点的键值或索引总是小于（或者大于）它的父结点。

归并排序

Merge sort是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

RANSAC 算法

RANSAC 是"RANdom SAmpleConsensus"的缩写。该算法是用于从一组观测数据中估计数学模型参数的迭代方法，由Fischler and Bolles在1981提出，它是一种非确定性算法，因为它只能以一定的概率得到合理的结果，随着迭代次数的增加，这种概率是增加的。该算法的基本假设是 观测数据集中存在"inliers"（那些对模型参数估计起到支持作用的点）和"outliers"（不符合模型的点），并且这组观测数据受到噪声影响。 RANSAC 假设给定一组"inliers"数据就能够得到最优的符合这组点的模型。

RSA加密演算法

这是一个公钥加密算法，也是世界上第一个适合用来做签名的算法。今天的RSA已经专利失效，其被广泛地用于电子商务加密，大家都相信，只要密钥足够长，这个算法就会是安全的

并查集Union-find

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

Viterbi algorithm

寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states)


BTY:
关于这个世界上的算法，你可以看看Wikipedia的这个网页：http://en.wikipedia.org/wiki/List_of_algorithms

关于排序算法，你可以看看本站的这几篇文章《一个显示排序过程的Python脚本》、《一个排序算法比较的网站》

matlab syms

>>syms x
>>syms y
>> y=diff(0.25*3^x*exp(-3.56*x*(1-x)))


y =
(3^x*exp((89*x*(x - 1))/25)*((178*x)/25 - 89/25))/4 + (3^x*exp((89*x*(x - 1))/25)*log(3))/4


>> solve('-(178*x)/25 + 89/25-log(3)=0','x')

ans = 1/2 - (25*log(3))/178


>> x=1/2 - (25*log(3))/178

x = 0.3457



***OR***

>> solve('y=0','y','x')

% if x has only one solution, the value can be seen from the "Workspace"
% However, if it has more than one solution, i still do not know how to look into % the construction of syms......

backup: interview summary

谷歌笔试：
1.
n支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系，存储在一个二维数组w[n][n] 中，w[i][j]
的值代表编号为i，j的队伍中更强的一支 所以w[i][j]=i 或者j，现在给出它们的出场顺序，并存储在数组order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一轮比赛就是 4对3， 5对8。。。。。。
胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，
下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4对5,直至出现第一名
编程实现，给出二维数组w，一维数组order 和 用于输出比赛名次的数组result[n]，求出result

2.题目说的比较花哨，根据我的理解，本质上就是有n个长为m+1的字符串，如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误

百度面试：

3.
用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x次天平 最多可以从y个小球中找出较轻的那个，求y与x的关系式
4.有一个很大很大的输入流，大到没有存储器可以将其存储下来，而且只输入一次，如何从这个输入流中随机取得m个记录
5.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度

网易有道笔试：
6. 求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是
这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度
7.求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法

discussion can be found @:
http://topic.csdn.net/u/20100930/13/9f10c56c-9545-488e-9b53-edffc9b6761d.html

==========

GOOGLE今天晚上的笔试题，刚参加回来.

第一题比较简单，检测同一个平面上的两个矩形是否重合

第二题是，给定一个随机函数，对一个数组进行随机排列，保证所有可能的排列出现的概率相等，也就是n!分之一

第三题就是约瑟夫问题的最优解法~Knuth具体数学上有，不过我忘记了，自己没推导出来，就写了个模拟

discussion can be found @:
http://topic.csdn.net/u/20101018/23/75b6dc53-610f-401e-b8ae-5aebee5cabe8.html

==========

雅虎：
1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。

2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3

搜狐：

3.四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））

创新工场：

4.求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}

微软：
5.一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。

discussion can be found @:
http://topic.csdn.net/u/20101021/14/7fdbcd52-3ee6-42ce-b48e-8fb56c4418da.html

==========

雅虎：
1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。

2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3

搜狐：

3.四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））

创新工场：

4.求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}

微软：
5.一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。

discussion can be found @:
http://topic.csdn.net/u/20101021/14/7fdbcd52-3ee6-42ce-b48e-8fb56c4418da.html

sth. about usrp in gnuradio

On Thu, Jul 21, 2005 at 05:48:33PM +0530, Arora_Amit wrote:
> Hi all,
>
> We are working on USRP. Please can any let us know what the
> factors or on what basis the audio_decimation, if_freq, usrp_decim.

These values are choosen so that the sample rates through the
processing path "make sense".  The USRP can sample and decimate at
particular rates.  The audio sink/source can sample at particular
rates.  We generally pick ratios such that they are related by simple
integer factors and that the signals of interest have appropriate
bandwidth at various points in the signal processing chain.

The API for using and controlling the usrp is documented in
usrp/host/lib/usrp_basic.h and usrp_standard.h

> It will be help if we can get what the following mention programs does:

> 1.    usrp_fft_simple.py

Does the same thing as usrp_fft only with less gui cruft.
(Plots Fast Fourier Transform of samples received from USRP.)

> 2.    benchmark_usb.py

An unreliable program to detemine maximum bandwidth of USB

>From the comment at the top of the file:

  Benchmark the USB/USRP throughput.  Finds the maximum full-duplex speed
  the USRP/USB combination can sustain without errors.

> 3.    usrp_oscope.py

Digital oscilloscope that uses a USRP as the source of samples.

> 4.    dbs_debug.py

Program to assist in debugging the DBS_RX daughterboard.

The DBS_RX daughterboard is a receive-only daughterboard that covers
800 MHz to 2400 MHz.

> 5.    nbfm_ptt_quick_and_dirty.py

Removed from CVS.  See nbfm_ptt.py  Narrow Band FM "Push to Talk" (wakie-talkie)

> 6.     usrp_rx_cfile.py

Read samples from the USRP and write to file formatted as binary
single-precision complex values.

> 7.    dbs_fft.py

Removed from CVS.

> 8.    nbfm_rcv.py

Narrow Band FM receiver.


If you haven't already, I suggest that you spend some time with:

  http://www.gnu.org/software/gnuradio/doc/exploring-gnuradio.html
  http://www.gnu.org/software/gnuradio/doc/howto-write-a-block.html


Also, there are online docs for the C++ guts:

  http://www.gnu.org/software/gnuradio/doc/index.html

matlab log

log: Natural logarithm
Syntax: Y = log(X)
Description:
The log function operates element-wise on arrays. Its domain includes
complex and negative numbers, which may lead to unexpected results if
used unintentionally.
Y = log(X) returns the natural logarithm of the elements of X. For
complex or negative , where , the complex logarithm is returned.
log(z) = log(abs(z)) + i*atan2(y,x)
Examples
The statement abs(log(-1)) is a clever way to generate .
ans =
3.1416

CS Conference Rankings: System Technology area

Rank 1:

SIGCOMM: ACM Conf on Comm Architectures, Protocols & Apps
INFOCOM: Annual Joint Conf IEEE Comp & Comm Soc
SPAA: Symp on Parallel Algms and Architecture
PODC: ACM Symp on Principles of Distributed Computing
PPoPP: Principles and Practice of Parallel Programming
RTSS: Real Time Systems Symp
SOSP: ACM SIGOPS Symp on OS Principles
SOSDI: Usenix Symp on OS Design and Implementation
CCS: ACM Conf on Comp and Communications Security
IEEE Symposium on Security and Privacy
MOBICOM: ACM Intl Conf on Mobile Computing and Networking
USENIX Conf on Internet Tech and Sys
ICNP: Intl Conf on Network Protocols
PACT: Intl Conf on Parallel Arch and Compil Tech
RTAS: IEEE Real-Time and Embedded Technology and Applications Symposium
ICDCS: IEEE Intl Conf on Distributed Comp Systems

Rank 2:

CC: Compiler Construction
IPDPS: Intl Parallel and Dist Processing Symp
IC3N: Intl Conf on Comp Comm and Networks
ICPP: Intl Conf on Parallel Processing
SRDS: Symp on Reliable Distributed Systems
MPPOI: Massively Par Proc Using Opt Interconns
ASAP: Intl Conf on Apps for Specific Array Processors
Euro-Par: European Conf. on Parallel Computing
Fast Software Encryption
Usenix Security Symposium
European Symposium on Research in Computer Security
WCW: Web Caching Workshop
LCN: IEEE Annual Conference on Local Computer Networks
IPCCC: IEEE Intl Phoenix Conf on Comp & Communications
CCC: Cluster Computing Conference
ICC: Intl Conf on Comm
WCNC: IEEE Wireless Communications and Networking Conference
CSFW: IEEE Computer Security Foundations Workshop

Rank 3:

MPCS: Intl. Conf. on Massively Parallel Computing Systems
GLOBECOM: Global Comm
ICCC: Intl Conf on Comp Communication
NOMS: IEEE Network Operations and Management Symp
CONPAR: Intl Conf on Vector and Parallel Processing
VAPP: Vector and Parallel Processing
ICPADS: Intl Conf. on Parallel and Distributed Systems
Public Key Cryptosystems
Annual Workshop on Selected Areas in Cryptography
Australasia Conference on Information Security and Privacy
Int. Conf on Inofrm and Comm. Security
Financial Cryptography
Workshop on Information Hiding
Smart Card Research and Advanced Application Conference
ICON: Intl Conf on Networks
NCC: Nat Conf Comm
IN: IEEE Intell Network Workshop
Softcomm: Conf on Software in Tcomms and Comp Networks
INET: Internet Society Conf
Workshop on Security and Privacy in E-commerce

Un-ranked:

PARCO: Parallel Computing
SE: Intl Conf on Systems Engineering (**)
PDSECA: workshop on Parallel and Distributed Scientific and
Engineering Computing with Applications
CACS: Computer Audit, Control and Security Conference
SREIS: Symposium on Requirements Engineering for Information Security
SAFECOMP: International Conference on Computer Safety, Reliability and Security
IREJVM: Workshop on Intermediate Representation Engineering for the
Java Virtual Machine
EC: ACM Conference on Electronic Commerce
EWSPT: European Workshop on Software Process Technology
HotOS: Workshop on Hot Topics in Operating Systems
HPTS: High Performance Transaction Systems
Hybrid Systems
ICEIS: International Conference on Enterprise Information Systems
IOPADS: I/O in Parallel and Distributed Systems
IRREGULAR: Workshop on Parallel Algorithms for Irregularly Structured Problems
KiVS: Kommunikation in Verteilten Systemen
LCR: Languages, Compilers, and Run-Time Systems for Scalable Computers
MCS: Multiple Classifier Systems
MSS: Symposium on Mass Storage Systems
NGITS: Next Generation Information Technologies and Systems
OOIS: Object Oriented Information Systems
SCM: System Configuration Management
Security Protocols Workshop
SIGOPS European Workshop
SPDP: Symposium on Parallel and Distributed Processing
TreDS: Trends in Distributed Systems
USENIX Technical Conference
VISUAL: Visual Information and Information Systems
FoDS: Foundations of Distributed Systems: Design and Verification of
Protocols conference
RV: Post-CAV Workshop on Runtime Verification
ICAIS: International ICSC-NAISO Congress on Autonomous Intelligent Systems
ITiCSE: Conference on Integrating Technology into Computer Science Education
CSCS: CyberSystems and Computer Science Conference
AUIC: Australasian User Interface Conference
ITI: Meeting of Researchers in Computer Science, Information Systems
Research & Statistics
European Conference on Parallel Processing
RODLICS: Wses International Conference on Robotics, Distance Learning
& Intelligent Communication Systems
International Conference On Multimedia, Internet & Video Technologies
PaCT: Parallel Computing Technologies workshop
PPAM: International Conference on Parallel Processing and Applied Mathematics
International Conference On Information Networks, Systems And Technologies
AmiRE: Conference on Autonomous Minirobots for Research and Edutainment
DSN: The International Conference on Dependable Systems and Networks
IHW: Information Hiding Workshop
GTVMT: International Workshop on Graph Transformation and Visual
Modeling Techniques

basic python math calculation in gnuradio

/gnuradio3.2.2/gr-wxgui/src/python/common.py

####################
# Shared Functions
#####################
import numpy
import math

"""
# Python is a general purpose programming language.
It is interpreted and dynamically typed and is very
suited for interactive work and quick prototyping,
while being powerful enough to write large applications in.
# NumPy is a Python extension module, written mostly in C,
that defines the numerical array and matrix types
and basic operations on them.
"""

def get_exp(num):
"""
Get the exponent of the number in base 10.
@param num the floating point number
@return the exponent as an integer
"""
if num == 0: return 0
return int(math.floor(math.log10(abs(num))))

def get_clean_num(num):
"""
Get the closest clean number match to num with bases 1, 2, 5.
@param num the number
@return the closest number
"""
if num == 0: return 0
sign = num > 0 and 1 or -1
exp = get_exp(num)
nums = numpy.array((1, 2, 5, 10))*(10**exp)
return sign*nums[numpy.argmin(numpy.abs(nums - abs(num)))]
#numpy.argmin: Return the indices of the minimum values along an axis.

def get_clean_incr(num):
"""
Get the next higher clean number with bases 1, 2, 5.
@param num the number
@return the next higher number
"""
num = get_clean_num(num)
exp = get_exp(num)
coeff = int(round(num/10**exp))
return {
-5: -2,
-2: -1,
-1: -.5,
1: 2,
2: 5,
5: 10,
}[coeff]*(10**exp)

def get_clean_decr(num):
"""
Get the next lower clean number with bases 1, 2, 5.
@param num the number
@return the next lower number
"""
num = get_clean_num(num)
exp = get_exp(num)
coeff = int(round(num/10**exp))
return {
-5: -10,
-2: -5,
-1: -2,
1: .5,
2: 1,
5: 2,
}[coeff]*(10**exp)

def get_min_max(samples):
"""
Get the minimum and maximum bounds for an array of samples.
@param samples the array of real values
@return a tuple of min, max
"""
scale_factor = 3
mean = numpy.average(samples)
rms = numpy.max([scale_factor*((numpy.sum((samples-mean)**2)/len(samples))**.5),
.1])
min = mean - rms
max = mean + rms
return min, max