情報数学

科目基礎情報

学校 鈴鹿工業高等専門学校 開講年度 平成30年度 (2018年度)
授業科目 情報数学
科目番号 0094 科目区分 専門 / 選択
授業形態 授業 単位の種別と単位数 履修単位: 2
開設学科 電子情報工学科 対象学年 5
開設期 前期 週時間数 4
教科書/教材 教科書:「情報科学のための離散数学」柴田正憲・浅田由良共著(コロナ社),参考書:「離散数学」牛島和夫編著(コロナ社),「計算論への入門」E.キンバー(ピアソンエデュケーションジャパン),「工学のための離散数学」黒澤著(数理工学社),「オートマトン・言語理論の基礎」米田ほか著(近代科学社),など.
担当教員 田添 丈博

到達目標

オートマトン・言語理論,計算の理論・計算の複雑さ,代数系・整数論・有限体,暗号・符号理論に関して,それらの基本的事項を理解し,工学上の応用問題を解決するための数学的知識と計算技術を習得すること.

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1離散数学の基本的な概念に関する問題を解くことができる.離散数学の基本的な概念を説明できる.離散数学の基本的な概念を説明できない.
評価項目2離散数学に関するアルゴリズムを実装することができる.離散数学に関する知識をアルゴリズムに利用することができる.離散数学に関する知識をアルゴリズムに利用することができない.
評価項目3オートマトン・言語理論に関する問題を解くことができる.オートマトン・言語理論の概念について説明できる.オートマトン・言語理論の概念について説明できない.

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

教育方法等

概要:
オートマトンは,現実の機械を抽象化したものとして,計算というものを理論的に考察する場合の基礎である.このような抽象化された機械を用いて,計算が不可能な問題が存在することを示す.計算が可能な場合においても,その計算量の程度についても考察する.また,オートマトンは,文字の並びとしての語,そして,語の集まりである言語を定めるものとして,コンパイラなどの分野で重要である.さらに,集合,写像,関係,代数系などに関して,これらを応用と関連付けて学ぶと,興味深い分野であることを示す.
授業の進め方と授業内容・方法:
・すべての授業内容は,学習・教育到達目標(B)<基礎>およびJABEE基準1(2)(c)に対応する.
・授業は講義・輪講形式で行う.講義中は集中して聴講する.
・「授業計画」における各週の「到達目標」はこの授業で習得する「知識・能力」に相当するものとする.
注意点:
<到達目標の評価方法と基準>下記授業計画の「到達目標」を網羅した問題を2回の中間試験,2回の定期試験で出題し,目標の達成度を評価する.各到達目標に関する重みは同じである.評価結果が100点法で60点以上の場合に目標の達成とする.
<学業成績の評価方法および評価基準>前期中間・前期末・後期中間・学年末の,計4回の試験結果の平均点を最終評価とする.再試験は実施しない.
<単位修得要件>学業成績で60点以上を取得すること.
<あらかじめ要求される基礎知識の範囲>指数・対数・三角関数,数列と級数,微分と積分,順列と組合せ,線形代数の基本事項について理解していること.とくに,本教科の学習には「線形代数Ⅰ」「線形代数Ⅱ」の理解と習得が必要である.
<自己学習>授業で保証する学習時間と,予習・復習(中間試験,定期試験のための学習も含む)及びレポート作成に必要な標準的な学習時間の総計が,90時間に相当する学習内容である.
<注意事項>オートマトン・言語理論,計算の理論・計算の複雑さ,代数系・整数論・有限体,暗号・符号理論は,情報工学のさまざまな分野で利用されており,技術者にとって重要な数学の一分野である.基本的な例題と演習問題に取り組み,内容を十分理解することが大切である.本教科は,後に学習する「代数学特論」(専攻科)に強く関連する教科である.

授業計画

授業内容・方法 週ごとの到達目標
前期
1週 集合
双対性
<集合と写像>
1. 集合と濃度に関する問題を解くことができる.
2週 関数
関数の合成
<集合と写像>
2. 写像に関する問題を解くことができる.
3週 順列・組合せ
多項定理
<集合と写像>
3. 代数的構造に関する問題を解くことができる.
4. 関係,類別と同値類に関する問題を解くことができる.
4週 基数法
論理代数
<集合と写像>
5. 証明の方法に関する問題を解くことができる.
<代数的構造>
10.群・環・体についての問題を解くことができる.
5週 条件文と双条件文
ブール代数
<代数的構造>
11.剰余環についての問題を解くことができる.
12.多項式環についての問題を解くことができる.
6週 論理ゲートと論理回路
カルノー図
<代数的構造>
13.Galois体(有限体)についての問題を解くことができる.
<計算の理論・計算の複雑さ>
8. 計算機械とその言語に関する問題を解くことができる.
7週 述語論理
束縛変数と自由変数
<計算の理論・計算の複雑さ>
9. 計算不可能な問題に関する問題を解くことができる.
10. 計算量と計算の複雑さに関する問題を解くことができる.
11. NP完全問題に関する問題を解くことができる.
8週 中間試験
これまでに学習した内容を説明し,諸量を求めることができる.
9週 グラフの概念と基礎知識
いろいろなグラフ
<グラフ理論>
6. グラフ構造の基本に関する問題を解くことができる.
10週 二つの古典的問題
結婚の問題とラテン方陣
<グラフ理論>
7. オイラー閉路に関する問題を解くことができる.
11週
有向グラフ
<グラフ理論>
8. 木構造の基本に関する問題を解くことができる.
12週 ネットワークプランニング
アルファベットと言語
<グラフ理論>
9. ネットワークフローに関する問題を解くことができる.
<オートマトン・言語理論>
1. 集合,写像等に関する問題を解くことができる.
13週 有限状態機械
有限オートマトン
<オートマトン・言語理論>
2. 有限オートマトンに関する問題を解くことができる.
3. プッシュダウンオートマトンに関する問題を解くことができる.
14週 文脈自由文法
プッシュダウンオートマトン
<オートマトン・言語理論>
4. チューリング機械に関する問題を解くことができる.
5. 線形拘束オートマトンに関する問題を解くことができる.
15週 チューリング機械
オートマトンと言語
<オートマトン・言語理論>
6. オートマトンと形式言語の関係に関する問題を解くことができる.
7. 言語とその階層構造に関する問題を解くことができる.
16週

評価割合

試験課題相互評価態度発表その他合計
総合評価割合10000000100
配点10000000100