Discrete mathmatics and Problem Solving
-
6 경우의 수 (곱셈 규칙)Discrete mathmatics and Problem Solving/6, 8 경우의 수와 그 응용(dp) 2017. 10. 9. 03:03
경우의 수영어로는 Counting이다. 수 세기. 셈법. 조합론. 등 으로도 불린다. 조합론은 무엇인가?1 무엇보다 이산수학에서 굉장히 중요한 분야 중 하나다.2 비교적 최근 수학이다. 17세기 즈음에 도박 확률 문제와 연관되어 정립되었다.3 주로 특정 상태의 어떤 것들을 세는데 사용한다. 예) 2개 이상 연속하는 0을 포함하지않는 0과 1로만 이루어진 n길이의 문자열 갯수는?4 이론적인 곳 외에도 굉장히 다양한 곳에서 사용된다.예) 알고리즘의 복잡도 구하기, IP 수요와 그 할당의 문제, DNA 염기서열 등등의... 앗 복잡해 어찌됐든 알아보기로 하자... 경우의 수 기초컴퓨터를 사용할 때 패스워드를 생성하는 것을 생각해보자. 패스워드를 생성하는데 최소 1개의 숫자를 포함해야하고 최대 8자의 소문자 알..
-
3.1 알고리즘 탐색과 정렬Discrete mathmatics and Problem Solving/3 알고리즘 2017. 10. 1. 16:14
이전글 보기 알고리즘 Introduction + 알고리즘의 특징http://ingyeoking13.tistory.com/75 Contents탐색알고리즘 (순차탐색, 이진탐색) 정렬알고리즘 (버블정렬, 삽입정렬) 탐색 알고리즘Searching Algorithms정렬된 리스트에서 어떤 원소를 찾는 문제는 많은 상황에서 발생합니다. 예로, 사전같이 순서대로 정렬되어있는 단어 리스트들 중에서 단어 탐색을 하기위해 스펠링을 체크하는 프로그램이 있습니다. 이런 류의 문제들은 탐색 문제searching problems 입니다. 우리는 이 섹션에서 탐색을 위한 몇 몇 알고리즘들에 대해 논의할 것입니다. 일반적인 탐색 알고리즘은 다음과 같이 서술될 수 있습니다. 각 각 다른 원소들 a1, a2, .... , an 의 리..
-
백준 어린왕자Discrete mathmatics and Problem Solving/1 논리 2017. 9. 23. 00:59
*문제 https://www.acmicpc.net/problem/1004 이 문제는 논리기호를 이용해 굉장히 간단히 접근할 수 있다. 출발지점과 도착지점이 해당 원에 동시에 안에 있거나 동시에 바깥에 있다면 해당 원에 진입하지 않아도 된다. 둘 중 단 하나가 포함되어 있을 때의 경우는 진입을 따져야한다.이는 구조상 논리기호 XOR과 같다. 따라서 다음과 같이 가능하다.if " 출발 지점이 원 1에 포함되어있나? xor 도착 지점이 원 1에 포함되어있나? " then answer++; *소스코드 보기https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/p1004.c
-
Foundation : predicate logic and quantifiersDiscrete mathmatics and Problem Solving/1 논리 2017. 1. 16. 04:25
오랜만의 포스팅입니다. 이 포스팅을 완료하고 공개로 전환한것이 2월 7일이니까... 포스팅을 같이하면서 미적분책을 독학하는데 첫 장부터 무리수를 도출하는 방법인 바빌로니아 메서드와 무리수와 관련된 증명 문제, 그리구 포물선과 관련된 기하학 문제를 푸는데 그리고 여러가지 고민거리를 안고 지내다가 ( precalculus...고등학교 1학년문젠데 막히니까 고민거리가 생길수 밖에요) 새벽에 삘 받아서 완성하게 되었습니다. 크,,, 아무 금전적 보상도 없지만 열심히하는 클라쓰,,,수학 원리에서... *이번 토막문은 본문 포스팅과 내용이 중복되고 길지만, 다 해치우고 싶은 저의 욕심입니다 ㅎ.....propositional function 명제 함수ϕx를 변수 x를 포함하는 진술이라고 하자. 이 명제는 x가 어떤..
-
Answers : propositions and logical operation, equivalencesDiscrete mathmatics and Problem Solving/1 논리 2017. 1. 15. 04:20
1 a) 명제, 참 b) 참, 거짓을 가릴 수 없는 진술이므로 명제가아니다. c) 이는 명제 함수propositional function이다. 변수variable에 값이 지정되지 않으므로 참, 거짓을 가릴 수 없다. 따라서 명제가 아니다. d) 명제, 참2 a) 민수 또는 민환은 나의 친구가 아니다. b) 주환의 가방에는 책이 3권이 있지 않다. c) 121은 11의 제곱이 아니다.3 a) 나는 이번 주 복권을 사지 않았다. b) 나는 이번 주 복권을 샀거나 1등 상금을 얻었다. c) 나는 이번 주 복권을 샀다면, 1등 상금을 얻었다. d) 나는 이번 주 복권을 샀고, 1등 상금을 얻었다. e) 나는 이번 주 복권을 샀다면, 1등 상금을 얻었다. 그리고 1등 상금을 얻었다면, 이번 주 복권을 산것이다. ..
-
Exercises : propositions and logical operation, equivalencesDiscrete mathmatics and Problem Solving/1 논리 2017. 1. 13. 00:45
수학 원리에서...1.01 p→q = ~p∨q Df.앞으로 "Df"의 단어는 정의를 뜻한다. 이 단어와 같다라는 기호 equal symbol은 왼쪽 항의 복합명제가 우항의 복합명제를 의미한다고 정의한다. 즉, 정의되는 것은 왼쪽 항이다. 우리는 가장 단순한 논리연산자 부정형negation과 논리합disjunction을 기초로 사용하기 때문이다. 조건문의 필요성은 다음에 의해 기인한다. "한 명제 p가 참일 때 그것이 의미하는 q가 반드시 참이여야 한다." 조건문은 증명에 반드시 필요하다. 그러나 어떠한 명제 p가 거짓일 때 그것이 의미하는 어떠한 것들에 대해서 진리값을 판단하려는 의미는 아니다. 그러므로, p가 참일 때 q가 거짓일 때만 거짓이라고 판단한다. p가 거짓이거나 q가 참일때는 항상 참이다. ..
-
Handbook : propositions and logical operation, equivalencesDiscrete mathmatics and Problem Solving/1 논리 2017. 1. 11. 15:03
사실은...기호논리학의 또 다른 거장, 버트런드 러셀Bertrand Russell와 화이트 헤드Whitehead는 그들의 공동 저서 수학원리principia mathematica에서 세상의 수학들을 기호논리로 다루려고 노력했습니다. 그들은 수학원리에서 다음과 같이 기호논리를 사용합니다.논리곱logical product은 . 로 표현했습니다. 따라서 p.q는 "p and q"를 뜻합니다. 그러나 때로 .는 괄호parentheses를 표현하기도 하는데요. 다음의 명제를 봅시다.⊦ :p∨q.⊃.q∨p우선, ⊦ 는 다음이 반드시 참이라고 주장하는 것입니다. 이는 정리theorem 이거나 공리axiom일 수 있습니다. 그리고 :는 . 보다 한 단계 더 높은 중괄호라고 봅니다. ⊦ [p∨q.⊃.q∨p]⊦ 이후의 콜..