| 科目名 |
離散数学 |
| 担当教員 |
坂本 明雄 |
| 対象学年 |
1年 |
クラス |
学部：専門001 |
| 講義室 |
Ａ１０６ |
開講学期 |
２学期 |
| 曜日・時限 |
月２,木２ |
単位区分 |
選択 |
| 授業形態 |
一般講義 |
単位数 |
2 |
| 準備事項 |
|
| 備考 |
|
| 授業の詳細1 |
【 授業の目的 】
微分積分学に代表される連続量を扱う数学に対して，この授業では離散構造や離散量を対象とする理論および数学的技法について学ぶ。この授業科目を履修するには，『情報代数』で学んだ集合，関係，関数，演算などの概念を理解していることが必要である。
ある種の性質をもつものを数え上げる手法の代表例が順列と組合せである。
一方，議論の対象となる要素の間に何らかの関係が定義されているとき，それらはある種の構造をもっているという。離散的な要素についての構造を表現する代表的なものがグラフである。特に木構造をもつグラフは，情報システムを学んでいくさまざまな場面で登場する基本的かつ重要なグラフである。なお，放物線や２次曲線などで代表される関数を直交座標上に図示した“グラフ”は，連続量の関係を表現したものであり，この授業では扱わない。
この授業の目的は，離散的要素の基本的な数え上げ技法である順列と組合せについて学習することと，離散構造の代表であるグラフに関する基本的な知識を修得することである。
|
| 授業の詳細2 |
【 授業の進め方 】
はじめに，順列と組合せを学習して各種の数え上げ手法を修得する。
次に，グラフ理論の基礎とグラフに関するいくつかの概念を学ぶ。さらに，平面グラフ，グラフの彩色，最小全域木などグラフに関する基本的な応用問題について学習する。
この授業は，12回の講義と３回の試験（数え上げ，グラフ基礎，グラフ応用）からなる。毎回の講義の最後にはQuiz（小テスト）を実施してその日の学習内容を復習する。
|
| 授業の詳細3 |
【 達成目標 】
数え上げ手法に関するこの授業の達成目標は，次の３項目である。
［E1］階乗の計算が適確にできる
［E2］順列の計算式 P(n, r) および組合せの計算式 C(n, r) を理解し使いこなせる
［E3］重複順列，順列分割といった複雑な数え上げの概念を理解し，具体例に応用できる
グラフ理論に関するこの授業の達成目標は，次の５項目である。
［G1］次数，部分グラフ，同型，連結，距離，直径といったグラフの基礎概念を理解する
［G2］オイラーグラフ，ハミルトングラフの性質を理解し，その性質を持つかどうかを判定できる
［G3］平面的グラフの意味を理解し，グラフの平面判定ができる
［G4］グラフの染色数を理解し，その色数でグラフの彩色ができる
［G5］重み付きグラフの最小全域木を求めることができる
|
| 授業の詳細4 |
【 授業計画（数え上げ）】
１．『離散数学』で学ぶこと
まず，ケーニヒスベルグの７つの橋問題を例にして，グラフとは何かを理解する。また，パスカルの三角形を題材に，２項係数などの数え上げ技法についての概要を理解する。最後に，この授業科目の成績評価について説明する。
２．階乗とΣ記法
順列と組合せの計算式で使われる階乗計算について学習する。また，一定条件をみたすものの総和を表す便利な記法であるΣ記法について学習する。
３．順列と組合せ
順列の計算式 P(n, r) および組合せの計算式 C(n, r) について学習し，それらがどういった場合の数え上げに対応しているかを理解する。
４．特殊な数え上げ
重複順列，円順列，順列分割など，与えられた対象を特別な条件の下で並べたり分割したりする場合の数え上げ手法について学習する。
５．試験（数え上げ）
＊ 数え上げ手法の概念を確実に理解できているかどうかを試験によって確認する。
＊ 試験問題は授業に使用する補助テキストにある演習問題のレベルである。
|
| 授業の詳細5 |
【 授業計画（グラフ基礎）】
６．グラフの概念
グラフは頂点集合と辺集合から構成される概念であることを理解する。更に，頂点の次数に関するグラフの基本的な定理について学ぶ。
７．部分グラフと同型
点誘導部分グラフ，辺誘導部分グラフなどの部分グラフについて学ぶ。また，二つのグラフが同じ構造であることを意味する同型の概念を理解する。
８．道と閉路
道と閉路の概念を理解し，グラフの連結性について学ぶ。更に，２頂点間の距離やグラフの直径といった概念を理解する。
９．オイラーグラフとハミルトングラフ
オイラーグラフとハミルトングラフの定義を理解しその相違点を学ぶ。
10．試験（グラフ基礎）
＊ グラフ理論の基礎概念（目標G1とG2に関するグラフの基礎事項）を確実に理解できているかどうかを試験によって確認する。
＊ 試験問題は授業に使用するテキストにある演習問題のレベルである。
|
| 授業の詳細6 |
【 授業計画（グラフ応用）】
11．平面グラフ
グラフの平面性とそれに関連したオイラーの公式やクラトフスキーの定理を学ぶ。また，これらの定理を使って与えられたグラフが平面的でないと判定できることを理解する。
12．グラフの彩色
隣接する頂点には異なる色を割り当てるという条件で，可能な限り少ない色数でグラフを彩色する問題を理解し，グラフの彩色数の意味および具体的な彩色法の一つを学ぶ。
13．最小全域木
木とよばれる構造をもつグラフは，データを記憶し効率よく処理する際にしばしば用いられる。ここでは，重み付きグラフの最小全域木などについて学習する。
14．試験（グラフ応用）
＊ グラフ理論の応用（目標G3〜G5に関するグラフの応用項目）に関する概念を確実に理解できているかどうかを試験によって確認する。
＊ 試験問題は授業に使用するテキストにある演習問題のレベルである。
15．『離散数学』で学んだこと
この授業で学んだことを整理する。さらに，返却された最終試験の答案を検討して，各自がこの授業の目標に達しているかどうかを自己点検する。また，まとめとして課される最終課題についてその概要を理解する。
|
| 授業の詳細7 |
【 成績評価 】
成績を評価するための３回の試験は次のとおりである。
［数え上げ法］目標E1〜E3の達成状況を確認する問題。30点満点。
［グラフ基礎］目標G1・G2の達成状況を確認する問題。40点満点。
［グラフ応用］目標G3〜G5の達成状況を確認する問題。30点満点。
成績評価は次のようにするが，講義の最後に実施するQuizの結果および最終課題を成績評価の一部に利用する。
◆Ｃ：合計点が55点以上であることを基準とする。
◆Ｂ：合計点が65点以上であることを基準とする。
◆Ａ：合計点が75点以上であることを基準とする。
◆AA：最終課題の完成度を含めて，この授業の目標を完全に達成したと認められた場合
なお，成績評価の詳細は最初の授業で説明する。
□□□□□□□□□□□□□□□□□□□□
◇テキスト
『離散数学』（第４章），牛島 和夫 編著，相 利民・朝廣 雄一 共著（コロナ社，2006），ISBN 4-339-02715-4
また，必要に応じて補助テキストを授業中に配付する
◇参考書
『情報科学のためのグラフ理論』，加納 幹雄 著（朝倉書店，2001），ISBN 4-254-11424-9
『離散数学 〜コンピュータサイエンスの基礎数学〜』，S. Lipschutz 著，成嶋 弘 監訳（オーム社，1995）ISBN 4-274-13005-3
『コンピュータサイエンスのための離散数学入門』，C. L. Liu 著，成嶋 弘・秋山 仁 共訳（オーム社，1995）ISBN 4-274-13007-X
◇備 考
履修登録必須科目，履修前提科目＝「情報代数」
|
| 授業の詳細8 |
|
| 授業の詳細9 |
|
| 授業の詳細10 |
|