<-->
본문 바로가기

반응형

이산수학

(8)
트리 - 1 트리 : 루트와 서로 연결되지 않는 서브트리로 이루어진 특수한 그래프이다. n-트리 중간 노드들이 n개의 자식 노드를 갖는 것을 의미한다. ( 이진트리는 모든 중간노드들이 2개의 자식노드를 가짐) 이진트리 : 공집합이거나 루트,왼쪽 또는 오른쪽 서브트리로 이루어져있다. 1. 사향이진트리 : 왼쪽 또는 오른쪽으로 편향된 이진트리 2. 완전 이진트리 : 레벨 k-1 까지만 차있고 레벨 k부터 왼쪽부터 하나씩 채우는 이진트리 3. 포화이진트리 : 잎노드를 제외한 모든 노드가 2개의 자식노드를 갖는 경우.
그래프 1. 그래프의 정의 그래프 G = (V,E) vertex의 집합 V edge의 집합 E 경로: 연결된 정점들의 순서 순회: 사이클 ( ex) 1->2->3->1) 2. 그래프의 용어 단순그래프 : 한쌍의 정점사이에 최대 하나의 연결선이 존재. 멀티그래프 : 단순 그래프의 확장, 한쌍의 꼭지점 사이 연결선의 개수는 제한이 없다. 3. 그래프의 표현 그래프 관련 알고리즘을 사용하려면 그래프를 컴퓨터가 이해할수 있는 형태로 만들어 줘야한다. 인접행렬 : |v|=n일때 n*n행렬 인접리스트 : 인접한 정점들을 연결리스트로 표시한것.
함수 - 2 단사,전사,전단사 함수 1. 단사함수 f: A->B에서 a1,a2 ∈ A에 대하여 f(a1)=f(a2)이면 x1 = x2일 경우 단사함수 라고한다 ( one - to -one function) Ran(f) ⊆ B이다. (치역) 롤 랭크게임이랑 비슷하다. 집합 A의 원소들은 겹치는 챔프를 고를수 없다. 2. 전사함수 f: A->B에서 에서 B의 모든 원소 b에 대하여 f(a)=b가 성립되는 a ∈ A가 적어도 하나존재할때 전사함수라고한다. (onto function) Ran(f)=B B의 모든 원소가 화살에 맞아야 성립할 수 있다. 3. 전단사 함수 f:A->B에서 f가 전사인 동시에 단사인 함수 (one-to-one correspond function) Ran(f) = B 여러가지 함수들 1. 함성함수 ..
함수 함수는 관계의 특수한 형태이다. (관계의 화살표 도표 형태) 함수는 관계에서 첫번째 원소가 같지 않은 순서쌍의 모임이다. ex) R = {(1,a),(2,b),(3,c)}를 함수로 표현하면 함수의 정의 집합 X에 있는 모든 원소 x가 집합 Y에 있는 원소 중 오직 하나씩만 대응되는 관계를 말한다. (집합 X의 모든 사람들은 무조건 화살 한발을 쏴야한다.) 이때 집합 X는 정의역(domain)이 되고 집합 Y는 공변역(codomain)이 된다. 화살을 맞은 Y의 원소는 치역(range)이라고 한다. 정의역 = Dom(f) = {x|(x,y)∈f, x ∈X, y∈Y} -> (x,y) 순서쌍의 x 치역 = Ran(f) = {y|(x,y)∈f, x ∈X, y∈Y} -> (x,y) 순서쌍의 y 함수는 자판기랑 비..
관계의 성질 집합 A에 대한 관계 R은 특정 성질에 따라 나뉘어진다 4개의 성질들을 외우고 방향그래프로 보면서 이해하는게 더 쉬운거같다! 1. 반사관계 : 집합 A의 모든원소 x에 대해 xRx을 만족 A = {1,2,3,4}라고 할때 집합의 모든 원소가 xRx를 만족하기 때문에 반사관계이다 2. 대칭관계 : xRy 이면 yRx임을 만족 1R2 이면 2R1 이기 때문에 대칭관계이다. ( 3R3 또한 대칭) 반사관계와 달리 위 그림에서 원소 1,3이 대칭관계가 아닌데도 관계 R이 대칭관계가 되는이유는 p -> q 에서 p가 false 일때 항상 참이 되기 때문이다. (xRy가 없(false)기 때문에 대칭관계는 참) 3. 반대칭관계 : xRy이고 yRx 일때 x=y를 만족 (대칭관계와 정반대개념이 아니다!) 반대칭 관계..
관계 관계 : 객체들 간의 연관성을 표현하는 구조 1. 관계와 이항관계 2개의 집합의 곱집합의 부분 집합중에 조건을 만족하는 원소를 특정 기호로 표현한것 A*B의 원소 (a,b)가 주어졌을때 (a,b) ∈ R 과 aRb는 동치이다. 2. 관계의 표현 화살표 도표 좌표도표 방향 그래프 관계행렬 3. 합성관계 R1 ∘ R2 = {(a,c)| a∈A, c ∈C, (a,b) ∈R1 , (b,c)∈R2} (3단 논법 생각하면 쉽다) + 항등관계 Ia = {(a,a)|a∈A} 이책에서는 관계가 쓰이는 예시로 "같은 메모리공간을 공유하는 변수를 관계있는 변수" 정도로만 표현하는데... 이정도 예시로는 어디에 쓰이는지 잘 모르겠다.
증명 코딩문제를 풀고나서 찝찝한 기분이 드는 이유는 명시적인 "증명"을 하지 못했기 때문이다. 증명하기를 연습하면 더 나은 결과물을 만들어 낼 수있다. 증명: 추론의 한 방법, 명제나 논증이 타당한지 입증 하는 것 증명 종류 1. 직접증명법 : p -> q 를 직접 증명 2. 간접 증명법 : 논리적 동치 또는 간접적으로 증명 3. 기타 증명법 증명의 방법 1. 수학적 귀납법 : ① P(1)이 참임을 보이기 ② P(n)이 참이라 가정 ③ P(n+1)이 성립함을 보이기 2. 모순 증명법 : 문제의 명제를 부정한뒤 모순임을 증명하여 참거짓 증명 ( 거짓의 거짓은 참) 3. 직접증명법 : 주어진 유용한 정보를 토대로 추론하여 결론에 도달 ( p -> q ) 4. 대우증명법 : 대우가 논리적으로 동치임을 이용하는 증명..
이산 수학을 배우는 이유 1. 이산 수학을 통하여 해결하고자하는 문제를 추상화, 논리적 판단, 모델링 하기위해서 2. 전산분야의 수학적 배경을 확립하여 더 쉽게 이해하기 위해서!

반응형