CS251: 理論計算機科学における優れたアイデア

• CMUのCS251コースは、宇宙、社会、新しい技術、そしてそれらを理解する私たちの心にとって根本的な要素である計算を厳密に研究することに関するもの。
• 計算を研究するための適切な言語と道具を備えることが重要。
• このコースでは、計算の本質に関する中心的な結果と問いを探究する。

計算の形式化

モジュール 1: 紹介

• 理論計算機科学とは何かを高い視点から説明し、今後扱う内容に対する適切な文脈を設定することが主な目標。
• データを形式的に表現する方法と、計算問題の概念を形式的に定義することから始める。

モジュール 2: 有限オートマトン

• 単純で制約のある計算モデルである決定性有限オートマトン（DFA）を紹介することが目標。
• DFAはそれ自体でも興味深く有用な応用があるが、アルゴリズムの概念を形式的に定義するための第一歩として用いられる。

モジュール 3: 計算の形式化

• あらゆる種類の計算装置に対する標準的な数学モデルであるチューリングマシンの定義を紹介することが主な目標。
• チューリングマシンを厳密に研究することは、ノートPCができることだけでなく、宇宙が計算的にできることとできないことについての洞察を与える。

モジュール 4: 計算の限界

• ほとんどの問題が決定不能であることを証明し、決定不能問題の具体例を示す。
• 対角化と帰着という二つの中核的な技法を用いる。

モジュール 5: 人間の推論の限界

• 数学的推論を数学的に形式化する作業が必要であり、それには「アルゴリズム」または「計算」を形式化することが含まれる。
• 理論計算機科学の言語を用いて、数学の基礎に関する重要な問いに効果的に答える。

計算複雑性

モジュール 6: 時間計算量

• 多くの問題は実際には決定可能だが、最も効率的なアルゴリズムが非常に多くの計算ステップを必要とするなら、その問題は実質的には決定不能である。
• 時間計算量を含むさまざまな資源に対する計算複雑性を研究するが、時間計算量に焦点を当てる。

モジュール 7: グラフ理論

• グラフは、計算機科学で生じる計算問題を抽象化するうえで非常に基本的な役割を果たす。
• グラフ理論に関する膨大な文献を活用して、グラフ問題の計算複雑性をよりよく理解できる。

モジュール 8: P対NP

• NP複雑性クラスを紹介し、計算機科学で最も重要な未解決問題であるP対NP問題について議論する。
• NPに属する多くの自然でよく研究された言語を多項式時間で決定できれば、驚くべき応用が可能になる。

モジュール 9: 乱択アルゴリズム

• ランダム性は、自然をモデル化し分析するために不可欠な概念であり道具でもある。
• 乱択アルゴリズムは、乱数生成器のようなランダム性の源にアクセスできるアルゴリズムであり、非常に小さな誤り確率で誤りを起こす可能性がある。

モジュール 10: 暗号学

• 計算機科学革命によって、暗号学の分野は大きく発展し始めた。
• 計算複雑性の研究は暗号学を完全に革新した。

理論計算機科学のハイライト

モジュール 11: 追加トピック

• 理論計算機科学から選りすぐりのハイライトを紹介する。

GN⁺の意見

• このコースは、計算機科学の理論的側面に対する深い理解を提供し、学生が計算の本質を探究し、複雑性理論や暗号学のような重要なテーマを学べる機会を提供する。
• 特にP対NP問題のような未解決問題に関する議論は、学生に計算機科学の最前線で進んでいる研究への洞察を与える。
• このコースは計算機科学の基礎を築くうえで重要な役割を果たし、理論的背景を備えたソフトウェアエンジニアになるために不可欠な知識を提供する。
• 暗号学モジュールは、現代社会におけるデータセキュリティとプライバシー保護の重要性を強調し、この分野の専門家になるための基礎を築く。
• このコースは、計算機科学分野でキャリアを築こうとする学生が不可欠な理論的背景と問題解決スキルを身につけるのを助けるという点で非常に価値がある。

[quack337]

ああ……大学生のとき、頭を抱えながら苦労した記憶が……
たぶん今でも理解できないだろうけど、それでも頑張って聞いてみないとですね。

[GN⁺]

Hacker Newsの意見

• この授業はさまざまな概念を紹介し、特に問題解決能力の向上に重点を置いている。

  • 授業の進め方としては、毎週新しいテーマについて基本的な定義だけを学生に与え、そのテーマを専門的に扱う過程で3週目に学べるような問題を解くことを求める。
  • このやり方は繰り返し適用され、非常にもどかしいことがあるが、それは意図されたものだ。
  • 常に手の届きにくい問題を解こうと試みることで、与えられた問題について考えるより良い戦略を身につけていく。

• 理論計算機科学は面白いこともあるが、ときには非常に厄介でもある。

• 理論計算機科学の問題の解き方を尋ねるRedditの投稿を見かけたが、それはアイオワ州立大学の COMS 331（Computing Theory）の課題を不正に解こうとする試みだと判明した。

  • 誰も手助けせず、投稿者は投稿を削除した。
  • 問題は興味深そうだったので、短時間で楽しめる挑戦だと思って取り組んでみた。
  • 数学専攻だったが、理論計算機科学の学部課程はすべて履修しており、それから約35年が過ぎて多くを忘れていたとはいえ、その問題は COMS 331 の最初の課題セットから出ていたので、基礎的なことは思い出せるはずだと思っていた。
  • 数日費やしたがまったく進展がなく、その後も何度もその問題を思い出しては数時間から丸一日考えてみたが、やはり解けなかった。

• こうしたアイデアをプログラミングを通して自分で学びたいなら、Tom Stuart の "Understanding Computation From Simple Machines to Impossible Programs" を勧める。

• この授業のより完全な版は YouTube の再生リストで見ることができる。

• 「確率的手法」を含むこの授業の別バージョンもあり、現代的な存在論的（構成的ではない）証明の考え方なしに、トポロジカルな解空間の障害に関する証明を想像することはできない。

• このテーマに関心があるなら、Boaz Barak のウェブサイトと PDF で提供されている教科書を確認できる。

• 理論計算機科学で最も重要な2つのアイデア:

  1. Move to front リストは、最適なリスト順序での探索時間の最大2倍かかることがあるが、静的なリスト順序よりもしばしばはるかに優れている。
  2. ランダム化アルゴリズム（例: クイックソート）は、最悪の場合でも非ランダム化アルゴリズムと同じ時間がかかることが多いが、実際には非ランダム化版よりはるかに高速である。

• 他の分野でこの授業のバージョンはどのようなものになるだろうか。

  • 理論物理学、実験物理学、経済学などにおける「偉大なアイデア」の授業を想像できる。
  • かつて「情報時代の発明」という授業を教えたことがあり、そこでは文字の発明から現代のコンピューティング・インフラに至るまで、文明が私たちの情報時代を再現するために必要なすべての発明とアイデアを扱った。単一分野の授業ではなかったため、より面白かった。

• 大学時代に時間計算量の授業を受けたことを覚えている。教授が無作為に学生を指名して複雑なアルゴリズムの計算量を尋ね、答えが間違っていれば別の学生を指名する方式だった。

• 宇宙の根本的な性質としての計算はどのように理解できるのだろうか。植物や動物はどのように計算を行っているのだろうか。