離散数学入門/2008

概要

計算機を使う上で最低限必要な数学的知識を身につけてもらうために、 M1 の人たちを対象に下記の教科書の演習問題を中心に勉強会を行なっています。

コンピュータのための離散数学入門. C. L. Liu 著, 成嶋 弘/秋山 仁 共訳, 1995, オーム社.

(原書: C. L. Liu. Elements of Discrete Mathematics, 2nd ed. McGraw-Hill, New York, NY, USA. 1985.)

2008 年度 D-MATH

2008年度は M1学生 + TA/RA で行います。

各節の担当者は、勉強会の時間までにその節の内容に関する質問に答えられるように予習してきてください。分からないことがあれば気軽にチュータに質問してください。 担当者以外の人も事前に予習して、少なくとも「どこが分からないかが分からない」ということがないようにしてください。

参加者

• (1)hayato-a, (2)naoya-i, (3)megumi-e, (4)katsumasa-y,(5)emiko-y, (6)zottip, (7)francisco-s, (8)alex-s, (9)abulikemu-a

予定

• 5月12日13:30- kick off
• 5月19日19:00 chap.1 集合と命題
  • 担当:　1.1(1), 1.2(2), 1.3(3), 1.4(4), 1.5(5), 1.6(6)
  • keyword:
    • 1.1　集合(set),要素(elements or members),集合Sは要素aを含む(contains),順列集合(ordered set),空集合(empty set),部分集合(subset),真部分集合(proper subset)
    • 1.2　組み合わせ(combine),和(union),積(intersection),差(difference),補集合(complement set),普遍集合(universe),対称差(symmetric difference),べき集合(power set)
    • 1.3　有限(finite)集合,集合の個数(cardinality),可算無限(countably infinite)集合
    • 1.4　対角線論法(diagonal argument),非可算無限集合
    • 1.5　数学的帰納法(principle of mathematical induction),強数学的帰納法(principle of strong mathematical induction)
    • 1.6　和積の原理(principle of inclusion and exclusion)
    • 1.8　命題(proposition),恒真命題orトートロジー(tautology),矛盾命題(contradiction),真(true),偽(false),同値(equivalent),論理和or離接(disjunction),論理積or合節(conjunction),否定(negation),複合(compound)命題,原子(atomic)命題,(cannot possibly be false),(if p then q),(p implies q),(p if and only if q)　
• 5月26日（テスト週間のため休み）
• 6月2日19:00-
  • 担当:　1.8(7)
  • 演習問題:　1.1(1), 1.8(2), 1.19(3), 1.26(4), 1.32(5), 1.40(6), 1.60(7), 1.71(8)

• 6月9日, 16日 19:00-
  • 担当：　
    • 2.1序論（TA）、2.2ラッセルの逆理と計算不可能性（TA）、2.3順序集合（TA）、2.6文法の型と言語の型（TA）
    • 2.4言語 hayato-a, naoya-i, megumi-e, katsumasa-y,
    • 2.5句構造文法 emiko-ya, patti-z, francisco-s,
    • 演習問題2.2(a)-(g): hayato-a
    • 演習問題2.2(h)-(o): naoya-i
    • 演習問題2.3: megumi-e,
    • 演習問題2.4: katsumasa-y,
    • 演習問題2.5(a)-(e): emiko-ya,
    • 演習問題2.5(f)-(j): patti-z,
    • 演習問題2.6: francisco-s

• 6月23日, 30日 19:00-
• 本文はTAが読み進めますので，担当の例題を解いてください．演習問題は後日指定します．
  • 3.1-3.3(-p.91): 例3.3,例3.7, francisco-s
  • 3.3 (p.92-p.95): 例3.8,例3.9, emiko-ya
  • 3.4(p.95-p.98): 例3.15, abulikemu-a
  • 3.4(p.98-p.101): 例3.19,例3.20, katsumasa-y
  • 3.6(p.105-p.112): 例3.26,例3.27, megumi-e
  • 3.7(p.113-p.116): 例3.31,例3.32, naoya-i
  • 3.8(p.116-p.123): 例3.33,例3.34, hayato-a

• 7月7日、14日 19：00− 第5章　グラフと平面的グラフ
  • 担当：
    • 5.1序論、5.2基本的な用語＋演習問題5.1、演習問題5.10 hayato-a
    • 5.3多重グラフと重み付きグラフ＋例5.1、例5.2＋演習問題5.4 naoya-i
    • 5.4道と閉路、5.5重み付きグラフの最短道＋演習問題5.14、演習問題5.22 megumi-e
    • 5.6オイラー道とオイラー閉路＋例5.3、例5.4、例5.5＋演習問題5.27 francisco-s
    • 5.7ハミルトン道とハミルトン閉路＋例5.6、例5.7、例5.8、例5.9＋演習問題5.30 emiko-ya

• 演習問題5.22は、動的計画法で解くのはふさわしくないですね（右または下に移動しなければならないという制約は、ない）。やはり、やってもらったようにDijkstraのアルゴリズムを用いるのがよいです。

• 7月21日　　（海の日＋都合のため、休み）
• 7月28日　　（テスト週間のため、休み）
• 10月20日19:00 第4章　関係と関数
  • 4.1 序論 hayato-a
  • 4.2 データバンクの関係モデル naoya-i
  • 4.3 二項関係の性質 megumi-e
  • 4.4 同値関係と分割 katsumasa-y
• 10月27日19:00
  • 4.5 半順序関係と束 emiko-y
  • 4.6 鎖と反鎖 zottip
  • 4.8 関数と鳩の巣原理 francisco-s

• 11月4日(Tue) 17:00
  • 演習問題 4.2 abulikemu-a
  • 演習問題 4.12 hayato-a
  • 演習問題 4.13 naoya-i
  • 演習問題 4.33 megumi-e
  • 演習問題 4.39 katsumasa-y
  • 演習問題 4.46 emiko-y

• 11月10日 (Mon) 19:00 第6章 木と切断集合 (TA 担当：東)
  • 6.1 木 zottip
  • 6.2 根付き木 francisco-s megumi-e
  • 6.3 根付き木の道の長さ abulikemu-a ai-a

• 11月17日 (Mon) 19:00 第6章 木と切断集合 (第2回) (TA 担当：東)
  • 6.4 プレフィクスコード hayato-a
  • 6.5 2分探索木 naoya-i

• 11月24日 (祝日) 休み

• 12月1日 (Mon) 19:00 第6章 木と切断集合 (第3回) (TA 担当：東)
  • 6.6 全域木と切断集合 megumi-e francisco-s
  • 6.7 最小全域木 emiko-y

• 12月8日
  • 6.6 全域木と切断集合 残り francisco-s

• 演習問題 - 以下の問題から1人1問自由に選択
  • 演習問題 6.21 francisco-s
  • 演習問題 6.24 hayato-a
  • 演習問題 6.31 emiko-y

• 12月15日
  • 演習問題 - 以下の問題から1人1問自由に選択
    • 演習問題 6.1
    • 演習問題 6.10 naoya-i
    • 演習問題 6.11
    • 演習問題 6.12
    • 演習問題 6.15
    • 演習問題 6.25 megumi-e

• 12月22日 (忘年会) 休み
• 12月29日 (冬季休業中) 休み
• 1月5日
  • 7.1 naoya-i
  • 7.2 erlyn-m
  • 7.3 erlyn-m
  • 7.4 hayato-a
• 1月12日（祝日）休み
• 1月16日 (金)　中止
• 1月19日
  • 7.5 francisco-s
  • 7.6 megumi-e ※7.6はアスタリスクの付いた節ですがやります．
• 1月26日
  • 演習問題 - 7.5 以降の問題から1人1問自由に選択
    • 演習問題 7.6 hayato-a
    • 演習問題 7.8 naoya-i
    • 演習問題 7.9 emiko-y
    • 演習問題 7.13 francisco-s
    • 演習問題 7.16 erlyn-m
    • 演習問題 7.22 megumi-e
• 終了
• 2月2日
• 2月9日
• 2月16日
• 2月23日

以下、基本的に月曜19:00。試験期間前の1週間は休み。

TA/RA

• manab-ki 1, 4
• ai-a 6, 7
• kazuo-h 2, 5
• ikumi-s 3