논리적 사고를 기르는 알고리즘 수업(2025.01.24)

논리적 사고를 기르는 알고리즘 수업

논리적 사고를 기르는 알고리즘 수업

Ch 15 ~ 15.5 연습문제 4

체크인 (기분/근황/기대하는 바)

• 성큼이
  • 하는 것 없이 분주한 느낌
  • 이것저것 변화가 많다
  • 진도 잘 뺐으면
• Wayne
  • 연휴라 좋다
  • 연초라 여유있게 지내는 중
  • 진도 잘 나갔으면
• 상호
  • 피곤
  • 좀 더 바빠짐
  • 정수론 잘 배웠으면

문제풀이

• 15.5 연습문제

1. 0을 곱하는 것이 이하 연산에 대해서 단조적인가? 미만 연산에 대해서는 단조적인가?

0을 곱하면 전부 0으로 같아지므로, 같은 걸 허용하는 이하 연산에 대해서는 단조적, 미만 연산에 대해서는 단조적이 아님

2. 규칙 (15.11)을 이용해 $\frac{1}{x} \leq \frac{1}{y}$를 간략하게 정리하라. 즉, 다음과 같은 형태의 규칙

​ $[(\frac{1}{x}\leq \frac{1}{y} \equiv ?) \impliedby ??]$

에, 나눗셈이 들어가지 않은 표현식 $?$와 $??$를 채워서 규칙을 완성하라

(15.11) [단조성] $[(x \times z \leq y \times z \equiv x \leq y) \impliedby 0 < z]$

에서 $x := \frac{1}{x}, y := \frac{1}{y}, z := xy$를 각각 대입해 정리하면

$[(\frac{1}{x}\leq \frac{1}{y} \equiv y \leq x) \impliedby 0 < xy]$

3. 다음을 간략화하라. 계산의 각 단계에서 어떤 규칙을 쓰는지 명확히 서술하라

(a) $n - \frac{1}{2}m \leq m - \frac{1}{2}n$

(b) $n - m < \frac{1}{2}(m - \frac{1}{2}n)$

(a) $n - \frac{1}{2}m \leq m - \frac{1}{2}n$

= { (15.9) 단조성. ($\frac{1}{2}m + \frac{1}{2}n$을 더함) }

$n + \frac{1}{2}n \leq m + \frac{1}{2}m$

= { 덧셈에 대한 곱셈의 분배법칙 }

$\frac{3}{2}n \leq \frac{3}{2}m$

= { (15.11) 단조성. ($\frac{2}{3}$을 곱합)}

$ n \leq m $

(b) $n - m < \frac{1}{2}(m - \frac{1}{2}n)$

= { (15.12) 단조성. ($4$를 곱함), 분배법칙}

$4n - 4m < 2m - n$

= { (15.10) 단조성 ($4m + n$을 더함), 분배법칙}

$5n < 6m$

4. 다음을 증명하라.

$[(k \times m + r < j \times m \equiv k < j) \impliedby 0 \leq r < m]$

$0 \leq r$

= { (15.9) 단조성 }

$k \times m \leq k \times m + r$

$k \times m + r < j \times m$

= $k \times m \leq k \times m + r < j \times m$

= $k \times m < j \times m$

= { (15.12) 단조성. ($0 \leq r < m$에서 $0 < m$) }

$k < j$

회고 (좋았던 점/ 아쉬웠던 점/ 다음주 이 시간까지 할 일)

• 성큼이
  • 15장을 다 봤다
  • 크게 없다
  • 4번문제 완성하겠다
• Wayne
  • 진도 많이 나갔다
  • 딱히 없다
  • 일이 있어서 다다음주에 오겠다
• 상호
  • 풀 수 있는 문제가 있었다
  • 중간에 좀 졸렸다
  • 잘 쉬다 오겠다

나머지 공부