홈으로 센터소개 센터소개 IC-PBL Connect & Share 교수지원 학습지원 IC-PBL Connect & Share IC-PBL 소개 IC-PBL Connect & Share IC-PBL 명예의 전당 IC-PBL 통계 IC-PBL 자료실 IC-PBL Share IC-PBL Connect IC-PBL Share IC-PBL Share IC-PBL Share는 한양대학교에서 이루어진 다양한 학부와 대학원 IC-PBL 수업 과정 및 결과를 공유하는 공간입니다. (비로그인 회원에게는 일부정보가 제한되어 표기됩니다.) ※ 2022학년도 첨부파일만 제공되니 전년도 자료가 필요하신 분들은 IC-PBL교수학습센터로 메일 주시기 바랍니다. 기본정보 입력 [학부] 수학캡스톤PBL(그래프알고리즘의응용) 권오정23.01.31조회 34 계열 인문사회계열 학부/대학원 학부 전공 수학과 학년도 2022 학기 2학기 과목명 수학캡스톤PBL(그래프알고리즘의응용) 담당교수 권오정 소속 자연과학대학 수학과 IC-PBL 유형 M(현장통합형) 문제제시·기업 평가·기업 E(현장평가형) 문제제시·교수자 평가·기업 C(문제해결형) 문제제시·교수자 평가·교수자 ○ A(현장문제형) 문제제시·기업 평가·교수자 보고서 내용 수업목표 그래프(네트워크)에서 나타나는 최적화 문제들 중에 실생활에서 유용하게 사용되는 최단거리 문제, 최대 수송 문제, 최대매칭 문제 등과 이들의 변형을 학생들이 파이썬으로 코딩하고 해결할 수 있도록 한다. 이 때 알고리즘이 원하는 문제를 잘 해결한다는 것을 수학적으로 증명할 수 있도록 한다. 이를 통해 IT 기업 등에 취업 시 알고리즘 문제를 해결하는 데 필요한 능력을 기르고자 한다. 대표적인 문제들 중에서 세부 주제를 선택하여 한 학기동안 탐구하고 그 결과를 발표하는 것을 목표로 한다. 결과물은 결과보고서, 발표자료 등으로 한다. 추가적으로 관심이 있는 학생은 논문을 연결시켜주어 어떠한 관련연구들이 있는 지 알려주고자 한다. 처음 몇 주 동안은 파이썬의 기본적인 사용에 대해 다루어 파이썬을 사용해 보지 않은 학생들도 수업을 들을 수 있게 할 예정이고, 그래프 기본 알고리즘, 분할 정복, 다이나믹 프로그래밍 등에 대해 강의를 진행할 예정이다. IC-PBL 수업 문제 1) 최대수송 문제(Maximum flow problem)는 물류수송에 대한 네트워크 정보가 있고, 각 경로 별로 최대로 수송할 수 있는 수용량이 제시되어 있을 때 원하는 지점까지 최적으로 보내는 방법을 알아본다. 현실에서 여러 가지 제약조건이 있을 때 어떻게 변형하여 문제를 해결할 수 있는 지 탐구해 본다. 2) 최대매칭 문제(Maximum matching problem)는 두 집합 사이에서 한 집합이 다른 집합으로 선호도 등이 있을 때 선호를 최대한 충족시키면서 매칭을 시키는 방법을 찾는 문제이다. 이전에 사용한 정보 등 을 이용하여 볼 영화를 추천해주는 추천 알고리즘 등은 대표적인 매칭 문제로 그래프의 문제로 표현할 수 있다. 여러 가지 선호도 등이 표현되어 있을 때 어떻게 문제를 해결할 수 있는 지 탐구해 본다. 3) 최소 피드백 셋 문제(Minimum feedback vertex set)는 주어진 그래프에서 순환 구조가 생기지 않 게 하기 위해 최소한의 점을 지우는 방법을 찾는 문제이다. 이러한 문제는 네트워크 상에서 바이러스 등 이 퍼지고 있을 때 효율적인 방법으로 방어하기 위한 방법을 제시해 준다. 여러 가지 제약 조건이 주어져 있을 때 문제를 해결할 수 있는 방법을 탐구해 본다. 4) 스타이너 셋 문제 (Steiner set problem) 주어진 그래프에 몇 개의 점이 주어져 있을 때 이를 연결하는 최소의 연결 부분그래프를 찾는 문제이다. 이는 도시에서 전력공급선 연결 등의 문제를 풀 때 유용하게 사용될 수 있다. 이 문제를 어떻게 해결할 수 있는 지 탐구해 본다. 리스트수정삭제 top