@ 2024a;Weekly[2];quadratic,gcd,Add two big numbers,Hanoi,TSP,196,하렐,WCP

[문교식]

@@@@@@@@@@@@@@@@@@@@@@@@@@

< Wk 2> ============================================================

 computability,  computational complexity, nonpolynomial problem, unsolvable problem

수학문제 풀이; 문제정의, 데이터, 결과값이 명확한 문제를 대상으로 한다.
[예1]; quadratic 

Py코드; [Q] Quadratic ; Py [LecPrep #448] ;   [ MathProblems #68 / (Soln) Quadratic ; Py ]  

   ; 오류를 수정하자.  /2*a  -->  /(2*a) 

(#3; 24.3.19.)   >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 

[예2]; GCD.

[Lab]   ; [Math / #53 ; GCD - Non-Euclid ] ; [LecPrep/Math-GCD-nonEuclid.py]

  입력값 -> 출력값 확인. 코드 해설(상세한 문법이 아닌, 알고리즘적 흐름) 

    ; 두 수 중에서 작은값(smaller)를 찾아서 그것에서 부터 1씩 감소하면서 두 수를 

       나누는지 검사하고, 최초로 두 수를 나누는 순간 gcd를 출력한다.
    --> 개선; 효율성 제공 ( 두 가지 의미; 계산시간의 절약, 메모리의 절약; 시공의 두면) 
               Euclid GCD를 실습한다. 정확한 연산후 효율성 제고를 위한 노력이 필요하다.

[Lab]   Euclid GCD  [Math #31] 

 ; 예를 두어 가지 살펴본다. 직접 풀어본다. nonEuclid와 비교한다.

 파이썬 코드  ; [LecPrep ; Euclid GCD] ; 실행 실습. 

   [실습문제]  두 수가 782091 54492일때의 GCD=?  답> gcd=3

                      Euclid 방법과 nonEuclid 방법의 성능을 비교하자. (in terms of # of iterations)

                      답> Euclid는 9회 반복, nonEuclid는 (54492-3+1)회 반복

  ; quadratic, gcd와 같은 문제들은 컴퓨터 프로그램에 의해 실용적 시간 안에 정확한 결과를 보장한다.

    대부분의 과학, 공학적 문제들이 이 범주에 속한다. 
    많은 문제들은 수학적 결과를 이용하여 문제를 풀 수 있다. 

[탐구문제] 수학에서는 문제가 안되지만, 컴퓨터에서는 문제가 발생;
주로, 표현오차, 저장공간, 등으로 인해 발생. 
컴퓨팅 환경에 맞는 새로운 방법의 고안이 필요.
(예) 두 큰 수의 덧셈; [Math #17; cpp] [Math #21; exe] 

  58302579658022005943850 + 753402898595792030845839 = ?
숫자가 너무 커서 프로그램이 사용하는 변수에 저장을 못해.
변수의 저장 범위를 넘어선다. 
알고리즘적 처리가 필요하다.

    [아이디어 제출] 

[예3];  Hanoi Tower Problem

[Lab]  [Ref; Algo #15] [LecPrep / Algo-Hanoi] ; [실습 & 실습문제]

특징; 데이터의 크기가 증가함에 따라 계산회수가 기하급수적으로 증가하는 문제이다.
최적해/정확한 해를 원한다면, 2의 N승으로 증가하는 지수증가를 완화할 방법이 없다. 
이러한 범주의 문제를 NP(nonpolynomial problem)라 한다.
많은 문제들이 NP에 속함을 알게 되었다.
다수의 AI문제들이 이 범주에 속한다.

(#4; 24.3.26.)   >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 

  개교기념일 휴강; LMS 보강

(#5; 24.4.2.)   >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 

 > [수업내용간추림] 

 > 숙제 Rvw; Hanoi문제. See 신정민. 

[예4];  TSP (Travelling Salesman Problem)
[Lab]  [LecPrep#453] ; TSP - Lab (st) ; Exl (10 pts)]  dist=? 

        최적해(optimal solution)를 구하는 방법을 고안하자;

                   실용적 방법이 없다면, 모든 경우를 다 비교하는 수 밖에 없다; brute-force  

        [시범 실습]; [LecPrep#455]; Permutation계산. brute-force로 최적해 찾기

                    데이터의 개수(N)이 증가함에 따라 계산시간의 증가를 측정하자.

                    결과 제출;  계산시간. 이 실험으로부터의 결론은? 

 *  10! = 3,628,800  (360만)
     11! = 4천만
     12! = 4.8억 
     13! = 62억
     14! = 871억
     15! = 1.3*10^12 (trillion,조) 2^15=32,768

 * Brute-Force ; 하나씩 다 해보기. 모든 가능한 경우를 다 해보기
  모든 가능한 경우를 나열하기= permutation (N!의 가지수)

  비유> 대형 콘테이너에 실린 콩. 콩의 개수는?  >> brute-force법; 하나씩 헤아림.

            heuristic방법; 표준용기 여러개의 평균으로 개수를 어림잡음.

                          exact soln은 아니지만 효율적임. 실제의 soln과 큰 차이는 없을 것임.

  ;; AI문제는 따져야할 경우의 수가 너무 많다. Exact soln은 불가능. Heuristic방법을 채용.

  Lab> [LecPrep#455]; TSP - Py ; permutation, brute-force]

            ; permut(5 pts), 10 pts, 15 pts

       N=15의 TSP ; Min.Dist= 95.015129
          Path(32nd;still running)=
              [1,5,2,11,4,7,8,15,10,9,6,12,14,3,13]
       ; still running for three hours.
       ;Pentium 2.5GHz. 8GB RAM. 64비트. 삼성. Windows8.

개요; 모든 가능한 경로들 중에서 최단거리의 경로를 찾는다.
최단경로 문제는 최적해(optimal solution)의 경우 O(N!)의 방문을 필요로한다.
(N!은 2^N 보다 훨씬 크다)
아주 어려운 문제들이다. 이런 문제들이 다수 존재한다.

[LecPrep / QZ - TSP]
   

 >>> 휴리스틱은 [Brute-Force vs. Heuristic] 단원에서 배운다

(#6; 24.4.9.)   >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 

 > [수업내용간추림] 

 > 숙제 Rvw; TSP 퀴즈 두건.

[예5];  196 Problem
(숫자 팰린드롬 문제)    [Ref; Math #23 / 숫자팰린드롬]  [LecPrep / 숫자팰린드롬]

           [실습 & 실습문제] ; cpp,exe
팰린드롬의 소개, 숫자 팰린드롬의 소개, 

196문제의 소개;  [인터넷 검색]; '196 problem'을 검색한다(google).

[Lab] [LecPrep / 숫자팰린드롬 ; Q 포함] ; cpp, exe  실습 문제 제출;  

아주 빠른 속도로 계산량이 엄청나게 증가하므로 대규모 데이터의 저장, 처리속도 등의 
하드웨어적 성능을 테스트하는 좋은 재료가 되고 있다. 
이런 이유로 수퍼컴퓨터의 성능 테스트에 많이 활용되고 있다. 
지금도 세계적인 이슈가 되고 있다. 
이 문제의 특징; 종료를 보장하지 못한다. (언제 끝날지 알 수 없다)
이런 유형의 문제가 다수 발견되었다.

[예6];  Harel's Integer Problem;
[Lab]   [LecPrep / Harel - Py] [실습과 실습문제 포함]   

             실습 문제 제출;

여러 번 실행하면, 어떠한 수이든 종료한다는 느낌이 들어온다. 
그러나 왜 종료하는지에 대한 이유를 찾지 못했다. 
즉, 결과를 증명할 수 없는 경우이다. 
이러한 문제는 해(솔루션)의 존재를 보장할 수 없는 문제이다. 
이러한 종류의 어려운 문제도 다수 존재한다.


[예7];   WCP(word correspondence problem, 단어 일치 문제)
[LecPrep / WCP(word correspondence problem, 단어 일치 문제)]

[실습문제]
이 문제의 특징; 
이 문제에 대한 알고리즘은 존재하지 않는다고 알려져있다. 
즉, 해결 방법이 없다. 
이런 문제를 unsolvable problem이라 한다. 
'Halting Problem'이라는 문제는 대표적으로 이 범주에 속하는 문제이다. 
이러한 문제들이 다수 존재한다는 것이 알려져 있다. 
(현재의 과학기술로는 이러한 문제를 풀 수 있는 컴퓨터는 없다)
이와 같이 컴퓨터로 풀 수 없는 문제들도 다수있다. 

또 다른 예; Halting problem

//