世界を動かす技術を、日本語で。

コンピュータサイエンスのための数学 (2024)

概要

このコースは 初等離散数学 の基礎を扱い、 計算機科学 に役立つ数学的手法と証明技法に重点を置く。 論理記法、集合、関係、グラフ理論、状態機械、帰納法、背理法などの主要トピックを網羅。 アルゴリズム解析、数論、暗号理論、組合せ論、確率論なども学習対象。 主なリソースとして 講義動画・ノート・問題集・教科書 を提供。 科学・工学分野の学生を対象とした 実践的内容

初等離散数学コース概要

  • 初等離散数学 の体系的学習
  • 計算機科学 分野で有用な数学的ツール・証明技法の習得
  • 論理記法・集合・関係 の基礎理解
  • 初等グラフ理論 の概念整理
  • 状態機械・不変量 の導入
  • 数学的帰納法・背理法 による証明方法
  • 再帰関係・漸近記法 の分析技法
  • アルゴリズムの初歩的解析
  • 初等数論・暗号理論 の基礎
  • 順列・組合せ・計数法 の応用
  • 離散確率論 の概念把握

コース情報

  • トピック一覧

    • アルゴリズムとデータ構造
    • 論理記法、集合、関係、グラフ理論
    • 状態機械、帰納法、背理法
    • 再帰関係、漸近記法、アルゴリズム解析
    • 数論、暗号理論
    • 順列、組合せ、計数法、離散確率
  • 学習リソース

学習対象者と応用分野

  • 科学・工学分野 の学生・エンジニア
  • 計算機科学 の基礎力強化
  • アルゴリズム設計・解析 への応用
  • 暗号理論・数論的手法 の理解深化
  • 確率論的解析 のスキル向上

Hackerたちの意見

講義の動画はここにあるよ: https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer... https://www.youtube.com/playlist?list=PLUl4u3cNGP61VNvICqk2H...

トピックをリストしたページ(プレイリストと同じ): https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer... 講義ノート: https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer... ちょっと変わった部分もあって、最後の講義(「大きな偏差」)は特にそうだね。コース全体には詳しくないけど、状態機械についての講義はすごく良いと思う。不変量について話していて、わかりやすい例(15パズル)を使ってるよ。テキスト(最後の改訂は2018年): https://courses.csail.mit.edu/6.042/spring18/mcs.pdf もし見たことがなければ、そこにある問題はすごく面白いよ。例えば、AとNot(B)についての退屈なブール論理の問題の代わりに、ページ81の問題3.17があるんだけど、これが始まるんだ: 「この問題では、以下の仕様が満たされるかどうかを検討します: 1. ファイルシステムがロックされていない場合、... (a) 新しいメッセージがキューに追加される。 (b) 新しいメッセージがメッセージバッファに送信される。 (c) システムは正常に機能している。逆に、システムが正常に機能している場合、ファイルシステムはロックされていない。」[...] (a) まず、五つの仕様を四つの命題変数を使って命題式に翻訳することから始めてみて。

大きな偏差についても見られて嬉しかったけど、講義ノートでは実際に大きな偏差が何かを定義していないんだよね。独立同分布のランダム変数の和に対するチェルノフ(指数)境界の例は出てくるけど、もちろんその境界は指数形式だし、大きな偏差とは呼んでないんだ。だからちょっとした機会損失だよね、章のタイトルに名前が入ってるのに。こういう境界はコンピュータサイエンスのあちこちで出てくるけど、特に最近は学習理論でよく見かける。

ユニットは独立しているみたいで、どの順番でも進められるらしい。詳しい人、確認してくれない?集合論とかは、通常の形式的な数学の基礎だから、聞いてみた。

世界のトップ大学の講義が無料で受けられるなんて信じられないよね。31時間の深い数学を、分野のトップの人たちから学べるなんて。とはいえ、長い講義のプレイリストについていくのはいつも苦労してる。できるだけ短い動画を探して、早く概念を説明してもらおうとするけど(たぶん深さは欠けてるけど)、結局途中で投げ出しちゃうことも多い。やっぱり、実際に大学に入学することが、教材についていくための本当のモチベーションになるのかな?誰か一人でこういう講義を全部終えた人いる?どうやって一貫性を保って、規律を持ってるの?自分は、courseraやkhanacademyのコースの方がちょっとモチベーションが上がる気がする。締切があるからね。締切に合わせた勉強に慣れてるのかも。もし他にも集中力に苦労してる人がいて、短い講義を探してるなら(深さは同じじゃないかもしれないけど): https://www.youtube.com/@ProfessorDaveExplains/playlists

「世界クラスの教育が無料で、気を散らさない人に提供される。」

そんな風に自己管理するのは本当に難しいよね。自分は、強制的に参加するために入学しないといけないと感じる。自分の弱点だってわかってる。

自分の経験では、courseraやkhan academyのコースは厳格な大学のコースには決して敵わない。代替の説明が必要なときには素晴らしいリソースだけど、単独では成り立たない。長い講義のプレイリストは機能であって、バグじゃないと思う。フルタイムで教育を受けていないと、こういう教材にコミットするのはずっと難しいよね。

いくつかの講義を通して、1回の座学で動画を終えるための数学的なトレーニングや練習が足りないことに気づいたんだ。しばしば、他のサイトで基本を説明してもらうために急いで行く必要があった。1つの講義を数日かけて(必要なら数週間でも)やったこともある。大半の規律は期待値の管理から来てると思う。詰まることを予想して、何かを考え込むのに数分や数日、時には数週間かかることを受け入れることが大事。理解できることとできないことのリストを作って(シンプルなテキストファイルや紙で十分)、数ヶ月続けてやれば、きっとできるようになるよ。

以前のバージョンのこのクラスを受けたことがあって、構造がすごく役に立ったよ。毎日決まった時間と場所で学ぶ時間を作ったら、かなり助けになったけど、やっぱり何週間も触れないこともあったから、苦労はリアルだね :) ちょっと余談だけど、講義がそのコースの中で一番面白い/役に立つ部分だとは思わないな。問題セットとそれを解こうとする時間が、実際には自分が理解していると思っていたアイデアを固めるのに役立った。だから、問題を解くことを強く勧めるよ。講義よりも時間はかかるけど、その分得られるものは大きいから。

数学が大好きで、博士号も取得したし、自己管理もできるけど、それでも動画講義だけで自分で学ぶのは難しいと思う。特に最初はね。なぜか、まず「臨界質量」の知識に達しないといけない気がするし、他の人と一緒にプログラムに参加することや、経験豊富なメンターがいることが重要だと感じてる。経験豊富なメンターがいないと、数学の独学の段階に進むのはすごく難しいと思う。それが鍵だよ。誰かに自分の作業を見てもらって、修正してもらうことが必要なんだ。だから、少なくとも数学の大学院生を見つけて手伝ってもらうのがいいよ。ピアノの先生みたいなもので、ピアノを習ったことがあるなら、先生が絶対に必要だってわかるでしょ。最初から独学する人は、弾けるようにはなるけど、あまり上手くはならないんだ。追記:もう一つの重要な要素は時間だね。線形代数や解析、微積分を流暢に理解したいなら、少なくとも週に10時間はそれに費やす覚悟をしないといけないよ。週に2時間だと、ほんとに表面的で弱い理解しか得られないから。

このコースは、今やってるプロジェクト(Gコードプレビューとプログラム的な3Dモデリングシステムを(Open)PythonSCADで書いてる)にとってすごく助けになったよ。これと一緒にやることをおすすめするのは: https://ocw.mit.edu/courses/6-001-structure-and-interpretati... あと、すごく役に立ったオンラインリソースもいくつかあるよ: - https://mathcs.clarku.edu/~djoyce/java/elements/elements.htm... - https://www.motionmountain.net/ そしてもちろん https://librivox.org/ と https://www.gutenberg.org/ --- なんでかっていうと、父がバージニアの田舎に引退したとき、図書館は古い裁判所の地下にある金属製の書架だけだったから。夏に学校の図書館に行けなかったときのお気に入りの本は、父が働いていた刑務所の塔で見つけたハル・クレメントの『スペース・ラッシュ』と、母が26マイル離れた町のデパートの残り物の本のテーブルから買った短編小説が入った英語の教科書だったんだ。

動画をただ見るだけじゃなくて、LLMを使ってみよう。リンクをLLMに渡して、要約を作ったり、シノプシスを生成したり、クイズを出してもらったりするんだ。講義から学ぶんじゃなくて、問題解決から学ぶんだよ。それに、自分が思ってるよりも頭が悪いと思って、謙虚に始めるのが大事。カバーされている内容の少なくとも50%をすでに知っているコースから始めよう。

この気持ち、めっちゃわかる。大学時代は本当に好きな時期だったな。コンピュータサイエンスのいろんな高度なトピックを学べたし。でも卒業して仕事を始めたら、新しいことを学ぶのがすごく大変になった。教授が課題を採点したり、試験をしたり、話せるクラスメートがいるわけじゃないからね。ちょっと楽しみでオンライン大学に入学しようかなって考えてる。でも、オンラインで、安くて、進んだCSやMLのコースがあって、経験豊富な教授とやりとりできる大学のVennダイアグラムはほぼゼロだと思う。もし誰かおすすめがあったら教えてほしいな。

「実際に大学に入学することが、教材を追いかける本当のモチベーションになるのかも?」ほとんどの人にとって、教材を追いかける本当のモチベーションは、卒業後に得られる給料の上乗せから来るんだよね。君のような謙虚な独学者が、実際のMITの学生よりもずっと苦労しているのは驚きじゃない。だって、実際のMITの学生とは違って、このコースを終えてもMITの学位に近づくことはないから。 >「締め切りを意識した勉強に慣れてるんだと思う。呪いを逆転させて、Xの教材をY日までに終わらなかったら誰かにお金を払うって約束することもできるよね。」おそらく、実際にやったことを示すための証明手段も欲しいだろうし、例えば採点されたテストみたいな。 >「誰かがこういう講義を独学で終えたことある?」どうやって一貫性を保って、規律を持ってるの?卒業後、いくつかの教科書を問題集も含めて隅から隅まで読んだよ。モチベーションは主に好奇心の燃えるようなもの。何も知らないだけじゃなくて、自分が知らないことを知っているって感じるのが耐えられないし、知っていることに基づいて行動するたびにそれを偽っているように感じる。

これらのトピックは面白そうだけど、普通のソフトウェアエンジニアにはほとんど必要ないと思う。プログラミングを始めた頃、実際には数学がほとんど関係ないことに驚いたよ。もちろん、MITの講義はコンピュータサイエンティスト向けで、ソフトウェアエンジニアとはかなり違うってアメリカの大学は考えてるからね。

「平均的なソフトウェアエンジニアには、それがほとんど必要ない。」それは違うよ。全部を深く知る必要はないけど、概念的な理解は「正しい」(仕様に対して)コードを書くためにはすごく必要なんだ。人間は自然にアルゴリズム的な問題解決者だから、与えられた問題に対してアドホックな解決策を見つけることができる。もちろん、ここでは個人の知能に大きく依存するけどね。数学が提供するのは、思考を体系化するための構造と概念で、それを厳密に適用することで問題解決がより機械的になるんだ。だから、数学的な概念を使って問題を厳密に特定し、その要求を満たす「プログラム」を導き出すために数学的論理を使うことを学ぶ。少なくとも集合論、論理学、関係代数の知識は、数学からコンピュータプログラミングへのマッピングを理解するのに大いに役立つよ。以下の本が役に立つかも;1) Nimal Nissankeの「コンピュータ科学者のための入門論理と集合」。必要な基本数学の良い概要と幅広いカバー。2) Jean-Francois Moninの「形式手法の理解」。数学モデルとそれを実装するツールの概要を一気に紹介している。

このコースをLeanで形式化しようと思ってるんだけど、どれくらい難しいかわからない。もし同じことに興味がある人がいたら、ぜひ参加してね! https://github.com/dernett/Lean61200J

これ、すごく面白そうだし、最近始まったCSLibイニシアティブの目標にも関連してるね。今はこれ以外に良い公開リンクはないけど、このLinkedInの投稿があるよ(もしかしたらZulipのタグもあるかも): https://www.linkedin.com/posts/lean-fro_leanlang-cslib-forma...

誰かOpenCoursewareを使ってキャリアチェンジした人いる?MOOCの時代は、すでに教育を受けた自己啓発型や趣味の学習者向けだったんじゃないかって疑ってる。労働者の世代を力づけるって宣伝されてたけどね。否定するつもりはないけど。仕事の合間に量子コンピューティングを進めてるから、数十年後には追いつけると思う。

「コンピュータサイエンスのための数学」っていうコースタイトル、なんかしっくりこない。コンピュータサイエンスは数学の専門的なサブフィールドだと思ってたから。