프로그래머, 수학으로 생각하라 24-2기 정성헌.

Presentation on theme: "프로그래머, 수학으로 생각하라 24-2기 정성헌."— Presentation transcript:

1 프로그래머, 수학으로 생각하라 24-2기 정성헌

2 무슨 책이지??? 프로그래밍을 더 잘 이해할 수 있도록 수학적 사고방식을 길러주는 책

3 INDEX 1장 0이야기 2장 논리 3장 나머지 4장 수학적 귀납법 5장 순열과 조합 6장 재귀 7장 지수적 폭발
8장 계산할 수 없는 문제 9장 프로그래머 수학이란?

4 “ 순열과 조합 ”

5 이 장에서 배울 내용 78% 22% 10% 수를 세는 것이란? 순열 조합 22% 78%

6 누락과 중복에 주의해서 수를 세자 덧셈법칙 |A U B| = |A| + |B| - |A ∩ B|
곱셈법칙 |A x B | = |A| x |B| 곱셈법칙: 주사위 3개가 있을 때 나올 수 있는 경우의 수는 ? 6*6*6=216가지 22% 78%

7 순열 N개 중에 K개를 선택하여 순서를 생각하며 나열 ex) 5장의 카드로부터 3장을 뽑아 나열하는 경우 일반화하기
5P3 = 5*4*3 =60 일반화하기 nPk = n * (n-1) * (n-2) * … * (n-k+1) 78%

8 조합 N개 중에 M개를 순서를 생각하지 않고 선택하는 것 ex) 5장의 카드로부터 3장을 선택하는 경우 일반화하기
5C3 = (5*4*3)/(3*2*1) =10 일반화하기 nCk = 𝑛! 𝑛−𝑘 !∗𝑘! 78%

9 Quiz 카드가 5장 있는데, 조커 2장과 J,Q,K 각각 1장씩으로 구성되어 있습니다. 이 5장의 카드를 가로로 나열했을 때 왼쪽 끝이나 오른쪽 끝 중 적어도 한쪽이 조커가 되는 나열 방법은 몇가지일까요? 단, 조커 2장은 서로 구별하지 않습니다. 조커 J Q K 조커 78%

10 Answer 1) (왼쪽 끝이 조커인 경우+오른쪽 끝이 조커인 경우 –양쪽 끝이 조커인 경우)/2
2*4P *4P P2*3P3 2) 모든 나열 방법 – 양끝 모두 조커가 아닌 나열방법 5P5/2 (3P2*3P3) /2 = 42 1)전부 조커의 중복을 고려하지 않았기 때문에 끝에 2로 나눠줌 2)양끝에 J,Q,K에서 2개 뽑아 나열하는 경우 3p2* 남은 3장을 나열하는 경우 3p3 / 조커 중복 2 78%

11 “ 재귀 ”

12 이 장에서 배울 내용 78% 22% 10% 하노이의 탑 피보나치 수열 22% 78%

13 하노이의 탑 3개의 기둥이 있다. 기둥 A에는 원반이 6장 쌓여있다. 기둥 A에 있는 6장의 원반을 모두 기둥 B로 옮기자.
단, 한번에 움직일 수 있는 원반은 기둥의 가장 위에 놓인 원반 1개뿐이다. 어떤 원반위에 그보다 더 큰 원반을 쌓을 수는 없다. A B C 22%

14 힌트 작은 하노이 탑을 풀면서 생각해보자! 우선 3장의 원반을 대상으로 생각해보자 A의 원반을 B로 옮긴다.
A의 원반을 C로 옮긴다. B의 원반을 C로 옮긴다. C의 원반을 A로 옮긴다. C의 원반을 B로 옮긴다. 3수 동안 2장의 원반을 기둥 A에서 C로 옮긴다 78% 3수 동안 2장의 원반을 기둥 C에서 B로 옮긴다

15 힌트 H(n-1) 1 H(n-1) H(n) = H(n-1) + 1 + H(n-1) A의 원반을 B로 옮긴다.
A의 원반을 C로 옮긴다. B의 원반을 C로 옮긴다. C의 원반을 A로 옮긴다. C의 원반을 B로 옮긴다. H(n-1) 3수 동안 2장의 원반을 기둥 A에서 C로 옮긴다 1 H(n-1) 3수 동안 2장의 원반을 기둥 C에서 B로 옮긴다 78% H(n) = H(n-1) H(n-1) N하노이를 푸는 횟수 N-1하노이를 푸는 횟수 가장 큰 원반을 움직인 횟수 N-1하노이를 푸는 횟수

16 피보나치 수열 태어난 지 2일 지나면 새끼를 한 마리 낳고 그 이후는 매일 새끼 한 마리씩을 낳는 생물이 있다.
1일째에 막 태어난 생물을 한 마리 받았다고 합시다(이 생물이 처음 새끼를 낳는 것은 3일째 이다) 11일째에는 전부 몇 마리가 될까요?

17 피보나치 수열 1일 1마리 2일 1마리 3일 2마리 4일 3마리 5일 5마리

18 피보나치 수열 F(n) = F(n-1) + F(n-2) N일째의 생물 N-1째까지의 생물 N-2일째까지의 생물이 낳은 새끼

19 “ 지수적 폭발 ”

20 이 장에서 배울 내용 78% 22% 10% 지수적 폭발이란? 이진검색 로그 암호 22% 78%

21 지수적 폭발이란? Quiz 달에 닿는 종이 접기 단 39번! 수가 급격히 증가하는 것을 지수적 폭발이라 한다.
단 39번 접으면 달까지 닿는다. 놀랍지 않은가? 두께 1mm인 종이가 있다. 이 종이를 접을 때 마다 두께가 2배씩 늘어난다. 달까지 거리가 약 39만 km라고 할 때 몇번을 접으면 달까지 닿을까? = 274, km = 549, km 22% 78% 단 39번!

22 이진검색 : 지수적 폭발을 이용한 검색 15명의 용의자중 1명이 범인이다. “범인이 누구입니까?”라고 물어봐서 몇번만에 범인을 찾을 수 있을까? 단, 질문 받은 사람은 (1)범인은 저입니다. (2)범인은 저보다 왼쪽에 있습니다. (3)범인은 저보다 오른쪽에 있습니다. 로 대답한다. 이 문제에서 보듯이 주기성을 찾는 것이 중요하다! 22% 78%

23 Answer 3번만에 찾을 수 있다.

24 로그란? 큰 수를 다루는 도구이다! Log101000 = 3 Log28 = 3
Log10(A*B) = Log10A + Log10B 22% 78%

25 1234712rWJDFQWRQWERRCC$((O@#$KJ!@#$!@#*$(CWEORO@CO#J@#R@$#*(
암호 : 지수적 폭발로 비밀을 지킴 키 메시지 암호문 안녕하세요. 이번에는 일요일에 신촌에서 만나요. 암호화 키의 비트길이가 길수록 무작위 공격 시간이 오래 걸린다!! 4bit : 16가지 경우의 수 5bit : 32가지 경우의 수 6bit : 64가지 경우의 수 … 현재는 256,512bit의 키를 사용한다. 그래서 무작위 공격을 하기에 시간이 오래걸려 해킹을 할 수가 없다. 256bit는 2^256가지 경우의 수 이고 512bit는 2^512가지 경우의 수이다. 78%

26 지수적 법칙을 이용하면 문제를 푸는데 강력한 무기가 될 수도 있지만 주의하지 않으면 큰 시간적 문제가 생기기도 한다!
22% 78%

27 “ 계산할 수 없는 문제 ”

28 이 장에서 배울 내용 78% 22% 10% 1. 귀류법이란 2. 계산할 수 없는 문제 22% 78%

29 귀류법이란? 우선 ‘ 증명하고자 하는 명제의 부정＇이 성립한다고 가정한다.
그 가정을 기본으로 증명을 진행하여 모순을 유도한다. 22% 78%

30 계산할 수 없는 문제 계산할 수 없는 문제라는 것은 프로그램으로 푸는 것이 원리적으로 불가능한 문제를 말한다. 22%

31 QUIZ : 정지 판정 문제 프로그램의 동작은 반드시 다음 중 하나가 된다. 1)한정된 시간 안에 동작을 정지한다.
2)한정된 시간 안에 동작을 정지하지 않는다. 영원히 정지하지 않음 데이터 프로그램 결과를 출력하고 정지함

32 프로그램에 데이터를 주어 동작하게 했을 때 한정된 시간 안에 동작이 멈추는지 판단하는 프로그램은 누구도 만들 수 없다.
귀류법으로 증명하기! 22%

33 1. 판정 프로그램을 만들 수 있다고 가정한다. 판정 프로그램의 파라미터로 판정 프로그램과 데이터를 준다.
HaltChecker(p,d) 판정 결과는 다음과 같이 표현한다. HaltChecker(p,d) = true (p에 d를 입력했을 때 p가 한정된 시간 안에 정지할 때) false ( p에 d를 입력했을 때 p가 한정된 시간 안에 정지하지 않을 때) 22%

34 2.프로그램 SelfLoop작성하기 HaltChecker를 이용하여 다음과 같은 함수 SelfLoop를 만든다.
SelfLoop(p) { halts = HaltChecekr(p,p); if(halts){ while(1>0){ } 1)HaltCheker를 사용하여 프로그램 p에 대해 그 프로그램 p 자신을 입력데이터로 주었을 때 정지할 것인가를 판정한다. 2)만약 HaltChecker가 정지한다고 판정하면 SelfLoop는 무한 순환에 빠진다. 3)만약 HaltChecker가 정지하지 않는다고 판정하면 SelfLoop는 바로 종료되고 정지한다. 22%

35 3-1. 모순 이끌어내기 [1]SelfLoop(SelfLoop)가 한정된 시간 안에 정지할 때
->SelfLoop(SelfLoop)가 한정된 시간 안에 정지한다는 것은 HaltChecker(SelfLoop,SelfLoop)가 False가 될 때이다. HaltChecker(SelfLoop,SelfLoop)가 False가 된다는 것은 SelfLoop에 SelfLoop를 입력했더니 SelfLoop는 정지하지 않는다는 의미다. ->SlefLoop(SelfLoop)가 한정된 시간 안에 정지할 때를 생각하는데 SelfLoop에 SelfLoop를 입력했더니 SelfLoop는 정지하지 않는다는 결론이 나와버려 모순이 되었다. 22%

36 3-2. 모순 이끌어내기 [2]SelfLoop(SelfLoop)가 무한순환에 빠질 때
HaltChecker(SelfLoop,SelfLoop)가 true가 될 때이다. HaltChecker(SelfLoop,SelfLoop)가 true가 된다는 것은 SelfLoop에 SelfLoop를 입력했더니 SelfLoop는 정지한다는 의미이다. ->SlefLoop(SelfLoop)가 한정된 시간 안에 무한 순환할 때를 생각하는데 SelfLoop에 SelfLoop를 입력했더니 SelfLoop는 정지정지한다는 결론이 나와버려 모순이 되었다. 22%

37 4 결론 HaltChecker를 만들 수 있다는 가정에서 출발하면 반드시 모순이 생기게 된다.
정지 판정 문제를 계산할 수 없다는 것은 1963년 앨런 튜링(Alan Turing)이 증명했다. 22%

38 “ 프로그래머 수학이란 ”

39 이 책을 되돌아보며 1장 0이야기 10% 2장 논리 3장 나머지 4장 수학적 귀납법 5장 순열과 조합 22% 6장 재귀
7장 지수적 폭발 8장 계산할 수 없는 문제 9장 프로그래머 수학이란? 78% 22% 10% 22% 78%

40 ‘0’은 규칙을 간단하게 만든다. 0을 도입하면 패턴이나 규칙을 쉽게 만들 수 있다.
규칙을 만들면 기계적으로 처리하기 쉬워지며 컴퓨터 문제 해결을 맡기기도 편해진다. 22%

41 이 책을 되돌아보며 1장 0이야기 10% 2장 논리 3장 나머지 4장 수학적 귀납법 5장 순열과 조합 22% 6장 재귀
7장 지수적 폭발 8장 계산할 수 없는 문제 9장 프로그래머 수학이란? 78% 22% 10% 22% 78%

42 ‘논리’는 둘로 나누기 문제를 하나의 커다란 덩어리로 풀지 말고 작게 나눠 풀어라 논리는 자연어의 애매함을 피하는 도구이다.
22%

43 이 책을 되돌아보며 1장 0이야기 10% 2장 논리 3장 나머지 4장 수학적 귀납법 5장 순열과 조합 22% 6장 재귀
7장 지수적 폭발 8장 계산할 수 없는 문제 9장 프로그래머 수학이란? 78% 22% 10% 22% 78%

44 ‘나머지’로 그룹화 문제 대상이 무한히 많은 경우 주기성을 발견하면 적은 개수의 문제로 바꿔 풀 수 있다.
나머지를 잘 사용하면 그룹화를 이용해 문제를 간단히 풀 수 있다. 22%

45 이 책을 되돌아보며 1장 0이야기 10% 2장 논리 3장 나머지 4장 수학적 귀납법 5장 순열과 조합 22% 6장 재귀
7장 지수적 폭발 8장 계산할 수 없는 문제 9장 프로그래머 수학이란? 78% 22% 10% 22% 78%

46 ‘수학적 귀납법＇은 2단계로 무한에 도전한다. 수학적 귀납법은 반복(순환)으로 문제를 푸는 기초가 된다. 22%

47 이 책을 되돌아보며 1장 0이야기 10% 2장 논리 3장 나머지 4장 수학적 귀납법 5장 순열과 조합 22% 6장 재귀
7장 지수적 폭발 8장 계산할 수 없는 문제 9장 프로그래머 수학이란? 78% 22% 10% 22% 78%

48 ‘순열과 조합＇에서는 대상의 성질을 파악하는 것이 중요하다
대상의 성질을 조사하여 이를 일반화하는 방법을 이용하면 직접 셀 수 없는 것들을 셀 수 있다. 22%

49 이 책을 되돌아보며 1장 0이야기 10% 2장 논리 3장 나머지 4장 수학적 귀납법 5장 순열과 조합 22% 6장 재귀
7장 지수적 폭발 8장 계산할 수 없는 문제 9장 프로그래머 수학이란? 78% 22% 10% 22% 78%

50 ‘재귀’는 자신 안에서 자신을 발견하는 것 커다란 문제에 직면했을 때, 재귀적인 구조를 발견한다면 점화식을 사용하여 문제의 성질을 조사할 수 있다. 22%

51 이 책을 되돌아보며 1장 0이야기 10% 2장 논리 3장 나머지 4장 수학적 귀납법 5장 순열과 조합 22% 6장 재귀
7장 지수적 폭발 8장 계산할 수 없는 문제 9장 프로그래머 수학이란? 78% 22% 10% 22% 78%

52 ‘지수적 폭발’이란 지수적 폭발을 포함한 문제는 약간의 규모만 커져도 다룰 수 없을 정도로 되지만,
지수적 폭발을 적절하게 사용하면 큰 규모의 문제를 다루기 쉽게 바꿀 수 있다. 22%

53 이 책을 되돌아보며 1장 0이야기 10% 2장 논리 3장 나머지 4장 수학적 귀납법 5장 순열과 조합 22% 6장 재귀
7장 지수적 폭발 8장 계산할 수 없는 문제 9장 프로그래머 수학이란? 78% 22% 10% 22% 78%

54 ‘계산할 수 없는 문제＇는 원리적인 제한을 나타낸다.
컴퓨터로 풀 수 있는 문제는 무한하지만 기껏해야 셀 수 있는 문제의 집합이다. 모든 문제는 셀 수 있는 문제보다 훨씬 큰 풀 수 없는 무한한 문제들이 존재한다. 22%

55 프로그래머에게 고도의 수학적 지식을 요구할 때는 그리 많지 않다.
하지만 문제의 구조를 파악하고 그것을 간단하게 표현하여 규칙을 정리할 때 기본적인 수학적 지식들이 기본 베이스가 된다. 22%

56 THANK YOU