이산수학문제풀이4 이산수학 11. 조합적 증명과 개수 세기(Counting) 안녕하세요 블레이즈입니다. 조합적 증명은 조합적 논증이라고도 합니다. 하나의 문제 상황을 두 개의 스토리 라인으로 푸는 방식이라고 보면 되는데요, 아래의 1번 문제를 보시면 이해가 편할 것 같습니다. 첫 번째 문제입니다. 조합적 증명으로 풀이하라고 해서 그 방식으로 풀어봤습니다. 저는 이렇게 목표를 먼저 쓰고 풀이하는 걸 선호합니다. n명으로 구성된 위원회를 만들어야 하는데 위원회장은 반드시 수학교수이가 되려면 그 경우의 수는 총 몇가지일까요? 이를 두 개의 방법으로 풀어보겠습니다. 첫 번째 방법은 위원회에 포함될 수학 교수의 인원수 먼저 정하고 나머지 인원을 컴퓨터공학과 교수 중 뽑는 방법입니다. 이 때, 수학 교수가 k 명이라면 위원회장을 뽑을 경우의 수는 k가 되겠죠. 두 번째 방법은 위원회장이 될.. 2023. 7. 11. 이산수학 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. 이전 1 다음
