MAX-SAT 기법을 이용하여 프로그래밍 과제의 피드백을 자동으로 생성하는 방법

Abstract

오늘날 널리 퍼지고 있는 소프트웨어 교육에서 많은 수의 학생에게 도움이 되는 피드백을 주는 것은 어려운 문제이다. 이를 해결하기 위해 본 논문은 입문용 프로 그래밍 과제에서 학생이 제출한 코드의 틀린 곳을 자동으로 짚어 주는 효율적인 방법을 제안한다. 이 방법은 크게 두 단계로 구성된다: (i) 제출된 코드의 실행 흐름 을 나타내는 논리식을 생성하고

(ii) MAX-SAT solver를 이용하여, 올바른 결과를 내기 위해 수정해야 하는 최소한의 프로그램 지점을 찾는다. (i) 에서 생성된 논리 식은 코드의 틀린 실행 의미를 그대로 유지하면서, 과제의 입출력 제약을 반드시 만족하는 논리식이다. 따라서, 틀린 실행 의미의 일부를 바꿔야만 전체 논리식이 참이 될 수 있다. MAX-SAT solver는 전체 논리식이 참이 되기 위해 수정해야 하는 최소한의 논리식을 찾을 수 있고 이로부터 잠재적인 오류 지점을 찾을 수 있다. 이 방법의 실효성을 보이기 위해 Python 프로그램을 입력으로 받는 자동 피드백 생성기 H ONEY B EE 를 설계 및 구현하였다. 구현한 피드백 생성기 평가를 위해 5 종류의 과제에 대해 오류 지점이 있는 43개의 코드(평균 37줄)에 대해 실험한 결과 평균 0.3초 만에 40개의 틀린 코드에서 피드백을 생성하였고, 1천 줄의 큰 코드에 대해서도 89.8초 만에 피드백을 생성하였다.