[이산수학] 알고리즘 유형(탐색, 정렬, 패턴매칭, 최적화)

<< 이산수학 3주차 >>

복습
- 암시적 정의(블랙박스) // 선행조건과 후행조건 & result
- 명시적 정의(화이트박스) // 재귀적인 방법

알고리즘 >> 입력으로부터 출력이 디테일하게 기술되어 있다.

------------------------------------------------------------------------------------------------------

알고리즘이란?
: 계산을 하거나, 문제를 풀기 위한 정확한 명령의 유한 순서

표현방법
- 자연어
- 흐름도
- 프로그래밍언어
- 슈도코드, 의사코드

"추적" 입력이 들어왔을 때, 출력이 어떻게 만들어지는지
max : Z* -> Z
max(<8,4,11,3,10>) = 11 의 과정을 알아보자.
----
max := a1
for i:=2 to n 
if  maxreturn max
----

알고리즘의 속성
- 명확성
- 정확성
- 유한성(종료)
- 효율성
- 일반성


알고리즘의 주요 유형
1. 탐색 문제(searching)
2. 정렬 문제(sorting)
3. 패턴매칭 문제(pattern-matching)
4. 최적화 문제(optimization)

① 탐색 알고리즘
: 리스트에 특정 원소가 있는지 판정, 있으면 index, 없으면 0이 리턴된다.
- 선형 탐색 : 처음부터
- 이진 탐색 : 반토막

(( 선형탐색, linear search ))
Z x Z* -> N0
(과정)
-----
i:=1
while( i≤n and x≠ai)
i:=i+1
if  i≤n  then  location:=i
else  location:=0
return location
----

(( 이진탐색, binary search ))
Z x Z* -> N0
----
i:=1
j:=n
while i m:=(i+j)/2
if


② 정렬 알고리즘
- 버블 정렬
- 삽입정렬

(( 버블 정렬, bubble sort ))
bubble : Z* -> Z*
----
for  i:=1  to  n-1
for  j:=1  to n-i
if  aj＞aj+1  then  interchange aj,aj+1
----

(( 삽입 정렬, insertion sort ))
insert : Z* -> Z*
----
for  i:=2  to  n
i:=1
while aj > ai
 i:=i+1
m:=aj
for  k:=0  to j-i-1
aj-k := aj-i-1
a:=m
----


③ 패턴매칭 문제
: 내가 원하는 데이터가 존재하는지.
pattern : A* x A* -> B


④ 최적화 문제
: 최적값(최소 또는 최소)를 구한다.
이때 쓰는 알고리즘을 greedy algorithm이라고 한다.
// Unsolvable Problem : 알고리즘이 존재 (ex.halting problem)
  모든 프로그램은 언제간 종료된다는 판정하는 프로시저를 만들수 있는가? >> 없다
  따라서 정지문제를 풀 수 있는 알고리즘은 존재하지 않는다.

욕심쟁이 알고리즘 : greedy algorithm
- 매 단계마다 모든 경우를 고려하기보다는 "best choice"을 한다.
- 반드시 최적해를 보징하지 X
- best choice를 무엇을 할지 중요하다.
  ex) 계산원, 강연할당

(( 1. 계산원 알고리즘 ))
: 가장 적은 동전 수 구하기
가정) 동전 종류로는 25센트, 10센트, 5센트, 1센트 

// 가장 큰 수를 choice하여 미리 배당함.
----
c1 > c2 > ... > cr; n;
for i:=1  to r
d1 :=0
while n≥ci
----

(( 2. 강연할당 알고리즘 )) 
: 강의실이 하나 있음. 시작/종료/사용시간을 가짐. 시간이 겹치지않게 가능한 강연을 많이 배정
// maximal 강연수를 선택한다.
// 선택 기준) starts earliest/ shortest/ ends earliest

earliest ending
----
sort  e1(가장 일찍 끝남)≤e2≤ ... ≤en(가장 늦게 끝남)
----


------------------------------------------------------------------------------------------------------

알고리즘 패러다임
1. brute-force 알고리즘(억지 알고리즘)
 - 순진한 풀이방식
 - 모든 경우를 고려
 - 쉽지만 계산양이 많아진다.
  ex) 선형탐색, 버블정렬, 삽입정렬

2. greedy 알고리즘(욕심쟁이 알고리즘)
 - 모든 경우 X, 최고의 선택 O
 - 때로는 최적해를 얻지 못하지만, 많은 경우에 적용
  ex) 계산원 알고리즘, 외판원 방문 알고리즘(TSP)

3. backtracking(백트래킹)
 - 먼저 찾아보면, 없으면 돌아와서 다른대안들을 찾아봄
 - 한수물리기
  ex) 깊이-우선 탐색

------------------------------------------------------------------------------------------------------

   행렬
row x column
- 행렬의 덧셈 : 행렬의 크기가 같아야함.
- 행렬의 곱셈 : (m x k) (k x n)  >> m x n
 //곱셈의 순서가 중요하다. AB≠BA

 [ 1 0 4  ]   [  2 4 ]       [ 2+12   4 ]    [ 14 4 ]
 [ 2 1 1  ]   [  1 1 ]   =  [ 4+1+3  8+1 ]   =   [ 8 9 ]  
 [ 3 1 0  ]   [  3 0 ]       [ 6+1     12+1 ]      [ 7 13 ]
 [ 0 2 2 ]                    [ 2+6     2  ]           [ 8 2 ]

- 항등 행렬(정방행렬) : identity  // nxn, 다른 행렬(A)와 곱하면 A가 나옴 
     A : mxn  B : nxk   >> AB : mxk
- 전치 행렬 : transpose  // 행과 열을 바꿈
- 대칭 행렬 : symmetric   // 대각선을 기준으로 두 공간을 바꿔도 똑같다
- 0-1 행렬 : 1은 참, 0은 거짓   //결합행렬(덧셈∨), 만남행렬(곱셈∧), 부울곱행렬(논리곱)
     A^[0]=In (종료조건) A^[r]=A^[r-1]A
     A^[r]=A⨀A⨀ ... ⨀A


행렬 곱셈 알고리즘
----
for i:=1 to m
for j:=1 to k
cij:=0
for q:=1 to n
   cij:=cij+aiqbqj
return C
----

행렬 부울곱 알고리즘
----
for i:=1  to m
for j:=1 to k
cij:=0
for q:=0 to n
   cij:=cij∨(aiq∧bqj)
return C
----

■마코프 체인■
: 확률 과정을 모델링하는 그래프
- 정점 : 한 state를 의미
- 간선 : 상태에서 상태로 전이를 나타냄 
 //모든 정점에서 나가는 확률 값이 "1"이어야함
 //종료조건은 M^(n-1) = M 일 때 종료된다.

>> 마코프체인이 성립한다? 모든 나가는 확률의 합이 1임.

(ex) 학생 성적
 //2학기 후, 3학기 후, 7학기 후에는? >> short-tem probability, transient probability라고도 불림
   그럼 무한대로 보낼 때는 long-term probability, stable probability라고 불린다.
(ex) 거북이 이동
(ex) 테니스 게임
 // 45:45 듀스일 경우, S(서버,60%) vs R(리비서,40%) 
(ex) 야구 게임