속리산 프로젝트-최소비용신장트리

복잡한 형태의 문제를 단순화 시켜봅시다.

2016.03.28
동영상 설명

※ 개요

책이나 영화에서의 관계들은 처음에는 머리로 그려지지만, 나중에 복잡해지면 기억하기 어려운 정도로 복잡해집니다. 이런 복잡한 것을 단순화시킬 수 있는 방법은 없을까요? 복잡한 자료들을 핵심적인 부분만 표시해서 그들의 관계를 표시한 것이 그래프입니다. 그래프는 지하철 노선도와 같이 점과 선으로만 연결되어 점 간의 관계를 표현하는 표현형식입니다.

그래프는 순환구조가 있는 그래프와 순환구조가 없는 트리로 나눌 수 있습니다. 여기에서는 트리를 중심으로 살펴보도록 합니다. 수도, 도로, 가스, 전기, 인터넷망과 같이 기반 시설들을 어떻게 해야 전선이나 파이프와 같은 망(네트워크)을 최소의 비용으로 최대의 효과를 낼 수 있는지 1956년에 발표된 크루스칼 알고리즘으로 최소의 비용으로 그래프에서 트리를 찾는 최소비용신장트리(Minimal Spanning Tree) 알고리즘을 통해 살펴보도록 합니다.



※ 학습지도안 

 학습 목표

 1. 복잡한 형태의 문제를 그래프의 형태로 단순화시킬 수 있다.

 2. 최소비용신장트리 알고리즘을 이해하고 적용할 수 있다.

 학습 방법

 탐구학습

 소요 시간

 55분

 적정 연령

 13세 이상

 관련 CT

 자료 표현, 알고리즘과 절차

 학습 준비물

 선생님:  활동지, 프레젠테이션 자료

 학생: 활동지, 필기도구


영상 목록

CS 언플러그드 로고 CS 언플러그드

컴퓨터 없이 몸을 움직이며 놀이를 통해 컴퓨터 과학 원리를 배워보세요~~

연관 동영상