離散数学入門/2011

概要

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

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

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

2011年度は M1学生 + TA/RA/スタッフ で行います。

• ゼミ、輪読形式で行います。
• 各節の担当者は、その節の内容に関して参加者から質問があった場合に答えられるように、勉強会の時間までにしっかり準備・予習してきてください。
• 担当者以外の参加者も、事前に予習して、少なくとも「どこが分からないかが分からない」ということがないようにしてきてください。
• 各章の章末に演習問題があります。1週間前までに章末問題の一部を割り当てますので、参加者全員で協力して解いてきてください。勉強会の時間に演習形式で発表してもらいます。
• 担当者・参加者ともに、分からないことがあれば勉強会の時間外でも構いませんので気軽に TA/RA に質問してください。

日時

毎週月曜日19:00

TA/RA

• ai-a
• (心優しいM2とDとスタッフの方々)

参加者

• Vianh To (thichinh-t)
• Lis Kanashiro (lis-k)
• 程 飛 (Fei Cheng: fei-c)
• 江崎 大嗣 (hirotsugu-e)
• 柏木 潔 (kiyoshi-k)
• 金川 元信 (motonobu-k)
• 小林 龍 (ryo-ko)
• 酒井 啓道 (hiromichi-s)
• 坂口 慶祐 (keisuke-sa)
• 高橋 弘志 (hiroshi-t)
• 濱口 拓男 (takuo-h)
• 藤野 拓也 (takuya-fu)
• 三谷 亮介 (ryosuke-m)
• 吉川 友也 (yuya-y) (連携講座：コミュニケーション学研究室)
• 澤井 悠 (Yu Sawai: yu-s) (客員講座：言語科学研究室)

担当

• 5月9日 (月) 19:00 chap.1 集合と命題
  • chap.1 担当
    • 1.1 序論 (thichinh-t)
    • 1.2 集合の組合せ (lis-k)
    • 1.3 有限集合と無限集合 (fei-c)
    • 1.4 非可算無限集合 (hirotsugu-e)
    • 1.5 数学的帰納法 (kiyoshi-k)
    • 1.6 和積の原理 (motonobu-k)
    • (1.7 はやりません)
    • 1.8 命題, 1.9 注意と参照 (hiromichi-s)

• 5月16日 (月) 19:00 chap.1 集合と命題
  • chap.1 章末問題　担当者は選択した問題番号を書いておきましょう。
    • 1.1 〜 1.5 から1問 ("∋", "�", "�" その1)(ryo-ko)→ 1.2
    • 1.6 〜 1.14 から2問 ("∋", "�", "�" その2) (keisuke-sa)→ 1.6, 1.11
    • 1.15, 1.16, 1.24, 1.54 から1問 (集合の要素の数え上げ)(hiroshi-t)→1.16
    • 1.17 〜 1.23 から1問 (べき集合)(takuo-h)→1.23
    • 1.25 〜 1.29 から1問 (対角線論法)(takuya-fu)→1.29
    • 1.30 〜 1.53, 1.55 から2問 (数学的帰納法)(ryosuke-m)→1.30,1.33
    • 1.56 〜 1.63 から1問 (和積の原理と数え上げ)(yuya-y)→1.62
    • 1.65 〜 1.74 から1問 (陳述と論理式)(yu-s)→1.72

• 5月23日 (月) 19:00 chap.2 計算可能性と形式言語
  • chap.2 担当
    • 2.1 序論, 2.2 ラッセルの逆理と計算不可能性(thichinh-t)
    • 2.3 順序集合, 2.4 言語(lis-k)
    • 2.5 句構造文法(fei-c)
    • 2.6 文法の型と言語の型, 2.7 注意と文献(hirotsugu-e)

• 5月30日 (月) テスト期間のため休み

• 6月6日 (月) 19:00 chap.2 計算可能性と形式言語
  • chap.2 章末問題　1問を1人が担当．問題の担当者は参加者全員が相談して自主的に決めてください．担当者は選択した問題番号を書いておきましょう．
    • 2.1 〜 2.4 から2問 (ラッセルの逆理，言語の集合記法その1)(kiyoshi-k →2.2, motonobu-k→2.1)
    • 2.5 〜 2.8 から2問 (文法による文の導出)(ryo-ko→2.5, hiromichi-s→2.7)
    • 2.9, 2.11 〜 2.13, 2.17 から2問 (文法の設計)(keisuke-sa→2.11, hiroshi-t→2.13)
    • 2.10, 2.16 から1問 (言語の集合記法その2)(takuo-h)
    • 2.14, 2.15 から1問 (言語の型)(takuya-fu→2.14)

• 6月13日 (月) 19:00 chap.3 順列，組合せと離散的確率
  • chap.3 担当
    • 3.1 序論, 3.2 和と積の集合(ryosuke-m)
    • 3.3 順列(yuya-y)
    • 3.4 組合せ(yu-s)
    • 3.5 順列と組合せの生成(thichinh-t)
    • 3.6 離散型確率(lis-k)
    • 3.7 条件付確率(fei-c)
    • 3.8 情報量と相互情報量, 3.9 注意と文献(hirotsugu-e)

• 6月20日 (月) 19:00 chap.3 順列，組合せと離散的確率
  • chap.3 章末演習問題
    • 3.1 - 3.4 から1問 (和と積の法則，数え上げ)(kiyoshi-k →3.1)
    • 3.5 - 3.15 から2問 (順列・組合せその1)(motonobu-k, ryo-ko)
    • 3.16 - 3.18 から1問 (順列・組合せその2)(hiromichi-s→3.17)
    • 3.19 - 3.39 から5問 (順列・組合せその3)(keisuke-sa→3.19, hiroshi-t→3.20, takuo-h, takuya-fu→3.23, ryosuke-m)

• 6月27日 (月) 19:00 chap.3 順列，組合せと離散的確率
  • chap.3 章末演習問題 (続き)
    • 3.40 - 3.48 から2問 (順列・組合せその4)(yuya-y, yu-s)
    • 3.49 - 3.54 から2問 (順列・組合せその5)(thichinh-t, lis-k)
    • 3.56 - 3.62 から3問 (離散型確率)(fei-c, hirotsugu-e→3.60, kiyoshi-k→3.56)
    • 3.63 - 3.69 から3問 (条件付確率)(motonobu-k→3.68, ryo-ko→3.66, hiromichi-s→3.67)
    • 3.70 - 3.71 から1問 (情報量と相互情報量)(keisuke-sa→3.70)

• 7月4日 (月) 19:00 chap.4 関係と関数
  • chap.4 担当
    • 4.1 序論 (hiroshi-t)
    • 4.2 データバンクの関係モデル (takuo-h)
    • 4.3 2項関係の性質 (takuya-fu)
    • 4.4 同値関係と分割 (ryosuke-m)

• 7月11日 (月) 19:00 chap.4 関係と関数
  • 4.5 半順序関係と束 (yuya-y)
  • 4.6 鎖と反鎖 (yu-s)
  • (4.7 はやりません)
  • 4.8 関数と鳩の巣原理, 4.9 注意と文献 (thichinh-t)

• 7月18日 (月) 19:00 chap.4 関係と関数
  • chap.4 章末演習問題
    • 4.1 - 4.9から2問 (直積，2項関係)
    • 4.10 - 4.14から1問 (2項関係の性質その1)
    • 4.15 - 4.26から3問 (2項関係の性質その2)
    • 4.27 - 4.30, 4.42から1問 (半順序関係と束，鎖と反鎖)
    • 4.32 - 4.33から1問 (関数)
    • 4.34 - 4.41, 4.43 - 4.54から4問 (鳩の巣原理)

• 10月17日 (月) 19:00 chap.5 グラフと平面グラフ
  • chap.5 担当
    • 5.1 序論, 5.2 基本的な用語 (lis-k)
    • 5.3 多重グラフと重み付きグラフ, 5.4 道と閉路 (fei-c)
    • 5.5 重み付きグラフの最短道 (hirotsugu-e)

• 10月24日 (月) 19:00 chap.5 グラフと平面グラフ
  • 5.6 オイラー道とオイラー閉路 (kiyoshi-k)
  • 5.7 ハミルトン道とハミルトン閉路 (motonobu-k)
  • 5.8 巡回セールスマン問題 (ryo-ko)
  • 5.9 グラフの因子 (hiromichi-s)
  • 5.10 平面的グラフ (keisuke-sa)

• 10月31日 (月) 19:00 chap.5 グラフと平面グラフ
  • chap.5 章末演習問題
    • 5.1 - 5.5から1問 (その他) (hiroshi-t)
    • 5.6 - 5.16から2問 (その他) (takuo-h, takuya-fu→5.7)
    • 5.17 - 5.22から1問 (最短距離) (ryosuke-m)
    • 5.23 - 5.37から2問 (オイラー道・閉路，ハミルトン道・閉路) (yuya-y, yu-s)
    • 5.38 - 5.39から1問 (最近傍法) (thichinh-t)
    • 5.40 - 5.43から1問 (因子) (lis-k)
    • 5.44 - 5.47から1問 (平面的グラフ) (fei-c)

• 11月7日 (月) 19:00 chap.6 木と切断集合
  • chap.6 担当
    • 6.1 木(hirotsugu-e)
    • 6.2 根付き木(kiyoshi-k)
    • 6.3 根付きの道の長さ(motonobu-k)
    • 6.4 プレフィクスコード (ryo-ko)
    • 6.5 2分探索木(hiromichi-s)

• 11月14日 (月) 19:00 chap.6 木と切断集合
  • chap.6 担当
    • 6.6 全域木と切断集合(keisuke-sa)
    • 6.7 最小全域木(hiroshi-t)
    • 6.8 輸送回路網 (takuo-h)

• 11月21日 (月) 19:00 chap.6 木と切断集合
  • chap.6 章末演習問題
    • 6.1 - 6.10 から2問 (takuya-fu → 6.4, ryosuke-m)
    • 6.11 - 6.13 から1問 (yuya-y→6.13)
    • 6.14 - 6.16 から1問 (yu-s -> 6.15)
    • 6.17 - 6.25 から2問 (thichinh-t, lis-k)
    • 6.26 - 6.31 から1〜2問 (fei-c)
    • 6.32 - 6.42 から1〜2問 (hirotsugu-e)

• 11月28日 (月) 19:00 テスト期間のため休み

• 12月5日 (月) 19:00 TA不在のため休み

• 12月12日 (月) 19:00 chap.7 有限状態機械
  • chap.7 担当
    • 7.1 序論(kiyoshi-k)
    • 7.2 有限状態機械, 7.3 物理系のモデルとしての 有限状態機械 (ryo-ko)
    • 7.4 同値な機械(hiromichi-s)
    • 7.5 言語認識系としての有限状態機械(keisuke-sa)
    • 7.6 有限状態言語とタイプ3言語 (hiroshi-t)

• 1月23日 (月) 19:00 chap.7 有限状態機械
  • chap.7 章末演習問題
    • 7.1 - 7.7 から3問 (takuo-h, takuya-fu→7.3,yuya-y)
    • 7.8 - 7.10 から1問 (yu-s->7.8)
    • 7.11 - 7.20 から3問 (thichinh-t, lis-k, fei-c)
    • 7.21 - 7.29 から3問 (hirotsugu-e, kiyoshi-k→7.22, ryo-k→7.21)

• 1月30日 (月) 19:00 chap.8 アルゴリズムの解析
  • chap.8 担当
    • 8.1 序論 (hiromichi-s)
    • 8.2 アルゴリズムの時間計算量 (keisuke-sa)
    • 8.3 最短道アルゴリズム (hiroshi-t)
    • 8.4 問題の時間計算量(takuo-h)
    • 8.5 扱いやすい問題と扱いにくい問題(takuya-fu)

• 2月6日 (月) 19:00 chap.8 アルゴリズムの解析
  • chap.8 章末演習問題
    • 8.1 - 8.2 から1問 (ryosuke-m)
    • 8.3 - 8.4 から1問 (yuy-y)
    • 8.5 - 8.6 から1問 (yu-s)
    • 8.7 - 8.8 から1問 (thichinh-t)
    • 8.9 - 8.11 から1問 (lis-k)

• 2月13日 (月) 19:00 (予備日)

• 2月20日 (月) 19:00 (予備日)

• 2月27日 (月) 19:00 (予備日)

• 以下は希望者が居る場合に開催
  • chap.9 離散的数値関数と母関数
    • 9.1 序論
    • 9.2 数値関数の取り扱い
    • 9.3 (2人で担当を分割すること) 数値関数の漸近的性質
    • 9.4 母関数
    • 9.5 組合せの問題
  • chap.10 漸化式と再帰的アルゴリズム
    • 10.1 序論
    • 10.2 漸化式
    • 10.3 定数係数の線形漸化式
    • 10.4 同次解
    • 10.5 特殊解
    • 10.6 一般解
    • 10.7 母関数を用いた方法
    • 10.8 ソーティングアルゴリズム
    • 10.9 行列積のアルゴリズム
  • chap.11 群と環
    • 11.1 序論
    • 11.2 群
    • 11.3 部分群
    • 11.4 生成元とべき元の計算
    • 11.5 剰余類とラグランジュの定理
    • 11.6 (2人で担当を分割すること) 置換群とバーンサイドの定理
    • 11.7 コードと群コード
    • 11.8 同型写像と自己同型写像
    • 11.9 準同型写像と正規部分群
    • 11.10 群，整域，体
    • 11.11 環準同型写像
    • 11.12 多項式環と巡回コード
  • chap.12 ブール代数
    • 12.1 束と代数系
    • 12.2 双対原理
    • 12.3 束により定義される代数系の基本的性質
    • 12.4 分配束と相補束
    • 12.5 ブール束とブール代数
    • 12.6 有限ブール代数の一意性
    • 12.7 ブール関数とブール表現
    • 12.8 命題計算
    • 12.9 ディジタル回路網の設計と制作
    • 12.10 (2人で担当を分割すること) スイッチ回路