離散数学
工学部のやつ。
出席はとらないけど、期末テストの時自己申告。（〜2011年）
範囲は狭い。集合、グラフと木、数え上げと確率。教科書のページだと30ページくらい。
追試験がある。簡単。
期末テスト2010年(高橋先生)
基礎問題
問1 A={1,2,3},B={2,3,4}とする。以下の集合を求めよ。
(a)A∩B (b)A∪B (c)A×B (d)2^A
問2 A={1,2,3},B={0,1}とする。以下の写像の個数を求めよ。
(a)AからBへの写像 (b)BからAへの単射 (c)AからBへの全射 (d)Aから空集合への写像
問3 集合A={1,2,3,4,5}上の関係R={(1,2),(2,3),(3,4),(5,3)}に対し、次の関係を(有向)グラフで表せ。
(a)R^0 (b)R^2 (c)R^3 (d)R^*
問4 以下に挙げる正整数の集合上の関係Ra,Rb,Rcはそれぞれ反射的、対称的、反対称的、推移的か?あてはまる場合は○、そうでない場合は×をつけよ。
(a)Ra={(x,y) | 差の絶対値|x-y|が3で割りきれる}
(b)Rb={(x,y) | xの1の位はyの1の位以上}
(c)Rc={(x,y) | x/yは自然数である}
問5 A,B,C,D,E,Fの6人から委員長、副委員長、書記の各役員を一人ずつ決めたい。
(a)異なる決め方は全部で何通りか?
(b)AあるいはBが委員長となる決め方は何通りか?
(c)Cが役員(委員長、副委員長、書記のうちのいずれか)となる決め方は何通りか?
(d)AとBが共に役員となる決め方は何通りか?
発展問題
問6 Sn=1/(1×2)+1/(2×3)+…+1/(n(n+1))とする。
(a)Snの公式を推測し、
(b)数学的帰納法により証明せよ。
問7 fをA={1,2,…,n}上の全単射、またf^k=fofo…of(fをk回合成)とする。
(a)f^i=f^jとなる異なる自然数i,jが存在することを示せ。
(b)f^k(x)=x,すなわちf^kが恒等写像となる自然数kが存在することを示せ。
問8 fを有限集合上の写像とする。fが全射であることとfが単射であることは同値であることを証明せよ。
2012年追記
毎講義ごとに予習を兼ねた数問の練習問題を課し、それの提出をもって出席とする。成績の50%を占める。
試験は持ち込みは不可。範囲はレポートの範囲とほぼ同じだがアルゴリズムや確率論は出題されない。
出席はとらないけど、期末テストの時自己申告。（〜2011年）
範囲は狭い。集合、グラフと木、数え上げと確率。教科書のページだと30ページくらい。
追試験がある。簡単。
- 期末テスト2006
- {1}のべき集合求める。さらにそのべき集合のべき集合を求める
- N：自然数。N→Nへの全射、単射関数の例を挙げる
- 連結無効グラフGの辺eを取り除いたときの連結成分は３にならないことを示せ
- 5種類のおまけがある。5種類全て当たる期待値を求めよ。ただし、おまけのでる確率はどれも1/5とする
- 高さがｈの木の節点数が最大の時の節点の数、最小の時の節点の数を求めよ
- Rは半順序関係。A上の異なる極大元は比較不可能であることを示せ
- 10進数1から100万までのなかで9はいくつ現れるか
- 追試験2006
- A={1,2,3}、B={3,4,5}のとき(i)A∪B(ii)A∩B(iii)A-B
- =,<,>,<=,>=を(i)反射的(ii)対称的(iii)推移的にわける
- 無向グラフGの頂点xからｙへの経路があるとき、ｙからｘへの経路があることを証明する。
- 100円と10円を同時に投げて表が出たらもらえる。期待値はいくらか
期末テスト2010年(高橋先生)
- 教科書、ノート持ち込み可。
- 基礎問題(75点満点)と発展問題(25点満点)
基礎問題
問1 A={1,2,3},B={2,3,4}とする。以下の集合を求めよ。
(a)A∩B (b)A∪B (c)A×B (d)2^A
問2 A={1,2,3},B={0,1}とする。以下の写像の個数を求めよ。
(a)AからBへの写像 (b)BからAへの単射 (c)AからBへの全射 (d)Aから空集合への写像
問3 集合A={1,2,3,4,5}上の関係R={(1,2),(2,3),(3,4),(5,3)}に対し、次の関係を(有向)グラフで表せ。
(a)R^0 (b)R^2 (c)R^3 (d)R^*
問4 以下に挙げる正整数の集合上の関係Ra,Rb,Rcはそれぞれ反射的、対称的、反対称的、推移的か?あてはまる場合は○、そうでない場合は×をつけよ。
(a)Ra={(x,y) | 差の絶対値|x-y|が3で割りきれる}
(b)Rb={(x,y) | xの1の位はyの1の位以上}
(c)Rc={(x,y) | x/yは自然数である}
問5 A,B,C,D,E,Fの6人から委員長、副委員長、書記の各役員を一人ずつ決めたい。
(a)異なる決め方は全部で何通りか?
(b)AあるいはBが委員長となる決め方は何通りか?
(c)Cが役員(委員長、副委員長、書記のうちのいずれか)となる決め方は何通りか?
(d)AとBが共に役員となる決め方は何通りか?
発展問題
問6 Sn=1/(1×2)+1/(2×3)+…+1/(n(n+1))とする。
(a)Snの公式を推測し、
(b)数学的帰納法により証明せよ。
問7 fをA={1,2,…,n}上の全単射、またf^k=fofo…of(fをk回合成)とする。
(a)f^i=f^jとなる異なる自然数i,jが存在することを示せ。
(b)f^k(x)=x,すなわちf^kが恒等写像となる自然数kが存在することを示せ。
問8 fを有限集合上の写像とする。fが全射であることとfが単射であることは同値であることを証明せよ。
2012年追記
毎講義ごとに予習を兼ねた数問の練習問題を課し、それの提出をもって出席とする。成績の50%を占める。
試験は持ち込みは不可。範囲はレポートの範囲とほぼ同じだがアルゴリズムや確率論は出題されない。
2020年11月03日(火) 22:52:05 Modified by ID:NSy3Vzretg