読者です 読者をやめる 読者になる 読者になる
スポンサーリンク

アルゴリズムの「計算量理論」の講義ノート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...

  • サウスカロライナ大の「計算複雑性理論」の講義ノート,509ページ。

 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...

  • 東大2年生の方によるスライド,72ページ。

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


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

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


電子情報通信学会知識ベース |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



関連する記事:

ゲーム理論の講義ノートPDF。応用を含めた講義資料 (戦略と意思決定の方法論)
http://language-and-engineering.hatenablog.jp/entry/20140516/GameTheoryPDFNot...


量子コンピュータ・量子情報の講義ノートPDF。 量子計算や量子通信の理論を,基礎から応用まで勉強するための教科書や資料
http://language-and-engineering.hatenablog.jp/entry/20140607/QuantumComputati...


「オペレーティングシステム論」の講義資料・ノートPDF。OSのプロセス管理やメモリ管理,ファイルシステムを勉強
http://language-and-engineering.hatenablog.jp/entry/20140510/OperatingSystemL...


「自然言語処理論」の講義ノートPDF。形態素解析や文脈自由文法,知能機械による言語処理の扱い
http://language-and-engineering.hatenablog.jp/entry/20140511/NaturalLanguageP...