알고리즘/online algorithm (5) 썸네일형 리스트형 Online 알고리즘 (5) - Randomized Online Algorithms (MBG 문제) 이번 포스팅에서는 Modified Bit Guessing Problem (이하 MBG 문제) 에 대하여 randomness가 deterministic 알고리즘에 어떤 영향을 끼치는지 알아보도록 하겠습니다. MBG 문제는 다음과 같이 정의할 수 있습니다. 2명의 사람이 게임을 한다고 합시다. 한 사람이 n개의 비트의 나열 패턴을 정합니다. 그리고 다른 한 사람은 그 비트를 하나씩 들으면서 다음에 어떤 비트가 올 지 맞추는 게임입니다. 즉, 다음 비트가 0일지 1일지 과거 비트의 패턴을 보고 맞춰야 합니다. 목표는 하나라도 맞추는 것입니다. 맞춘다면 점수를 $g(n)/(1-1/2^{n-1})$를 얻고 모두 틀린다면 1 만큼 점수를 얻습니다. 우선 직관적으로 이 게임에 대해서 해석해봅시다. 만약 비트의 나열 .. Online 알고리즘 (4) - Randomized Online Algorithms (1) 이번 포스팅에서는 온라인 알고리즘을 푸는데 있어서 randomness가 어떻게 영향을 끼치는지 정리해보도록 하겠습니다. 우선 randomized 온라인 알고리즘을 정리하려면 기존 deterministic 온라인 알고리즘에서 다음과 같은 몇가지 확장이 필요합니다. competitive ratio type of adversaries and relationship Randomized 온라인 알고리즘에서는 competitve ratio를 측정하는 것은 Randomness가 3가지의 adversaries를 허용하기 때문에 deterministc 온라인 알고리즘과 상이합니다. Randomness 온라인 알고리즘에서 adversary는 3가지 유형으로 oblivious(망각형), adaptive online (적응형.. Online 알고리즘 (3) - Deterministic Online Algorithms (2) Maximization Problem: Time Series Search 이번 포스팅에서는 전 포스팅의 Minimization과 대비되는 형태의 문제인 Maximization 문제를 다루도록 하겠습니다. Time Series Search (이하 TSS)문제는 대표적인 maximization 문제입니다. 한 항공사에서 유럽여행 이벤트를 한다고 가정하겠습니다. 이럴 경우는 없겠지만 이 이벤트는 여러분을 n일 후에 유럽으로 공짜로 보내주는 이벤트입니다. 다만 여러분은 n일이 언제인지 모르고 당일날 통보를 받게 됩니다. 이 여행을 가기 위해서 많은 준비를 해야하겠지만 가장 중요한 건 원화를 유로로 바꿔야합니다. 목표는 환율이 여러가지 요인으로 변동하는 상황에서 가장 이득이 되는 날을 골라서 모든 돈을 바꾸는 것.. Online 알고리즘 (2) - Deterministic Online Algorithms (1) 지난번 온라인 알고리즘의 포스팅에서 간략하게 온라인 알고리즘을 설명했다면, 이번 포스팅에서는 Minimization 문제인 maskespan problem의 솔루션 중의 하나인 Graham’s greedy makespan algorithm를 분석해보도록 하겠습니다. 우선 들어가기에 앞서 determinisic online 알고리즘 문제를 정의하는 하나의 템플릿을 소개하겠습니다. request-answer game은 determinisic online 알고리즘을 정형화하는 일종의 템플릿입니다. 정의는 간단합니다. 온라인 알고리즘은 연속된 요청(request)를 σ = σ(1), . . . , σ(m) 받습니다. 이 요청들은 순서가 있으며, σ(t)의 요청을 받았을 때, σ(t ′ ) ,t ′ > t를 알지.. Online 알고리즘 (1) - Online Algorithm 하루 24시간 1년 365일 요청을 받아 프로세스들을 진행하고 있는 서버가 존재합니다. 서버는 지속적으로 프로세스를 실행시키기 위한 시간, 컴퓨팅 자원등 프로세스에 대한 정보를 요청으로 받아 서버내의 자원을 분배하여 프로세스를 실행시켜야 합니다. 이 때, 우리는 어떠한 전략, 알고리즘을 이용하여 자원을 분배해야 할까요? Online 알고리즘은 위와 같은 문제를 효과적으로 풀기 위한 알고리즘입니다. Online 알고리즘에서의 Online의 의미는 '입력을 순차적으로 받으면서 진행하며 돌이킬 수 없는 결정을 하는 것' 을 나타내며, 우리가 흔히 알고있는 인터넷 온라인과는 이론적으로 아무 관련이 없습니다. Online의 반대말은 Offline이며 의미는 '모든 입력을 시작부터 끝까지 알고 있는 상태로 결정을 .. 이전 1 다음
