正文

本站内容链接2007-07-06 02:43:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/rickone/27336.html

分享到:

您现在访问的是

算法驿站 powered by 编程爱好者网站

这个小站是我修读《信息与计算科学》本科时就自己所学到的所感受的东西留于笔下,开始不叫这名字,后来才慢慢感觉到‘算法’的威力,而‘驿站’是指作者我也是在学习,大家一起学习的这个过程。

有这样一种说法,先不说它的正确与准确性,至少还是有些道理的,就是,程序=数据结构+算法,程序就是一段指令,看看现在的计算机技术,从硬件的描述语言,汇编,高级语言,脚本,其实可以都认为是‘程序’,及程序就是计算机的全部,就算你是做硬件的人,你用CAD吧,你会从逻辑门开始设计吗?可编程逻辑器件,什么Intel8253之类,你做单片机,你会从汇编开始吧,或者是C语言,你不会去做那个片(我国国内好像还不能做'片'),拿到一堆APIs就开始干活,无非是2个8位拼成16位,还不就是做程序,好,你做程序员,就算你做系统程序员,你写个OS之类的,下面也是用别人做好的指令,你不会去设计微指令吧,流水线也不用管,cache也透明,剩下的东西,还不就是编程,做应用程序员,站在XP上干活,站在linux上干活,到你去做的事情,还是编程。我想说的是,‘程序’可以代替一个词‘逻辑’,而逻辑就是计算机的全部,至少当前的冯计算机,不同的只是大家所处的层次不同(越低级的人越少,但是我不同意越赚钱)。

而程序是=数据结构+算法,数据结构是精心地准备好数据,将那些信息以一定的形式一定的逻辑组织在一起,以使算法的效用达到最大,算法是所有程序的核心,可以看成程序本身,也可以这样比,算法是无形的,而程序是有形的,不管你如何实现,算法是发挥最大作用的东西,而程序是算法的某个实例。

做IT这行,只要是做技术的,只要把算法学好,动手能力强,不管做哪一行(计算机行也分很多)都会很吃香,剩下的只是工具的问题,实现的具体环境,熟能生巧嘛,越是高级的工具其实越容易上手,少数可能门槛比较高,但也都没有算法本身重要。

好了不多说了,本文是想把小站的内容做个链接,做个目录,以下是目录。


目录

1 基础算法

排序由浅入深(一)::选择排序
排序由浅入深(二)::交换排序
排序是算法的切入点,这两篇可能也没什么深度,现在看,那些个经典的排序算法,要时刻牢记于心,那会是一种算法设计泛型,比如快排,归并,基数排序,桶排等。

穷举搜索::回溯与深搜
分酒问题-搜索解法
就是一个DFS,图的深度搜索,基础。后面是一个好玩的例子。

贪心算法::启发式搜索
马踏棋盘的贪心算法
当时有些不太清楚,其实贪心和启发式还是有区别的,贪心是一种分阶段决策,和DP很是相同,但是更简单,往往只要从一个有序元组中依次选择决策,或从堆中动态选择,常见的最小支撑树啊,最短路径Dijkstra,都算是贪心,贪心算法现在还没有充要条件可以判别,就是在何时可以贪心。启发式,实际上就是做局部最优选择,可以是在搜索过程中,比如那个马遍历,但他不同于多阶段决策。

分治的实现::递归程序设计
想表述一下‘递归’的思想,分治的思想是整个算法设计的精髓,最简单的二分,二进制,有很多优秀的或者说伟大的算法里都有这些思想的影子,比如FFT,快排等。

最短带权路径问题的解法::Dijkstra & Floyd
两个确定的基本的最短路径算法。

公历历法::星期算法
当时研究出来比较兴奋,也没学初等数论的基础,中国人应该了解一下同余理论,扫扫盲吧。这个算是很简单的,比起证明费马小定理是不是容易很多。

满足任意精度的概率事件发生器
产生任意范围内的等概率随机数
满足任意概率密度函数分布的随机变量生成算法
这三篇的水平只能算是中学对概率理解的水平,当时还没学《概率论》,对随机数的发生,其实现在还不完全了解,应该是用相关度描述的,至于很好的随机数发生器,要到了专门学密码学的时候才会了解到,不知道有没缘了。第三个,其实早有了蒙特卡罗方法,只要有了U[0,1]的随机数,再知道了概率函数的反函数,就可以简单模拟了,但实际中有很多概率函数是积分形式,反函数没有简单形式,就只好单独对待了,比如高斯分布,有一个函数变换的方法和一个蒙特卡罗方法,有时间写一篇吧。

树的计数公式推导
这个叫catalan数,写的时候还不知道这东西,和离散卷积有关系。

CRC循环冗余校验码
好像是计算机网络时学的,后来又学信息论认识到了,一种线性分组码。

模式匹配的KMP算法详解
带通配符*,?的模式匹配

模式匹配基础东西。如果是模式识别,以我现在的数学水平还不够研究。后一篇有BUG,感谢那位网友指出来。

最长递增子序列问题的求解(LIS)
我转来的一篇,重复的东西也不用写了,写得很好。

Euclid算法与RSA
主要是讲如何求解同余方程xa=1(mod b)的Euclid算法。有一位网上朋友联系过我,说用我的代码不能过OJ,他也没发现问题在哪,如果你发现了,请告诉我。

基础算法还缺一些内容,比如非常重要的程序设计泛型DP。

2 中级算法

和基础算法不同,有些算法比较偏,更像是某种数学或某个方面的专门算法。

最小二乘法线性回归
最小二乘算得上一种数学方法吧,用处非常广泛,又何止只能线性回归呢?我们泛涵考试的最后一题就是求L2[0,1]上exp(x)的最佳三次多项式,由于是2范线性空间,恰好就是最小二乘。

幂极数在近似计算上的应用
数学分析2考完时写的,算是我对数值分析的启蒙认识吧,用我们数分老师的话说,那门课就是‘泰勒级数打天下’,连续的东西化成离散的,其实都是相通的,理论数学慢慢向实用靠近了。

博弈与人工智能
最小最大原理与搜索方法
估值函数与优化搜索
置换表与迭代加深
一个暑假突然迷上了人机博弈,写得比较空洞,文章中没有具体代码。当时做了一个黑白棋,后来觉得估值估得好还真不容易,不过至少对一个没学过黑白棋的人是可以轻易下赢的,我让我大堂哥和她走,他的结论是很需要脑筋,经常被我的程序翻盘。听他评价我的程序,真是开心。PS,人机的对弈本质上还是搜索,对弈树的搜索。

了解遗传算法
就是简单的表达了一下,遗传算法是怎么样的,收敛性,收敛速度都没任何表述,还没到那水平。

关于人工神经网络
也是对神经网络非常朴实的认识。下学期有选这门专业课。在我看到的一篇论文里他和遗传算法、模拟退火算法、模糊数学一同被称为先进算法。可能是因为他们都是非常成功的算法,但都有一些理论上遗留的未解决的问题吧。

[转]模拟退火算法求解TSP问题
转载的,写得很通俗易懂,SAA用于组合优化的有效方法。

A*高效搜索算法
搜索方法小结
两篇讲搜索的。A*是一种带启发式高效搜索算法,它的启发式带有某种预见性,因此可看成是智能搜索算法。

牛顿插值算法与实现
多项式插值,牛插是很容易计算机实现的一种算法。

香农编码
照香农老大的说法,编码的平均最优码长是以它的信息熵为下界的,通常情况下,哈夫曼编码也不是最优编码,只能是近似最优,因为编码必须是整数个符号,而哈夫曼编码的缺点是编码长短不一,香农编码是另一种编码,还有扩展码等。

Romberg算法求数值积分的原理与实现
我已经在不止一次课程设计里使用过这个算法了。有着变步长,可控制精度,收敛速度快诸多优点。

Fibonacci数列的计算
比较了几种算法实现的优劣,主要是介绍一种矩阵算法。

Priority Queue - Binary Heap
FibonacciHeap的C++模板实现
优先队列,我最喜欢的数据结构之一。

单纯形法性规划问题求解器
LP问题的有效求解方法,虽然最差情况下是NP的,但LP问题不是NP的,相反有人提出的in P的算法在实际中还不如单纯形法有效。

简单方法算pi和e,计算到小数点后面一万位
FFT乘法和高精运算库(1)
FFT乘法和高精运算库(2)
高精度的算法。

解线性方程组的一些方法
直接消元的,迭代的,和一些解特殊方程的方法。

其它的还有一些OJ上的题解,但是我做得不多,没什么影响力,还有一些就是学工具的,比如VC啊之类,原谅我把这些也滥竽充数放在这里吧。

最后希望这个小站能够带您在算法的广阔空间里自由飞翔!再引一位网友的签名结尾吧:算法如此多娇,引无数天才竞折腰。

阅读(9184) | 评论(15)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册