집밖은 위험해

이산 확률 분포 discrite probability distribution

- 주사위 눈의 값과같이 (셀수 있는) 이산적인 확률 변수를 갖는 확률 분포

이산 균등 분포 discrete uniform distribution

- 모든 확률변수에서의 확률 값이 동일(균일)한 확률 분포

초기하 분포 hypergeometry distribution

- 표본 조사시 모집단에서 표본을 비복원 추출을 하는 경우 이용됨

베르누이 분포 bernoulli distribution

- 베르누이 시행 : 서로 배반인 두가지 경우만 발생하는 사건

    ex. 동전 앞면/뒷면,  양품/불량품

- 베르누이 시행 확률 질량 함수

- 기대값과 분산

이항 분포 binomial distribution

- 일정 확률 p를 가진 독립시행을 n번 반복했을때의 확률 분포

- 이항분포의 확률 질량 함수 pmf와 이에 대한 표기를 다음과 같이 한다.

포아송 분포

- 발생 가능성 p는 매우 작지만 시행횟수 n은 충분히 큰 경우 사용하는 분포

- 포아송 분포는 이항 분포의 근사라 할 수 있음

- 포아송 분포의 확률 질량 함수와 포아송 분포를 따르는 확률 변수 X에 대한 표기

- 아래의 그림에선 시행횟수는 k, 발생 게인은 lambda 

확률 변수 random variable

- 관심 사건을 변수로 설정한 것

 => 확률 변수 X = 0, 1, 2, 3 중 하나의 값 -> X = 1, X = 2와 같이 표현

확률 분포표

- 확률 변수의 값과 그에 대한 확률을 나열한 표

이산 확률 변수 discrete random variable

- 확률 변수가 정수와 같이 셀수 있는 값을 가지는 경우 이산확률 변수라 부름

 => ex. 동전 앞면 수, 오타 수, 합격자 수 등

이산 확률 분포

- 이산 확률 변수에 대한 확률들의 분포

- 아래는 동전 2개를 던질때 앞면이 나온 수에 대한 이산 확률 분포

확률 질량 함수 probability mass function, pmf

- 각 확률 변수에 대한 이산 확률들, P(X=x_i) = p_i가 확률 질량 함수 pmf

연속 확률 변수 continuous random variable

- 확률 변수가 셀수 없는 경우 연속 확률 변수라 부름

 => ex. 시간, 무게 등

확률 밀도 함수 probability density function, pdf

- 어느 확률 변수가 어느 구간에 속할 확률을 결정짓는 함수

 => [1, 2]에 속할 확률, [1, 3]에 속할 확률 등

 기대값 expectation value

- 확률 변수 x_i와 해당 확률 p_i의 곱들의 합으로 시행시 기대되는 결과를 예측할 수 있음

복권 예제에서의 기댓값

- 복권을 뽑을때 받을수 있는 상금에 대해 아래와 같은 확률분포표가 제시된다고 하자.

- 한번 복권을 뽑는 경우 예상되는 상금은 다음과 같다.

 => 기대값 E(x)는 한번 시행시 예상 결과로 이 경우에는 12원의 상금이 기대된다.

분산 variance

- 확률 변수가 기댓값을 중심으로 얼마나 퍼져있는지 정도

- 기대값 E(x) = mu로 표기하나 mu가 음수인 경우도 존재하므로

 1. 확률 변수 X와 기대값 mu의 차이를 제곱

 2. 차이의 제곱에 대한 평균을 구함

표준 편차 standard variation

- 분산 Var(X)는 차이 제곱에 대한 평균을 구하므로 기존의 확률 변수 X와 단위가 다름

 => 단위 일치를 위해 제곱근을 수행하여 구함

조건부 확률 conditional probability

- 정보가 주어졌을 떄 어떤 사건이 발생할 확률

주사위와 조건부 확률 - 상황

- 주사위 던질때 1의 눈이 나올 확률 1/6

- 짝수가 나올 확률 1/2

주사위와 조건부 확률 

- 주시위가 3이하라는 정보가 주어짐. 짝수일 확률은 몇일까? 여전히 1/2?

- 위 경우 짝수인 경우는 세가지 중 하나

 => 3 이하라는 정보가 있을때, 짝수일 확률은  1/2(전체의 절반)가 아니라 1/3(3이하 수중 하나)

조건부 확률

- 주어진 정보로 사건 B가 발생하였다는 가정하에 사건 A가 발생할 확률

베이즈 정리

- 조건부 확률을 이용해 어느 사건의 발생 확률을 구하는데 사용되는 정리

베이즈 정리의 예시 - 공장

- 생산 라인 1(생산률 20%, 불량 비율 5%), 생산 라인 2(생산률 50%, 불량 비율 4%), 생산 라인3(생산률 30%,불량률 3%)

=> 문제 : 1) 전체 불량률은 몇일까? 2) 불량품이 첫 라인에서 만들어질 확률은?

전체 불량률

- 생산 라인 1 : 0.2 x 0.05 = 0.01

- 생산 라인 2 : 0.5 x 0.04 = 0.02

- 생산 라인 3 : 0.3 x 0.03 = 0.09

=> 전체 불량률 = 0.39

표본 공간 분할과 사건 A

- 표본 공간 S는 분할된 사건 B1, B2, B3, B4로 구성

사건 A가 주어졌을떄 조건부 확률

- 사건 A에 대한 정보가 주어진 경우, 사건 B_i에 대한 조건부 확률

베이즈 정리 bayes theorem

- 표본 공간을  B1 , ... Bk로 나눌 경우 사건 A와 조건부 확률 B_i는 아래와 같다.

    => 베이즈 정리 : 사전 확률과 분할 사건에 대한 사후확률을 구하는 아래의 식

베이즈 정리를 이용한 전체 불량률 구하기

- 전체 불량률 P(A)은 얼마나 되는가?

1. 사건 정의

- B1 : 제품이 생산 라인 1에서 만들어질 사건

- B2 : 생산 라인 2에서 만들어질 사건

- B3 : 생산 라인 3에서 만들어질 사건

2. 우도 likelihood 정리

- 각 라인에서 생산한 제품이 불량률일 확률

3. 베이즈 정리로 구한 전체 불량률

- 베이즈 정리로 사후확률과 사전 확률은 아래와 같이 정리할 수 있다.

- 지금 구하고자 하는것은 전체 불량률, 즉 사후확률 P(A)를 구하므로 다음과 같이 정리된다.

4. 베이즈 정리로  불량 제품을 뽑앗을때 1번 라인에서 생산한 제품일 확률

1. 미분

미분 derivative

- 변화하는 정도. 즉, 기울기

평균 변화율 average rate of change

- y = f(x)가 주어질때 x = $x_0$, x = $x_1$ 사이에서의 평균 변화율. 아래와 같이 정의

 => 두 점을 지나는 직선의 기울기

$\frac{\Delta y}{\Delta x} = \frac{f(x_1) - f(x_0)} {x_1 - x_0}$

미분 계수 differential coefficient

- 함수 y = f(x)가 주어질때, x = a에서의 미분계수는 다음과 같이 정의

$lim_{\Delta x -> 0}  \frac{f(a + \Delta) - f(a)} {\Delta x}$

- 위 비분계수가 수렴하는 경우 극한값은 f'(a)

 => x = a에서 미분 가능함.

미분 계수와 미소 증분

- 미소 증분 increment $\Delta x$: x가 0에 가깝지만 0이 아닌, 아주 작은 값의 증가.

- x = a에서 증분 값 $\Delta x$가 0에 가까워질때 평균 변화율은 순간 변화율이 되어 f'(a)로 표기

도함수 derivative

- 함수 y = f(x)가 주어질때, f(x)의 도함수를 아래와 같이 정의

f'(x) = $\frac{dy}{dx}$ = $\frac{df}{dx}$ = $lim_{\Delta x-> 0} \frac{f(x + \Deta x) - f(x)}{\Delta x}$

상미분 ordinary derivative

- 일변수 함수 y = f(x)에 대해, 함수 f를  독립 변수 x에 대한 도함수

- 도함수와 동일

f'(x) = $\frac{dy}{dx}$ = $\frac{df}{dx}$ = $lim_{\Delta x-> 0} \frac{f(x + \Deta x) - f(x)}{\Delta x}$

편미분 particial derivative

- 다변수 함수 y = f(x, y)가 주어질때, 함수 f에 대해 독립변수 x와 y 각각에 대한 도함수

$\frac{\sigma f}{\sigma x}$, $\frac{\sigma f}{\sigma y}$

접선의 방정식

- y = f(x)에서 x = a에서 미분 가능한 경우, 접선의 방정식

y = f'(a)(x - a) + f(a)

2. 미분 법칙 

함성 함수의 미분 - 연쇄법칙

- z = f(y),  y = g(x)가 주어질때 z를 x에 대해서 미분하면. 즉, z = f(g(x))의 x에 대한 미분

$\frac{dz}{dx}$ = $\frac{dz}{dy}$ $\frac{dy}{dx}$ = f'(g(x)) g'(x)

로피탈 정리

- f(0) = g(0) = 0이고, f'(0)과 g'(0)이 존재하면 아래의 식이 성립

$lim_{x->0} \frac{f(x)}{g(x)}$ = $lim_{x -> 0} \frac{f'(x)}{g'(x)}$

1. 수열

수열 sequence

- 자연수 N 집합을 정의역, 실수 전체 집합 R을 공역으로 하는 함수

 => f : N -> R

- 보통 수열은 a(n)으로 표기되어 f(n) = $a_n$이 됨

- 함수와 구별되도록 아래와 같이 표기

$a_1$, $a_2$, . . . = {$a_n$}

무한 수열 infinite sequence

- 정의역 N이 무한한 대응 관계를 갖는 함수

등차 수열

- 이웃하는 두 항의 차가 d로 일정한수열

$a_n$ = $a_1$ + (n-1)d

등비 수열

- 이웃하는 두 항의 비가 r인 수열

$a_n$= $a_1$ $r^{n-1}$

수렴 Convergence

- 수열 $a_n$에서 n이 증가함에 따라 $a_n$이 일정 값 $\alpha$에 가까워지는 현상

      => 수열 $a_n$은 $\alpha$에 수렴

- n이 무한대에 가까워질때 $a_n$이 $\alpha$로 수렴 하는것을 다음과 같이 표현

     => n -> $\inf$, $a_n$ -> $\alpha$ or lim$a_n$ = $\alpha$

발산 divergence

- 수열 $a_n$ 이 수렴하지 않는 경우

- 무한대로 갈수록 하나의 값에 가까워지지 않고, 매우 커지거나 매우 작아짐 

=>   n -> $\inf$ => $a_n$ -> $\inf$ or lim $a_n$ = $\inf$ {=$-\inf$}

진동 osillate

- 여러 값에 가까워지기는 하지만 한개의 값에 수렴하지는 않는 경우

 => 진동도 발산

수렴 수열과 경계

- 수렴하는 수열은 절대값이 유계(한계가 존재, bounded)

- 충분히 큰 실수 M이 존재하고, 모든 자연수에 대해 다음이 성립

|$a_n$| <= M

단조 증가 수열과 단조 감소 수열

- 단조 증가 monotone increasing : 수열 $a_n$이 아래의 조건을 만족하면서 계속 증가하는 경우

$a_n$ <= $a_{n+1}$

- 단조 감소 monotone decreasing : 수열 $a_n$이 아래의 조건을 만족하면서 계속 감소하는 경우

$a_n$ >= $a_{n+1}$

2. 급수

무한 급수 infinite series

- 무한 수열 $a_n$의 모든 항을 합한 식

$\sum_{k = 1}^{\infty}a_k$ = $\lim_{n -> \infty} \sum_{k = 1}^{n}a_k$

무한 등비 급수

- 일반 항이 $a_n$ = $a r^{n-1}$인 무한 등비수열의 급수

=> S = a + ar + a$r^2$ + . . . 

양항 수열과 양항 급수

- 양항 수열 : 모든 항 $a_n$이 0이상인 수열

- 양항 급수 : 양항 수열의 무한 급수

교대 급수

- 단조 감소하는 양항 수열 $a_n$이 존재할때, 교대 급수는 아래와 같다.

 $\sum_{n=1}^{\infty}$ $(-1)^{n-1} a_n$

- 위 교대 급수가 수렴하기위한 필요충분 조건은 아래와 같다.

$\lim_{n -> \infty}$ $a_n$ = 0

3. 함수의 극한

극한

- 함수 f(x)에서 x가 a로 가까워질때 f(x)가 상수 b로 가까워지는 현상

 => x가 a로 수렴할 때, f(x)는 b로 수렴함

- 이를 아래와 같이 표기

     1. $\lim_{x->a} f(x) = b$ 

     2. x -> a    =>    f(x) -> b

극한 값 존재 여부

- x가 a로 가까위질때, + 방향에서 가까워짐과 동시에 -방향에서도 가까워지는 값이 동일하면 극한 값이 존재한다고 한다.

  * 임의의 수 a에서 함수 f(x)가 끝어져, +방향과 -방향에 따라 f(x)서로 다른 값으로 수렴할수 있기 때문

$\lim_{x -> a^{-}} f(x) = b$ = $\lim_{x -> a^{+}} f(x)$ = $\lim_{x -> a} f(x)$ = b

4, 함수의 연속

함수의 연속

- 다음의 세 조건을 만족하면 f(x)는 x = a에서 연속함

 1. x = a에서 f(a)가 존재

 2. $\lim_{x -> a}$ f(x)도 존재

 3. $\lim_{x -> a}$ f(x) = f(a)

함수와 연속

- 함수 f(x)가 특정 구간에서 모든 점에 대해 연속일 떄 => f(x)는 그 구간에서 연속 continuous

- 모든 점에서 연속이지 않은 경우 => f(x)는 그 구간에서 불연속  discontinuous

최대 최소 값 정리 extreme value theorem

- 닫힌 구간 [a, b]에서 f(x)가 연속이면, 반드시 이 구간에서 최대 최소값을 가짐

 * 닫힌 구간 [a, b] : a ~ b사이 범위. a와 b 포함

 * 열린구간 (a, b) : a ~ b사이 범위이나 a와 b는 불포함

중간값 정리 intermediate value theorem

- 아래의 조건을 만족할 떄

 1. 닫힌 구간 [a, b]에서 f(x)가 연속

 2. f(a) < f(b)

- 중간값 정리 : f(c) = u인 c가 닫힌 구간 [a, b]에서 적어도 하나는 존재

알고리즘과 복잡도

- 복잡도가 O(n) 처럼 작은 경우가 있지만 복잡도가 매우 큰 알고리즘도 많음

NP 완비 문제

- 풀기 쉬운지 어려운지도 모르는 문제들

P 문제

- 결정론적 알고리즘 deterministic algorithm으로 다항식 시간에 해결할수 있는 문제

- 결정론적 알고리즘 : 명확하게 결정되어있어 데이터 입력시 어느 순서대로 동작하는지 알수있는 알고리즘

NP 문제

- 비결정론적 알고리즘 nondeterministic algorithm으로 다항식 시간에 해결할수 있는 문제

- 비결정성 알고리즘 : 결정 가능한 경우가 여러개로 나뉘어져 적당한 경로러 선택해 나가는 알고리즘

=> 가장 적절한 경로를 잘 선택한 경우 다항식 시간으로 해를 찾을수 있는 문제를 NP 문제라 부름

근사 알고리즘 approximation algorithm

- NP문제는 최악의 경우 복잡도가 지수적으로 됨.

 => 최적해는 아니더라도 최적해에 가깝기만 하면 됨.

- 최적해에 가까운 근사해를 구하는 (결정론적) 알고리즘

휴리스틱 알고리즘

- 해를 얻을때까지 경험해가는 알고리즘

- 최적해의 계산 비용이 크고, 근사해로도 충분한 경우 사용

백트래킹법

- 모든 가능성을 조사하지 않고도 최적해를 얻을수 있는 문제도 존재

- 하나의 시행을 통해 조사하다가 해를 구하지 못하면 이전으로 되돌아가 다른 경우를 조사

=> 해를 찾을떄까지 백트래킹 후 다른 경우를 조사하는 방법

백트래킹 방법의 예시

1. 수도크 플기

분할 통치법

- 잘 파악된 부분을 조금씩 넓혀가 결과를 찾음

- 해에 접근하는 방법에 따라 능률이 좋거나 나빠지기도 함.

탐욕법 greedy algorithm

- 현재 상태에서 볼때 가장 좋은 경우를 따라가는 방법

- 당장의 성능 개선이 보임

- 지역적 최선의 선택이 전역적으로 좋다고 보장할 수 없음

=> 당장의 최적의 방향으로만 쫓다간 지역해에 수렴함. 전역해에 도달못하는 경우 발생

탐욕법의 예시

1. 다익스트라 알고리즘

2. 프림 알고리즘

재귀적인 recursive 방법의 한계

- 재귀적 방법은 문제를 간단한 부분 문제로 만듬

- 하지만 부분 문제의 크기 합을 작게 유지시켜야만 효과적임

- 부분 문제의 크기가 균형이 맞지 않을시 복잡도가 지수적으로 증가

 => 재귀적인 방법의 한계로 인해 동적 계획법 이용

동적 계획법 dynamic programming

- 부분 문제들의 답을 별도의 표에 기억

- 필요할때마다 표를 참조

   * 재귀적 방법의 문제 : 재귀적인 방법에선 그 표의 값을 매번 새로 계산했었음

=> 동적 계획법은 부분 문제의 답을 기억. 이후 다시 계산하지 않음

균형법

- 분할 통치법에서 모든 문제를 같은 크기의 부분 문제로 나눠서 풀거나, 균등하지 않게 나눌수도 있음.

=> 부분 문제의 크기를 균등하게 하면 더 좋은 알고리즘을 얻을 수 있음

균형법의 예시

- 합병 정렬 알고리즘

알고리즘설계기법