인천대학교 과학영재교육원

Incheon Science Elite Program

Tel: 032-835-4971~2, Fax: 032-835-4976

화학교실

인천과학영재교육센터

중등 사사과정 지도 개요
제 목	빠르게 짝짓기를 하는 알고리즘 고안하기
지도교수	성 명	권오정	직 위	조교수
	소 속	수학과	전 공	수학
탐구분야	이산수학과 알고리즘		학년도	2021학년도
탐구 개요
1. 탐구 필요성 두 집단 사이에 원하는 관계를 분석하는 경우가 많다. 가령 학생들이 선호하는 기숙사에 신청을 한다거나, 학생들이 상담하고 싶은 선정하는 경우 등이다. 이 경우에 최대한 많은 학생들이 원하는 대로 되기 위해서는 어떤 조건이 필요하고 그런 경우를 만족하는 사항을 찾아내는 것은 수학의 중요한 문제이다. 이를 해결하는 알고리즘을 고안해 보고자 한다.
2. 탐구 목적 두 집단 사이에 원하는 관계를 선으로 표현한 그래프를 통하여 최대한 만족도가 높은 쌍들을 찾아내는 매칭을 찾아내고자 한다.
3. 탐구 내용 Python의 기본을 익히고 그래프 매칭 알고리즘을 구현해보도록 한다. 아주 큰 그래프에서도 구현을 해 보고, 변형된 형태의 그래프에서 매칭 알고리즘을 구현해보는 것을 목표로 한다.
4. 탐구 방법 그래프와 매칭에 대해 기본적인 내용들을 학습한 후, 알려져 있는 매칭에 대한 알고리즘을 구현해 본다. 부가적은 조건들이 결합된 경우 이런 알고리즘이 잘 알려져 있지 않은 경우들이 많은데, 이에 대해 새롭게 탐구해보고자 한다.
5. 기대 효과 그래프의 매칭 알고리즘은 현대 산업수학에서 기본이 되는 알고리즘이다. 이를 구현하고 발전시켜봄을 통해 수학의 새로운 즐거움을 깨달을 수 있을 것으로 기대한다.