@@@@@@@@@@@@@@@@@@@@@@@@@@
< 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
//