1. Analyzing Algorithms and Problems: Principles and Examples
1-2. Mathematical Background 수학적배경지식
Analysis Tool: Mathematics
- series: 숫자들의 나열(sequence)의 합
- Arithmetic series: 연속적으로 증가하는 정수들의 합
- Polynomial Series 다항식 시리즈
-The sum of squares
-The general case is
- Power of 2
-Arithmetic-Geometric Series
Analysis Tool: Logic(논리학)
Logic: 더 명확한 추론을 위해 자연어를 formalizing(수학적으로 형식화)하는 시스템
A ⇒ B
- A implies B (if A then B)
- 만약 A가 참이면, B 역시 참이다
- ￢ A ∨ B(not A or B)와 동치
| A | B | A ⇒ B | ￢ A | ￢ A ∨ B |
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
- implies 추가 설명
imply는 수학에서 번역할때에는 '내함한다, 내포한다'로 해석하는데요
내함이란, 그 의미가 함께 포함되어있다는 뜻입니다. 함께 포함되어 있다는 뜻은 그림으로 나타내면 다음과 같습니다.
이는 A가 B에 포함된 경우인데요, A가 B에 포함되었다는 것은 A에 이미 B라는 개념이 꽉 차 있다는 의미이고, 반대로 B에는 A가 꽉 차있는 경우는 아닙니다. 이와 같이 A라는 개념에 B라는 개념이 동시에 차있는 경우를 내함이라하고, 이 경우 imply를 쓰는 것입니다.
즉, A라는 개념이 참인 모든 경우 언제나 B가 참임을 나타내는 상황을 의미하기 때문에 이는 A -->B를 이와 같이 나타내는 것입니다.
￢ (A ∧ B)
- 드모르간 법칙에 의해, ￢ A ∨ ￢ B와 동치
￢ (A ∨ B)
- ￢ A ∧ ￢ B와 동치
Proof (증명방법)
Counterexample(반례): 명제가 틀린 실제 예시를 제시
Contraposition(대우): p → q ⇔ ~q → ~p
Contraadiction(모순/귀류법): ￢(￢p), 일단 결론을 부정한 뒤 모순을 찾아가는 방법
Mathematical Indution(수학적 귀납법)
자료 출처
Computer Algorithms
(Sara Baase, Allen Van Gelder저, Addison Wesley, 2000)
'Computer Science > 알고리즘' 카테고리의 다른 글
| 알고리즘: Mergesort 합병 정렬 (0) | 2021.11.11 |
|---|---|
| 알고리즘6. Searching on Ordered Array(정렬된 배열 탐색)(2) - binary search(이진탐색) (0) | 2021.10.03 |
| 알고리즘5. Searching on Ordered Array(정렬된 배열 탐색)(1) (0) | 2021.09.27 |
| 알고리즘4. 점근적 증가율에 따른 함수 분류 (0) | 2021.09.13 |
| 알고리즘3. 알고리즘과 문제 분석 (0) | 2021.09.07 |
| 알고리즘 1. Problem Solving의 절차 (0) | 2021.09.02 |