情報数学

科目基礎情報

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

到達目標

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

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
V-D-7．集合に関する基本的な概念を理解し、集合演算を実行できる。	集合に関する基本的な概念を理解し、集合演算を実行できる。	集合に関する基本的な概念を理解し、集合演算を大凡、実行できる。	集合に関する基本的な概念を理解し、集合演算を実行でない。
V-D-7．集合の間の関係（関数）に関する基本的な概念を説明できる。	集合の間の関係（関数）に関する基本的な概念を説明できる。	集合の間の関係（関数）に関する基本的な概念を大凡、説明できる。	集合の間の関係（関数）に関する基本的な概念を説明できない。
V-D-7．ブール代数に関する基本的な概念を説明できる。	ブール代数に関する基本的な概念を説明できる。	ブール代数に関する基本的な概念を大凡、説明できる。	ブール代数に関する基本的な概念を説明できない。
V-D-7．論理代数と述語論理に関する基本的な概念を説明できる。	論理代数と述語論理に関する基本的な概念を説明できる。	論理代数と述語論理に関する基本的な概念を大凡、説明できる。	論理代数と述語論理に関する基本的な概念を説明できない。
V-D-5．形式言語の概念について説明できる。	形式言語の概念について説明できる。	形式言語の概念について大凡、説明できる。	形式言語の概念について説明できない。
V-D-5．オートマトンの概念について説明できる。	オートマトンの概念について説明できる。	オートマトンの概念について大凡、説明できる。	オートマトンの概念について説明できない。
V-D-１．プログラミング言語は計算モデルによって分類されることを理解している。	プログラミング言語は計算モデルによって分類されることを理解している。	プログラミング言語は計算モデルによって分類されることを大凡、理解している。	プログラミング言語は計算モデルによって分類されることを理解していない。
V-D-１．主要な計算モデルを説明できる。	主要な計算モデルを説明できる。	主要な計算モデルを大凡、説明できる。	主要な計算モデルを説明できない。

教育方法等

概要:

情報数学の授業では大きく分けて二つの内容を学ぶ。一つには情報工学で使われる様々な概念を形式的に表現し説明するための数学の基礎として集合、グラフ、記号論理を学ぶ。もう一つには、チューリング計算機を基礎とする計算可能性と計算理論のいくつかの話題を学ぶ。特にP ?= NP問題は現在でも最重要な未解決問題の一つであり、いつの日にか学生諸君により解決されることを期待する。

授業の進め方・方法:

毎回の授業では、可能な限り問題演習に取組む。
中間時期の試験40%、定期試験60%として評価する。合格は60点以上である。
不合格の場合には、定期試験と同じ試験範囲で、再試験を1度のみ実施する。
この科目は学修単位科目のため、事前・事後学習として「自己学習課題」を実施します。

注意点:

充分に予習・復習を済ませて授業に臨まなくてはならない。また、授業に集中できるよう、普段から睡眠・食事・休息に気を配り、体調を整えておくこと。
この授業では高専3年生までに身に付けた数学的な資質・能力を活用する。
授業を受講する他に、自学自習時間(60時間)が必要である。

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	数学的基礎（１）集合・写像	集合・写像に関する基本的な概念を理解し、集合演算を実行できる。
		2週	数学的基礎（１）集合・写像	集合・写像に関する基本的な概念を理解し、集合演算を実行できる。
		3週	数学的基礎（１）集合・写像	集合・写像に関する基本的な概念を理解し、集合演算を実行できる。
		4週	数学的基礎（２）グラフ	離散数学（グラフ理論）に関する知識とアルゴリズムの関連を理解している。
		5週	数学的基礎（２）グラフ	離散数学（グラフ理論）に関する知識とアルゴリズムの関連を理解している。
		6週	数学的基礎（２）グラフ	離散数学（グラフ理論）に関する知識とアルゴリズムの関連を理解している。
		7週	数学的基礎（３）命題論理	命題論理（ブール代数）に関する基本的な概念を説明できる。
		8週	試験（達成度評価試験）
	2ndQ
		9週	数学的基礎（３）命題論理	命題論理（ブール代数）に関する基本的な概念を説明できる。
		10週	数学的基礎（４）述語論理	述語論理に関する基本的な概念を説明できる。
		11週	数学的基礎（４）述語論理	述語論理に関する基本的な概念を説明できる。
		12週	正規言語	有限オートマトンの概念について説明できる。
		13週	文脈自由言語	形式言語の概念について説明できる。
		14週	チューリング機械	チューリング機械に基づき計算可能性とアルゴリズムの複雑さについて説明できる。
		15週	チューリング機械	チューリング機械に基づき計算可能性とアルゴリズムの複雑さについて説明できる。
		16週	試験(前期末)

評価割合

	試験	自己学習課題	合計
総合評価割合	80	20	100
基礎的能力	50	10	60
専門的能力	30	10	40