-
Choice Coordination Problem
개요 문제 상황 $n$개의 프로세서가 존재한다. 각 프로세서는 $m$개의 선택지 중 하나를 선택해야 한다. 그런데, 프로세서들이 완전히 비동기적으로 작동한다. 프로세서가 공유하는 일관적인 시계 (global clock)이 존재하지도 않을 뿐더러, 프로세서의 응답 속도에 대한 가정을 할 수도 없다. 이러한 상황에서 모든 프로세서가 동일한 선택으로 합의하도록 하는 알고리즘이 필요하다. 인격을 부여해 이러한 비유 상황을 만들어낼 수 있다: $n$명의 관광객이 존재한다. 그들이 머무는 여행지는 $m$개의 방으로 이루어져 있다. 이 때 관광객 모두가 방 하나에 모일 수 있도록 행동 규약을...
-
완전 매칭을 찾는 병렬 알고리즘
PRAM Model PRAM (Parallel Random Access Machine) 모델은 병렬 처리를 이론적으로 표현한 모델이다. $P$개의 프로세서와 크기 $M$의 공통 메모리로 이루어져 있다. PRAM 모델에서 한 번의 (병렬) 연산은 다음과 같은 과정을 통해 이루어진다: 공통 메모리의 어떤 위치에 있는 값을 읽는다. 간단한 (unit-step) 연산을 실행한다. 공통 메모리의 어떤 위치에 값을 쓴다. 여러 개의 프로세서가 동시에 연산을 수행할 때 총돌할 가능성을 배제하기 위해, 다음과 같은 가정을 한다. 먼저, 모든 프로세서가 값 읽기 (1.)를 끝낸 다음에 연산 실행과 값...
-
Randomized Algorithm의 시간 복잡도 분석
Introduction 우리가 PS에 대해 배우면서 학습하는 대부분의 알고리즘은, 확률에 의존하지 않는다. 해당 알고리즘의 로직을 올바르게 구현했을 때에는 항상 정해진 시간 복잡도로 정답을 낸다. 현대 연구되는 많은 알고리즘은 그렇지 않다. 알고리즘은 확률적으로 오답을 낼 수도 있고, 정답과 적절히 가까운 근삿값만을 계산할 수도 있다. 또는 알고리즘의 수행 시간이 확률적으로 들쑥날쑥할 수 있다. 이러한 알고리즘의 가장 간단한 예시로는 피벗을 무작위로 잡는 퀵 소트 알고리즘이 있다. 무작위 알고리즘 (Randomized algorithm) 가운데, 항상 정답을 내는 것이 보장된 알고리즘을 Las Vegas...
-
The Short-Side Advantage in Random Matching Markets
이 글은 L. Cai와 C. Thomas의 논문 The Short-Side Advantage in Random Matching Markets 의 결과를 간략하게 정리한 것이다. 1. Introduction Stable Matching Problem은 남-여 간의 짝 매칭, 의사와 병원간의 매칭, 학생과 지도교수 간의 매칭 등 여러 상황에서 응용될 수 있는 문제로 다음과 같은 상황을 다룬다. $n$ 명의 의사 $\mathcal{D} = {d_1, d_2, \cdots, d_n}$ 와 $m$ 개의 병원 $\mathcal{H} = {h_1, h_2, \cdots, h_m}$ 이 있다. 각각의 의사는 병원에 대한 선호하는 순서($\prec_d$)가 존재하고, 각각의...
-
랜덤 올바르게 사용하기
서론 프로그램을 작성할 때 랜덤한 요소는 많이 들어갑니다. 어떤 공간을 탐색할 때 무작위로 탐색을 하기도 하고, 프로그램의 비밀 키를 만들거나 게임을 만들 때 카드 덱을 섞을 때 등, 랜덤이 프로그램에 사용되는 곳은 굉장히 많습니다. 하지만 이 랜덤은 자주 잘못 사용되고는 합니다. 랜덤을 올바르게 사용하는 방법에 대해 알아보려고 합니다. 랜덤이란? 랜덤이란 특정한 패턴이 없다는 것을 말합니다. 즉, 어떤 규칙에 의해 생성되지 않고 다른 변수와 독립적으로 만들어진 결과를 랜덤한 결과라고 합니다. 과연 완벽한 좋은 랜덤을 만들 수...