이산수학문제9 이산수학 13. 확률계산을 위한 기초, 조건부 확률 안녕하세요 블레이즈 테크노트 블레이즈 입니다. 첫 번째 문제는 간단한 조합 활용 문제입니다. 로또에서 6개의 정수 중 하나도 맞지 않을 때의 확률을 구하시오. 단 순서는 중요하지 않다. 다음의 주어지는 숫자는 각 로또에서 뽑을 수 있는 숫자의 최댓값이다. a) 40 b) 48 c) 56 d) 64 두 번째 문제는 수학적 귀납법을 이용한 증명 문제입니다. 만약 E1, E2, . . . , En 이 샘플 스페이스 S에서 동시에 일어날 수 없는 n pairwise disjoint events 의 순서라고 하자. (n은 양의 정수) 다음이 성립함을 증명하시오. 세 번째 문제는 조건부확률 문제입니다. E1 과 E2 은 각각 w1 와 w2라는 단어를 포함하고 있는 받은 메일이다. E1 과 E2 이 독립이고 E1 |.. 2023. 7. 22. 이산수학 12. 이항정리 증명과 중복이 있는 조합 안녕하세요 블레이즈 테크노트의 블레이즈입니다. 오늘은 이항정리에 대해서 공부해보려고 합니다. 이항정리는 어떻게 보면 제곱식의 전개를 예측할 수 있는 정리입니다. 이 이항정리를 증명해보는 것이 오늘의 문제입니다. 저는 수학적 귀납법을 이용해 증명했습니다. 다음은 조합에 대한 다양한 문제 상황에 대한 문제입니다. 5개의 공을 3개의 박스에 나누는 방법이 몇가지인지 구하시오. 단, 모든 박스는 최소 1개의 공을 담고 있어야 한다. a) 공과 상자에 모두 이름표가 있을 때 b) 공은 이름표가 있지만 상자는 구분할 수 없을 때 c) 공은 구분할 수 없고 상자는 이름표가 있을 때 d) 공과 상자 모두 구분할 수 없을 때 감사합니다. 블레이즈 테크노트 2023. 7. 12. 이산수학 11. 조합적 증명과 개수 세기(Counting) 안녕하세요 블레이즈입니다. 조합적 증명은 조합적 논증이라고도 합니다. 하나의 문제 상황을 두 개의 스토리 라인으로 푸는 방식이라고 보면 되는데요, 아래의 1번 문제를 보시면 이해가 편할 것 같습니다. 첫 번째 문제입니다. 조합적 증명으로 풀이하라고 해서 그 방식으로 풀어봤습니다. 저는 이렇게 목표를 먼저 쓰고 풀이하는 걸 선호합니다. n명으로 구성된 위원회를 만들어야 하는데 위원회장은 반드시 수학교수이가 되려면 그 경우의 수는 총 몇가지일까요? 이를 두 개의 방법으로 풀어보겠습니다. 첫 번째 방법은 위원회에 포함될 수학 교수의 인원수 먼저 정하고 나머지 인원을 컴퓨터공학과 교수 중 뽑는 방법입니다. 이 때, 수학 교수가 k 명이라면 위원회장을 뽑을 경우의 수는 k가 되겠죠. 두 번째 방법은 위원회장이 될.. 2023. 7. 11. 이산수학 10. 재귀 알고리즘과 개수 세기(Counting) 안녕하세요 블레이즈입니다. 첫 번째 문제입니다. 이 문제는 비트 문자열을 뒤집는 재귀적 알고리즘을 짜보는 문제입니다. 두 번째 문제입니다. 이 문제는 상당히 어려웠습니다. 파티에 온 사람들 중 지인의 수가 동일한 사람이 최소 두 명 이상 존재하는지 증명하는 문제입니다. 감사합니다. 블레이즈의 테크 노트. 2023. 7. 10. 이산수학 8. 시간 복잡도, 계산 복잡도, 알고리즘 복잡도(Time Complexity, Complexity of Algorithms) 안녕하세요 블레이즈입니다. 첫 번째 문제입니다. 첫 번째 문제는 시간복잡도 문제의 증명이네요. n log n 가 O(log n!) 임을 증명하기. 두 번째 문제입니다. 두 번째 문제는 알고리즘 복잡도 문제입니다. 알고리즘을 보고 이 알고리즘의 계산복잡도가 어느 정도인지 확인해보는 것입니다. while 문의 조건을 확인하기 위한 비교는 제외하고 다음의 알고리즘에서 수행된 더하기/곱하기 연산의 횟수를 big-O 로 나타내기. i := 1 t := 0 while i ≤ n t := t + i i := 2i 감사합니다. 블레이즈 테크 노트 Blaze Tech Note 2023. 7. 8. 이산수학 7. 행렬 매트릭스 안녕하세요 블레이즈입니다. 첫 번째 문제입니다. m과 n이 양의 정수이고 x가 실수일 때 다음이 성립함을 증명하기. 두 번째 문제입니다. 이런 류의 문제는 일단 해보고 패턴을 발견하는 게 편하더라고요. 세 번째 문제입니다. 이 문제는 증명 문제네요. A가 2×2 matrix 이고 모든 2x2 행렬인 B에 대하여 AB = BA가 성립하면 A=cI 가 성립함을 보이기. (c is a real number and I is the 2 × 2 identity matrix) 감사합니다. 블레이즈 테크 노트 Blaze Tech Note 2023. 7. 7. 이산수학 6. 함수 전단사, 점화식, 수열과 수열의 합 안녕하세요 블레이즈 입니다. 이번 포스팅에서는 이산수학에서 사용하는 함수의 정의와 활용에 대해서 공부해보겠습니다. 첫 번째 문제입니다. 이 문제는 함수가 실수에서 실수로 정의된 전단사 함수(bijection)임을 확인하는 문제입니다. a) f(x)=−3x+4 b)f(x)=−3x2+7 c) f(x)=(x+1)/(x+2) d) f(x)=x5+1 정의역에서 문제가 없고 순수하게 증가만 하는 함수는 bijection임이 당연해서 특별히 증명은 하지 않았습니다. 두 번째 문제입니다. 두 번째 문제는 첫 해 연봉이 5만 달러인 직원의 차후 연봉에 대해 예상해보는 문제입니다. 점화식(recurrence relation)으로 연봉을 나타내보라는 것 같네요. "한 직원이 2009년에 연봉 5만 달러로 입사했다. 매년 연.. 2023. 7. 6. 이산수학 5. 명제논리 이산수학의 증명 문제(Proof Methods and Strategy) 안녕하세요 블레이즈입니다. 오늘은 이산 수학에서 자주 볼 수 있는 간단한 증명 문제 풀이를 해보고자 합니다. 증명에서 사용할 수 있는 전략이 몇 가지 있는데 이번 포스팅은 이 증명 전략을 활용해볼 것입니다. 첫 번째 문제입니다. 첫 번째 문제는 가정을 통해 원하는 결과를 도출해내는 전략입니다. if x is rational and x ≠ 0, then 1/x is rational 임을 증명하기 QED는 증명 완료라는 의미입니다. 두 번째 문제입니다. 두 번째 문제는 반례를 제시해서 주어진 statement가 거짓임을 보이는 전략입니다. 다음의 문장이 거짓임을 증명하기. Every positive integer can be written as the sum of the squares of three int.. 2023. 7. 5. 이산수학 4. 명제논리 중첩된 한정기호(Nested Quantifiers)와 추론 규칙(Rules of Inference) 안녕하세요 블레이즈입니다. 오늘은 먼저 한정 기호가 중첩된 경우에 대해서 공부해보고 추론 규칙을 이어서 알아보겠습니다. 먼저 Nested Quantifiers, 중첩된 한정 기호 문제입니다. 첫 번째 문제는 L(x, y) 라는 술어를 사용해서 문장을 표현하는 것입니다. L(x, y) 가 “x loves y,” 라고 하자. x와 y의 정의역은 모두 전 세계 모든 사람이다. a) Everybody loves Jerry. b) Everybody loves somebody. c) There is somebody whom everybody loves. d) Nobody loves everybody. e) There is somebody whom Lydia does not love. f) Thereissomebod.. 2023. 7. 4. 이전 1 다음
