-
Lie groups and Lie algebras in a nutshell
0. Introduction 리 군(Lie groups)은 현대 물리, 수학, 공학 등에서 널리 쓰이고 있습니다. 수학을 전공하지 않는 경우 연속적인 대칭군 정도로 생각하는 경우가 많습니다. 수학적으로 엄밀하게 리 군에 대해서 배우기에는 요구하는 선수지식이 너무나 많고, 물리 또는 공학에서는 필요한 토픽들 위주로 공부를 하게 되면서 리 군과 리 대수가 어떻게 정의되는지 모르는 상태로 넘어가는 경우가 많은 것 같습니다. 본 글에서는 리 군과 리 대수를 수학적으로 엄밀하면서도 전공자가 아니더라도 최대한 이해할 수 있는 수준으로 서술하려고 합니다. 미적분학과 선형대수 지식을...
-
Graph Measure와 Tree-decomposition (1): Tree-independence Number
0. Preliminaries Treewidth를 이용한 알고리즘에 대해 다루는 국문 블로그 글이 상당수 있어 많은 독자들이 익숙할 것으로 보이나, treewidth에 익숙하지 않은 독자들이 있을 수 있으니, treewidth에 대해 먼저 소개하고자 한다. Graph 상의 다양한 NP-hard 문제들 가운데 상당수는 트리 혹은 트리와 유사한, 특수한 종류의 그래프에서 쉽게 다항시간에 해결할 수 있는 경우가 많다. 이에, 그래프가 얼마나 tree에 가까운지에 대한 척도를 생각해볼 수 있다. 그래프 $G$에 대해 $G$의 tree-decomposition은 다음 두 조건을 만족하는 트리 $T$와 $\beta : V(G) \to...
-
A game of cops and robbers on planar graph
A game of cops and robbers on planar graph “Cops and Robbers” 게임은 그래프 $G$ 상에서 정의되는 추격-회피 문제의 한 유형이다. 이 게임은 두 명의 플레이어, ‘Cop’ (C)와 ‘Robber’ (R)가 참여한다. 게임의 규칙은 다음과 같다. 먼저 Cop이, 그 다음 Robber가 그래프 상의 정점을 선택하여 위치한다. 이후 두 플레이어는 교대로 인접한 정점으로 이동한다. Cop이 Robber와 동일한 정점을 차지하게 되면 Cop의 승리로, Robber가 이러한 상황을 무한히 회피할 수 있다면 Robber의 승리로 규정된다. 본 논의는 Robber가 현재 위치에...
-
Advanced Game Search Algorithms (1)
1. Introduction 이번 글에서는 게임 에이전트의 가장 단순한 형태인 Random Agent부터 시작하여 Greedy, Minimax, Alpha-Beta Pruning의 핵심 원리를 다룹니다. 또한 에이전트의 성능을 객관적으로 평가하기 위해 SPRT(Sequential Probability Ratio Test)라는 평가 기법을 소개합니다. 이를 이용하면 통계적으로 두 에이전트 간의 실력 차이를 엄밀하게 검증할 수 있습니다. 이후 이어지는 글에서는 Minimax Algorithm의 추가적인 Search Pruning 기법을 알아보고, MCTS 등의 현대적인 탐색 기법과 NNUE와 같은 neural network를 이용한 평가 방법을 살펴보겠습니다. 이번 글에서 소개하는 방법론은 $2$인, 제로섬, 턴제, 완전정보,...
-
Ladder Decomposition
개요 트리의 Ladder Decomposition은 Heavy-Light Decomposition과 유사하게, 트리를 경로들의 집합으로 분해하는 기법이다. 이번 글에서는 Ladder Decomposition의 정의와 알고리즘, 그리고 이를 응용해서 풀 수 있는 문제에 대해 알아보고자 한다. 정의 Ladder Decomposition를 한 문장으로 줄여 말하면 ‘HLD인데, subtree의 크기가 아니라 높이를 대신 본 것’ 이다. 구체적으로, Ladder Decomposition은 다음과 같은 알고리즘으로 구할 수 있다. 먼저 $h(u)$ 를 정점 $u$를 루트로 하는 서브트리의 높이라 정의하자. 루트부터 DFS를 실행하면서 정점 $v$에 도달 했을 때, $v$의 자식들이 $c_1$, $c_2$,...