d라이브러리: 미래세대의 과학지식 플랫폼

잡지 기사(12)

[지식]P일까, NP일까? 그래프 동형 문제
수학동아 | 2016년 01호
그래프 동형 문제가 P집합에 속하는지 여부는 밝혀지지 않았지만, 바바이 교수가 상수 C와 d를 사용한 2C (log n)d번 이내의 해결 알고리즘을 제시함으로써 P에 가까울 수 ...
[지식] 해밀턴 회로가 있을까? 가운데층 문제
수학동아 | 2016년 12호
가운데층 문제는 특정 그래프가 해밀턴 회로를 가지는지 여부를 보이는 것이며, 모든 n에 대해 해밀턴 회로의 존재를 증명한 토르슈텐 뮈체의 연구와 로바스의 추측에 대한...
[수학뉴스] 비행기 연착, 수학으로 해결한다!
수학동아 | 2019년 12호
비크란트 베이즈 미국 다트머스대학교 교수팀은 복잡한 승무원 일정 문제를 해결하기 위한 효율적인 방법을 제안했다. 이들은 항공사 버진아메리카의 항공편 정보를 분석해...
Part 2. 유전자 조각 맞추기 퍼즐
수학동아 | 2017년 08호
바이오인포매틱스는 생명현상을 분석하는 학문으로, 슈퍼컴퓨터를 이용해 DNA 염기서열의 유사성을 찾아내 조상을 추적합니다. 고대인과 현대인의 DNA를 비교하기 위해서는...
[엄상일 교수의 따끈따끈한 수학] 세계여행 가장 싸게 하는 이동 경로는? 외판원 문제
수학동아 | 2017년 11호
외판원 문제는 모든 도시를 한 번씩 방문하며 최소 비용의 이동경로를 찾는 NP-완전 문제로, 효율적인 해결 알고리즘의 존재 여부가 미지수다. 수학자들은 근사 알고리즘 ...
[알고리듬 시그널] 시각은 용납하지 않는다! 집합 덮개 문제
수학동아 | 2019년 04호
CCTV를 효율적으로 설치하기 위한 '집합 덮개 문제'는 주어진 전체집합의 부분집합을 최소로 사용하여 전체를 덮는 방법을 찾는 것이며, 원소가 많을 때는 근사알고리듬을 ...
[수학뉴스] 상금 10억 원 걸린 체스 문제 탄생!
수학동아 | 2017년 10호
세인트앤드루스대 이안 겐트 교수팀은 'N-퀸 완전 문제'가 NP-완전임을 발표했습니다. 퀸 N개를 n×n 체스판에 놓되 서로 공격하지 않게 배치하는 문제로, 일부 퀸이 자리 ...
Part 3. 세기의 난제 ‘짐 쌓기’
수학동아 | 2019년 02호
이사 때 짐을 효율적으로 싣는 '상자 채우기 문제'는 NP-완전 문제로 물건이 많아질수록 해법이 기하급수적으로 증가한다. 이를 해결하기 위해 최적의 근삿값을 찾는 알고...
양자컴퓨터 시대에 대비하는 수학!
수학동아 | 2019년 12호
수학자들은 양자컴퓨터의 초능력이 암호를 무력화 시킬 수 있다는 문제를 인식하고 처리하기 위한 대책을 세우고 있다. 현재 가장 흔하게 사용되는 'RSA 암호'는 양자컴퓨...
[알고리듬 시그널] 완벽한 답을 찾기 어려울 땐 근사 알고리듬
수학동아 | 2019년 02호
NP-완전 문제는 유한한 시간 안에 정확한 답을 찾기 어려운데, 실생활 적용을 위해 이에 아주 가까운 답을 주는 근사 알고리듬이 사용된다. 클러스터링은 많은 데이터를 비...