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