シラバス

組合せ論
2015/09/28
重要文書
単位取得規約書
1. 概要
「数え上げ」や「グラフ理論」などの組合せ論の初歩を学習する．組合せ論は，離散数学の一分野
であり，アルゴリズム論，計算量理論，暗号理論，符号理論といったコンピュータサイエンスの様々
な分野で応用されている．本講義では，集合・論理といった離散数学の導入部分の復習から始め，前
半は数え上げに関する基礎事項，後半はグラフ理論の初歩を学習する．
2. 担当教員
氏名
居室
メールアドレス
ホームページ
:
:
:
:
山本真基（やまもとまさき）
１１号館４階１４０３号室
yamamoto[あっと]st.seikei.ac.jp
http://www.ci.seikei.ac.jp/yamamoto/index j.html
3. 到達目標
組合せ論の初歩を習得する．理論分野の学習を通じて，プログラミング能力を含む論理的思考力
を高める．
4. 講義スケジュール
回
内容
説明
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
離散数学の復習１
集合
離散数学の復習２
論理
順列と組合せ
二項係数
鳩ノ巣原理
包除原理
母関数
母関数と数え上げ
中間テスト
グラフ
グラフとは？
色々なグラフ１
完全グラフ，正則グラフ，二部グラフ
色々なグラフ２
オイラーグラフ，ハミルトングラフ
色々なグラフ３
木，根付き木
グラフ彩色１
グラフ頂点彩色問題
グラフ彩色２
グラフ辺彩色問題
到達度確認テスト
1
5. 授業の方法
講義では，基礎知識や基礎概念，それに基本的な定理とその証明を解説する．その中で，新たな知
識や概念を学ぶごとに，基礎的な練習問題（テキスト中の「問」）を解いてもらう．更に，演習のた
めの授業を別途もうけ，それらに類似した問題（テキスト中の「章末問題」）を解くことにより，そ
れまでに習得した知識や概念の習熟を図る．
6. レポート課題
以下のように二つの課題がある．
（提出方法は，講義内で手渡しかレポートボックス＃７への投函．
）
1. 第一回目
• 課題：第一章から第五章までの「問」と「章末問題」．それに，集合・論理の問題すべて．
• 締切：中間テスト終了時
2. 第二回目
• 課題：第六章の「問」と「章末問題」
• 締切：到達度確認テスト終了時
レポートはすべて手書きで，Ａ４サイズのレポート用紙にて（綴じたものを）提出する．なお，レ
ポートの返却は行わない．
7. 成績評価
レポート課題（１０％），中間テスト（４０％），到達度確認テスト（５０％）で評価する．なお，
試験は，テキストとレポートのみを持ち込み可能とする．
8. 注意事項
• レポート課題で解く問題は，その多くは授業中で出題され解答が示される問題である．テキス
トの最後には問題の略解のみが記されているが，略解を写しただけのレポートの評価は（５点
満点中）１点とする．よって，授業に毎回出席することを強く勧める．
• 試験では，講義や演習で行った問題と類似した問題が出題される．
（逆に，そういうものしか出
題されない．
）よって，授業中に出題される問題は，各自自力で解くことを強く勧める．
9. テキスト
自作のテキストを用いる．各自，以下 URL からダウンロードすること．
http://www.ci.seikei.ac.jp/yamamoto/lecture/combinatorics/material.html
10. 参考図書
• 離散数学入門，守屋悦朗著，サイエンス社，２００６年．
• 工学のための離散数学，黒澤馨著，数理工学社，２００８年．
2

Download Report