구사과

많은 일반적인 알고리즘은 하나의 프로세서에서 작동함을 가정하지만, 현실의 계산에서는 컴퓨팅 기계가 하나의 프로세서가 아닌 여러 프로세서를 사용할 수도 있다. Parallel Algorithm의 경우는 효율성을 위해서 여러 개의 프로세서를 두고 동시에 중앙적으로 컨트롤하지만, 가끔은 여러 프로세서를 두는 것이 단순 효율성 때문이 아니라 실제적인 시공간적 제약에 의해서일 수도 있다. 예를 들어, 세계 각지에서 정보를 모으는 컴퓨터가 있고, 이 정보들을 한데 모아서 특정한 계산을 하고 싶은데, 정보들이 하나로 모으기에는 너무 크거나, 아니면 장거리 네트워크를 사용하는 것이 아주 비효율적인 상황들이 있을 것이다. Distributed Algorithm이란 어떠한 알고리즘이 하나의 프로세서가 아니라 여러 분할된 ..

(2023/05/19 최근 과제들을 추가했습니다.) (2020/06/13 6월 과제가 완성되어서 공개했습니다.) (2020/04/18 초판 작성.) 이미 아시는 분들도 계시겠지만, 2017년 가을 이후 포스팅되는 대부분의 글은 삼성전자 SW멤버십의 지원을 받아 작성되고 있습니다. 매달 컴퓨터 과학에 관한 글을 주기적으로 SW멤버십에 제공하고, 이에 따른 지원금을 받는 식입니다. 비정기적으로 관리하던 블로그에 매달 주기적으로 글이 올라올 수 있게 된 것은 SW멤버십의 지원 덕분이 큽니다. 감사합니다. SW멤버십에 제공하는 대다수의 글은 제 블로그에 같이 올립니다. 일반적으로 제출 기한이 있는 SW멤버십에 글을 먼저 제출한 후, 데드라인 안에 손보지 못한 부분이 있으면 이 부분을 보강해서 블로그에 올리는 식..

1. Separating Hyperplane Theorem 2차원 평면에 겹치지 않는 두 원이 있을 때, 두 원을 분리하는 직선을 찾을 수 있을까? 다시 말해, 직선의 한 쪽에 첫 번째 원이, 직선의 다른 쪽에 두 번째 원이 존재하게 직선을 그을 수 있을까? 어렵지 않게, 두 원의 공통 접선을 적절히 그어서 나누면 될 것이다. 같은 원리로, 겹치지 않는 두 볼록 다각형이 있을 때 둘을 분리하는 직선 역시 찾을 수 있다. 조금 더 복잡하지만, 3차원 공간에서도 겹치지 않는 두 볼록 다면체를 분리하는 평면이 존재할 것 같다. 즉, 평면의 한 쪽에 볼록 다면체 하나가, 다른 한 쪽에 볼록 다면체 하나가 있는 것이다. 이를 $n$ 차원으로 일반화하면 다음과 같다. 두 개의 Disjoint한 ($A \cap B ..