到達目標
[1] 数えるとはどういうことなのかを説明できる
[2] 証明で用いられる論法を習得することにより、自主的・継続的学習能力を養う
[3] 再帰的なものの考え方ができる
[4] 等しいということ、大きい(小さい)ということを一般化した概念を説明できる
[5] グラフ理論の基礎的な事項を説明できる
[6] 形式言語理論の基礎的な事項を説明できる
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | 集合と関数を分類しながら説明でき、2つの集合の濃度が等しいかどうか判別できる | 集合と関数を説明でき、2つの集合の濃度が等しいかどうか判別できる | 集合と関数を説明できず、2つの集合の濃度が等しいかどうかも判別できない |
| 評価項目2 | 命題と述語を的確に説明でき、対偶法、背理法、および数学的帰納法を用いて正しく証明が書ける | 命題と述語を説明でき、対偶法、背理法、および数学的帰納法を用いて証明が書ける | 命題と述語を説明できず、対偶法、背理法、および数学的帰納法を用いて証明が書けない |
| 評価項目3 | 集合と関数を再帰的に正しく定義できる | 集合と関数を再帰的に定義できる | 集合と関数を再帰的に定義できない |
| 評価項目4 | 同値関係、半順序、および全順序を的確に説明できる | 同値関係、半順序、および全順序を説明できる | 同値関係、半順序、および全順序を説明できない |
| 評価項目5 | グラフの道・連結度と木の性質を的確に説明できる | グラフの道・連結度と木の性質を説明できる | グラフの道・連結度と木の性質を説明できない |
| 評価項目6 | バッカス記法、文脈自由文法、有限オートマトン、および正規文法を正しく使うことができる | バッカス記法、文脈自由文法、有限オートマトン、および正規文法を使うことができる | バッカス記法、文脈自由文法、有限オートマトン、および正規文法を使うことができない |
学科の到達目標項目との関係
学習・教育到達度目標 (D)
説明
閉じる
学習・教育到達度目標 (F)
説明
閉じる
教育方法等
概要:
離散数学は有限の対象ないしは離散的対象を扱う数学の一分野で、計算機科学の礎の1つである。この科目では、集合と関数、数学的帰納法と再帰的定義、バッカス記法と文脈自由文法、集合上の関係、グラフと木、有限オートマトンと正規文法について学ぶ。
授業の進め方・方法:
講義形式
注意点:
用語の定義を正確に理解して、形式的に記述されていることから直観的なイメージを得ることを心掛ける。例題や演習問題を自力で解き、解答と照らし合わせて採点してみること。
合格の対象としない欠席条件(割合) 1/3以上の欠課
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
基本的な記法
|
集合や条件を表すための記法を使うことができる。
|
| 2週 |
集合の間の関係
|
種々の集合演算が行え、基本的公式を使うことができる。
|
| 3週 |
関数 1/2
|
関数の基礎的事項について説明できる。
|
| 4週 |
関数 2/2
|
単射、全射、全単射、関数の合成、合成に関する結合律、逆関数、および置換について説明できる。
|
| 5週 |
無限集合と濃度 1/2
|
集合の濃度を説明でき、2つの集合の濃度が等しいか否か判別できる。
|
| 6週 |
無限集合と濃度 2/2
|
数えるということと連続の濃度について説明できる。
|
| 7週 |
命題と背理法
|
命題とその逆、裏、対偶を説明できる。対偶方と背理法を用いて証明が書ける。
|
| 8週 |
中間試験
|
|
| 2ndQ |
| 9週 |
述語
|
述語(値として真または偽しかとらないような関数)を説明できる。
|
| 10週 |
命題論理とその記述能力の限界
|
命題論理の論理式を説明でき、陳述を論理式で表すことができる。述語論理の論理式を説明できる。
|
| 11週 |
言語
|
形式言語の基礎的事項を説明できる。
|
| 12週 |
数学的帰納法 1/2
|
数学的帰納法を用いて証明が書ける。
|
| 13週 |
数学的帰納法 2/2
|
完全帰納法を用いて証明が書ける。2重帰納法を説明できる。
|
| 14週 |
再帰的定義
|
集合、関数などを再帰的に定義できる。
|
| 15週 |
バッカス記法と文脈自由文法
|
バッカス記法と文脈自由文法を扱うことができる。
|
| 16週 |
期末試験
|
|
| 後期 |
| 3rdQ |
| 1週 |
2項関係 1/2 |
2項関係の基本的事項を説明できる。
|
| 2週 |
2項関係 2/2
|
2項関係の合成とべき乗を計算できる。
|
| 3週 |
同値関係 1/2
|
等しいという概念の一般化である同値関係を説明できる。
|
| 4週 |
同値関係 2/2
|
同値類、商集合、同値関係の細分を扱うことができる。
|
| 5週 |
順序 1/2
|
等号付きの不等号(≦)の一般化である半順序と全順序を説明できる。
|
| 6週 |
順序 2/2 |
半順序集合の極大値、極小値、最大値、および最小値を扱うことができ、上に(下に)有界を説明できる。また、関係の閉包、束、ソート、トポロジカルソートを説明できる。
|
| 7週 |
2項関係の図示と有向グラフの基礎
|
2項関係を有向グラフとして図示することができる。また、有向グラフの基礎的事項を説明できる。
|
| 8週 |
中間試験
|
|
| 4thQ |
| 9週 |
有向グラフの連結成分と半順序集合のハッセ図
|
有向グラフの連結成分を見つけることができる。有向グラフの隣接行列と到達可能性行列を書くことができる。半順序集合のハッセ図を描くことができる。
|
| 10週 |
グラフの基礎 1/2
|
グラフの基礎的事項を説明できる。
|
| 11週 |
グラフの基礎 2/2
|
n部グラフとグラフの道を説明できる。また、グラフの隣接行列、隣接リスト、接続行列を書くことができる。
|
| 12週 |
グラフの連結度
|
グラフの直径、半径、連結成分、切断点、切断辺、連結度、辺連結度を説明できる。また、グラフがn重連結、n重辺連結であることを説明できる。
|
| 13週 |
木
|
木に関する基礎的な事項と定理を説明できる。また、順序木、位置木、2分木、n分木を説明できる。
|
| 14週 |
有限オートマトンと非決定性有限オートマトン |
有限オートマトンと非決定性有限オートマトンを形式的に書き、その状態遷移図を描くことができる。また、それらが受理する言語を判別することができる。
|
| 15週 |
正規文法と正規表現
|
右線形文法と左線形文法を形式的に書くことができ、それらが生成する言語を判別することができる。正規表現で言語を表すことができる。
|
| 16週 |
期末試験
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | 情報数学・情報理論 | 集合に関する基本的な概念を理解し、集合演算を実行できる。 | 4 | 前1 |
| 集合の間の関係(関数)に関する基本的な概念を説明できる。 | 4 | 前1 |
| ブール代数に関する基本的な概念を説明できる。 | 4 | 前7 |
| 論理代数と述語論理に関する基本的な概念を説明できる。 | 4 | 前9,前10 |
| 離散数学に関する知識をアルゴリズムの設計、解析に利用することができる。 | 4 | 前14 |
評価割合
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 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 |