전기차 충전소 설치–지배집합

최적화 문제를 해결하는 다양한 방법을 알아봅시다.

2016.10.04
동영상 설명

※ 개요

실생활의 많은 상황은 네트워크 형태나 혹은 다양한 종류의 그래프로 추상화될 수 있습니다. 네크워크는 실생활에 유용한 알고리즘 개발을 위한 많은 기회를 제공하고 보다 효율적인 방법을 고민하게 합니다. 이번 주제에서는 집들을 연결한 마을 지도 그래프에서 주요정점(노드)을 몇 개 표시해서 다른 모든 정점이 각 주요정점들과 한 구간 떨어지게 만드는 것입니다.

다시 말해 지배집합을 만들고 최소지배집합을 이루는 주요정점을 찾아 최소한의 자원으로 최대의 효과를 내는 방법을 구안하게 됩니다. 최소지배집합 문제로 가까운 미래에 실현될 전기차 충전소 설치 문제를 가정하여 그 해결방법을 경험해 보고 최적의 알고리즘을 찾아보는 활동입니다. 하지만 최소 지배 집합을 찾는 알고리즘이 컴퓨터로 해결 가능한 시간동안에 해결하는 방법이 존재하는지 아직 증명하지 못하고 있습니다. 그래서 이런 문제들을 지금은 근사알고리즘 즉, 가장 최적화되는 해결방법은 아니지만 비교적 빠른 시간에, 어느 정도 보장된 해결방법이 되는 알고리즘을 적용하여 풀어야 하는 것입니다. 이와 같은 현재 미결 과제들은 학생들에게 ‘컴퓨터 과학’이 아직 미완성의 세계임을 인식하게 하고 ‘컴퓨터 과학’에 몰입하는 계기가 될 것입니다.


※ 학습지도안 

 학습 목표

 1. 최적화 문제를 해결하는 다양한 방법이 있음을 알 수 있다.

 2. 최적화 문제를 다양한 방법으로 해결할 수 있다.

 학습 방법

 문제해결학습, 협동학습

 소요 시간

 60분

 적정 연령

 13세 이상

 관련 CT

 자료 분석, 시뮬레이션, 추상화

 학습 준비물

 선생님: 원형 도화지, 컬러콘(小) 26개, 컬러콘(大) 26개, 색 테이프

 학생: 색연필


영상 목록

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

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

연관 동영상