중학교 STEAM 자유학기제 학생용 교재
제약 만족 문제
차 례
프롤로그 1
시작하며 – 인공지능 4
1차시 – 제한된 조건을 가진 문제에 대해 생각해보기 9
1차시 – 3색 땅따먹기 놀이하기 12
읽을거리 1 – 비행기 착륙 스케줄링 알고리즘 13 2차시 – 복잡한 것을 단순하게 나타내보기 16 2차시 – 복잡한 것을 단순하게 나타내보기 2 17 2차시 – 여러 가지 방법으로 해결해보기 19
읽을거리 2 – 4색 문제 21
3차시 – 다양한 제약 만족 문제 만들기 : 시간표 23
3차시 – 다양한 제약 만족 문제 만들기 : 스도쿠 25
프롤로그
2016년 3월. 전 세계 바둑기사 중 최고라고 인정받는 이세돌 9단이 구 글의 인공지능 ‘알파고’에게 패했다는 기사는 온 세상을 떠들썩하게 만들었습니다. 그동안 인공지능이 어느 정도로 발전한지를 실감하지 못 했던 사람들이 이 사건으로 인해 뼈저리게 알게 되었으며, 인공지능 시 대가 열렸다는 것은 인정하게 되었죠. 이제 인공지능은 단순한 수학계산 을 하는 것이 아니라 다양한 경우의 수에 대한 판단과 통찰력의 수준까 지 인간을 능가할 수 있게 되었음을 보여주었습니다.
인공지능은 단순한 신기술이 아닌 산업이나 사회의 커다란 변화를 불 러오는 혁신기술이자 범용기술이라고 할 수 있습니다. 인공지능이 활용 되고 있는 분야도 매우 다양합니다. 국방, 의료 및 헬스케어, 생활, 교육 및 게임, 보안, 안전한 자율주행차 운전, 번역, 로봇 등 다양한 분야에서 개발이 되고 있습니다. 앞으로는 더 강한 인공지능이 개발되겠죠.
<자료> 이승훈, ‘최근 인공지능 개발 트렌드와 미래의 진화방향’, LG경제 연구원, 2017.12.
[그림] 인공지능 기술의 발전과정과 미래
인공지능이 사람의 문제를 해결해주고, 도움을 준다는 것은 매우 반가 운 일입니다. 하지만 우려되는 점은 인공지능이 사람의 일을 대체하고 있어 그와 관련된 일을 하는 사람들이 일자리를 잃는다는 것입니다. 앞 으로 인공지능에 의해 대체될 가능성이 가장 높은 직업으로 변호사, 회 계사 및 세무사, 증권사 애널리스트, 의사 등이 언급되고 있습니다. 그나 마 다행인 것은 인공지능은 고도의 연산이 필요한 부분에서는 인간보다 뛰어난 능력을 보여주지만 추상적인 개념이나 아이디어, 직관, 사람에 대한 공감을 필요한 영역에서는 10년 안에 인간을 능가하기가 쉽지 않 다고 합니다. 그래서 여러분이 자신의 진로를 설계할 때에는 인공지능이 그 일을 대체할 수 있을지 없을지를 고려해보아야 합니다. 인간만이 할
여러분이 살아갈 미래는 인공지능과 함께 공존해가는 사회가 될 것입 니다. 인공지능을 두려워하기보다는 인공지능을 제대로 알고, 이를 바르 게 활용하여 문제를 해결할 수 있는 방법을 찾는다면 인류에게 도움이 될 수 있을 것입니다. 칼을 어떻게 쓰느냐에 따라 도구가 되기도 하고 무기가 되기도 합니다. 인공지능을 바르게 활용하고 함께 공존하여 살아 갈 수 있는 방법을 찾는 것은 바로 여러분들의 몫입니다. 인공지능에 대 한 바른 이해와 더불어 바른 가치관의 확립으로 빠르게 변화하는 세상 에서 우뚝 설 수 있는 여러분이 되길 기대해봅니다.
시작하며
인공지능
인공지능은 시스템에 의해 만들어진 지능을 말한다(위키백과). 인공지 능에 대한 정의는 학자들이 매우 다양하게 정의하고 있으며, 현재 가장 활발하게 연구되고 있는 분야는 ‘인간처럼 행동하는 시스템’이다.
[이미지 출처: www.pixabay.com]
기계가 사람의 지능을 모방하여 사람의 일을 좀 더 효율적으로 처리 하기 위해 고안하여 만들어졌으며, 이 생각은 1950년 앨런 튜링의 생각 하는 기계의 구현 가능성에 대한 분석이 담긴 논문에서 시작이 되었다.
그는 "생각"을 정의하기 어려움에 주목해, 그 유명한 튜링테스트를 고안 했다. 텔레프린터를 통한 대화에서 기계가 사람인지 기계인지 구별할 수 없을 정도로 대화를 잘 이끌어 간다면, 이것은 기계가 "생각"하고 있다 고 말할 충분한 근거가 된다는 것이었다.
이렇게 시작된 초기 인공지능 연구에서는 문제해결과 기호법 등의 주 제를 탐구하였으며, 1960년대로 들어오면서 인간의 기본적인 추론 방식 을 흉내낼 수 있는 컴퓨터를 훈련하기 시작하였고, 1970년 국방 고등 연 구 기획국(DARPA)이 도로 지도화 프로젝트를 실시하기도 하였다. 2003 년에ms 지능형 개인 비서를 개발하기도 하였으며, Siri(시리), Alexa(알렉 사)와 같은 인공지능이 이어서 개발이 되었다.
[이미지 출처: https://www.sas.com/ko_kr/insights/analytics/what-is-artificial-intelligence.html]
우리가 보는 영화나 공상 과학 소설에서는 인공지능이 세상을 파괴하 고 인류를 멸망하게 하는 인간형 로봇으로 표현되기도 하지만 현재의 인공지능 기술은 그렇게 똑똑하거나 위협적이지 않다. 인공지능은 모든 산업분야에 도움을 주고 있으며 이제는 소프트웨어의 핵심으로 자리를 잡아 여러 분야에서 활용이 되고 있다.
최근 AI의 급격한 발전은 머신러닝과 딥러닝이 대두된 시점에서부터이 다. 2010년도 들어가며 빅 데이터(Big Data)라는 훌륭한 기반이 갖춰지며 데이터 풍부해졌으며, 컴퓨터 성능의 발전, 고성능 네트워크 장비를 갖
춘 환경이 완성되었기 때문이다. 알파고와 왓슨의 탄생은 이 시점과 맞 물려 있다. IBM이 만든 왓슨은 의사와 변호사의 역할을 대신 수행하고 있으며, 왓슨의 암 진단율은 평균 96%, 미국 내 12개 로펌에서는 왓슨을 활용하고 있다. 이렇게 인공지능이 점점 똑똑해지고 있는 것은 기계가 스스로 학습하는 ‘머신러닝(Machine Learning)’ 덕분이며, 여기에 사람 의 뇌처럼 생각하도록 알고리즘을 만든 ‘딥러닝(Deep Learning)’으로 인해 인공지능은 점점 진화하고 있다. 머신러닝은 ‘기계가 인간처럼 학 습한다’는 뜻이다. 2012년 ‘이미지넷 이미지 인식 대회’에서 토론토 대학교 제프리 힌튼 교수 팀이 만든 ‘알렉스넷 (Alexnet)’이 우승하였다.
알렉스넷은 인간의 뇌 신 경망(합성곱 신경망, CNN) 을 인공지능에 적용한 딥 러닝의 결과물이다. 딥러닝 은 사람 뇌 속 1000억 개 에 달하는 뉴런 구조를 본따 만든 인공신경망을 컴퓨터에 적용시킨 결 과이다.
[이미지 출처: www.pixabay.com]
인공지능이 적용되는 분야는 무궁무진하다. 국방, 교육, 행정, 교통(자 율 자동차), 두뇌 인터넷, 생체인터넷(웨어러블), 로봇, 드론, SNS, 증강/
가상현실, 음성개인비서, 핀테크 등 안 들어간 분야가 없다.
앞으로 인공지능의 발전은 더욱더 가속화될 것이다. 인공지능의 발전 을 사람을 도와 보다 창의적인 아이디어를 만들어주고, 사람이 꿀 수 없 는 꿈을 대신 꿔서 비전과 전략을 그려주고, 사람들과 함께 어울릴 수 있는 개발로 이루어져야 할 것이다.
1차시
우리가 여행을 가기 전에 하는 고민은 무엇인가요? 바로 여행 일정을 어떻게 구성할지 계획하는 것입니다. 이때 고려되는 점들은 바로 여행 장소와 시간이 될 것입니다. 우리는 정해진 시간 안에 여러 장소를 이동 하며 여행을 다니게 됩니다. 이와 같이 우리는 여행하는 상황에서 시간 이라는 ‘제약’을 받게 되지요.
우리가 여행할 때 시간과 같은 제약이 있는 것처럼 제약만족문제는 여러 제약이 있는 상황에서 적합한 답을 찾는 문제입니다. 적합한 답은 한 가지가 될 수도 있고 그 이상이 될 수도 있습니다. 가령, 여행을 갈 때 시간이라는 제약이 있지만 주어진 시간 동안 갈 수 있는 다양한 코 스가 나올 수 있는 것과 같은 이치입니다.
제약만족문제(CSP, Constraint satisfaction problem)는 위에서 이야기한 제약이 있는 상황을 해결해가는 문제입니다. 이와 같은 문제상황을 다양 한 해결방법으로 해결해가면서 해결과정의 효율성과 정교성을 익힐 수 있고 인공지능이 해결하는 과정을 체험해 볼 수 있습니다.
본 프로그램은 제약만족문제의 해결원리를 놀이로 경험해보고 해결방 법을 공유해나갈 수 있도록 구성하였습니다. 학생들은 다양한 제약만족 문제를 해결해보며 여러 제약조건 속에서 문제해결 과정을 익히게 됩니 다. 이를 통해 실생활에서 발생 되는 문제 해결과 인공지능의 원리와 필 요성을 이해하는데 도움이 되길 바랍니다.
제약 만족 문제란 무엇일까?
활동 1 제한된 조건을 가진 문제에 대해 생각해보기
제약 만족 문제 1차시
[이 활동을 통해]
• 제한된 조건을 가진 문제에 대해 생각해 볼 수 있다.
• 3색 땅따먹기 게임하기를 통해 제약만족문제에 대해 알 수 있다.
◆ 다음을 읽고 물음에 답해 보세요.
민준이는 이번에 가족여행으로 제주도에 갔다가 돌아오는 길에 태풍으로 인해 비행 기가 지연되어 한 시간 이상 늦게 출발하게 되었다. 불편함을 겪으면서 비행 스케줄 이 어떻게 돌아가는지 호기심이 생긴 민준이는 직업 탐색 과제도 할 겸 ○○항공에 서 일하는 삼촌에게 인터뷰를 요청했다.
민준 : 삼촌! 오랜만이에요. 이번에 비행기를 타다가 좀 궁금한 게 생겨서요. 비행 시간표를 보면 똑같은 시간대에 출발하는 비행기가 많이 있는데, 비행기가 동시에 출발할 수 있나요?
삼촌 : 민준이가 이쪽에 관심을 갖다니 대견하구나. 일단, 하나의 항공에는 이륙과 착륙을 하는 활주로가 각 1개씩 있고, 서로 반대편에 있단다. 예외적으로 샌프란시 스코에 2개의 이륙 활주로가 있지. 비행기가 동시에 뜨는 것이 쉽지 않은데 그게 또 장관이라 유튜브에 보면 멋진 영상도 있어.
민준 : 우와.. 저는 비행기 게이트가 여러 개 있어서 활주로도 여러 개 있는 줄 알았 는데 아니네요. 그럼 시간표에서 같은 시각에 출발하는 비행기의 경우 어떻게 조절 하나요?
1. 인터뷰 내용을 읽어보고 새로 알게 된 내용에 대해 이야기해 봅시다.
2. 밑줄 친 삼촌의 마지막 질문에 대한 여러분의 생각을 적어 봅시다.
3. 비행기 시간표의 스케줄을 짜는 데에 영향을 주는 것에는 무엇이 있을지 생각해봅시다.
[이미지 출처: www.pixabay.com]
활동 2 3색 땅따먹기 놀이를 해 봅시다.
제약 만족 문제 1차시
민준 : 아하~! 비행기가 지연되면 승객들은 좀 불편을 겪기도 할 것 같은데 여러 대 가 한꺼번에 지연되면 엄청 불편하겠어요.
삼촌 : 그렇지, 우리나라에는 전 세계에서 약 80여개의 항공사들이 취항하고 있고, 비행 스케줄을 짜는데 시간 이외에 아주 많은 것들을 고려해야 한단다. 그럼 민준 아, 삼촌이 퀴즈 하나 내볼게. 비행기가 승객 난동으로 인해 이륙이 어려운 상황인 데 뒤에는 10분 안에 출발해야 할 비행기가 5대가 남아있단다. 남아 있는 비행기들 의 크기가 각각 다른데 사고가 나지 않도록 겹치는 시간이 없이 출발시키려면 어떻 게 조정해야 할까?
◆ 짝과 함께 3색 땅따먹기 놀이를 해 봅시다.
< 놀이 규칙 >
1. 두 사람이 각자 빈 종이에 다양하고 자유롭게 구역을 나눈다.
2. 1인당 검정바둑알 1인 1개, 흰 바둑알 10개를 갖는다.
3. 1인당 3가지 색의 색연필을 갖는다.
4. 검정바둑알을 원하는 귀퉁이에 각자 둔다.
5. 검정바둑알을 구역을 향해 튕긴다.
- 빈칸에 들어갔을 경우
: 땅의 주인이 되어 3개의 색연필 중 한 가지 색으로 색칠한다. 단 인접 한 면과는 다른 색으로 칠해야 한다.
- 내 땅에 들어갔을 경우
: 아무런 일도 일어나지 않는다.
- 상대방의 땅에 들어갔을 경우
: 흰 바둑알 1개를 상대방에게 넘긴다.
6. 모든 칸에 색칠이 끝나거나 더 이상 색칠할 수 없는 경우, 흰 바둑알을 모두 소진한 경우 게임이 종료된다.
7. 색칠한 칸수 + 흰 바둑알 개수가 많은 사람이 승자가 된다.
1. 색을 칠하면서 어떤 조건이 어려웠나요?
2. 모든 면을 색칠하는 데에 몇 개의 색이 더 필요할까요?
[이미지 출처: www.pixabay.com]
비행기 착륙 문제는 현실에서 착륙 시간보다 늦어질수록 발생하는 비용이 지수적으로 증가하므로 최적화된 알고리즘을 갖는 것이 매우 중요하다. 비행 기 착륙 시간에 영향을 주는 요인으로 활주로의 수를 포함한 활주로의 정보 를 모두 포함시켜야 하고, 착륙하는 순서(원래 스케줄된 순서)또한 포함한다.
알려진 유명한 알고리즘으로 심플렉스(Simplex) 알고리즘과 분기 절단 (Branch-and-Cut) 알고리즘이 있다. 심플렉스 알고리즘은 실수 형태만 사용 할 수 있다. 이는 위의 여러 가지 제한 조건들이 만들어내는 공통부분을 차 원을 확장한 다각형들이 만들어 내는 공통부분에서 최적의 답을 찾아낸다.
우리가 살고 있는 세상은 3차원이지만, 컴퓨터는 3차원 이상의 초평면들에 걸친 계산을 할 수 있다. 심플렉스 알고리즘은 순서나 활주로가 모두 정해져
비행기 착륙 스케줄링 알고리즘
있을 때 착륙 시간만 결정할 수 있다.
분기 절단 알고리즘은 정수를 최적화 하여 계산할 수 있는 프로그램으로 비행기가 착륙하는 순서, 선택하는 활주로의 정보를 모두 포함하여 계산할 수 있다. 이는 여러 개의 가지(Branch)를 가진 가상의 정답들을 만들어내고 답이 없는 확률이 높은 가지들을 제거해 나가면서 최적의 답을 찾아가는 방 법이다.
참고 : 최적의 비행기 착률 스케줄링 알고리즘 개발/한국항공우주학회
2차시
활동 3 복잡한 것을 단순하게 나타내보기
제약 만족 문제 2차시
[이 활동을 통해]
• 문제 해결을 위해 복잡한 것을 단순하게 나타낼 수 있다.
◆ 다음 모양을 몇 가지 색으로 구분하여 칠할 수 있는지 경우의 수를 모두 써 보세요.
(단, 선이 맞닿은 부분은 같은 색으로 칠하지 않습니다.) (1) - ( )가지 (2) - ( )가지
(3) - ( )가지 (4) - ( )가지
(5) - ( )가지 (6) - ( )가지
(7) - ( ) 가지 (8) - ( )가지
◆ 칸의 숫자가 많아질수록 꼭 더 많은 색을 사용해서 칠해야 할까요?
제약 만족 문제
활동 4 복잡한 것을 단순하게 나타내보기 2
제약 만족 문제 2차시
◆ 다음 그림을 보고 물음에 답하세요.
<보기>
(1) <보기> 그림은 위의 무엇과 같나요? ( )
① ② ③ ④ ⑤
(2) 선이 맞닿은 곳을 기준으로 단순화할 때, <보기>와 같은 구조는 무엇일까 요? ( )
① ② ③ ④ ⑤
* <활동 1>의 (1)~(8)을 이와 같이 점과 선으로 연결된 모양으로 만들어 봅 시다.
예시) (1) → (2) →
(3) →
(4) →
(5) →
(6) →
(7) →
(8) →
<심화문제>
(3) 선이 맞닿은 곳을 기준으로 구분할 때, 아래와 같은 그림은 무엇일까요?
( )
① a b c d ②
b c d
a ③
c d
a b
a b a b c
활동 5 여러 가지 방법으로 해결해보기
제약 만족 문제 2차시
◆ 색을 하나씩 칠할 때 마다 다음에 올 수 있는 색깔들을 선으로 연결하면서 나열한다고 가정하고, 색칠을 하면서 문제를 해결 해 봅시다. (이것을 트리 구조라고 합니다. 선을 추가하거나 지도를 더 추가해서 그려도 됩니다.)
이미지출처: https://www.youtube.com/watch?v=lCrHYT_EhDs
◆ 해결한 과정을 친구에게 설명해 봅시다.
◆ 해결해야 할 문제를 점과 선으로 단순하게 만들어 봅시다.
T
이미지출처: https://www.youtube.com/watch?v=lCrHYT_EhDs
(1) 선이 하나도 연결되지 않은 부분은 어디입니까?
(2) 가장 선이 많이 연결된 부분은 어디입니까?
(3) 이러한 모양으로 단순화 했을 때 찾을 수 있는 해결 방법을 생각해봅시다.
가장 먼저 할 수 있는 일은 무엇일까요?
(4) (3)을 했을 때, 나머지 부분을 칠할 수 있는 색은 몇 가지가 남습니까?
(5) 다른 색으로 이 과정을 반복했을 때 총 나올 수 있는 경우의 수는 몇 가 지가 될까요?
4색 정리(또는 4색 문제)는 평면을 유한개의 부분으로 나누어 각 부분에 색을 칠할 때, 서로 맞닿은 부분을 다른 색으로 칠한다면 네
가지 색으로 충분하다는 정리이다. 이 문제는 지도에서 서로 맞닿은 지역에 다른 색을 칠한다는 것에서 착안해 만들어졌다.
세 가지 색으로는 평면을 칠할 수 없다는 것은 반례를 찾는 것으로 증명할 수 있다. 또한 다섯 가지 색으로 칠 하는 것이 가능하다는 것도 증명되어 있다. 하지만 네 가지 색으로 가능한지에 대한 문제는 오랫동안 미해결 상태였다.
평면을 여러 개의 부분으로 나누는 가짓수를 무한 개에서 유한 개로 줄인 증 명이 발표된 후, 이후 이 유한개의 경우를 모두 컴퓨터 계산을 통해 검사하였다.
즉, 이 문제는 컴퓨터를 이용한 증명으로, 일부 사람들은 이러한 증명은 진정한 의미의 수학적인 증명이 아니라고 생각하고, 더욱 간단한 방법의 증명을 찾는 사람들도 있다.
출처: https://ko.wikipedia.org/wiki/4색정리
네 가지 색으로 모두 칠하기! 4색 문제
3차시
◆ 일상생활에서 제약이 있는 조건이 있는 문제를 찾아봅시다.
1. 일상생활에서 제약만족문제와 관련된 사례에는 어떤 것이 있을까요?
2. 각 문제에는 어떤 제약 조건이 있나요?
3. 각 문제를 해결하려면 어떻게 해야 할까요?
◆ 시간표 짤 때의 조건을 살펴보며 모둠원과 시간표를 짜 봅시다.
1. 시간표를 짤 때 어떤 조건들이 필요할까요?
2. 모둠원과 조건을 만들어 우리 학년의 시간표를 짜 보세요.
과목 : 국어, 수학, 영어, 사회, 도덕, 과학, 기술·가정, 음악, 미술, 체육
조건 1. 일주일 간 총 몇 시간의 수업을 해야 하는가?
조건 2. 과목별로 일주일 간 몇 시간씩 수업을 해야 하는가?
조건 3. 과목을 수업하시는 교사는 몇 명인가?
조건 4. 하루에 같은 과목을 몇 시간까지 수업할 수 있는가?
조건 5. 하루 수업은 몇 교시까지 구성할 수 있는가?
다양한 제약 만족 문제를 알아볼까요? : 시간표 짜기
제약만족문제 3차시
활동 5
( ) 반
월 화 수 목 금
1교시 2교시 3교시 4교시 5교시 6교시 7교시
( ) 반
월 화 수 목 금
1교시 2교시 3교시 4교시 5교시 6교시 7교시
( ) 반
월 화 수 목 금
1교시 2교시 3교시 4교시 5교시 6교시 7교시
( ) 반
월 화 수 목 금
1교시 2교시 3교시 4교시 5교시 6교시 7교시
◆ 간단한 스도쿠 문제를 풀어보고 문제를 만들어 봅시다.
1. 다음의 빈칸에 가로, 세로에 각각 1~9가 한 번씩만 들어가도록 숫자를 채워보세요.
8 6 4 9 1 2 7 3 1 9 5 7 2 3 4 8 6
3 2 7 1 9 5
9 2 3 8
6 4 8 3 9 7 5 2 1
2 3 7 9
4 6 7 9 2
9 8 2 5 3 4 6 1 7 1 2 6 9 8 4
2. 다음 조건을 확인하여 새로운 스도쿠 문제를 만들어 보세요.
조건 1. 총 22개의 빈 칸을 만드세요.
조건 2. 가로 3줄과, 세로 3줄은 1~9가 모두 채워져 있도록 만드세요.
조건 3. 가로줄에서 두 칸이 비어 있는 줄이 1줄, 세 칸이 비어 있는 줄 이 2줄, 네 칸이 비어 있는 줄이 1줄, 5칸이 비어 있는 줄이 2줄 이 되도록 만드세요.
다양한 제약 만족 문제를 알아볼까요? : 스도쿠
제약만족문제 3차시
활동 6
8퀸 문제는 8×8크기의 64칸의 체스 판에 퀸 8개를 배치하는 문제이다.
1848년 막스 베첼이 처음 제안하였다. 이 문제를 일반화하면 N×N 크기의 체 스 판에 퀸을 N개 배치하는 N퀸 문제가 된다. N이 2, 3인 경우를 제외하고 해 를 찾을 수 있다.
아래와 같은 8×8 체스 판에 퀸을 배치하는데 다음과 같은 조건을 고려한다.
1. 퀸을 배치하고자 하는 위치에서 같은 행과 열에 퀸이 있는지 확인한다.
2. 퀸을 배치하고자 하는 위치에서 오른쪽 대각선 방향으로 퀸이 있는지 확인한다.
3. 퀸을 배치하고자 하는 위치에서 왼쪽 대각선 방향으로 퀸이 있는지 확 인한다.
8퀸 문제의 고유한 해(선대칭이나 점대칭 으로 대칭인 해)는 12개가 있고, 일반적인 해(대칭을 구별한 해)는 92개가 있다. 다음 은 그 해들 중 일부이다. 또 다른 해에는 어 떤 것이 있을까?
(출처 : 위키 백과 ‘여덟 퀸 문제’)
