IT (30) 썸네일형 리스트형 [이산수학] 그래프 그래프 1. 그래프(Graph) 이산수학에서 "그래프"는 "꼭짓점(vertex, 노드)"들의 집합과 이들을 연결하는 "변(edge)"들의 집합으로 구성된 수학적인 구조를 가리킵니다. 이때 꼭짓점들의 집합이 V, 변들의 집합이 E라고 하면 그래프 G는 G = (V, E)라고 표현합니다. 그리고 변이 방향을 가지고 있으면 방향 그래프(directed graph), 방향이 없다면 무향 그래프(undirected graph)로 분류할 수 있습니다. 2. 기본 용어 2.1. 인접(Adjacent) 1개의 변이 2개의 꼭지점을 연결할 경우, 연결된 2개의 꼭짓점은 서로 인접하다고 합니다. 2.2. 루프(Loop) 1개의 변이 동일한 꼭지점을 연결할 경우, 해당 변을 루프라고 합니다. 2.3. 고립(Isolated).. [이산수학] 이산확률과 경우의 수 이산확률과 경우의 수 1. 경우의 수(Counting) 경우의 수는 발생한 사건에서 가능한 모든 결과의 수를 세는 것을 의미합니다. 사건 A에서 발생하는 경우의 수를 N(A)할 때, 아래와 같은 법칙이 성립합니다. 연산법칙 관계 덧셈 법칙 N(A ∪ B) = N(A) + N(B) - N(A ∩ B) 곱셈 법칙 N(A × B) = N(A) × N(B) 2. 순열(Permutation) 순열은 순서를 고려하여 주어진 요소들을 배열하는 것을 의미합니다. 순열의 경우의 수는 P를 사용하며, n개의 요소들로부터 r개의 요소를 선택하여 순서에 맞추어 배열하는 경우의 수는 상황에 따라 다른 계산 법을 가지고 있으며, 아래처럼 표현합니다. $$_{n}\mathrm{P}_{r}$$ 2.1. 순열 n개의 요소에서 r개를 .. [이산수학] 함수 함수 1. 함수(Function)? 함수는 두 집합 사이의 관계를 나타내는 규칙입니다. 예를 들어, X에서 Y로의 함수는 집합 X의 각 원소들이 집합 Y의 원소들에 대응되는 관계를 의미하는데, 이때 X의 원소는 오직 하나의 Y 원소에 대응되어야 합니다. 이때, 함수가 f라면 집합 X는 f의 "정의역(domain)"이라 하고, 집합 Y는 f의 "공역(codomain)"이라고 합니다. 그리고 집합 X의 원소 x가 매핑되는 집합 Y의 원소 y는 "f(x)"라고 표현하며, 함수는 관계를 나타내는 것이기 때문에 xfy 또는 f: X → Y라고 표현도 가능합니다. 이때 함수 f는 x를 y로 사상한다고 하여 y를 x에 대한 "상(image)"이라고 합니다. 또한, 이 상의 집합을 "치역(range)"이라고 합니다. .. [컴퓨터 프로그래밍] 프로그래밍? 프로그래밍? 1. 프로그래밍이란? 프로그래밍(programming)이란 프로그램을 만드는 행위이며, 프로그램(program)은 컴퓨터에게 어떤 작업을 수행하는데 필요한 명령어들을 순차적으로 작성한 것을 의미합니다. 그리고 이러한 프로그램을 작성하는 데 사용되는 언어를 프로그래밍 언어(programming language)라고 합니다. 그런데, 컴퓨터는 기계어(machine language)로 명령을 받아야 이해할 수 있습니다. 하지만 기계어는 사람이 프로그래밍하기에 어려운 작업입니다. 그렇기 때문에 사람이 이해하기 쉬운 언어로 프로그램을 작성한 후 기계어로 번역하는 과정을 거칠 수 있도록 도구룰 마련하였고, 이 도구가 컴파일러(compiler)입니다. 2. 프로그래밍 언어의 종류 프로그래밍 언어는 프로그.. [이산수학] 관계 관계 1. 관계(Relation) 이산수학에서 관계는 한 집합의 원소와 다른 집합 원소 간의 연관성을 표현하는 것에 중점을 둡니다. 관계를 나타내는 일반적인 기호로는 R을 사용하며, 집합 X, Y의 원소인 x, y가 R의 관계를 가지고 있을 때 xRy라고 표현합니다. 이 때 R은 집합 X, Y의 곱집합의 부분집합 개념이기도 합니다. 그리고 X, Y의 관계처럼 2개 집합의 관계를 "이항 관계(Binary relation)"라고 정의합니다. 이러한 관계는 순서쌍의 집합, 화살표 도표, 부울행렬 등 다양한 방법으로 표현할 수 있습니다. 2. 관계의 성질 2.1. 반사성(Reflexivity) 모든 x ∈ A에 대해 xRx를 만족하면, R은 반사적이라고 합니다. 2.2. 대칭성(Symmetry) 모든 x, y .. [이산수학] 행렬 행렬 1. 행렬(Matrix) 행렬은 숫자들을 직사각형 모양으로 배열한 것으로, m개의 행과 n개의 열로 이루어진 배열을 m x n행렬이라고 합니다. 이때, 임의의 행렬 A를 구성하는 수 중 i번째 행, j번째 열에 위치한 수를 행렬 A의 (i, j) 원소라고 하며, aij로 표기합니다. 2. 행렬의 종류 2.1. 영행렬(Zero matrix) 모든 원소가 0인 행렬입니다. 대문자 o인 "O"로 표현합니다. (예시) \begin{pmatrix} 0 & 0 \\ 0 & 0 \\ \end{pmatrix} 2.2. 정방행렬(Square matrix) 행과 열의 개수가 같은 행렬입니다. 행과 열의 개수가 n일 경우 이때의 정방행렬은 "n차 정방행렬"이라고 합니다. 그리고 이 때 행렬 원소 aij에서 i = j .. [이산수학] 증명 증명 1. 공리(Axiom) 공리는 다른 정의나 정리를 통한 증명 없이 참으로 이용되는 명제이며, 이는 다른 정의나 정리들을 증명하기 위한 전제로 사용되는 가정입니다. (예시) 유클리드 기하학의 공리 ① 일직선 위의 점들 사이의 거리는 측정 가능하다. ② 임의의 선분은 무한히 연장 가능하다. ③ 모든 직각은 서로 동일하다. ④ 두 점이 주어졌을 때, 두 점을 통과하는 직선을 그릴 수 있다. ⑤ 모든 직선과 평행선에 대해 한 점에서 만나는 직선은 하나뿐이다. 2. 정리(Theorem) 정리란 증명된 명제를 의미합니다. 3. 증명(Proof) 증명은 이미 가정된 공리 하에 어떤 명제가 참임을 보이는 과정입니다, 3.1. 직접 증명법(Direct proof) 가정과 공리를 사용하여 명제의 변형 없이 논리적인 .. [이산수학] 부울대수 부울대수 1. 부울대수(Boole algebra) 조지 부울(George Boole)이라는 수학자가 소개한 논리 대수의 한 형태로, 논리적인 상태를 다루는 데 사용되는 수학적인 체계입니다. 논리적인 상태는 "0"과 "1", 두 개 값으로 "거짓", "참"을 표현할 수 있습니다. 즉, 참/거짓 명제 문제를 수로 표현한 형태입니다. 2. 논리연산 논리연산은 입력과 출력으로 구분됩니다. 입력변수는 부울변수이며, 부울변수로 구성된 연산식을 부울식이라고 합니다. 또한, 부울식으로 표현된 함수를 부울함수라고 합니다. (예시) F(X, Y) = X + Y 대표적인 논리연산과 진리표는 다음과 같습니다. 2.1. 논리곱(AND, ⋅) 두 입력이 모두 1일 때에만 출력이 1이 됩니다. XY = F 또는 X⋅Y = F로 표.. 이전 1 2 3 4 다음
