선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 그 결과 사다리 게임 프로젝트를 심화하는 별도의 후속 연구를 통해 최소생성사다리를 생성하는 새로운 알고리즘을 Mathematica 프로그래밍으로 구현하였고 그 결과 생성된 그래프의 속성을 분석하였다. 연구 문제는 사다리 게임에서 등장하는 최소생성사다리의 개수를 찾는 알고리즘을 향상하는 방법을 통해 등장한 새로운 그래프의 구조를 파악하면서 그 과정에서 최소생성사다리에 관한 자료의 분석 및 시각화, 추상화 작업 등을 통해 나타나는 컴퓨팅 사고력의 양상을 다루는 것이다.
- 이 연구는 사다리 게임의 순열에 대응하는 함수 개념을 적용한 최소생성사다리의 특성을 탐구하면서 이산수학과 컴퓨팅 사고력의 관련성을 다루고자 하였다. 구체적으로 대학 교수인 연구자는 사다리 게임을 주제로 사사 형태의 장기 프로젝트인 R&E 활동[5]에 참여하였던 고등학생들을 지도하였다.
- 이러한 이유로 화이트박스 형태로 수학적 사고력을 신장시키는 학습 방식이 컴퓨터교육에서 전개되는 사례를 탐구할 필요가 증가하고 있다. 이에 이 연구는 고등학생들이 일상생활에서 내기를 하거나 복불복 형태로 어떤 것을 선택하고자 할 때 흔히 사용하는 사다리 게임에 관하여 팀별 프로젝트를 수행하였던 사례를 고찰하고자 한다. 순열과 일대일 대응을 보여주는 사다리 게임의 이산 구조는 수학과 컴퓨터 분야에서 매력적으로 등장한다[2][3][4].
제안 방법
- (4, 6) 사다리의 경우에 ‘010210’ 사다리에서 ‘101210’으로 수열을 치환하는 방법을 사용하여 8개의 최소생성사다리를 생성하는 그래프를 만들었다.
- R&E 고등학생들을 지도하면서 연구자는 다음과 같이 필터링 알고리즘 A를 Mathematica로 구현하였다.
- 구체적으로 하이퍼큐브에 트리구조를 임베딩하는 것처럼 다원트리 형태의 그래프 탐색 방법을 적용하여 다음과 같이 알고리즘 B를 설계하였다.
- R&E 고등학생들을 지도하면서 연구자는 다음과 같이 필터링 알고리즘 A를 Mathematica로 구현하였다. 구체적으로, n개의 중복되지 않는 숫자로 이루어진 순열 전체의 집합 [n]에서 역순열을 생성해 주는 사다리 집합을 골라서 같은 모양을 제거하는 필터링 방식을 사용하였다. 이 알고리즘은 순열, 치환, 필터링을 사용하는 비교적 간단한 장점을 가진 반면에 n이 증가할수록 메모리와 연산의 복잡도가 증가하는 O(2^n)의 복잡도를 가지고 있다.
- 구체적으로 대학 교수인 연구자는 사다리 게임을 주제로 사사 형태의 장기 프로젝트인 R&E 활동[5]에 참여하였던 고등학생들을 지도하였다. 그 결과 사다리 게임 프로젝트를 심화하는 별도의 후속 연구를 통해 최소생성사다리를 생성하는 새로운 알고리즘을 Mathematica 프로그래밍으로 구현하였고 그 결과 생성된 그래프의 속성을 분석하였다. 연구 문제는 사다리 게임에서 등장하는 최소생성사다리의 개수를 찾는 알고리즘을 향상하는 방법을 통해 등장한 새로운 그래프의 구조를 파악하면서 그 과정에서 최소생성사다리에 관한 자료의 분석 및 시각화, 추상화 작업 등을 통해 나타나는 컴퓨팅 사고력의 양상을 다루는 것이다.
- 기존 연구에서 R&E 프로젝트에 참여하였던 학생들은 C 프로그래밍을 사용하여 초기 순열(예, 1234)을 사다리 타는 게임의 경우를 모두 탐색한 후에 그 결과값이 역순으로 정렬되는 사다리만 나타내고, 그렇지 않은 사다리들은 삭제하였다[10]. 다시 말하면 가로판이 n개, 세로줄이 m개일 때 (n-1)m개의 전체 탐색 공간에서 초기 순열의 역순열에 해당되지 않는 사다리를 제거시키는 필터링 알고리즘을 적용하였다. 그들은 C 프로그램을 테스트한 결과 다음과 같이 최소생성 사다리의 수를 구하였다.
- 첫째, 그들은 사다리 타기 게임에서 나타나는 순열과 조합, 사다리 그래프 등 이산적 구조를 사용하여 최소생성사다리의 특징을 포착하였다. 둘째, 최소생성사다리를 찾는데 필요한 조합적 생성과 중복되는 연산의 결과를 제거하는 필터링 알고리즘을 고안하였고 C 프로그래밍으로 구현하여 그들이 예측한 바를 검증하였다. 이 과정에서 그들은 역할 분담을 통해 손으로 계산을 하면서 필터링 알고리즘을 C 언어로 구현하는 등 컴퓨팅 사고력과 관련된 역량을 신장시키는 모습을 보여주었다.
- 또한 이광연과 동료들은 고등학교 함수 단원에서 사다리 게임을 도입하기 위하여 사다리 게임의 함수적 속성을 분석하였으며 사다리타기 게임을 통한 함수 지도 방안을 제시하였다[2]. 그들은 사다리 타기 게임에 대하여 수학적으로 접근함으로써 수학 내적인 부분에 대하여 집중할 수 있도록 하였으며 학습 활동의 난이도가 증가할 것을 고려하여 팀별 활동을 제안하였다.
- 앞서 소개한 R&E 프로젝트 활동은 순열과 조합을 이용하여 단계별로 논리적 사고를 전개하면서 컴퓨터 프로그래밍(예, C 언어)으로 구현하는 화이트박스 기반의 알고리즘 학습의 특징을 보여준다[1]. 부연하면 참여 학생들은 최소생성사다리의 개수를 찾는 과정에서 다음과 같이 알고리즘적 사고를 C 프로그래밍으로 구현하였다[14]. 첫째, 그들은 사다리 타기 게임에서 나타나는 순열과 조합, 사다리 그래프 등 이산적 구조를 사용하여 최소생성사다리의 특징을 포착하였다.
- 그들은 사다리의 세로판 개수와 가로판의 개수 사이의 관련성을 살펴보았고 C 프로그래밍을 사용하여 사다리 게임의 결과에 해당되는 빈도수를 조사하였다. 빈도수를 분석한 결과 중복되는 원소를 발견하였고 이를 제거하는 방식을 탐구하였다. 이 과정에서 중요한 역할을 하는 것은 <그림 1>의 #2와 #6처럼 서로 대칭되면서 {1,2,3}에 대한 역순열인 {3,2,1}을 대응시켜 주는 사다리이다.
- 재귀적 패턴이 나타나는 것에 착안하여 Mathematica 프로그래밍으로 데이터 시각화와 알고리즘에 대한 추상화 작업을 하면서 탐구한 결과 최소생성 사다리를 정점으로 하는 새로운 그래프를 발견하여 YC그래프라는 이름을 붙였다. 연구자가 수행하였던 자료분석 및 표현, 추상화, 알고리즘의 설계, Mathematica 프로그래밍으로 구현, 테스트한 과정를 다음에 제시하면서 컴퓨팅 사고력에 관하여 탐구하고자 하였다.
- 연구자는 62개의 정점을 가진 새로운 그래프의 구조에 주목하면서 (4, 6) 사다리의 최소생성사다리의 집합과 비교하는 작업을 수행하였다. 재귀적 패턴이 나타나는 것에 착안하여 Mathematica 프로그래밍으로 데이터 시각화와 알고리즘에 대한 추상화 작업을 하면서 탐구한 결과 최소생성 사다리를 정점으로 하는 새로운 그래프를 발견하여 YC그래프라는 이름을 붙였다.
- 이 논문에서 연구자는 R&E 프로젝트에 참가하였던 고등학생들을 지도하면서 함께 사다리 게임에서 등장하는 최소생성사다리의 특징을 탐구하였던 기존 연구[6][10]를 토대로 최소생성사다리를 생성원(generator)으로 하는 새로운 그래프를 창출하였다[11]. 연구자는 Mathematica 언어의 Make 명령어를 사용하여Mathematica로 구현함으로써 그래프의 탐색 알고리즘을 응용하여 새로운 그래프의 속성을 조사하는 프로젝트로 확장하였다[13].
- 연구자는 알고리즘 A를 Mathematica로 구현하여 (4, 6) 사다리에서 최소생성사다리 8개를 찾아서 출력한 결과 에서 보듯이 팔각형의 모양을 확인하였다.
- 연구자는 앞서 소개한 R&E 고등학생들을 지도하면서 별도로 최소생성사다리를 정점으로 하는 새로운 그래프의 생성에 주목하면서 그에 관련된 구조를 탐색하였다.
- 이 같은 방식을 적용하여 최소생성사다리를 정점으로 구성한 새로운 그래프에 대한 주요 속성을 에 제시하였다.
- 이 논문에서 연구자는 R&E 프로젝트에 참가하였던 고등학생들을 지도하면서 함께 사다리 게임에서 등장하는 최소생성사다리의 특징을 탐구하였던 기존 연구[6][10]를 토대로 최소생성사다리를 생성원(generator)으로 하는 새로운 그래프를 창출하였다[11].
- 필터링 알고리즘을 보완하는 과정에서 추상화(문제분석, 문제분해와 상호연결망 그래프의 트리 임베딩) 과정을 거쳐 최소생성 사다리를 모두 생성하는 그래프 탐색 알고리즘으로 발전되었다. 이 논문에서 제시하였던 알고리즘은 최초 발견한 최소생성사다리를 시작 정점으로 하여 Mathematica가 가진 Map 함수와 Make 함수를 사용하였다. 최초 생성된 최소생성사다리 중에서 전환사다리 연산을 사용할 수 있는 모든 경우를 따져서 연산자를 적용하여 얻은 YC그래프는 흥미롭게도 재귀적, 위계적인 구조를 보여 주었다.
- (4, 6) 사다리의 경우에 ‘010210’ 사다리에서 ‘101210’으로 수열을 치환하는 방법을 사용하여 8개의 최소생성사다리를 생성하는 그래프를 만들었다. 이를 확장하여 (5, 10) 사다리의 경우에 독립사다리연산을 이용하여 수열의 부분 수열을 치환하는 방식으로 최소생성사다리의 집합을 모두 구하였다.
- 참여 학생들은 사다리 게임을 통해 나타나는 순열의 결과를 C 프로그래밍으로 조사하면서 사다리 모양에서 나타나는 이산구조를 순열 자료구조로 다루고 순열을 치환하는 일대일 대응 알고리즘을 구현하여 그 결과를 순열과 시각적 모양으로 나타나도록 출력하였다[13]. 이 활동을 통하여 학생들은 사다리의 가로판 개수가 짝수이면 짝순열, 홀수 개이면 홀순열이 나온다는 사실을 알게 되었다.
- 일례로 3개의 세로판과 3개의 가로판을 가진 사다리의 경우 모두 8개의 사다리 모양을 얻게 된다. 참여 학생들은 이러한 결과를 직접 손으로 작성하여 알아내는 방법과 C 프로그래밍을 통해 이중으로 검토하였다.
- 여기서 연구자가 설계 및 구현한 알고리즘은 다음과 같다. 큐브 다면체를 시작 노드로부터 하위 자식(최소생성그래프)을 만들어 나가는 방식을 채택하였다. (4, 6) 사다리의 경우에 ‘010210’ 사다리에서 ‘101210’으로 수열을 치환하는 방법을 사용하여 8개의 최소생성사다리를 생성하는 그래프를 만들었다.
- 한편 (6, 15) YC그래프를 생성하기 위하여 트리 탐색을 이용한 병렬처리 알고리즘을 응용하여 Mathematica로 테스트 하였다. 그 결과 노드 및 간선을 생성하는 과정에서 메모리와 연산이 부하가 너무 많이 걸려서 큐브 다면체의 층별로 나누어서 간선의 개수를 구하는 별도의 서브루틴을 작성하여 결과를 얻게 되었다.
성능/효과
- 한편 (6, 15) YC그래프를 생성하기 위하여 트리 탐색을 이용한 병렬처리 알고리즘을 응용하여 Mathematica로 테스트 하였다. 그 결과 노드 및 간선을 생성하는 과정에서 메모리와 연산이 부하가 너무 많이 걸려서 큐브 다면체의 층별로 나누어서 간선의 개수를 구하는 별도의 서브루틴을 작성하여 결과를 얻게 되었다. (6, 15) YC그래프는 최소생성사다리 908개와 2128개의 간선을 가지고 있다.
- 두 가지의 탐구 프로젝트를 수행하면서 R&E 참여 학생들과 연구자는 컴퓨팅 사고력의 함양이 두드러지게 나타나는 공통점을 보여주었다.
- 연구자는 새로이 생성한 그래프의 구조를 탐색하면서 수와 그래프 구조에서 나타나는 수열의 대칭적 아름다움을 느꼈다. 또한 계산적 복잡도가 증가함에 따라 문제를 분해하여 접근하는 추상화 과정을 거쳐 그래프 탐색 알고리즘을 적용하여 응용하면서 수학과 이산구조의 접합점에서 컴퓨팅 사고력을 신장시키는 경험을 할 수 있었다. 이 프로젝트는 컴퓨팅 사고력에 기반하여 과학영재반 학생들의 사사 과정[12]뿐만 아니라 대학교의 이산구조 강좌에서 충분히 활용할 가치가 높은 콘텐츠 개발의 사례를 보여주었다.
- 실제 알고리즘 B를 구현한 Mathematics 프로그래밍으로 파일럿 테스트해 본 결과 16층의 구조를 가지면서 24218개의 노드를 가지는 것으로 나타났다. 그러나 층별 노드 수를 살펴본 결과 1층과 16층은 908개의 노드를 가지고 있으나 2층(1320개)과 15층(1340개)의 노드 수가 일치하지 않아서 간선 대칭 그래프일 것이라는 예측과 빗나갔다.
- 이 결과는 컴퓨팅 사고력을 수행하는 경우에 일반 학생이라도 컴퓨터 프로그래밍을 통하여 이처럼 어려운 과제에 도전할 가치가 충분히 있음을 시사하였다. 즉, 일반학생들도 이 논문에서 제시한 것처럼 사다리 게임 에 관련되는 순열의 개념에서 출발하여 조합적 사고[7]를 하면서 모든 순열을 생성하는 사다리의 집합을 구하고 그 중에서 역순열만 생성하는 사다리 모양만 걸러내는 필터링 알고리즘을 충분히 고안하고 코딩할 수 있다.
- 이 연구는 R&E 참여 학생들의 사례에서 살펴보았듯이 고등학생들이 팀을 이루어서 장기간에 걸쳐 순열과 조합, 통계적인 관점에서 사다리 그래프에 관한 이산적 구조와 수학적 탐구를 병행하면서 프로그래밍으로 알고리즘을 구현해 보는 화이트박스 기반의 학습의 장점을 보여주었다.
- 참여 학생들은 사다리 게임을 통해 나타나는 순열의 결과를 C 프로그래밍으로 조사하면서 사다리 모양에서 나타나는 이산구조를 순열 자료구조로 다루고 순열을 치환하는 일대일 대응 알고리즘을 구현하여 그 결과를 순열과 시각적 모양으로 나타나도록 출력하였다[13]. 이 활동을 통하여 학생들은 사다리의 가로판 개수가 짝수이면 짝순열, 홀수 개이면 홀순열이 나온다는 사실을 알게 되었다. 또한 가로판이 n개, 세로줄이 m개 일 때 사다리의 개수는 (n-1)m이다.
- 연구자는 62개의 정점을 가진 새로운 그래프의 구조에 주목하면서 (4, 6) 사다리의 최소생성사다리의 집합과 비교하는 작업을 수행하였다. 재귀적 패턴이 나타나는 것에 착안하여 Mathematica 프로그래밍으로 데이터 시각화와 알고리즘에 대한 추상화 작업을 하면서 탐구한 결과 최소생성 사다리를 정점으로 하는 새로운 그래프를 발견하여 YC그래프라는 이름을 붙였다. 연구자가 수행하였던 자료분석 및 표현, 추상화, 알고리즘의 설계, Mathematica 프로그래밍으로 구현, 테스트한 과정를 다음에 제시하면서 컴퓨팅 사고력에 관하여 탐구하고자 하였다.
- 최초 생성된 최소생성사다리 중에서 전환사다리 연산을 사용할 수 있는 모든 경우를 따져서 연산자를 적용하여 얻은 YC그래프는 흥미롭게도 재귀적, 위계적인 구조를 보여 주었다. 즉, YC그래프는 이전 차원의 그래프를 내포하는 재귀적 구조를 가지고 있었으며 그래프의 속성 중에서 간선대칭적인 특징 외에도 노드, 간선 수가 증가함에 따라 분지수와 지름도 증가하는 패턴을 보여주었다.
후속연구
- R&E 또는 영재반의 사사과정에 참가하지 않는 학생들이라도 그들이 과제에 집중할 수 있는 시간적인 여유와 차분함, 끈기, 수학적 사고력과 결합된 알고리즘적 사고, 즉 컴퓨팅 사고력을 통해 최소생성사다리처럼 이산 구조에 대한 속성을 충분히 탐구할 수 있을 거라고 판단된다.
- 다시 말하면, (n, k) 사다리 중에서 최초 발견한 최소생성사다리 중에서 ‘변환 대상’을 찾아서 독립사다리연산을 계속 적용함으로써 최소생성사다리의 집합을 모두 찾을 수 있었다.
- 그러나 층별 노드 수를 살펴본 결과 1층과 16층은 908개의 노드를 가지고 있으나 2층(1320개)과 15층(1340개)의 노드 수가 일치하지 않아서 간선 대칭 그래프일 것이라는 예측과 빗나갔다. 따라서 향후에 Mathematica 코드를 수정할 예정이며 이에 덧붙여 차원(세로판의 개수)이 증가할수록 YC그래프의 노드 및 간선의 개수를 결정하는 식을 도출하고 알고리즘에 대한 복잡도를 탐구할 예정이다.
- 이 연구는 R&E 참여 학생들의 사례에서 살펴보았듯이 고등학생들이 팀을 이루어서 장기간에 걸쳐 순열과 조합, 통계적인 관점에서 사다리 그래프에 관한 이산적 구조와 수학적 탐구를 병행하면서 프로그래밍으로 알고리즘을 구현해 보는 화이트박스 기반의 학습의 장점을 보여주었다. 이 연구에서 제시한 학습 콘텐츠는 과학영재교육원의 학생들이 사사과정을 수행하는 프로젝트 기반 학습에도 도입될 수 있으며 더 나아가 대학생들이 수강하는 이산구조 강좌에서 컴퓨팅 사고력을 증진하는데 기여 할 수 있는 프로젝트 기반 학습으로 활용될 수 있을 것이다.
- 후속적으로 (6, 15) YC그래프가 노드 대칭인지를 확인하는 작업 외에도 한 차원을 높인 (7, 21) YC그래프의 속성을 탐구할 예정이다. 이 새로운 그래프의 1층과 마지막 층은 908개의 노드가 배치될 것으로 확실하며 노드 대칭적 위계 구조를 가진 층 수는 아마도 약 908/62 보다 큰 자연수인 15 또는 17 등 소수일 가능성이 있다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.