| 科目名 |
離散数学 |
| 担当教員 |
坂本 明雄 |
| 対象学年 |
1年 |
クラス |
学部：専門001 |
| 講義室 |
Ａ１０７ |
開講学期 |
２学期 |
| 曜日・時限 |
火２,金２ |
単位区分 |
選択 |
| 授業形態 |
一般講義 |
単位数 |
2 |
| 準備事項 |
|
| 備考 |
|
| 授業の詳細1 |
【 授業の目的 】
微分積分学に代表される連続量を扱う数学に対して，この授業では離散構造や離散量を対象とする理論および数学的技法について学ぶ。この授業科目を履修するには，『情報代数』で学んだ集合，関係，関数，演算などの概念を理解していることが必要である。
ある種の性質をもつものを数え上げる手法の代表例が順列と組合せである。
一方，議論の対象となる要素の間に何らかの関係が定義されているとき，それらはある種の構造をもっているという。離散的な要素についての構造を表現する代表的なものがグラフである。特に木構造をもつグラフは，情報システムを学んでいくさまざまな場面で登場する基本的かつ重要なグラフである。なお，放物線や２次曲線などで代表される関数を直交座標上に図示した“グラフ”は，連続量の関係を表現したものであり，この授業では扱わない。
この授業の目的は，離散的要素の基本的な数え上げ技法である順列と組合せについて学習することと，離散構造の代表であるグラフに関する基本的な知識を修得することである。
|
| 授業の詳細2 |
【 授業の進め方 】
はじめに，順列と組合せを学習して各種の数え上げ手法を修得する。
次に，グラフ理論の基礎とグラフに関するいくつかの概念を学ぶ。さらに，平面グラフ，グラフの彩色，最小全域木，根付き木などグラフに関する基本的な応用問題について学習する。
この授業では，毎回の講義の最後にその日の学習内容を復習するための Quiz（小テスト）を配布する。その解答および解説は，講義時間とは別の『専門科目演習』の時間に行う。
|
| 授業の詳細3 |
【 達成目標 】
数え上げ手法に関するこの授業の達成目標は，次の３項目である。
［E1］階乗の計算が適確にできる
［E2］順列の計算式 P(n, r) および組合せの計算式 C(n, r) を理解し使いこなせる
［E3］重複順列，重複組合せといった複雑な数え上げの概念を理解し，具体例に応用できる
グラフ理論に関するこの授業の達成目標は，次の６項目である。
［G1］次数，部分グラフ，同型，連結，距離，直径といったグラフの基礎概念を理解する
［G2］オイラーグラフ，ハミルトングラフの性質を理解し，その性質をもつかどうかを判定できる
［G3］平面的グラフの意味を理解し，グラフの平面判定ができる
［G4］グラフの彩色数を理解し，その色数でグラフの彩色ができる
［G5］重み付きグラフの最小全域木を求めることができる
［G6］根付き木に関する基本的性質を理解し，具体例を書くことができる
|
| 授業の詳細4 |
【 授業計画（数え上げ）】
１．『離散数学』で学ぶこと
まず，ケーニヒスベルグの７つの橋問題を例にして，グラフとは何かを理解する。また，パスカルの三角形を題材に，２項係数などの数え上げ技法についての概要を理解する。最後に，この授業科目の成績評価について説明する。
２．階乗とΣ記法
順列と組合せの計算式で使われる階乗計算について学習する。また，一定条件をみたすものの総和を表す便利な記法であるΣ記法について学習する。
３．順列と組合せ
順列の計算式 P(n,r) および組合せの計算式 C(n,r) について学習し，それらがどういった場合の数え上げに対応しているかを理解する。
４．特殊な数え上げ
重複順列，円順列，順列分割など，与えられた対象を特別な条件の下で並べたり分割したりする場合の数え上げ手法について学習する。
５．［数え上げ法（第２〜４回）］の復習と習熟度確認
＊ 数え上げ手法の概念を確実に理解できているかどうかを確認する。
＊ 確認内容は，第１回目の授業で配布した演習問題のレベルとする。
|
| 授業の詳細5 |
【 授業計画（グラフ基礎）】
６．グラフの概念
グラフは頂点集合と辺集合から構成される概念であることを理解する。更に，頂点の次数に関するグラフの基本的な定理について学ぶ。
７．部分グラフと同型
点誘導部分グラフ，辺誘導部分グラフなどの部分グラフについて学ぶ。また，二つのグラフが同じ構造であることを意味する同型の概念を理解する。
８．道と閉路
道と閉路の概念を理解し，グラフの連結性について学ぶ。更に，２頂点間の距離やグラフの直径といった概念を理解する。
９．オイラーグラフとハミルトングラフ
オイラーグラフとハミルトングラフの定義を理解しその相違点を学ぶ。
10．［グラフ基礎（第６〜９回）］の復習と習熟度確認
＊ グラフ理論の基礎概念（目標G1とG2に関するグラフの基礎事項）を確実に理解できているかどうかを確認する。
＊ 確認内容は，授業に使用するテキストにある演習問題のレベルとする。
|
| 授業の詳細6 |
【 授業計画（グラフ応用）】
11．平面グラフ
グラフの平面性とそれに関連したオイラーの公式やクラトフスキーの定理を学ぶ。また，これらの定理を使って与えられたグラフが平面的でないと判定できることを理解する。
12．グラフの彩色
隣接する頂点には異なる色を割り当てるという条件で，可能な限り少ない色数でグラフを彩色する問題を理解し，グラフの彩色数の意味および具体的な彩色法の一つを学ぶ。
13．最小全域木
長さが３以上の閉路をもたない連結なグラフを木という。ここでは，重み付きグラフの最小全域木について学習する。
14．根付き木
根とよばれる頂点が指定された木を根付き木という。根付き木は，情報システムを学んでいくさまざまな場面で登場する重要な概念である。ここでは，根付き木に関する基本的な性質を理解する。
15．［グラフ応用（第11回〜14回）］の復習と習熟度確認
＊ グラフ理論の応用（目標G3〜G6に関するグラフの応用項目）に関する概念を確実に理解できているかどうかを確認する。
＊ 確認内容は，授業に使用するテキストにある演習問題のレベルとする。
16．『離散数学』で学んだこと
この授業で学んだことを整理する。さらに，これまでの習熟度確認の結果を検討し，各自がこの授業の目標に達しているかどうかを自己点検する。また，まとめとして課される最終課題についてその概要を理解する。
|
| 授業の詳細7 |
【 成績評価 】
成績は，習熟度確認の結果をもとに評価するが，最終課題を成績評価の一部に利用する。なお，数え上げ法20％，グラフ基礎40％，グラフ応用40％の割合で最終評価する。
◆Ｃ：全体として，習熟度が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
◇準備学習等についての指示
履修前提科目＝「情報代数」
「情報代数」が不合格あるいは未履修の者が履修登録を希望する場合には，前記テキスト（牛島編著『離散数学』）の第１章をよく理解したうえで登録すること。
◇備 考
履修登録必須科目
数学免許（中学･高校）取得のための選択科目
オフィスアワー：［第３クォータ］ 火曜日５時限目
連絡先：Ａ棟416室 |
| 授業の詳細8 |
|
| 授業の詳細9 |
|
| 授業の詳細10 |
|