유키 히로시의 '프로그래머, 수학으로 생각하라'(원제는 프로그래머의 수학)를 읽다.
히로시가 '수학걸'을 쓰기 전에 쓴 책으로 역시 이 저자는 수학을 알기 쉽게, 깊이있게 이해시키는데 재능이 있다.

0의 역할이 자리를 확보하여 패턴을 만들어 규칙을 간단하게 한다라는 것이나 나누기를 통해 나온 나머지의 주기성을 이용, 그룹을 나누고 패턴을 발견하거나 패리티 비트(홀/짝)를 이용해 2개로 나누는 것 등 단순한 내용에서 심오한 깊이를 찾아내는 내용들이 흥미로웠다.

* 수학의 논리식(논리는 둘(참/거짓)로 나누기), 진리표(표로 정리), 벤 다이어그램(시각화), 드모르간의 법칙~(A^B) = ~(A)V~(B) 논리곱/합으로 변형하면 !(A && B) == (!A || !B), 카르노 맵(복잡한 논리 그룹지어 간단히 정리하는 기술), true, false 이외에 undefined를 포함한 3값 논리.

* 수학적 귀납법(도미노 쓰러뜨리기): 1. 기저의 증명, 2. 귀납의 증명.
: P(K)를 증명한 뒤 P(K+1) 증명하기

* 치환, 순열, 조합-나열하는 방법, 몇 개를 골라 순서를 바꿔 나열하는 방법, 순서 상관없이 고르는 방법.
ex) 5C3 x 3P3 = 5P3(5장에서 3장 선택하는 조합 x 3장의 치환 = 5장에서 3장을 선택한 순열)

* 재귀와 귀납은 모두 큰 문제를 같은 형태의 작은 문제로 만들기.
재귀는 큰 문제에서 점점 작은 문제로, 귀납은 작은 문제에서 점점 큰 문제로.
재귀적 구조(자신안에서 자신을 발견하기)를 찾아내 점화식 만들기.
ex) n! => n * (n-1)!

* 지수적 폭발과 로그: 지수적 폭발을 이용한 이진검색(반으로 나눠 참 혹은 좌/우로 구분하여 찾기), 10^5 = 100,000, log10 100,000 = 5, 로그 이용하여 덧셈으로 곱셈 구하기, 계산자.

* 귀류법(배리법): 1. 증명하고자 하는 명제의 부정이 성립한다고 가정 > 2. 그 가정을 기본으로 증명을 진행하여 모순을 유도.
예) 정수열 전체는 셀 수 없다를 증명하기 위한 대각선 논법.

* 셀 수 없는 집합, 계산할 수 없는 문제(프로그램으로 푸는 것이 원리적으로 불가능한 문제). 정지 판정 문제 > 귀류법에 의해 모순에 빠진다.

문제 해결법:
1. 패턴을 발견해 일반화:
작은 수로 시험하여 규칙, 성질, 구조, 반복, 정리를 통해 패턴 발견 > 다른 비슷한 문제에 적용 가능하도록 일반화하기

2. 서투름에서 생기는 지혜:
큰수 > 수 표기법 변화(위치값 기수법, 지수 표기법),
복잡한 논리 판단 > 논리식 형태로 추론, 카르노 맵 사용,
많은 물건 관리 > 그룹화하여 동일 그룹내의 것을 동일시,
무한의 수 다루기 > 유한으로 무한 다루기.

3. 세계를 바꿔가며 풀기:
현재 세계에서 복잡한 문제를 보다 간단히 정리할 수 있는 단순한 세계로 이동, 그곳에서 계산한 뒤 다시 현재 세계로 되돌아 오기.

15/5/24 일