4장: VPL을 사용한 알고리즘 프로그래밍

VPL로 디버깅 하기


  프로그래밍에 있어서 완성된 프로그램의 Accuracy를 높이기 위해서 반드시 필요한 단계가 디버깅이다. 현재까지 완성된 프로그램을 차근차근 돌아보면서 오류가 있나 없나를 확인 하는 작업이기 때문이다. 중요한 작업인 만큼 대표적인 프로그래밍 언어인 C언어나 JAVA 에서는 사용자를 위한 디버깅 환경을 제공하고 있다. 다음은 C와 JAVA의 디버깅 환경이다.


  MSRDS를 이용한 시뮬레이션을 할 때 사용되는 VPL 또한 디버깅 환경을 제공하는 데 사용 법은 다음과 같다.


  10과 20을 더해 결과를 출력하는 간단한 프로그램을 VPL을 이용해 디버깅 해보도록 하자.
  디버깅을 위해서 F10을 눌러주면


  다음과 같은 디버깅 창이 생성된다.
  Current Activity에서 현재 활성화 된 Activity를 알 수 있고, 바로 밑의 창에서 현재 값이 바뀐 변수를 확인 할 수 있다.
  버튼으로 프로그램에서 현재까지 수행하고 나서 남은 부분을 프로그램이 종료될 때까지 실행 할 수 있다.
  버튼으로 Activity 단위로 Step-by-Step으로 프로그램을 실행 시 킬 수 있다.

  하지만 이러한 디버깅 환경은 시뮬레이션 화면과 로봇의 센서 값 등 여러 가지를 한번에 실시간으로 확인해야 되는 프로젝트에서는 사용하기 힘이 들 수 있는데, 이 경우 ListBox를 값의 변화를 알 고 싶은 Activity와 연결하여 주면 실시간으로 그 변화를 확인 할 수 있다.


  Target Activity를 ListBox Dialog와 연결 한 뒤, 연결 옵션을 “AddItem”으로 설정하고 Data 옵션에서 변화를 알고 싶은 값을 선택해 준다.


  그렇게 해주면 프로그램 실행 시 다음 과 같은 ListBox가 나타나며, 값이 바뀔 때 마다 실시간으로 새 값을 화면에 표시해 준다.




VPL로 작성한 GCD 구하기 프로그램

목표 : VPL을 이용하여 최대공약수(GCD) 찾기

Step1. 유클리드 호제법


  주어진 두 수의 최대공약수를 찾는 가장 대표적인 알고리즘은 유클리드 호제법이다.
  두 수 a, b에 대해서 (a>b) a가 b로 나누어 떨어지면 b가 a, b의 최대공약수이다, 만약 나누어 떨어지지 않는다면 a를 b로 나눈 나머지 r을 새로운 b로 두고 a를 이전의 b로 둔다. 이 과정을 a가 b로 나누어 떨어질 때까지 반복하여 최대공약수를 구할 수 있다.

  특히 프로그래밍에서 반복문과 재귀에 어울리는 이 알고리즘은 이미 여러 언어에서 널리 구현되어 있다. 다음은 그 예시들이다.


  이번 Exercise에서는 VPL(Visual Programming Language)에서 제공하는 Basic Activities를 이용하여 유클리드 호제법을 구현 해 보도록 한다.

Step 2. 두 개의 입력 숫자 지정하기
 

 1) 두 개의 Data Activity를 추가한다.

 2) Integer 타입으로 설정 한 뒤 적절한 정수 값을 입력해 준다.

 3) Join Activity를 추가한다.

 4) 앞에서 추가한 두 개의 Data Activity를 연결해 준다.

 5) Join Activity에 입력한 이름들은 앞으로 반복문과 조건문에서 계속 쓰이게 되니 구분이 확실하게 되도록 지정해 두도록 한다.


Step 3. 반복문, 조건문 만들기
 

 1) 유클리드 호제법에서의 전제에 따라 항상 num1에 num2 보다 큰 수가 입력된다고 가정한다.

 2) 새로운 num1의 값을 계산하는 Calculate Activity를 추가한다.

 3) num2 % num1 (위쪽 Calculate Activity)에 들어갈 계산식

 4) 새로운 num2의 값을 계산하는 Calculate Activity를 추가한다.

 5) num1 % num2 (아래쪽 Calculate Activity)에 들어갈 계산식

 6) Join Activity를 추가하여 업데이트 된 num1과 num2의 값을 설정해 준다.


 7) num1과 num2의 바뀐 값을 적용하여 반복문을 구현하기 위한 Activitiy를 추가한다. (빈공간에 알맞은 Activity를 추가하세요)


Step 4. 출력하기


1) num2가 0이 되어 유클리드 호제법에 의한 GCD가 구해졌을 때, 출력을 위한 Simple Diagram을 추가한다.


 2) 결과를 보기 쉽게 나타내기 위하여 Caculate Activity를 추가한다.

 3) 그림 8과 같은 결과 값이 나오도록 하기 위해 추가한 Caculate Activity에 들어갈 계산식
    -> “GCD is.. ”+ num1

 4)  (실행) 버튼을 눌러 결과를 확인한다.

 5) 프로그램을 종료한다.


Step 5. 주의 해야 할 점


 1) VPL을 사용하여 유클리드 호제법을 구현 할 때 기존의 C나 JAVA와 같은 언어와 같이 변수를 선언하여 작성하고자 했을 때, 다음과 같은 실수를 하기 쉽다.

 2) Step 3에서의 첫 번째 조건문을 선언 할 때, 변수를 Join문을 통해 사용하면 그림 10과 같이 Type이 맞지 않다는 Error가 발생한다.

 3) 이는 msg, msg0라는 Join문에서 선언된 객체를 바로 integer 인 0과 비교했기 때문이다.

 4) 이 문제를 해결하기 위해서는 if문 안에 들어갈 식을 다음과 같이 수정해주면 된다.
 

 5) if문에서 프로그램에서 비교하고자 하는 것은 msg 객체가 아니라 msg객체가 가지고 있는 num1 이라는 variable의 value이기 때문에 msg를 msg.num1로 수정해주면 된다.


Step 6. 추가 과제
 
 1) Data값이 주어질 때, num1 이 항상 num2 보다 크지 않을 경우 GCD를 구하는 프로그램을 작성하시오

 2) 두 수의 최소공배수(LCM)를 구하는 프로그램을 작성하시오




VPL로 작성한 자연상수 e 근사 프로그램

목표 : VPL을 이용하여 자연상수(e)의 근사값 찾기

Step1. 테일러 급수(Taylor series)


  테일러 급수(Taylor series)는 미적분학에서, 미분가능한 어떤 함수를 다항식의 형태로 근사하는 방법이다. 이 이름은 영국의 수학자 브룩 테일러의 이름에서 따온 것이지만, 이것을 브룩 테일러가 처음으로 발견한 것은 아니다.
  n ≥ 0 인 정수 n에 대하여, 폐구간 [a,x]에서 n번 미분가능하고 개구간 (a,x)에서 (n + 1)번 미분 가능한 함수 f는
 

로 나타내어질 수 있다. 처음 몇 항까지를 선택함으로써 x = a 주변에서의 f(x)의 근사식으로 사용할 수 있는데, 이를 테일러 다항식(Taylor polynomial)이라고 한다. 특히 선형근사는 n = 1인 테일러 급수로 볼 수 있다.
 
  이번 연습 문제에서 근사 하고자 하는 자연상수 함수에 대한 테일러 급수는 다음과 같다.


  여기서 x 값에 1을 대입하면 자연상수 (e)의 값을 근사 할 수 있다.


  여기서 정확한 근사를 위해서는 를 무한히 전개해야 하지만 이번 연습 문제에서는 임의로 10번만 전개 하는 것으로 한다.
  그럼 지금부터 VPL의 Basic Activities를 사용하여 자연상수 e를 구해보자.


Step 2. factorial 구현하기
 

  10 factorial을 구하는 프로그램을 구현해 보자.

 1) 두 개의 Data Activity를 추가한다.

 2) Integer 타입으로 설정 한 뒤 각각 10과 1의 데이터를 넣어준다.

 3) Join Activity를 추가한다.

 4) 앞에서 추가한 두 개의 Data Activity를 연결해 준다.

 5) tmp는 승수(乘數) fac은 피승수(被乘數)가 될 것이다.

 6) If Activity를 추가한다.

 7) If Activity에 승수가 1보다 작아지면 factorial 결과 값을 출력 시키기 위해 tmp < 1 이라는 조건을 입력한다.


 8) 승수를 하나씩 줄여 나가면서 피승수에 곱해주기 위해 Calculate Activity들을 추가한다.
 
 9) 만약 승수가 0 이라면 피승수에 1을 곱해준다.

 9) 새로운 tmp(승수) 값을 구하기 위해 들어가야 할 계산식
   -> tmp -1

 10) 새로운 fac(피승수) 값을 구하기 위해 들어가야 할 계산식
   -> fac * tmp

 11) Join Activity를 추가하여 두 개의 Calculate Activity를 각각 tmp 와 fac 에 연결한다.
 
 12) Merge Activity를 추가하여 Join 두 개를 연결해 If Activity에 넘겨줌으로써 tmp가 1보다 작아지기 전까지 프로세스를 반복 할 수 있도록 해준다.
 

 13) If Activity의 조건이 만족 되었을 때 결과값을 저장하기 위해 Calculate Activity와 Variable Activity를 추가해 준다.

 14) If Activity와 Calculate Activity를 연결하여 fac(피승수) 값을 가져온다.
 

 15) Variable Activity에 fact 변수를 추가한 뒤 결과값을 저장한다.


Step 3. Factorial 프로그램을 Activity로 만들기

  자연상수 e 를 구하는 프로그램에 있어서 Factorial은 +,-와 같은 연산자처럼 계산과정에서 필요한 하나의 함수에 지나지 않는다. 그러나 Step2에서처럼 복잡한 다이어그램으로 표현된다면, 프로그램을 해석하는데 상당히 난해할 것이다. 그러므로 간결한 전체 Diagram을 위해 Factorial process를 하나의 Activity로 표현 하기로 하자.
 

 1) Factorial을 하나의 함수로 만든다고 생각했을 때 입력은 어떤 자연수 n 그리고 출력은 n! 이 될 것이다.
 
 2) Activity를 추가한다.

 3) Activity를 더블 클릭한다.

 
 4) Step 2에서 작성한 Factorial 프로그램을 복사하여 Activity 창에 붙여 넣는다.

 5) Activity 액션 창()을 열어 입력과 출력 형식을 지정해 준다.
 

 6) 입력은 정수 n 출력은 정수 fact로 지정한다.

 7) 피승수를 지정하는 값을 Data Activity에서 Calculate Activity로 바꿔준다.

 8) Activity에서의 입력을 7)에서 바꿔준 Calculate Activity에 연결한다.
 
 9) Activity에서의 입력을 피승수를 초기화 해주는 Data Activity에 연결한다.

 10) Factorial 프로그램의 결과값을 임시 저장하는 Variable Activity를 삭제한다.

 11) Factorial 프로그램의 결과값을 Activity에서의 출력에 연결한다.



Step 4. 자연상수의 근사값 구하기
 

 1) 초기값을 지정하기 위해 Data Activity 두 개와 Join Activity를 추가한다.

 2) flag는 테일러 급수의 에서 현재 n이 얼마일 때를 수행하고 있는가를 나타내기 위한 변수이며 초기값은 0이다.

 3) result는 최종적인 근사 값을 저장하기 위한 변수이며 초기 값은 0이다.

 4) If Activity를 추가한다.
 

5) n이 10이 되면 수행을 종료하기 위해 If Activity에 들어가야 할 식
 -> flag > 10
 

6) If Activity에서 result 값을 받아오기 위한 Calculate Activity를 추가한다.

7) 1/n! 을 구하기 위해서 If Activity의 flag 값을 Factorial Activity에 추가한다.

8) Calculate Activity를 추가하고 Factorial Activity의 결과 값을 사용하여 1/n!을 계산한다.
 

 9) 에서의 더하기를 수행하기 위해 Join Activity와 Calculate Activity를 추가한다.
    (그림 16의 빈칸에 result + inv_fac 수행을 위해 필요한 activity를 넣으세요)
 

 10) flag를 1 증가시키기 위한 Calculate Activity를 추가한다.

 11) Update된 flag와 result 값을 Join Activity에 연결한다.

 12) Join된 flag와 result 값을 Merge Activity를 통해 조건문에 연결해준다.
 

 13) 출력을 위해 Calculate Activity와 Simple Dialog를 추가해준다.

 14) 그림 18과 같은 출력을 위해 Calculate Activity에 들어갈 계산식
  -> “자연상수(e): ”+ result

 15) (실행) 버튼을 눌러 결과를 확인한다.

 16) 프로그램을 종료한다.


Step 5. 주의 해야 할 점

 1) 그림 10에서 Activity의 입출력 형식을 지정해 줄 때, 반드시 int type으로 선언 하도록 한다.
 
 2) Activity에서 외부로 출력을 위한 연결을 할 때에 반드시 value 형태를 취하도록 한다. 그러지 않으면 타입 에러가 날 수 있다.



Step 6. 추가 과제
 1) 의 전개 횟수가 10번으로 고정되지 않고 k라는 variable을 두어 k번 전개하여 자연 상수 e 를 근사 하는 프로그램을 작성하시오.

 2) Hyperbolic functions중 하나인 sinh 함수를 테일러 급수로 나타내면 다음과 같다.

 
   VPL을 사용하여 sinh1 값을 근사 하는 프로그램을 작성하시오.

본 연구는 Microsoft Research Asia (MSRA)의 지원으로 수행되었습니다.