조합론 프로젝트
"Java
와 Mathematica
를 이용한 조합론 알고리즘의 구현"
성균관대학교 수학과
4학년 1992312068번 유병혁
한 학기동안 조합론을 배우면서 느낀 결론은, 조합론은 현실세계를 수학적으로 모델링하기에 좋은 학문이라는 것이었습니다. 하지만, 현실세계의
복잡성으로 인하여 그것을 성공적으로 모델링하였다고 하더라도 모델링한 식을 손으로 계산한다는 것은 거의 불가능한 일임을 알게 되었습니다.
기존의 수학 프로그래밍은 C 나 PASCAL, 그리고 FORTRAN 등을 이용한 것이었으나, 이것은 프로그래밍에 소요되는 시간이 길고,
모델링된 내용을 화면에 시각적으로 나타내기에는 불편한 점이 많았습니다. 또한 현재는 인터넷의 World Wide Web(이하 웹) 환경을
이용한 정보의 공유가 주가 되는데, 기존의 프로그래밍 언어는 결과를 공유하기에 불편한 점이 많았습니다.
그런 이유로 수학적인 모델링을 컴퓨터를 이용해 빠르게 시각화하고 결과값을 구해낼 수 있는 메쏘드를 찾던 중, 서로 성격이 다른 도구지만,
Java 와 Mathematica 가 그것에 적합하다는 결론에 이르게 되었습니다. 그래서 저의 프로젝트에서는 Java 와 Mathematica
라는 도구를 소개하고, 그것을 가지고 조합론의 문제들을 실제적으로 구현 / 풀어내는 과정을 발표하기로 하였습니다. 이 프로젝트는 향후
수학 프로그래밍을 하려는 사람들을 위한 가이드가 될 수 있으리라 생각합니다.
저의 프로젝트는 다음과 같은 구조로 이루어져있습니다.
- Java & Mathematica 에 대한 소개
- Java Applet 을 이용한 구현
- Mathematica 을 이용한 구현
- 활용 예
1. Java & Mathematica 에 대한 소개.
1.1 Java
Java 는 Sun Microsystems에서 개발, 현재 무료로 배포하고
있는 프로그래밍 언어로써 1999년 11월 현재 버젼 1.2 까지 배포되어 있는 상태입니다. Sun Microsystems 의 웹사이트
http://www.javasoft.com 에서 자바개발자 키트(JDK:
Java Developement Kit) 전체를 인터넷에서 다운 받을 수 있습니다. 이 사이트는 윈도우즈 95/98, 윈도우즈 NT,
솔라리스 및 매킨토시에 대한 JDK 버젼을 제공합니다.
( Microsoft 의 Java 개발 도구, Visual J++ 의 화면 예 )
Java 는 C 나 PASCAL 과는 달리 객체지향적인 개념을 내포하고 있으며, 여러 특징을 가지고 있는데, 특히 Java 는 Java
Applet 을 제작할 수 있는 기능을 가진다는 점에 주목할만 합니다. 이것은 자신이 제작한 프로그램을 별도의 저장과 컴파일 과정 필요없이
넷스케이프나 인터넷 익스플로러 등의 웹 브라우저에서 바로 실행할 수 있도록 하는 특징입니다..
Java 에 대한 더 많은 정보는, Sun社의 Java 홈페이지(http://java.sun.com)에서
찾을 수 있습니다.
1.2. Mathematica
Mathematica 는 Wolfram Research에서 개발,
현재 버젼 4.0 까지 출시되어 있습니다. Mathematica 는 방대한 양의 수학 패키지를 보유하고 있으며 특히 그래픽과 수학식
표현에 필요한 함수들을 많이 포함하고 있기 때문에 수학적인 모델링을 쉽게 시각화 할 수 있는 도구입니다.
( Mathematica 의 화면 예 )
Mathematica 를 이용하면 특정한 함수를 제공하는 패키지를 만들 수 있으며 그것을 사용하여 작업의 생산성을 높일 수 있습니다.
Mathematica 에 대한 더 많은 정보는, Wolfram Research의 홈페이지(http://www.wolfram.com)에서
얻을 수 있습니다.
2. Java Applet 을 이용한 구현
Java Applet 을 이용하여 (수학) 프로그램을 제작 하는 것은 다음의 단계를 거칩니다.
- 알고리즘 분석
- 소스코드 작성
- 컴파일 / 디버깅
- 바이트코드 작성
- 웹 문서와 연결
- 웹 문서 내에서 실행
다음은 주어진 수의 Factorial을 표시하는 Java Applet 의 코드와 실제 Applet 입니다.
(※ 위 Applet 은 주어진 숫자가 21 이상일때 factorial 값이 Java 의 정수표현 한계보다 커지기 때문에 제대로 작동하지
않습니다. )
위 Applet 을 구성하는 Source Code 는 다음과 같습니다.
import java.awt.*;
import java.applet.*;
import java.awt.event.*;
/**
* 이 Applet은 사용자로부터 하나의 자연수를 받아서, 그것에 해당하는
* Factorial 값을 리턴합니다.
*/
public class Factorial extends Applet implements ActionListener {
Label numLabel, resultLabel;
TextField num, result;
public void init()
{
numLabel = new Label("숫자를 입력하고 Enter를 누르세요");
num = new TextField( 10 );
num.addActionListener( this );
resultLabel = new Label("Factrial 값 : ");
result = new TextField( 20 );
result.setEditable( false );
add( numLabel );
add( num );
add( resultLabel );
add( result );
}
public void actionPerformed( ActionEvent e )
{
long number, factorialValue;
number = Long.parseLong( num.getText() );
showStatus( "Calculating... " );
factorialValue = factorial( number );
showStatus( "Done." );
result.setText( Long.toString(factorialValue) );
}
long factorial( long n )
{
if( n == 0 || n == 1 )
return 1;
else
return n * factorial( n - 1 );
}
}
소스코드를 작성한 후, JDK의 Java compiler 를 이용하여 다음의 문장을 실행하면 결과로 Factorial.class
화일을 얻습니다.
c:\work> javac Factorial.java
이렇게 만들어진 Factorial.class 화일을 웹 문서에 삽입하는 코드는 다음과 같습니다.
<html>
<body>
<applet code="Factorial.class" width="320" height="60">
</applet>
</body>
</html>
다음은 같은 원리와, 다음의 함수를 이용하여 제작한 fibonacci number 생성용 Java Applet 입니다. 다음 Applet
의 소스코드는 fibonacci.java 입니다. 1)
long fibonacci( long n )
{
if( n == 0 || n == 1 )
return n;
else
return fibonacci( n - 1 ) + fibonacci( n - 2 );
}
더 유용한 Java Applet 의 활용은 4장의 활용 예에서 살펴보기로 하겠습니다.
3. Mathematica 를 이용한 구현
Mathematica 를 이용하는 것은 Mathematica 가 제공하는 많은 함수들과 Mathematica Notebook 의 프리젠테이션/출판
기능을 사용하는 것을 의미합니다. 기본적으로 Mathematica 는 다음의 Combinatorics 함수들을 제공합니다. (이어지는
그림은, Mathematica가 지원하는 조합론의 함수들을 직접 입력하고 작업하는 화면을 캡쳐한 것입니다.
Mathematica 가 제공하는 조합론 기반 함수들은 이것보다 훨씬 많지만, 한 학기동안 배운 내용과 중복되는 부분만 추린 것입니다.
Mathematica 를 사용하면 수학 프로그래밍의 작업시간을 효과적으로 줄일 수 있습니다.
4. 활용 예
4.1 Magic Square Applet
Magic Square 란 각 열, 행, 그리고 두개의 대각선에 위치한 수의 합이 같도록 만든 행렬을 말합니다.
따라서, order n의 magic square는 동일한 Magic Sum, 즉 s = n (n2 + 1) /
2 를 가집니다. 여기서 문제는 어떻게 하면 order n의 magic square를 구하는 일반적인 방법을 구축할 수 있는가 하는
점입니다. 이 절에서는, 17세기의 수학자 la Loubere의 방법으로 n이 홀수인 경우의 magic square를 만드는 Java
Applet을 만들어 봅니다.
la Loubere의 알고리즘은 다음과 같이 분석할 수 있습니다.
- n은 홀수여야 합니다. (n이 홀수가 아닌경우 error)
- 0th 열의 가운데 행에 1을 넣고 출발합니다.
- 그후, 다음 그림과 같은 방식으로 진행합니다.
오른쪽 윗쪽 대각선 방향으로 이동하면서, 윗쪽 경계에 이르면 다시 아래쪽으로 돌아오고, 이미 숫자가 채워져있는 칸을 만나면, 한칸
아래로 이동한 후, 다시 같은 방법으로 진행하면서 지나치는 칸에 숫자를 채우는 것입니다.
이것을 표현할 수 있는 Java Applet은 다음과 같으며 n = 3 부터 n = 11 까지 작동합니다.
이 프로그램의 소스코드는 MagicSquare.java 입니다. 소스의 알고리즘
구현부분은 다음과 같습니다.
전략...
-------
public void actionPerformed( ActionEvent e )
{
int magicSumValue;
number = Integer.parseInt( num.getText() );
if( number <= 11 && number > 1 )
{
magicSumValue = magicSum( number );
status.setText( "Magic Sum은 " +
Integer.toString( magicSumValue ) + "입니다." );
repaint();
}
else
{
status.setText( "1 보다 크고, 11 이하인 수를 입력하세요." );
}
}
int magicSum( int n )
{
return (n*n*n + n) / 2;
}
void drawBox( Graphics g, int n )
{
...;
}
void drawMagicSquare( Graphics g, int n )
{
int i,j,k,l,num;
num = 1;
k = 0;
i = (n-1)/2;
for(l = 0; l < n; l++ )
{
for( j = 0; j < n; j++ )
{
try { Thread.sleep(500);
} catch (InterruptedException e) {}
g.drawString(Integer.toString(num),
10 + 3 + (300/n)*((i+10*n)%n),
65 + 13 + (300/n)*((k+10*n)%n)
);
k--;
i++;
num++;
}
k = k + 2;
i--;
}
}
-------
후략...
4.2 n-Queens Problem
다음은 n by n 체스판에 n개의 Queen들을 서로 공격하지 않도록 배치하는 모든 가지수를 구하는 Applet입니다. 이 Applet은
1부터 10까지의 n-Queens Problem을 풀 수 있도록 설계되어 있습니다. 이 Applet은 좀더 복잡한 기능들을 요구하기
때문에 두개의 java source 화일로 구성되어 있습니다. (NQueens.java,
ChessBoard.java)
이 프로그램은 다음과 같이 구성되어 있습니다.
여기서 해가 "73025164" 라고 표현된것은
- 0번째 열의 7번째 행에 첫번째 Queen을 넣고,
- 1번째 열의 3번째 행에 두번째 Queen,
- 2번째 열의 0번째 행에 세번째 Queen,
- 같은 방법으로 7번째 열의 4번째 행에 마지막 Queen을 넣는 것을 뜻합니다.
실제로 작동하는 Applet은 다음과 같습니다.
Non-Attacking Queens의 해를 구하는 함수는 다음과 같습니다.
boolean Threatens(int x, int y, int numPiecesPlaced)
{
int i = 0;
boolean threats = false;
int temp;
while ((i < numPiecesPlaced) && (threats == false)) {
if (board[i] == y)
threats = true;
temp = x-i;
if ((y == (board[i]-temp)) || (y == (board[i]+temp)))
threats = true;
++i;
}
return threats;
}
void FindSolution(int piecesPlaced) {
int i;
for (i=0; i<NUM_QUEENS; ++i) {
if (!Threatens(piecesPlaced, i, piecesPlaced)) {
board[piecesPlaced] = i;
if (piecesPlaced == (NUM_QUEENS-1)) {
PrintSolution(NUM_QUEENS, solutionsFound);
++(solutionsFound);
}
FindSolution(piecesPlaced+1);
}
}
return;
}
void PrintSolution(int numQueens, int s)
{
int i;
sol = new StringBuffer("");
for (i = 0; i<numQueens; ++i) {
sol.append(Integer.toString(board[i]));
}
c.setSolution(sol.toString());
sol.append(": #" + Integer.toString(s));
solutions.addItem(sol.toString());
}
결론
Java / Java Applet 과 Mathematica 등의 새로운 도구를 사용하면 수학적인 내용을 쉽게 표현하고 구현할 수 있으며,
특히 교육을 목표로 사용될때 그 효과가 크다고 하겠습니다.
Java 와 Mathematica 등의 도구들, 그리고 변화하는 현실에 적응하는 것이 학문을 하는 사람의 자세라고 생각합니다.
참고자료.
- fibonacci 메쏘드의 각 순환단계에서 메쏘드 호출의 수가 두배로 되는 효과가 발생가기 때문에
이것은 금방 걷잡을 수 없이 커집니다. 30번째 fibonacci number를 계산하기 위해서는 2,692,537 번의 순환호출이
필요하기 때문에 그보다 더 큰 수를 넣을 경우, Applet에서 결과를 나타내기 까지는 아주 많은 시간이 필요할 것입니다.