일기 (17) 썸네일형 리스트형 튜링머신에 대한 완벽한 이해 (1편) 요약과거에는 어떤것이 "computable" 한지 혹은 아닌지에 대한 수학적인 정의가 없었다. 엘런튜링 이 개발한 Turing machine 은 어떤것이 연산가능한지/아닌지를 판단할 수 있는 수학적 정의를 제공해주어 computability(계산 가능함) 에 대한 거대 담론의 시발점이 되었고, 또한 이는 현대의 컴퓨터의 전신이 되었다. Motivation"튜링 머신이 등장하게 된 배경은 무엇일까?"20세기 초반, 독일의 수학자 힐버르트는 정의와 공리를 입력하면 모든 수학적 명제를 도출해 줄 수 있는 만능 기계를 만들자는 제안을 한다. 쉽게 말해 우리가 알고있는 수학적 명제와 정의들을 때려 넣으면 자동으로 증명을 해주는 컴퓨터를, 즉 수학자를 대체할 인공지능을 개발하자는 것이다. 앨런 튜링은 힐버르트 프로.. decision problem 과 optimization problem 의 관계 (feat. np) optimization problem 에 대해 배우는 최적화 수업과 decision problem 의 다양한 구분들 (p, np)에 대해 배우는 알고리즘 수업을 동시에 듣다가 optimization 문제를 decision problem 으로 바꿀 수 있다는 사실을 알게되었다. 예를들어 traveling salesperson problem (TSP) 문제를 최적화 문제로 말한다면 우리는 모든 도시를 방문하는 최소 경로를 구하고 싶다고 할 수 있다. 이걸 decision problem 으로 바꾸면 어떨까? 참고로 decision problem 은 YES/NO로 답을 내릴 수 있는 문제를 의미한다. 모든 도시를 방문하면서 최대 k거리를 갖는 경로가 있을까? 로 바꿀 수 있다. 만약 decision proble.. Duality 변환 공식 암기하지말고 이해하기 Duality 변환 공식 선형계획법에서 Duality 에 대해 배우다보면 아래와 같은 dual 변환 공식을 종종 접한다. 다음과 같이 규칙 기반으로 표를 외우는 방법도 있다. 한쪽 문제의 equality constraints는 다른쪽 문제의 free variables 과 대응된다. minimize 문제의 constrainst 와 그의 dual 인 maximize 문제의 variables 의 부호는 같다. minimize 문제의 variables 과 그의 dual 인 maximize 문제의 contraints 부호는 다르다. 하지만 왜 꼭 이렇게 되어야만 하는것인지 규칙에 숨겨진 원리를 당위적으로 이해하고 싶은 사람이라면 아래 예제를 살펴보자. 다음 LP 예제를 살펴보자 minx1+3x2\min x_1+.. Lagrange Multiplier 로 유도해보는 dual 공식을 써보지 않고 Lagrange Multiplier Method 에 대한 선행 지식만 가지고 있다고 가정한 채 dual 을 유도해볼 것이다. 과정을 한번 따라 써보면 dual에 대해 다른 관점으로 이해할 수 있을 것이다. 아래는 LP minimization 문제의 standard form 이다. minc′x\min c'xminc′x s.t. Ax=bAx = bAx=b x≥0x \geq 0x≥0 이러한 LP 문제를 보면 가장 먼저 궁금해져야하는 것이 각 벡터와 행렬의 차원이다. c, x 는 n 차원의 벡터이며 A는 m x n 행렬, b는 m 차원의 벡터이다. c와 x 벡터를 내적해주기 위해 그냥 c 벡터가 아니라 c′c'c′를 사용한다. 참고로 c′c'c′는 c벡터를 transpose 한 cTc^Tc.. 이전 1 2 3 4 5 다음
