통신망 구축 – 스타이너 트리

가장 짧은 경로를 그리는 방법을 알아봅시다.

2016.10.18
동영상 설명

※ 개요

전 세계는 인터넷으로 연결되어 있습니다. 예를 들어 한국과 미국은 인터넷으로 연결되어 있습니다. 다만 먼 거리를 연결하는 광케이블은 가격이 비싸고 한국과 미국은 거리가 아주 멀기 때문에 인터넷 선로를 연결하는 비용이 많이 듭니다. 다행히도 한국과 일본도 인터넷이 연결되어 있고, 거리가 가깝기 때문에 미국과 연결하는 인터넷 선로를 공통으로 사용할 수 있습니다.

이렇게 여러 나라를 인터넷으로 연결하는 데 가장 짧은 인터넷 선로를 이용해서 모든 나라를 연결하기 위해서는 스타이너 트리라는 알고리즘을 이용할 수 있습니다.


※ 학습지도안 

 학습 목표

 1. 스타이너 점을 이용하여 점 3개와 점 4개를 연결하는 가장 짧은 경로를 그릴 수 있다.

 2. 스타이너 점을 이용하여 여러 점을 연결하는 가장 짧은 경로를 그릴 수 있다.

 학습 방법

 게임

 소요 시간

 60분

 적정 연령

 13세 이상

 관련 CT

 자료 분석, 알고리즘과 절차

 학습 준비물

 선생님: 세계지도

 학생: 연필, 지우개, 가위, 자


영상 목록

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

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

연관 동영상