平成23年度前期　離散数学入門a

時間割：火曜３限
教室：１−３０１
数え上げノート
期末試験は１号館230で行います．普段の教室と違うので注意してください．

授業方針・テーマ

　電車の乗換えを調べると，いくつもの道のりの中から最適なルートが瞬時に選び出されて表示される．ネット検索では，キーワードを入れると，膨大な数のページから関連が深そうなURLが瞬時に表示される．このように現代では，有限とはいえ巨大なデータを効率的に取り扱う情報処理技術が必要になっている． 　数学・情報のみならず，統計物理，分子構造の決定等でも，状態が何通りあるかの数え上げが必要なことがある．グラフによる表現も有用であり，ファインマン図形や炭水化物の構造式，進化系統樹，回路図等はその一例である．この授業では，有限集合を対象とした数学について，予備知識をほとんど仮定せず講義する．

習得できる知識・能力や授業の目的・到達目標

　有限の対象に関する様々な問題に対し，論理的に扱い効率的に解くための，数学的知識と計算能力の基礎を身につけることができる．具体的には，次を学ぶことを目的とする． (1) 論理演算など有限代数系の初歩的取り扱い (2) 起こりうる場合を漏れなく列挙して数え上げる技術 (3) 関係をグラフ化して調べたり，行列を用いて計算すること

授業計画・内容

（以下はすべて予定）
第1回		イントロダクション，集合
第2回〜第4回	論理・代数系
第5回〜第7回	数え上げ
第8回		まとめ・演習
第9回〜第11回	グラフの基礎
第12回〜第14回	グラフと行列
第15回		試験・解説

4/12  1. イントロダクション，集合（テキスト1.1, 1.6）
テキスト問1.12を含むレポート

4/19  2. 写像（テキスト1.2），論理（テキスト1.5, 5.1, 5.2, 5.3）
de Morganの法則を真理値表で証明し，レポートと一緒に提出

4/26  3. 論理の標準形，順序集合と束（テキスト3.1, 3.3, 5.4）
レポート

5/10  4. 同値関係，mod n（テキスト3.2）
Z_6の演算表をレポートと一緒に提出

5/17  5. 包含と排除の原理，順列・組合せ
PIEの証明・7回で4人を全員呼び出す場合の数・テキスト6.4の問題，から2問位をレポート

5/24  6. 数列，差分・和分とジョルダンの階乗関数
4乗和をレポートと一緒に提出

5/31  7. 母関数，二項係数とその一般化，カタラン数
提出なし

6/ 7  8. 演習
問題演習による前半のまとめと発展

6/14  9. 演習の解説，鳩の巣原理，重複円順列
演習・講義をしっかり復習すること

6/21 10. 9の続き（Frobenius-Burnsideの定理），グラフの基礎概念
レポート：立方体の面の5色塗り分け（オプション），Petersenグラフの番号付け，問題4.5，問題4.4など

6/28 11. 一筆書き，ハミルトングラフ，木，全域木とクラスカルのアルゴリズム
ハミルトンサイクルをレポートと一緒に提出

7/ 5 12. 二部グラフ，平面グラフ
レポート：4.110前半，K_6の辺の二色塗り分けで同色三角形が2個以上存在すること（オプション），PetersenグラフがK_{3,3}
と同相な部分グラフを含むこと（オプション），その他

7/12 13. 有向グラフ，隣接行列，確率遷移行列

7/19 14. ネットワーク（輸送問題），最大流量最小切断定理，アンケート

7/26 15. 試験・解説

教科書

成績評価方法

期末試験60％，授業参加度・レポート40％

特記事項

LABO研究室へ戻る