2009年度『計算モデル諭』 期末試験問題 (猪 股)2009/01/29
■ 解答 上の注意
い いな文章 (正 答 とも
な文字 でわか りやす い文章 を書 くこ と.あ ま
●誰 もが読 める (読 み間違 い しな い)よ うに 丁事
売)は
リオ ドとコ ンマの判言
しな い。 また,判 読 で きない文軍 (た とえば,ピ
誤答 とも意 味が とれ る文章 )は 正答 とは
fiWii[∵ :Fも
皇 「∵
T[猟 曇
う
詳ギ
増「吾想
る
。
あ
;ill替
T「
￨こ
.[槽 ][ギ :曇 ::￨ま
}を 表す
●Nは 自然数全体からなる集合 {0,1,2,3,… ・
.
1.次 の ように定義 され るチ ュー リング機械 TAイ 4を 考
TAイ 4=<I(4,Σ 4,δ 4,90,9∬
える。 (25点 )
>
ただ し,bを 空 自 とす る
記号の集合 Σ4={0,1,ち #,△ },
状態の集合 κ4={90,91,92,9〃 },
.
δ
4の 各値 を図 1(a)の 重力作図によって定める
F/1が
己号列 を
書 き込 まれている.こ の言
の言
己号 として 1ま たは 0の 記号
“
初期状態においては,テ ープ上に空自以外
己号列 χ
の左端言
己号 のマス ロとす る.TAイ 4は ,入 力言
ヘ
は
の
,π
位置
ッド
おける
態に
.初
期状
己号列 とよぶ
で表 し,入 力言
ープ上にはこれ ら以外 の文字 も書 かれていることもある).
る
に応 じて,記 号 *ま たは #を 書 き込んで停止す (テ
.
o動
o)入 力言己号列 1010
作図
o/十
R
′
R
■/十 ′
(c)入 力記号 列 001
図 1:チ ユー リング機械:T_lF4
テ ープ上に書 かれてあ
ある とき,チ ユー リング機lll alf4が 停止 した時に
図 1(b)の ように入力記 号列 が 1010で
る非空 自記号 列 を答 え よ
した時 にテ ープ上に書 かれてあ る
が 001で ある とき,チ ユー リング機械 T_lf4が 停止
(b) 図 1(C)の ように入力記号列
非空 自記号 列 を答 え よ。
しなが ら文章 で答
いて停止す るのは, どのよ うな入力記号列 の ときか Jllを 示
このチ ュー リング機械 T lf4が *を 書
(a)
.
えよ
.
(d) このチ ュー リング機械
TM4が #を 書 いて 停止す るのは,
答 え よ.
(e)TM4が
TM4が
己号 列 の と言か例 を示 しなが ら文章 で
どの ような入力言
_
*を 書 いて唇・止 す る
´ _,山 ^'゛ エ ワ
えンス
*以 外 の非 空 白記号 も残 って い る場 合が ある。 そ こで
*の 1文 字 だけになるように図 1(a)を 修
ときには,常 にテ ープ上 の非 空 自記号 列 は
*を 書 いて動作 を停止 した ときに,テ ープ上には
正 せ よ.状 態 の集 合の要素 は必要 に応 じて追加
せよ
.
,
2.以 下 の 間に答え よ.答 は最 も適 当な ものを解答欄 に記 入せ よ.(12点 )
o Tω =am7344+""7ぽ +Ю 6η のとき,OCO)=回
Oο いう+列 ② 〉を簡単にすると00つ である。
である
.
―
ーと
ば
ダ
よ
れる
数
)は 定
Oο (E≡ ≡
す
コ
.
(a)あ るアルゴ リズムを用いて問題 を解くとき,解 き終わるまでの時間は,入 カデータの量に依存する。この入カデー
ま
の
わ
諷
問
こ
墓
。 量Ⅱ量禁
回 牌¨
回 物式
"れ
6:暑 :唇 J:こ
FttЫ
.
(f)あ る問題 の解法 の時間計算量が問題 の [(4)コ の指数 関数 である とき,そ の問題 は
[(6)]問 題 とい う。
3.チ ュー リングの提 ロ
ロを弓1用 しなが ら計算可 能性 について述 べ よ。 (7点 )
4オ ーダー記法を用いる際に気をつける事を例をあげて言党日
月せよ.(6点
)
問題 は裏 に もある
次 の ように各述語 の意 味 を定める
.
(25点 )
好意
攘 夷志士 (2)
ライバル し ,υ )
0ま
)
α
好物
(2,υ )
恋敵
(π ,υ )
この とき,以 下 のような言
命理 プロ グラム
別人 (2,υ )
α
(α ,ν
α の恋敵 は υだ"―
“
"の
と υ は別 人である"―
(“ )
好物 は νだ"―
“
のペ ッ トは υ だ"―
真選組 (a)
ベ ツ ト (・ ,υ )
α
π は ν に好意がある"―
“
は真選糸
且のメンバ ー"―
α
万事屋
α
“ は万事 屋 のメンバー"―
“
α は攘 夷志士"―
“
%と υ はライバ ル だ"―
*1)を
υ を追跡す る"―
は逃亡す る"一
追跡
(“ ,υ )
逃亡
(π )
考 える。
-1)
万事 屋 (銀 時)←
―
●
“幼
―
→
―
“→
-0
“
0-0
“
万事屋 (新 八)←
万事屋 (神 楽 )←
真選組 (土 方十 四郎)←
真選組 に 藤勲 )←
真選組
(,中
田総悟 )←
懐 夷志士 (桂 小太郎)←
ペ ッ ト (神 楽 ,定 春 )←
0-つ
-0
-0
“
(5-10
“
ペ ッ ト (桂 ,エ リザ ベ ス)←
ライバル (神 楽 ,沖 田総悟 )←
ライバル (銀 時,土 方十 四郎)←
ライバル
(を
(5-11)
,J)← ライバル
(卜 12)
(プ ,じ )
恋敵 C,υ )← 好意 (し ,υ ),好 意
逃亡 (c)← 追跡 (d,c)
(υ ,υ ),別 人 (2,υ )
(5-14)
追跡 (2,υ )← 真選組 (2),攘 夷志士 (υ )
(5-15)
好意 (近藤勲 ,妙 )←
好意 (猿 飛 あやめ,銀 時)←
(5-16)
好意 (柳 生 九兵衛 ,妙 )←
好物 (銀 時,い ち ご牛手し
)←
(5-18)
好物 (神 楽 ,酢 昆布)←
好物 (土 方十 四郎,マ ヨネ ーズ)←
(5-20)
(5-17)
(5-19)
(5-21)
別 人 (た ,J)← たと Jは 異 なる定数
SLD反 駁 にお い て,確 定節 の優先順位 を列学順 (節 香号 の若 い もの を優先 的に選 ぶ)と
を次 の 目標 とす る選択法 とせ よ
.
なお,SLD反 駁 を記述 する際には,次 の形式 で記述 せ よ
.
目標節 または導 出節
(節 番 号)
[変 数
← 万事屋
(5-1)
[π
□
*1):『
銀魂』 をもとに作成
(5-13)
(“ )
へ束縛 (代 入)]
=銀 時
]
(5-22)
し
,
目標 節 の 最 左 の リテ ラル
(a)“ ← ペ ッ ト (神 楽 ,p)"を 目標節 として,SLD反 駁 をした とき,わ か ることを文章 で述 べ よ。
(b)“ ← 好物 (P,9)"を 目標節 として,SLD反 駁 を した とき,わ かることを文章 で述 べ よ
.
← ライバル (P,9),万 事 屋 (p),真 選組 (9)"と した とき, この 目標節 が表 して い る 内容 (何 がわか るのか)
(c)目 標節 を “
をで きるだけ こなれた 日本語で答えな さい。
(d)SLD反 駁 によって,“ ある懐 夷志 士 (p)の ペ ッ トが何 (q)か "を 調 べ たい。 そのため の 目標節 を答えな さい。
(e)“ ← 恋敵
(P,Illl生
九兵衛)"を 目標節 とし,SLD反 騒 をす る(解 答用紙 に記入す る)と ともに,わ かる ことを文章 で述
べよ
.
(D“ ← 逃亡 (p)"を 目標節 とし,SLD反 駁 をす る(解 答用紙 に記 入す る)と ともに,わ かることを文章 で述 べ よ
.
(g)節 (5-13)が 表 して い る内容 を,で きるだけこなれた 日本語 で述 べ よ
.
(h)節 (5-12)は 何 のために必 要 なのか (な か った ときに どんな ことで 困るのか)答 えな さい。
6.以 下 の間 に答え よ.答 は最 も適 当な ものを解答欄 に記入せ よ.(15点 )
(a)節 ￢P(“ )∨ ￢R(“ )と R(0)よ り導 出 され る導 出節 は [(7)コ である。なお,0は 定数 とす る。
(b)節 ￢C(υ )∨
となる
E(υ )を ホー ン節 の表記法 (← を用 い た表記)に 書 き直す と
[(8)コ
.
(C)(P→ 0)∧ ￢Rを 節集合 に変換す る と [(9)コ となる。ただ し,民 0,Rは 命題 とす る
.
(d)以 下 の命題や述語 が定義 されて い るもの とす る。
R:雨
が降 って い る
F(π ):α
はカエルである。
この とき,つ ぎの各文 を論理式 で表せ
C(“ ):α
は緑色である.
J(α ):“
は跳ねて い る
.
.
」
緑色ではないカエルがいる
・「
J(10)
「
い
べ
エ
い
て
なら
ば
る
●
がね
て
る
の
ル
降っ
て
,雨 が
」
カ
す
J(11)
Dし
7.節 集合 {ス (z),￢ θ(“ ),￢ B(2)vθ (1),￢ ス(3)∨
B(υ )}か
ら矛盾を導 く導出本 (図 )を 2つ (2種 類)描 くとともに
α,υ ,zに 代 入され る項 (定 数 )を それぞれ答え よ.な お,0,1,2,3は 定数 とす る。 (10点 )
,
© Copyright 2024 ExpyDoc
