[이산수학] 순열, 이산적 확률, 재귀적 관계

순열, 이산적 확률, 재귀적 관계에 연관된 전반적인 논제들을 고찰하고 그에 따른 문제 해결 방법을 습득할 수 있음 경우의 수 어떤 사건이 일어나는 경우의 수를 구하기 위해 모든 경우를 일정한 기준에 따라 빠짐없이, 중복되지 않게 해야함 경우의 수를 구하는 방법에는 구하는 방법에는 트리를 이용한 방법과 표를 구하는 방법이 있음 #1 합의 법칙 두 사건 A, B가 일어날 경우의 수를 n(A) = m, n(B)=n이라 하면 , A 또는 B가 일어날 경우의 수는 m+n #2 곱의 법칙 두 사건 A, B가 일어날 경우의 수를 n(A) = m, n(B)=n이라 하면, A,B가 동시에 일어날 경우의 수는 m*n 순열 서로 다른 원소들을 순서를 고려하여 일렬로 배열하는 것 1부터 n까지의 모든 자연수의 곱을 n의 계승..

• format_list_bulleted Computer Science/Discrete Mathematics
• · 2023. 8. 14.
• textsms

[이산수학] 트리

트리의 개념을 익히고 트리의 응용 방법을 고찰한다 트리의 기본 개념 트리 그래프의 모양이 나무를 거꾸로 세워 놓은 것처럼 생겼다하여 불리는 이름 그래프의 특별한 형태로 컴퓨터를 통한 자료 처리와 응용에 있어 매우 중요한 역할 이진 트리는 산술적 표현이나 자료 구조를 매우 간단히 표현 가능 → 컴퓨터 기술의 발전에 따라 수 많은 분야에 적용 가능 트리는 하나 이상의 노드로 구성된 유한 집합으로 특별히 지정된 루트가 있으며 나머지 노드 들은 다시 각각 트리이며 연결되지 않는 서브 트리로 나뉜다 트리의 응용 분야 최적화 문제 해결, 언어들 간의 번역, 알고리즘, 자료 탐색/정렬, 등 트리의 구조 루트 : 주어진 그래프의 시작 노드로서 통상 트리의 가장 높은 곳에 위치 차수 : 어떤 노드의 차수는 그 노드의 서..

• format_list_bulleted Computer Science/Discrete Mathematics
• · 2023. 8. 13.
• textsms

[이산수학] 그래프

그래프의 기본 개념을 알아보고 응용 문제인 최단 경로, 순회판매원, 그래프 탐색 문제 등을 고찰한다 그래프의 기본 개념 오일러에 의해 시작 쾨니히스베르크 다리 문제는 대표적인 그래프 문제 **그래프 G = ( V, E )**는 유한한 개수의 정점 또는 노드들의 집합인 V와 연결선 또는 에지라고 불리는 정점들의 쌍들의 집합인 E로 이루어진다 #1 방향 그래프 방향이 있는 그래프로 연결선을 화살표로 표시하여 방향을 나타내는 그래프 #2 방향이 없는 그래프 방향이 없는 그래프로 그래프의 특수한 형태 #3 트리 사이클이 존재하지 않는 그래프 루트라 불리는 특별한 노드가 한개 존재하고 루트로부터 다른 모든 노드로 가는 경로가 항상 유일하게 존재 루트로 들어오는 연결선이 없으므로 루트는 모든 트리의 출발점 그래프의..

• format_list_bulleted Computer Science/Discrete Mathematics
• · 2023. 8. 10.
• textsms

[이산수학] 함수

함수의 개념을 살펴보고 그래프의 관계를 살펴봄 컴퓨터 언어에서의 함수의 역할에 대해 알아보기 함수의 정의 함수 (Function) 관계의 특수한 형태 ⇒ 첫 번째 원소가 같지 않은 순서쌍들의 집합 여러 가지 수학적 도구 중 가장 중요한 개념 다양한 공학 분야에 폭넓게 활용 → 함수의 개념을 이해하고 응용하여 주어진 문제 해결에 도움 두 집합 X, Y에서 함수 $f$는 집합 X에서 Y로의 관계의 부분 집합, 집합 X에 있는 모든 원소 x가 집합 Y에 있는 원소 중 오직 하나씩만 대응되는 관계 $f$ : X → Y 이때 X를 함수 $f$의 정의역, Y를 함수 $f$의 공빈역이라함 관계와 함수의 차이점 함수의 개념은 관계와 매우 밀접하고 기본적으로 비슷 관계에서 함수가 되기 위해서는 정의역의 모든 원소가 일대..

• format_list_bulleted Computer Science/Discrete Mathematics
• · 2023. 8. 9.
• textsms

[이산수학] 관계

관계에 대해 정의하고 성질에 고찰하며 여러 분야에 사용 방법을 익힐 수 있다 관계와 이항 관계 관계 객체들 간의 연관성을 표현하는 구조 이항 관계 (binary relation) 두 집합 A, B에 대하여, A로부터 B로의 이항 관계 R은 두 집합의 곱집합의 부분 집합 (a,b) ∈ R 과 aRb는 동치 2개의 집합 사이의 관계를 이항 관계 2개 그 이상의 원소에 대한 관계는 n-ary 관계라고 함 #1 관계 R의 원소인 순서쌍 첫 번째 원소의 집합을 정의역, Dom(R)로 표시 두 번째 원소의 집합을 치역, Ran(R)로 표시 Dom(R) = {a | (a,b) ∈ R} ⊆ A Ran(R) = {b | (a,b) ∈ R} ⊆ B #2 xRy ≠ yRx 정의역은 순서쌍의 첫 번째 원소로 이루어진 집합이고..

• format_list_bulleted Computer Science/Discrete Mathematics
• · 2023. 8. 8.
• textsms

[이산수학] 증명론

증명의 일반적인 방법론을 고찰하고 여러 가지 증명법을 살펴보면서 주어진 문제를 해결하기 위한 단계적 접근 방법을 제시한다 증명의 방법론 증명 논리적 법칙을 이용하여 주어진 가정으로부터 결론을 유도해내는 추론의 한 방법 어떠한 명제나 논증이 적절하고 타당한지 입증하는 작업 증명의 단계적 접근 방법 아이디어 스케치 문제 해결의 핵심적인 실마리를 찾아내 기술 문제를 해결할 수 있는 방법론을 구상하게 되며 개략적인 아이디어 스케치 구체적인 방법론 제시 아이디어를 묶어서 구체적인 블록 다이어그램 등으로 표현 프로그래밍의 경우 유사 코드 단계까지 구체화 엄밀한 입증이나 증명 결론을 객관적인 증명 방법을 통해 누구나 공감할 수 있게 증명함 여러 가지 증명 방법 수학이나 공학에서의 증명 문제는 p→q와 같은 논리 함축..

• format_list_bulleted Computer Science/Discrete Mathematics
• · 2023. 8. 7.
• textsms