平成22年度前期　離散数学入門c

時間割：火曜３限
教室：１−１０１ （期末試験教室：１−２１０）
補充プリント（2010.6.1更新）

授業方針・テーマ

　電車の乗換えを調べると，いくつもの道のりの中から最適なルートが瞬時に選び出されて表示される．ネット検索では，キーワードを入れると，膨大な数のページから，関連が深いと思われるもののURLが瞬時に表示される．このように現代では巨大なデータを効率的に取り扱う情報処理技術が必要になっている． 　この授業では，情報処理やオペレーションズ・リサーチ等の基本である，有限集合を対象とした数学について，予備知識をほとんど仮定せず講義する．

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

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

授業計画・内容

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

4/13  1. イントロダクション，集合（テキスト第１章§1）
テキスト演習問題をいくつか解いて，来週の授業の最初に提出．

4/20  2. 論理（テキスト第１章§2）
テキスト演習問題をいくつか解いて，来週の授業の最初に提出．

4/27  3. 代数系（テキスト第３章）
（提出課題なし）
今回は難しいこともやりましたが，次回からはまた易しくなります．

5/11  4. 順序集合と束（テキスト第４章）
テキスト演習問題５１，５４を解いて，来週の授業の最初に提出．

5/18  5. 数列
関数・写像，差分・和分とジョルダンの階乗関数，線形漸化式，母関数
提出課題：テキスト演習問題26，4乗和の公式，母関数による漸化式の解法

5/25　6. 数え上げ１
無限集合，可算集合，Cantorの対角線論法，重複組合せ
提出課題：x1+x2+x3=8,x1≧1,x2≧1,x3≧0の整数解の個数を求めよ．

6/ 1  7. 数え上げ２
特性関数，包含と排除の原理，対称群，同値関係
提出課題：テキスト演習問題３８

6/ 8  8. 演習
問題演習による前半のまとめと発展
提出課題：演習の残り

6/15  9. 演習の解説，グラフの基礎１
グラフの基礎概念，グラフ理論の第１定理
提出課題：テキスト演習問題６１，６２

6/22 10. グラフの基礎２
一筆書き，ハミルトングラフ，Catalan数
提出課題：テキスト演習問題７４，７５

6/29 11. グラフの基礎３
第２定理，木，全域木とクラスカルのアルゴリズム，平面グラフ
提出課題：テキスト演習問題７０，７１

7/ 6 12. グラフと行列１
有向グラフ，確率遷移行列，隣接行列，安定結婚問題
提出課題：授業中に出した問題（定常状態を求めよ），テキスト演習問題６４

7/13 13. グラフと行列２
対応・関係，ネットワーク（輸送問題）
提出課題：テキスト演習問題１８，２０，（２３），授業中に出した輸送問題（最大流量を求めよ）

7/20 14. グラフと行列３
演習問題解説，グラフ理論補足（経路の数等），重複円順列
アンケート

7/27 15. 試験・解説
試験範囲：テキスト（１６１ページまで），数え上げ，クラスカルのアルゴリズム，フォード・ファルカーソンのアルゴリズム．
テキストの演習問題と，第８回の演習を復習しておくこと．

教科書

『やさしく学べる離散数学』石村園子著　共立出版(ISBN978-4-320-01846-4) 必要に応じてプリントを配布する．

成績評価方法

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

特記事項

LABO研究室へ戻る