計算量理論特論[22M2075]

科目名
Course Title
計算量理論特論[22M2075]
Advanced complexity theory
授業言語
Language
Japanese
科目区分・科目種 情報科学コース クラス 理学
CCBM   キャリアデザイン  
単位数 2.0単位 履修年次 12

担当教員 長尾 篤樹
学期 後期
曜日・時限・教室
金曜 7 8 共3-408【情報科学講義室2】

受講条件・その他注意
情報科学科学部科目である「計算基礎論」及び「オートマトンと言語理論」を履修していることが望ましいが,必須ではない.

授業の形態
講義,演習,一部対面授業あり

教科書・参考文献
参考文献:M.Sipser 著「計算理論の基礎 3.複雑さの理論」(英語原著のPDFが検索すると出てきます)
参考文献:パズル通信ニコリ別冊 ザ・ペンシルパズル2021 ISBN:978-4890728473
ISBN:(各自で購入する必要はありません)

ALH区分
通常授業として実施(11・12限等)

評価方法・評価割合
発表=50%,授業への参加態度=40%,ALH(アクティブ・ラーニング・アワー)=10%

主題と目標
この講義では,アルゴリズムの解析を扱います.
まず,アルゴリズムとは何かを再確認し,実用上のアルゴリズムがどのような計算量クラスに属すのかを確認します.
コードを一つ一つ追うのではなく,計算モデルの挙動と人間の挙動との対応について把握することが一つの到達点となる.

授業計画
以下のように進める。
1. 計算モデルとは
・ チューリング機械という計算を扱うモデルを確認します.これにより様々な関数・問題が扱えることを確認しましょう.
. 余裕がある場合は他の計算モデルも紹介します.
2. 計算量クラス
・ 計算モデルが扱える関数・問題の範囲によって関数・問題をクラス分けします.
・ これにより,具体的な実用上の問題,(例えばペンシルパズル等)がそれぞれどのようなクラス分けになるのかを確認しましょう.
3. 完全性の証明
・ 実用上の問題がそのクラスでの完全問題であるか否かを確認するための手法を理解しましょう.
・ 最終的には自分で証明を構築できるようになると完璧です.

時間外学習
離散的な数理演習問題としてペンシルパズル等を利用することを予定している.興味があるものは配布するもの以外にも取り組んでもらいたい.
また,ペンシルパズルに限らず現実問題に対する計算量を扱った文献紹介を授業で行ってもらうため,各自論文を読み込む必要がある.

学生へのメッセージ
「考える」を定量的に評価するためには,まず自分が普段どのように問題に取り組んでいるかを客観的にみる必要があります. パズルを解くという機会からその工程と計算モデルとの対応付けを考えてみましょう.
学期全体を通しての課題をALHとして出題し、レポートにまとめて提出してもらいます.

学生の問い合わせ先
eメール: a-nagao@is.ocha.ac.jp
居室:理学部3号館401室