1.1 알고리즘

알고리즘: 유한성, 명확성, 입력, 출력, 효과성

1. (a, b, c, d) 를 (b, c, d, a)로
   
   1. t=a;
   2. a=b;
   3. b=c;
   4. c=d;
   5. d=t;

1.2 수학적 기초

1.2.1 수학적 귀납법

1. 수학적 귀납법에 의한 증명 P(n) n=1, 2, 3… -> n=0, 1, 2…
   P(0)이 참임을 증명한다. (a)
   "만일 P(0),P(1),P(2),...P(n)이 모두 참이면 P(n+1)도 참이다"를 증명한다. 이 증명은 모든 음이 아닌 정수 n에 대해서 유효해야 한다 (b)
   알고리즘 1.2.1.1 (증명의 구축). 음이 아닌 정수 n이 주어졌다고 할 때, 이 알고리즘은 P(n)이 참임을 보이는 증명을 출력한다.
   I1. [P(0)을 증명.] k<-0로 설정하고 (a)에 의거해서 P(1)의 증명을 출력한다.
   I2. [k=n?] 만일 k=n이면 알고리즘을 끝낸다. 요구된 증명은 이미 출력되었다.
   I3. [P(k+1)을 증명.] (b)에 의거해서 "P(1), ...,P(k)가 참이면 P(k+1)도 참이다"에 대한 증명을 출력한다. 또한 "이미 P(1), ...,P(k)는 증명되었으며, 따라서 P(k+1)은 참이다."도 출력한다.
   I4. [k를 증가.] k를 1 증가시키고 단계 I2로 간다.

1.2.2 수, 거듭제곱, 로그

//47쪽 오타: 무한이->무한히

1. 0
2. 1+0.239999....는 소수 전개
3. -1/27
4. 4
5. 2진 전개 x = n + 0.d₁d₂d₃.... n은 이진수이고, 각 d_i는 0에서 1사이의 숫자이다. 이 숫자들의 열은 끝나지 않고, 무한히 많은 1들로 이어진다.
   이는 를 의미한다.
6. x = m + 0.d₁d₂... y = n + 0.e₁e₂... 는 실수이다.
   
   1. m과 n을 비교한다. (m>n이면 x>y, m<n이면 x<y이다. ->종료)
   2. m=n이면 i에 1을 둔다.

   3. d_i와 e_i를 비교한다.

   4. 전자가 크면 x가 크고, 후자가 크면 y가 크다. 같다면 i에 1을 증가시키고 3번으로 돌아간다.
   5. 모든 양의 정수 i에 대해 d_i와 e_i가 같다면 x=y이다.

10. log₁₀2는 유리수가 아니다.

1. log₁₀2가 유리수라면 그 값은 b/a로 설정할 수 있다. (b와 a는 정수, a는 0이 아니다.)
2. 이는 이다.
3. 양변을 a제곱 하면, 2^a = 10^b이다.
4. 이는 10을 소인수분해할 때 이고
5. 양변을 2^b로 나눌 때 2^a-b=5^b이다.
6. 2와 5는 서로소 관계이므로 이를 만족하는 정수 a와 b는 존재하지 않는다.
7. 따라서 처음 가정은 틀렸고, log₁₀2는 유리수가 아니다.

11. b=10, 일 때 b^x의 소수 전개 처음 세 자리를 결정하는데 필요한 x 값의 소수점 이하 유효 숫자는 세 개

http://inphy.korea.ac.kr/Work/Gen_Phy_Exp/Worksheet/Gen_Phy_Exp_0_0/Significant_Figures.pdf

12. 식 9에서 log에 대한 정의를 내렸고,

10^0.30102999 = 1.9999999739 와 10^0.30103000=2.0000000199 이므로

log₁₀2는 위에 제시된 지수 사이의 값이 분명하므로 log₁₀2=0.301029999...로 쓸 수 있다.

16.log₁₀x=

17. lg32=5, log_ππ=1, lne=1, log_b1=0, log_b(-1) 은 e^iπ = − 1이므로  에서, 이다.

18. log₈x는 이므로 옳지 않다.

20. log₁₀2와 log₂10는 역수 관계이다.

1.2.3 합과 곱

1.조건을 만족하는 정수에 대해서만 적용되므로 a₁+a₂+a₃

2.,

4.a₁₁ + a₁₂ + a₁₃ + a₂₁ + a₂₂ + a₂₃ + a₃₁ + a₃₂ + a₃₃

9.유효하다

10. 유효하지 않다.

11. (n+1)a

12.

13.

17. 정수의 개수는 무한하므로, 특정값으로 정의될 수 없다. 즉, 무한히 커지는 상태이다.

http://en.wikipedia.org/wiki/Vandermonde_matrix

http://www.google.co.kr/search?q=combinatorial+matrix&btnG=%EA%B2%80%EC%83%89&complete=1&hl=ko

http://en.wikipedia.org/wiki/Cauchy_determinant

이 글은 스프링노트에서 작성되었습니다.

1.2-1 응용프로그램: 웹 브라우저, HTML을 읽어와서 태그에 맞게 해석하여 화면에 출력하는 알고리즘이 필요하다. HTML 태그를 읽어와서, 정규식 등을 이용해 파싱하고 이 엘리먼트에 대응하는 출력 형식을 판단한 후 화면에 나타내는 기능.

1.2-2 8n² 과 64nlgn 여기서 lgn=log₂n이다. n이 무한히 커질 때, 8n²이 64nlgn보다 커질 것이고, 두 값이 같은 점이 8n²이 64nlgn을 앞지르는 지점이다. n 자리에 2의 거듭제곱 꼴을 넣고 그 수는 x라고 할 때 8n은 2^3+2x 64nlgn은 x*2^6+x이다.  x에 8을 대입할 경우 2의 지수가 19로 같다. 따라서 n은 2⁸ 즉 256보다 클 때 8n²이 64lgn보다 커진다.

1.2-3 100n²이 2ⁿ보다 클 경우 n의 최소치를 구하려면 대입해서 범위를 좁힌다. 14를 대입할 경우 100n²는 19600 2ⁿ는 16384가 나와서 앞 쪽이 크지만, 15를 대입하면 100n²는 22500 2ⁿ는 32678이 나와서 큰 정도가 뒤집어진다. 계산 횟수는 정수이므로, 최소값 n은 14이다.

이 글은 스프링노트에서 작성되었습니다.

1.1-1 정렬 문제가 발생하는 현실 세계의 사례에는 사전 표제어 들이 멋대로 흩어진 데이터에서 국어같으면 ㄱ, ㄴ, ㄷ..  순으로 정렬해야 하고, ㄱ 내부에서는 ㅏ, ㅑ, ㅓ.. 순으로 정렬해야 하는 문제가 발생한다. 영어사전이라면 맨 처음 글자를 a, b, c .. 순으로 정렬하고 바로 다음 글자도 앞과 같은 순으로 정렬해야 하는 문제가 발생한다.

1.1-2 속도 외에 효율성을 평가할 만한 다른 척도에는 소모하는 메모리 공간, 알고리즘이 요구하는 통신 대역, 알고리즘이 요구하는 하드웨어 자원 등이다.

1.1-3 자료구조
연결리스트  장점은 자료의 추가와 삭제가 빠르다. 단점은 특정 데이터를 찾으려고 할 때 순차적으로 찾아야 하므로, 느리다.

1.1-4 최단 경로 문제와 순회 판매원 문제는 거리를 계산하고, 짧은 경로를 목적으로 한다는 점이 비슷하다. 다른 점은 최단 경로 문제는 출발지에서 목적지로 가는 경우이지만, 순회 판매원 문제는 물건을 여러 지점에서 판매하고 다시 원래 지점으로 돌아온다는 점이 있다. 최단 경로 문제는 효율적 해결 방법이 있으나, 순회 판매원 문제는 어느 정도 좋은(최적의 알고리즘은 아닌) 해결 방법이 있다.

1.1-5 최적의 해만이 의미 있는 문제: 전자 상거래에서 보호가 필요한 정보를 안전하게 관리하는 알고리즘
근접한 해를 구해도 충분한 문제: 인터넷에서 특정 정보가 있는 페이지를 검색하는 알고리즘

이 글은 스프링노트에서 작성되었습니다.