[이산수학] Mathematical Thinking in computer Science 5주차

Summary.

• Invariants are important tools for proving impossibility, termination, and various bounds.
• 불변량은 불가능성, 종료 등의 문제를 해결하는데 중요한 도구이다.
• Invariants may take many forms: numbers, "parity", equations, inequalities.
• 불변량은 숫자, 패리티, 등호, 부등호 등 다양한 형태일 수 있다.
• To prove impossibility, one finds a quantity that never changes during a process.
• 불가능성을 증명하기 위해 과정 동안 바뀌지 않는 양을 찾는다.
• To prove that a process terminates in a number of steps, one usually finds a quantity that decreases at every step.
• 과정이 단계를 거쳐 종료됨을 증명하기 위해 매 단계마다 줄어드는 양을 찾는다.
• Double counting is a method that uses the sum invariant.
• 덧셈의 불변량을 찾기 위해 더블카운팅 방법을 사용한다.

 

coursera Introduction to Discrete Mathematics for Computer Science 과정 중

Mathematical Thinking in coumputer Science 4주차 내용 정리