-
Diversified Late Acceptance Search
서론 지역 검색(Local Search) 알고리즘은, 여러 종류의 최적화 문제를 광범위하게 해결하는 데에 사용하고, 다양한 알고리즘의 기준선(baseline)이 될 수 있습니다. 우리는 이 알고리즘 중 기초적인 언덕 오르기(Hill Climbing) 알고리즘과, 그 변형인 늦게 수용하는 언덕오르기(Late Acceptance Hill Climbing, LAHC) 알고리즘 중 하나인 다양성을 갖춘 늦게 수용하는 탐색(Diversified Late Acceptance Search, DLAS)에 대해 알아봅니다. 언덕 오르기 알고리즘과 변형 언덕 오르기 알고리즘은 최적화 문제를 해결하기 위한 간단하고 직관적인 알고리즘 중 하나입니다. 이 알고리즘은 현재 상태에서 지역 최적해를 찾는 데...
-
A Bayesian Perspective on Federated Learning (1)
Introduction Federated Learning은 최근에 머신러닝과 인공지능 연구에서 매우 중요한 분야로 떠오르고 있습니다. 이 기술은 분산된 디바이스들의 데이터를 이용하여 중앙 집중식으로 데이터를 수집하지 않고 모델을 학습시키는 것으로, 개인정보 보호와 같은 문제를 해결하는 데 도움이 됩니다. 따라서, Federated Learning은 데이터 프라이버시와 보안 문제가 중요한 분야에서 매우 유용합니다. 이 기술은 인공지능 모델을 개발하는 데 있어서 중요한 문제 중 하나인 데이터 분산 문제를 해결할 수 있습니다. 이러한 이유로, Federated Learning은 최근 많은 관심을 받고 있으며, 새로운 연구와 개발이 계속해서...
-
Variation of Mo's Algorithm 1
안녕하세요 jthis 입니다. 이 글에서는 Mo’s Algorithm의 variation에 대해 소개하겠습니다. Mo’s Algorithm Mo’s Algorithm은 구간 쿼리를 offline으로 해결하는 알고리즘입니다. Mo’s Algorithm에 대한 자세한 설명은 Mo’s Algoithm에서, Mo’s Algorithm을 사용한 트리의 서브 트리에 대한 쿼리나 경로에 대한 쿼리는 Mo’s on Tree 에서 찾아보실 수 있으니 읽고 오시면 도움이 될 것입니다. Mo’s Algorithm with Rollback Mo’s Algorithm을 사용할 때 원소를 제거만 하거나 삽입만 하고 싶다는 생각을 해보신 적 있으실 겁니다. 간략하게 설명하자면 원소를 삽입하는 연산만 하고 싶을...
-
다양한 언어에서의 async/await
동시성과 병렬성, 멀티쓰레드와 멀티프로세스 무어의 법칙이란 반도체 성능이 24개월마다 2배씩 증가하게 된다는 법칙입니다. 이 법칙은 최근까지 잘 맞아떨어지지만 이제는 한계에 가까워졌다고 합니다. 그래서 최근에는 CPU의 코어 수를 늘리는 추세입니다. 즉, 프로그래머는 CPU의 많은 코어를 모두 활용해야 프로그램이 돌아가는데 많은 이점을 볼 수 있습니다. 그래서 최근에 많은 프로그래밍 언어에서 동시성과 병렬 프로그래밍을 지원하고 있습니다. 병렬 프로그래밍에는 다양한 방법이 있는데, 그 중 오늘은 Async IO, 비동기적 IO에 대해 설명하겠습니다. Async IO란? Async IO의 정의 그럼 Async IO란...
-
Dilworth's Theorem
Introduction 딜워스의 정리(Dilworth’s Theorem)는 부분 순서 집합(partially ordered set)에서 최대 반사슬(antichain)의 크기는 사슬 분할의 최소 개수와 같다는 정리입니다. 먼저 용어들을 설명하겠습니다. 부분 순서 집합이란 말 그대로 순서가 부분적으로 정의된 집합입니다. 예를 들어 자연수 집합 $S$에서 $x$가 $y$로 나누어 떨어질 때 $x\geq y$로 정의하는 경우 $S$를 부분 순서 집합이라고 생각할 수 있습니다. 여기서 6과 3은 비교 가능하지만 6과 5는 비교 불가능합니다. 다른 예시는 2차원 좌표를 원소로 하는 집합에서 $x_1\leq x_2,y_1\leq y_2$이면 $(x_1,y_1)\leq(x_2,y_2)$로 정의하는 것입니다. 여기서는 (1,5)와...