독학사 - 이산수학

집합

공통된 특징을 갖는 원소의 모임

내용 규정 명확

순서중복 상관 없음

한번만 나열

​

원소나열

1,2,3,4

​

조건제시

1~4 정수

​

연산가능

합,교,차

> 세로운 집합

​

여집합

제외한 나머지

​

대수법칙

필요없는거 생략

​

 

분할

겹치지 않게 나눈 부분집합의 집합(파티션)

​

증명

어떤 명제가 진리라는 것을 참이라는 것을 확정하는 과정

프로그램 검증용

수학적 귀납법,직접증명,대우증명,모순증명,반례증명

​

귀납법

p(n)이 모든 자연수 n에대해 만족하는 것을 증명

p(1) 은 참일시 , p(k)가 참이면 p(k+1)이 참인것을 증명

​

직접 증명

명제를 유지

명제를 참이라 가정하고 정리와 공리로 증명

​

간접 증명

명제를 논리가 허용하는 범위에서 쉬운명제로 변환하여 증명

p는q이다 를 다른 방법으로 바꿔 증명

대우증명 대우명제를 이용(동치)

모순증명 부정을하고 거짓인것을 확인

반례증명 모순이되는 예를 증명

​

알고리즘

과정 절차를 순서대로 나열

​

특성

입력

출력

정확

유한성 반드시 종료해야함, 제한된 명령을 거침

일반 같은 형태의 입력에 항상 가능

​

프로그램 코드로 작성

조건문

반복문(루프)

지정문 변수명=계산식

제어문

​

복잡도

처리시간, 용량이 적은게 효율적

시간복잡도

공간복잡도

​

​

관계

관련성

원소들간의 순서쌍

역관계

합성관계

​

​

단사함수 일대일 함수

전사함수

전단사함수

역함수

합성함수

바닥함수 x보가 크지안은 최대의

천정함수 최소

나누셈함수 나머지 값을 구함

​

계승 n!

​

​

계수법칙

곱법칙 연속된 작업

합법칙 독립적

​

순열과 조합

선택과 순서의 고려

​

​

일반 순열 =중복 허용 순열

일반조합 = 중복 허용

​

점화식

초기조건으로 나머지 원소의 수열을 구합

​

​

​

그래프

오일러 모든걸 한번씩만

사이클 원위치로 돌아옴

​

최단경로

가중치가 가장 짧음

​

동형그래프

정점과 간서이 같음

​

G(v,e) = G (점,선)

​

트리

사이클이 없음

​

최소 신장트리

경제 효율

모든 정점 포함

사이클 없음

​

뿌리트리

정점중 하나가 뿌리

​

 

​

​

이진트리 순회

전위순회 뿌 왼 오

중위순회 왼 뿌 오

후우순회 왼 오 뿌

​

​

​

이진탐색트리

제약조건

외쪽은 뿌리보다작음

오른쪽은 뿌리보다 큼

검색 삽입 삭제 정렬에 용이

​

수학논리

명제

진리값 참 거짓으로

​

부정

낫

​

논리합

또는

​

함축

​

​

역 이 대우

​

​

​

​

항진명제

항상 참

모순명제

항상 거짓

​

논리적 동치

​

​

​

술어 논리

주어와 술어로

특정갑 ㅅ 대입시 명제

​

​

한정자

​

추론규칙

새로운 사실 유도

​

​

불대수

논리연산

​

​

​

논리회로 간소화

게이트수와 입력의 변수를 줄임

​

​

카르노맵

인접한 셀로 묶음

​

​

​

자동장치와 언어

순차회로 상태에따라 출력이 달라짐

​

유한상태기계

​