2010 年度 D-MATH
日時
毎週月曜日 19:00 (暫定、参加者の都合に合わせて柔軟に対応)
概要
計算機を使う上で最低限必要な数学的知識を身につけてもらうために、 M1 の人たちを対象に下記の教科書の演習問題を中心に勉強会を行なっています。
コンピュータのための離散数学入門. C. L. Liu 著, 成嶋 弘/秋山 仁 共訳, 1995, オーム社.
(原書: C. L. Liu. Elements of Discrete Mathematics, 2nd ed. McGraw-Hill, New York, NY, USA. 1985.)
2010年度は M1学生 + TA/RA/スタッフ で行います。
- ゼミ、輪読形式で行います。
- 各節の担当者は、その節の内容に関して参加者から質問があった場合に答えられるように、勉強会の時間までにしっかり準備・予習してきてください。
- 担当者以外の参加者も、事前に予習して、少なくとも「どこが分からないかが分からない」ということがないようにしてきてください。
- 各章の章末に演習問題があります。1週間前までに章末問題の一部を割り当てますので、参加者全員で協力して解いてきてください。勉強会の時間に演習形式で発表してもらいます。
- 担当者・参加者ともに、分からないことがあれば勉強会の時間外でも構いませんので気軽に TA/RA に質問してください。
TA/RA
- ai-a
- katsuhiko-h
- (心優しいスタッフの方々)
参加者
- teruaki-o
- seiji-k
- shuhei-k
- toshikazu-t
- takahiro-t
- kodai-t
- tomoya-m
- yasuhisa-y
- yasuhiro-r
- joseph-i
担当
- 5月13日 (木) 19:00 chap.1 集合と命題
- 担当
- 1.1 序論 (teruaki-o)
- 1.2 集合の組合せ (seiji-k)
- 1.3 有限集合と無限集合 (shuhei-k)
- 1.4 非可算無限集合 (toshikazu-t)
- 1.5 数学的帰納法 (takahiro-t)
- 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)
- 担当
- 5月20日 (木) 19:00 chap.1 と章末演習問題
- 担当
- 1.6 和積の原理 (kodai-t)
- (1.7 はやりません)
- 1.8 命題, 1.9 注意と参照 (tomoya-m)
- keyword:
- 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)
- 章末問題 - 以下の条件を満たすように参加者同士で問題を割り振ること．出来る限り，各自が面白そうだと思った問題を解いてくること．追加で問題を解いてくるのは大歓迎です．
- 1.1 〜 1.5 から1問 ("∋", "∪", "∩" その1) - 1.5 (yasuhiro-r)
- 1.6 〜 1.14 から2問 ("∋", "∪", "∩" その2) - 1.6 (teruaki-o), 1.14 (toshikazu-t)
- 1.15, 1.16, 1.24, 1.54 から1問 (集合の要素の数え上げ) - 1.24 (yoseph-i)
- 1.17 〜 1.23 から1問 (べき集合) - 1.19 (seiji-k)
- 1.25 〜 1.29 から1問 (対角線論法)
- 1.30 〜 1.53, 1.55 から2問 (数学的帰納法)
- 1.56 〜 1.63 から1問 (和積の原理と数え上げ)
- 1.65 〜 1.74 から1問 (陳述と論理式)
- 担当
- 5月27日 (木) テスト期間中につき休み
- 6月3日 (木) 19:00 chap.1 章末演習問題(続), chap.2 計算可能性と形式言語
- chap.1 章末演習問題(続) 担当
- 1.26 (shuhei-k)
- 1.28 (shuhei-k)
- 1.51 (yasuhisa-y)
- 1.53 (takahiro-t)
- 1.57 (kodai-t)
- 1.71 (tomoya-m)
- chap.2 担当
- 2.1 序論, 2.2 ラッセルの逆理と計算不可能性 (yasuhisa-y)
- 2.3 順序集合, 2.4 言語 (yasuhiro-r)
- 2.5 句構造文法 (joseph-i)
- 2.6 文法の型と言語の型, 2.7 注意と文献 (teruaki-o)
- keyword:
- 2.2 ラッセルの逆理(Russell's paradox),異論理的(heterological),仮定(assume),全体集合(universe)
- 2.3 集合は順序づけられていない(unordered),順序対(ordered pair),順序付けられた3つ組(ordered triplet),新しい(new),順序付けれたn組(ordered n-tuple)
- 2.4 列(sequences),文字列(strings),文(sentences),字母系(alphabet),言語(language)
- 2.5 句構造文法(phrase structure grammars),終端記号(terminal),非終端記号(nonterminal),生成規則(production),開始記号(starting symbol),部分(portion),導出(derivation)
- 2.6 タイプ3の文法(type-3 grammar),タイプ2の文法(type-2 grammar),タイプ1の文法(type-1 grammar),タイプ0の文法(type-0 grammar),タイプi(type-i)
- chap.1 章末演習問題(続) 担当
- 6月10日 (木) 19:00 chap.2 章末演習問題
- 担当
- 2.1 (seiji-k)
- 2.2 (yasuhiro-r)
- 2.5 (toshikazu-t)
- 2.7 (kodai-t)
- 2.8 (takahiro-t)
- 2.9 (shuhei-k)
- 2.10 (tomoya-m)
- 2.13 (teruaki-o)
- 2.14 (yasuhisa-y)
- 2.16 (joseph-i)
- 担当
- 6月17日 (木) 19:00 chap.3
- 担当
- 3.1 序論, 3.2 和と積の集合 (seiji-k)
- 3.3 順列 (shuhei-k)
- 3.4 組合せ (toshikazu-t)
- 3.5 順列と組合せの生成 (takahiro-t)
- 3.6 離散型確率 (kodai-t)
- 3.7 条件付確率 (tomoya-m)
- 3.8 情報量と相互情報量, 3.9 注意と文献 (yasuhisa-y)
- keyword:
- 3.2 試行(experiment),積の法則(rule of product),和の法則(rule of sum)
- 3.3 順列,異なる(distinct),区別不能(indistinguishable),区別可能(distinguishable)
- 3.5 辞書式順序(lexicographical order),右(right),左(left)
- 3.6 試行(experiment),互いに排反(mutually exclusive),すべてを網羅している(exhaustive),表(head),裏(tail),側面で立つ(standing on its side),標本空間(sample space),標本(sample),標本点(sample point),離散標本空間(discrete sample space),確率(probability),推定量(guesstimation),事象(event),単一事象(simple event),複合事象(compound event)
- 3.7 条件付確率(conditional probability),相対(relative)
- 3.8 確実な(unerring),2進対称通信路(binary symmetric channel)
- 担当
6月24日 (木) 19:00 chap.3 章末演習問題
- 以下の各問題ブロックについて，指定された問題数を参加者全員で分担して解いてきてください．計20問なので1人2問担当してください
- 3.1 - 3.4 から1問 (3.3 teruaki-o)
- 3.5 - 3.15 から2問 (3.7 seiji-k, 3.8 joseph-i)
- 3.16 - 3.18 から1問 (3.17 shuhei-k)
- 3.19 - 3.39 から5問 (3.20 toshikazu-t, 3.23 takahiro-t, 3.25 kodai-t, 3.36 tomoya-m, 3.39 yasuhisa-y)
7月1日 (木) 19:00 chap.3 章末演習問題(続) & chap.4 関係と関数
- chap.3 章末演習問題(続)担当
- 3.40 - 3.48 から2問 (3.43 yasuhisa-y, 3.48 yasuhiro-r)
- 3.49 - 3.54 から2問 (3.52 takahiro-t, 3.54 kodai-t)
- 3.56 - 3.62 から3問 (3.58 joseph-i, 3.60 shuhei-k, 3.61 toshikazu-t)
- 3.63 - 3.69 から3問 (3.65 teruaki-o, 3.67 seiji-k, 3.69 yasuhiro-r)
- 3.70 - 3.71 から1問 (tomoya-m 3.71)
- (その他，追加で問題を解いてくるのは大歓迎です)
- chap.4 担当
- 4.1 序論 (yasuhiro-r)
- 4.2 データバンクの関係モデル (joseph-i)
7月8日 (木) 10:00 chap.4 関係と関数 (続)
- chap.4 関係と関数 (続)
- 4.3 2項関係の性質 (teruaki-o)
- 4.4 同値関係と分割 (seiji-k)
- 4.5 半順序関係と束 (shuhei-k)
7月15日 (木) 19:00 chap.4 関係と関数 (続) & chap.4 章末演習問題
- chap.4 関係と関数 (続)
- 4.6 鎖と反鎖 (toshikazu-t)
- (4.7 はやりません)
- 4.8 関数と鳩の巣原理, 4.9 注意と文献 (takahiro-t)
- chap.4 章末演習問題 - n は参加者のやる気を表す自然数
- 4.1 - 4.9から 2n 問
7月22日(木) 19:00 chap.4 章末演習問題(続)
- chap.4 章末演習問題(続)
- 4.10 - 4.22から 2n 問
- 4.23 - 4.26から n 問
- 4.27 - 4.30から n 問
- 4.32 - 4.33から n 問
- 4.34 - 4.40から 2n 問
10月7日 (木) 19:00 chap.4 章末演習問題(続) ＆ chap.5 グラフと平面的グラフ
- chap.4 章末演習問題(続)
- 4.41 - 4.54から n 問 (joseph-i)
- chap.5 担当
- 5.1 序論, 5.2 基本的な用語 (kodai-t)
- 5.3 多重グラフと重み付きグラフ, 5.4 道と閉路 (tomoya-m)
- 5.5 重み付きグラフの最短道 (yasuhisa-y)
- 5.6 オイラー道とオイラー閉路 (yasuhiro-r)
- 5.7 ハミルトン道とハミルトン閉路 (joseph-i)
- 5.8 巡回セールスマン問題 (teruaki-o)
- 5.9 グラフの因子 (seiji-k)
- 5.10 平面的グラフ (shuhei-k)
10月14日 (木) 19:00 chap.5 グラフと平面グラフ(続)
10月20日 (水) 19:00 chap.5 章末演習問題
- chap.5 章末演習問題
- 5.1 toshikazu-t
- 5.4 kodai-t
- 5.7 takahiro-t
- 5.14 tomoya-m
- 5.17 seiji-k
- 5.24 teruaki-o
- 5.36 shuhei-k
- 5.46 yasuhisa-y
10月28日 (木) 19:00 chap.6 木と切断集合
- chap.6 木と切断集合
- 6.1 木 (toshikazu-t)
- 6.2 根付き木 (takahiro-t)
- 6.3 根付きの道の長さ (
kodai-tshuhei-k) - 6.4 プレフィクスコード (tomoya-m)
- 6.5 2分探索木 (
yasuhisa-y) - 6.6 全域木と切断集合 (yasuhiro-r)
- 6.7 最小全域木 (joseph-i)
- 6.8 輸送回路網 (teruaki-o)
11月11日 (木) 19:00 chap.6 木と切断集合（続） & chap.6 章末演習問題
- chap.6 章末演習問題
- 6.1 - 6.10 から2問 (takahiro-t, kodai-t)
- 6.11 - 6.13 から1問 (tomoya-m)
- 6.14 - 6.16 から1問 (shuhei-k)
- 6.17 - 6.25 から2問 (seiji-k, yasuhiro-r)
- 6.26 - 6.31 から1〜2問 (joseph-i, teruaki-o)
- 6.32 - 6.42 から1〜2問 (yasuhisa-y)
11月18日 (木) 18:30 chap.7 有限状態機械
- chap.7 有限状態機械
- 7.1 序論 (seiji-k)
- 7.2 有限状態機械, 7.3 物理系のモデルとしての 有限状態機械 (shuhei-k)
- 7.4 同値な機械 (takahiro-t)
- 7.5 言語認識系としての有限状態機械 (kodai-t)
- 7.6 有限状態言語とタイプ3言語 (tomoya-m)
11月25日 (木) 19:00 chap.7 章末演習問題
- chap.6 章末演習問題
- 7.1 - 7.7 から3問 (teruaki-o, seiji-k, shuhei-k)
- 7.8 - 7.10 から1問 (takahiro-t)
- 7.11 - 7.20 から3問 (kodai-t, tomoya-m, yasuhisa-y)
- 7.21 - 7.29 から3問 (yasuhiro-r, joseph-i)
12月2日 (木) 19:00 chap.8 アルゴリズムの解析
- chap.8 アルゴリズムの解析
- 8.1 序論
- 8.2 アルゴリズムの時間計算量
- 8.3 最短道アルゴリズム
- 8.4 問題の時間計算量
- 8.5 扱いやすい問題と扱いにくい問題
- chap.8 章末演習問題
- 8.1 - 8.11 から1人1問ずつ担当すること
随意開催
- 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人で担当を分割すること) スイッチ回路