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

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

2025年7月23日原文(ocw.mit.edu)

概要

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

初等離散数学コース概要

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

コース情報

  • トピック一覧

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

学習対象者と応用分野

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

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マイル離れた町のデパートの残り物の本のテーブルから買った短編小説が入った英語の教科書だったんだ。

Hacker Newsで議論の続きを見る