정지 문제란 무엇인가?처음 프로그래밍을 할 때, 누구나 한 번쯤은 프로그램을 작성한 후 예상치 않게 컴퓨터가 멈추거나, 프로그램이 끝없이 실행되는 상황을 경험했을 것입니다. 여러분이 고심 끝에 작성한 코드가 실행되길 기대했는데, 프로그램이 멈추지 않고 계속해서 실행된다면 어떤 기분이 들까요? 심지어 이 프로그램이 여러분의 컴퓨터 자원을 모두 소모해 다른 작업도 방해한다면 단순히 불편함을 넘어서, 시스템 성능에 큰 문제를 일으킬 수 있습니다. 그러므로 프로그램을 작성할 때, 프로그램이 주어진 입력값에 대해 반드시 종료 될지(정지 문제), 혹은 계속해서 실행 될지(무한 실행 문제)를 미리 판별하는 것이 매우 중요합니다. 프로그램의 정지 여부를 미리 판단할 수 있다면, 예상치 못한 오류를 줄이고, 시스템의 안..
여러분은 파티를 준비하고 있고, 초대할 손님 명단을 작성 중입니다. 파티가 즐겁게 진행되려면 몇 명을 초대해야 할까요? 여기서 핵심은 초대된 사람들 사이의 관계입니다. 모든 손님이 서로 잘 아는 사이라면 이야깃거리가 금방 고갈될 수 있습니다. 반대로, 모든 손님이 서로 모르는 사이라면 어색한 분위기가 형성될 수도 있죠. 따라서, 손님들 사이의 관계가 적당히 섞여 있는 것이 중요합니다. 그렇다면, 이 균형을 유지하면서도 파티가 흥미롭게 진행되려면 어떻게 해야할까요? 이런 질문을 던져봅시다. 적어도 3명이 서로 알거나, 3명이 서로 모르는 그룹이 생기도록 하려면 최소 몇 명의 손님을 초대해야 할까요? 파티 플래너 문제와 그래프앞서 본 문제를 파티 플래너 문제라고 부릅니다. 이 문제를 이해하기 위해서는 그래프..
임의의 자연수를 하나 가져옵니다. 짝수라면 2로 나누고 홀수라면 3을 곱하고 1을 더합니다. 만약 그 수가 1이 되면 멈추고, 아니라면 위 과정을 반복합니다. 이 과정을 반복하면 항상 마지막 수는 1이 나오게 됩니다. 컴퓨터로 2^68까지의 자연수를 확인해본 결과 성립했지만 아직 모든 자연수에 대해 성립하는지 증명은 되지 않았습니다. 한 번 도전해보시겠습니까? 콜라츠 추측(Collatz conjecture)은 1937년에 처음으로 이 추측을 제기한 로타르 콜라츠의 이름을 딴 것으로 3n+1 추측, 울람 추측, 혹은 헤일스톤(우박) 수열 등 여러 이름으로 불립니다. 생각을 바꾸어보면 1부터 출발해 콜라츠 추측의 역과정을 진행하며 수형도를 만들어보았을 때 모든 자연수가 나오는지 확인해보는 방법도 있습니다. ..
여기 만원이 들어 있는 투명한 상자 A와 불투명한 상자 B가 있습니다. 여러분들은 A, B 두 상자 모두 가져가거나 B상자만 가져갈 수 있습니다. 그런데 저는 여러분이 미래에 어떤 선택을 할지 정확히 알고있습니다. 여러분들이 미래에 두 상자 모두 가져간다면 전 B 상자를 비워두고 여러분이 B 상자만 가져간다면 전 B상자에 100만원을 넣어두겠습니다. 제가 돈을 넣을지 말지 선택하고 떠난 이후 여러분이 할 수 있는 최선의 선택은 무엇일까요? A,B 둘다 가져 가실건가요? 아니면 B만 가져가실 건가요? 선택하셨나요? 1 ) 상자 A, B를 모두 가져간다. 저는 이미 돈을 넣어두고 떠났기에 여러분이 선택을 할 때 B 상자에 들어있는 돈의 액수는 이미 정해져 있습니다. 다른 말로 여러분이 어떤 선택을 하든지에 ..
최근 수십년간 컴퓨터에 의한 수학 이론의 발견과 증명에 학자들 뿐만 아니라 일반인까지도 많은 관심을 가졌다. 컴퓨터가 증명한 수학문제들을 먼저 알아보고 이러한 컴퓨터의 발전이 현대 수학에 미치는 영향에 대해 생각해보자 . 컴퓨터에 의한 증명 컴퓨터에 의한 증명 중 제일 유명한 것은 4색문제일 것 같다. 1852년 영국의 수학자 프랜시스 구트리에는 영국 지도를 색칠하다 한 가지 물음을 갖게 된다. 임의의 구획으로 나뉜 지도를 색칠할 때 인접한 구획을 같은 색으로 칠하지 않으려면 최소한 몇 가지의 색이 필요할까? 실제로 색을 칠해보니 영국의 지도는 네 가지 색이면 충분하게 색칠 되었다. 그런데 그는 왜 그렇게 되는지 알 수는 없었다. 이 문제는 '4색 문제'라고 불리며 수수께끼로 남았고 100년이 넘는 시간..