분류 전체보기50 이산수학 10. 재귀 알고리즘과 개수 세기(Counting) 안녕하세요 블레이즈입니다. 첫 번째 문제입니다. 이 문제는 비트 문자열을 뒤집는 재귀적 알고리즘을 짜보는 문제입니다. 두 번째 문제입니다. 이 문제는 상당히 어려웠습니다. 파티에 온 사람들 중 지인의 수가 동일한 사람이 최소 두 명 이상 존재하는지 증명하는 문제입니다. 감사합니다. 블레이즈의 테크 노트. 2023. 7. 10. 이산수학 9. 정렬성 원리(well ordering property), 재귀함수(Recursive functions) 안녕하세요 블레이즈입니다. 이번 포스팅에서는 정렬성 원리와 재귀적으로 정의된 함수에 대해서 알아보도록 하겠습니다. 첫 번째 문제는 모든 양의 정수 k와 n에 대하여 아래의 식이 성립함을 보이는 것입니다. 저는 정렬성 원리(well ordering property)를 사용해보겠습니다. 두 번째 문제입니다. 이 문제는 비트 문자열을 재귀적으로 정의해보는 문제입니다. 1보다 0이 많은 비트 문자열을 재귀적으로 정의하기. 세 번째 문제입니다. 이 문제는 재귀적으로 정의된 함수에 대해서 일반항을 구해야 하네요. f (n) 은 다음을 만족한다. f(n) < f(m) when n < m f(k)가 다음과 같이 재귀적으로 정의되어 있다. c가 양의 실수일 때, f c∗ 는 그 값이 c 이하가 되기 위해 반복되어야 하는.. 2023. 7. 9. 이산수학 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. 이산수학 3. 명제논리 술어(Predicates)와 한정 기호(Quantifiers) 안녕하세요 블레이즈 테크노트의 블레이즈입니다. 이번 포스팅에서는 명제 논리 중 술어(Predicates)와 한정 기호(Quantifiers)에 대해 알아보도록 하겠습니다. 첫 번째 문제는 술어를 한정기호와 논리 연산 기호(logical connectives)로 표현하는 것입니다. C(x)를 “x has a cat,” D(x) 를 “x has a dog,” F (x) 를 “x has a ferret.” 라고 하겠습니다. 정의역이 교실의 모든 학생이라고 할 때, 다음의 문장을 C(x), D(x), F(x), quantifiers, logical connectives를 사용해 나타내보겠습니다. a) A student in your class has a cat, a dog, and a ferret. b) All.. 2023. 7. 3. 이산수학 2. 명제 논리의 응용, 동치(equivalence)와 만족가능성(satisfiability) 안녕하세요 블레이즈 입니다. 지난 포스팅에서 명제 논리를 공부했습니다. 이번 포스팅에서는 명제 논리의 좀 더 심화 개념을 알아보도록 하겠습니다. 먼저 첫 번째 문제는 You can graduate only if you have completed the requirements of your major and you do not owe money to the university and you do not have an overdue library book. 라는 문장이 있을 때 이 문제를 명제와 기호로 표현해보는 것입니다. g를 “You can graduate,” m을 “You owe money to the university,” r을 “You have com- pleted the requirements o.. 2023. 7. 2. 이산수학 1. 명제 논리의 역, 대우, 이 와 진리표 그리기 안녕하세요 블레이즈입니다. 이산수학은 컴퓨터 프로그래밍 과정에서 기초가 되는 학문입니다. 명제 논리는 p이면 q이다 와 같은 문장을 뜻하는데요 이러한 논리 관계를 잘 알면 아무래도 좋을 것입니다. 문제와 함께 알아보도록 하겠습니다. 첫 번째 문제는 해당 영어 문장이 inclusive or 인지, exclusive or 인지 판별하고 그 이유를 설명하는 문제입니다. 두 번째 문제는 조건문(conditional statement)에 대하여 역(converse)과 대우(contrapositive), 이(inverser)를 적어보는 문제입니다. a) If it snows today, I will ski tomorrow. b) I come to class whenever there is going to be a .. 2023. 7. 1. 이전 1 2 3 4 5 다음
