-
2-SAT 및 그의 응용
1. 2-SAT 문제란? 2-SAT 문제란 참/거짓의 값을 가지는 불리언 변수 $n$개 $x_1, x_2, \cdots, x_n$ 와 2-CNF가 있을 때, 2-CNF를 참으로 만들기 위해 $x_i$ 들에 적당한 값을 할당하는 문제이다. 2-CNF란 2개의 변수를 $\lor$ (or)한 식(절) 여러 개에 $\land$ 연산을 취해 만들어지는 식을 의미한다. 예를 들어, $(x_1 \lor x_2) \land (\bar x_3 \lor x_4)$ 는 2-CNF이다. 그리고, $x_1 = true$, $x_2 = false$, $x_3 = false$, $x_4 = false$ 는 이 식을 만족 시키는 하나의 방법이다....
-
람다 표현과 처치 인코딩(2)
이전 글에 이어서, 자연수와 그 연산들을 어떻게 함수로 인코딩하는지 알아보도록 하겠습니다. 자연수 인코딩(Church Numerals) 처치 인코딩에서는 다음과 같이 자연수를 정의합니다. \[0 = \lambda f. \lambda x. x\] \[1 = \lambda f. \lambda x. f \, x\] \[2 = \lambda f. \lambda x. f \, (f \, x)\] \[3 = \lambda f. \lambda x. f \, (f \, (f \, x))\] \[\vdots\] \[n = \lambda f. \lambda x. f^{n} \, x\] 간단히 말하자면, 처치 인코딩에서 자연수...
-
알고리즘 문제 접근 과정 2
알고리즘 문제 접근 과정 2 이번 포스트에서도 ‘알고리즘 문제 접근 방법’에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 나무 막대 - Taejon Asia Regional 2001 B번 관찰 우리는 문제를 이해할 때, 복잡하게 주어진 조건을 머리에 표상하기 쉬운 형태로 변경하는 것이 중요합니다. 주어진 조건에서, 한 번 기계를 작동할 때, 그 다음에 오는 막대의...
-
Wireless Digital Communication 3
서론 지난 글에서는 AWGN 채널의 특성에 대한 내용과, Probability of error 구하는 방법을, 혹시 정확한 계산이 어렵다면 그 상한을 계산하는 방법(Union Bound, Nearest Neighbor Union Bound)에 대해서 알아보았습니다. 이번 글에서는 현재 통신 시스템에서 사용하고 있는 constellation인 QAM과, 특정 주파수 사이의 신호만 통과시키는 passband system에 대해 알아보겠습니다. 아마 지금 passband system을 왜 설명하는지 헷갈릴 수 있지만, 나중에 작성할 글들을 이해하는 데에 있어 필수적인 내용이므로 꼭 이해하고 넘어가야 합니다. 본론 Quadrature Amplitude Modulation (QAM) 여태까지 저희가 알아본...
-
Expected Complexity of Random Convex Hulls
Table Of Contents Introduction Experimental Results Notations Planar Case On Higher Dimension Summary Introduction 안녕하세요, Aeren입니다! Convex hull은 computational geometry의 가장 기본이 되는 개념 중 하나입니다. 이번 글에서는 $\mathbb{R} ^ 2$의 compact (closed and bounded와 동치입니다.) and convex subset에서 uniformly random하게 선택된 점들의 집합의 convex hull의 vertex의 갯수의 기댓값을 알아볼 것입니다. 이 글은 다음 글을 바탕으로 작성되었습니다. Experimental Results 다음은 $C$가 unit disk, unit triangle, unit square일때 100회의 sampling으로 얻어낸 convex hull의 평균 vertex 갯수입니다....