文档章节

改变计算技术的9个伟大算法

小骏骏
 小骏骏
发布于 2015/04/20 09:31
字数 1336
阅读 46
收藏 0

        

    改变计算技术的9个伟大算法

   

在过去,很多巧妙的计算机算法设计,改变了我们的计算技术。通过操作标准计算机中提供的中间运算符,可以产生很多的高效函数。这些函数导致了计算机程序的复杂性和多样性,这也是今天计算机时代快速发展的重要原因。如下所示,我们列举了一些算法,它们改变了我们的计算机使用。


压缩技术


哈弗曼编码




哈弗曼编码在无损数据压缩中广泛应用。为了找到一种最高效的二进制编码,哈弗曼在1951年提出了根据字符频率排序的二叉树这样的编码方法。这种方法被证 明,是最有效的编码方法。由于这种方法简单、高效,这种方法被用在很多的压缩方法中比如:DEFLATE(PKZIP压缩软件中的算法),以及很多的多媒 体编码包括JPEG和MP3中。


密码学


公共秘钥加密



对于加密算法而言,需要两种不同的秘钥,公共秘钥是用来作为加密的明文或者验证数字签名。私钥则用来解密密文,或生成数字签名。公共秘钥加密使得用户可以在 公共信道中安全传送数据。虽然这种方法于1997年发表,但是由英国政府通讯总部(GCHQ)的James H. Ellis, Clifford Cocks, Malcolm Williamson在1973年设计完成,并且投入使用。


搜索算法


Dijkstra 最短路径算法



这一算法由Dijkstra在1956年完成,这是一个为图设计的搜索算法。它解决了单向图中的最短路径问题,因此,也可以用来生成最短路径树。很多基于图 的算法中,都应用了这样的算法来进行路径规划或是子路径选择。上图展示了在单向图中,利用这样的算法求最短路径的过程。


二分搜索算法



二分搜索算法用来在已经有序的数组中找到关键字的位置。在说明词义的字典中,词的排列基本是有序的。电话本上,记录也都按照人名、地址或是电话号码排序。通过这样的算法,我们可以由人名,很快地在电话本中找到相应的电话以及地址。


排序算法


快速排序



这种算法由Tony Hoare在1960年设计。这个算法本来用于调整待翻译单词的顺序,从而使它们与词典顺序更加一致,方便翻译。这种算法由于在Unix系统中被用作默认排序算法而声名大噪。同时,这种算法由于它在C语言标准库中的函数名“qsort”而得名。


数学方法


Karatsuba快速相乘算法



这种算法用来更快完成相乘的数学操作。由Anatolii Alexeevitch Karatsuba在1962年提出。它减少了乘法中需要操作的数字,并且提供了一个快速的相乘计算方法。这种算法的改进算法是Toom–Cook算法。 然而,对于大数相乘,Schönhage–Strassen 算法则是一种更快速的解决方案。


欧几里得算法(辗转相除)


利用欧几里得算法,可以计算最大公约数。即两个正整数可以被整除的最大数。虽然这种算法只通过减法和比较来找到最大公约数,但是它被应用在了许多高级算法 中。欧几里得被认为是这个算法的发明者,欧几里得的这个算法被认为是欧几里得时期(公元前300年左右)最古老的算法之一。


图形学的发展


Bresenham直线算法


这种算法由Jack Elton Bresenham在1962年,他在IBM工作期间提出。这种算法本来用于在计算机屏幕上画出直线。算法用到的操作非常简单,整数的加法,减法和移位操 作。这在计算机图形学中是非常先进的方法。基于这样的方法,后来算法又有了一系列的拓展,比如:画圆算法等。由于这种算法的高效、快捷,至今在很多硬件中 (比如绘图仪和现代图形卡等)这种算法仍然十分重要并且仍在使用。.


平方根倒数速算法


这种算法提供了一种快速计算平方根的倒数的方法。这种方法在3D图像中广泛应用于确定光线和投影关系,这可能需要每秒上千万次的计算速度。在《雷神之锤三: 竞技场》的源代码中就有这样的算法,可是,直到2002年这种算法才被广泛应用。这个算法使用了一系列的简单操作来解决复杂问题。虽然很多人认为,这种算 法由John Carmack研发,但是,SGI和3dfx早就曾在产品中应用此算法,当时应用的是Gary Tarolli实现的版本。

本文转载自:http://mp.weixin.qq.com/s?__biz=MjM5MDI1ODUyMA==&mid=206000531&idx=1&sn=304a4403a9b948dde364fb025...

小骏骏
粉丝 8
博文 110
码字总数 22428
作品 0
厦门
高级程序员
私信 提问
改变计算技术的 9 个伟大算法

在过去,很多巧妙的计算机算法设计,改变了我们的计算技术。通过操作标准计算机中提供的中间运算符,可以产生很多的高效函数。这些函数导致了计算机程序的复杂性和多样性,这也是今天计算机时...

天天顺利
2015/05/15
38
0
开源中文分词系统--HTTPCWS

HTTPCWS是一款Linux下的基于HTTP协议的开源中文分词系统,采用BSD协议。 这个分词系统是对中国科学院计算技术研究所免费提供的 ICTCLAS 3.0 共享版分词后的结果,再采用逆向最大匹配算法,根...

张宴
2009/08/11
8.9K
0
【开源者行】高校巡回活动 - 中科院站- 12月22日

  由开源社及中国科学院计算技术研究所研究生职业发展协会共同主办的高校巡回宣讲活动——「开源者行」中科院计算所站将在12月22日(周一)晚19:00 - 21:00于中科院计算技术研究所四层报告厅...

fnnn99
2014/12/24
51
0
2018年 九大改变世界的技术趋势

欢迎关注天善智能,我们是专注于商业智能BI,人工智能AI,大数据分析与挖掘领域的垂直社区,学习,问答、求职一站式搞定! 对商业智能BI、大数据分析挖掘、机器学习,python,R等数据领域感兴...

天善智能
2018/05/24
0
0
现在的云计算技术,比如hadoop,和数据挖掘data mining有联系吗?

现在的云计算、大数据技术,比如hadoop,好像涉及数据仓库的知识。比如hive和BI、ETL有联系。 云计算技术还会向数据挖掘和机器学习方向发展吗?data mining有很多算法和技术,今后有没有可能...

文心雕码
2014/07/27
560
2

没有更多内容

加载失败,请刷新页面

加载更多

如何快速为网站选择合适的SSL证书

随着HTTPS普及,越来越多用户开始采用SSL证书,来对HTTP进行加密,升级到HTTPS。但面对各种不同的SSL证书,用户应如何选择?安信SSL证书将为大家讲解: 一、按SSL证书类型选择 DV SSL证书:域...

安信证书
11分钟前
1
0
被嫌弃的eval和with

本文转载于:专业的前端网站➥被嫌弃的eval和with 前面的话   eval和with经常被嫌弃,好像它们的存在就是错误。在CSS中,表格被嫌弃,在网页中只是用表格来展示数据,而不是做布局,都可能被...

前端老手
13分钟前
1
0
Allegro非常实用的快捷键-PCB环境

立题简介: 内容:简单介绍Allegro绘制的PCB环境下的快捷键; 来源:实际使用得出; 作用:对Allegro绘制PCB快捷键进行介绍; PCB环境:Cadence 16.6; 立题详解: 对“allegro”板而言,其在...

demyar
20分钟前
1
0
润乾报表与 ActiveReport JS 功能对比

简介 润乾报表是用于报表制作的大型企业级报表软件,核心特点在于开创性地提出了非线性报表数学模型,采用了革命性的多源关联分片、不规则分组、自由格间运算、行列对称等技术,使得复杂报表...

泡泡糖儿
21分钟前
1
0
仿微信打飞机游戏网页版,基于cocos2d-js游戏引擎,在线试玩,内含源码

早几年研究cocos2d的demo项目,这个是基于cocos2d-js游戏引擎,整个游戏用js编写。 玩法:鼠标拖动飞机移动即可 试玩地址 源码地址 游戏截图: 文件说明 cocos2dx:游戏引擎 res:存放游戏素...

tanghc
24分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部