Core 演習 完全解答

採点方針

• 定義問題は、用語を日本語で説明できていれば可。
• 証明問題は、結論だけでは不可。定義展開、仮定、結論への推論が必要。
• 計算量問題は、O だけでなく、可能なら Θ と根拠を書く。
• 実装問題は Python 例を示すが、同等の擬似コードでも可。

Level 1: 記号を読む

集合・論理

1.
x∈A: x は A の要素。
x∉A: x は A の要素ではない。
A⊆B: A のすべての要素が B に含まれる。
A=B: A と B が同じ要素を持つ。

2.
A∪B={1,2,3,4,5}。
A∩B={3,4}。
A\B={1,2}。
B\A={5}。

3.
∀x(x∈A -> x∈B)。

4.
P->Q の逆は Q->P。
裏は ¬P->¬Q。
対偶は ¬Q->¬P。

5.
¬(∀x∈S, P(x)) は ∃x∈S, ¬P(x)。

6.
¬(∃x∈S, P(x)) は ∀x∈S, ¬P(x)。

7.
S の任意の x について、P(x) ならば Q(x) である。

8.
S のある x について、P(x) かつ Q(x) である。

関数・関係

9.
f: A -> B では、A が定義域、B が終域である。

10.
単射: f(x)=f(y) ならば x=y。異なる入力は異なる出力へ写る。
全射: 任意の b∈B について、ある a∈A が存在し f(a)=b。終域の全要素が像に含まれる。
全単射: 単射かつ全射。

11.
関係 R が同値関係であるとは、反射律、対称律、推移律を満たすこと。
反射律: 任意の a について aRa。
対称律: aRb ならば bRa。
推移律: aRb かつ bRc ならば aRc。

12.
半順序の条件は、反射律、反対称律、推移律。
反対称律: aRb かつ bRa ならば a=b。

13.
二項関係 R は直積集合の部分集合として表せる。aRb は (a,b)∈R と同じ意味である。

14.
同値類とは、ある要素 a と同値な要素をすべて集めた集合 [a] = {x | xRa} のこと。

15.
対称律は aRb -> bRa。
反対称律は aRb かつ bRa なら a=b。
等号以外で両方向が許されるのが対称律、両方向が成り立つなら同一でなければならないのが反対称律。

証明

16.
直接証明では、仮定 P から出発し、定義や既知の事実を使って結論 Q を導く。

17.
対偶証明では、P->Q の代わりに同値な命題 ¬Q->¬P を示す。

18.
背理法では、示したい命題の否定を仮定し、矛盾を導く。矛盾が出たため否定が誤りであり、元の命題が真だと結論する。

19.
数学的帰納法の2ステップは、基底部と帰納ステップ。
基底部で最初の値について命題を示し、帰納ステップで P(k) を仮定して P(k+1) を示す。

20.
反例は、普遍命題が偽であることを示す具体例である。∀x P(x) を否定するには、P(x) が成り立たない x を1つ示せばよい。

漸近記法・擬似コード・グラフ

21.
O(g(n)) は漸近的上界。
Ω(g(n)) は漸近的下界。
Θ(g(n)) は上界と下界が一致し、同じ増加率であること。

22.
小さい順に、log n, n, n log n, n^2, 2^n。

23.
線形探索の前提は、配列やリストの要素を順に調べられること。ソートは不要。最悪時間計算量は Θ(n)。

24.
二分探索の前提は、配列が探索キーでソート済みであること。最悪時間計算量は Θ(log n)。

25.
木は、連結で閉路を持たない無向グラフである。n 頂点の木は n-1 本の辺を持つ。

26.
DAG は Directed Acyclic Graph の略で、有向閉路を持たない有向グラフである。

27.
BFS はキューを使い、始点から距離が近い順に探索する。DFS はスタックまたは再帰を使い、行けるところまで深く進む。

Level 2: 計算する

28.
B∪C={b,c,d,e}。
したがって A∩(B∪C)={b,c}。

29.
|P(A)|=2^|A|=2^4=16。

30.
f(n)=3n+1 は単射。なぜなら f(a)=f(b) なら 3a+1=3b+1 なので a=b。
全射ではない。たとえば 0∈Z に対して 3n+1=0 となる整数 n=-1/3 は存在しない。

31.
g(n)=n^2 は N を 0,1,2,... とするなら単射。a^2=b^2 かつ a,b≥0 なら a=b。
全射ではない。たとえば 2 は自然数だが、n^2=2 となる自然数 n は存在しない。

32.
aRb ⇔ a-b が3で割り切れるとは、a と b が3で割った余りを同じくすること。
同値類は、

[0] = {...,-6,-3,0,3,6,...}
[1] = {...,-5,-2,1,4,7,...}
[2] = {...,-4,-1,2,5,8,...}

の3つ。

33.
n≥1 なら 20n≤20n^2 かつ 1≤n^2。よって、

5n^2+20n+1 ≤ 5n^2+20n^2+n^2 = 26n^2

したがって c=26, n0=1 とすれば 5n^2+20n+1 = O(n^2)。

34.
n≥1 なら n^2≤n^3。したがって c=1, n0=1 とすれば n^2=O(n^3)。

35.
n^3 は O(n^2) ではない。仮に n^3≤c n^2 が十分大きなすべての n で成り立つなら、n≤c となる。しかし n は任意に大きくできるため、固定定数 c では抑えられない。

36.
内側ループの反復回数は i 回。全体では、

1+2+...+n = n(n+1)/2

回。各回が定数時間なので Θ(n^2)。

37.
i は各回で半分になる。k 回後におおよそ n/2^k。1 以下になるまでの回数は Θ(log n)。

38.
fact(5)=5!=120。

39.
fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8。

40.
5頂点の木の辺数は 5-1=4。

41.
完全グラフ K_n は任意の2頂点間に辺を持つ。辺数は C(n,2)=n(n-1)/2。

42.
有向辺 (a,b) と (b,c) があるので、長さ2の有向パス a -> b -> c が存在する。したがって a から c は到達可能。

Level 3: 証明する

43.
A⊆B かつ B⊆C と仮定する。A⊆C を示す。任意の x∈A を取る。A⊆B より x∈B。さらに B⊆C より x∈C。したがって任意の x∈A について x∈C なので、A⊆C。

44.
集合の等号 A=B は、同じ要素を持つことを意味する。A⊆B は A の任意の要素が B に含まれること、B⊆A は B の任意の要素が A に含まれること。両方が成り立てば、どちらか一方にだけ属する要素は存在しない。よって同じ要素を持ち、A=B。

45.
任意の x∈A∩B を取る。共通部分の定義より、x∈A かつ x∈B。特に x∈A。よって A∩B⊆A。

46.
両包含を示す。
まず x∈A∩(B∪C) とする。すると x∈A かつ x∈B∪C。後者より x∈B または x∈C。x∈B なら x∈A∩B、x∈C なら x∈A∩C。したがって x∈(A∩B)∪(A∩C)。
逆に x∈(A∩B)∪(A∩C) とする。すると x∈A∩B または x∈A∩C。前者なら x∈A かつ x∈B、後者なら x∈A かつ x∈C。どちらの場合も x∈A かつ x∈B∪C。したがって x∈A∩(B∪C)。
両包含より等号が成り立つ。

47.
a,b が偶数とする。ある整数 m,n が存在して a=2m, b=2n。すると a+b=2m+2n=2(m+n)。m+n は整数なので a+b は偶数。

48.
a,b が奇数とする。ある整数 m,n が存在して a=2m+1, b=2n+1。すると、

ab = (2m+1)(2n+1) = 4mn+2m+2n+1 = 2(2mn+m+n)+1

2mn+m+n は整数なので、ab は奇数。

49.
対偶を示す。すなわち、n が偶数でないなら n^2 は偶数でない。整数では偶数でないことは奇数であることなので、n=2k+1 と書ける。すると、

n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1

よって n^2 は奇数であり、偶数ではない。したがって対偶が成り立つので、元の命題も成り立つ。

50.
P(n): 1+2+...+n=n(n+1)/2 とする。
基底部: n=1 では左辺 1、右辺 1(2)/2=1。
帰納ステップ: P(k) を仮定する。

1+2+...+k+(k+1)
= k(k+1)/2 + (k+1)
= (k+1)(k+2)/2

これは P(k+1)。よって帰納法により成り立つ。

51.
P(n): 1+3+...+(2n-1)=n^2。
基底部: n=1 で 1=1^2。
帰納ステップ: P(k) を仮定する。

1+3+...+(2k-1)+(2(k+1)-1)
= k^2 + (2k+1)
= (k+1)^2

よって成り立つ。

52.
P(n): 2^n≥n+1。
基底部: n=0 で 1≥1。
帰納ステップ: 2^k≥k+1 を仮定する。すると、

2^(k+1)=2*2^k ≥ 2(k+1) = 2k+2 ≥ k+2

最後の不等式は k≥0 より成り立つ。したがって P(k+1) が成り立つ。

53.
関係 R を aRb ⇔ a-b が偶数とする。
反射律: a-a=0 は偶数なので aRa。
対称律: a-b が偶数なら、b-a=-(a-b) も偶数。よって bRa。
推移律: a-b と b-c が偶数なら、和 (a-b)+(b-c)=a-c も偶数。よって aRc。
以上より同値関係。

54.
集合族上の包含関係 ⊆ について示す。
反射律: 任意の集合 A について A⊆A。
反対称律: A⊆B かつ B⊆A なら、両包含により A=B。
推移律: A⊆B かつ B⊆C なら、問43より A⊆C。
したがって半順序。

55.
有向グラフで到達可能性を u R v と書く。uRv なら u から v への有向パスが存在する。vRw なら v から w への有向パスが存在する。この2つのパスを連結すれば、u から w への有向パスが得られる。したがって uRw。よって推移的。

56.
n 頂点の木の辺数が n-1 であることを帰納法で示す。
基底部: n=1 の木は辺を持たないので 0=1-1。
帰納ステップ: n 頂点の木を考える。木には葉が少なくとも1つ存在する。葉 v とそれに接続する辺1本を除くと、n-1 頂点の木が得られる。帰納法の仮定より、この木の辺数は (n-1)-1=n-2。元の木はこれに葉へ接続する辺1本を加えたものなので、辺数は n-1。
よって成り立つ。

57.
DAG に入次数0の頂点が存在しないと仮定する。任意の頂点は少なくとも1本の入辺を持つ。任意の頂点 v0 から始め、入辺を逆向きにたどって v1, v2, ... を作る。頂点数は有限なので、どこかで同じ頂点が再び現れる。すると有向閉路が存在することになる。これは DAG が有向閉路を持たないことに矛盾する。したがって入次数0の頂点が少なくとも1つ存在する。

Level 4: 実装する

58. 線形探索

def linear_search(a, x):
    for i, value in enumerate(a):
        if value == x:
            return i
    return None

59. 二分探索

def binary_search(a, x):
    left, right = 0, len(a) - 1
    while left <= right:
        mid = (left + right) // 2
        if a[mid] == x:
            return mid
        if a[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return None

前提: a は昇順にソート済み。

60. 階乗関数・再帰

def fact_recursive(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * fact_recursive(n - 1)

61. 階乗関数・ループ

def fact_iterative(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

62. BFS

from collections import deque

def bfs(graph, start):
    visited = set()
    order = []
    q = deque([start])
    visited.add(start)

    while q:
        v = q.popleft()
        order.append(v)
        for w in graph.get(v, []):
            if w not in visited:
                visited.add(w)
                q.append(w)
    return order

63. DFS

def dfs(graph, start):
    visited = set()
    order = []

    def visit(v):
        visited.add(v)
        order.append(v)
        for w in graph.get(v, []):
            if w not in visited:
                visit(w)

    visit(start)
    return order

64. 到達可能な頂点集合

from collections import deque

def reachable_vertices(graph, start):
    visited = {start}
    q = deque([start])
    while q:
        v = q.popleft()
        for w in graph.get(v, []):
            if w not in visited:
                visited.add(w)
                q.append(w)
    return visited

65. DAGのトポロジカルソート

from collections import deque

def topological_sort(graph):
    vertices = set(graph.keys())
    for neighbors in graph.values():
        vertices.update(neighbors)

    indeg = {v: 0 for v in vertices}
    for v, neighbors in graph.items():
        for w in neighbors:
            indeg[w] += 1

    q = deque([v for v in vertices if indeg[v] == 0])
    order = []

    while q:
        v = q.popleft()
        order.append(v)
        for w in graph.get(v, []):
            indeg[w] -= 1
            if indeg[w] == 0:
                q.append(w)

    if len(order) != len(vertices):
        raise ValueError("graph is not a DAG")
    return order

Level 5: 本体への接続

66.
有限オートマトンの遷移関数 δ: Q×Σ -> Q は、状態集合 Q とアルファベット Σ の直積から、次の状態 Q への関数である。つまり、現在状態 q∈Q と入力記号 a∈Σ の組 (q,a) に対して、次状態 δ(q,a)∈Q が一意に定まる。

67.
決定性オートマトンでは、δ: Q×Σ -> Q により次状態が1つに決まる。
非決定性オートマトンでは、δ: Q×Σ -> P(Q) により、次に進める状態の集合が返る。つまり、次状態が0個、1個、または複数あり得る。

68.
計算量クラスを集合として見るとは、ある計算資源制約を満たして解ける問題全体の集合として捉えること。たとえば、P は決定性チューリング機械で多項式時間に判定できる判定問題の集合、NP は多項式時間で検証可能な証明を持つ判定問題の集合として見られる。

69.
グラフの到達可能性問題は、次のように計算問題として定義できる。

入力: 有向グラフ G=(V,E)、頂点 s,t∈V
出力: s から t への有向パスが存在するなら True、存在しないなら False

探索アルゴリズムとして BFS または DFS を用いれば判定できる。

70.
アルゴリズムの正しさとは、すべての許された入力に対して仕様を満たす出力を返すことである。計算量とは、そのアルゴリズムがどれだけの時間やメモリを使うかの評価である。
正しいが遅いアルゴリズムはあり得る。速いが誤答を返す手続きもあり得る。したがって、正しさと計算量は別々に主張し、別々に証明・評価する必要がある。