跳到主要内容

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

标签：

Author​

Isidore, 祭音Myyura

Description​

設問1​

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

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

設問2​

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

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

(2) ４つの葉 を持ち、それ以外には葉を持たない木を考える。 を満たす木を重複なく全て導出して、各辺の長さとともに図示せよ。

Kai​

設問1​

The answer is .

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)​

葉 のみを持つ根無し無順序木を考える。

すべての頂点の次数は または なので，3 つの葉を持つ木は，中央に次数 の頂点 を 1 つ持つ形に限られる。

各辺の長さを

とおく。

条件より，

である。

これを解くと，

となる。

したがって，求める木は次の 1 つである。

      A
      |
      | 8
      |
      X
     / \
  4 /   \ 2
   /     \
  B       C

(2)​

4 つの葉 を持ち，それ以外には葉を持たない木を考える。

すべての頂点の次数が または であるから，内部頂点は 2 つである。したがって，木の形は葉の分割により

の 3 通りを調べればよい。

与えられた距離は

である。

場合 1：

この場合，木の形は次のようになる。

A -- u -- v -- C
B --/     \-- D

辺の長さを

とおく。

このとき，

である。与えられた値を代入すると，

より，

である。

一方，

でもあるが，

より，

となる。これは矛盾である。

したがって，この場合は不可能である。

場合 2：

この場合，木の形は次のようになる。

A -- u -- v -- B
C --/     \-- D

辺の長さを

とおく。

このとき，

である。与えられた値を代入すると，

より，

である。

一方，

でもあるが，

より，

となる。これは矛盾である。

したがって，この場合も不可能である。

場合 3：

この場合，木の形は次のようになる。

A -- u -- v -- B
D --/     \-- C

辺の長さを

とおく。

条件より，

である。

まず，

より，

である。

また，

なので，

を得る。

次に，

に を代入すると，

である。

また，

に を代入すると，

である。

さらに，

であるから，

より，

となる。

なので，

より，

である。

したがって，

となる。

よって，

である。

したがって，求める木は次の 1 つである。

      A
      |
      | 5
      |
      u
     / \
  2 /   \ 3
   /     \
  D       v
         / \
      4 /   \ 2
       /     \
      B       C

すなわち，

である。

木の形は の分割に対応するものだけである。

目录