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