概要
計算機を使う上で最低限必要な数学的知識を身につけてもらうために、 M1 の人たちを対象に下記の教科書の演習問題を中心に勉強会を行なっています。
コンピュータのための離散数学入門. C. L. Liu 著, 成嶋 弘/秋山 仁 共訳, 1995, オーム社.
(原書: C. L. Liu. Elements of Discrete Mathematics, 2nd ed. McGraw-Hill, New York, NY, USA. 1985.)
期間
例年9月前には終わらせる予定で行なっていますが、実際には11月くらい3月までかかっています。
2004 年度
2004年度は M1学生 4人 + 新保, 浅原 + TA (高橋，藤田，東）で行ないました。
05/07 (金) 第 1 章 集合と命題 (担当: 新保)
- 宿題
- 演習問題 1.10, 1.32, 1.43, 1.57, 1.65, 1.72
05/17 (月) 第 2 章 計算可能性と形式言語(担当: 浅原)
- 宿題
- 演習問題 2.7, 2.10(a), 2.10(b), 2.17(a)
05/21 (金) 第 3 章 順列, 組合せと離散的確率 (担当: 新保)
- 宿題
- 演習問題 3.5, 3.18, 3.57, 3.62, 3.69
05/28 (金) 第 4 章 関係と関数 (担当: 浅原)
- 宿題
- 演習問題 4.10, 4.25, 4.32, 4.36, 4.42
06/21 (月) 第 5 章 グラフと平面的グラフ(担当: 新保)
- 宿題
- 演習問題 5.6, 5.21, 5.23, 5.38
11/09 (火) 第 6 章 木と切断集合(担当: 新保)
:宿題:演習問題 6.2, 6.13(b), 6.17, 6.27, 6.33
第 7 章 有限状態機械(担当: 高橋（て）)
- 宿題
- 演習問題 7.3, 7.8, 7.9, 7.20, 7.22
11/15 (月) 第 8 章 アルゴリズムの解析 (担当: 高橋（て）)
- 宿題
- 演習問題 8.5, 8.7
第 9 章 離散的数値関数と母関数 (担当: 藤田)
- 宿題
- 演習問題 9.1, 9.3, 9.13, 9.16, 9.27
第 10 章 漸化式と再帰的アルゴリズム (担当: 藤田)
- 演習
- 演習問題 10.1, 10.2
- 宿題
- 演習問題 10.3, 10.25, 10.26
第 11 章 群と環 (担当: 東)
第 12 章 ブール代数 (担当: 東)
参加人数
2003年度は M1学生 9人 + 宮本, 新保, 浅原 で行ないました。
コンピュータのための離散数学入門 (オーム社) - 正誤表
Ch. 3
- 正誤表 (文責 新保)
ページ 行 誤 正 103 ↓4-5 初めて減少する項の2つの前の項の添字 初めて減少する項の添字 104 ↓4-5 1236 / 1246 1236 / 1245 / 1246 (1245 が欠落) 104 ↑6 可能な最大値 取り得る最大値 110 ↓9 ?sum_{i=0}^?infty 2^{-2i+1} ?sum_{i=0}^{?infty}2^{-(2i+1)} 110 ↑4 (例3.27) 0番目から32番目のバッファに入れられる 0個から32個のバッファを占有する 110 ↑2 (例3.27) i番目のバッファが 全32個のバッファのうちi個が 111 ↓2 (例3.27) 16番目までのバッファ たかだか16個のバッファ 111 ↓2-3 (例3.27) 奇数番目のバッファがすべて満たされているという事象 一杯になったバッファの数が奇数個であるという事象
Ch. 4
- 正誤表 (文責 新保)
ページ 行 誤 正 168 ↓7 (例4.5) 順序対を名づけられている 順序対でラベルづけされている 168 ↑5-6 (例4.7) どの90人の客も どの90人を選んでも
Ch. 5
- 正誤表 (文責 新保)
ページ 行 誤 正 193 ↑3 最短距離である必要はない 最短距離とは限らない 202 ↓4 {000, 001, ..., 1} {000, 001, ..., 111} 204 ↑4 他の場合は さもなくば 209 ↓7 w(j,p) w(j,k)
Ch. 6
- 正誤表 (文責 新保)
ページ 行 誤 正 264 ↓1 w(?hat T)=... W(?hat T)=... 273 脚注 最大の重みを持つ1つの辺は 最大の重みを持つ辺のうち1つは 276 ↑5 w(?hat T)<... W(?hat T)<... 276 ↓7 w(T)とW(?hat T)を, ... W(T)とW(?hat T)を, ...
Ch. 8
- 正誤表 (文責 新保)
ページ 行 誤 正 343 脚注 もちろん, 読者は, ...後者(各頂点の指標の再計算)は, 多少冗長で, 2(n-1) に比例することを理解していることだろう. 時間計算量が(n-1)に比例するならば, 同じ計算量が 2(n-1)に比例することは言うまでもない---もっとも後者の言い方は少々冗長である. 356 ↓2 左の数 右の数
Ch. 9
- 正誤表 (文責 藤田)
ページ 行 誤 正 377 ↑6 r{?leq}4 r{?geq}4 389 9.16(b) r^{3}/3 r^{2}/3
Ch.10
- 正誤表 (文責 藤田)
ページ 行 誤 正 406 ↓5 a_{r}=16{?cdot}4^{r} a_{r}^{(p)}=16{?cdot}4^{r} 410 ↓6 10.2節において 10.3節において 417 ↑1 a_{r}で表わす． a_{n}で表わす．
Ch.11
- 正誤表
ページ 行 誤 正 437 ↑7 ★(a_1,a_2)+(10セント硬貨, 25...) ★(a_1,a_2) +(10セント硬貨) ... + の直前にスペース挿入. これらは別々の例なので. 449 ↑8 剰余類の要素を数えあわせれば 剰余類を全て計算すれば 450 ↑13 2つの関数の合成として定める 「2つの関数の合成」と定める