【授業の目的】
機械的手計算の数理モデルであるチューリングマシン、およびその等価な定式化である部分帰納的関数における計算可能性の理論を学ぶ。
【授業の到達目標】
「機械的計算」の数学的モデル化であるチューリングマシンの概念を中心にして、「機械的に手計算が出来る（アルゴリズムが存在する）問題」および、その効率性を特徴づけるための方法論（いわゆる「計算可能性」と「計算複雑性」の理論）を身につける
【授業概要（キーワード）】
チューリングマシン、非決定性チューリングマシン、判定可能性、計算量、クラスP、クラスNP、NP完全性、多項式時間還元、学生主体型授業
【学生主体型授業（アクティブラーニング）について】
A-1．ミニッツペーパー、リフレクションペーパー等によって、自分の考えや意見をまとめ、文章を記述し提出する機会がある。：76～100％
B-1．学生同士の話し合いの中で互いの意見に触れる機会がある。：76～100％
C-1．自分の意見をまとめて発表する機会がある。：76～100％
D-1．演習、実習、実験等を行う機会がある。：76～100％
A-2．小レポート等により、事前学習（下調べ、調査等含む）が必要な知識の上に思考力を問う形での文章を記述する機会がある。：76～100％
D-2．事前学習（下調べ、調査等含む）で習得した知識等を踏まえて演習、実習、実験等を行う機会がある。：76～100％
【科目の位置付け】
この授業は，情報科学に関する基本的な知識として、計算モデルと計算モデルの間の関係に関する原理、アルゴリズムの設計方法、計算の限界や効率に関する原理を理解する力を身につけるものである。
【SDGs（持続可能な開発目標）】
04.質の高い教育をみんなに
09.産業と技術革新の基盤をつくろう
【授業計画】
・授業の方法
授業は講義形式で行うが、能動的学習を促すため、各回につき、講義内容の理解に必要な演習問題を学生に解かせる時間を設けることにより、学生主体型授業を展開する。
・日程
第１回：コンピュータで解けない問題は存在するか？計算の効率を如何にして測るか？（「計算可能性」および「計算の複雑性」の理論とは何か）
第２回：チューリングマシン入門（記法・時点表示・遷移図）
第３回：様々なチューリングマシンの等価性
第４回：帰納的加算言語と帰納的言語
第８回：チューリング機械の停止問題の決定不能性
第９回：決定性チューリングマシンとクラスＰ
第１０回：非決定性チューリングマシンとクラスＮＰ
第１１回：多項式時間還元
第１２回：ＳＡＴ問題のＮＰ完全性
第１３回：制限された形の充足可能性問題（ＣＳＡＴ・３ＳＡＴのＮＰ完全性）
第１４回：独立集合問題と頂点被覆問題
第１５回：クラスＮＰの補集合とＮＰ完全性
【学習の方法・準備学修に必要な学修時間の目安】
・受講のあり方
基本的に講義形式なので、理解出来ないところを残さないようにする。授業中の質問についても、積極的に行って頂いて構わない。
・授業時間外学習（予習・復習）のアドバイス
１）自主的な学修時間の目安は４時間／週です。（注）大学設置基準で、1単位の授業科目は45時間の学修を必要とする内容をもって構成することが標準と定められています。
２）授業の進捗状況に応じて、適宜講義の最後に宿題を出しますので、出された週の翌週までに、これを完成させ、授業内容の理解を深めるように努力して下さい。
【成績の評価】
・基準
期末試験と授業中に実施する演習の得点を合算して評価得点を算出し，それをもとに評価を決定します．
・方法
期末試験 60％ + 授業中に実施する演習および宿題 40% として評価する。
【テキスト・参考書】
授業の初日と、その後の進展に沿って数種類の本を紹介する。
参考書：J.ホップクロフト、R.モトワニ、J.ウルマン 著「オートマトン 言語理論 計算論II(第２版)」サイエンス社
参考書：マイケル・シプサ 著『計算理論の基礎』、渡辺 治 他訳、共立出版
参考書：松原・大島・藤田 他著「IT Text 離散数学」オーム社 など
【その他】
・学生へのメッセージ
基本的なところから地道にコツコツと学習を積み重ねることが重要である。
・オフィス・アワー
感染拡大防止の観点から、まず、webclssなどを利用し、メールによるコンタクトを取って下さい。
随時オンラインにより、対応致します。
（これはコロナ禍以前の記載内容です。）授業時間外に学生の質問に答える「オフィスアワー」を佐久間研究室（地域教育文化学部２号館４階システム情報資料室Ⅲ）において、水曜日の１８時００分から２０時００分までとしますが、これに限らず在室している時は随時対応します。
|