본문 바로가기

가젤의 컴퓨터과학

 (93)
온라인 이분 매칭 경쟁비 상한 (Upper Bound of Competitive Ratio for Online Bipartite Matching) 지난 시간에 우리는 온라인 분수 이분 매칭 문제(online fractional bipartite matching problem)를 \(1-1/e \approx 0.632\)의 경쟁비로 해결하는 결정론적 알고리즘(deterministic algorithm)인 물 채우기 알고리즘(water-filling algorithm)을 공부하였습니다. 온라인 분수 이분 매칭 (Online Fractional Bipartite Matching) 우리에게 처리해야 할 작업들이 있다고 해 보겠습니다. 다만 작업들은 처음부터 주어지지 않고 시간이 흐르면서 하나씩 도착합니다. 작업을 처리하기 위해 우리는 최대 하나의 작업을 할당받을 gazelle-and-cs.tistory.com 아래 본문의 정의와 기호는 이전 글의 것과 동..
온라인 분수 이분 매칭 (Online Fractional Bipartite Matching) 우리에게 처리해야 할 작업들이 있다고 해 보겠습니다. 다만 작업들은 처음부터 주어지지 않고 시간이 흐르면서 하나씩 도착합니다. 작업을 처리하기 위해 우리는 최대 하나의 작업을 할당받을 수 있는 기계를 몇 대 갖고 있습니다. 문제는 각 작업마다 해당 작업을 처리할 수 있는 기계가 따로 정해져 있다는 것이며, 심지어 어느 기계에서 처리될 수 있는지는 해당 작업이 도착해야 알 수 있다는 점입니다. 우리는 매번 작업이 도착할 때마다 이 작업을 어떤 기계에 할당할지, 그리고 만약 할당한다면, 어느 가용한 기계에 할당하여 줄지를 바로 결정하여야 합니다. 여기서 어려운 점은 이 결정을 후일 번복할 수 없다는 것입니다. 이런 환경에서 작업이 모두 도착했을 때 최대한 많은 작업을 처리하는 것이 목표입니다. 이는 유명한 ..
설비 입지 선정 원-쌍대 근사 알고리즘 (Primal-Dual Approximation Algorithm for Facility Location) 지난 포스트에서 우리는 설비 후보지들이 주어질 때 최소의 비용으로 몇 곳의 후보지에 설비를 지어 모든 고객을 서비스하는 방법을 찾는 설비 입지 선정 문제(facility location problem)를 공부하였습니다. 언뜻 보기에도 산업적으로 유용해 보이는 이 문제는 이론적으로도 흥미로운 부분이 많아서 널리 연구가 되었습니다. 지난 포스트에서는 그중에서도 특히 이 문제를 해결하는 4-근사 알고리즘을 배웠습니다. 설비 입지 선정 문제 (Facility Location Problem) 여러분이 큰 물류 회사를 경영한다고 가정해 봅시다. 여러분에게는 수많은 고객들이 있으며 여러분은 그들에게 상품을 배송해 주어야 합니다. 이를 위해서는 몇몇 장소에 큰 물류 창고를 건설 gazelle-and-cs.tistory..
서큘레이션 (Circulation) 최대 흐름 문제(maximum flow problem)는 어떤 방향 그래프(directed graph)와 간선 위의 용량(capacity)으로 정의되는 흐름 네트워크(flow network)에서 시점(source)부터 종점(sink)까지 최대한 많은 양의 물을 흘리는 방법을 찾는 문제입니다. 이 문제는 이론적으로는 물론 산업적으로도 깊이 연구된 매우 중요한 조합론적 최적화 문제입니다. 제 블로그에서도 현재까지 다섯 개의 글을 적었을 만큼 매우 비중 있게 다룬 주제입니다. 이번 포스트에서는 이 문제를 보다 확장을 시켜 보고자 합니다. 원래 문제에서는 각 간선에 이 이상은 흘릴 수 없다는 제약을 주는 용량만 있었습니다. 하지만 경우에 따라서는 각 간선마다 적어도 이 정도는 흐르고 있어야 한다는 일종의 필요량..
상관없는 기계에서 가중치 완성 시간 최소화하기 (Minimizing Weighted Completion Time on Unrelated Machines) 한 회사에서 어떤 작업들을 처리해야 한다고 합시다. 이 작업들을 처리하기 위해 기계 수 대를 갖고 있습니다. 각 기계들은 회사가 성장해 가면서 하나씩 사들이는 바람에 제원이나 사양이 모두 다릅니다. 다만, 모든 기계는 한 번에 하나의 작업만을 처리할 수 있으며, 한 작업이 시작되면 이를 중단하지 않고 끝까지 처리합니다. 회사 내에서 거의 유일하게 머리 좀 쓰는 공돌이인 여러분은 기계를 활용하여 작업들을 적절히 처리하라는 지시를 받았습니다. 지시 사항을 전달 받은 여러분은 상사에게 곧장 되물었습니다. 목표가 무엇인가요? 기계의 수행 시간을 최소화해야 하는지, 마감 기한을 어기는 정도를 최소화해야 하는지, 아니면 전기비 절감을 위해 기계가 사용하는 에너지를 최소화해야 하는지 등 작업 스케줄을 평가하는 요소는..
A* 알고리즘 (A* Search Algorithm) A* 알고리즘(A* search algorithm), 그동안 개념만 얼추 알고 있던 알고리즘이었습니다. A* 알고리즘은 인공지능 분야에 더 가깝기 때문입니다. 따라서 저도 학부 인공지능 수업 시간에 잠깐 들었던 게 다였죠. 그런데 이번 학기 조교 일을 하면서 어쩌다 보니 A* 알고리즘을 좀 심도 있게 공부해야 할 모종의 사건(?)이 생겼습니다. 처음에는 뭐 이런 것까지 공부해야 하나 싶었지만, 이것저것 찾아 보고 공부하다 보니 웬걸 이론적으로도 흥미로운 내용이 많이 있더군요. 이번 기회에 공부한 내용을 정리하는 겸하여 이 글을 적습니다. 다만 본문의 내용은 제가 이해한 내용을 바탕으로 제 방식대로 재해석하여 적은 것입니다. 따라서 원래 인공지능 분야에서 이해되는 방식과는 다를 수 있습니다. 이점 양지하시..
이산 푸리에 변환 (Discrete Fourier Transform) 글을 적는 현재 티스토리 에디터가 어색하게 느껴질 정도로 오랜만에 포스팅을 해 봅니다. 그동안 졸업 준비를 하느라 바빴습니다. 졸업 논문을 적고 심사 발표를 준비하는 일은 여간 힘든 일이 아니더군요. 다행히 예심은 잘 마쳤고, 본심까지 부족한 부분을 잘 보완할 일만 남았습니다. 그 사이 약간의 짬이 나서 글을 적습니다. 이번 포스팅의 주제는 이산 푸리에 변환(discrete Fourier transform, DFT)입니다. 약간 뜬금없게도 이 주제를 공부하게 된 계기는 쇼어의 알고리즘(Shor's algorithm) 때문입니다. 요새 학교에서 세미나 모임을 만들어 양자 컴퓨팅(qunatum computing)을 공부하고 있습니다. 여기서 여러 유명한 결과들을 살펴 보고 있는데, 그 중에서도 가장 유명한 ..
최적 경매 (Optimal Auction) 희대의 역작이 다시 또 경매에 올라왔습니다. 이번에도 여러 입찰자들이 작품을 쟁취하기 위하여 구름같이 모여들었군요. 열 길 물 속은 알아도 한 길 사람 속은 모른다고, 입찰자들은 약았습니다. 각자 본인이 생각하는 가치가 있지만, 본인의 이득을 위해서라면 거짓말도 서슴지 않을 속내입니다. 지난 시간에는 이런 상황 속에서 가치를 가장 높게 쳐주는 입찰자에게 작품을 판매하는 경매 방식인 비크리 경매(Vickrey auction)를 공부하였습니다. 비크리 경매 (Vickrey Auction) 희대의 역작이 경매로 올라왔고, 여러 입찰자들이 이 작품을 구매하기 위해 모여들었습니다. 작가는 자신의 가치를 실제로 가장 높게 쳐주는 사람에게 자신의 작품을 넘기기를 바라고 있습니다 gazelle-and-cs.tistor..
최적 페이지 교체 알고리즘 (Optimal Page Replacement Algorithm) 삼 년 전, 저는 유명한 온라인 최적화(online optimization) 문제 중 하나인 온라인 캐싱(online caching)을 소개하고, 이를 해결하는 유명한 방법인 LRU(least recently used) 알고리즘의 경쟁성을 증명하였습니다. [캐싱 / Caching] LRU는 얼마나 좋은 알고리즘일까? 세세한 부분을 많이 놓치기는 하겠지만, 간략히 말해 컴퓨터는 다음과 같이 동작합니다. 메모리에서 데이터를 프로세서로 가지고 와서 사칙 연산, 대소 비교 등과 같이 어떠한 작업을 수행한 다 gazelle-and-cs.tistory.com 글의 서론에서 저는 캐시 미스가 발생했을 때 캐시 메모리 상에서 가장 마지막에 사용되는 자료를 삭제하는 정책인 LFD(longest forward distan..
LRU보다 좋은 페이지 교체 알고리즘 (Randomized Marking Algorithm) 캐시 메모리(cache memory)는 프로세서와 주 메모리 사이에 위치한 용량은 작지만 속도는 빠른 저장 장치를 의미합니다. 이 장치의 용도는 어떤 프로세스가 동작할 때 많이 접근하는 자료를 저장해 두는 것이죠. 프로세스가 특정한 자료를 필요로 할 때 해당 자료가 최신의 상태로 캐시 메모리에 존재한다면, 주 메모리에 직접 접근하지 않고 캐시 메모리에 접근하여 자료를 가져옴으로써 상당한 시간적 이득을 꾀할 수 있습니다. 프로세스가 호출하는 자료의 단위를 페이지(page)라고 부르겠습니다. 만약 프로세스가 어떤 페이지를 필요로 하는데, 최신의 해당 페이지가 캐시 메모리에 존재하는 때를 캐시 히트(cache hit), 그렇지 않을 때를 캐시 미스(cache miss)라고 부릅니다. 전자의 경우에는 캐시 메모..

티스토리툴바