計算の理論 II 時間量と領域量 月曜4校時 大月美佳 2019/9/13 佐賀大学理工学部知能情報システム学科

今日の講義 前回復習 時間量と領域量 space(x), time(x) O記号 カウンタ NTIME(T(n)), NSPACE(S(n)), … 領域構成可能、時間構成可能 2019/9/13 佐賀大学理工学部知能情報システム学科

講義の前に 今後の日程(再掲) 休講・補講について レポートについて 試験 1/26は休講（学会関連） 1/21と1/22と1/30が補講(時間は一緒) レポートについて 今日大レポート回収(20点配点) 試験 2/9が試験(40点配点) 2019/9/13 佐賀大学理工学部知能情報システム学科

時間量（ステップ数） timeM(x) xを受理するMの最小ステップ。 timeM(x)=min{ t | ある受理計算状態D(x)に 対してC0(x)├tM D(x)} timeM(x)≧|x| 入力ヘッドは全ての入力記号を読んで 右エンドマーカに到達するから。 2019/9/13 佐賀大学理工学部知能情報システム学科

領域量（ます目の量） space(x) Mがxを領域sで受理 xを受理するMの計算 α: C0(x)├ C1(x) …├ Ct(x) space(α)=max{hi(j)| 0≦j≦t, 1≦i≦k } ただし、 Cj(x): (pj , (h(j), ￠x$), (h1(j), ξ1(j)), …, (hk(j), ξk(j))) (0≦j≦t) spaceM(x)=min{ space(α) | ある受理計算状態 D(x)に対してα: C0(x)├*M D(x)} spaceM(x)≧1 Mがxを領域sで受理 ある自然数sに対して、 s≧spaceM(x) 2019/9/13 佐賀大学理工学部知能情報システム学科

O記号 定義 f(n)=O(g(n)) 関数f(n), g(n)に対して、 ある定数c>0と整数n0≧0が存在して、 全てのn≧n0に対してf(n)≦cg(n)となるとき、 f(n)=O(g(n)) と書く。 例: n=O(n2), 2n ≠O(n), log2n=O(√n) 2019/9/13 佐賀大学理工学部知能情報システム学科

カウンタ 作業用テープをカウンタとして使用 2進数x=b1…bm→$bm…b1BB… 1加える動作 1引く動作動作 (初期状態p, 終了状態q) →(p, add1, q) 1引く動作動作 (初期状態p, 終了状態q(x>0), r(x=0)) →(p, sub1, q, r) 2019/9/13 佐賀大学理工学部知能情報システム学科

(p, add1, q) 足す 戻る s1 X s2 Y D p $ p1 R 0/B 1/1 L 1 p2 0/1 q N 0/1 q N 足す 戻る 2019/9/13 佐賀大学理工学部知能情報システム学科

(p, sub1, q, r) 引けない 借りる 引けた 先頭探し中 戻れる 先頭発見 0削除 戻れる 終了 戻り中 終了 s1 X s2 Y D p $ p1 R B r L 1 p2 p4 p3 q N 0/1 引けない 借りる 引けた 先頭探し中 戻れる 先頭発見 0削除 戻れる 終了 戻り中 2019/9/13 終了 佐賀大学理工学部知能情報システム学科

カウンタ使用時の領域量 L={w#w| ∈{0, 1}*}を領域O(log2n)で 受理するDTM M C1←1; C2←1; 1: 入力ヘッドをx1…x2#のi番目に持っていき、C2番目の記号Aを記憶する; 入力ヘッドを#まで右に動かし、y1…ymのi番目に持っていき、C2番目の記号Bを記憶する; if A=B then C1←C1+1; C2←C2+ 1; goto 1 else if A=# and B=$ then accept else reject 2019/9/13 佐賀大学理工学部知能情報システム学科

T(n)時間限定 T(n)を関数とし、MをkテープNTMとする。 言語Lに対して以下の(1)(2)が成り立つとき、 MはLを時間T(n)で受理するという。 また、MはT(n)時間限定(T(n)-time bounded) であるという。 L=L(M) 有限個を除いてすべてのx∈Lに対して timeM(x)≦T(|x|) 2019/9/13 佐賀大学理工学部知能情報システム学科

S(n)領域限定 S(n)を関数とし、MをkテープNTMとする。 言語Lに対して以下の(1)(2)が成り立つとき、 MはLを領域S(n)で受理するという。 また、MはS(n)領域限定(S(n)-space bounded) であるという。 L=L(M) 有限個を除いてすべてのx∈Lに対して spaceM(x)≦S(|x|) 2019/9/13 佐賀大学理工学部知能情報システム学科

NTIME(T(n)), NSPACE(S(n)) NTIMEk(T(n)) ={L|LはあるkテープNTMによって時間T(n)によって受理される} NSPACEk(S(n)) ={L|LはあるkテープNTMによって領域S(n)によって受理される} 2019/9/13 佐賀大学理工学部知能情報システム学科

DTIME(T(n)), DSPACE(S(n)) DTIMEk(T(n)) ={L|LはあるkテープDTMによって時間T(n)によって受理される} DSPACEk(S(n)) ={L|LはあるkテープDTMによって領域S(n)によって受理される} 2019/9/13 佐賀大学理工学部知能情報システム学科

正規言語 Lを正規言語とする。 このとき、以下の(1), (2)が成立する。 L∈DTIME(n) L∈DSPACE(1) 2019/9/13 佐賀大学理工学部知能情報システム学科

領域構成可能 関数S(n)は、 このときMはS(n)を、 L(M)={1}*かつ 有限個を除いてすべてのx∈{1}*に対して spaceM(x)=|_S(x)_|となるDTM Mが 存在するとき、 領域構成可能(fully space constructible)である。 このときMはS(n)を、 領域構成する。 2019/9/13 佐賀大学理工学部知能情報システム学科

時間構成可能 関数T(n)は、 このときMはT(n)を、 L(M)={1}*かつ 有限個を除いてすべてのx∈{1}*に対して timeM(x)=|_T(x)_|≧xとを満たすDTM Mが 存在するとき、 時間構成可能(fully time constructible)である。 このときMはT(n)を、 時間構成する。 2019/9/13 佐賀大学理工学部知能情報システム学科

最後に 開始 大レポートを提出して帰ること 次回は、 言語のクラス 2019/9/13 佐賀大学理工学部知能情報システム学科