1.2「Stanford Algorithms」Why Stud

Hi, my name's Tim Roughgarden.

I'm a professor here at Stanford University.

And I'd like to welcome you to this first course on the Design and Analysis of Algorithms.

Now, I imagine many of you are already clear on your reasons for taking this course.

But let me begin by justifying this course's existence.

And giving you some reasons why you should be highly motivated to learn about algorithms.

So what is an algorithm anyways? Basically it's a set of well defined rules, a recipe in effect for solving some computational problem.

Maybe you have a bunch of numbers and you want to rearrange them so that they're in sorted order.

Maybe you have a roadmap and an origin and a destination And you want to compute the shortest path from that origin to that destination.

May be you face a number of different tasks that need to be completed by certain deadlines and you ant to know in what order you should accomplish the task.

So that you complete them all by their respective deadlines.

So why study algorithms? Well first of all, understanding the basics of algorithms and the related field of data structures is essential for doing serious work in pretty much any branch of computer science.

This is the reason why here at Stanford, this course is required for every single degree that the department offers.

The bachelors degree the masters degree and also the PHD.

To give you a few examples routing and communication networks piggybacks on classical shortest path algorithms.

The effectiveness of public key cryptography relies on that of number-theoretic algorithms.

Computer graphics needs the computational primitives supplied by geometric algorithms.

Database indices rely on balanced search tree data structures.

Computational biology uses dynamic programming algorithms to measure genome similarity.

And the list goes on.

Second, algorithms play a key role in modern technological innovation.

To give just one obvious example, search engines use a tapestry of algorithms to efficiently compute the relevance of various webpages to it's given search query.

The most famous such algorithm is the page rank algorithm currently in use by Google.

Indeed in a December 2010 report to the United States White House, the President's counsel of advisers on science and technology argued that in many areas performance gains due to improvements in algorithms have vastly exceeded event he dramatic performance gains due to increased processor speeds.

Third, although this is outside of the score, the scope of this course.

Algorithms are increasingly being used to provide a novel lens on processes outside of computer science and technology.

For example, the study of quantum computation has provided a new Computational viewpoint on quantum mechanics.

Price fluctuations in economic markets can be fruitfully viewed as an algorthmic process and even evolution can be usefully thought of as a surprisingly effect search algorthim.

The last two reasons for studying algorthims might sound flippant but both have more than a grain of truth to them.

I don't know about you, but back when I was a student, my favorite classes were always the challenging ones that, after I struggled through them, left me feeling a few IQ points smarter than when I started.

I hope this course provides a similar experience for many of you.

Finally, I hope that by the end of the course I'll have converted some of you to agree with me that the design and analysis of algorithms is simply fun.

It's an endeavor that requires a rare blend of precision and creativity.

It can certainly be frustrating at times, but it's also highly addictive.

So let's descend from these lofty generalities and get much more concrete.

And let's remember that we've all been learning about and using algorithims since we were little kids.

嗨，我叫Tim Roughgarden。

我是斯坦福大学的教授。

我也欢迎您参加有关算法设计和分析的第一门课程。

现在，我想你们中的许多人已经很清楚您选择此课程的原因。

但是，让我首先证明该课程的存在。

并为您提供一些为什么您应该非常有动力学习算法的原因。

那么，什么是算法？基本上，这是一组定义明确的规则，实际上是解决某些计算问题的诀窍。

也许您有一堆数字，并且想要重新排列它们，以便它们按排序顺序排列。

也许您有一个路线图，一个起点和一个目的地，并且您想计算从该起点到该目的地的最短路径。

可能是您面临需要在一定期限内完成的许多不同任务，并且您想知道应该以什么顺序完成任务。

这样您就可以在各自的截止日期之前完成所有任务。

那为什么要研究算法呢？首先，了解算法的基础知识和数据结构的相关领域对于在计算机科学的几乎所有分支中进行认真的工作都至关重要。

这就是为什么在斯坦福大学，本系提供的每个学位课程都需要该课程的原因。

学士学位，硕士学位以及PHD。

为了给您提供一些示例，说明路由和通信网络在经典的最短路径算法上的搭载。

公钥密码学的有效性依赖于数论算法。

计算机图形学需要几何算法提供的计算原语。

数据库索引依赖于平衡的搜索树数据结构。

计算生物学使用动态编程算法来测量基因组相似性。

而这样的例子不胜枚举。

其次，算法在现代技术创新中起着关键作用。

仅举一个显而易见的例子，搜索引擎使用一系列算法来有效地计算各种网页与其给定搜索查询的相关性。

最著名的算法是Google当前使用的页面排名算法。

的确，在2010年12月提交给美国白宫的报告中，总统的科学和技术顾问顾问认为，在许多领域，由于算法改进而导致的性能提升远远超过了由于处理器速度提高而带来的显着性能提升。

第三，尽管这不在分数之内，但本课程的范围。

越来越多地使用算法来提供计算机科学和技术之外的流程的新颖视角。

例如，量子计算的研究为量子力学提供了新的计算观点。

可以将经济市场中的价格波动视为一个算法过程，甚至可以将演变有效地视为令人惊讶的效果搜索算法。

研究算法的最后两个理由听起来可能有些愚蠢，但它们都具有不小的真理。

我不了解您，但是回到我还是学生的那一刻起，我最喜欢的课程总是充满挑战性，在我努力学习之后，让我觉得自己的智商要比刚开始时聪明一些。

我希望本课程为您提供类似的体验。

最后，我希望到本课程结束时，我会转换一些人的观点，使我同意算法的设计和分析很有趣。

这项工作需要将精确度和创造力进行罕见的融合。

有时它肯定会令人沮丧，但它也很容易上瘾。

因此，让我们从这些崇高的概括中衍生出更多细节。

而且请记住，我们从小就一直在学习和使用算法。