Skip to content

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

Author

Isidore

Description

設問1

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

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

設問2

すべての頂点の次数が１または３であり、辺に向きがない、根無し無順序木について考える。 次数が１の頂点を葉と呼ぶ。 すべての辺には正の値の長さが与えられ、葉 \(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\) を満たす木を重複なく全て導出して、各辺の長さとともに図示せよ。

Kai

設問1

The answer is \(2\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
A = ["P", "A", "R", "I", "S"]
B = ["P", "A", "I", "R", "S"]
cost = [[0]*(len(A)+1) for _ in range(len(B)+1)]

for i in range(len(A)):
    cost[i+1][0] = cost[i][0]+1
for j in range(len(B)):
    cost[0][j+1] = cost[0][j]+1

for i in range(len(A)):
    for j in range(len(B)):
        c = 0 if A[i] == B[j] else 1
        cost[i+1][j+1] = min(cost[i][j+1]+1, cost[i+1][j]+1, cost[i][j]+c)

for i in range(len(cost)):
    print(cost[i])

設問2

(1)

(2)