京都大学情報学研究科知能情報学専攻 2023年8月実施情報学基礎 F2-2

Author

２つの文字列の編集コストは、文字の置換・削除・挿入により、一方を他方に変換するのに必要最小限の操作（置換・削除・挿入）の数で定義できる。なお、２つの文字列の長さは同じとする。以下の問いに答えよ。

(1) 文字列 PARIS を PAIRS に編集するコストを答えよ。

すべての頂点の次数が１または３であり、辺に向きがない、根無し無順序木について考える。次数が１の頂点を葉と呼ぶ。すべての辺には正の値の長さが与えられ、葉 \(X, Y\) 間の最短路の長さを \(d(X, Y)\) とする。

(1) ３つの葉 \(A, B, C\) を持ち、それ以外には葉を持たない木を考える。\(d(A, B)=12, d(A,C)=10, d(B, C)=6\) を満たす木を重複なく全て導出して、各辺の長さとともに図示せよ。

(2) ４つの葉 \(A, B, C, D\) を持ち、それ以外には葉を持たない木を考える。\(d(A, B)=12, d(A,C)=10, d(A,D)=7, d(B, C)=6, d(B,D)=9, d(C,D)=7\) を満たす木を重複なく全て導出して、各辺の長さとともに図示せよ。

2