離散数学

科目基礎情報

学校 明石工業高等専門学校 開講年度 令和03年度 (2021年度)
授業科目 離散数学
科目番号 0028 科目区分 専門 / 選択
授業形態 講義 単位の種別と単位数 履修単位: 2
開設学科 電気情報工学科(電気電子工学コース) 対象学年 4
開設期 通年 週時間数 2
教科書/教材 守屋悦朗:「離散数学入門」、サイエンス社
担当教員 濱田 幸弘

目的・到達目標

[1] 数えるとはどういうことなのかを説明できる
[2] 証明で用いられる論法を習得することにより、自主的・継続的学習能力を養う
[3] 再帰的なものの考え方ができる
[4] 等しいということ、大きい(小さい)ということを一般化した概念を説明できる
[5] グラフ理論の基礎的な事項を説明できる
[6] 形式言語理論の基礎的な事項を説明できる

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1集合と関数を分類しながら説明でき、2つの集合の濃度が等しいかどうか判別できる集合と関数を説明でき、2つの集合の濃度が等しいかどうか判別できる集合と関数を説明できず、2つの集合の濃度が等しいかどうかも判別できない
評価項目2命題と述語を的確に説明でき、対偶法、背理法、および数学的帰納法を用いて正しく証明が書ける命題と述語を説明でき、対偶法、背理法、および数学的帰納法を用いて証明が書ける命題と述語を説明できず、対偶法、背理法、および数学的帰納法を用いて証明が書けない
評価項目3集合と関数を再帰的に正しく定義できる集合と関数を再帰的に定義できる集合と関数を再帰的に定義できない
評価項目4同値関係、半順序、および全順序を的確に説明できる同値関係、半順序、および全順序を説明できる同値関係、半順序、および全順序を説明できない
評価項目5グラフの道・連結度と木の性質を的確に説明できるグラフの道・連結度と木の性質を説明できるグラフの道・連結度と木の性質を説明できない
評価項目6バッカス記法、文脈自由文法、有限オートマトン、および正規文法を正しく使うことができるバッカス記法、文脈自由文法、有限オートマトン、および正規文法を使うことができるバッカス記法、文脈自由文法、有限オートマトン、および正規文法を使うことができない

学科の到達目標項目との関係

学習・教育到達度目標 (D) 説明 閉じる
学習・教育到達度目標 (F) 説明 閉じる

教育方法等

概要:
離散数学は有限の対象ないしは離散的対象を扱う数学の一分野で、計算機科学の礎の1つである。この科目では、集合と関数、数学的帰納法と再帰的定義、バッカス記法と文脈自由文法、集合上の関係、グラフと木、有限オートマトンと正規文法について学ぶ。
授業の進め方と授業内容・方法:
講義形式
注意点:
用語の定義を正確に理解して、形式的に記述されていることから直観的なイメージを得ることを心掛ける。例題や演習問題を自力で解き、解答と照らし合わせて採点してみること。
合格の対象としない欠席条件(割合) 1/3以上の欠課

授業の属性・履修上の区分

アクティブラーニング
ICT 利用
遠隔授業対応
実務経験のある教員による授業

授業計画

授業内容・方法 週ごとの到達目標
前期
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週 期末試験

モデルコアカリキュラムの学習内容と到達目標

分類分野学習内容学習内容の到達目標到達レベル授業週

評価割合

試験発表相互評価態度ポートフォリオその他合計
総合評価割合10000000100
基礎的能力0000000
専門的能力10000000100
分野横断的能力0000000