Course Objectives
[1] 数えるとはどういうことなのかを説明できる
[2] 証明で用いられる論法を習得することにより、自主的・継続的学習能力を養う
[3] 再帰的なものの考え方ができる
[4] 等しいということ、大きい(小さい)ということを一般化した概念を説明できる
[5] グラフ理論の基礎的な事項を説明できる
[6] 形式言語理論の基礎的な事項を説明できる
Rubric
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | 集合と関数を分類しながら説明でき、2つの集合の濃度が等しいかどうか判別できる | 集合と関数を説明でき、2つの集合の濃度が等しいかどうか判別できる | 集合と関数を説明できず、2つの集合の濃度が等しいかどうかも判別できない |
| 評価項目2 | 命題と述語を的確に説明でき、対偶法、背理法、および数学的帰納法を用いて正しく証明が書ける | 命題と述語を説明でき、対偶法、背理法、および数学的帰納法を用いて証明が書ける | 命題と述語を説明できず、対偶法、背理法、および数学的帰納法を用いて証明が書けない |
| 評価項目3 | 集合と関数を再帰的に正しく定義できる | 集合と関数を再帰的に定義できる | 集合と関数を再帰的に定義できない |
| 評価項目4 | 同値関係、半順序、および全順序を的確に説明できる | 同値関係、半順序、および全順序を説明できる | 同値関係、半順序、および全順序を説明できない |
| 評価項目5 | グラフの道・連結度と木の性質を的確に説明できる | グラフの道・連結度と木の性質を説明できる | グラフの道・連結度と木の性質を説明できない |
| 評価項目6 | バッカス記法、文脈自由文法、有限オートマトン、および正規文法を正しく使うことができる | バッカス記法、文脈自由文法、有限オートマトン、および正規文法を使うことができる | バッカス記法、文脈自由文法、有限オートマトン、および正規文法を使うことができない |
Assigned Department Objectives
学習・教育到達度目標 (D)
See
Hide
学習・教育到達度目標 (F)
See
Hide
Teaching Method
Outline:
離散数学は有限の対象ないしは離散的対象を扱う数学の一分野で、計算機科学の礎の1つである。この科目では、集合と関数、数学的帰納法と再帰的定義、バッカス記法と文脈自由文法、集合上の関係、グラフと木、有限オートマトンと正規文法について学ぶ。
Style:
講義形式
Notice:
用語の定義を正確に理解して、形式的に記述されていることから直観的なイメージを得ることを心掛ける。例題や演習問題を自力で解き、解答と照らし合わせて採点してみること。
合格の対象としない欠席条件(割合) 1/3以上の欠課
Course Plan
|
|
|
Theme |
Goals |
| 1st Semester |
| 1st Quarter |
| 1st |
基本的な記法
|
集合や条件を表すための記法を使うことができる。
|
| 2nd |
集合の間の関係
|
種々の集合演算が行え、基本的公式を使うことができる。
|
| 3rd |
関数 1/2
|
関数の基礎的事項について説明できる。
|
| 4th |
関数 2/2
|
単射、全射、全単射、関数の合成、合成に関する結合律、逆関数、および置換について説明できる。
|
| 5th |
無限集合と濃度 1/2
|
集合の濃度を説明でき、2つの集合の濃度が等しいか否か判別できる。
|
| 6th |
無限集合と濃度 2/2
|
数えるということと連続の濃度について説明できる。
|
| 7th |
命題と背理法
|
命題とその逆、裏、対偶を説明できる。対偶方と背理法を用いて証明が書ける。
|
| 8th |
中間試験
|
|
| 2nd Quarter |
| 9th |
述語
|
述語(値として真または偽しかとらないような関数)を説明できる。
|
| 10th |
命題論理とその記述能力の限界
|
命題論理の論理式を説明でき、陳述を論理式で表すことができる。述語論理の論理式を説明できる。
|
| 11th |
言語
|
形式言語の基礎的事項を説明できる。
|
| 12th |
数学的帰納法 1/2
|
数学的帰納法を用いて証明が書ける。
|
| 13th |
数学的帰納法 2/2
|
完全帰納法を用いて証明が書ける。2重帰納法を説明できる。
|
| 14th |
再帰的定義
|
集合、関数などを再帰的に定義できる。
|
| 15th |
バッカス記法と文脈自由文法
|
バッカス記法と文脈自由文法を扱うことができる。
|
| 16th |
期末試験
|
|
| 2nd Semester |
| 3rd Quarter |
| 1st |
2項関係 1/2 |
2項関係の基本的事項を説明できる。
|
| 2nd |
2項関係 2/2
|
2項関係の合成とべき乗を計算できる。
|
| 3rd |
同値関係 1/2
|
等しいという概念の一般化である同値関係を説明できる。
|
| 4th |
同値関係 2/2
|
同値類、商集合、同値関係の細分を扱うことができる。
|
| 5th |
順序 1/2
|
等号付きの不等号(≦)の一般化である半順序と全順序を説明できる。
|
| 6th |
順序 2/2 |
半順序集合の極大値、極小値、最大値、および最小値を扱うことができ、上に(下に)有界を説明できる。
|
| 7th |
2項関係の図示
|
2項関係を有向グラフとして図示することができる。
|
| 8th |
中間試験
|
|
| 4th Quarter |
| 9th |
ハッセ図、トポロジカルソート、関係の閉包
|
半順序集合のハッセ図を書くことができ、トポロジカルソートと関係の閉包を説明できる。
|
| 10th |
グラフの基礎 1/2
|
グラフの基礎的事項を説明できる。
|
| 11th |
グラフの基礎 2/2
|
部分グラフ、誘導部分グラフ、辺誘導部分グラフ、補グラフ、n部グラフを説明できる。
|
| 12th |
グラフにおける道と閉路
|
グラフにおける道、閉路、およびそれらに関する定理を説明できる。
|
| 13th |
グラフの連結度
|
グラフの連結度とそれに関する定理を説明できる。
|
| 14th |
木 |
木と木に関する基礎的な定理を説明できる。
|
| 15th |
有限オートマトン
|
有限オートマトンを扱うことができる。
|
| 16th |
期末試験
|
|
Evaluation Method and Weight (%)
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | その他 | Total |
| Subtotal | 100 | 0 | 0 | 0 | 0 | 0 | 100 |
| 基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 専門的能力 | 100 | 0 | 0 | 0 | 0 | 0 | 100 |
| 分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |