发帖
雷达卡
The Real 10 Algorithms that Dominate Our World
什么是算法？What is an algorithm?
Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. Source: Thomas H. Cormen, Chales E. Leiserson (2009), Introduction to Algorithms 3rd edition. （论坛里有此书）
In simple terms, it is possible to say that an algorithm is a sequence of steps which allow to solve a certain task ( Yes, not just computers use algorithms, humans also use them). Now, an algorithm should have three important characteristics to be considered valid:
本帖隐藏的内容
- It should be finite: If your algorithm never ends trying to solve the problem it was designed to solve then it is useless
- It should have well defined instructions: Each step of the algorithm has to be precisely defined; the instructions should be unambiguously specified for each case.
- It should be effective: The algorithm should solve the problem it was designed to solve. And it should be possible to demonstrate that the algorithm converges with just a paper and pencil.
Also it is important to point out that algorithms are not just used in Computing Sciences but are a mathematical entity. In fact the first recorded mathematical algorithms that we have date from 1600 BC — Babylonians develop earliest known algorithms for factorization and finding square roots. So here we have the first problem with the post mentioned before, it treats algorithms as computing entities, but if you take the formal meaning of the word the real top 10 algorithms that rule the world can be found in a book of arithmetic (addition, subtraction, product, etc).
But lets take computing algorithms as our definition of algorithm in this post, so the question remains: Which are the 10 algorithms that rule the world? Here I’ve put together a little list, in no particular order.
1. Merge Sort, Quick Sort and Heap Sort
What is the best algorithm to sort elements? It depends on what you need, and that’s why I put the three more frequently used sort algorithms in the same place; maybe you have a preference for one, but all of them are equally important.
The Merge Sort algorithm is by far one of the most important algorithms that we have today. It is a comparison-based sorting algorithm that uses the divide-and-conquer approach to solve a problem that once was a O(n^2). It was invented by the mathematician John von Neumann in 1945.
Quick Sort is a different approach to the sorting problem, it can use in-place partition algorithms and is a divide and conquer algorithm as well. The problem with this algorithm is that is not a stable sort but is really efficient for sorting RAM-based arrays.
Finally, Heap Sort algorithm uses a priority queue that reduces the search time in the data. This algorithm is also an in-place algorithm and is not stable sort.
These algorithms are a big improvement over other approaches previously used like bubble sort, in fact, it is thanks to them that today we have Data mining, artificial intelligence, link analysis and most of the computing tools in the world including the web.
2. Fourier Transform and Fast Fourier Transform
Our entire digital world uses these simple but really powerful algorithms, which transform signals from their time domain into their frequency domain and vice versa. In fact, you are seeing this post thanks to these algorithms.
The internet, your WiFi, smartphone, phone, computer, router, satellites, almost everything that has a computer inside uses these algorithms in one way or another to function. You can’t get a degree in electronics, computing or telecommunications without studying these important algorithms.
3. Dijkstra’s algorithm
It is not crazy to say that the internet wouldn't work as efficiently as it does if it wasn't because of this algorithm. This graph search algorithm is used in different applications where the problem can be modeled as a graph and you have to find the shortest path between two nodes.
Today, even when we have better solutions to the problem of finding the shortest path, Dijkstra’s algorithm is still used in systems that require stability.
4. RSA algorithm
The internet wouldn't be as important as it is today if it wasn't for cryptography and cyber security. You can think “Sure, security in the era of NSA and other intelligence agencies” or “You have to be really naive to think you are safe in the Internet”; but, people need to feel that they are secure in order to spend their money. After all, you wouldn't input your credit card number on a web service if you know it is not secure.
And from the field of cryptography there is an algorithm that remains one of the most important in the world: the RSA algorithm. Developed by the founders of the company RSA, this algorithm made cryptography available to everybody in the world and helped to shape how cryptography works today. The RSA algorithm is a solution to a simple but complex problem: how to share public keys between independent platforms and final users, in order to allow cryptography (I would argue that it hasn’t been completely solved, I think we need more work in this direction) .
5. Secure Hash Algorithm
This isn't exactly an algorithm but a family of cryptographic hash functions developed by the NIST in the USA. But this family of algorithms is fundamental for the functioning of the World. From your app store, your email, your antivirus, to your browser, etc , all of them use these algorithms (in reality the hash that results from them) to determine if you have downloaded what you wanted or if you have been the victim of a man in the middle attack or maybe a phishing attack.
6. Integer factorization
This is a mathematical algorithm that is heavily used in computing field. Without this algorithm, cryptography would be much more unsafe. The algorithm is a series of steps used to get the prime factorization of a composite number into smaller non-trivial divisors. This is considered an FNP problem, which is an extension of the class NP making the problem really hard to solve.
Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem—for example, the RSA problem. An algorithm that efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure.
The birth of quantum computing is making it easier to solve this problem, opening a completely new field that uses properties of the quantum world to make systems safe.
7. Link Analysis
In the era of internet, the analysis of relationships between different entities is crucial. From search engines and social networks to marketing analysis tools, everybody is trying to find the real structure of the Internet through time.
Link analysis is arguably one of the algorithms with the most myths and confusion in the general public. The problem is that there are different ways to make link analysis and there are also characteristics that make each algorithm a little different (which allows to patent the algorithms) but in their bases they are similar.
The idea behind link analysis is simple, you can represent a graph in a Matrix form making it a eigenvalue problem. This eigenvalues can give you a really good approach of the structure of the graph and the relative importance of each node. The algorithm was developed in 1976 by Gabriel Pinski and Francis Narin.
Who uses this algorithm? Google in its Page Rank, Facebook when it shows you your news feed (this is the reason why Facebook news feed is not an algorithm but the result of one), Google+ and Facebook friend suggestion, LinkedIn suggestions for jobs and contacts, Netflix and Hulu for movies, YouTube for videos, etc. Each one has a different objective and different parameters, but the math behind each remains the same.
Finally, I’d like to say that even thought it seems like Google was the first company to work with this type of algorithms, in 1996 (two years before Google) a little search engine called “RankDex” , founded by Robin Li, was already using this idea for page ranking. Finally Massimo Marchiori, the founder of “HyperSearch”, used an algorithm of page rank based on the relations between single pages. (The two founders are mentioned in the patents of Google).
8. Proportional Integral Derivative Algorithm
Have you ever used an airplane, an automobile, a satellite service or a cellphone network? Have you ever been in a factory or seen a robot? If so, then you have seen this algorithm in action.
Basically, this algorithm uses a control loop feedback mechanism to minimize the error between the desired output signal and the real output signal. It is used wherever you need signal processing or you need an electronic system controlling a mechanical, hydraulic or thermal system using automation.
You could say that without this algorithm our modern civilization wouldn't exist.
9. Data compression algorithms
It is difficult to decide which is the most important compression algorithm because, depending on the application, the algorithm used can vary from zip to mp3 and from JPEG to MPEG-2. But there is something that everybody knows that these algorithms are really important in almost all the structures.
Where could you find them, besides the obvious zipped document? This web page used data compression to be downloaded into your computer, in video games, videos, music, data storage, cloud computing, databases, etc. You could say that everything uses data compression algorithms; they help make systems cheaper and more efficient.
10. Random Number Generation
Today we don’t have a “true” random number generator, but we have some pseudo random number generators that are sufficient. These are used in a large number of applications, from interlink connection, cryptography, secure hash algorithm, video games, artificial intelligence, optimization, to initial conditions for problems, finances, etc.
Finally I just want to add that this list should be taken as an opinion, not a comprehensive list, because there are some algorithms in fields like Machine Learning, Matrix multiplication, categorization, etc, which are important in our world and are not mentioned here.
想要随时跟踪最新好书，请点击头像下方“加关注”。关注成功后，查看这里即可：三步走把千本好书“一网打尽”！。
[原创] 浅析动量因子（附带Matlab/SAS程序及经典文献85篇，免费
[原创] 如何复制对冲基金的成功？（hedge fund replication，附免费文献）
[原创] 对于目前流行的量化投资与smart beta策略的一些看法 （附免费文献10篇）
[原创] 庄子“逍遥”之我见
【经典教材系列】（资料汇总帖，附链接，持续添加中）
【金融教材系列】（资料汇总帖，附链接，持续添加中）
【大数据系列】（资料汇总帖，附链接，持续添加中）
【程序软件系列】（资料汇总帖，附链接，持续添加中）
【大师系列】（资料汇总帖，持续添加中）
【华尔街系列】（资料汇总帖，附链接，持续添加中）
【阿尔法系列】（资料汇总帖，附链接，持续添加中）
【Wiley-Kolb金融系列】（资料汇总帖，附链接，持续添加中）
【国际政经系列】（资料汇总帖，附链接，持续添加中）
【2008金融危机必读系列】（资料汇总帖，附链接，持续添加中）
【畅销书系列】（资料汇总帖，附链接，持续添加中）
【查理芒格系列】Charlie Munger 推荐的20本书！（附链接）
【西蒙系列】跨学科旅行家: 赫伯特 西蒙 （Herbert Simon）资料汇总帖
【弗格森系列】学术界里的明星与怪伽: 尼尔•弗格森（Niall Ferguson）著作汇总帖
美国《时代》杂志2015年度十大最佳非小说类作品（附链接）
《经济学人》2015年度最佳书单（附链接）
《经济学人》2014年度最佳书单（附链接）
亚马逊2015年度最佳商业投资类图书（附链接）
亚马逊2014年度最佳商业投资类图书（附链接）
2015年度英国《金融时报》最佳商业图书书单（附链接）
2014年度英国《金融时报》最佳商业图书书单（附链接）
彭博社: 2015年欧美政商学界精英的精彩阅读瞬间！
好书推荐！扎克伯格的读书年（A Year of Books）
比尔·盖茨2015年度推荐书单：关注事物的工作原理 （附链接）
提升卡
置顶卡
沉默卡
变色卡
抢沙发
千斤顶
显身卡
京公网安备 11010802022788号
