離散数学

コース情報

評価方法

詳細情報

スケジュール

1. 講義の概要とスケジュールの説明， 数学的帰納法 [講義の概要] 第１回目は，講義の前半をガイダンスにあてます。講義で取り上げる内容を紹介するとともに，この講義を通じて受講者の皆さんに伝えたいことについてお話します。講義スケジュールや試験，成績のつけ方についても，このガイダンスで説明します。 また，講義の後半では，離散数学の理論を展開する上で必要不可欠な「数学的帰納法」についてその原理を確認します。 [テーマ] ・ペアノの公理と整列集合 ・数学的帰納法 ・数学的帰納法の間違った使い方
2. 場合の数と包除原理 [講義の概要] 離散数学におけるもっとも基本的な問題は，場合の数，すなわち「ある条件を満たすものの個数」を数えることと言っても過言ではありません。第２回目の講義では，場合の数を数えるための強力な手段である「包除原理」をとりあげます。まず初めに包除原理に関する例題を吟味した後，その成立を証明します。さらに，包除原理の応用として，整数論における基本的な関数の一つであるオイラー関数の導出と，クローク係の問題と呼ばれる一見不思議な場合の数についてお話します。 [テーマ] ・包除原理とは ・包除原理の応用① オイラー関数 ・包除原理の応用② クローク係の問題
3. 母関数 [講義の概要] 包除原理を用いて場合の数を求める以外にも，数列として表された場合の数の一般項を，漸化式に基づく母関数を経由して求めたり，漸化式そのものを直接解くことによって求めたりする方法があります。今回の講義では，母関数を経由して数列の一般項を求める手法について，フィボナッチ数やカタラン数の一般項の導出を例にとってお話しします。 [テーマ] ・フィボナッチ数列の導出 ・母関数とその性質 ・母関数の応用 カタラン数
4. 差分方程式(１) 線形１階差分方程式の解法 [講義の概要] 場合の数を求める３つ目の方法として，数列として表された場合の数の一般項を漸化式を直接解くことによって求める方法を，今回から３回にわたって学びます。１回目は，差分と和分の概念を用いて漸化式を解く「差分方程式論」の初歩として，線形１階差分方程式の解の構造について説明します。 [テーマ] ・差分と和分 ・線形１階差分方程式の解法
5. 差分方程式(２) [講義の概要] 差分方程式の２回目では，線形１階差分方程式の様々な解法を紹介します。また，より複雑な線形２階差分方程式について，その解の構造を明らかにします。 [テーマ] ・線形２階差分方程式の一般解の構造 ・線形２階同次差分方程式の解法
6. 差分方程式(３) [講義の概要] 差分方程式の３回目では，線形２階差分方程式の様々な解法を紹介します。 また，講義の後半では，中間試験に備えて重要事項の復習を行います。 [テーマ] ・線形２階同次差分方程式(一般形)の解法 ・その他の線形２階同次差分方程式
7. 中間試験 第６回目までの講義内容に関する試験を実施します。
8. グラフ理論(１) グラフの基礎概念/木 [講義の概要] 本講義の後半では，離散数学における主要な研究分野の一つである「グラフ理論」をとり上げます。グラフ理論は，純粋数学の視点から見て興味深い数多くのテーマを含むだけでなく，数理科学や情報科学，様々な工学への多様な関連テーマを含む，極めて重要な研究分野と言えます。第１回目の講義では，グラフ理論の導入として，グラフ理論に登場する用語とグラフに関する 基本的な性質について説明します。 また，データ構造やアルゴリズムの動作を端的に表現することのできるグラフとして，「木」と 呼ばれるグラフは，情報科学の分野で特に重要なグラフ構造の一つです。講義後半では，木の定義と基本的な性質について確認します。続いて，与えられた木に対する全域木の概念を導入し，全域木の総数を求める方法について議論します。最後に，輸送コスト最小化や道路建設コスト最小化問題と深くかかわる，最小重みの全域木の導出アルゴリズムについて紹介します。 [テーマ] ・グラフ理論の用語と基本的な性質 ・様々なグラフ(完全グラフ，正則グラフ，二部グラフ，etc.) ・木の定義と基本的な性質 ・根付き木の同型判定 ・グラフの全域木と探索アルゴリズム
9. グラフ理論(２) 平面グラフ [講義の概要] 平面上に辺が交わることなく描けるグラフを平面的グラフと呼び，与えられたグラフが平面的であるための極めてシンプルな必要十分条件が知られています。今回の講義では，この必要十分条件を紹介します。また，平面グラフを特徴づける性質の一つとして，オイラーの公式を証明します。さらに，オイラーの公式の応用として，正多面体が５つしか存在しないことの証明を与えます。 [テーマ] ・平面的グラフの定義と基本的な性質 ・グラフの平面性の判定とクラトフスキーの定理 ・オイラーの公式 ・正多面体が５種類に限られることの証明
10. グラフ理論(３) グラフの周遊問題 [講義の概要] 「与えられた図形が一筆書き可能か否か」という問題は，大昔から人々の興味を引く問題であったと考えられます。この「一筆書き問題」が歴史の表舞台に登場するのは，１８世紀初頭のケーニヒスベルグ(現在のカリニングラード)で流行った「ある問題」にまで遡ります。また，この問題を解いた大数学者オイラーの業績は，現代的なグラフ理論の萌芽ともいわれます。 今回の講義では，図形が一筆書きできるための必要十分条件の証明を与え，さらに，実際に一筆書きを与えるためのアルゴリズムを紹介します。また，グラフを巡回するもう一つの問題である「ハミルトン閉路問題」を紹介し，情報セキュリティや計算量理論の分野における「巡回セールスマン問題」との関連についてお話します。 [テーマ] ・一筆書きとオイラーグラフ ・オイラー回路を求めるアルゴリズム ・オイラー有向グラフ ・ハミルトングラフと巡回セールスマン問題
11. グラフ理論(４) グラフの彩色問題 [講義の概要] 国境を接する国同士の色が互いに異なるように地図を塗り分けるには，高々４色あれば十分であることが知られています。この数学的事実は「４色問題」として有名であり，また，その証明において史上初めてコンピュータが本質的な役割を果た，記念碑的な問題です。 今回の講義では，このような歴史的経緯を紹介するとともに，条件を少し緩めて「５色あれば塗り分けられる」ことの証明を与えます。 [テーマ] ・４色問題と平面グラフの頂点彩色 ・平面グラフが５-彩色可能であることの証明 ・一般のグラフの頂点彩色と辺彩色
12. グラフ理論(５) ネットワークと流れ 電力の供給(送電)や生活用水の供給(給水)などのようにネットワークを通じて資源を配布する場合，現状のネットワークの下で効率よく配布する方法や，配布効率を改善するためのボトルネックの発見は，古くからある重要な問題です。これらの問題をグラフ理論的・アルゴリズム的に取り上げます。 [テーマ] ・ネットワークとネットワーク上の流れ ・キルヒホッフの法則 ・最大流を求めるアルゴリズム ・最大流・最小カット定理
13. グラフ理論(６) マッチング [講義の概要] グラフ理論の最終回では，グラフのマッチングをとり上げます。知り合い関係にある男女のグループにおいて，一人もあぶれることなくカップルが誕生するための条件(結婚定理)など，マッチングの概念は，数理科学・工学だけでなく現実的な応用においてもしばしば現れます。 また，講義の後半では，期末試験に備えて重要事項の復習を行います。 [テーマ] ・マッチングとは ・二部グラフのマッチング ・結婚定理 ・一般のグラフのマッチング
14. 期末試験 第８回目から第１３回目までの講義内容(グラフ理論)に関する試験を実施します。