[알고리즘 기말 이론]

탐욕알고리즘은 선택할 당시의 최적의 값을 구한다.
하지만 그 최적의 선택이 전체적으로 볼때 최적의 선택일지는 보장이 안됨.


진약수는 1과 자기자신을 제외한다.
여기서 최소값과 최대값을 찾아서 곱하면 N이 나올것이다.
따라서 N을 구할때의 최소비교횟수는 진약수의 개수를 최대 최소 동시에 찾기 공식에 넣으면 됨.

최대값 찾기 : n-1
차대값 찾기 : n+lgn-2
중앙값 찾기 : 5/6 * n
최대최소 동시에 찾기  : 홀수일때[ 3n/2- 3/2] 짝수일떄[3n/2-2]
차대키의 후보들의 집합은 : 최대키한테 진 집합들이다.

적대적 논증 : 최악시간복잡도가의 lower bound를 구함.

몬테 카를로 알고리즘 :
반드시 맞는 답을 주지는 않음.
오히려 그 답의 추정치를 제공하고 그 추정치가 맞는 답에
가까운 확률은 알고리즘의 사용시간이 증가할수록 커진다.

샤워드 알고리즘 : 
항상 맞는 답을 준다.
최악의 경우보다 평균의 경우 훨씬 빠르게 실행되는 결정적 알고리즘에 적합

라스베이거스 알고리즘 :
항상 맞는 답을 준다.
하지만 가끔 답을 주지 않음.

다루기 힘든 문제(intractable)는 다차시간안에 풀지 못하는 알고리즘임.

다차시간 알고리즘은 최악시간복잡도의 상한이 입력크기의 다항식 함수가 되는 알고리즘.

다루기 힘든 정도에 대하여 세가지 분류
1. 다차시간 알고리즘을 찾은 문제
2. 다루기 힘들다고 증명된 문제
3. 다루기 힘들다고 증명되지 않았지만 다차시간 알고리즘도 찾지 못한 문제

입력크기 n은 n 수 그자체가 아닌 필요한 문자의 개수로 정의한다.

다루기 힘든 문제의 종류

1. 지수 이상 크기의 출력을 요구하는 문제이다.
2. 지수 이상 크기의 출력을 요구하지 않고 문제를 다차시간안에 풀 수 없다고 증명할 수 있는 경우이다.

Halting probelm은 다루기 힘든 문제에 속함. OX 문제.
다루기 힘든 문제는 모두 NP집합에 속하지 않는다고 증명되어있다.
하지만 다루기 힘들 것처럼 보이는 문제는 모두 NP집합에 속한다.

다루기 힘들다고 증명되지도 않았고, 다차시간 알고리즘도 찾지 못한 문제
0-1 knapsack, 외판원문제, 부분집합의 합, m-coloring, 해밀톤 문제
이러한 문제들은 사례를 제한한 부분집합에서는 다항시이 존재하지만 모든 사례에 대해서는 존재하지 않는다.

NP
1. 결정문제(진위판별문제)
2. 최적화 문제
최적화 문제에 각각 대응되는 결정문제가 존재한다.
0-1 knapsack, 외판원문제, 부분집합의 합, m-coloring, 해밀톤 문제들은 결정문제와 최적화 문제 모두 다차시간 알고리즘을 아직 찾지 못햇다.
하지만 어느 하나라도 최적화 문제에 대한 다차시간 알고리즘을 찾을 수있다면 그에 대응하는 진위판별도 다차시간 알고리즘이 있따.
최적화 해답을 구한다면 진위판별은 쉽게 얻을 수 잇다.

P는 다차시간 알고리즘으로 풀 수있는 모든 진위판별 문제의 집합.

다차시간 알고리즘을 만들어내지 못햇지만, 다차시간으로 풀수없다고 증명한 문제라면
P에 속할 가능성도 있다. 속하지 않는걸 증명할려면 불가능하다고 증명해야함. --> 아무도 증명 X

비결정 알고리즘추측 : 

추측단계 : 비결정
단순히 추측한 해답을 만듬.
검증단계 : 결정
그 추측한 해답을 검증함.

다차시간 비결정 알고리즘은 검증단계까 다차시간 알고리즘인 비결정 알고리즘이다.
NP는 다차시간 비결정적 알고리즘으로 풀 수 있는 모든 진위판별 문제의 집합이다.
N(nondeterministic)P(polynomial)의 약자
NP에 속하기 위해서는 다차시간에 검증을 하는 알고리즘이 반드시 존재해야 한다.
외판원 결정 문제는 다차시간 알고리즘이 있으므로 NP에 속함.
검증하는 다차시간 알고리즘이 있다고 해서 문제를 푸는 다차시간 알고리즘이 존재하는건 X

비결정 알고리즘과 NP의 개념을 도입한 목적은 알고리즘을 분류하기 위해서이다.
0-1 knapsack, 외판원문제, 부분집합의 합, m-coloring, 해밀톤 문제들은 결정문제 NP에속함.

P에 속하는 문제는 NP에 속한다. 당연한것

NP에 속하지 않는다고 증명된 문제들은 다루기 힘들다고 증명된 문제.
ex) 멈춤검사, 프레스버거 산술문제

P=NP인가가 컴퓨터 사이언스에서 중요한문제.
P=NP라면 지금까지 알고있는 결정문제를 푸는 다차시간 알고리즘이 있다는것.
증명할려면 NP에 속한 각각의 문제에 대해 다차시간 알고리즘을 모두 찾아야함.
P!=NP NP에속하면서 P에는 속하지 않는 문제를 찾아야함.

NP-complete
0-1 knapsack, 외판원문제, 부분집합의 합, m-coloring, 해밀톤 문제들은 결정문제 같이 하나라도 P에 속하면 나머지 모든 문제들도 P에
속해야한다. 이러한 문제들을 NP-complete라고 한다.

CNF 문제 (논리판별 문제)
logical variable은 true or false를 가지는 변수
literal은 not(부정)
clause(절)은 논리연산자 or를 사이사이에 끼운 리터럴의 나열
CFN는 논리식으로 논리연산자 and를 사이사이에 끼운 절의 나열
CFN진위판별 문제 주어진 CNF 논리식을 true로 만드는 참값 대입이 존재하는지 판별하는 문제.

쿡의 이론
CNF가 만약 P에 속한다면 P=NP가 사실임을 증명하는 논문 발표

변환알고리즘
진위판별 A의 각 사례를 진위판별 문제B의 사례y로 매핑하는 변환알고리즘.

NP-complete
1. NP에속한다.
2. NP에 대하여 A와 B는 다차시간 변환 알고리즘이 존재해야함.

따라서 NP-complete 문제 하나라도 P에 속한다고 증명하면 P=NP라고 결론 가능.\

CNF 만족은 NP-complete이다.
ex) 0-1 knapsack, 외판원문제, 부분집합의 합, m-coloring, 해밀톤 문제들은 결정문제 CNF 
만약 진위판멸 문제 A가 다차시간 알고리즘으로 풀수 있고 B로 변환가능하다면 B도 NP-complete

CNF-sat
3-sat 
U-tsp, D-tsp sum of sub-set, knapsack
NP-complete는 NP에속함
프레스버거,산술문제,홀팅프로그램은 NP에 속하지않으므로 , NP-complete도 아님.

NP-Hard, NP-easy, NP-equivalent

만약 B를 푸는 다차알고리즘을 사용하여 A를 다차시간에 풀 수 있다면 문제 A는 문제 B로 다차시간 튜링 축소변환가능이라고 한다.

만약 NP-complete 문제 A에 대해서 B로 다차시간 튜링 축소변환가능하다면 B는 NP-Hard라고 한다.
NP문제는 모두 NP-hard 문제로 축소변환가능하다.
NP-Hard 문제를 푸는 다차시간 알고리즘이 존재한다면 P=NP가 성립
NP-complete 문제는 모두 NP-hard 문제이다.
따라서 NP-complete 문제에 상응하는 최적화 문제는 모두 NP-Hard이다.
NP-hard 문제를 푸는 다차시간 알고리즘이 없는데 그러한 문제를 풀고 싶으면 어떻게 해야할까?
TSP를 푸는데 되추적알고리즘과 분기한정 알고리즘은 모두 최악의 경우 다차시간이 아니다.

근사알고리즘을 사용 
최적해를 얻는다는 보장은 없지만 최적에 상당히 가까운 해를 내준다.
구 한 해가 얼마나 최적에 가까운지를 보장해주는 범위(bound)값을 얻을 수 있따.

최적여행경로에서 어떤 이음선이라도 하나 제거하면 최소신장트리가 될것이다.
최소신장트리의 가중치는 최적여행경로가중치보다 작아야한다.
다차시간안에 최소신장트리 얻기 가능.
신장트리를 두번 횡단함으로써 그 신장트리를 모든 도시를 방문하는 경로로 바꿀수 있음.
지름길을 택해서 마디를 두번이상 방문하지 않는 경로로 바꿀수잇다.

TSP 근사방법
1. 최소비용 신장트리를 구한다.
2. 트리를 두번 횡단하여 모든 도시를 방문하는 경로를 구축한다.
3. 지름길을 택하여 두번 방문 안하게 여행경로를 구축
최적은 아니지만 최적에 가까움이 보장됨.

크루스칼 알고리즘, 프림 알고리즘을 통해서 MST를 만드는 것은 다차시간으로 얻을 수 있다.
최적에 가까운것이지, 최적은 아님.
Bin packing 근사 알고리즘
1. 차례로 채우기 
2. 큰 아이템부터 차례로 채우기

0-1배낭문제 동적계획법 시간복잡도는 세타 NW이지만
다항시간이라 할수 없다.
Backtracking은 DFS 이지만 branch&bound는 BFS를 기준으로 하는 Best-first-search이다.

계산복잡도는 lower-bound를 구한다.

적대적논증법은 가능한한 알고리즘을 어렵게 만들려는것이 목표이다.

최적화 문제가 NP-complete집합이라면 NP-hard라고 할 수있다.

quick sort에서 랜덤으로 피봇을 정한다면 big of (n^2)이다.