Computing

튜링머신과 정지문제(halting Problem)

튜링머신에 1개의 프로그램과 Input자료 1개를 넣으면서 "야 너 이게 유한한 단계 후에 답이 나올지 나에게 풀어보기 전에 미리 알려줄 수 있어?" 라는 질문을 할 때 이를 해결해줄 수 있는 특정한 단일 프로그램이 있는가가 정지 문제이다. 1936년 앨런 튜링은 이것을 해결할 수 있는 일반화된 방법은 없다라는 결론을 내렸으며[1], 이는 논리학적으로 결정불가능함(undecidable)이 증명된 최초의 문제다. 즉, 해결방법이 있다라는 가정에서 모순이 발생한다는 것을 보임으로써 증명한다. 정지 문제 판별 알고리즘이 있다고 가정했으니, 이에 따라 exit(a, i)라는 함수를 구현할 수 있다.이 함수는 a가 i 입력에 대해 정지하고 결과를 반환하면 참을, 아니면 거짓을 반환한다. a: 사용될 임의의 프로그..

동적프로그래밍 vs Memoization

동적 계획법(Dynamic Programming) -요약:부분문제 반복과 최적부분구조 우리가 전에 피보나치 수를 계산하기 위해 재귀 함수를 사용했었다.이는 같은 연산이 반복되기 때문이다. 그러나 이 함수의 진행 과정을 살펴보면 중복이 심하다는 것을 알수 있다. 위의 그림에서 보면 fib(2)가 여러번 반복되며 오버헤드가 증가함으로 결국 비효율적인 코드가 된다. 따라서 이러한 중복을 제거 하기 위해서 메모이제이션(Memoization)이라는 테크닉을 사용한다.이는 사전에는 나오지 않는 프로그래밍 테크닉이며, 계산된 값을 버리지 말고 저장한다는 뜻이다예를 들어 위의 그림에서 계산이 된 fib(2) 값을 저장해 놓고 있다가, 필요한 경우 계산없이 호출하게 된다.이렇게 저장되는 배열을 '캐시'라고 하며, 중간에..

Sequence Alignment Algorithm

서열비교: 여러 개의 서열 중에서 서로 닮은 부분과 다른 부분을 찾아냄 DNA 서열은 알파벳 ATCG로 구성된 서열 두 개의 다른 DNA 서열을 대응시켜 유사성을 비교 .......G A - C G G A T T A G .......G A T C G G A A T A G 두 서열은 서로 다른 길이를 가질 수 있고 또한 각 서열은 공백들을 가질 수 있음 주어진 두 서열에 공백들을 포함시켜 서로 같은 길이로 만든다 공백들끼리 대응되는 것은 허용되지 않지만 서열의 시작부분과 끝 부분에도 공백을 삽입할 수 있음 두 서열을 대응시키기 위해 score를 정함 한 열(column)에 같은 문자가 있다면 score는 +1 (match)다른 문자가 대응되었을 때는 -1 (mismatch)문자와 공백이 대응되었을 때는 -..

Ford Fulkerson Algorithm

–용량 제한 속성 : f(u,v) ≤ c(u,v) •각 간선의 유량은 최대 용량을 초과할 수 없다. –유량의 대칭성 : f(u,v)=-f(v,u) •u에서 v로 a만큼의 유량이 흐를 경우 v의 입장에서는 v에서 u로 –a만큼의 유량이 흐르는 것과 같다. • –유량의 보존 : ∑_(v∈V)▒〖f(u,v)〗=0 •각 정점에 들어오는 유량과 나가는 유량은 항상 같다.Dynamyc algoritym-부분 문제 반복과 최적 부분 구조