danny-factory

degree = 차수

최고차항만 비교해보면 비교적 쉽게 알 수 있다.

Ex)

Total Probability :

{ A1, A2 …. , An } -> partition of S (샘플 스페이스 전체의 파티션이다)

• Independent

  P(A|B) = P(A)

  P(B|A) = P(B)

   

  • P(A∩B) = P(A)P(B)

     

     

• Combinatorial Analysis

1. Permutation ( 순열 ) : 서로 다른 n개를 일렬로 나열하는 것. Line arrangement of n different objects

   (순서를 고려해야한다)

• Group Permutation : 중복이 있는 것의 수열.

  N = N1 + N2 + …. Nk

   

  Ex) 10개의 공 = 빨강 5개 + 흰색 3개 + 파랑 2개

  중복이 있는 것들의 팩토리얼만큼 나눠준다

  • 조합의 개념과도 이어진다

   

   

• Circular Permutation (원순열)

(n개의 중복이 생기므로)

(조금 더 심화한 문제. 어떻게 중복이 되는 지와 자리 모양을 살펴봐야한다)

• Combination (조합)

  = Select r objects out of n ones. nCr

  순열과의 다른 점: 순서가 필요 없다!

  

   

  [ 외워두면 좋을 공식 ]

  

   

  

  전체 n+m명이 있을 때 (남 : n, 여: m) 남녀 각각 0~r명까지 뽑는 경우의 수라고 보면 된다

  (배반사건의 합) -> 이항정리와 연결된다

   

   

  • Binomial Theorem

    이항정리의 기본 공식

    

     

    이를 응용하여 2^(n-1) 등을 구할 수 있다.

     

    중요한 것은 미분을 해서 얻어지는 식이다

    

     

    

     

    이것이 중요한 이유는 이 유도로 인해 이항분포 평균, 분산 유도식이 얻어진다

    

    이항분포의 평균 = np

    분산 = np(1-p)

    이 둘을 구할 때 위의 식을 이용해야 한다

     

     

  • 멱급수

     

    

    등비급수로 쉽게 f(x)를 구할 수 있다

    

     

     즉, 멱급수를 구할 때 g(x)를 정의해서 미분을 이용해 구하는 방법도 있다.

이를 평균과 분산을 구할 때 사용한다!

• Stirling's formula

  = n!를 계산할 때 n이 커지면 계산이 힘들어진다. n!에 대한 대략적인 추정식이다

  

   

   

• Reliability

  = Duration of useful functioning of system

  

  시스템의 시작 시점부터 t라는 시간까지의 시스템이 얼마나 유효한지 확률적으로 표현한 것.

  어느 시점에서 고장나는 지는 모른다. (단지 확률일 뿐)

   

  Ex) Cascade 시스템(Series connection)에서의 Reliability

  

  전체 시스템의 Reliability.

  =

  • Assume that all modules are independent
  • 프로그램 작성 시에도 각 블록마다 독립적으로 만들어야 한다( 객체지향 )

Cf. 병렬 연결 (parallel connection)

전체 시스템이 동작할 확률 = 적어도 1개 이상의 모듈이 작동할 확률

시스템이 동작할 확률

Ex)

1. C3가 동작할 때 (Rx)

이런 식으로 Topology가 구성됨

1. C3가 동작하지 않을 때 (Ry)

이런 식으로 Topology가 구성됨

• 전체 R

    동작할 경우 : (1,4) / (2,5) / (1,3,5) …. / (1,2,3,4,5)

• Linear Equation

  Linear Equation은 으로 표현할 수 있다.

   

  이 때, a1,a2,….an, b는 상수이며 a들은 모두 0이 아니다

   

   

    만약 b가 0이라면, homogeneous linear equation 이라고 정의한다.

    Linear sytem에서의 해의 개수 (미지수 2개일 때3가지 경우)

    해가 적어도 하나인 경우 = Consistent

    해가 없을 경우 = Inconsistent 라고 정의한다.

미지수 3개일 때

Augmented Matrix란 ?

    Reduced Row Echelon Form

Echelon Form에 대한 사실들

• 모든 행렬은 고유의 Reduced Row echelon Form을 갖고 있다.
• Row echelon Form은 유일하지 않다. 여러가지 존재가 가능.

  하지만 모든 Row Echelon Form들은 동일한 위치에 Leading 1들을 갖고 있다.

  이를 Pivot Point라고 한다(Augmented matrix에서)

  또한 Leading 1을 포함하고 있는 Column들을 Pivot Columns라고 한다

   

   

   

  Homogeneous Linear System에 대해서

  Ex)

  

   

  모든 Homogeneous linear system은 Consistent하다.

  (모든 미지수 x가 0이라는 답을 갖기 때문에.)

  모든 미지수 = 0 : Trivial Solution

  다른 답 : Nontrivial Solutions

  그림으로 표현하자면 이렇다

   

  결론적으로

  

    이를 이용하여 아주 중요한 이론이 나온다

    명심해야 할 것! 이 Theorem들은 Homogeneous Linear System에만 적용 된다 !

    Linear system들의 적용

    4개의 점이 주어졌기 때문에 이 점들을 지나는 3차방정식을 구할 수 있다.

    다른 유형의 문제 ( 적분의 근사값을 구해보자 )

    4차방정식을 유도하여 적분을 구해본다.

• Insertion sort의 입력 : a list of keys + a new k

   

• Merge Sort

Running time :

• A divide-and-conquer approach :

1. Divide
2. Conquer
3. Combine

   

    

   

    

   Pseudo Code

   

    

   1. p=r 인 경우를 제외하고는 모두 성립. 즉, key가 하나일 때를 제외하기 위해 만든것

   2. 큐를 반으로 나눈다

   3~4. Merge-sort를 재귀함
   5. Merge

    

   Time

   

    

   결론적으로

   

    

   

   

    

   Recursive 문제에서

   

    

   첫째항 : subproblem의 개수*subproblem의 사이즈(기존대비)

    

   따라서

    

    

    

• Binary Search

  Binary Search 의 시간복잡도

  

   

   

• Selection Sort

  구버전의 시간복잡도 : n+n-1+n-2+ … 1 = Θ(n^2)

   

   

  [ 정리 ]

  	시간복잡도 Best	시간복잡도 Worst
  Insertion	Θ(n)	Θ(n^2)
  Merge	Θ(nlgn)	Θ(nlgn)
  Selection	Θ(n^2)	Θ(n^2)

   

  • Insertion Sort는 Stable (몇 개의 key만 움직이면 된다)
  • Selection Sort 는 Stable
  • Merge Sort 는 Unstable. Output을 담는 Array가 따로 필요하다

    즉, Merge sort는 Selection sort보다 빠르지만 Memory Requirement가 더 크다.

     

     

• Sorting problem

  + Input : A sequence of n number

  + Output : A permutation(reordering) . 작은 수부터 큰 순서로

   

• Insertion sort

  = A sorting algorithm using insertion

   

  Insertion : Given a key and a sorted list of keys, insert the key in to the sorted list preserving the sorted order.

   

   

  

   

  Pseudocode of insertion sort

  

   

Vector norm = length of vector

unit vector

Standard Unit vector

Orthogonal

Orthonormal