5차 과제

벡터

벡터 자료형

벡터 자료형은 부동소수점들로 이루어진 리스트로 정의될 수 있다.

from typing import List

Vector = List[float]

벡터 덧셈

차원이 같은 두 벡터의 항목별 합을 항목으로 같은 벡터를 반환하는 함수는 다음과 같다.

def addV(v: Vector, w: Vector) -> Vector:
    assert len(v) == len(w)   # 두 벡터의 길이가 같아야 함

    return [v_i + w_i for v_i, w_i in zip(v, w)]

벡터 덧셈 함수 일반화

동일한 차원의 임의의 개수의 벡터를 더하는 함수를 다음과 같이 정의할 수 있다.

def vector_sum(vectors: List[Vector]) -> Vector:
    """
    인자: 동일한 차원의 벡터들의 리스트
    반환값: 각 항목의 합으로 이루어진 동일한 차원의 벡터
    """
    
    assert vectors                   # 1개 이상의 벡터가 주어져야 함

    num_elements = len(vectors[0])   # 벡터 개수
    
    assert all(len(v) == num_elements for v in vectors)   # 모든 벡터의 크기가 같아야 함

    # 동일한 위치의 항목을 모두 더한 값들로 이루어진 벡터 반환
    return [sum(vector[i] for vector in vectors)
            for i in range(num_elements)]

벡터 뺄셈

차원이 같은 두 벡터의 항목별 차를 항목으로 같은 벡터를 반환하는 함수는 다음과 같다.

def subtractV(v: Vector, w: Vector) -> Vector:
    assert len(v) == len(w)   # 두 벡터의 길이가 같아야 함

    return [v_i - w_i for v_i, w_i in zip(v, w)]

벡터 스칼라 곱셈

벡터의 각 항목에 동일한 부동소수점을 곱한 결과를 반화하는 함수는 다음과 같다.

def scalar_multV(c: float, v: Vector) -> Vector:
    return [c * v_i for v_i in v]

항목별 평균 벡터

동일한 차원의 여러 벡터가 주어졌을 때 항목별 평균으로 이루어진 벡터를 반환하는 함수는 다음과 같다.

def vector_mean(vectors: List[Vector]) -> Vector:
    n = len(vectors)
    return scalar_multV(1/n, vector_sum(vectors))

벡터 내적

동일 차원의 두 벡터의 내적을 반환하는 함수는 다음과 같다.

def dot(v: Vector, w: Vector) -> float:
    assert len(v) == len(w), "벡터들의 길이가 동일해야 함"""

    return sum(v_i * w_i for v_i, w_i in zip(v, w))

벡터의 크기

벡터 $v = (v_1, \cdots, v_n)$가 주어졌을 때 다음이 성립한다.

$$\vert v\vert = \sqrt{v \cdot v} = \sqrt{v_1^2 + \cdots + v_n^2}$$

import math

def sum_of_squares(v: Vector) -> float:

    return dot(v, v)

def magnitude(v: Vector) -> float:
    return math.sqrt(sum_of_squares(v))

벡터 사이의 거리

벡터 $v = (v_1, \cdots, v_n)$와 벡터 $w = (w_1, \cdots, w_n)$ 사이의 거리는 다음과 같다.

$$ \begin{align*} \vert v - w\vert &= \sqrt{(v-w) \cdot (v-w)} \\[.5ex] &= \sqrt{(v_1-w_1)^2 + \cdots + (v_n-w_n)^2} \end{align*} $$

def squared_distance(v: Vector, w: Vector) -> float:
    return sum_of_squares(subtractV(v, w))

# 버전 1
def distance(v: Vector, w: Vector) -> float:
    return math.sqrt(squared_distance(v, w))

# 버전 2
def distance(v: Vector, w: Vector) -> float:
    return magnitude(subtractV(v, w))

행렬

행렬 자료형

행렬을 리스트의 리스트, 즉 2중 리스트로 구현한다.

Matrix = List[List[float]]

예를 들어, 아래 A와 B는 각각 (2, 3), (3, 2) 모양의 행렬을 나타낸다.

A = [[1, 2, 3],  # 2 x 3 행렬
     [4, 5, 6]]

B = [[1, 2],     # 3 x 2 행렬
     [3, 4],
     [5, 6]]

행렬의 모양(shape)

아래 함수 shape()는 주어진 행렬의 모양을 튜플로 반환한다.

from typing import Tuple

def shape(A: Matrix) -> Tuple[int, int]:
    num_rows = len(A)
    num_cols = len(A[0]) if A else 0   # number of elements in first row
    return num_rows, num_cols

행벡터와 열벡터

아래 두 함수는 각각 지정된 행와 지정된 열의 항목들로 구성된 행벡터와 열벡터를 반환한다.

# 행벡터 계산
def get_row(A: Matrix, i: int) -> Vector:
    return A[i]             

# 열벡터 계산
def get_column(A: Matrix, j: int) -> Vector:
    return [A_i[j] for A_i in A]

행렬 생성 함수

아래 함수는 지정된 모양의 행렬을 생성한다. 셋째 인자는 지정된 위치의 항목을 계산하는 함수이다.

• 인자
  • num_rows: 행의 수
  • num_rows: 열의 수
  • entry_fn: i, j가 주어지면 i행, j열에 위치한 값 계산
• 반환값: 지정된 방식으로 계산된 (i, j) 모양의 행렬

from typing import Callable

def make_matrix(num_rows: int,
                num_cols: int,
                entry_fn: Callable[[int, int], float]) -> Matrix:
    return [ [entry_fn(i, j) for j in range(num_cols)] for i in range(num_rows)]   

특수 행렬

영행렬

지정된 모양의 영행렬을 생성하는 함수는 다음과 같다.

def zero_matrix(n: int, m:int) -> Matrix:
    return make_matrix(n, m, lambda i, j: 0)

단위행렬

단위행렬은 행과 열의 개수가 동일한 정방행렬이며, 지정된 모양의 단위행렬을 생성하는 함수는 다음과 같다.

def identity_matrix(n: int) -> Matrix:
    return make_matrix(n, n, lambda i, j: 1 if i == j else 0)

행렬 덧셈과 뺄셈

행렬의 덧셈과 뺄셈을 계산하는 함수는 다음과 같다.

def addM(A: Matrix, B: Matrix) -> Matrix:
    assert shape(A) == shape(B)
    
    m, n = shape(A)
    
    return make_matrix(m, n, lambda i, j: A[i][j] + B[i][j])

def subtractM(A: Matrix, B: Matrix) -> Matrix:
    assert shape(A) == shape(B)
    
    m, n = shape(A)
    
    return make_matrix(m, n, lambda i, j: A[i][j] - B[i][j])

C = [[1, 3, 7],
     [1, 0, 0]]

D = [[0, 0, 5], 
     [7, 5, 0]]

행렬의 스칼라 곱셈

숫자 하나와 행렬의 곱셈을 행렬 스칼라 곱셈이라 부른다. 스칼라 곱셈은 행렬의 각 항목을 지정된 숫자로 곱해 새로운 행렬을 생성한다. 즉, 벡터의 스칼라 곱셈과 동일한 방식이다.

행렬 곱셈

$m \times n$ 행렬 $A$와 $n \times p$ 행렬 $B$의 곱은 $m \times p$ 행렬이며, 각 $(i, j)$번째 항목은 다음과 같이 정의된다.

$$ \begin{align*} (A B)_{ij} &= \sum _{k=0}^{n-1} A_{ik} \cdot B_{kj} \\ &= A_{i0} \cdot B_{0j} + A_{i2} \cdot B_{2j} + \cdots + A_{i(n-1)} \cdot B_{(n-1)j} \end{align*} $$

행렬 곱셈과 벡터 내적

$(A B)_{ij}$는 $A$의 $i$ 행벡터와 $B$의 $j$ 열벡터의 내적으로 정의된다.

항등원

영행렬은 행렬 덧셈의 항등원이며, 단위행렬은 행렬 곱셈의 항등원이다.

전치행렬

행렬의 전치란 행과 열을 바꾸는 것으로, 행렬 $A$의 전치는 $A^T$로 나타낸다. 즉, $A$가 $m \times n$ 행렬이면 $A^T$는 $n \times m$ 행렬이며, 그리고 $A^T$의 $i$행의 $j$열번째 값은 $A$의 $j$행의 $i$열번째 값이다. 즉,

$$ A ^{T}_{ij} = A_{ji} $$

전치행렬의 성질

$a$를 스칼라, $A, B$를 크기가 같은 행렬이라 하자. 이때 다음이 성립한다.

• $(A^T)^T = A$
• $(A + B)^T = A^T + B^T$
• $(A - B)^T = A^T - B^T$
• $(a\cdot A)^T = a\cdot A^T$
• $(A B)^T = B^T A^T$

문제 1 (5점)

행렬의 스칼라 곱셈을 실행하는 함수 scalar_multM() 를 구현하라.

# pass와 None 적절한 코드와 표현식으로 대체하라.

def scalar_multM(c: float, A: Matrix) -> Matrix:
    pass

    return None

문제 2 (10점)

행렬 곱셈을 실행하는 함수 multM() 를 구현하라.

# pass와 None 적절한 코드와 표현식으로 대체하라.
# 힌트: 벡터 내적을 이용하라.

def multM(A: Matrix, B: Matrix) -> Matrix:
    pass

    return None

아래 행렬을 이용하여 아래 assert 명령문이 성립함을 확인하라.

E = [[3, 1],
     [2, 1],
     [1, 0]]

assert addM(E, zero_matrix(3, 2)) == E

assert multM(E, identity_matrix(2)) == E

문제 3 (5점)

전치 행렬을 생성하는 함수 transpose() 를 구현하라.

# pass와 None 적절한 코드와 표현식으로 대체하라.

def transpose(A: Matrix) -> Matrix:
    pass

    return None

앞서 정의된 행렬 A, B, C, D를 이용하여 전치행렬의 성질 5개가 성립함을 보여라.

assert transpose(transpose(A)) == A

assert transpose(addM(C, D)) == addM(transpose(C), transpose(D))

assert transpose(subtractM(C, D)) == subtractM(transpose(C), transpose(D))

assert transpose(scalar_multM(3, A)) == scalar_multM(3, transpose(A))

assert transpose(multM(A, B)) == multM(transpose(B), transpose(A))

문제 4 (10점)

어떤 동호회의 사용자 아이디 $i$와 $j$가 친구사이라는 사실을 $(i, j)$로 표시한다고 하자. 그리고 열 명의 사용자 사이의 친구관계가 다음과 같다고 가정하자.

friendships = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4),
               (4, 5), (5, 6), (5, 7), (6, 8), (7, 8), (8, 9)]

그런데 이렇게 하면 사용자들 사이의 친구관계를 쉽게 파악하기 어렵다. 반면에 아래와 같이 $10\times 10$ 행렬로 표시하면 다르게 보인다.

$$ F = \begin{bmatrix} 0&1&1&0&0&0&0&0&0&0\\ 1&0&1&1&0&0&0&0&0&0\\ 1&1&0&1&0&0&0&0&0&0\\ 0&1&1&0&1&0&0&0&0&0\\ 0&0&0&1&0&1&0&0&0&0\\ 0&0&0&0&1&0&1&1&0&0\\ 0&0&0&0&0&1&0&0&1&0\\ 0&0&0&0&0&1&0&0&1&0\\ 0&0&0&0&0&0&1&1&0&1\\ 0&0&0&0&0&0&0&0&1&0 \end{bmatrix} $$

즉, 사용자 $i$와 사용자 $j$ 사이의 친구관계 성립여부는 행렬 $F$의 $(i,j)$ 번째 항목이 1이면 친구관계이고, 0이면 아니라는 것을 바로 확인할 수 있다. 즉, $F_{ij} = 1$인가를 확인만 하면 된다.

위 행렬 $F$를 구현하는 (10, 10) 모양의 행렬를 가리키는 변수 friend_matrix 를 선언하라. 단, make_matrix() 함수 등을 사용해야 한다.

# None 을 적절한 표현식으로 대체하라.
# make_matrix() 함수를 활용한다.

friend_matrix = None

아이디 0번은 아이디 2번과 친구관계이다.

assert friend_matrix[0][2] == 1

아이디 8번은 아이디 0번과 친구관계가 아니다.

assert friend_matrix[8][0] == 0

아이디 5번과 친구사이인 아이디는 다음과 같다.

friends_of_five = [ i for i, is_friend in enumerate(friend_matrix[5]) if is_friend ]

assert friends_of_five == [4, 6, 7]

문제 5 (10점)

본문 포함 앞서 정의한 함수를 모두 넘파이 어레이를 이용하여 구현하라.

• 벡터: 1차원 어레이
• 행렬: 2차원 어레이

주의사항: 넘파이의 linalg 모듈 등 추가 모듈은 절대 사용하지 못한다.

문제 6 (5점)

문제 5에서 정의한 함수를 모두 넘파이의 linalg 모듈에서 제공하는 함수로 대체하라.

문제 7 (5점)

넘파이의 linalg 모듈에서 제공하는 pinv() 함수를 예를 들어 설명하라.