English

年度	2025年度	開講部局	先進理工系科学研究科博士課程前期先進理工系科学専攻情報科学プログラム
講義コード	WSN20501	科目区分	専門的教育科目
授業科目名	Computational Complexity Theory
授業科目名 （フリガナ）	コンピューテイショナル　コンプレクシティー　セオリー
英文授業科目名	Computational Complexity Theory
担当教員名	岩本　宙造
担当教員名 (フリガナ)	イワモト　チュウゾウ
開講キャンパス	東広島	開設期	1年次生   後期   ３ターム
曜日・時限・講義室	(3T) 火1-4：工104
授業の方法	講義	授業の方法 【詳細情報】	対面
			講義中心
単位	2.0	週時間	4	使用言語	E : 英語
学習の段階	6 : 大学院専門的レベル
学問分野（分野）	25 : 理工学
学問分野（分科）	02 : 情報科学
対象学生
授業のキーワード	言語理論，並列計算，一様論理回路族，完全性と還元
教職専門科目		教科専門科目
プログラムの中での この授業科目の位置づけ （学部生対象科目のみ）
到達度評価 の評価項目 （学部生対象科目のみ）
授業の目標・概要等	本授業の目標は，計算問題の本質的難しさを解析し，クラスＰやＮＰといった複雑性クラスに分類することである．具体的には，計算問題への入力データの大きさを増やしたとき，計算時間や必要な記憶量がどのように増えるのかを解析する．これは，計算機の能力の実際的な限界を与えるものであり，計算機が現実的な時間で問題を解決できるか否かを決定することを意味する． 授業の概要：計算複雑性理論は，計算問題をその本質的難しさに基づいて分類し，難しさの関係を解明する研究である．本授業では，並列計算モデルの一つである一様論理回路族を取り上げ，本モデルで効率良く計算できる問題のクラスＮＣについて考察する．また，計算の並列化が困難なＰ完全問題や，多項式時間の直列処理では計算できないとみられるＮＰ完全問題などについても解説する．
授業計画	トピック：計算複雑さの理論   (0) ガイダンス（0.5週）   (1) 並列計算の複雑さ       計算機モデル：論理回路族       (a) 回路族とクラスＮＣの定義（２週）       (b) 加算（２週）       (c) 減算（１週）       (d) 乗算（１週）       (e) 除算（１週）   (2) 直列計算の複雑さ       計算機モデル：チューリング機械（ＴＭ）       (a) ＴＭとクラスＤＬＯＧ，Ｐ，ＮＰ（２週）       (b) Ｐ完全問題（２週）       (c) ＮＰ完全問題（３週） (3) まとめ（0.5週）
教科書・参考書等	なし
授業で使用する メディア・機器等
	【詳細情報】	なし
授業で取り入れる 学習手法
予習・復習への アドバイス	エントリー試験や宿題に取り組むこと
履修上の注意 受講条件等
成績評価の基準等	授業への参加態度，レポート
実務経験
実務経験の概要と それに基づく授業内容
メッセージ	本科目は基礎理論なので講義中は深い思考が必要である．
その他
すべての授業科目において，授業改善アンケートを実施していますので，回答に協力してください。 回答に対しては教員からコメントを入力しており，今後の改善につなげていきます。