집밖은 위험해

미분방정식

미분 방정식 differential equation

- 종속 변수에 대한 독립 변수의 미분

- 미분 방정식에서의 미분이 상미분인지 편미분인지에 따라 분류됨

상미분 방정식 ordinary differential equation

- 종속 변수에 대한 독립변수의 상미분으로 이루어진 방정식

- 상미분 방정식은 1변수 함수의 미분 방정식

편미분 방정식 partial differential equation

- 종속 변수에 대한 독립 변수의 편미분으로 이루어진 방정식

- 편미분 방정식은 다변수 함수의 미분 방정식

공업 수학 관련 함수와 도함수 기초

미분 방정식에서의 수

- 상수 constan : 일정한 수

- 변수 variable : 변하는 수로 기호를 사용해 표기

함수의 형태

- y = f(x)

=> 두 변수 x와 y간의 상관 과계를 나타냄

함수의 관련 개념

- 독립 변수 independent variable : 독립적으로 변하는 변수

- 종속 변수 dependent variable : 독립 변수의 값에 따라 종속적으로 변하는 수

- 정의역 domain : 독립 변수의 집합

- 치역 range : 종속 변수의 범위

- 그래프 graph : 함수에 의해 대응되는 변수들의 관계를 그린것.

1변수/다변수 함수

- 1변수 함수 single variable function : y = f(x)과 같이 독립변수가 하나인 경우

- 다변수 함수 multiple variable function : y = f(x, y, z)와 같이 독립 변수가 여러개 인 함수

상미분 ordinary derivative

- 1변수 함수에 대한 미분

편미분 partial derivative

- 다변수 함수 z = f(x, y)는 독립 변수가 2개므로 미분도 x, y에 대한 경우 2가지가 있음.

- 각 독립 변수에 대한 미분을 편미분이라 하며 미분되지 않는 독립변수는 상수로 취급

양함수와 음함수

- 양함수 explicit function : 일반적인 함수로 독립변수 x와 종속 변수 y가 다른 항으로 나눠진 함수

- 음함수 implicit function : 독립 변수와 종속 변수가 같은 항으로 몰린 함수

수학적 모델링

 자연 과학 및 공학 분야에서 문제해결을 하기 위해서는 해당 현상이나 공학 문제를 수학적 모델링하여 방정식 구함

과학적 현상 방정식의 예시

- 파동 방정식, 맥스웰 방정식 등

방정식의 예시

- 대수 방정식 algebraic equation : 미지함수에 대한 사칙연산으로 나타내는 방정식

- 미분 방정식 differential equation : 미지수에 대한 미분으로 이루어진 방정식

- 적분 방정식 integral equation : 미지수에 대한 적분이 들어있는 방정식

- 미적분 방정식 integro-differential equation : 미지수에 대한 미분과 적분 요소를 가진 방정식

- 연립 방정식 : 여러개의 방정식들로 이루어진 방정식

해석적 방법론 analytic method

- 수학적 방법을 이용하여 해 solution을 구하는 방법

수치적 방법 numerical method

 - 컴퓨터를 이용하여 해를 구하는 방법

자연, 공학에서의 문제 해결 과정

1. 자연 현상, 공학 문제

2. 수학적 모델링

3. 대수방정식, 미분방정식, 연립방정식 등

4. 방정식의 해를 구함(해석적 or 수치적 방법으로)

5. 결과 도출

미분 방정식의 예시

1. 뉴턴의 제 2법칙

2. 가속도에 속도의 시간에 대한 미분 대입

3. m을 지우면

- 위와 같이 미분으로 이루어진 식이 미분 방정식 differential

종속변수, 독립변수

- 종속 변수 dependent variable : 독립 변수로 부터 얻을수 있는 미지 수

- 독립 변수 independent variable 

- 미분방정식을 푼다 = 미분방정식의 해를 구한다.

미분 방정식의 해

- g는 중력가속도 상수, c는 임의의 상수

초기 조건

- v(0) = 0과 같이 초기조건이 주어지면 임의의 상수 c를 구할수 있으며, 해를 정리할 수 있음.

수치 해석 전반 정리

1. 수치해석 시작

수치해석은 무엇? 왜 해야하는가? 어떻게해서 수학문제릃 해결할수 있는가?

-> 오차 -> 알고리즘

2. 변수가 하나인 비선형 방정식

이것의 솔루션 해를 찾기 힘들면

어떤 수치적인 방법을 찾을수 있겠는가 소개

bisection method, secant method, newton's method, muller's method 등 봄

3. 이산 데이터를 다항식으로

이러한 해를 찾는 방법들이 끝나면

실험이나 자현현상의 데이터는 끊어짐 연속되지 않은 이산적인 데이터

이산 데이터를 어떻게 스무스한 커브로 만들까?

-> largrange polynomial, divided difference

hermit interpolation, spline

4. 실제에 가까운 값 구하기

미분이 가능한 도함수 경우만 다룸

적분 역시원시함수로 정적분값을 정확한 가질수 있었음.

위와 같이 정확한 값을 못구하는 경우 어떻게 최대한 true value에 가까운 값을 구할수있는 방법

5. 초기치가 주어진 미분방정식을 해석적 방법으로 풀수 없는 경우

이후 공헙 수학, 미분방정식 문제를 다룸

특히 초기치가 주어진 미방 문제가 있을떄

해석 해 analytic solution, 미방 해를 손으로 풀수 없는 경우 어떻게 풀까?

taylor method나 runge-kutta method, predictor-crrector method 등 여러 방법들을 서로 비교하여

장/단점을 비교해보자

6. 연립일차 방정식 수치 해 구하는 방법 - 직접법

선형 대수와 관련된

선형 시스템, 연립일차 방정식

변수가 두개, 방정식이 두개인 경우 손으로 풀수 있으나

많아지면 손으로 풀수 없음.

연립일차방정식의 솔루션을 찾는 수치적 방법들을 소개

첫번째. direct method 직접법, 반복적 연산이 아니라 바로 해를 찾을수 있는 방법

-> 가우스 소거법

가우스 소거법을 할때 더 정확한 해를 구하기 위해 하는 pivot, inverse matrix를 구해서 하는 방법, factorization

연립 일차방정식에서 주어진 행렬 A를 어떻게 나누고 해를 찾을수 있겟는가 하는 방법들을 소개

특별한 행렬들은 쉽개 해를 찾을수 있는 방법이 없을까 찾아봄

7. 반복법

direct method에 알고리즘을 넣으면 바로 해가 나옴

-> 다른 반복해서 해를 찾는 방법을 소개

norm이라는 개념이 필요

iterative method 소개

행렬이 특별한 성질을 가진 행렬이라고한다면 좀더 iterative method가 없는지 함깨 소개

8.  근사 approximation

문제들이 주어졌을떄 얼마만큼 거기에 유사한 가까이에 해를 찾는가 하는 방법

연립일차방정식에 해가없다고 풀지 못하는게 아니라 근사한, 해와 유사한 역활을할수 있는 근사값을 찾는 방법 소개

9. 고유값, 고유벡터 구하는 문제

고유값과 고유벡터를 구하는데 결적적인 역활을 하는 분해 방법들이 있음.

대각화 diagonalization

수학적 이론상 중요한 역활을하는 jordan canonical form

수치적 방법으로 유명한 schur decomposition

decomposition 중에서 아주 인기가 높아지는 singular value decomposition

앞에서 예기한 고유값을 어떻게 수치적으로 찾을수 있겠는가

householder, QR method까지 소개함

10. 비선형 방정식의 해를 찾는 방법들

- 하나인 경우 bisection method나 newton's method썻으나 변수가 여러개, 방정시고도 여러개

- 이러한 것들을 시스템이라고 하면, 비선형 시스템에 대한 솔루션을 구하는 방법

-> newton's method, quasi-newton method

11. 미분방정식 문제중 경계치가 주어진 경우(boundary value problem)

- linear shooting method, nonlinear shooting method 등 장단점 비교

12. 편미분 방정식

- 해석 솔루션을 찾을수 없다면 어떻게 수치적인 방법으로 근사해를 찾을수 있을까

- 유명한게 finite difference method, finite element method

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

수학이란 무엇인가

1. 수치 해석을 하기 전에 선수 과목

선형 대수, 미적분, 미분방정식(공업 수학)

+ MATLAB 같은 코딩 언어

2. 수학 이란 무엇일까?

 우리는 평생 수학을 공부했지만 왜 공부한지 잘모름

산업 발전에서 중요한 역활, 과학의 언어

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

수치 해석이란 무엇인가

1. 사전적 정의

근사 approximation,

오차 error

근사값과 에러만 구하는 학문 ? 부족함.

수치적 방법을 이용한 수학적 한 분야 ? 이해하기엔 부족

Llyod Trefethen(옥스포드 대)

- 수치해석의 정의 : continuos mathmatics 연속적인 수학문제를 다루는 알고리즘을 개발해서 함께 공부하는 과목

2. 오차, 에러란?

x라는 참값이 존재

x*는 x에 대한 근사값. 여러개 존재가능

근사값을 하나를 선택 시 차 -> 절대적 오차 absolute error(참값과 선택된 근사값의 차)

절대 오차를 참값의 절댓값으로 나누는 경우 -> 상대적 오차 relative error

무슨 에러가 좋은가? 둘다 장단점을 가지고 있어서 사용됨

절대 오차의 장점

- 계산하기 쉬움, 얼마만큼 틀린지 정확히 눈에 보임

상대오차의 장점

- 상대적인 에러의 크기를 알 수 있음. 

100 - 1, 10 - 1 -> 두 경우다 절대 오차는 1이나 상대 오차는 1/100, 1/10이 됨 오차의 영향을 알 수 있음

3. 근사

참값을 알고 있으면 참값을 쓰면 되나, 

오차 계산은 실제 참값을 아는 문제를, 수치적 방법으로 근사값을 구하여 비교

참값을 모르는 문제가 있을때 어떻게 할까?

참값을 아는 문제로 개발한 방법으로

참값을 모르는 문제에 적용하여 해를 구하면 에러가 어느정도 안에 들어갈것이다 생각하고 문제 품.

=>참값을 모르더라도 수치적인 방법으로 근사값을 구해 사용

4. 수학적 모델

 참 값을 모르더라도 오차는 적은게 좋음

에러가 어디에서 발생하는가? 파악하면 오차를 줄일수 있지않을까? -> 수학적 모델 이용

5. 알고리즘

- 알고리즘을 구현하여 근사값을 구하려고함.

- 알고리즘 고안 시 중요한 것은 알고리즘이 stable 한지 unstable한지 확인해야힘.

- 인풋 데이터의 에러로 알고리즘이 수학적으로 안정적이고 참이나 unstable할 수 있음.

- 알고리즘을 버리기 보다는 조건을 주면 안정적이지 않을까 고민해야 함.

6. 반복법 iterative method

- 반복법을 이용하여 해를 찾을것임 -> 해로 수렴하는가 안하는가는 매우 중요함

- 수렴성 뿐만아니라 얼마나 빨리 수렴하느냐 rate of convergence도 매우 중요함

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

수치해석의 영역 - 수치해석은 어디에 있는가?

 중학교에서 처음 집합을 만남

집합들 사이 원소간의 관계 -> 대응 correspondence

의미 있는 대응들 =>함수 function

 대학교 1학년때 극한을 배움

- 연속인지 알야야 함 -> 미분 -> 도함수

 직선은 1차원. 차수가 낮음 but 우리가 사는 공간은 3차원, +시간을 한다면 4차원

=> 함수는 몇차원으로 주어짐

 우리가 모르는 미래를 방정식을 세워 예측해야함

- 자연 현상을 수학적으로 표현하면 미분이 들어감.

-> 미래를 예측하기 위해 미분 방정식이됨

=> 미분 방정식은 이 세상을 표현하는데 매우 유용함.

 수치해석은 미분 방정식을 해결함

- 미분 방정식을 어떻게 수치적으로 푸는것인가가 중요

 미분의 개념이 없다면 비선형 방정식 뿐일 것

함수들 중에 linear 선형성을 가진 함수를 고려해야함

- 행렬로 표현하여 연립 일차 방정식을 어떻게 풀까?

행렬로 고유값과 고유벡터는 어떻게 될까?

행렬을 어떻게 분해하여 활용할수 있을까?

함수를 이용해서 차원과 함꼐 설명하면 무엇을 하는지 설명이 가능해짐

ray casting 광선 투사

 컴퓨터 그래픽스와 계산 기하학의 다양한 문제를 해결하기 위해 광선과 표면의 교차 검사를 사용하는 기법으로

다양한 문제와 기술들과 관련이 있습니다.

- 광선에 처음 교차되는 물체를 가려내는 일반적인 문제

- 카메라 이미지의 각 픽셀을 향한 광선 교차 검사로 은닉면 제거

- 기본적인 광선들만 검사하는 재귀적 광선 추적 렌더링 알고리즘

https://ko.wikipedia.org/wiki/%EA%B4%91%EC%84%A0_%ED%88%AC%EC%82%AC

2.2 미로 문제

 미로에서 길을 찾는건 컴퓨터 과학에서 가장 흔히 다루는 탐색 문제라고 할수 있습니다. 여기서 사용할 지도는 2차원 그리드 셀로 되어있으며, 여기서 셀 cell이란 문자열로 빈 공간은 " ", 막힌 공간은 "X"로 표시하겠습니다. 이 외에도 시작점, 도착지, 경로등을 나타내기위해 아래와 같이 정의하겠습니다.

2.2.1 임의의 미로 생성하기

 이제 만들 Maze 클래스는 2차원 그리드로(리스트의 리스트)로 상태를 나타내려고 하는데, 이 상태들의 종류로는 행의 수, 열의 수, 시작 위치, 목적지, 긜고 임의로 막힌 공간들이 있겠습니다.

 미로는 시작지점과 도착지를 지정하면, 이에 대한 경로가 존재하도록 희박해져야 하는데, 일단 새 미로를 호출할때 희소 정도를 명시하도록하고, 기본값으로 20%정도 블록으로 설정하겠습니다. 

#file_name : maze.py
from enum import Enum
from typing import NamedTuple
import random

class Cell(str, Enum):
    EMPTY = " "
    BLOCKED = "X"
    START = "S"
    GOAL = "G"
    PATH = "*"


class MazeLocation(NamedTuple):
    row: int
    column: int


class Maze:
    def __init__(self, rows = 10, columns = 10, sparseness = 0.2, start = MazeLocation(0, 0), goal = MazeLocation(9, 9)):
        self._rows = rows
        self._columns = columns
        self.start = start
        self.goal = goal
        self._grid = [[Cell.EMPTY for c in range(columns)] for r in range(rows)]
        self._randomly_fill(rows, columns, sparseness)
        self._grid[start.row][start.column] = Cell.START
        self._grid[goal.row][goal.column] = Cell.GOAL

    def _randomly_fill(self, rows, columns, sparseness):
        for row in range(rows):
            for column in range(columns):
                # 균일 분포로 생성한 확률이 희소 임계치보다 작은 경우에만 블록
                if random.uniform(0, 1.0) < sparseness:
                    self._grid[row][column] = Cell.BLOCKED

    def __str__(self):
        output = ""
        for row in self._grid:
            output += "".join([c.value for c in row]) + "\n"
        return output

maze = Maze()
print(maze)

2.2 다른 세부사항들

 목적지를 탐색하는 함수를 구현하기 전에 우선 MazeLocation이 도착지에 도달했는지 확인할수 있어야 하는데 이 함수를 Maze 클래스에 추가해 줍시다.

    def goal_test(self, ml):
        return ml == self.goal

 그 다음으로 미로 상에 어느 위치가 주어지면 이 곳에서 수직이나 수평으로 움직일수 있는지 확인하여야 합니다. ㅎ함수 successors()로 해당 위치에서 가능한 다음 위치를 찾아볼수 있도록 구현하겠습니다. 이 함수는 단순하게 위, 아래, 오른쪽, 왼쪽이 빈 공간인지만 확인하는 것으로 지도의 가장자리는 확인을 해서는 안됩니다. 반환 값은 이동 가능한 모든 MazeLocation이 되겠습니다.

    def succesors(self, ml):
        locations = []
        # 오른쪽이 미로 범위 안이고, 막히지 않은 경우
        if ml.row + 1 < self._rows and self._grid[ml.row+1][ml.colum] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row + 1, ml.column))
        # 왼쪽이 미로 범위 안이고, 막히지 않은 경우
        if ml.row - 1 >= 0 and self._grid[ml.row - 1][ml.column] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row - 1, ml.column))
        # 위쪽이 미로 안이고 안 막힌 경우
        if ml.column + 1 < self._column and self._grid[ml.row][ml.column + 1] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row, ml.column + 1))
        # 아래가 미로 안이고 안막힌 경우
        if ml.column -1 >= 0 and self._grid[ml.row][ml.colum - 1] != Cell.BLOCKED:
            location.append(MazeLocation(ml.row, ml.column - 1))
        return locations

2. 탐색 문제
  탐색 search는 앞으로 볼 수많은 알고리즘에서 사용되는 용어로 이번에는 모든 프로그래머들이 알아야하는 핵심 탐색 알고리즘들을 살펴보겠습니다. 

2.1 DNA 탐색
 컴퓨터 소프트웨어에서 유전자 gene는 문자들의 시퀀스 A, C, G, T로 나타낼수 있는데요. 각각의 문자를 뉴클레오타이드라고 하며, 뉴클레오타이드가 3개가 모인 것을 코돈 codon이라고 부릅니다. 이것에 대한 내용은 아래의 그림 2.1에서 볼수있는데요. 코돈은  단백질 protein을 형성하는 다른 아미노산들과 함께 특정 아미노산을 부호화 하는데, 생물 정보학에서 일반적인 작업은 유전자에 있는 특정한 코돈을 찾는 것이 됩니다.

2.1.1 DNA 저장하기
 4가지 경우에 대한 뉴클레오타이드를 간단한 IntEnum으로 나타내보겠습니다.

from enum import IntEnum
from typing import Tuple, List

Nucleotide = IntEnum('Nucleotide', ('A', 'C', 'G', 'T'))

 여기서 뉴클레오 타이드는 그냥 Enum대신에 IntEnum이라는 타입으로, 이 타입은 비교 연산자도 사용할수 있게 해줍니다. IntEnum에서 이 연산들은 앞으로 구현할 탐색 알고리즘에서 필요한 것들입니다. 튜플과 리스트는 typing 패키지에서 가져와서 사용하면 되겠습니다.

# 타입 별칭 설정
Codon = Tuple[Nucleotide, Nucleotide, Nucleotide]
Gene = List[Codon]

 코돈은 3개의 뉴클레오타이드로 정의할수 있고, 유전자는 코돈들의 목록, 리스트로 정의되겠습니다.


* 주의사항
 나중에 코돈을 다른 코돈이랑 비교할건데,  파이썬에서 빌트인으로 비교할수 있게 되어있어 따로 이 클래스에서 비교 연산자를 구현할 필요는 없습니다.


 일반적으로 인터넷에서 유전자는 유전자들의 시퀀스에 있는 모든 뉴크레오타이드를 문자열로 나타낸것으로 파일 형식같은 것이 됩니다. 이제 가상의 유전자에 대한 문자열을 gene_str이라고 부릅시다.


이제 이 문자열 str을 유전자 gene으로 변환해봅시다.

gene_str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"

def str_to_gene(s):
    gene = []
    for i in range(0, len(s), 3):
        if (i + 2) >= len(s):
            return gene
        codon = (Nucleotide[s[i]], Nucleotide[s[i+1]], Nucleotide[s[i+2]])
        gene.append(codon)
    return gene

 string_to_gene()은 주어진 str을 이용해서 3개의 문자들을 코돈으로 만들고, 새 유전자의 끝에다가 추가시키는 역활을 수행합니다. 만약 더 이상 뉴클래오타이드 2개가 담겨질 곳이 없으면, 불안전한 유전자로서 끝에 도달한것이 됩니다. 이 경우에 마지막 하나나 2개 남은 뉴클레오 타이드를 무시하면 됩니다.

 string_to_gene()은  gene_str을 gene으로 변환하는데 사용될수 있겠습니다.

my_gene = str_to_gene(gene_str)

2.1.2 선형 탐색
 유전자에 사용할수있는 기본적인 연산 중 하나로 특정 코돈이 어디있는지에 대한 탐색이 될수 있습니다. 여기서 목표는 코돈이 이 유전자 내부에 존재하는것인지 안하는것인지 찾아내기만 하면 되겠는데요.

 선형 탐색은 탐색 공간에 존재하는 모든 요소에 대해서 해당 요소를 찾거나 그 데이터 구조의 끝에 도달할때까지 수행하게 됩니다. 그래서 선형 탐색은 가장 단순하고 명확한 방법이라고 할수 있겠습니다. 하지만 최악의 경우에 선형 탬식시에는 데이터 구조상에 존재하는 모든 요소들을 확인해야 할것이고, 이 구조에 요소의 갯수가 n개가 존재한다면 O(n) 복잡도를 가진다고 할 수 있겠습니다. 

 선형 탐색 함수는 쉽게 정의할수 있는데요. 그냥 데이터 구조상에 있는 모든 요소들을 돌려보고 찾으려고 하는 것과 같은지만 확인하면 되겠습니다. 아래의 코드는 유전자와 코돈이 주어질때, 해당 유전자 안에 입력한 코돈이 존재하는지 검사하게 됩니다.

def linear_contains(gene, key_codon):
    for codon in gene:
        if codon == key_codon:
            return True
        return False

acg = (Nucleotide.A, Nucleotide.C, Nucleotide.G)
gat = (Nucleotide.G, Nucleotide.A, Nucleotide.T)


"""
gene_str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"

ACG는 gene_str의 0~2에 존재
"""
print("\n-binary search-")
print(linear_contains(my_gene, acg)) # 참
print(linear_contains(my_gene, gat)) #거짓

2.1.3 이진 탐색
 모든 요소를 확인하는것 보다 더 빠른 방법들이 있지만 데이터 구조의 순서에 대해서 알아야 합니다. 만약 정렬된 데이터 구조가 있다면 어느 요소의 인덱스 번호로 해당 요소에 바로 접근할수 있을것이고, 이진 탐색을 할수 있겠습니다. 이런 기준에 따라서 정렬된 리스트는 이진 탐색의 완전한 예시라 할수 있습니다.

 이진 탐색은 정렬된 요소들의 중간 요소와 찾으려는 요소를 비교해서 수행하는데, 비교할 범위를 절반으로 줄이면서 반복 과정을 하게 됩니다. 간단한 예시를 살펴보겠습니다.

 다음과 같은 정렬된 알파벳의 리스트가 있다고 해봅시다.

 [“cat”, “dog”, “kangaroo”, “llama”, “rabbit”, “rat”, “zebra”]

그리고 여기서 “rat”이라는 단어를 찾아보겠습니다.


 1. 우선 7개의 글자에 있는 중간 원소인 “llama”를 찾을수 있습니다.

 2. “rat”은 알파벳 순서를 생각하면 “llama”뒤에 있으므로, “llama”의 뒷쪽에 리스트의 전체 목록 절반 중 어딘가에 있을겁니다. 

3. 이제 목록의 절반에 대해서 1, 2번 단계를 수행하면  “rat”이 어디있는것인지 찾을수 있겠으나 더 이상 탐색할 원소가 존재하지 않게 된다면 이 단어의 리스트에는 “rat”이 없다고 볼수 있겠습니다.

 이진 탐색은 탐색공간을 계속 절반씩 나누므로 최악의 경우에 실행시간이 O(log n)이 됩니다. 그 전에 잠시 생각해봐야할 점은 선형 탐색과는 달리 이진 탐색에서는 이미 정렬된 데이터 구조를 필요하므로, 최적의 정렬 알고리즘으로 정렬을 한 후에 이진 탐색을 수행한다면 O(n log n) 복잡도를 가지게 됩니다.

 만약 기존의 데이터가 정렬되어있지 않은데 탐색을 바로 수행한다고 하면, 선형 탐색처럼 똑같이 동작하게 될겁니다. 하지만 탐색을 여러 차례 수행해야한다고 하는 경우에, 정렬을 해놓은 후 각각에 대한 탐색을 수행하면 시간 비용을 크게 줄일수 있을 겁니다.

  유전자와 코돈을 이용한 이진 탐색 알고리즘에서는 다른 데이터 타입을 사용할 필요가 없는데, 코돈 codon 타입 자체가 유전자 타입의 한 원소와 비교할수 있기 때문입니다.

def binary_contains(gene, key_codon):
    low = 0
    high = len(gene) - 1
    while low <= high:
        mid = (low + high) // 2
        if gene[mid] < key_codon:
            low = mid + 1
        elif gene[mid] > key_codon:
            high = mid - 1
        else:
            return True
     return False

 찾으려는 원소가 중간 원소보다 크거나 작지 않다는 것은 그 원소를 찾은게 되겠습니다. 하지만 루프를 여러번 반복하더라도 False가 반환되었다면 못찾은게 되겠지만요.

 이 함수를 같은 유전자와 코돈으로 돌릴수는 있더라도, 돌리기전에 정렬부터 해야만 하겠습니다.

my_sorted_gene = sorted(my_gene)
print("\n-binary search-")
print(binary_contains(my_sorted_gene, acg))
print(binary_contains(my_sorted_gene, gat))

전체

#file_name : dna_search.py
from enum import IntEnum
from typing import Tuple, List

Nucleotide = IntEnum('Nucleotide', ('A', 'C', 'G', 'T'))

# 타입 별칭 설정
Codon = Tuple[Nucleotide, Nucleotide, Nucleotide]
Gene = List[Codon]

gene_str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"

def str_to_gene(s):
    gene = []
    for i in range(0, len(s), 3):
        if (i + 2) >= len(s):
            return gene
        codon = (Nucleotide[s[i]], Nucleotide[s[i+1]], Nucleotide[s[i+2]])
        gene.append(codon)
    return gene

my_gene = str_to_gene(gene_str)


def linear_contains(gene, key_codon):
    for codon in gene:
        if codon == key_codon:
            return True
        return False

acg = (Nucleotide.A, Nucleotide.C, Nucleotide.G)
gat = (Nucleotide.G, Nucleotide.A, Nucleotide.T)


"""
gene_str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"

ACG는 gene_str의 0~2에 존재
"""
print("\n-linear search-")
print(linear_contains(my_gene, acg)) # 참
print(linear_contains(my_gene, gat)) #거짓


def binary_contains(gene, key_codon):
    low = 0
    high = len(gene) - 1
    while low <= high:
        mid = (low + high) // 2
        if gene[mid] < key_codon:
            low = mid + 1
        elif gene[mid] > key_codon:
            high = mid - 1
        else:
            return True
    return False


my_sorted_gene = sorted(my_gene)
print("\n-binary search-")
print(binary_contains(my_sorted_gene, acg))
print(binary_contains(my_sorted_gene, gat))

실행 결과

파이썬 알고리즘 첫 번째로

다른 재귀적인 함수들을 사용하지 않는

간단한 문제 푸는 방법들을 살펴보겠습니다.

1.1 피보나치 수열 fiboncci sequence

 피보나치 수열은 첫쩨 둘째를 제외하고 그 이전의 두 수를 합한 수들의 열로

0, 1, 1, 2, 3, 5, ... 

와 같습니다.

피보나치 수열의 첫번째 값은 0이되고, 4번째 피보나치 수는 2가 됩니다.

n 번째 피보나치 수에 대한 공식으로 다음과 같이 정리할수 있습니다.

fib(n) = fib(n-1) + fib(n - 2)

1.1.1 첫번째 재귀

# file name : fib1.py

def fib1(n):
    return fib1(n - 1) + fib1(n-2)

if __name__ == "__main__":
    print(fib1(5))

이 경우 fib1은 한번 호출되면 끊임없이 무한하게 자기자신을 호출해서 무한 루프에 빠지게 됩니다.

1.1.2 베이스 케이스 base case 활용

여기서 무한 루프, 무한 재귀에 빠지는걸 막으려면 베이스 케이스를 지정해주면 되는데

베이스 케이스는 멈출 지점이 됩니다.

여기서 n이 0과 1인 경우는 자기 자신을 반환해주면 되므로

# file name : fib1.py

def fib2(n):
    if n < 2 : #base case
        return n
    return fib2(n - 1) + fib2(n - 2) #recursive case

if __name__ == "__main__":
    for i in range(10):
        print(fib2(i))

반복문으로 첫번째에서 10번째 피보나치 수들을 출력하면 아래와 같습니다.

* 주의사항

여기서 50번째 피보나치 수를 출력하지는 마세요

5번째 피보나치 수를 출력하기 위해서 fib2함수가 15번 호출되고

10번째 피보나치 수를 출력하는데는 fib함수가 177번 호출됩니다.

20번째의 경우 21,891번으로 점점 커지게 됩니다.

다음은 fib2 를 약간 수정하여 fib2 함수가 몇번 호출되는치 출력하도록 수정하였습니다.

# file name : fib2_cnt.py

call_cnt = 0

def fib2(n):
    global call_cnt
    call_cnt = call_cnt + 1
    if n < 2 : #base case
        return n
    return fib2(n - 1) + fib2(n - 2) #recursive case

if __name__ == "__main__":
    for i in range(11):
        call_cnt = 0
        print(" i - ",i, " : ", fib2(i), "  - call_cnt : ", call_cnt)

1.1.3 재귀 대신 기억하기

 기억은 계산작업이 끝날때 까지 계산 결과를 저장해놓는 것으로 재귀에서 이전의 결과를 구하기 위해 수많은 계산을 했던것 대신 필요한 값들을 저장해놓고 찾아서 사용하면 됩니다.

 이번에는 값을 기억하도록 딕셔너리를 써서 구현해보겠습니다.

#file_name : fib3.py

memo = {0:0 , 1:1} #base case

def fib3(n):
    if n not in memo:
        memo[n] = fib3(n - 1) + fib3(n - 2) # memorization
    return memo[n]

if __name__ == "__main__":
    print(fib3(5))
    print(fib3(10))
    print(fib3(50))

1.2 단순 압축

 공간 절약은 보통 중요합니다. 데이터가 더 작은 공간을 차지하도록 하는 기술이 압축 compression이고, 이 압축된 데이터를 원래대로 되돌리는것을 압축풀기 decompression이라 합니다.

 초기 데이터 압축에서는 데이터 저장소가 사용하는 비트 수을 따라왔는데요.

64비트 컴퓨터에서 unsigned integer는 65,535를 초과하는 수를 저장할수 없으며, 이는 매우 비효율적입니다.

하지만 16비트 unsigned integer에서는 남는 공간을 다 채울수 있어서

unsigned integer를 사용하는 경우 64비트 보다 16비트에서 75%정도 공간낭비를 줄일수 있습니다.

 이번에 sys.getsizeof() 함수로 객체가 얼마나 메모리 공간을 차지하고 있는지 확인해 볼것이고

DNA에서 유전자를 구성하는 뉴클레오 타이드를 가지고 살펴보겠습니다.

뉴클레오 타이드는 A, C, G, T 이 4가지 값 중 하나만 가질수 있는데요

"ATG" 라는 유니코드 문자열이 있는 경우

한 글자에 8비트로 총 24비트 공간을 차지하는 문자열이 됩니다.

하지만 뉴클레오 타이드의 경우에 수는 4가지 뿐이므로

8비트 대신 2비트로 다음과 같이 비트 문자열에다 저장하면 75%정도 더 절약할수 있겠습니다.

즉, 하나의 뉴클레오 타이드를 2비트로 나타낼수 있겠습니다.

이제 압축된 유전자 클래스를 만들어서

압축 함수와 압축 해제 함수 등을 구현해서

뉴클레오 타이드 문자열을 압축해보고, 압축해제를 해보겠습니다.

* 주의사항

_compress()는 언더스코어로 시작하는 함수인데

파이썬에서는 private 함수 같은 제한이 없어서

외부에서 호출하면 안되는 함수들은 앞에 언더스코어 _를 붙여주겠습니다.

from sys import getsizeof
# file_name : trivial_compression.py
class CompressedGene:

    def __init__(self, gene):
        self._compress(gene)

    def _compress(self, gene):
        self.bit_string = 1
        for nucleotide in gene.upper():
            #print(nucleotide)
            #print("bit_str : ", bin(self.bit_string))
            # 비트 문자열에 압축한 값을 넣기 전에 기존의 비트문자열을 2번 시프트
            self.bit_string <<= 2
            # 문자 A가 오면 00, C가 오면 01 등으로 비트문자열에 저장
            if nucleotide == "A":
                self.bit_string |= 0b00
            elif nucleotide == "C":
                self.bit_string |= 0b01
            elif nucleotide == "G":
                self.bit_string |= 0b10
            elif nucleotide == "T":
                self.bit_string |= 0b11
            else:
                raise ValueError("Invalid Nucleotide: {}".format(nucleotide))

    def decompress(self):
        gene = ""
        for i in range(0, self.bit_string.bit_length() - 1, 2):
            bits = self.bit_string >> i & 0b11
            if bits == 0b00:
                gene += "A"
            elif bits == 0b01:
                gene += "C"
            elif bits == 0b10:
                gene += "G"
            elif bits == 0b11:
                gene += "T"
            else:
                raise ValueError("Invalid bits:{}".format(bits))
        return gene[::-1] # 문자열을 역순으로 반환

    # CompressGene의 문자열 반환값
    def __str__(self):
        return self.decompress()

if __name__ == "__main__":
    original = "TAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATATAGGGATTAACCGTTATATATA" * 100
    compressed = CompressedGene(original)
    #print(compressed)
    print("original is {} bytes".format(getsizeof(original)))
    print("compressed is {} bytes".format(getsizeof(compressed.bit_string)))
    print("original and decompressed are the same : {}". format(original == compressed.decompress()))

압축전에 6549 바이트 던 문자열이

비트 문자열로 압축후에 1760바이트로 크게 줄었습니다.

압축 해제후 둘다 동일한 결과가 나온걸 확인했고

압축 해제후 결과를 보려면 주석문만 지워주시면 되겠습니다.

수치해석 numerical analysis

- 어떤 함수나 방정식의 해를 수치적으로 근사하여 해석하는 알고리즘

- 선형대수 이론의 수치 계산, 방정식의 수치해 계산, 미분방정식의 수치해 계산 등 이론의 계산 방법 다룸

범위

1. 비선형 방정식

2. 에러 해석 error analysis

3. 보간법 interpolation

4. 적분, 미분

5. 선형 대수

6. LU 인수분해 LU factorization

7. QR 인수분해 QR factoriation

9. 반복법 interative method

10. 양의 정부호행렬 positive definite

11. 상미분 방정식 ordinary difeerential equation

12. runge-kutta method

13. 상미분 방정식과 편미분 방정식 O.D.E and P.D.E

커널, 윈도우와 평활화 

- 사각이나 삼각, 정규분포 같은 커널로 컨볼루션하여 더부드럽게 하는 동작 평활화smoothening

다음의 밀도 함수가 주어질때

삼각 함수 커널을 적용한 결과

커널 예시

- 사각, 삼각, 정규분포 함수

- 각 영역의 합은 1, 표준 편차도 1