情報数学

科目基礎情報

学校 苫小牧工業高等専門学校 開講年度 2018
授業科目 情報数学
科目番号 116889 科目区分 専門 / 必修
授業形態 授業 単位の種別と単位数 学修単位: 3
開設学科 情報工学科 対象学年 4
開設期 通年 週時間数 2
教科書/教材 教科書:柴田 正憲、浅田 由良「情報科学のための離散数学」コロナ社/参考図書:石村 園子「やさしく学べる離散数学」共立出版、M. シプサ「計算理論の基礎」共立出版、E.キンバー、C.スミス「計算論への入門」ピアソン・エデュケーション、丸岡 章「計算理論とオートマトン言語理論」サイエンス社、M. Sipser, "Introduction to the Theory of Computation," 2nd. ed., Course Technology, 2006.
担当教員 川口 雄一

到達目標

1.集合・写像を用いた記述を説明し表現できる。
2.グラフを用いた記述を説明し表現できる。
3.論理式を用いた記述を説明し表現できる。
4.有限オートマトンと形式文法・言語の関係を説明できる。
5.チューリング機械と計算可能性の関係を説明できる。
6.チューリング機械に基づき、アルゴリズムの複雑さを説明できる。

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
1.集合・写像を用いた記述を説明し表現できる。集合・写像を用いた記述を説明し表現できる。集合・写像を用いた記述を、大凡、説明し表現できる。集合・写像を用いた記述を説明し表現できない。
2.グラフを用いた記述を説明し表現できる。グラフ用いた記述を説明し表現できる。グラフ用いた記述を、大凡、説明し表現できる。グラフ用いた記述を説明し表現できない。
3.論理式を用いた記述を説明し表現できる。論理式を用いた記述を説明し表現できる。論理式を用いた記述を、大凡、説明し表現できる。論理式を用いた記述を説明し表現できない。
4.有限オートマトンと形式文法・言語の関係を説明できる。有限オートマトンと形式文法・言語の関係を説明できる。有限オートマトンと形式文法・言語の関係を、大凡、説明できる。有限オートマトンと形式文法・言語の関係を説明できない。
5.チューリング機械と計算可能性の関係を説明できる。チューリング機械と計算可能性の関係を説明できる。チューリング機械と計算可能性の関係を、大凡、説明できる。チューリング機械と計算可能性の関係を説明できない。
6.チューリング機械に基づき、アルゴリズムの複雑さを説明できる。チューリング機械に基づき、アルゴリズムの複雑さを説明できる。チューリング機械に基づき、アルゴリズムの複雑さを、大凡、説明できる。チューリング機械に基づき、アルゴリズムの複雑さを説明できない。

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

JABEE基準1 学習・教育到達目標 (c), JABEE基準1 学習・教育到達目標 (e), JABEE基準1 学習・教育到達目標 (g), 学習目標 Ⅱ, 学校目標 D(工学基礎), 学科目標 D(工学基礎), 本科の点検項目 D-ⅳ, 学校目標 E(継続的学習), 本科の点検項目 E-ⅱ, 学校目標 F(専門の実践技術), 学科目標 F(専門の実践技術) , 本科の点検項目 F-ⅰ

教育方法等

概要:
情報数学の授業では大きく分けて二つの内容を学ぶ。一つには情報工学で使われる様々な概念を形式的に表現し説明するための数学の基礎として集合、グラフ、記号論理を学ぶ。もう一つには、チューリング計算機を基礎とする計算可能性と計算理論のいくつかの話題を学ぶ。特にP ?= NP問題は現在でも最重要な未解決問題の一つであり、いつの日にか学生諸君により解決されることを期待する。
授業の進め方と授業内容・方法:
毎回の授業では、可能な限り問題演習に取組む。
前期・後期ともに、中間時期の試験40%、定期試験60%として評価する。前期と後期を合算して学年成績とする。合格は60点以上である。
不合格の場合には、定期試験と同じ試験範囲で、再試験を1度のみ実施する。
注意点:
充分に予習・復習を済ませて授業に臨まなくてはならない。また、授業に集中できるよう、普段から睡眠・食事・休息に気を配り、体調を整えておくこと。
高専3年生までに学んだ基本的な数学の知識・技能が必要である。授業を受講する他に、自学自習(75時間以上)が必要である。

授業計画

授業内容・方法 週ごとの到達目標
前期
1週 数学的基礎(1)集合・写像 集合・写像に関する基本的な概念を理解し、集合演算を実行できる。
2週 数学的基礎(1)集合・写像 集合・写像に関する基本的な概念を理解し、集合演算を実行できる。
3週 数学的基礎(1)集合・写像 集合・写像に関する基本的な概念を理解し、集合演算を実行できる。
4週 数学的基礎(1)集合・写像 集合・写像に関する基本的な概念を理解し、集合演算を実行できる。
5週 数学的基礎(2)グラフ 離散数学(グラフ理論)に関する知識とアルゴリズムの関連を理解している。
6週 数学的基礎(2)グラフ 離散数学(グラフ理論)に関する知識とアルゴリズムの関連を理解している。
7週 数学的基礎(2)グラフ 離散数学(グラフ理論)に関する知識とアルゴリズムの関連を理解している。
8週 試験(前期中間)
9週 数学的基礎(3)命題論理 命題論理(ブール代数)に関する基本的な概念を説明できる。
10週 数学的基礎(3)命題論理 命題論理(ブール代数)に関する基本的な概念を説明できる。
11週 数学的基礎(4)述語論理 論理代数と述語論理に関する基本的な概念を説明できる。
12週 数学的基礎(4)述語論理 論理代数と述語論理に関する基本的な概念を説明できる。
13週 正規言語 有限オートマトンの概念について説明できる。
14週 文脈自由言語 形式言語の概念について説明できる。
15週 試験(前期末)
16週
後期
1週 計算可能性(1)TM TMに基づき、アルゴリズムの概念を説明できる。
2週 計算可能性(1)TM TMに基づき、アルゴリズムの概念を説明できる。
3週 計算可能性(1)TM TMに基づき、アルゴリズムの概念を説明できる。
4週 計算可能性(2)決定可能性 与えられたアルゴリズムが問題を解決していく過程を説明できる。
5週 計算可能性(2)決定可能性 与えられたアルゴリズムが問題を解決していく過程を説明できる。
6週 計算可能性(3)決定不能性 与えられたアルゴリズムが問題を解決していく過程を説明できる。
7週 計算可能性(3)決定不能性 与えられたアルゴリズムが問題を解決していく過程を説明できる。
8週 試験(後期中間)
9週 計算の複雑さ(1)時間計算量 時間計算量によってアルゴリズムを比較・評価できることを理解している。
10週 計算の複雑さ(1)時間計算量 時間計算量によってアルゴリズムを比較・評価できることを理解している。
11週 計算の複雑さ(2)クラスP 問題を解決する複数のアルゴリズムを計算量等の観点から比較できる。
12週 計算の複雑さ(2)クラスP 問題を解決する複数のアルゴリズムを計算量等の観点から比較できる。
13週 計算の複雑さ(3)クラスNP 問題を解決する複数のアルゴリズムを計算量等の観点から比較できる。
14週 計算の複雑さ(3)クラスNP 問題を解決する複数のアルゴリズムを計算量等の観点から比較できる。
15週 計算の複雑さ(4)NP完全 問題を解決する複数のアルゴリズムを計算量等の観点から比較できる。
16週 試験(学年末)

評価割合

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