rule of sum
두 사건 A,B () 가 일어날 경우의 수를
A 또는 B가 일어날 경우의 수는 m+n 이다.
n()=n(A)+n(B)=m+n
rule of product
두 사건 A,B 에서
A, B가 동시에 일어날 확률은 mn 이다.
n()=n(A)n(B)=m*n
서로 다른 원소들을 순서를 고려하여 일렬로 배열하는 것.
서로 다른 n개의 원소를 한 줄로 배열하는 순열의 개수는
1부터 n까지의 모든 자연수의 곱을 n의 계승 또는 n factorial 이라고 읽으며 로 나타낸다.
서로 다른 n개의 원소 중에서 r개를 선택하는 순열의 수
= 단
=
P(n, r)로 표현하기도 한다.
같은 것을 포함하는 순열
n개 중 같은 것이 각 p개, q개, ..., r개씩 있을 때, n개를 일렬로 배열하여 만들 수 있는 순열의 수는 단p+q+...+r=n
서로 다른 n개의 원소 중, 순서를 생각하지 않고 r개를 택할 때. 이것을 n개의 원소에서 r개를 택하는 조합이라 하고, 그 조합의 수를 nCr로 나타낸다.
, 로 표현
을 전개 했을 때,
이 때 nCr을 이항계수(binomial coefficient)라 한다.
파스칼의 삼각형에서는 이항 계수가 다음과 같이 만들어 진다.
n,r이 음이 아닌 정수이고 일 때
조합론적 증명: n개의 물체에서 r개를 고른다 하자. n개중 1개를 고정, A라 한다. 그럼 구하고자 하는 경우의 수는 A가 포함되는 경우와 포함되지 않는 경우 2가지로 나눈다.
전자의 경우 나머지 n-1개중 r-1개를 고르고
후자의 경우 n-1개중 r개를 고르면 되므로
합의 법칙에 의해
대수적 증명:
확률변수
변수 X가 취할 수 있는 모든 값이 이고 X가 이들 값을 취할 확률 이 정해져 있을 때, X를 확률 변수라 한다.
X가 이산적인 값을 취할 때 이러한 확률을 이산적 확률(discrete probability)이라고 한다.
확률분포
확률 변수 X가 취하는 값 와 X가 를 취할 확률 와의 대응 관계를 X의 확률분포라고 한다.
X의 기대값, 평균
분산(variance): 확률 변수 X의 평균이 m일 때
표준 편차(standard deviation)
분산의 양의 제곱근
베이즈의 정리(bayesian theorem)
어떤 사건이 서로 배반하는 원인 둘에 의해 일어난다고 할 때 실제 사건이 일어났을 때 이것이 두원인 중 하나일 확률을 구하는 정리.
사후확률(posterior)
어떤 사건이 만든 상황에서, 그 사건이 일어난 후 앞으로 일어나게 될 다른 사건의 가능성을 구하는 것
P(H): 사전확률(prior)
Hypothesis: 가설, 어떤 사건이 발생했다는 주장
Evidence: 새로운 정보
베이즈 정리는 본래 역확률 문제를 해결하기 위한 방법이었다.
P(H|E)를 알고 있을 때 전제와 관심사건의 관계가 정반대인 P(E|H)를 구하는 방법
최근 빅데이터를 통해 기존 사건의 확률을 대략적으로 알아낼 수 있게 됨으로 사회적 통계나 주식에서 빅데이터를 이용한 베이즈 정리 활용이 이용된다.
하지만 베이즈 정리를 이전의 경험과 현재의 증거를 토대로 어떤 사건의 확률을 추론하는 알고리즘으로 볼 수도 있다.
1. 어떤 사람이 병A에 걸려있을 확률을 몰라서, 인구 일반이 해당 질병에 걸릴 확률인 1%의 유병률을 가정
2. 정확도가 90%인 검사를 받았더니 양성
3.어떤 사람이 양성 판정을 받았다는 새로운 사실을 토대로 이 사람이 실제 병에 걸려있을 확률을 알아낼 수 있다.
이 문제에서 베이즈 정리가 알려주는 것은 '어떤 사건 A가 일어났다고 가정할 때 B라는 자료를 얻게 될 확률'을 알고 있다면 자료에 근거해서 어떤 사건이 일어날 확률을 새로 계산할 수 있다.
수학적인 일반화: n개의 사건 ~이 표본 공간 S를 분할할 때 공사건이 아닌 사건 B에 대하여 P(B)는 확률의 덧셈정리에 의해 아래와 같이 나타낼 수 있다.
이 때 조건부 확률는
확률을 사각형으로 표현하면 쉽다.
n개의 비둘기 집에 n+1 마리 이상의 비둘기가 들어갔다면, 두 마리 이상의 비둘기가 들어간 비둘기 집이 적어도 하나 있다는 법칙
수학적 귀납법에서와 같이 첫 번째 요소가 정의 되고, n+1번째의 요소는 바로 앞의 n번째와 그 이항의 요소와의 관계로서 정의되는 경우를 말하며, 재귀적 관계로 표현된다.
1. 주어진 문제를 원래의 문제와 같은 형태의 더 작은 문제들로 분할한다.
2. 가장 작은 문제로 분할된 문제들의 해를 구한 후, 최종적으로 이들을 결합하여 주어진 문제의 해를 구한다.(분할정복?)
다음과 같이 재귀적 관계식으로 정의된다.
fib(0)=0, fib(1)=1
fib(n)=fib(n-1)+fib(n-2)
심심해서 만들어봤다...
#include<iostream>
using namespace std;
int fib(int max)
{
if (max == 0) return 0;
if (max == 1) return 1;
return fib(max - 2) + fib(max - 1);
}
int main()
{
int z = 0;
int o = 1;
for (int i = 0; i < 10; i++)
{
int c = z + o;
cout << "fib" << i + 2 << " = " << z << '+' << o << endl;
z = o;
o = c;
}
cout << fib(10) << endl;
}
void hanoi(int n, char from, char tmp, char to)
{
if (n == 1)
printf_s("원반 1을 %c에서 %c로 옮긴다.\n",from,to);
else
{
hanoi(n - 1, from, to, tmp);
printf_s("원반 %d을 %c에서 %c로 옮긴다.\n",n, from, to);
hanoi(n - 1, tmp, from, to);
}
}