計算は普遍的かつ基本的な概念である

計算は普遍的かつ基本的な概念である ティム・ラフガーデンは、 deceptively simple な質問から始めます。「コンピューターができないことは何か？」それに答えるために、彼は1936年、実際のコンピューターが存在する10年前に、アラン・チューリングが難解な数学的問題を解決する副産物として計算機科学の基礎を築いた時代に私たちを連れ戻します。チューリングの論文は、彼にちなんで名付けられた理論上の機械を導入し、驚くべきことを証明しました。それは、どれだけの時間や計算能力を費やしても、どんなアルゴリズムでも決して解決できない問題が存在するということです。プログラムが最終的に停止するかどうかを問う停止性問題は、どんなコンピューターの手にも永遠に届かないものです。この基礎から、ラフガーデンはより微妙な質問に移行します。コンピューターが解決できる問題の中で、それらを迅速に解決できるものはどれでしょうか？彼は、すべての可能な解を調べることを避けることができる巧妙なトリックであるアルゴリズムのショートカットを紹介します。あなたの電話の地図アプリケーションは、考えられるすべての経路をチェックすることなく最短経路を見つけるために、ダイクストラアルゴリズムに基づいています。カラツバの乗算法は、私たち全員が学んだ小学校の方法よりも優れています。これらのショートカットはほとんど魔法のように見え、自然な希望を生み出します。おそらく、このようなショートカットはすべての問題に存在するでしょう。その希望は、巡回セールスマン問題に打ち砕かれます。最短経路ルーティングとほぼ同じように見えますが、TSPは高速アルゴリズムを見つけるためのあらゆる試みを抵抗してきました。ラフガーデンは、このパズルがコンピュータサイエンスの最も驚くべき発見の一つであるNP完全性の理論につながった経緯を説明します。数千もの一見無関係な問題（スケジューリング、パズル解決、ネットワーク最適化）が、同じ根本的な課題の偽装されたバージョンであることが判明します。誰かがそのうちの1つに対して高速なアルゴリズムを見つけた場合、すべてが簡単になります。もしそのうちの1つが本当に難しいなら、すべてが難しいのです。これにより、P対NP問題、つまりコンピュータサイエンスにおける最も重要な未解決の問題であり、数学における偉大な未解決問題の一つに到達します。ラフガーデンは、ヒルベルト、ゲーデル、フォン・ノイマンのような人物を通してその歴史をたどり、アルゴリズムが達成できること、そしてその限界に焦点を当てた2つの別々の研究の流れが、この単一の質問に収束したことを示しています。このコースは、その答えが暗号、人工知能、量子コンピューティング、そして計算そのものについての私たちの理解に何を意味する可能性があるかを検証して締めくくられます。コンピュータサイエンスや数学の予備知識は一切必要ありません。以下の講義を視聴したり、章のインデックスを参照したり、YouTubeで視聴したりできます。ティム・ラフガーデンティム・ラフガーデンは、高等研究所の数学科の教授です。以前はコロンビア大学のコンピュータサイエンス学部で7年間、スタンフォード大学で15年間勤務しました。彼の主な関心は、コンピュータサイエンスと経済学の関係、そしてアルゴリズムの設計、分析、限界にあります。彼は、『Twenty Lectures on Algorithmic Game Theory』、『Beyond the Worst-Case Analysis of Algorithms』、および『Algorithms Illuminated』シリーズ、ならびに多数の研究論文の著者です。彼の業績は、ACMグレース・マレー・ホッパー賞やゲーデル賞など、理論計算機科学におけるいくつかの主要な賞で認められています。中断したところから再開計算ティム・ラフガーデン intro計算とその限界計算ティム・ラフガーデン 01 コンピューターができないことはありますか？計算ティム・ラフガーデン 02 アルゴリズムは複雑さをどのように出し抜くか計算ティム・ラフガーデン 03 簡単な問題、難しい問題計算ティム・ラフガーデン 04 私たちが生きるかもしれない2つの世界計算ティム・ラフガーデン 05 AI、量子コンピューティング、そしてその先