함수
Coding The Matrix를 보다보면 후반부에 갈수록 앞서 본 용어들에 대해서 잊어버려 찾는 것을 반복하게 되어 정리해보며 읽어나가고자 한다.
집합(Set)
수학 객체를 모아 놓은 것으로, 집합에 속하는 각 객체는 많아야 한 번 그 집합에 나타나는 것으로 간주한다. 집합은 원소들 사이에 순서가 없으므로 집합 내 원소의 순서는 중요하지 않다.
집합의 포함 관계는 위와 같이 나타내며, 두 집합이 같다는 것은 다음 두 단계를 사용하여 증명한다.
- 첫 번째 집합이 두 번째 집합에 포함됨을 증명한다.
- 두 번째 집합이 첫 번째 집합에 포함됨을 증명한다.
집합 S가 유한집합이면, |S|를 사용하여 집합의 크기(원소의 개수)를 나타낸다.
Ref
- Ch1 - 1p
- 집합 - 위키백과
카테시안 곱(Cartesian product)
두 집합 A와 B의 카테시안 곱(데카르트 곱)은 a ∈ A 와 b ∈ B 의 모든 쌍 (a, b)으로 이루어진 집합이다.
Ref
- Ch1 - 1p
- 곱집합 - 위키백과
함수(Function)
Ref
- Ch1 - 2p
- 함수 - 위키백과
비공식
가능한 입력 집합 D의 각 원소에 대해 가능한 출력을 할당하는 규칙이다.
- 출력 : 함수에 의한 입력의 상(image), 함수값
- 입력 : 출력의 원상(pre-image)
- 정의역 : 가능한 입력 집합
- 공역 : 함수값이 선택되는 집합, 모든 원소가 함수값이 되어야하는 것은 아님
- 치역 : 모든 정의역 원소들에 대한 함수값들의 집합, 공역의 원소들 중 실제로 함수값이 되는 공역 원소들의 집합
공식
쌍 (a, b)들의 집합(무한 집합도 가능)이다.
예
정의역 {1, 2, 3,...} × {1, 2, 3,...}을 가지는 곱셈 함수는 아래와 같이 나타낼 수 있다.
매핑
함수 f에 대해, f에 의한 q의 상을 f(a)로 나타낼때,
이면, q는 f에 의해 r로 매핑된다고 한다. (q ↦ r)
D에서 F로의 함수 or D를 F로 매핑하는 함수
f: 함수- 집합
D: 정의역 - 집합
F: 공역
주어진 정의역과 공역을 가지는 함수들의 집합에 대한 표기법
집합 D와 F에 대해, D에서 F로의 모든 함수는 아래와 같이 나타낸다.
Fact 1.3.9
임의의 유한 집합 D와 F에 대해,
Ref
- Ch1 - 5p
- 함수 - 위키백과
항등함수
임의의 정의역 D에 대해, 아래를 만족하면 함등함수라 한다.
모든 d ∈ D 에 대해, 항등함수는 다음과 같이 정의된다.
Ref
- Ch1 - 5p
- 항등함수 - 위키백과
함수의 합성
두 개의 함수를 결합하여 하나의 새로운 함수를 얻는 것이다.
위와 같이 주어진 함수 f와 g에 대해,
합성 함수 g∘f는 정의역 A, 공역 C인 함수가 된다.(반드시, 함수 f의 치역이 함수 g의 정의역에 포함되어야 한다.)
Ref
- Ch1 - 5p
- 함수의 합성 - 위키백과
함수 합성의 결합법칙
함수를 합성할 때 결합법칙이 성립한다.
Proposition 1.3.12
Ref
- Ch1 - 6p
단사함수, 전사함수(Definition 1.3.14)
- 단사함수
함수 f : D ⟶ F 일때, 모든 x, y ∈ D에 대해, f(x) = f(y)는 x = y이면 단사함수이다.
- 전사함수
함수 f : D ⟶ F 일때, 모든 z ∈ F에 대해, f(x) = z를 만족하는 x ∈ D가 존재하면 전사함수이다.
Ref
- Ch1 - 7, 8p
- 단사함수 - 위키백과
- 전사함수 - 위키백과
역함수(Definition 1.3.13)
다음 두 조건을 만족하면 함수 f와 g는 서로의 역함수이다.
g∘f가 정의되고,g의 정의역에 대해 항등함수이다.f∘g가 정의되고,f의 정의역에 대해 항등함수이다.
모든 함수가 역함수를 가지는 것은 아니며, 역함수를 가지는 함수를 가역적이라고 한다.
- 가역함수는 단사함수이다. (Lemma 1.3.16)
- 가역함수는 전사함수이다. (Lemma 1.3.17)
- 함수가 가역적이 될 필요충분조건은 그 함수가 단사함수이며 동시에 전사함수인 경우이다.(전단사함수, Theorem 1.3.18)
- 모든 함수는 많아야 하나의 역함수를 가진다. (Lemma 1.3.19)
Ref
- Ch1 - 7~9p
- 역함수 - 위키백과
가역함수를 합성한 함수의 가역성(Lemma 1.3.20)
만약 f와 g가 가역함수이고 f∘g가 존재하면, f∘g는 가역함수이고,
이다.
Ref
- Ch1 - 9p
프로시저(Procedure)
입력(매개변수)을 받아들여 출력(리턴값)을 생산하는 계산 절차에 대한 정확한 기술이다.
예
def mul(p, q): return p*qRef
- Ch1 - 3p
- 프로시저 - 위키백과
계산 문제(Computational problem)
프로시저가 필요할 수도 있는 입력-출력에 대한 사양(스펙)(input-output specification)이다.
예
- input: 1보다 큰 정수의 쌍 (p, q)
- output: 곱 pqRef
- Ch1 - 4p
프로시저, 계산 문제, 함수의 연관 관계
- 프로시저와는 달리, 함수 또는 계산 문제는 입력을 사용하여 출력을 어떻게 계산하는지에 대한 정보를 주지 않는다.
- 동일한 입출력 사양을 만족하거나 동일한 함수를 구현하는 많은 다른 프로시저가 존재한다.
- 때로는 동일한 프로시저가 다른 함수를 위해 사용될 수 있다.
- 함수와는 달리, 계산 문제는 모든 입력에 대해 하나의 유일한 출력을 명시할 필요는 없다.
- 함수와 계산 문제는 다르게 정의되지만 서로 연관되어 있다.
- 정의역 각 원소에 대해 프로시저를 적용하여 출력을 확인하는 방법으로 원상 문제를 풀면 비용이 클 수 있지만, 모든 함수에 적용 가능한 더 나은 방법은 없다.
- 원상 문제를 임의의 함수가 아니라 특정 종류의 함수에 적용하는 방법을 사용하면, 원상 문제를 풀기위한 빠른 프로시저가 존재하여도 실질적인 문제를 해결하는데 도움이되지 않을 수 있다.
- 계산산의 어려움과 가능성 사이에서 길을 찾는 것이 필요하다.
- 선형 함수들을 사용하여 실질적인 문제를 모델링하고 이 함수들을 사용하여 원상 문제를 풀 수 있다.
확률
확률이론
무엇이 일어날 수 있는지, 그리고 그것이 일어날 가능성이 얼마나 되는지에 관한 것이다.
Ref
- Ch1 - 10p
- 확률 - 위키백과
확률분포
유한한 정의역 𝛀에서 음수가 아닌 실수의 집합 R+로의 함수 Pr(⋅)는 만약
이면 (이산) 확률분포이다.
- 정의역 : 실험결과(outcome)
- 치역 : 실험결과의 확률
확률은 실험결과의 상대적인 가능도(relative likelihoods)에 비례한다고 가정한다. 확률은 가능도의 수학적 개념을 의미하기 위해 사용한다.
가능도(likelihood) : 상식적인 개념을 의미하기 위해 사용
- 균등(uniform)분포 :모든 실험결과가 동일한 가능성을 가지며 동일한 확률이 할당되는 경우이다.
- 비균등분포 : 서로 다른 실험결과가 서로 상이한 확률을 가지는 경우이다.
Ref
- Ch1 - 10~11p
- 확률분포 - 위키백과
사건과 확률의 합(Priciple 1.4.5 확률이론의 기본 원칙)
어떤 사건에 대한 확률은 그 사건을 구성하는 실험 결과들에 대한 확률의 합이다.
Ref
- Ch1 - 12p
랜덤 입력에 함수 적용
- 함수가 가역함수이면 확률이 보존된다.
- 다양한 출력에 대한 확률은 입력에 대한 확률과 매칭된다.
- 입력이 균등분포에 따라 선택되면, 출력의 분포도 또한 균등분포가된다.
Ref
- Ch1 - 12~13p