[논문]정보영재학생과 일반학생의 최단경로 탐색 과정 분석

강성웅; 김갑수

doi:10.14352/jkaie.2016.20.3.243

정보영재학생과 일반학생의 최단경로 탐색 과정 분석
An Analysis on Shortest Path Search Process of Gifted Student and Normal Student in Information 원문보기

정보교육학회논문지 = Journal of the Korean Association of Information Education, v.20 no.3, 2016년, pp.243 - 254

초록
AI-Helper

본 연구는 PISA 2012 문제해결력 평가 문항 중 이산수학의 그래프 이론이 적용된 'TRAFFIC' 문항을 바탕으로 총 19문항의 최단경로 탐색 검사 도구를 제작했고, 웹기반 컴퓨터 평가로 정보영재학생과 일반학생을 대상으로 실시했다. 컴퓨터는 일상의 문제를 해결하는 과정에서 없어서는 안 될 중요한 기기이자 평가의 기반이 되는 매체로 자리 잡았고, 정보영재학생은 컴퓨터를 통해 문제를 해결할 수 있어야 하고, 컴퓨터가 절차를 수행할 수 있는 분명한 명령을 내려줄 수 있어야 한다. 또한, 컴퓨팅 사고가 어느 분야든 영향을 미치는 시대이기 때문에 학생들에게 새로운 교육적 자극을 줘야 한다. 최단경로 탐색 과정을 통해 문제해결에 걸린 시간과 정답률 간의 상관관계를 찾을 수 있었고, 노드와 엣지의 증가로 문항의 곤란도가 높아짐에 따라 노드가 문제해결에 영향을 크게 미치는 것을 찾을 수 있었다. 또한, 정보영재학생의 문제해결 과정에서 알고리즘적 사고 과정을 볼 수 있었고, 정보영재학생의 인지적 특성인 '효율화 능력'과 '정보구조 기억력'을 확인할 수 있었다.

Abstract ▼ AI-Helper

This study has produced a checker of the shortest path search problem with a total of 19 questions as a web-based computer evaluation based on the 'TRAFFIC' questions of PISA 2012. It is because the computer has been settled as an indispensable and significant instrument in the process of solving the problems of everyday life and as a media that is underlying in assessment. Therefore, information gifted students should be able to solve the problem using the computer and give clear enough commands to the computer so that it can perform the procedure. In addition, since it is the age that the computational thinking is affecting every sectors, it should give students new educational stimuli. The relationship between the rate of correct answers and the time took to solve the problem through the shortest route search process showed a significant correlation the variable that affected the problem solving as the difficulty of the question rises due to the increase of nodes and edges turned out to be the node than the edge. It was revealed that information gifted students went through algorithmic thinking in the process of solving the shortest route search problem. And It could be confirmed cognitive characteristics of the information gifted students such as 'ability streamlining' and 'information structure memory'.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

따라서 정보영재에게 알고리즘 학습은 프로그래밍을 하기 위해 문제를 해결해 가는 절차나 방법을 논리적으로 탐구함으로써, 문제해결력을 신장시킬 수 있기 때문에 반드시 필요한 학습과정이라 할 수 있다. 본 연구에서는 여러 알고리즘 중에서도 이산수학의 그래프 이론을 활용한 최단거리 탐색 알고리즘을 통해 정보영재학생의 인지적 특성을 찾아보고자 한다.
최단경로 탐색 문제는 각 노드와 연결된 노드들, 노드와 노드 사이의 엣지들의 탐색할 경로를 나눠서 순서를 정하고 예측해서 실행하는 일련의 과정 즉, 알고리즘적 과정을 얼마나 정확하고 빠르게 해결하는지의 문제이다. 최단경로 탐색 문제를 통해 알 수 있는 정보영재의 인지적 특성을 찾아보고자 한다.

가설 설정

둘째, 엣지(edge)의 길이와 가중치인 이동 시간은 비례하지 않는다. 즉, 실제 겪을 수 있는 교통 상황을 반영해 도로의 길이가 길고 짧음에 따라 이동에 걸린 시간도 비례하지 않는다는 것이다.
셋째, 이동 했던 길로 되돌아 올 수 없다. 최종 이동시간이 늘어나기 때문이다.

제안 방법

5가지 노드에 각각 4가지 엣지가 산출되기 때문에 총 20문항이 가능하지만 5노드 10엣지의 경우 평면그래프의 변이 서로 교차하지 않아야 하는 조건과 맞지 않아 제외해서 총 19문항을 채택했다.
PISA 2012 문제해결력 평가 ‘TRAFFIC’ 문제를 바탕으로 최단경로 탐색 검사 문항을 제작했고, 완성된 검사 도구는 http://kangteus.cafe24.com/에 탑재하여 ‘크롬’ 웹브라우저를 통해 실시했다.
넷째, 문제해결에 대한 집중도를 높이고, 새로운 변수에 대한 대응을 알아보기 위해 19문항 중 3문항의 도착지를 변경했다. 출발점과 도착지의 표시는 빨간색으로 쉽게 눈에 띄게 제작했다.
또한 영재학생이 일반학생 보다 문제해결 시간이 왜 오래 걸리는지, 어디에서 차이가 나는지를 더 면밀히 분석하기 위해 정답인 문제만을 가지고 분석을 하였다.
문제해결시간이 한 없이 오래 걸린다고 해서 정답률이 100%에 근접하지는 않는다. 문제해결시간과 정답률과의 관계를 구체적으로 알아보기 위해 영재학생과 일반학생 각각의 문제해결 시간대별 정답률 분포표를 만들어 분석했다. 영재학생과 일반학생의 정답률, 문제해결시간의 평균과 표준편차를 바탕으로 범위를 정했다.
문항의 설계는 다음과 같이 6가지의 규칙을 적용해서 웹기반으로 제작을 하였고, 연구 대상이 컴퓨터를 통해 최단경로 탐색 과정을 수행하였다.
본 연구는 PISA 2012문제해결력 평가 문항 중 ‘TRAFFIC’ 문항을 그래프 이론을 적용해 총 19문항의 최단경로 탐색문제를 만들었고, 이를 영재학생과 일반학생에 적용한 연구결론은 다음과 같다.
본 연구의 바탕이된 PISA 2012 문제해결력 역시 최단경로를 찾는 지도 그림을 제시하고, 새롭게 접한 정보를 구조화한 형태로 기억하고 그 기억을 바탕으로 문제를 해결 할 수 있게 구성하였다.
선다형 문항 대신 수행형 문항으로 제작하였고, PISA TRAFFIC 문제와 마찬가지로 엣지를 클릭하면 형광색으로 표시가 되고 ‘총 소요 시간’에 엣지들의 합이 계산이 되어 표시가 된다.
여섯째, [Table 3]과 같이 규칙을 적용해 노드와 변의 산출을 바탕으로 총 19문항을 구성하였다. 노드의 수는 5부터 13까지 노드가 2씩 증가해 총 5가지 노드를 바탕으로, 엣지의 수는 노드의 수(N)에 각각 1.
문제해결시간과 정답률과의 관계를 구체적으로 알아보기 위해 영재학생과 일반학생 각각의 문제해결 시간대별 정답률 분포표를 만들어 분석했다. 영재학생과 일반학생의 정답률, 문제해결시간의 평균과 표준편차를 바탕으로 범위를 정했다.
첫째, PISA 2012 ‘TRAFFIC’ 문항은 4지선다형의 문제였으나 운에 의한 정답을 배제하기 위해 제작한 19문항 모두 수행형 문항으로 검사 도구를 설계 했다.

대상 데이터

따라서 영재학생 39명, 일반학생 92명, 총 131명을 대상으로 진행하였다.
본 연구에서 정보영재학생 41명은 서울교육대학교 과학영재교육원 5, 6학년 학생과 서울강서교육지원청 영재교육원 6학년 학생을 대상으로 하였고, 일반학생 94명은 서울, 경기지역 5, 6학년 학생을 대상으로 실시하였다.
영재학생과 일반학생 모두인 131명을 대상으로 문제해결시간과 정답률 간의 상관관계를 분석했다. 문제해결시간과 정답률은 유의수준 p<.

데이터처리

다만, 문제해결시간과 정답률이 정확히 비례하지는 않는 점을 ‘4.1.3 문제해결 시간대별 정답률 분포’에서 분석해 보았다.

성능/효과

둘째, 영재학생이 일반학생에 비해 전체 정답률이 높았고, 노드가 증가할수록 정답률도 높았다. 다만 엣지 수의 증가에 따른 유의미한 차이는 없었다.
따라서 이번 연구에서는 Renzulli가 영재의 특성으로 제시한 ‘과제 집착력’도 발견할 수 있었다[14].
따라서 정보영재는 8엣지, 9엣지로 갈수록 정답률이 증가했고, 일반학생에 비해 8엣지에서는 정답률이 18%나 높았다.
또한, 새로운 문제를 접했을 때 정보영재학생은 집중력 있게 문제를 상세히 파악했으며 이는 Renzulli가 제안한 영재의 특성 중 ‘과제집착력’을 발견할 수 있었고, 정보영재학생의 인지적 특성인 ‘효율화 능력’과 ‘정보 구조 기억력’을 실제 사례를 통해 확인할 수 있었다.
또한, 영재학생의 평균 문제해결시간은 546.8초로 측정되었고, 일반학생의 평균 문제해결시간은 428.6초로 측정되었다.
셋째, 각 엣지의 가중치(이동 시간)는 2∼10 사이의 수가 랜덤으로 나타나게 프로그램화 했다.
셋째, 최단경로 탐색 과정을 통해 정보영재의 인지적 특성인 ‘효율화 능력’과 ‘정보 구조 기억력’을 확인할 수 있었다.
이를 통해 최단경로 문제를 해결하는 데는 엣지보다 노드가 더 많은 영향을 미치는 것을 알 수 있었다.
이번 최단경로 탐색 문제를 통해 문제해결시간과 정답률 간에는 일정한 상관관계가 있으나, 정답률이 높은 상황에서는 크게 작용을 하지 않음을 알 수 있었다.
정답률이 75% 이상인 학생들의 각 노드의 첫 번째 문항에서 문제해결에 걸린 시간을 분석한 결과, 영재학생이 일반학생 보다 문제해결에 걸린 시간이 짧았고 정답률 또한 높았다.
첫째, 노드 13에서 영재학생과 일반학생의 문제해결 시간과 정답률의 차이가 명확하게 드러났다.
첫째, 최단경로 탐색 과정에서 문제해결시간과 정답률은 일정시간 까지는 상관관계를 보인다. 즉, 시간이 증가할수록 정답률도 높아진다.

후속연구

난이도가 낮은 노드 5를 제외하고 노드 13이상으로 문제를 확장한다면 더 명확한 자료를 얻을 수 있을 것이다.
둘째, 검사 문항이 웹기반으로 제작되었고, 엣지의 가중치가 랜덤으로 주어지기 때문에 그래프 이론 수업을 하면서 사전, 사후 검사를 한다면 학습 전과 후의 유의미한 결과도 얻을 수 있을 것이다.
셋째, 영재학생의 선발 과정이나 수업, 평가 등의 과정에서도 다양한 컴퓨터 기반 프로그램과 어플리케이션을 개발하고 활용해야 한다면 영재교육 발전에 큰 밑거름이 될 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	평면그래프란?	그래프 G=(V, E)에서 모든 연결선 e ∈ E가 방향을 가진 그래프를 방향 그래프(directed graph)라고 한다. 변이 서로 교차하지 않도록 그래프 G를 평면에 그릴 수 있으면 G를 평면그래프(planar graph)라고 한다. 변e에 지정된 실수를 변e의 가중치(weight)라 하고, 각 변에 가중치가 주어진 그래프를 가중그래프(weighted graph)라고 한다.
	최단경로란?	가중 그래프에서 꼭짓점 u와 꼭짓점 v를 연결하는 경로에 있는 모든 변의 가중치를 합한 값을 경로의 길이(length)라 하고, u와 v를 연결하는 경로 중에서 경로의 길이가 가장 짧은 경로를 u와 v를 연결하는 최단경로(shortest path)라 한다.
	다익스트라 알고리즘의 과정은?	① 초기조건으로 출발점 A는 0으로, 다른 노드들은 ∞로 초기화 한다. ② 출발점 A에서 인접 노드에 이르는 가중치를 계산하고 이 값들을 임시 저장한다. ③ 계산되어 있는 노드 중 가중치의 값이 가장 적은 노드에서부터 인접 노드까지의 거리를 계산해서 임시 저장한다. ④ 노드B 다음으로 최단경로인 노드D에서 다시 인접 노드까지의 가중치를 계산하고 임시 저장한다. ⑤ 가장 짧은 최단경로에서 다시 같은 과정을 반복한다. ⑥ 최종적으로 가중치의 합이 18로 가장 낮은 값의 경로인 A → D → E → H → F가 최단경로가 된다.

참고문헌 (15)

Cho, Sungjin., Kim, Handu (2013). Combinatorics and Graph theory. p.520, kyungmoonsa.
Choi, Jeongwon., Lee, Eunkyoung., Lee, Youngjun (2013). Analysis of UK Computing textbooks for Elementary School Informatics Education. The Korean Association of Computer Education, 17(1), 19-22.
Euler, Leonhard. Solutio Problematis ad Geometriam Situs Pertinentis, Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 128-140, 1741.
Jun, Woochun (2011). A Study on Correlation Analysis of Programming Ability and Logical Thinking Ability for the Gifted Children in IT. Journal of Gifted/Talented Education, 21(3), 761-772.

원문보기 상세보기
Kim, Kapsu (2013). A Study on Cognitive Characteristics of Information Gifted Children. Journal of The Korean Association of information Education, 17(2), 191-198.
Kim, Kapsu (2010). A Study on Programming Language Instruction Strategies of Improving the creative and logical thinking for Elementary Students. Journal of The Korean Association of information Education, 8(2), 63-70.
Lee, Jaeho., Lee, Jaesu (2006). A Study on the Development of the Selective Test Item for the Gifted of Elementary Information Science. Journal of Gifted/Talented Education, 16(1), 81-100.
Lee, Jaeho., Oh, Hyeonjong (2009). Design and Validation of Education Contents of Algorithm for the Gifted Elementary Students of Computer Science. Journal of Gifted/Talented Education, 19(2), 353-380.
Lee, Juhee., Kim, Kapsu (2006). A Study on Teaching and Learning in Sort-Algorithm for Concrete Operational Stage Students. Journal of The Korean Association of information Education, 11(2), 95-100.
Lee, Wookey., Park, Soonhyong (2014). Graph and Social Network. Korean Institute of Information Scientists and Engineers, 32(1), 33-43.
M. Wing, Jeannette (2008). Computational thinking and thinking about computing. Philosophical transactions of the royal society, 366(1881), 3717-3725.

상세보기
Moon, Gyosik (2007). On the Direction of the Computer Algorithm Education Based on Conceptual Algorithms. Journal of The Korean Association of information Education, 11(1), 29-38.
OECD (2014). PISA 2012 Results: Creative Problem Solving. Vol.V, Paris: OECD.
Renzulli, J. S. (1978). What makes giftedness? Reexamining a definition. Phi Delta Kappan, 60(3), 180-184.
Salomon, G. (1987). Transfer of Cognitive Skills from Programming: When and How? Journal of Educational Computing Research, 3, 149-169.

상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증