Big O notation의 정의는 알고 쓰자

1. little O notation 두 함수 f(x)와 g(x)가 어떤 a에 대하여 $$\left| f(x) \right| \leq \varepsilon g(x)$$ 를 만족하는 모든 양의 상수 $\varepsilon $ 이 $0< \left| x-a \right| < \delta$에서 존재하게 하는 $\delta $가 존재한다면, $$f(x) = o(g(x))$$ x →a 라고 표현한다. 동일한 말로 g(x)가 0이 아닐때, $$f(x) = o(g(x))$$ x →a 는 $$\displaystyle \lim_{ x \to a} \frac{f(x)}{g(x)} = 0$$과 동치이다. 근데 일단 이거는 그냥 극한으로 이해하는게 편한것 같다 2. 직관적인 이해 $$\displaystyle \lim_{ x ..

• format_list_bulleted 프로그래밍/프로그래밍 개론
• · 2022. 9. 16.
• textsms

증명하기 연습문제3

1. 52개의 카드를 이용해서 만들 수 있는 5개 카드 조합 중 같은 무늬의 카드가 정확히 3개인 경우의 수 52개의 카드에는 4가지 무늬가 존재하는데, 그러한 4가지 무늬중 같은 무늬로 만들 3개의 카드를 구성하기 위한 무늬를 고르는 경우의 수는.. $\binom{4}{1}$ 선택한 무늬에서 3개의 카드를 선택하는 경우의 수는.. 13가지 중에서 3장을 뽑아야하므로 $\binom{13}{3}$ 나머지 2장은 다른 무늬의 카드에서 골라야한다. 남은 3가지 무늬 중에서 2가지를 뽑는 방법의 수는$\binom{3}{2}$이고, 각각의 무늬에서 1장씩 뽑아야 정확히 3장만 같은 무늬를 가진다. $\binom{13}{1}\binom{13}{1}$ 따라서, $\binom{4}{1}\binom{13}{3}\bino..

• format_list_bulleted 프로그래밍/프로그래밍 개론
• · 2022. 9. 15.
• textsms

증명하기 연습문제2

1. 진리표를 이용해서 항진명제임을 증명 (~p∨q)∨(p∧~q) 진리표를 그려보면 다음과 같다 p,q의 모든 경우에 True이므로 (~p∨q)∨(p∧~q)은 항진명제이다. 2. 진리표를 이용해 모순명제임을 증명 (p∧q)∧(p∧~q) p,q의 모든 경우에 False이므로 (p∧q)∧(p∧~q)은 모순명제이다. 3. 다음 명제의 쌍들이 논리적으로 동등한지 진리표를 이용해 확인 ~p∨~q와 ~(p∨q) p,q의 어떤 경우에 대하여 위 그림과 같이 진리값이 서로 다르므로 ~p∨~q와 ~(p∨q)는 논리적으로 동등하지 않다 4. 명제식의 변형으로 다음 명제를 간소화 (p∨~q)∧(~p∨~q) 분배법칙으로부터 ~q를 이용해 묶으면 (p∨~q)∧(~p∨~q) = (p∧~p) ∨ (~q) 그런데 (p∧~p)는 p가..

• format_list_bulleted 프로그래밍/프로그래밍 개론
• · 2022. 9. 15.
• textsms

귀류법과 수학적 귀납법 정확히 알기

1. 증명 19세기 말부터 증명이 무엇인지 많은 연구가 있었다 증명은 글로 쓰는 것이 아니라 '정확한 명제로 표현할 수 있는 것'이라는 것이 확립된 상태 보통 정확한 명제식으로 쓰지는 않지만 근본적으로는 명제식으로 바꿀 수 있는 것이 증명이다 증명에 대한 수많은 오해는 p ↔ q 와 p → q를 혼동하는 것에서 시작함 2. 당구공 paradox '모든 당구공은 색이 같다'에 대한 증명 당연히 색이 같을리 없지만 논리적으로 증명하고자 함 ------------------------------------------------------------------------------------------------------------ 수학적 귀납법) 모든 자연수 n에 대해 명제 P(n)이 참이라는 것을 증명하기..

• format_list_bulleted 프로그래밍/프로그래밍 개론
• · 2022. 7. 13.
• textsms

논리학 연습문제1

1. 문제1 1) p: 0이 홀수이다, q: 미국에서 2080년 월드컵이 열린다. 명제식: p → q 참,거짓: '미국에서 2080년 월드컵이 열린다'라는 사실은 아무도 알 수없다 하지만 '미국에서 2080년 월드컵이 열린다'가 사실인지 몰라도 전체 p → q가 사실인지 아닌지는 알 수 있다 왜냐하면 p: 0이 홀수이다에서 0은 홀수가 아니므로 p는 반드시 거짓이다 가정인 p가 거짓이면 전체 p → q는 q의 참,거짓 여부에 관계없이 반드시 참이다 이를 많은 사람들이 받아들이지 못하지만 p → q가 참이어야 제대로 된 논리학을 만들 수 있다 https://deepdata.tistory.com/331 반드시 알아야하는 기초 논리학 - p가 거짓이면 'p이면 q이다'는 왜 참인가? 1. 공허한 참 'p이면 ..

• format_list_bulleted 프로그래밍/프로그래밍 개론
• · 2022. 7. 12.
• textsms

반드시 알아야하는 기초 논리학 - p가 거짓이면 'p이면 q이다'는 왜 참인가?

1. 공허한 참 'p이면 q이다'라는 명제가 있을 때 일반적으로 p가 참이라고 생각하고 q의 참, 거짓을 통해 'p이면 q이다'가 참인지 거짓인지 파악한다 그러니까 p가 참이면 q가 참일때 'p이면 q이다'는 참이고 q가 거짓이면 'p이면 q이다'는 거짓이다 그렇다면 p가 거짓이면 어떤가? 'p이면 q이다'는 어떻게 파악하는가? 결론부터 말하면 p가 거짓이면 q의 참,거짓과 무관하게 'p이면 q이다'는 반드시 참이다. 이것을 공허한 참이라고 부른다 2. 사람들이 이야기하는 직관적인 이유 2-1) 내가 너에게 '이번 시험에 100점을 맞으면 치킨을 사주겠다'라고 약속을 함 100점을 받았는데, 치킨을 사줬다. >> 나는 약속을 지킴 100점을 받았는데, 치킨을 사주지 않았다 >> 나는 약속을 어김 100점..

• format_list_bulleted 프로그래밍/프로그래밍 개론
• · 2022. 7. 11.
• textsms