일기 (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.. simplex method와 cycling 극복법 Simplex method 는 유한한 시간 안에 끝날까? 수학식으로 증명하는 것 말고 수식은 최대한 줄이고 말로 풀어 직관적으로 설명해보려한다. 이 글은 기본적으로 simplex method가 무엇인지 알고 있어야 이해할 수 있다. Simplex method는 유한한 시간 안에 해를 구해내는 것을 보장할까? 결론부터 말하자면 그렇다. non-degeneracy 를 가정했을 때 non-degeneracy 를 가정하면 쉽다. Simple method는 항상 Basic feasible solution (BFS) 이 감소하는 방향으로만 움직이니 같은 basis 로 돌아올 수가 없다. 우리는 유한한 basis 를 가지고 있으니 유한한 시간 안에 알고리즘이 끝난다. degeneracy 가 있을 때- cycling .. [선형대수] 그림으로 알아보는 Basic feasible solution 사전 지식active 하다는 것? 만일 어떤 벡터가 제약식의 equality 를 만족하면 그 제약식은 active 혹은 binding 되었다고 한다. 직관적으로 크거나 같다/ 작거나 같다 등의 조건이 있을때 그 조건에 딱 걸쳐있는 벡터를 상상하면 쉽다. Basic solution 이란? 어떤 벡터가 basic solution 이 될 조건은? (차원이 n 이라고 하자)(1) active contraints 중 선형 독립이 n개 존재해야 함. (n은 차원의 수)(2) equality contrains 은 무조건 active 해야함.첫번째 조건은 직관적으로 이해가 된다. solution을 어떤 한 점이라고 생각한다면 2차원의 공간에서 한 점을 특정하기위해서는 2개의 선분이 필요할테고 3차원의 공간에서 한 점을.. 파리크라상 커피 월간 구독제 요즘 코로나때매 카페에서 공부는 못하고 테이크아웃을 해오느라 싸고 맛있는 커피 테이크아웃 전문점을 선호하게 되었다. 근데 집주변에 없어서 매번 엄청 걸어야했다. 그러던 중 집에서 가까운 파리크라상에 기가 막힌게 생겼다!커피 월간 혜택권!✨ 6만원을 내면 커피를 한달 내내 마실 수 있다. 모든 커피종류 이용 가능이라 내가 좋아하는 바닐라라떼 (5000원)로 맨날 먹는다 치면 최대 60% 할인이다 ॱଳ͘ 구독제 서비스가 이제 요식업종에도 도입된게 흥미롭다. 근데 아직 시행된지 얼마 안됐는지 좀 엉성한 부분들은 있다. 일단 이렇게 실물 쿠폰으로 발행한것도 좀 엉성하고 (잃어버리면 어쩔건데!) 타인에게 양도가 불가능하다고는 하는데 본인 확인 절차도 딱히 없다. 무엇보다 저기에 분명히 구매한 날부터 사용가능하다고.. [처음처럼 FLEX] 염따빠끄 다 모으려면 소주 몇병이나 마셔야할까? 처음처럼에서 스페셜 에디션을 냈다. 가장 큰 특징은 소주 뚜껑에 랜덤으로 '염' '따' '빠' '끄' 중 하나가 써있다는 것. 이것을 활용해서 모든 조합을 모으기 전까지는 술자리를 파할 수 없다는 염따빠끄 챌린지가 유행하고있다. 그럼 궁금해지는게 있다. 과연 평균적으로 몇명이나 마셔야 염따빠끄 조합을 모으고 집에 갈 수 있을까? 정답부터 말하자면 평균적으로는 8.3병 안에 염따빠끄를 모두 모을 수 있다. 바쁜 사람들은 8병이라는 숫자만 외워가고 계산 방법이 궁금한 사람들만 함께 계산을 해보자. 1. 우선 analytical approach 로 풀어보겠다. 이 문제를 풀려면 최소한 먹어야하는 소주의 개수인 4병을 시작으로 5병, 6병, 7병... 이렇게 일일이 확률을 계산해주어야한다. 아, 처음처럼이 각 .. 이전 1 2 3 다음
