-
Introduction to Distributed Graph Algorithms
Introduction to Distributed Graph Algorithms 많은 일반적인 알고리즘은 하나의 프로세서에서 작동함을 가정하지만, 현실의 계산에서는 컴퓨팅 기계가 하나의 프로세서가 아닌 여러 프로세서를 사용할 수도 있다. Parallel Algorithm의 경우는 효율성을 위해서 여러 개의 프로세서를 두고 동시에 중앙적으로 컨트롤하지만, 가끔은 여러 프로세서를 두는 것이 단순 효율성 때문이 아니라 실제적인 시공간적 제약에 의해서일 수도 있다. 예를 들어, 세계 각지에서 정보를 모으는 컴퓨터가 있고, 이 정보들을 한데 모아서 특정한 계산을 하고 싶은데, 정보들이 하나로 모으기에는 너무 크거나, 아니면 장거리 네트워크를...
-
Dulmage-Mendelsohn Decomposition (Part 2)
개요 이전에 작성한 글에서는 Dulmage-Mendelsohn Decomposition(DM 분해)의 개념과 성질을 소개하고 이를 구하는 방법에 대해서 다루었습니다. 이 글에서는 Dulmage-Mendelsohn Decomposition의 코드와 PS에서의 활용에 대해 다룹니다. 코드 이전 글에서 언급한 구현 방법을 그대로 사용할 것입니다. BipartiteMatching은 이분 그래프를 받아서 최대 매칭을 구한 뒤에 각 정점이 어느 정점과 매칭되었는지를 반환하는 함수입니다. Kuhn’s Algorithm으로 $O(VE)$에 구현했지만, 더 빠른 시간복잡도를 원한다면 Hopcroft-Karp Algorithm 등의 다른 구현체로 대체해서 사용해도 됩니다. StronglyConnectedComponents는 방향 그래프를 받아서 SCC들의 번호를 위상정렬 순으로 매기고, SCC의 개수와...
-
symmetry in variational quantum algorithm
서론 Keywords: VQC(Variational Quantum Circuit), VQA(Variational Quantum Algorithm), VQE(Variational Quantum Eigensolver), Observable, Hamiltonian 기본적인 양자상태의 표현과 gate가 어떻게 작동하는지는 이해하고 있다는 가정하에 글을 작성하였다. Variational quantum cirquit, variational quantum algorithm등에 대한 개념이 생소하다면 이전 글을 참고하길 바란다. 이번 글에서는 Variational Quantum Algorithm(VQA) 을 굉장히 효율적으로 사용할 수 있게 해주는 방법 중 하나를 다뤄보고자 한다. 바로 symmetry를 사용하는 것이다. 저번 글에서는 Parameterized Quantum Cirquit(PQC)와 Variational Quantum Algorithm(VQA)를 다루었다. 하지만 기존의 단순한 PQC기반 VQA는 한계가 존재한다. 이번...
-
러스트로 PS를 해보았습니다.
서론 러스트가 신흥 프로그래밍 언어(?)로 뜨고 있습니다. 안전하면서도 빠른 실행, 자체적으로 지원하는 rustfmt와 Clippy 등의 유용한 개발 도구, Cargo를 통한 손쉬운 라이브러리 관리 등의 장점으로 큰 인기를 끌고 있고, 구글, 페이스북 등 여러 대기업이 제품에 러스트를 사용하기 시작했습니다. 대학원 연구를 위해 러스트를 배운 적이 있는데, “러스트가 미래다”라는 막연한 생각에 올해 약 반 년 동안 러스트로 백준 온라인 저지에서 문제 풀이를 진행해 보았습니다. 그 과정에서 구현한 자료구조 및 알고리즘과 전체적인 소감을 정리합니다. 스포일러: 러스트는 좋은 언어입니다....
-
Faster Matroid Intersection - Part 2
이번 포스트에서는 전 글에서 subquadratic approximation algorithm의 결과를 얻었다고 소개했던 Faster Matroid Intersection(2019)에 대해 다룬다. Preliminaries 전 글과 동일하게, matroid $\mathcal{M_1} = (V, \mathcal{I_1}), \mathcal{M_2} = (V, \mathcal{I_2})$가 주어진 세팅이다. 이제 본격적으로 Matroid Intersection 알고리즘에 들어가기 전에 필요한 성질들에 대해 먼저 알아보자. Submodularity of rank. $A, B \subset V$에 대해, $rank(A \cup B) + rank(A \cap B) \le rank(A) + rank(B)$가 성립한다. Proof. $rank(A \cup B) - rank(A) \le rank(B) - rank(A \cap B)$를 보이면...