Computing/Algorythm

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-부분 문제 반복과 최적 부분 구조

MatrixChainAlgorithm

m(i,j)과 s(i,j) 어떤 정수 k (i≤kA_i A_(i+1)…A_j는 A_i…A_k와 A_(k+1)…A_j 의 곱으로 나누어 생각할 수 있으며 곱셈 연산 횟수는 다음과 같은 수식으로 나타낼 수 있다. m(i,j) = m(i,k) + m(k+1,j) + p_(i-1) p_k p_j m(i,j)과 s(i,j) 이때, 정수 k (i≤km(i,j)를 최소로 만드는 k 값을 s(i,j)에 저장한다. 즉, 곱셈 횟수 m은 n×n사이즈 테이블에 채워질 value 값이며 각각의 경우에 대한 k 값을 나타내는 s는 역추적을 할 때 사용하기 위한 테이블에 채워질 값이다. PRINT-OPTIMAL-PARENS (s, i, j)if i = j then Ai 를 출력 else “ ( ” 를 출력 PRINT-OPTIMA..

알고리즘

1.시간복잡도 1. n ≥ n0인 모든 n에 대하여 f(n) ≤ c · g(n)을 만족하는 양의 상수 c, n0이 존재하 면 f(n) = O(g(n))이다.(점근적 상한) 2. n > n0인 모든 n에 대하여 f(n) ≥ c · g(n)을 만족하는 양의 상수 c, n0이 존재 하면 f(n) = Ω(g(n))이다.(점근적 하한) 3. n > n0인 모든 n에 대하여 c1 · g(n) ≤ f(n) ≤ c2 · g(n) 을 만족하는 양의 상수 c1, c2, n0 이 존재하면, 즉 f(n) = Ω (g(n)) = O(g(n))이면 f(n) = Θ (g(n))이다. 2.알고리즘에서 중요순위 1. 정확성 2. 유효성 3. cpu 효율 time confidence 4. 메모리 사용량 space confidence3...