| 年度 |
2024年度 |
開講部局 |
情報科学部 |
| 講義コード |
KA205001 |
科目区分 |
専門教育科目 |
| 授業科目名 |
計算理論 |
授業科目名
（フリガナ） |
ケイサンリロン |
| 英文授業科目名 |
Theory of Computing |
| 担当教員名 |
中西 透 |
担当教員名
(フリガナ) |
ナカニシ トオル |
| 開講キャンパス |
東広島 |
開設期 |
3年次生 前期 １ターム |
| 曜日・時限・講義室 |
(1T) 月1-4：工219 |
| 授業の方法 |
講義 |
授業の方法
【詳細情報】 |
|
| 基本的に対面での実施を予定 |
| 単位 |
2.0 |
週時間 |
|
使用言語 |
B
:
日本語・英語 |
| 学習の段階 |
3
:
中級レベル
|
| 学問分野（分野） |
25
:
理工学 |
| 学問分野（分科） |
02
:
情報科学 |
| 対象学生 |
3年次 |
| 授業のキーワード |
有限オートマトン，チューリング機械，計算可能性，計算複雑度 |
| 教職専門科目 |
|
教科専門科目 |
|
プログラムの中での
この授業科目の位置づけ
（学部生対象科目のみ） | システム・情報工学分野の基礎理論について学び，論理的思考能力を身に付ける.
|
|---|
到達度評価
の評価項目
（学部生対象科目のみ） | 電気システム情報プログラム
（能力・技能）
・電気，システム，情報分野の基礎となる概念，知識および手法
・電気，システム，情報分野の基礎概念，知識および手法を具体的・専門的な問題に応用する能力
計算機科学プログラム
（知識・理解）
・D1. 計算機科学の基礎となる理論体系を理解し，科学的論理性に基づいた情報処理技術を駆使して，高次元データを収集・処理するための知識と能力．
（能力・技能）
・A. 情報基盤の開発技術，情報処理技術，データを分析して新しい付加価値を生む技術．
データ科学プログラム
（能力・技能）
・A. 情報基盤の開発技術，情報処理技術，データを分析して新しい付加価値を生む技術．
知能科学プログラム
（知識・理解）
・D1. 人間が持つ高度な知能とその計算機による実現についての体系的な深い理解．
（能力・技能）
・A. 情報基盤の開発技術，情報処理技術，データを分析して新しい付加価値を生む技術． |
|---|
| 授業の目標・概要等 |
計算機（ハードウェア，ソフトウェア）の基本的な数学的性質として，計算可能性（何を計算できるのか？），計算複雑度（どのぐらい速く計算できるのか？）について，計算モデルを用いて理論的に習得することを目標とする．また，集合などの基本的概念および証明技法などを学ぶことにより，論理的思考能力を身につける． |
| 授業計画 |
第1回 講義概要
第2回 数学的概念の復習
第3回 有限オートマトン（１）
第4回 有限オートマトン（２）
第5回 チューリング機械（１）
第6回 チューリング機械（２）
第7回 チューリング機械（３）
第8回 計算可能性（１）
第9回 計算可能性（２）
第10回 計算可能性（３）
第11回 計算可能性（４）
第12回 計算複雑度（１）
第13回 計算複雑度（２）
第14回 計算複雑度（３）
第15回 暗号，演習
期末試験を実施予定 |
| 教科書・参考書等 |
参考書：「計算理論の基礎[原著第２版]」１〜３ Michael Sipser著 共立出版 |
授業で使用する
メディア・機器等 |
|
| 【詳細情報】 |
資料配布．上記の参考書を購入する必要はない． |
授業で取り入れる
学習手法 |
|
予習・復習への
アドバイス |
第1回−第15回 授業内容の復習. 各回で演習を行うので復習しておくこと．
|
履修上の注意
受講条件等 |
|
| 成績評価の基準等 |
評価方法：演習・小テスト・レポート：30%程度, 期末試験：70%程度 |
| 実務経験 |
|
実務経験の概要と
それに基づく授業内容 |
|
| メッセージ |
|
| その他 |
|
すべての授業科目において，授業改善アンケートを実施していますので，回答に協力してください。
回答に対しては教員からコメントを入力しており，今後の改善につなげていきます。 |