5 . 정보 이론
5.1 활동 5
개요
1,000 페이지 책에는 얼마나 많은 정보가 있을까요? 1,000 페이지 전화 번호부에 더 많은 정보가 있을까요? 1,000 페이지 백지에 더 많은 정보가 있을까요? 톨킨이 저작한 “반지의 제왕”에 더 많은 정보가 있을까요? 만약 정보의 양을 측정할 수 있다면, 정보를 저장하기 위해 얼마나 많은 저장공간이 필요한지 추정할 수 있습니다. 예를 들어, 공항에서 비행기에 가방에 단 3개 로마자로 ICN(인천), NRT(나리타), HKG(홍콩) 공항을 상상합니다. 다음 문장을 모음 없이 읽을 수 있습니까?
Ths sntnc hs th vwls mssng.아마도 여러분은 “This sentence has the vowels missing”라고 제대로 읽을 것입니다. 모음에는 그다지 정보가 많지 않기 때문입니다. 이번 활동은 정보의 양을 측정하는 방법을 소개합니다.
5.3 스무고개
5.3.1 토론
아이들과 아이들이 생각하는 정보가 무엇인지에 대해서 토론해 봅시다.
책에 정보의 양이 얼마나 되는지 어떻게 측정할 수 있을까요? 페이지 숫자가 중요할까요, 아니면 단어 숫자가 더 중요할까요? 이 책이 다른 책보다 더 많은 정보가 있을까요? 책이 몹시 지루한 책이거나, 반대로 특히 재미있는 책이라면 어떨까요? “뭐라, 뭐라, 뭐라(blah, blah, blah)”라는 문구만 포함된 400 페이지 책이 전화번호부보다 더 많은 혹은 더 적은 정보를 가지고 있습니까?
컴퓨터 과학자들은 메시지(혹은 책)가 얼마나 놀라운가에 따라 정보량을 측정한다고 설명합니다. 이미 알고 있는 것, 예를 들어 항상 걸어서 학교에 오는 아이가 “오늘은 걸어서 학교에 왔다”라고 말했다고 하면 여기에는 정보가 없습니다. 왜냐하면 놀랄 일이 아니기 때문입니다. 하지만 “오늘 헬리콥터 타고 학교에 왔어”라고 했다면, 놀랄 것이고, 엄청난 정보를 우리에게 전한 것입니다.
메시지의 ’깜짝도(suprise value)’는 어떻게 측정할까요?
하나의 방법은 정보를 추측하는 것이 얼마나 어려운지를 살펴보는 것이다. 만약 함께 걸어서 학교에 온 친구에게 “오늘 어떻게 학교에 왔는지 맞춰봐”라고 물어보면, 한번에 맞출 수 있습니다. 하지만 과거에 헬리콥터를 타고 온 적이 있으면 여러 번 추측할 필요가 있을지도 모르고, 우주선으로 여행을 한 적이 있다면, 더 시간이 걸릴지도 모릅니다.
메시지가 가지는 정보량은 그것을 짐작하는 것이 얼마나 쉬운지 어려운 것인지에 따라 측정합니다. 다음 게임은 이해하는 데 도움을 줄 것입니다.
우주선
5.4 질문 20개 활동
여기 질문 20개라는 게임을 소개합니다. 정답을 맞출 때까지, 아이들은 선택된 1 명의 아이에게 질문을 계속하고, 선택된 아이는 “예”, “아니오” 둘 중 하나만 대답합니다. “예” 또는 “아니오”로 대답할 수 있다면 어떤 질문을 해도 좋습니다.
5.4.1 질문의 예
다음과 같이 생각하고, 맞춰보세요.
- 1에서 100사이의 숫자 하나
- 1에서 1,000사이의 숫자 하나
- 1에서 1,000,000사이의 숫자 하나
- 임의의 정수
- 적당한 그룹으로 패턴을 가진 5개의 숫자 순열. 처음부터 끝까지 순서를 맞춰보세요.(예: 2, 4, 6, 8, 10)
질문 개수를 세어보세요. 질문 횟수를 정보량(value of the “information”)이라고 합니다.
5.4.2 후속 토론
어떤 전략으로 질문을 했나요? 가장 효과적인 질문 전략은 무엇이었나요?
1에서 100 사이의 숫자를 찾기 위해서 만약 질문 범위를 절반으로 줄여간다면 단 7번의 질문으로 정답을 맞출 수 있다. 예를 들어,
- 50보다 작습니까? 예.
- 25보다 작습니까? 아니요.
- 37보다 작습니까? 아니요.
- 43 보다 작습니까? 예.
- 40 보다 작습니까? 아니요.
- 41 보다 작습니까? 아니요.
- 42네요! 예!
흥미로운 점은 질문의 범위가 1,000으로 확대된다면, 10배만큼 노력이 들지 않고, 단지 추가 질문 3개만이 필요하다. 질문의 범위가 두 배씩 증가할 때마다 정답을 찾기 > 위해서 한 개의 추가 질문만을 필요로 합니다.
다음 연계된 후속 활동으로 아이들에게 Mastermind 놀이를 추천드립니다.
5.4.3 확장: 메시지에 얼마나 많은 정보가 있을까요?
컴퓨터 과학자는 단순한 숫자 맞추기 게임 말고, 단어나 문장에서 어느 글자가 다음에 가장 나올 것인가 같이 다음 문자를 추측하는 게임도 합니다.
4~6개 단어로 구성된 짧은 문장으로 게임을 진행해 봅시다. 글자를 처음부터 끝까지 잘 정렬된 순서로 질문을 합니다. 왼쪽에서 오른쪽 순서로 문자를 맞춰보세요. 한 아이가 > 글자를 적고, 얼마나 많은 시도 끝에 올바르게 정답을 맞췄는지 횟수를 기록합니다. 예/아니오 답을 가진 질문은 모두 사용될 수 있습니다. 예를 들어, ’t’가 있나요? > 모음인가요? 알파벳의 m 앞에 오나요? 단어 사이의 공백도 문자로 간주되며 맞춰야 하는 대상이 됩니다. 순서를 바꿔가며 어느 메시지가 찾기 쉬운지 확인해 보세요.
5.5 활동 : 의사결정나무
질문하는 전략에 대해서 익숙해졌다면, 질문을 하지 않고 메시지를 보낼 수 있다.
다음 도표를 “의사결정 나무”라고 부른다.
이 그림은 0 에서 7 사이 정수를 맞추기 위해 고안된 의사결정 나무 도표입니다. yes가 “예”, no가 “아니오”가 no입니다.
의사결정 나무
숫자5를 맞추기 위해서 필요한 yes / no 결정은 무엇일까요?
임의 숫자를 맞추기 위해서 yes / no 결정이 몇 번이나 필요할까요?
이제 뭔가 멋진 일을 살펴보시죠. 의사결정나무의 가장 아래 0,1,2,3 …의 숫자 아래에, 이진수를 써 봅시다. (활동 1 참조)
나무를 유심히 살펴보세요. No가 “아니오” 0을, yes가 “예” 1로 나타내면, 무엇이 보이나요? 숫자 추측 게임에서, 질문을 선택하는 하는데 응답 순서가 정확하게 숫자를 표현하는 방식과 동일합니다.
0에서 15사이 정수를 맞추기 위한 의사결정 나무를 직접 만들어 봅시다.
심화문제: 누군가의 나이를 맞추려면 어떤 종류의 의사결정 나무를 사용해야 할까요? 문장의 다음 글자를 맞추려면 어떤 의사결정나무가 있어야 할까요?
5.6 컴퓨터 과학 핵심 개념
저명한 미국 수학자 (저글러이며, 외발 자전거 선수) 클로드 섀넌(Claude Shannon)은 이 게임으로 많은 실험을 했습니다. 그는 정보량을 비트 (각 “예/아니오” 응답이 0/1 비트에 상응)로 측정했습니다.
메시지 정보량은 이미 얼마나 알고 있는냐에 달려있다는 것을 발견했습니다. 때때로 질문 하나로 다른 많은 질문을 할 필요를 없게 만듭니다. 이 경우 메시지의 정보량은 매우 적습니다. 예를 들어, 동전던지기 한번의 정보는 통상 1 비트(앞면, 뒷면)입니다. 하지만, 동전의 양면 중 한 면이 편향(bias)되어서 10번 던져 9번 앞면이 나온다면, 정보량은 더 이상 1 비트가 아니고, 믿든 믿지 않든, 1비트보다 적습니다. 어떻게 동전 던지기 결과를 1 회 미만의 질문으로 알 수 있는 것일까요? 간단합니다. 다음과 같은 질문을 하면 됩니다. “다음 2번 동전 던지기 결과 모두 앞면이 나왔나요?” 편향되어 있는 동전 던지기 결과는 이 질문에 약 80% 확률로 “예”, “아니요”가 나온 경우에는 두 개의 추가 질문을 해야 합니다. 하지만, 평균적으로, 동전을 던질 때마다 1회 미만의 질문을 할 것이다.
새논(shannon)
섀논은 메시지 정보량을 엔트로피(“entropy”) 라고 명명했습니다. “엔트로피”는 동전 던지기의 경우는 두 사건(앞면/뒷면)처럼 사건의 수(number) 뿐만 아니라 그것이 일어나는 확률(probability)도 영향을 받습니다. 있을 수 없는 사건, 즉 놀라운 정보는 해당 메시지에 대해 많은 횟수의 질문이 필요한데, 이유는 우리가 아직 알지 못하는 더 많은 정보를 알려주기 때문입니다. 마치 헬리콥터를 타고 학교에 가는 상황처럼 말입니다.
메시지 엔트로피는 컴퓨터 과학자에게 매우 중요합니다. 엔트로피보다 적은 공간을 차지하도록 메시지를 압축할 수 없습니다. 가장 압축이 좋은 시스템은 숫자 맞추기 게임과 동일합니다. 컴퓨터 프로그램이 ’추측’을 하는 것이기 때문에, 질문 목록은 나중에라도 다시 재구성될 수 있다. 그래서 정답(비트)이 저장이 되어 있으면, 정보를 다시 재구성할 수 있다! 가장 효율적인 압축 시스템은 텍스트 파일을 원래 크기의 4분의 1 까지 압축할 수 있습니다. 엄청난 저장공간의 절약입니다.
숫자를 추측하는 게임 방법은 사용자가 다음에 무엇을 입력할까를 추측하는 컴퓨터 인터페이스 설계에도 사용됩니다. 키보드 입력에 어려움이 있는 장애인을 위해서 이 방법이 유용하게 사용될 수 있습니다. 장애인이 다음에 입력할 것을 컴퓨터가 추측하여 제시하면, 장애인은 원하는 바를 선택하면 됩니다. 좋은 시스템은 평균적으로 문자당 2개 예/아니오(yes/no) 결과를 필요합니다. 마우스나 키보드를 미세하게 조정하는데 어려움이 있는 장애인에게 큰 도움이 될 수 있다. 이런 종류의 시스템은 동일한 원리로 스마트폰 문자를 입력하는데 사용될 수 있습니다.
5.7 해답과 힌트
그 질문이 간단한 “50보다 큽니까?”라는 질문이든 “20과 60 사이입니까?”라는 좀더 복잡한 질문이든지, 1 회 “예/아니오” 질문에 대한 답변은 정확히 1 비트 정보에 상응합니다.
숫자를 추측하는 게임에서는 특정 방식으로 질문을 선택해 나아간다면, 응답 순서는 이진수로 표현한 것과 동일합니다. 3은 이진수로 011이고, 의사결정나무에서 응답으로 나열하게 되면 “아니오, 예, 예”입니다. “아니오” 대신에 0, “예” 대신에 1을 쓰면, 3을 이진수로 표현한 것과 동일합니다.
나이를 맞히는 의사결정 나무는 작은숫자 쪽으로 편향(bias)이 있을지도 모릅니다.
문장에서 다음 글자의 추천은 앞에 나온 글자에 좌우됩니다.