離散数学 – オープン入門書 第4版

 (discrete.openmathbooks.org)
4 ポイント 投稿者 GN⁺ 2024-08-17 | 1件のコメント | WhatsAppで共有
  • 大学初級の離散数学授業ですぐに使える Discrete Mathematics: An Open Introduction 第4版が公開され、無料オンライン教材とPDFで提供
  • 新版は論理と証明から始め、グラフ理論で証明を練習した後、数え上げ・数列へ進む流れを強化
  • 2013年春以降、世界200以上の大学で主教材または補助教材として使われており、AIM Open Textbook Initiative の推薦と Open Textbook Library のレビューを受けている
  • オンラインebook、PDF、印刷版、GitHubソース、Runestone Academy・Edfinity・WeBWorKの宿題セットまで提供され、授業導入のハードルが低い
  • オンライン版は引き続き無料で維持され、第4版は CC BY-NC-SA 4.0 ライセンスにより非商用での利用・印刷・改変が可能

第4版の公開と教材の性格

  • Discrete Mathematics: An Open Introduction 第4版はオンラインと Runestone Academy で利用可能
  • 第3版も引き続き提供されている
  • この教材は、数学・コンピュータサイエンス専攻の1〜2年生向け離散数学科目に合わせた無料のオープンソース教材
  • 探究型学習を含む授業に特に適している
  • 2013年春以降、世界200以上の大学で主教材または補助教材として使用
  • American Institute of Mathematics の Open Textbook Initiative の推薦を受けており、Open Textbook Library にもレビューがある

第4版で変わった構成

  • 新版ではコンテンツの順序を大きく再構成
    • 最初に論理と証明を扱う
    • 続いてグラフ理論で証明を練習する
    • 後半には数え上げと数列を配置
    • 数え上げの単元には新しい確率の応用セクションが含まれる
  • ここ数年、この配列で学生がより良い成果を出してきた経験が反映されている
  • 離散構造への強調も強まった
    • 集合、関数、関係を含む
    • コンピュータサイエンスの学生にとってより有用にしつつ、数学専攻者と数学教員志望者に必要な数学概念の理解も維持

インタラクションと宿題サポート

  • 第4版ではインタラクション要素が増えた
    • Runestone Academyで教材ベースのコースを作成すると、学生に点数を付けられるインタラクティブな練習問題を利用できる
    • 一部のトピック探索用に Sage と Python のインタラクティブコードが含まれる
  • オンライン宿題セットは複数の経路で提供
    • Runestone Academy は無料
    • Edfinity は低価格の選択肢
    • WeBWorKセットは著者に依頼でき、OPLのContribフォルダにも含まれる
  • 誤りや誤字は GitHub issue で提出可能

提供形式とアクセシビリティ

  • 教材全体は無料のインタラクティブオンラインebookとして提供
    • スマートフォンを含むあらゆる画面サイズでうまく動作するよう設計
    • 視覚障害のある学生向けのスクリーンリーダー利用も考慮
    • 例題と練習問題のヒント・解答は隠されており、リンクをクリックすると確認できる
    • 一部の練習問題では答えを入力して確認できるため、正解をすぐ見ずに何度も試せる
  • オフライン利用向けの無料PDFも提供
    • タブレットやコンピュータで読むのに適している
    • 検索と内蔵リンクによるナビゲーションが可能
    • ヒントと解答は練習問題番号をクリックしてアクセスでき、ヒントや解答番号をクリックすると該当の練習問題に戻る
  • 印刷版は CRC Press から出版
  • オンライン版は引き続き無料で提供される

ソース、講義資料、コミュニティ

  • 教材の PreTeXt と LaTeX のソースファイルは GitHub で提供
  • 教材を活用した動画資料もある
  • 授業で教材を使用する講師は講師用資料を依頼できる
  • WeBWorKサーバーへのアクセス権があれば、WeBWorKの宿題セットも依頼可能
  • 離散数学を教える講師向けの Google Group がある

教材内容と授業での活用

  • この教材は University of Northern Colorado の離散数学科目の講義ノートから始まった
  • 同科目は離散数学トピックの入門であると同時に、数学専攻者向けの証明入門科目としての役割も持つ
  • 授業には学生による探究が多く含まれ、教材もそれを支援するように書かれている
  • もともとは数学教員志望者を支援するために設計され、親しみやすく非形式的なトーンを用いている
  • 手順の暗記よりも、含まれる概念の理解を重視
  • コンピュータサイエンス学生向け科目でも使われており、より深い理解を助けることに焦点を置く
  • 4つの主要トピックは、論理、グラフ理論、数え上げ、数列
  • 証明方法としては、背理法、数学的帰納法、組合せ論的証明が含まれる
  • 追加トピックとして母関数と数論も含まれる
  • 主教材としての使用を助ける機能も備える
    • 750個以上の練習問題
    • 解答とヒントがある問題多数
    • 易しい問題からかなり複雑な問題まで含む
    • 宿題に適した問題多数
    • 能動的・探究型学習を支援する Investigate! とプレビュー活動
    • 完全な索引と記号一覧
    • 例題の識別、定義・定理ボックスなど、一貫したページレイアウトと書式

ライセンス

  • Discrete Mathematics: an Open Introduction, 4th edition は CC BY-NC-SA 4.0 ライセンスで配布
  • 非商用目的ではダウンロード、利用、印刷が可能
  • テキストの改変も許可
    • 学生向けのカスタム版を作成できる
    • 使用した部分の著者表示が必要
    • 改変版は互換ライセンスで配布する必要がある
  • GFDLのような類似しているが異なるライセンスのテキストと組み合わせて使う場合は、ライセンス変更の許可を依頼できる

関連記事

1件のコメント

 
GN⁺ 2024-08-17
Hacker Newsのコメント

  • 「正式な」CSの学位なしで独学している立場からすると、離散数学はより高度なトピックへ進み、プログラミングの実践的な問題を解く鍵のように見え、実際に何度も役に立った
    1987年に出たFinkbeiner IIとLindstromの“A Primer of Discrete Mathematics” https://archive.org/details/isbn_0716718154も気に入っている。少し古く、無料ではないが、今でも十分よく、良い練習問題と一部の解答がある
    この本も必ず見てみるつもりで、インタラクティブな練習問題がある、より現代的なアプローチで、しかも完全に無料なので良さそう

    • Kenneth H. RosenのDiscrete Mathematics and It's Applicationsのおかげで、去年の夏にUC BerkeleyのCS70、つまり離散数学と確率の科目でAを取れた
      本はかなり分厚いが、内容は取り組みやすいほうだと思う。自分も独学出身で、30代になって足りない部分を埋めようと、正式な数学／物理の授業を受けているところ
      California Community Collegesも素晴らしいリソースだった。これまで出会った数学の教師はみな驚くほど熱心で、ほとんどの数学の授業に非同期／オンラインのセクションがあり、大人が趣味や自己啓発目的で受講することもよくある
    • こういう数学の本は怖そうに見えたが、Al DoerrとKen LevasseurのApplied Discrete Structures https://discretemath.org/で面白い内容をたくさん見つけられた
      「論理」のセクションに惹かれ、期待を裏切らなかった。Webサイトから無料でダウンロードできる
      「少し古く、残念ながら無料ではない」と言っていたが、探している人がいればAnna's Archiveにもある
    • AOPSのCounting & Probabilityの本は、完全な解説集まで付いた、驚くほど良い離散数学の本だ: https://artofproblemsolving.com/store
    • Graham、Knuth、PatashnikのConcrete Mathematicsも気に入るかもしれない

  • リンク先の資料のように、特に無料の教科書が解答をもっと多く提供してくれるといい。解答が不足している本は、自分にとって循環問題を生む
    自分の解法が正しいかを知るには、概念を本当に理解していなければならない。だが概念を本当に理解しているなら、そもそもその問題を解く必要がない。フィードバックなしでどう学べというのか分からない

    • 著者です。練習問題のうち何パーセントに解答を付けるかは、いつも難しい判断です
      PreTeXtのおかげで本文に簡単に入れられるインタラクティブな練習問題を多く使い、学生が答えを入力すると正しいかどうかのフィードバックを受けられるようにしました。計算問題にはよく合います
      証明ベースまたは理論的な問題については、完全な解説付きの例を十分に用意し、解答のある練習問題もいくつか入れようとしました。同時に、解答のない、よりオープンな問題を望む人にもその機会を残したかったのです
      他の教授が授業でこの本を有用に使うには、成績評価用に採点できる解答なしの問題も重要です。いずれにせよ、この資料が役に立つことを願っています
    • 数学の教科書に解答を載せないのはかなり一般的だ。教授が教科書の問題を授業課題として出したがることもあるし、解答を作る作業そのものが非常に大変だからでもある
      教室の外で外部からのフィードバックなしに教科書で学ぶには、資料をずっと能動的に読む必要がある
      本文中の各記述を非公式の練習問題だと考えればよい。定理であれ説明中の主張であれ、何か命題が出てきたら、読み進める前に自分で証明するか正当化しようとするべきだ
      例えばTheorems 2.3.1と2.3.2は非常によく似ている。2.3.1の証明を理解したなら、2.3.2を自分で試してみることができる。詰まったら、掲載されている証明から数文をヒントのように読み、証明を終えたら本文の証明と比較すればよい
      十分に能動的に読めば、問題を解かなくても内容をかなりよく学べる。数学を学ぶには形式的な問題演習が必要だとよく言われるが、実際にはそうではない。より高いレベルの数学教科書の中には、正式な練習問題や問題がまったくないものも多いが、それでも人々はうまく学んでいる
      もちろん、数学を読むこと自体が別の技術なので、最初から簡単にできると期待すべきではない。マンツーマンの先生がいれば一番いいが、そんな幸運に恵まれる人はまれだ
    • 問題を2通り以上の方法で解けばいい。離散数学のような分野では十分に可能なはずだ
      まず手で解き、その後MathematicaやOR-Toolsのようなツールでモデル化して、同じ解が出るか確認すればいい
      代数や微積分のような、より低いレベルの数学ではさらにうまく機能する。多くの問題でMathematicaのSolve[]関数を使えば、合っているか間違っているか分かる
      アルゴリズムの授業でも同じアプローチが可能だ。テストケースを単純だが確実に解く素朴なプログラムを自分で書き、より洗練されたアルゴリズムの結果と比較すればよい。あるいは他のライブラリのリファレンス実装を使ってもよい。例えば、自作のグラフアルゴリズムの解をNeo4jが返す結果と比較できる
    • 数学の本には、少なくともすべての問題の答えがあるべきで、ほとんどの問題には解法の過程もあるべきだと思う。ただし訓練のために、一部の問題は解法を残さないこともあり得る
      それより少ないなら、教師が参考書として使う程度にしかならない。教師は解法が本当に完全で正しいか確認しなければならないからだ
      数十年前に工学と経済学を学んでいたとき、解説がなければ自分の解法はしばしば不完全で、細部や特定のケースを見落としていただろう
    • 最近は多くの質問でChatGPTがその隙間を意外とうまく埋めてくれる

  • この本を作るのに使われたXMLベースの技術であるPreTeXtにも興味があるかもしれない: https://pretextbook.org/

  • こうした素晴らしい資料を見るとうれしい。特に、教材の著者たちを含め、自分の成果を無料でオンライン公開しているすべての著者に感謝したい。
    彼らの献身は明らかに伝わってくる。こうした無料、またはほぼ無料の資料のおかげで、独学者やリソースの限られた人を含む多くの人が学びを続けられる。
    著者たちの努力が本当に大きく評価されていることを知ってほしい。

  • 少し遅いけれど、Susanna Epp の Discrete mathematics with applications を強くおすすめする。
    似たタイトルの本はいくつかあるが、Epp の本は驚くほどよく書かれている。途方もない手間と細部への注意が注がれた教科書で、それがそのまま伝わってくる。独学にも素晴らしい。
    The Math Sorcerer が以前の版を取り上げた動画もあり、この本に捧げる愛らしい賛歌に近い。本当に惚れ込んでいるようだ: https://www.youtube.com/watch?v=FPr5-X9nZc4

  • 多くの離散数学の教科書と同じく、重根に対する特性根法のセクションでは公式の証明が示されていない。

    • これは特性方程式の形から出てくる。重根が r なら、x^2 - 2r + r^2 を展開して項を合わせ、a = 2r、b = -r^2 を得る。つまり漸化式は a(n) = 2r a(n-1) - r^2 a(n-2) になる。
      r^n で割ると、同値に c(n) = 2c(n-1) - c(n-2)、ここで c(n) = a(n)/r^n である。
      これは差が一定の漸化式 c(n) - c(n-1) = c(n-1) - c(n-2) である。
      したがって c(n) は初期条件で決まる何らかの x、y に対して等差数列 c(n) = x*n + y になる。元の数列は a(n) = c(n) r^n = (x*n + y) r^n である。
    • 存在性と一意性まで含めた完全な証明は非常に長くなるか、教科書の範囲を超える道具が必要になるためなのだと思う。
      たとえば線形代数を使うとかなり簡潔な証明があり、一部を再現すると次のようになる。この証明は仮定した形から始めるのではなく、第一原理から式が導かれるところが気に入っている。
      漸化式 x_{n+1} = a * x_{n-1} + b * x_n で定義される数列 x_n があるとしよう。
      連続する2つの要素からなるベクトル列 [x_0; x_1]、[x_1; x_2]、[x_2; x_3]、... を定義すると、行列/ベクトル積で関係を作れる。
      [x_1; x_2] = [[0 1], [a b]] [x_0; x_1]
      ベクトル列を y_n、行列を M と呼ぶと、y_1 = M * y_0 である。
      次の項は y_2 = M * y_1 = M * (M * y_0) = M^2 * y_0 として得られ、帰納的に y_n = M^n * y_0 となる。
      M の特性多項式は r^2 - br - a = 0 で、根は r_1 = (b - c)/2、r_2 = (b + c)/2、c = √(b^2 + 4a) である。
      したがって対角化により y_n = S * [[r_1^n 0], [0 r_2^n]] * S^(-1) * y_0 が得られる。ここで S は固有ベクトル行列である。
      ここからは、M の固有値の存在性と一意性によって、存在性と一意性の証明を締めくくれる。
    • この話で別のことも思い出した。1990年ごろに受けた離散数学の授業を Knuth の AoCP と比べていた記憶がある。
      Knuth は母関数で再帰数列の閉形式を見つけていて、記憶が正しければ他の方法はほとんど扱っていなかった。私が受けた授業は母関数に触れず、読んだ他の教科書のほとんども同様だった。
      この本はそのトピックを扱っているというので興味深い。「離散数学」は本当にいろいろなものになり得るのだと思う。

  • この無料教科書を書いている人たちが自分の分野を愛しているのと同じくらい、自分も自分の分野を好きでいられたらいいのにと思う。

  • 大学で一番好きだった科目だった。1年生のときに離散数学がとても気に入って、数学と AI をダブルメジャーすることになり、数学は形式検証のために選んだ。

  • 「PDF は8月15日まで提供される予定」とあるが、サイドバーには「PDF coming soon」としか書かれていない :(

    • PDF は本当にもうすぐ出る。コンパイル過程でいくつか問題があり、月曜日までには修正されるはず。
    • お金を払ったわけではないなら、不満を言う権利はない。

  • 暗号学に興味があるなら、離散数学は良い出発点だろうか？解析学よりは確実に良いのでは？

    • 間違いなくそうで、私の離散数学の授業には暗号学が付録のように付いていた。
    • その通り。暗号学で重要な整数論をよく理解するための構成要素になる。