計算量理論
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
] [
リンク元
]
開始行:
[[講義日程-2007年度冬学期]]
- 計算量理論(Computational Complexity)
-- 担当：今井 浩 教授
-- 1.5単位
--- 数理：限定選択B
-- 10:15～11:45 理学部７号館(化学教育東館)236号室
-- 参考書
--- Michael R. Garey and David S. Johnson~~Computers and ...
- 計算量理論とは、計算の難しさの学問。
-- 例）n都市TSP~~n頂点の重み付き単純グラフ上の閉路で、各...
--- 素朴な解法~~(n-1)!通りの巡り方での距離を全て計算・比...
--- cf)ある頂点から他の全ての頂点への最短路を求める問題は...
--- TSPはどんなアルゴリズムでも、(最悪の場合)O(n^c)で解く...
- NP完全性の理論
-- NP:Nondeterministic Polynomial,非決定性多項式時間
- n要素全順序集合のソーティング
-- Insert Sort O(n^2)
--- n個の整列されたリストにn+1個目の要素を適切な場所に挿...
-- Bubble Sort O(n^2)
--- リストから順序関係が壊れている部分を探し、正す。
-- Heap Sort O(n log n)
--- 要素からヒープツリーを作って、取り出す。
-- Quick Sort 平均的にはO(n log n)、最悪ではO(n^2)
--- 中間要素を選び、それより大きい部分リストと小さい部分...
-- Merge Sort O(n log n)
--- 分割統治。リストを二つに分け、それぞれをソートし、順...
-- どんなアルゴリズムでもΩ(n log n)の時間がかかる。~~(mem...
- Linear Decision Tree
-- プログラムの実行パスをツリーの形で全て書き表したもの。...
-- 正しいソーティングアルゴリズムでは、出力になり得る組み...
- 行列積
-- A,B ∈ R^(n×n)~~C = AB~~c[i][j] = Σ[k=1,n]a[i][k]b[k][j...
-- 行列をうまく分割して計算するとO(n^log[2]7)≒O(n^2.807)...
-- 現在ではO(n^2.386)まで下げられている。下限はΩ(n^2)以上...
- 漸近的性質~~関数f,g:N⇒Nについて
-- O~~f(n) = O(g(n))⇔∃n,∃c,∀m≧n. f(m)≦c*g(m)
-- Ω~~f(n) = Ω(g(n))⇔∃n,∃c,∀m≧n. f(m)≧c*g(m)
-- Θ~~f(n) = Θ(g(n))⇔f(n)=O(g(n))∧f(n)=Ω(g(n))
-- o~~f(n)=o(g(n))⇔lim[n→∞]f(n)/g(n)=0
- 入力サイズnについて、アルゴリズムAの計算時間t(n)がどう...
-- P: t(n)がnの多項式のオーダーとなるアルゴリズムが存在す...
-- EXP:t(n)がnの指数関数のオーダーとなるアルゴリズムが存...
-- P⊂EXP, nを十分に大きくすると常にEXPの問題の方が大きく...
- 計算の難しさ。（上に行くほど難しい。）
-- undecidable:計算不能、アルゴリズムが存在しない。~~Turi...
-- decidable:計算可能、アルゴリズムが存在する。
--- 多重指数オーダーで解ける。 Presburger Arithmetic
-- intractable:実行不可能、多項式オーダーでは解けない。
--- NP完全問題。非決定性チューリングマシンで多項式オーダ...
-- tractable:実行可能、多項式オーダーで解ける。
- アルゴリズムとは何か
-- 計算とは、状態遷移だ。
--- Turing Machine~~有限長のプログラム(内部状態)と無限の...
--- TM=(Γ,Σ,Q,δ)~~Γ=Σ∪{b} テープのセルに書く記号の集合。
--- Σ 問題を記述する記号の集合。alphabet
--- Q 機械の内部状態の集合。有限。~~q[0]：初期状態~~q[y]...
--- δ:Q×Γ→Q×Γ×{+1,-1} 遷移関数。現在の状態と現在地のテー...
--- 初期状態から、遷移関数に従ってテープ上に記録されたデ...
--- 現在のコンピュータで多項式時間で解ける問題はチューリ...
--- δが一価の関数→決定性チューリングマシン~~δが多価関数→...
- 決定性チューリングマシン(DTM,Deterministic Turing Machi...
-- 通常のチューリングマシン。同じ入力に対して同じ出力を返...
-- 計算資源、サイズnの入力に対して最悪の場合の量を指す。~...
-- P：チューリングマシンでの時間計算量が、入力のサイズの...
- PTime ⊂ PSpace ⊂ ExpTime
-- 空間計算量がnの多項式で押えられる問題は、時間計算量はe...
-- 無限ループに陥らないアルゴリズムの実行中には、状態遷移...
- 非決定性チューリングマシン(NTM,Nondeterministic Turing ...
-- 同時に複数の状態をとりうる、遷移関数が多価関数になりう...
-- 計算資源~~time complexity：NTMを次々に分岐させながらス...
- NP：非決定性チューリングマシンでの時間計算量が、入力サ...
- PTime ⊂ NP ⊂ PSpace
-- NTMをDTMでシミュレート。各ステップを幅優先探索。~~バッ...
- 並列計算をしたときや、計算機が速くなったときの、同一時...
-- プロセッサ数がp倍になったときに、~~O(n) p倍~~O(n^2) √p...
- 多項式時間変換(Polynomial-time Reducibility)
-- ハミルトン閉路(HC,Hamilton Circuit)問題~~入力:グラフ~~...
-- 巡回セールスマン問題の判定~~完全グラフ。距離関数。パラ...
-- ある問題クラスΠの、任意のインスタンスが、別のあるクラ...
-- ハミルトン閉路問題は、多項式時間で巡回セールスマン問題...
- NTM(Oracle版)
-- Guessing Module付きのDTM
-- 入力xがセル1からセル|x|まで与えられている。~
「Advice」をGuessing Moduleがセル(-1)から左に書く。~
Guessing Moduleを停止してDTMとして起動。処理。停止。
-- NTMでどの分岐をすべきかをあらかじめ外部から与えたもの。
-- NTMを使うと多項式時間で解ける問題は、DTMで多項式時間で...
- 命題論理の充足可能性判定問題(SAT,Satisfiability)
-- 入力：CNF命題論理式(CNF,Conjunctive Normal Form,∧標準形)
-- 出力：入力の論理式を満たす真偽値の組み合わせがあればTr...
-- 入力は論理変数をn個持った論理式で、論理変数と¬と∨から...
うまく論理変数の値を選んだとき、論理式全体を真にできると...
どの組み合わせを選んでも真にできないとき、恒偽、充足不可...
-- この充足可能正門第
終了行:
[[講義日程-2007年度冬学期]]
- 計算量理論(Computational Complexity)
-- 担当：今井 浩 教授
-- 1.5単位
--- 数理：限定選択B
-- 10:15～11:45 理学部７号館(化学教育東館)236号室
-- 参考書
--- Michael R. Garey and David S. Johnson~~Computers and ...
- 計算量理論とは、計算の難しさの学問。
-- 例）n都市TSP~~n頂点の重み付き単純グラフ上の閉路で、各...
--- 素朴な解法~~(n-1)!通りの巡り方での距離を全て計算・比...
--- cf)ある頂点から他の全ての頂点への最短路を求める問題は...
--- TSPはどんなアルゴリズムでも、(最悪の場合)O(n^c)で解く...
- NP完全性の理論
-- NP:Nondeterministic Polynomial,非決定性多項式時間
- n要素全順序集合のソーティング
-- Insert Sort O(n^2)
--- n個の整列されたリストにn+1個目の要素を適切な場所に挿...
-- Bubble Sort O(n^2)
--- リストから順序関係が壊れている部分を探し、正す。
-- Heap Sort O(n log n)
--- 要素からヒープツリーを作って、取り出す。
-- Quick Sort 平均的にはO(n log n)、最悪ではO(n^2)
--- 中間要素を選び、それより大きい部分リストと小さい部分...
-- Merge Sort O(n log n)
--- 分割統治。リストを二つに分け、それぞれをソートし、順...
-- どんなアルゴリズムでもΩ(n log n)の時間がかかる。~~(mem...
- Linear Decision Tree
-- プログラムの実行パスをツリーの形で全て書き表したもの。...
-- 正しいソーティングアルゴリズムでは、出力になり得る組み...
- 行列積
-- A,B ∈ R^(n×n)~~C = AB~~c[i][j] = Σ[k=1,n]a[i][k]b[k][j...
-- 行列をうまく分割して計算するとO(n^log[2]7)≒O(n^2.807)...
-- 現在ではO(n^2.386)まで下げられている。下限はΩ(n^2)以上...
- 漸近的性質~~関数f,g:N⇒Nについて
-- O~~f(n) = O(g(n))⇔∃n,∃c,∀m≧n. f(m)≦c*g(m)
-- Ω~~f(n) = Ω(g(n))⇔∃n,∃c,∀m≧n. f(m)≧c*g(m)
-- Θ~~f(n) = Θ(g(n))⇔f(n)=O(g(n))∧f(n)=Ω(g(n))
-- o~~f(n)=o(g(n))⇔lim[n→∞]f(n)/g(n)=0
- 入力サイズnについて、アルゴリズムAの計算時間t(n)がどう...
-- P: t(n)がnの多項式のオーダーとなるアルゴリズムが存在す...
-- EXP:t(n)がnの指数関数のオーダーとなるアルゴリズムが存...
-- P⊂EXP, nを十分に大きくすると常にEXPの問題の方が大きく...
- 計算の難しさ。（上に行くほど難しい。）
-- undecidable:計算不能、アルゴリズムが存在しない。~~Turi...
-- decidable:計算可能、アルゴリズムが存在する。
--- 多重指数オーダーで解ける。 Presburger Arithmetic
-- intractable:実行不可能、多項式オーダーでは解けない。
--- NP完全問題。非決定性チューリングマシンで多項式オーダ...
-- tractable:実行可能、多項式オーダーで解ける。
- アルゴリズムとは何か
-- 計算とは、状態遷移だ。
--- Turing Machine~~有限長のプログラム(内部状態)と無限の...
--- TM=(Γ,Σ,Q,δ)~~Γ=Σ∪{b} テープのセルに書く記号の集合。
--- Σ 問題を記述する記号の集合。alphabet
--- Q 機械の内部状態の集合。有限。~~q[0]：初期状態~~q[y]...
--- δ:Q×Γ→Q×Γ×{+1,-1} 遷移関数。現在の状態と現在地のテー...
--- 初期状態から、遷移関数に従ってテープ上に記録されたデ...
--- 現在のコンピュータで多項式時間で解ける問題はチューリ...
--- δが一価の関数→決定性チューリングマシン~~δが多価関数→...
- 決定性チューリングマシン(DTM,Deterministic Turing Machi...
-- 通常のチューリングマシン。同じ入力に対して同じ出力を返...
-- 計算資源、サイズnの入力に対して最悪の場合の量を指す。~...
-- P：チューリングマシンでの時間計算量が、入力のサイズの...
- PTime ⊂ PSpace ⊂ ExpTime
-- 空間計算量がnの多項式で押えられる問題は、時間計算量はe...
-- 無限ループに陥らないアルゴリズムの実行中には、状態遷移...
- 非決定性チューリングマシン(NTM,Nondeterministic Turing ...
-- 同時に複数の状態をとりうる、遷移関数が多価関数になりう...
-- 計算資源~~time complexity：NTMを次々に分岐させながらス...
- NP：非決定性チューリングマシンでの時間計算量が、入力サ...
- PTime ⊂ NP ⊂ PSpace
-- NTMをDTMでシミュレート。各ステップを幅優先探索。~~バッ...
- 並列計算をしたときや、計算機が速くなったときの、同一時...
-- プロセッサ数がp倍になったときに、~~O(n) p倍~~O(n^2) √p...
- 多項式時間変換(Polynomial-time Reducibility)
-- ハミルトン閉路(HC,Hamilton Circuit)問題~~入力:グラフ~~...
-- 巡回セールスマン問題の判定~~完全グラフ。距離関数。パラ...
-- ある問題クラスΠの、任意のインスタンスが、別のあるクラ...
-- ハミルトン閉路問題は、多項式時間で巡回セールスマン問題...
- NTM(Oracle版)
-- Guessing Module付きのDTM
-- 入力xがセル1からセル|x|まで与えられている。~
「Advice」をGuessing Moduleがセル(-1)から左に書く。~
Guessing Moduleを停止してDTMとして起動。処理。停止。
-- NTMでどの分岐をすべきかをあらかじめ外部から与えたもの。
-- NTMを使うと多項式時間で解ける問題は、DTMで多項式時間で...
- 命題論理の充足可能性判定問題(SAT,Satisfiability)
-- 入力：CNF命題論理式(CNF,Conjunctive Normal Form,∧標準形)
-- 出力：入力の論理式を満たす真偽値の組み合わせがあればTr...
-- 入力は論理変数をn個持った論理式で、論理変数と¬と∨から...
うまく論理変数の値を選んだとき、論理式全体を真にできると...
どの組み合わせを選んでも真にできないとき、恒偽、充足不可...
-- この充足可能正門第
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
