2012第52周四阴雨

今天上午想挑战完成概要设计,但真正开始写时才发现之前自己很多问题没有考虑到,包括具体的实现方案和思路。下午基本上完成了整个的文字描述,但要让别人理解还有很多流程图要画,想画数据流图,但看看不合适,流程图画了之后自己又思考,感觉很不妥。晚上回去再加班构思下要画的图和要解决的问题。下午支持解决了81审讯机播放光盘问题,主要是更新播放库。协助程真解决码率降低的问题。回去前摘录一下我看到的几篇文章要点:

2012移动应用盘点:乱象丛生 最佳与奇葩共舞

1.唱吧——一直被山寨,从未被超越

一直被模仿,从未被超越,几乎没有一家类似的App有生存的机会,甚至连YY也曾经复制过唱吧,但未成功。曹津曾说过,YY音乐曾开发过类似产品,但没怎么去推广。对于唱吧受欢迎的原因,陈华认为是它迎合了亚洲用户的典型需求,这个需求本来就是有的,只是唱吧把它搬到了手机上,移动互联网的普及,也是唱吧飞快火起来的原因之一。至于公司为什么一直被模仿,从未被超越,原因当然很多。在中国这个山寨成性,相互抄袭的国度,在这个领域,它能做到一枝独秀,绝对是奇迹。(扩展阅读:推广难,盈利更难:移动应用8大痛点剖析

2.啪啪——有声图片,快速风靡

国内首款有声图片应用,让图片会说话的首创。顶着光环出生的,由点点网联合创始人许朝军投资,出生之后,再经李开复等名人在微博上推推,一下就火了,然后就再也没下来,连小S这个鬼马娱乐明星都开始玩啪啪晒女儿照片了,名人效应带来更多关注。火了之后,国内各种媒体也忙着操心啪啪的未来,什么啪啪的潜藏危机啦,啪啪下一步该怎么走啦,如何构建自己的护城河啦。今年,啪啪很忙。(扩展阅读:语音照片应用啪啪:虚火还是传奇?

3.宫爆老奶奶——不花力气推广就火

推出仅仅一个月后便蹿升至App Store中国区付费榜Top 10,随后荣登榜首位置。席卷2012国内休闲游戏市场。在《甩开外包,雄踞榜首:揭开"宫爆老奶奶"成功的秘密》一文中,CSDN采访该团队时,谈到推广方式,他们回答:"都没有做什么推广,就是雷锋网曝光了一下,然后就有眼球了,后来也没花太多经费,莫名其妙被评了一些奖"。火的原因,笔者以为还有这个游戏的名称与动画太具趣味性,有利于传播。宫爆、老奶奶,很有喜感的元素,还没看见游戏是什么样,就有想玩的冲动。

4.图吧导航——工程师神吐槽

图吧导航修改AppStore的应用说明,且不论是别有用心的推广还是个人纯吐槽,图吧导航确实因为这个吐槽火了。下面一段说明文字似乎既充满了无奈但又有点小幽默,极能吸引大家的视线,随后客户端排名跃居付费类应用软件排行榜首位,引来众多网友围观、转载,迅速蹿红,大家都忍不住瞧瞧这神吐槽都在讲什么。以这种方式来传播,成功了。

5.韩寒一个——名人出应用

iOS上,韩寒的《ONE·一个》App上线不到24小时就超过众多热门游戏与应用,冲到了App Store中国区免费排行榜首位。在Android端,在豌豆夹发布以后,5小时内下载量突破20万,首日下载量超过33万。大概也就只有韩少有这个魅力,这就是名人App,估计没有哪款应用不靠刷帮或者其它方式能在这么短时间内获得这么高的下载量。

6.小小帝国——最牛最赚钱的国产Android游戏

每月高达四百万的收入,几百万的安装量,四个默默无闻的开发者,国内开发者开发的Android游戏。这大概是许多国内Android游戏开发者的楷模,投入产出让人艳羡。当然,要想这般成功需要你拿得出出彩的产品,《小小帝国》采用玩家熟悉的塌方系统,界面简单,操作容易,挥砍起来酣畅淋漓。火,总有它的理由。(扩展阅读:《小小帝国》包峰铭:小制作大回报

iOS Top排行榜榜首的常客,曾连续获得iOS平台应用收入冠军,其开发公司Supercell因此也成了游戏领域的一匹黑马,取代EA成为11App Store应用开发收入最高的开发商。Supercell创始人兼CEO称该公司的每日营收实际已经超过50万美金,每日运营成本才6万美元。成功的原因当然很多,专心做游戏,选对渠道等等,都是大家眼里的陈词滥调,但要真正做到并非易事。

8.鳄鱼爱洗澡——迪士尼成功进军移动

这款游戏并非迪士尼发布的第一款移动游戏,但却是迪士尼进军移动成功的典范。下载量曾一度打败《愤怒的小鸟》。无论下载量和收入都超过了之前迪士尼推出的移动游戏之和。当然,对于迪士尼而言。游戏的盈利并不是最重要的,重要的是移动互联网的大势所趋,如何借助这个平台扩大迪士尼的影响力。

9.Pandora——一年扭亏为盈的神话

12Canalys的分析报告中显示,来自GoogleApp Store的一半营收都来自25家开发商,其中有24家游戏,而Pandora是唯一一家上榜的AppPandora的第二季度财报显示,该服务有75%的访问来自移动端,仅仅是移动广告的收入就可以达到2亿2640万美元,Twitter + Facebook + 苹果iAd在移动广告方面的收入的总和也不过2亿7750万美元(扩展阅读:吸金也疯狂:Pandora掀起移动电台应用狂潮)。而在一年前,公司还处于亏损状态,却在一年之内缔造了扭亏为盈并且成功上市的神话。

10.微信——颠覆

微信这个产品的风靡程度已经不需要小编赘述了,从发布之初到今年九月,微信用户数量已突破2亿。张晓龙也因为微信的成功再加上自己不喜欢曝光的性格而被神化。这不仅仅是一个聊天工具,面对微信的迅速壮大,微博也深感亚历山大。连新浪董事长曹国伟也承认微信对微博造成了威胁。但个人认为除了微信的公众平台和圈子对新浪微博能真正产生影响力之外,两家其实并不会形成正面交锋,性质不一样。

但它的横空出世却是真正对米聊和陌陌产生了最直接的影响,另外免费短信、语音通话、免费发送图片却是真真切切对移动运营商造成了威胁。微信,这个应用还推动了二维码的盛行。

11.Facebook——逆流而行,放弃HTML5

靠互联网起家的Facebook,虽是社交巨头,却在移动端步履蹒跚。在整个IT行业都在高唱HTML5凯歌的时候,Facebook却果断放弃HTML5转投iOS NativeFacebook曾经野心很大,想在iOS上构建一个HTML5帝国,但随后又放弃HTML5,这家巨头对HTML5的态度不仅让人产生诸多联想,是Facebook工程师不行?还是HTML5鸡肋?理论上说HTML5可以做出更好的应用。Mozilla也在用HTML5构建移动操作系统,并且在不久将来准备投入市场,维基百科也在利用PhoneGap开发HTML5跨平台应用,但Facbook却放弃这个平台。未来Facebook是否会重拾HTML5?有待时间考证。(扩展阅读:独家爆料:Facebook移动客户端开发揭秘)。

12.Evernote——最擅长公关的App

比起Google当年将服务器搬到中国的水土不服,Evernote的中国之行可谓如鱼得水,背后当然离不开强大的人脉关系。Evernote有前网通CEO田溯宁的保驾护航。另外,Evernote出色的地方还在于,它很会处理App的本地化,比如在中国的应用取了个很诗意的名字"印象笔记",多么具有中国江南Style。(扩展阅读:大象的约会:专访Evernote CEO Phil Libin先生)。

QQ亿级业务演变:从文件、音视频说起

以下为腾讯即通平台部高级工程师王帅的演讲实录:

王帅,腾讯即通平台部高级工程师。重庆大学计算机硕士毕业,073月加入腾讯,一直在QQ后台工作。目前主要负责QQ实时语音、视频、文件等大数据传输业务。

MSN在中国为什么会水土不服?

因为我是做纯技术的,所以我就技术讲得稍微详细一点。QQ传文件还是相对简单的,大家都知道两个QQ传文件之前肯定有消息通道是可以互相发送消息的,我从一个用户本地的IP端口绑定一个可传输数据的端口,对方也绑定一个,他们相互告知对方,接下来他们比较容易建立一条直连的通道,在什么情况下这个通道是建不成的呢?可能是因为防火墙或NAT,那建立不成我们要怎么办?方法很简单,就是给他一台服务器帮他做数据中转,把数据传到服务器上,然后服务器帮他传给对方。

这个可以通过Traceroute来说明一下,说简单一点,我两个用户,一个用户是深圳市电信,另外一个是上海市联通,这个用户给这个用户发一个数据包,发一个Hello,这个数据是怎么走的?首先数据会直接走到北京,在北京做数据交换,再走到上海,为什么会这样?我们再回过来看这儿,因为他们一个是电信、一个是联通,我们知道中国运营商排第一位是电信,第二位是联通,第三位是移动,第四位更难了,排第四位是长宽,我是指专门PC上的。以前是接电信和教育网,现在教育网非常少了,很多学校都已经不是教育网了。

这种情况下,这就是中国特色,为什么叫中国特色呢?接下来我讲先中国特色再讲美国怎么样。中国特色的运营商首先运营商之间没有省级交换节点,可以看到千里迢迢跑到北京做数据交换,交换点是最容易网络拥塞的,跨ISP的用户进行直接连接效果一般比较差,用户连接和自己ISP不相同的服务器效果也会比较差。如果美国不让连接,我会告你,这就是跟中国不一样。

我们会看到中国是工信部管运营商,搞各种扩容,扩容的原因就是各个网用户在增长,目前我们得到的资料是核心交换有四个,北京有两个,广州一个,上海一个,其他省份不管怎么样都要到核心交换点进行数据传输,这样很容易网络拥塞。真正来技术问题了,好的传文件关键点有什么,刚才说了架构点是什么,其实这些MSN用过的同学都知道,他的速度比QQ慢很多,包括大家在微博搜索,其实文件的口碑一直是最好的。刚才说了,MSN这些都做了,它在中国还是水土不服,其实我理解,首先他的技术不畅,但是外企一些流程会比较多,还有外企它的一个资源申请都会非常麻烦,因为他的很多思想还是美国那种思想,我们传文件需要五个关键点:

  • 提高NAT穿透成功率。
  • 压缩传输,比如说白领之间传WordPPT,实际上传输文件是自己大小三分之一,大家认为传一个视频能不能压缩?能不能不损伤质量压缩呢?实际上是不行的,原因是什么?如果能不损伤质量压缩做视频那个软件早已经压缩好了。所以解决视频的这种问题,我们就是通过秒传,数据中转的时候我判断服务器已经有同一种数据,我就直接按一秒传了,其实对发送方来说是快速上传,但是接收方就是慢慢下载,这个就跟中国网络特点有关系,用户上行带宽,只有下行带宽的四分之一甚至更小。
  • 中转直连双通道的保证,什么是双通道的保证呢?说白了就是烧钱给用户服务,为什么烧钱呢?用户本来可以直连传输数据的,这个不花钱的,但是速度比较慢,用服务器速度很快,我们也让他用服务器,烧什么钱呢?运营商烧服务器计价钱跟服务器的费用,还有IDC上网流量,所以要做的好的服务肯定要有资本去支撑的。
  • 最佳接入服务器。说起来很简单,就是AB两个用户,我怎么样选择一台最好的中转服务器。
  • 海量服务器的运营。

海量服务器的管理

对于海量服务器,我们如何进行管理?这里讲了,这些是给用户中转数据用的,比如说这两个用户想传一个文件,我们会给他分一台中转服务器,这里面可能一共两三千台服务器,而且分布,可能分布在十几个省,通过一个配置中心,但配置中心怎么样管理一两千台服务器,配置中心的功能功能很简单,就是管理这些服务器的状态,还有当前负载。什么是当前负载?就是当前它最大提供一千个人视频,现在有八百个人视频了,就是这些信息。首先配置中心是整个集群的运营核心,因为它要管理这些服务器,另外它就要负责中转服务器的配置,各种集群的配制,还要收转服务器当前的状态,有没有死机,这些都做好了,你才能做到这句话,但这话说起来容易做起来却有难度。就是我们都会有一套系统,然后那系统里面都有你名下管理服务器各种信息,有些同时就在服务器里面写上这句话,机器故障直接重启,不用给机器负责人打电话。用这句话,当然不是说死机不管,第二天再去弄,几千人视频不了没关系,同时几万人视频这种是不行的。

比如说这可能字太小了,分辨率不够高,我简单说一下,这个就是我们每个月或者每个季度定期发的一封邮件,我们有接通率测试,由一台机器自动给我们所有员工打一遍电话,接到电话按照语音提示按一下#号就挂掉之后,如果直接挂掉也不会有直接惩罚,但是总监或者领导会找你谈谈话,而且这里有接通率的记录,上次记录,变化情况是怎么样的。

比如说我管理我下面那些人,怎么样提高他们的意识,这次没接到交一百块钱,下一次小组活动用,他做久以后自然有这种意识,但是在初期的时候你需要用手段让他提高这种意识。刚才讲了,你负责服务器多,手机不能关机,刚做有点朝阳,做一年有中年的感觉,做三年以后,所以说海量服务器一定要把服务器管理好才能一直保持这种状态。

接下来就讲一下配置中心到底是怎么样实现管理这些海量服务器的。他主要分两块信息,一块静态信息,它是在数据库里面,是通过可视化配置,程序启动后把数据从数据库刷如共享内存。动态信息就是由各个服务器定时上报而来,为什么分静态跟动态呢?静态是在配置方案开始就要配置好,而且很容易看到的。

静态信息可能包含这些东西,它不会随着你运营过程中改变而改变,比如说他服务器已经有这么多台,每一行代表一台服务器的话,那这些服务器服务场景就是电信到电信,还有一些场景是联通到联通。第二列标识这个服务器服务这种场景下区域是哪些?比如说他服务场景是广东到广东的电信对电信,这台服务器的唯一ID就是这里唯一ID,这里没有什么特别意义,只是区别它。这台服务器就是在汕头、在天津,这台服务器当前状况怎么样,大部分是可用,也有不可用,服务器最大承载多少人同时传文件,或者是音视频这里也有配置。大家可以看到每台服务器是不一样的,比如说差两年的服务器性能差一倍,这些都是静态信息,就是在你代码运行过程中,不会改变的,这个是动态信息,就是由各个服务器真正数据中转服务器上报而来的,它会改变的,比如它会记录最后上报时间是什么。它当前服务器负载是什么。因为这个还是稍微偏专业一些,可以把它理解为一个Excel,刚才讲了这个怎么管理它们,这个管理他们就是把这些信息提供给策略中心来用,策略中心就是来了两个用户,由策略中心配备一台合理的服务器。

音视频处理数据包的延迟

何谓音视频延迟?就是我一个数据包,一个语音包,从这个人开始说话,到我采集完,到我发给对方,到他真正听到,大概延迟现在一般在500毫秒左右,我们上次测在这个毫秒以内,这就要求你服务器的处理时间要非常短,而且不能有抖动,客户端那边也会做闭环测试,什么是闭环测试呢?这些都不要,我只从采集到直接收听花费是20毫秒,就是说一个数据从采集到真正播放需要20毫秒,没有任何干扰情况下。服务器处理数据包延迟非常小,做一个简单操作都会引起一段数据小搏动,比如说写字团这种就要慎用。

刚才讲了设计理念的变革,从瘦服务端到把服务器养成胖子,以前服务器要求流程很简单、很清晰的,很多的协议组合、逻辑判断都由客户端做,服务器主要是保证面对海量请求的稳定。

手持设备的崛起就需要更轻,更快速移植,这里面需要一些逻辑组合、协议控制、核心控制应该放在服务器。这个就是在音视频上新的挑战,以服务器为核心的云引擎设计,说白了就是客户端只是听命于服务器简单单一的角色,所以它能快速在各个不同版本间进行切换,依据网络的场景、FECJitter Buffer大小去调整,还有终端的能力,CPU用的视频编解码都是耗CPU,还有网络抖动、固有的丢包都采用不同的策略。

总结:

  • 海量服务器涉及的核心简单再简单,能力越高,设计的架构越简单,腾讯流传一句话就是优秀的架构师需要普通的程序员,普通的架构师需要优秀的程序员
  • 一切尽在掌握中,对于Demo性能要了若指掌。
  • 腾讯一直强调后台基础能力,后台保护、灰度、柔性。什么时候保护呢?我本来只能提供一万个人用户,突然来了两万个人,我还是能够保证提供一万个人的服务,而不是说一个人的服务都不能提供了。后台保护最经典例子是关于订票系统之类的,它本来设计新闻发布会说我当时设计只支持一万人同时订票,实际上三万人我也没办法,每个人都订不了了,这种是不对的在后台来说,你要有过来保护的能力。灰度就是我们切换一种策略以后,我们不能一刀切,让所有用户都使用,我们一般一步一步放一些用户去用。
  • 全面监控就是你一定有一套监控系统,去看你各个服务器状态。
  • 可运营,大家工作以后才出现的,就是你开发时间乘以20才是运营时间。

提问:策略中心是一台服务器还是什么?

王帅:肯定不可能一台,所有腾讯基础服务部可能有单点故障。什么是单点故障,就是只有一台服务器死了就没有办法提供服务了,这种是不合格的。接下来就讲,他怎么把收集到的这些信息给策略中心去用,我从技术的角度去讲个,可能大部分同学都能听懂,首先得到双方的IP,就能得到二维数组,得到一个IDC,它的服务场景是这些,服务区域是这些,就是说这些机器都可以给当前这两个人去用,接下来还要上报超时的时间,所谓超时就是这台机器死机了,我们可以看到这台晚两分钟,我们可以把这台去掉。得到双方IP,先找到这列,再找到这列的子类,剩下这三台我可以选一台给当前人用。怎么用呢?这就是刚才讲的负载均衡,这里说一下机器故障可以安然睡觉怎么实现呢?因为已经做管理了,死机的服务器不会为用户提供服务了,这就是简单海量服务器的管理,它的原理没有复杂,就是状态上报一种处理。

2013年10个科技预测 3D打印技术将成主流

1. 3D打印技术将成为主流 未来可在家中打印?

印刷术让人类开始走上文明的道路,在整个发展史上印刷虽然大都局限于商业环境,但打印最终还是到达用户家中。随着技术的不断发展,进入21世纪3D打印开始兴起,并有望和打印机一样进入普通用户家中。

这只是一个时间问题,随着技术越来越简化,未来家庭用户可以在家里从网上下载原理图和蓝图,来创建他们自己的产品。这一设想在2013年还很遥远,但在2013年我们将会看到3D打印技术将会得到飞速发展。

3D打印技术的快速发展,也会带来道德和方面的问题。比如在2D打印时代,艳照已经让人恐慌了,但通过3DMax嫁接3D打印出来更会让人抓狂。同时,枪支的模型更容易被传播,许多恐怖分子肯定期待其能制造出极具杀伤性的武器,笔者在这只能期待3D打印千万不要太万能。

2. 增强现实技术将开始应用:Google Glass

增强现实技术是指在现实世界一定时间空间范围内很难体验到的实体信息(视觉信息、声音、味道和触觉等),通过科学技术模拟仿真后再叠加到现实世界被人类感官所感知,从而达到超越现实的感官体验。

这种比较新颖的技术目前已在谷歌产品Google Glass上正式应用,它具有和智能手机一样的功能,可以通过声音控制拍照、视频通话和处理电子邮件等。

虽然正式应用还得等到2014年(2013年谷歌将会推出开发者预览版),但相信在2013年,我们会看到谷歌的竞争对手们会打开闸门,向大众带来更多类似的产品。

4. 大数据将变得更大更好

大数据是大企业在2012年流行语之一。何为大数据,简单地来说,它就是利用通过各种渠道搜集来的相当量的数据,这些渠道包括来自购物详细信息、气候信息、通过智能手机的各种反馈以及物联网等。

搜集到的各类数据不仅能帮助企业进行各类决策,同时也能基于数据挖掘到更多的商机。

2013年随着大数据的进一步应用,普通消费者工作机会将会迅速增加,很多企业将受益于大数据的巨大分析技术,同时标准化的实时分析能力,能够预测未来金融和银行业的主要变化。

5. BYODBring-your-own-device)工作场所将激增

随着Windows 8的发布以及混合云应用程序和服务之间差距不断缩小,那些来自个人的设备可以灵活连接到公司网络,而无需太接近敏感的数据库或网络,因此越来越多的笔记本电脑和平板电脑可以连接到企业网络,可以访问到应用程序、文件和在办公室工作所需要的服务。

未来一年将会有更多的初创公司和中小企业将奉行BYOD政策,让他们的员工可以携带自己的设备办公,这不仅员工比较喜欢,还可以削减公司成本和IT支出。不过也有人指出,BYOD趋势不会进一步在企业流行,因为在移动领域,占市场份额最高的是Android设备,对于平台而言Android后端移动管理服务比较困难,这就使得很多IT安全策略避开了这些设备,所以BYOD将受到一定影响。

9. 物联网将进驻家庭

进入2012年后,物联网的概念被炒的火热。而和家庭相连接的物联网是什么样呢?其实这很容易想象到:普通家庭中的个人物品与网络、近场通信(NFC)和蓝牙相连接。这种连接可以让珠宝随着天气而改变颜色、眼镜显示时间以及让其它物品做出相应的反应。2013年,进驻家庭的物联网将获得快速发展,并成为我们生活紧密相联的一部分。

从商业的角度来看,物联网将越来越能自主决策,而无需人工干预,如打印机直接告诉制造商墨水没有了或当计算机硬件坏了自动联系更换。

计算机科学中最重要的32个算法

英文原址:http://www.risc.jku.at/people/ckoutsch/stuff/e_algorithms.html

奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章,提到他做了一个调查,参与者大多数是计算机科学家,他请这些科学家投票选出最重要的算法,以下是这次调查的结果,按照英文名称字母顺序排序。

 

1.A* 搜索算法——图形搜索算法,从给定起点到给定终点计算出路径。其中使用了一种启发式的估算,为每个节点估算通过该节点的最佳路径,并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此,A*搜索算法是最佳优先搜索的范例。

2.
集束搜索(又名定向搜索,Beam Search——最佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过,集束搜索只能在每个深度中发现最前面的m个最符合条件的节点,m是固定数字——集束的宽度。


3.
二分查找(Binary Search——在线性数组中找特定值的算法,每个步骤去掉一半不符合要求的数据。


4.
分支界定算法(Branch and Bound——在多种最优化问题中寻找特定最优化解决方案的算法,特别是针对离散、组合的最优化。


5.Buchberger
算法——一种数学算法,可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。


6.
数据压缩——采取特定编码方案,使用更少的字节数(或是其他信息承载单元)对信息编码的过程,又叫来源编码。


7.Diffie-Hellman
密钥交换算法——一种加密协议,允许双方在事先不了解对方的情况下,在不安全的通信信道中,共同建立共享密钥。该密钥以后可与一个对称密码一起,加密后续通讯。


8.Dijkstra
算法——针对没有负值权重边的有向图,计算其中的单一起点最短算法。


9.
离散微分算法(Discrete differentiation


10.
动态规划算法(Dynamic Programming——展示互相覆盖的子问题和最优子架构算法


11.
欧几里得算法(Euclidean algorithm——计算两个整数的最大公约数。最古老的算法之一,出现在公元前300前欧几里得的《几何原本》。


12.
期望-最大算法(Expectation-maximization algorithm,又名EM-Training——在统计计算中,期望-最大算法在概率模型中寻找可能性最大的参数估算值,其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算,第一步是计算期望,利用对隐藏变量的现有估计值,计算其最大可能估计值;第二步是最大化,最大化在第一步上求得的最大可能值来计算参数的值。


13.
快速傅里叶变换(Fast Fourier transformFFT——计算离散的傅里叶变换(DFT)及其反转。该算法应用范围很广,从数字信号处理到解决偏微分方程,到快速计算大整数乘积。


14.梯度下降Gradient descent——一种数学上的最优化算法。

15.
哈希算法(Hashing


16.
堆排序(Heaps


17.Karatsuba
乘法——需要完成上千位整数的乘法的系统中使用,比如计算机代数系统和大数程序库,如果使用长乘法,速度太慢。该算法发现于1962年。


18.LLL
算法(Lenstra-Lenstra-Lovasz lattice reduction——以格规约(lattice)基数为输入,输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用:背包加密系统(knapsack)、有特定设置的RSA加密等等。


19.
最大流量算法(Maximum flow——该算法试图从一个流量网络中找到最大的流。它优势被定义为找到这样一个流的值。最大流问题可以看作更复杂的网络流问题的特定情况。最大流与网络中的界面有关,这就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一个流网络中的最大流。


20.
合并排序(Merge Sort


21.
牛顿法(Newton's method——求非线性方程(组)零点的一种重要的迭代法。


22.Q-learning
学习算法——这是一种通过学习动作值函数(action-value function)完成的强化学习算法,函数采取在给定状态的给定动作,并计算出期望的效用价值,在此后遵循固定的策略。Q-leanring的优势是,在不需要环境模型的情况下,可以对比可采纳行动的期望效用。


23.
两次筛法(Quadratic Sieve——现代整数因子分解算法,在实践中,是目前已知第二快的此类算法(仅次于数域筛法Number Field Sieve)。对于110位以下的十位整数,它仍是最快的,而且都认为它比数域筛法更简单。


24.RANSAC——
"RANdom SAmple Consensus"的缩写。该算法根据一系列观察得到的数据,数据中包含异常值,估算一个数学模型的参数值。其基本假设是:数据包含非异化值,也就是能够通过某些模型参数解释的值,异化值就是那些不符合模型的数据点。


25.RSA——
公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用,大家也相信它有足够安全长度的公钥。


26.Schönhage-Strassen
算法——在数学中,Schönhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为:O(N log(N) log(log(N))),该算法使用了傅里叶变换。


27.
单纯型算法(Simplex Algorithm——在数学的优化理论中,单纯型算法是常用的技术,用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组,以及一个等待最大化(或最小化)的固定线性函数。


28.
奇异值分解(Singular value decomposition,简称SVD——在线性代数中,SVD是重要的实数或复数矩阵的分解方法,在信号处理和统计中有多种应用,比如计算矩阵的伪逆矩阵(以求解最小二乘法问题)、解决超定线性系统(overdetermined linear systems)、矩阵逼近、数值天气预报等等。


29.
求解线性方程组(Solving a system of linear equations——线性方程组是数学中最古老的问题,它们有很多应用,比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组,可以使用高斯约当消去法(Gauss-Jordan elimination),或是柯列斯基分解( Cholesky decomposition)。


30.Strukturtensor
算法——应用于模式识别领域,为所有像素找出一种计算方法,看看该像素是否处于同质区域( homogenous region),看看它是否属于边缘,还是是一个顶点。


31.
合并查找算法(Union-find——给定一组元素,该算法常常用来把这些元素分为多个分离的、彼此不重合的组。不相交集(disjoint-set)的数据结构可以跟踪这样的切分方法。合并查找算法可以在此种数据结构上完成两个有用的操作:

原文地址:https://www.cnblogs.com/doit8791/p/2836410.html