アルゴリズムの「計算量理論」の講義ノートPDF。複雑性クラスP/NPの分類や「計算可能性」の理論を，独学で学ぶ教科書

講義ノートの目次へ

アルゴリズムの計算量理論の講義ノートPDF。

チューリングマシンやオートマトン，ラムダ計算などを使って，アルゴリズムの複雑さを判定する。

例えば，処理の複雑さを「P」と「NP」のクラスに分類したり（＝計算複雑性），

ある処理が決して終わらないので実行不可能だと判定したり（＝計算可能性）。

独学に使える資料を集めた。

※計算量理論とあわせて学習するとよいのは，ラムダ計算（ノート）や，グラフ理論・組み合わせ最適化（ノート）など。

ラムダ計算がわかれば「計算」を抽象化して扱える。組み合わせ最適化は，計算困難な問題の具体例を学べる。

計算量理論（計算複雑性・計算可能性）の講義ノート

計算量理論の，クラスPとNPからの入門を学べるノート：

計算量の理論
http://www.jaist.ac.jp/~uehara/course...

北陸先端大の講義スライド。

　(1)計算の基本要素
　(2)計算不可能性の証明と対角線論法
　(3)クラスNP
　(4)時間量クラス間の関係
　(5)多項式時間還元可能性
　(6)多項式時間還元可能性にもとづく完全性

計算量理論 - TOKYO TECH OCW
http://www.ocw.titech.ac.jp/index.php...

東工大の講義資料。

　1. アルゴリズムの記述法（計算モデル），時間計算量の測り方
　2. 階層定理
　3. クラスNP
　4. 様々な計算量クラス：回路クラス，乱択計算クラス
　5. 多項式時間還元可能性
　6. SAT のNP-完全性
　7. 計算量理論に関する最近の話題

計算量理論
http://www2.kobe-u.ac.jp/~ky/complexity/

神戸大の講義スライド。

NP 完全性に関する用語などの定義を学ぶ．基本的な NP完全問題について知る．NP完全性の証明法について学ぶ．

　計算量理論の入門
　NP完全性の定義
　基本的なNP完全問題
　NP完全性を証明する技法

情報数理学2008
http://www.akita-pu.ac.jp/system/elec...

秋田県立大の講義資料。

　第1回オートマトンと正規言語
　第2回オートマトンと正規言語の等価性
　第3回プッシュダウンオートマトンと文脈自由文法
　第4回プッシュダウンオートマトンと文脈自由文法の等価性
　第5回チューリングマシンと計算
　第6回チューリングマシンの符号化と計算可能性
　第7回時間限定チューリングマシンとクラスP
　第8回クラスNPと多項式時間帰着
　第9回NP完全問題とNP困難問題
　第10回クラスPとクラスNP完全の境界
　第11回疑多項式時間アルゴリズムと動的計画法
　第12回緩和法と分枝限定法
　第13回近似アルゴリズム入門
　第14回プライマルデュアル法

Computational Complexity:　A Modern Approach
http://www.math.sc.edu/~cooper/math77...

サウスカロライナ大の「計算複雑性理論」の講義ノート，５０９ページ。

　Part I: Basic Complexity Classes
　Part II: Lower bounds for concrete computational models
　Part III: Advanced topics

東工大の「計算機科学概論」の講義ノートより：

アルゴリズムの理論 4.1 計算の複雑さ
http://www.is.titech.ac.jp/~sassa/kei...

計算量とP/NP

4.2 計算不可能性
http://www.is.titech.ac.jp/~sassa/kei...

計算不可能，プログラムの正当性，停止性

チューリングマシンと計算可能性についての講義ノート：

計算機数学(情報理工学科)・電子計算機概論I(数学科)
http://pweb.cc.sophia.ac.jp/tsunogai/...

上智大の講義スライド。

計算機におけるデータの取扱いや計算の原理について軽く説明した後、計算の理論の入門として、計算モデルによる「計算」の定式化・計算可能性の理論・計算量の理論の初歩を紹介し、幾つかの基礎的な数理アルゴリズムについても触れる。

　「計算」の定式化
　計算のモデル化 : 有限オートマトン・チューリング機械など
　言語と文法 : 正規言語・文脈自由言語など
　計算可能性の理論の入門まで : 普遍チューリング機械と対角線論法
　計算量の理論の入門まで
　基礎的な数理アルゴリズムの例

アルゴリズム論
http://edu.net.c.dendai.ac.jp/algorit...

東京電機大の講義資料。Webページとして閲覧できる。

　第 1 回 Turing 機械
　第 2 回 Turing 機械のプログラミング
　第 3 回計算量理論
　第 4 回万能 Turing 機械
　第 5 回停止問題
　第 6 回線形加速定理、階層定理
　第 7 回下限
　第 8 回非決定性(1),オートマトン
　第 9 回非決定性(2)、完全問題
　第 10 回 NP完全問題

計算理論I（チューリング機械と決定不能性）
http://www.aist-nara.ac.jp/~yasumoto/...

奈良先端大の講義スライド。練習問題と解答つき。

　1. チューリング機械
　2. チューリング機械の拡張
　3. TMが受理する言語の性質と万能チューリング機械
　4. 決定不能な問題
　5. 帰着による決定不能性の証明法
　付録：ポストの対応問題の決定不能性の証明法

2010年度後期・数理科学展望I「計算可能性とラムダ計算」
http://www.math.nagoya-u.ac.jp/~garri...

名古屋大の講義ノート。ラムダ計算も扱う。

　第1回 12月20日 Turing機械と計算可能性
　第2回 12月27日万能Turing機械・判定不能な問題
　第3回 1月17日ラムダ計算
　第4回 1月24日ラムダ計算のTuring完全性
　第5回 1月31日帰納的関数

講義ではないが，学習に役立つ資料：

「解けない問題」を知ろう
http://hos.ac/slides/20120319_reducti...

東大２年生の方によるスライド，７２ページ。

　計算量に関して
　PとNP
　NP完全
　決定不能（停止問題など）

P対NP問題（解決したら100万ドル）
http://www.ics.nara-wu.ac.jp/jp/event...

ミレニアム懸賞問題の「P≠NP予想」についてのスライド。５８ページ。

電子情報通信学会知識ベース｜2編　計算論とオートマトン
http://www.ieice-hbkb.org/portal/doc_...

知識ベース。

　4章チューリング機械
　　4-1 チューリング機械
　　4-2 句構造文法
　　4-3 万能チューリング機械
　　4-4 停止問題と決定不能性
　　4-5 帰納的可算
　　4-6 チャーチ・チューリングの定立
　5章決定性，非決定性計算の複雑さ
　　5-1 クラスPとNP
　　5-2 階層定理
　　5-3 多項式階層
　　5-4 領域計算量
　6章様々な計算モデルにおける計算複雑さ
　　6-1 回路計算量
　　6-2 通信計算量
　　6-3 乱択計算
　　6-4 量子計算
　　6-5 対話型証明系

電子情報通信学会知識ベース｜3編　アルゴリズムとデータ構造
http://www.ieice-hbkb.org/portal/doc_...

同上。

　1章　アルゴリズムとアルゴリズム解析
　　1-1 アルゴリズム
　　1-2 計算モデルとアルゴリズムの表記
　　1-3 アルゴリズム解析と計算量

動画で学ぶ：

計算量理論の「P・NP」について勉強できるYoutube動画
http://computer-technology.hateblo.jp/entry/20140613/p1