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

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

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

Ch 14.3 ~ 14.5 문제 5

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

• 성큼이
  • 좋은 편
  • 조금 한가함
  • 진도 잘 뺐으면
• 상호
  • 살짝 피곤
  • 업무가 많아져서 바쁨
  • 잘 따라갔으면
• Wayne
  • 무난
  • 특별한 일 없음
  • 진도 잘 나갔으면

문제풀이

1. 다음 합을 계산하라

(a) $\braket{\sum k : 1 \leq k \leq 3 : k}$

(b) $\braket{\sum k : 0 \leq k < 5 : 1}$

(c) $\braket{\sum i, j : 0 \leq i < j \leq 2 \land odd(i): i + j}$

(d) $\braket{\sum i, j : 0 \leq i < j \leq 2 \land odd(i) \land odd(j) : i + j}$

(a) $1 + 2 + 3 = 6$

(b) $5$

(c) $i = 1, j = 2$ 인 경우 하나 뿐이므로 $3$

(d) 조건을 만족하는 경우가 존재하지 않으므로 $0$

2. 다음 두 가지 경우에서, $\braket{\sum k : k^2 = 4 : k^2}$의 값을 계산하라.

(a) $k$의 자료형이 자연수일 때

(b) $k$의 자료형이 정수일 때

(a) 자연수 범위에서는 $k \in \set{2}$ 이므로 $4$

(b) 정수 범위에서는 $k \in \set{-2, 2}$ 이므로 $4 + 4 = 8$

3. 다음 표현식에서 독립변수를 모두 나열하라.

(a) $ 4 \times i $

(b) $\braket{\sum j : 1 \leq j \leq 3 : 4 \times i}$​

(c) $\braket{\sum j : 1 \leq j \leq 3 : 4 \times j}$

(d) $\braket{\sum j : 1 \leq j \leq 3 : m \times j} \times \braket{\sum j : 1 \leq j \leq 3 : n \times j}$

(e) $\braket{\sum j : 1 \leq j \leq 3 : m \times j} \times \braket{\sum k : 1 \leq k \leq 3 : n \times j}$

(a) $i$

(b) $i$

(c) 없음

(d) $m, n$

(e) $m, n$

4. 다음 등식의 좌변과 우변을 계산하라. 등식 중 어떤 식은 항상 참이고, 어떤 식은 거짓이 될 수 있다. 그러한 식들을 구분하라.

(a) $\braket{\sum j: 1 \leq j \leq 3: 4 \times i} = \braket{\sum k: 1 \leq k \leq 3: 4 \times i}$

(b) $\braket{\sum j: 1 \leq j \leq 3: 4 \times j} = \braket{\sum k: 1 \leq k \leq 3: 4 \times j}$

(c) $\braket{\sum j: 1 \leq j \leq 3: \braket{\sum k: k = 0: 4 \times j}} = \braket{\sum i: 1 \leq i \leq 3: \braket{\sum k: k = 0: 4 \times i}}$

(d) $\braket{\sum j: 1 \leq j \leq 3: \braket{\sum j: j = 1: 4 \times j}} = \braket{\sum i=k: 1 \leq k \leq 3: \braket{\sum j: j = 1: 4 \times k}}$

(a) 항상 참

(b) 우변에서 $j$가 독립변수이므로 거짓이 될 수 있음

(c) 항상 참

(d) 우변의 안쪽 표현식에서 $k$가 독립변수이므로 거짓

5. 분리 규칙 (14.6)으로부터 거래 규칙 (14.10)을 유도하라. 가능한 모든 범위 $R$에 대해 $\braket{\sum k: R : 0} = 0$이 성립한다고 가정해도 된다.

$\braket{\sum k : Q : if P \rightarrow T \square \neg P \rightarrow 0 fi} $

= { (14.7) 에서 $P$ 와 $Q$를 바꿔서 적용 }

$\braket{\sum k : Q \land P : if P \rightarrow T \square \neg P \rightarrow 0 fi} + \braket{\sum k : Q \land \neg P: if P \rightarrow T \square \neg P \rightarrow 0 fi}$

= { term 안의 조건절 제거 }

$\braket{\sum k : Q \land P : T} + \braket{\sum k : Q \land \neg P:0}$

= { 논리곱의 교환법칙, 0의 합계는 0}

$\braket{\sum k : P \land Q : T} + 0$

= { 0 은 덧셈의 항등원 }

$\braket{\sum k : P \land Q : T}$

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

• 성큼이
  • 진도도 뺐고 문제도 반쯤 풀었다
  • 크게 없다
  • 잘 쉬다 오겠다
• 상호
  • 푼 문제도 있었다
  • 증명은 잘 안 된다
  • 잘 쉬다 오겠다
• Wayne
  • 진도 많이 나갔다
  • 증명은 어렵다
  • 잘 쉬고 오겠다

나머지 공부