Plan-recognition with template matching shows reasonable performance for recognizing general control structures. However, problems containing a well-defined algorithm such as sorting and searching are difficult to recognize by just the plan recognition methodology alone, because an algorithm is often highly optimized and therefore hard to divide into smaller meaningful units. Based on this observation, we propose an algorithm recognition methodology to augment the plan-recognition approach.
Our algorithm recognition approach is based on the flow graph parsing which performs a partial recognition of functions. The methodology is extended to completely understanding algorithm implementation by providing the information of the program's goal, which is available as a specification of programming assignment in our tutoring environment. Our effort for utilizing goal information is focused on two aspects; extending the role of transformation rules to represent algorithm-dependent information and looking for salient graph parts for an algorithm plan to determine which plan has been used to implement the goal. Transformation rules represent an alternative viewpoint of a subgraph. If an interpretation of a graph is suspended, alternative interpretation is tried on the transformed graph from different viewpoint. Identification of the algorithm plan in an implementation is performed by finding a discernible subgraph, clue, that uniquely determines which has been used among those plans for the algorithm goal.
Preliminary evaluation was performed on 72 programs of C programming language containing sort algorithm, which were submitted by freshmen of C programming language course at KAIST. 55 program were recognized completely. Excluding 8 extraordinary programs, our methodology showed high recognition rate (55/64).
형판정합(template matching)을 사용한 프로그래밍 플랜 인식은 일반적인 제어 구조를 인식하는데 좋은 성능을 보인다. 그러나 정렬이나 탐색 등과 같은 알고리즘은 대개 구조가 최적화되어 있어서 작은 단위의 의미있는 플랜으로 나누기 어렵기때문에 이런 알고리즘을 포함하는 프로그램은 플랜인식 방법만으로는 인식하기가 어렵다. 이런 사실에 근거하여 이 논문에서는 플랜인식 방법을 확장하기위한 알고리즘인식 방법을 제안한다.
제안하는 알고리즘인식 방법은 프로그램에 대한 부분적 인식이 가능한 플로우그래프(flow graph) 파싱을 이용한다. 프로그래밍 교육의 경우에 숙제로 제출된 문제에서 알아낼 수 있는 프로그램의 목적에 관한 정보를 제공함으로써 구현된 알고리즘을 부분적이 아니고 완전히 인식할 수 있도록 이 방법론을 확장하였다. 목적에 관한 정보는 두가지 측면에서 활용된다. 첫째로 그래프 변환규칙(graph transformation rule)의 역할을 확대하여 알고리즘에 의존적인 정보를 표현하도록 하며, 둘째, 목적으로 주어진 알고리즘을 구현하기 위해 어떤 알고리즘이 사용되었는가를 알아내기 위해 각 알고리즘플랜에 고유한 그래프 노드를 찾아낸다.
그래프 변환규칙은 하나의 그래프를 해석하는 각기 다른 관점을 표현한다. 어느 그래프의 해석이 중단되면 다른 관점에서 다른 해석을 시도한다. 알고리즘플랜은 알고리즘 단서(clue)라는 노드를 파싱과정중에 계속 확인하여 찾아낸다. 이 단서노드는 주어진 알고리즘 목적을 실현할 수 있는 여러 플랜중에 하나의 플랜에만 유일하게 나타나는 노드로 정의된다.
정렬이 요구되는 C 프로그램에 이 방법론을 적용한 결과 72개의 프로그램중에 55개 의 프로그램이 성공적으로 인식되었다. 알고리즘 플랜에 정의되지 않은 독창적인 방법으로 구현한 8개의 프로그램을 제외하면 플랜이 정의된 경우는 86%(55/64)의 높은 인식률을 보이며 이 중 오류를 포함한 14개의 프로그램도 인식이 성공하여 오류가 검색되었다.
