• >
  • 스타랩과제
  • >    컴퓨터이론 및 응용 연구실
컴퓨터이론 및 응용 연구실
NP-hard 그래프 문제를 위한 실용적인 알고리즘 프레임워크
서울대학교 / 총괄 책임자 : 박근수 / http://theory.snu.ac.kr
과제 소개
본 연구는 NP-hard 그래프 문제들을 대규모 그래프에서 풀 수 있는 세계 최고 성능의 알고리즘들을 개발하고, 이를 기반으로 NP-hard 그래프 문제들에 특화된 공개 SW 프레임워크를 개발한다. 주요 성능지표인 알고리즘 수행시간에 있어서 현존 최고 성능의 알고리즘 대비 개선율 100% 이상을 달성한다. 이를 통해 국제 산업계와 학계를 선도하는 기술을 확보하고, NP-hard 그래프 문제에 대한 연구 및 응용 SW 개발의 오픈 생태계를 구축한다.
인사말
컴퓨터이론은 컴퓨터공학의 기초학문으로서 효율적인 알고리즘 개발, NP-complete 개념, 현대 암호학 이론 등으로 컴퓨터공학 발전에 근본적인 기여를 하여 왔다. Turing Award를 받은 다수의 컴퓨터이론 학자들이 이러한 사실을 잘 보여주고 있다. 본 연구실은 컴퓨터이론 및 응용에 대해 연구하는 곳으로 구체적으로 스트링 알고리즘, 암호학, bioinformatics, 그래프 알고리즘, 금융공학 등에 대해 연구하고 있다.
연락처
전화 : 02-880-1828
메일주소 : kpark@theory.snu.ac.kr
찾아오는길
주소: 151-742 서울특별시 관악구 관악로 1 서울대학교 301동 414호, 452-1호
교통편
- 서울대입구역 3번출구-> 5511,5513 버스 -> 제2공학관
- 낙성대역 4번출구 -> 관악 02 버스 -> 제2공학관
총괄책임자
서울대학교 / 총괄책임자 : 박근수 / http://theory.snu.ac.kr
박근수 교수는 서울대학교 컴퓨터공학부에 재직 중 이며, 컴퓨터 이론 및 응용 연구실을 이끌고 있다. 주요 연구 분야는 컴퓨터 이론 및 알고리즘, 생물정보학, 암호학 등 이며, SW스타랩을 통해 subgraph isomorphism 같은 NP-hard 그래프 문제를 위한 실용적인 알고리즘을 개발하고 있다. 박근수 교수는 미국 Columbia 대학교에서 컴퓨터 이론으로 박사학위를 받았고, 영국 런던대학교 King’s College 조교수를 역임하였다. 또한, 호주 Curtin 대학교 방문연구원, 프랑스 Marne-la-Vallee 대학교 방문교수를 역임하였다. STOC, FOCS, SODA, SIAM Journal on Computing, Algorithmica 등 컴퓨터 이론 분야의 top-tier 학술대회 및 저널에 논문을 발표하였고, 금융감독원, 경찰청, 서울지검 등에 자문을 수행하였다.
구성원
성명 직위 연구담당분야 이메일
류철 석박사통합과정 오픈 생태계 구성 rcheol@theory.snu.ac.kr
김현준 석박사통합과정 알고리즘연구 hjkim@theory.snu.ac.kr
구건모 석박사통합과정 소프트웨어 및 툴 개발 gmgu@theory.snu.ac.kr
민승환 석박사통합과정 알고리즘 연구 shmin@theory.snu.ac.kr
Magsarjav Bataa 석박사통합과정 오픈 생태계 구성 magsarjav@theory.snu.ac.kr
이선호 석박사통합과정 알고리즘연구 shlee2@theory.snu.ac.kr
이정문 석사과정 소프트웨어 및 툴 개발 jmlee@theory.snu.ac.kr
안용주 석사과정 알고리즘연구 anyj0527@snu.ac.kr
송시우 석박사통합과정 소프트웨어 및 툴 개발 swsong@theory.snu.ac.kr
김현우 석박사통합과정 소프트웨어 및 툴 개발 hwkim@theory.snu.ac.kr
박성관 학사과정 오픈 생태계 구성 sgpark@theory.snu.ac.kr
연구목표
NP-hard 그래프 문제들을 대규모 그래프에서 풀 수 있는 세계 최고 성능의 알고리즘들을 개발하고, 이를 기반으로 NP-hard 그래프 문제들에 특화된 공개 SW 프레임워크를 개발한다. 주요 성능지표인 알고리즘 수행시간에 있어서 현존 최고 성능의 알고리즘 대비 개선율 100% 이상을 달성한다. 이를 통해 국제 산업계와 학계를 선도하는 기술을 확보하고, NP-hard 그래프 문제에 대한 연구 및 응용 SW 개발의 오픈 생태계를 구축한다.
연구내용
본 과제에서 개발하는 “NP-hard 그래프 문제를 위한 알고리즘 프레임워크”는 자료구조/툴, 그래프 알고리즘, 응용 SW의 세 층으로 구성된다.
(1) 대규모 그래프 처리를 위한 자료구조 및 그래프 생성/변환/분석 툴을 개발하고
(2) 중요 NP-hard 그래프 문제들(subgraph isomorphism, supergraph search, graph homomorphism, diversified top-k subgraph querying, graph similarity search)에 대하여 세계 최고 성능의 알고리즘을 개발하고
(3) 이를 기반으로 소셜 네트워크 분석 SW, protein-protein interaction 네트워크 분석 SW, RDF 쿼리 처리 SW, 화합물 검색 SW를 개발한다.
개발된 소스코드 및 라이브러리를 순차적으로 공개하여 NP-hard 그래프 문제를 위한 오픈 생태계를 형성한다.
공개 SW 현황
Algorithm Engineering for All-Pairs Suffix-Prefix Matching
All-pairs suffix-prefix matching은 DNA sequence assembly에서 가장 시간이 많이 소요되는 부분에 대한 문제이다. 이 연구에서는 all-pairs suffix-prefix matching을 기존에 존재하는 알고리즘들보다 현실적으로 빠르게 푸는 알고리즘을 개발하여 오픈소스로 공개하였다.
Improved Pattern-Scan-Order Algorithms for String Matching
이 연구에서는 패턴 스캔 순서를 이용하여 string matching 문제를 빠르게 풀 수 있는 알고리즘들을 개발하여 오픈소스로 공개하였다.
Fast Multiple Order-Preserving Matching Algorithms
텍스트 T와 패턴 P가 주어졌을 때 order-preserving problem은 T에 있는 substring 중에 P와 상대적 순서가 같은 것을 모두 찾는 문제이다. 이 연구에서는 패턴이 여러 개 주어지는 경우인 multiple order-preserving matching problem을 빠르게 푸는 알고리즘들을 개발하고 오픈소스로 공개하였다.
과제 연구 홍보 사이트