가젤의 컴퓨터과학 (93) 썸네일형 리스트형 근사 알고리즘 (Approximation Algorithm) 현대 사회는 컴퓨터와 떼어낼 수 없는 관계를 맺고 있습니다. 우리는 컴퓨터를 통해 문제를 해결하고, 다른 이들과 소통하며, 여가를 즐기기도 합니다. 그렇다면, 과연 컴퓨터는 모든 것을 해줄 수 있을까요? 아시는 분들은 아시겠지만, 컴퓨터가 모든 것을 해결해 줄 수는 없습니다. 가장 유명한 예시로는 halting problem이 있습니다. 이는 어떤 컴퓨터 프로그램과 그 프로그램의 한 입력이 주어졌을 때, 프로그램이 언젠간 끝이 나는지 아니면 영원히 동작할지를 판단하는 문제입니다. 저명한 수학자 Alan Turing은 이 문제가 컴퓨터로는, 좀 더 정확히는 Turing machine으로는, 해결할 수 없다는 것을 증명하였습니다. 이번에는 약간 결이 다른 이야기를 해보겠습니다. 여러분들이 유명 밴드의 매니저.. 쾨니그의 정리 (Kőnig's Theorem) 이 글은 홀의 정리 (Hall's Theorem)와 밀접한 연관이 있습니다. 필요한 경우에는 이를 참조하세요.2019/01/28 - [조합론적 최적화] - 홀의 정리 (Hall's Theorem) 무언가를 최적화시키는 문제를 보면 생각보다 많은 경우 다른 최적화 문제와 크게 관련이 있는 것을 볼 수 있습니다. 대표적인 예시가 바로 최대유량 최소컷 정리(maximum flow minimum cut theorem)입니다. 이 정리에 따르면, 어떤 flow network에서 유량(flow)을 최대화하는 문제는 곧 그 network의 최소 컷(cut)을 찾는 문제와 동일하다는 사실을 알 수 있습니다.. 이번에 함께 살펴 볼 문제들도 이와 비슷한 관계가 있습니다. 바로 matching과 vertex cover입니.. 홀의 정리 (Hall's Theorem) 여러분이 어떤 단체의 인사 담당자라고 하죠. 총 다섯 명의 직원이 새로이 자리를 배치 받아야 하는 상황입니다. 고맙게도 충원되어야 하는 자리도 총 다섯 개입니다. 자애로운 여러분은 모든 직원들이 만족하도록 자리를 배치하고 싶어서 직원들에게 자신이 배치 받아도 좋은 자리가 어딘지를 먼저 물어 보았습니다. 직원은 알파벳(A-E)으로, 자리는 숫자(1-5)로 표현했을 때, 여러분은 직원들이 원하는 자리를 다음과 같이 표현하였습니다.이제 여러분은 직원들에게 자리를 배치해야 합니다. 아마도 여러분은 다음 그림과 같이 손쉽게 네 명은 배치할 수 있을 것입니다. 실제로 배치된 것을 빨간 실선으로 표현하였습니다.하지만 직원 E를 배치하지 못한 상황입니다. 과연 여러분은 모든 직원에게 서로 다른 자리를 하나씩 배치할 수.. 이전 1 ··· 7 8 9 10 다음
