패스트캠퍼스 한 번에 끝내는 컴퓨터 공학 전공 필수 Part2. 이산수학

강의 출처 : 패스트캠퍼스 한 번에 끝내는 컴퓨터 공학 전공 필수 & 인공지능 심화 초격차 패키지 Online

Part2. 이산수학

패스트 캠퍼스 컴퓨터 공학 전공 필수 패키지 강좌의 Part 2 에서는 이산수학 관련된 기초적 내용이 나와있다. 총 여덟 챕터로 구성되어있는데 과목의 특성상 이전에 알았던 개념은 빠르게 복습하고 내가 새롭게 정리가 필요한 내용 위주로 포스팅하려고 한다. Ch01. 집합과 논리, Ch02. 증명, Ch03. 함수,수열과 관계, Ch04. 알고리즘 까지 우선 들어보았다.

이산수학이란 ?

: 이산수학은 실수가 아닌 이산적인 값에 관련된 수학을 모두 다루는 포괄적인 개념이라고 한다. 따라서 누구한테 이산수학을 배웠는지에 따라 배운 내용이 많이 상이할 수도 있다고 한다. 컴퓨터에서 모든 값들은 결국 이산적으로 계산된다. 따라서 배우는 내용이 다 필요한 것은 아니겠지만 한번 점검하고 넘어가는게 좋을 것 같았다.

Ch01. 집합과 논리

: 집합 관련 주요 개념들 (중고등학교 때 배워서 기억나는 부분들은 우선 빠르게 넘어갔다)

• 원소나열법
• 조건제시법
• 벤 다이어그램
• 유한집합 / 무한집합
• 부분집합
• 합집합
• 교집합
• 서로소
• 차집합
• 여집합
• 집합의 법칙들

: 논리 관련 주요 개념들 (중고등학교 때 배워서 기억나는 부분들은 우선 빠르게 넘어갔다)

• 명제
• 명제의 부정 ~
• 논리곱 : ^ (and) ; 명제 p,q 에 대하여 p와 q 가 모두 참일 경우에만 참이고, 그렇지 않을 경우 거짓이 되는 명제
• 논리합 : ∨ (or) ; 명제 p,q 에 대하여 p와 q 가 모두 거짓일 경우에만 거짓이고, 그렇지 않을 경우 참이 되는 명제

이전에 코드에서 논리곱,논리합으로 간결하게 표시된 부분을 본 적이 있었는데 처음에 이해하기가 굉장히 햇갈렸어서 복습해보았다.

• 동치 관계 : 명제와 대우 , 역과 이
• 명제 함수 : P(x) ; 변수 x 를 포함하여 진리값을 판별할 수 있는 문장이나 수식. 따라서 인풋으로 들어가는 x 변수가 무엇이냐에 따라서 참이 될 수도 있고 거짓이 될 수도 있음. -> 이어지는 개념 : 전체한정자, 존재한정자
• 전체한정자 : ∀ (for every) ; 모든 x 에 대하여 참일 경우 참인 명제이다
• 존재한정자 : ∃ (there exists x) ; 참이 되는 x 가 하나라도 있을 경우 참이 되는 명제이다

Ch02. 증명

• 공리 : 별도의 증명 없이 항상 참으로 이용되는 명제 ex. 어떤 자연수 n 에 대하여 n+1 이 존재한다.

• 정의 : 용어 또는 기호의 의미를 확실하게 규정한 문장이나 식.

• 정리 : 공리와 정의를 통해 참으로 확인된 명제. ex. 피타고라스의 정리

• 증명 : 명제가 진리값을 확인하는 과정 (=해당 명제의 True,False 여부를 증명하는 과정)

• 직접증명 : 조건 명제 ‘p이면 q이다’ 를 증명하기 위해 p 를 참이라고 가정한 상태에서 q 도 참임을 증명하는 방법 = 한 마디로 어떠한 트릭도 쓰지 않고 직접 수식을 전개해가면서 증명하는 가장 오리지날한 방법

  

• 반례증명법
• 모순증명 : “그래, q 가 참이 아니라고 하자 -> 모순이 발생하지? -> 그러니까 q는 참이 될 수 밖에 없어”
• 동치증명법 : 대우가 증명하기 더 쉽다면 대우를 통해 증명하는 방법
• 경우증명법 : 주어진 명제를 여러 case 로 나누어서 증명하는 방법
• 존재증명법 : 주어진 명제가 존재성을 증명하는 문제일 때 (ex. ~가 존재함을 보이시오.) 명제를 만족하는 예를 하나라도 찾아서 증명하는 방법
• 수학적 귀납법 : 명제함수 P(n) 에 대하여 1. P(1) 이 참임을 증명 2. P(K) 가 참이라고 가정하였을 때, P(K+1)이 참임을 증명. => 1,2 에 의해서 P(n) 이 참

Ch03. 함수, 수열과 관계

• 함수 : 집합 A,B 에 대하여 A 의 모든 원소가 B 의 모든 원소로 mapping 될 때 그 대응관계를 A에서 B로 가는 함수 f 라고 부름
• 공역 : 함수 f:A->B 에서 B 를 f의 공역
• 치역 : B 의 모든 원소들이 공역이었다면 실제로 mapping 되는 원소들만 모은 것 = 치（值）역
• 일대일 함수 : 정의역의 모든 원소들이 서로 다른 공역의 원소와 대응하는 함수
• 전사 함수 : 공역과 치역이 일치하는 함수
• 일대일 대응 : 전사 함수이면서 일대일 함수
• 합성함수
• 항등함수
• 역함수
• 상수함수
• 수열 : 함수 중에서 정의역이 자연수의 부분집합인 함수
  • 단조 증가 수열
  • 단조 감소 수열
  • 강한 증가 수열
  • 강한 감소 수열
• 부분수열 : 부분수열 인데 index 는 유지해야 함 ! ex. {1,2,3,4,5} -> 1,4,10
• 순서쌍 : a 는 A 의 원소이고 b 는 B 의 원소일 때, (a,b) 순서쌍
• 곱집합 : 모든 순서쌍 (a,b) 를 모아놓은 집합 ; A와 B의 곱집합 A X B
• 이항관계 : A X B 의 부분집합 (R)
  • 결국 함수란, A 의 원소인 a 에 대하여 a R b 를 만족하는 B 의 원소 b 가 단 하나만 존재하는 특수한 관계이다
• 관계의 표현 : 테이블, 유(有)향 그래프, 행렬
  • X x X 에서 정의된 관계 R이 있을 때, X 의 모든 원소 a 에 대하여 (a,a) 관계가 성립하면 반사 관계 라고 한다 = 대각선이 전부 1인 행렬
  • X x X 에서 정의된 관계 R이 있을 때, X 의 모든 순서쌍 (a,b) 에 대하여 (b,a) 관계도 성립하면 대칭 관계 라고 한다 <-> 반대칭 관계
  • X x X 에서 정의된 관계 R이 있을 때, X 의 모든 순서쌍 (a,b), (b,c) 에 대하여 (a,c) 관계도 성립하면 추이 관계 라고 한다

나머지는 나중에 혹시 참고할지도 모르겠어서 같이 올린다.

Ch04. 알고리즘

cs 에서 알고리즘이 좀 더 코테 보는 실전형 느낌이었다면 이산수학 강좌에서 간략하게 설명한 알고리즘은 좀 더 정의가 촘촘하고 엄밀한 수학적 느낌의 알고리즘에 가까웠다.

• 알고리즘 : 주어진 문제애 대해 그 문제를 해결하기 위한 방법을 순차적으로 나열한 것
  • 입력값을 가져야 한다
  • 출력값을 가져야 한다
  • 유한 시간 내에 종료되어야 한다
  • 각각의 중간과정은 명확하게 서술되어야 한다
  • 여러 입력값에 대해 적용 가능해야 한다
  • 알고리즘을 표현하는 방법 : 의사 코드, 도표, 실제 프로그래밍 언어
• 시간복잡도 : 주어진 입력 자료에 대한 실행 시간이 얼마나 긴가
  • 그 외 알고리즘의 질을 판별하는 기준 : 정확도, 코드 복잡도, 공간 복잡도(;RAM, 하드디스크 등의 하드웨어를 얼마나 사용하는가)
  • 시간복잡도 표기법 : O,Ω notation 등이 있지만 일반적으로 최악의 경우를 가정하는 빅 오 노테이션을 많이 사용한다. -> 최악의 경우에 해당 알고리즘에서, (비슷한) 계산이 총 몇 번 일어나는지

빅오 노테이션의 엄밀한 정의 : 두 양의 정수 c 와 n_0 가 존재하여 n>=n_0 인 모든 n 에서 |f(n)|<=c|g(n)| 을 만족하면, f(n)=O(g(n)) 이라고 쓰고, f(n) 은 big O of g(n) 이라고 읽는다. g(n) 에 들어가는 함수는 1, logn, n, nlogn, n^2, n^3 등이 있다.

• 재귀적 알고리즘 : 자기 자신을 스스로 호출하는 함수.
  • 재귀 알고리즘을 쓰는 이유 : 알고리즘 자체가 재귀적으로 표현하기 자연스러울 때가 있고, 변수 사용을 줄여듦
  • 재귀 알고리즘을 사용할 때는 자료 구조 중 스택이 사용
  • 스택 ; 지역 변수와 매개변수가 할당되는 영역. 할당되는 변수들은 선언된 함수를 빠져나가면 소멸. 재귀적으로 새로이 호출되는 함수 및 변수들이 스택에 push 됨. -> 재귀 알고리즘을 잘못 사용하면 스택 오버플로우가 발생할 수 있음 ! 😨

​ 재귀 알고리즘은 백트래킹이나 분할정복 할 때 주로 사용해서 빠르게 넘어갔다.