방송대 방통대 이산수학 15강 - 학습내용 정리 - 요약 노트 시험족보 예상문제 - 올에이클래스

이산수학 15강 - 학습내용 정리

이산수학의 목적과 학습방법을 되짚고, 1강부터 14강까지 배운 핵심 개념과 공식의 연결관계를 종합적으로 정리한다. 논리와 증명에서 출발하여 집합·행렬·관계·함수·부울대수·그래프·트리·조합이론·정수론·오토마타와 형식 언어까지 전체 시험 범위를 빠르게 복습한다.

1. 이산수학의 목적과 학습방법

이산수학은 연속적이지 않은 이산적인 수학구조를 연구하고 이산적 데이터를 처리하는 데 필요한 수학을 다루는 학문이다. 컴퓨터가 다루는 데이터와 구조는 유한하거나 셀 수 있는 형태가 많으므로, 이산수학은 컴퓨터과학의 여러 문제를 표현하고 해결하는 기초가 된다.

이 과목의 목표는 문제해결 방법을 모델링하고 구현할 때 사용하는 수학구조를 이해하여 활용하고, 수학적 추론기법을 익히며, 새로운 개념을 체계화해 정확히 표현하는 역량을 기르는 것이다.

학습 원칙	의미
약속을 지킨다	정의와 기호논리학의 약속을 정확히 이해하고 기억한다.
연습한다	강의에서 제시한 學以時習之의 태도로 문제를 반복해 풀며 논리적 사고와 표현을 훈련한다.
예습과 복습	새 개념의 배경을 미리 살피고 학습 후 개념 사이의 관계를 다시 정리한다.

이산수학에서는 정의를 정확히 아는 것이 계산보다 먼저이다. 기호의 뜻과 적용 조건을 확인한 뒤 예제에 적용하는 습관이 필요하다.

2. 모델링·추상화와 알고리즘 언어

성공적인 문제해결을 위해서는 알맞은 도구와 기법, 방법론을 선택해야 한다. 수학적 모델링은 실생활 문제를 수학적 도구로 해결할 수 있도록 추상화하는 과정이고, 추상화는 문제의 핵심을 남기기 위해 관련 없는 내용을 제거하거나 단순화하는 과정이다. 정보 모델링은 실생활 문제를 컴퓨터에서 해결할 수 있는 형태로 추상화한다.

알고리즘을 모호하지 않게 나타내기 위해 컴퓨터 프로그래밍 언어, 순서도, 의사코드 등을 사용한다. 표현 방식은 달라도 입력에서 출력으로 이어지는 처리 단계가 정확하고 유한하며 해석의 여지가 없도록 기술해야 한다.

이산수학의 주제는 컴퓨터 응용과 연결된다. 논리는 전문가시스템, 집합론은 자료구조와 데이터베이스, 행렬은 그래픽스와 로봇공학, 관계는 데이터베이스, 함수는 프로그래밍 언어, 부울대수는 디지털 논리회로, 그래프는 컴퓨터 네트워크, 트리는 데이터 검색, 정수론은 암호, 오토마타는 계산이론과 연결된다.

3. 논리

명제와 논리연산

명제는 참과 거짓을 분명히 구분할 수 있는 문장 또는 수식이다. 명제를 결합하는 연산에는 논리합 p ∨ q, 논리곱 p ∧ q, 부정 ~p, 배타적 논리합 p ⨁ q가 있다. 조건명제 p → q, 쌍조건명제 p ↔ q, 논리적 동치 p ≡ q도 구분해야 한다.

모든 진리값에서 참인 합성명제는 항진명제이고, 모든 진리값에서 거짓인 합성명제는 모순명제이다. 논리적 동치는 두 명제가 모든 경우에 같은 진리값을 가진다는 뜻이다.

술어논리와 추론

명제함수는 변수의 값에 따라 진리값이 정해지는 문장이나 식이다. 전체한정자 ∀는 “모든” 또는 “임의의”를, 존재한정자 ∃는 “존재한다”를 뜻한다.

참이라고 알려진 사실에서 논리적 과정을 거쳐 새로운 참인 사실을 이끌어 내는 것을 추론이라 한다. 전제를 참이라고 가정했을 때 결론이 항상 참인 추론은 유효추론이다.

4. 증명

공리는 다른 명제를 증명하기 위해 전제로 사용하는 기본 가정이고, 증명은 공리를 바탕으로 명제가 참임을 입증하는 작업이며, 정리는 가정에서 증명된 명제이다.

증명방법	핵심 절차
직접증명법	명제를 변형하지 않고 가정에서 결론을 연역적으로 이끌어 낸다.
수학적 귀납법	기본단계, 귀납가정, 귀납단계를 통해 모든 자연수에 대한 명제를 증명한다.
대우증명법	p → q 대신 동치인 ~q → ~p를 증명한다.
모순증명법	명제의 부정을 가정하여 모순이 생김을 보인다.
반례증명법	전칭명제가 거짓임을 보이는 하나의 반례를 제시한다.
존재증명법	조건을 만족하는 대상이 존재함을 보인다.
기타 방법	전수증명, 조합적 증명, 전단증명, 중복산정, 컴퓨터를 이용한 증명 등이 있다.

수학적 귀납법의 귀납가정은 n = k에서 명제가 참이라고 임시로 가정하는 단계이고, 귀납단계는 그 가정으로 n = k + 1에서도 참임을 보이는 단계이다.

5. 집합론

집합론에서는 집합과 원소, 원소나열법과 조건제시법, 부분집합과 진부분집합, 집합의 상등, 집합의 분할, 멱집합을 학습한다. 집합의 분할은 원래 집합의 모든 원소를 빠짐없이 포함하면서 서로 겹치지 않는 부분집합들의 모음이다. 멱집합은 주어진 집합의 모든 부분집합을 원소로 갖는 집합이다.

기본 집합연산에는 합집합 A ∪ B, 교집합 A ∩ B, 차집합 A - B, 여집합 A^c, 대칭차집합이 있다. 두 유한집합에 대해서는 포함배제의 원리에 따라 |A ∪ B| = |A| + |B| - |A ∩ B|가 성립하며 A ∩ B ⊆ A ⊆ A ∪ B이다.

집합연산은 교환·결합·분배법칙, 항등·보수·멱등법칙, 드 모르간 법칙, 흡수법칙, 차집합 관련 항등식 등을 만족한다. 논리연산과 집합연산은 구조적으로 대응하므로 논리합은 합집합, 논리곱은 교집합, 부정은 여집합과 연결해 이해할 수 있다.

6. 행렬

m × n 행렬은 m개의 행과 n개의 열로 이루어진 수 배열이며 (i, j) 원소를 a_ij로 표시한다. 1 × n 행렬은 행벡터, m × 1 행렬은 열벡터이고 모든 원소가 0인 행렬은 영행렬이다.

연산	핵심 수식과 조건
합	cij = aij + bij, 두 행렬의 크기가 같아야 함
차	cij = aij - bij, 두 행렬의 크기가 같아야 함
스칼라 곱	cij = kaij
행렬곱	cij = Σaikbkj, 앞 행렬의 열 수와 뒤 행렬의 행 수가 같아야 함

가우스 소거법은 확대행렬에 기본행연산을 적용하여 일차연립방정식을 푸는 방법이다. 기본행연산은 행 교환, 0이 아닌 스칼라를 곱하는 행 스케일링, 한 행의 스칼라 배를 다른 행에 더하는 행 대체이다. 행제형과 소거 행제형의 선도원소 조건을 구분해야 한다.

행렬의 종류에는 정방·대각·단위·대칭·역대칭·삼각·전치·역행렬이 있다. 부울행렬은 원소가 0과 1로만 구성되며 합 A ∨ B, 교차 A ∧ B, 부울곱 A ⨀ B를 정의한다.

7. 관계

집합 A에서 B로의 관계 R은 곱집합 A × B의 부분집합, 즉 R ⊆ A × B이다. A에서 A로의 관계는 R ⊆ A × A이다. 관계는 순서쌍의 집합, 화살표도표, 방향그래프, 부울행렬로 표현할 수 있다.

성질	의미
반사적	모든 x에 대해 (x, x)가 관계에 포함된다.
대칭적	(x, y)가 포함되면 (y, x)도 포함된다.
추이적	(x, y), (y, z)가 포함되면 (x, z)도 포함된다.

역관계는 순서쌍의 앞뒤를 바꾼 관계이고, 합성관계는 두 관계를 연속 적용한 결과이다. 반사적·대칭적·추이적 성질을 모두 만족하면 동치관계이며, 동치관계에 의해 서로 동치인 원소들의 집합을 동치류라고 한다.

8. 함수

함수는 정의역의 각 원소에 공역의 원소를 정확히 하나씩 대응시키는 관계이다. 두 함수가 같으려면 정의역과 공역이 같고 모든 입력에서 같은 함숫값을 가져야 한다.

함수 유형	판정 기준
전사함수	공역의 모든 원소가 적어도 하나의 원상과 대응한다.
단사함수	서로 다른 정의역 원소가 서로 다른 함숫값을 갖는다.
전단사함수	전사이면서 단사인 함수이다.
역함수	대응 방향을 거꾸로 한 함수로, 전단사일 때 정의된다.
합성함수	한 함수의 출력을 다음 함수의 입력으로 적용한다.

특수 함수로는 계승함수 n!, 주어진 수 이하의 최대 정수를 구하는 바닥함수, 주어진 수 이상의 최소 정수를 구하는 천장함수, 나눗셈의 나머지를 구하는 나머지 함수가 있다.

9. 부울대수

디지털 논리회로의 기본 게이트에는 AND, OR, NOT이 있고 기타 게이트에는 NAND, NOR, XOR, XNOR이 있다. 부울대수는 0과 1, 논리연산을 대수적으로 다루며 기본정리, 쌍대성원리, 부울함수의 보수를 학습한다.

논리와 부울대수의 대응은 T ↔ 1, F ↔ 0, p·q ↔ X·Y, 논리합 ∨ ↔ +, 논리곱 ∧ ↔ ·, 부정 ↔ 보수이다. 집합론에서도 T ↔ 전체집합 U, F ↔ 공집합 ∅, ∨ ↔ ∪, ∧ ↔ ∩, 부정 ↔ 여집합으로 대응한다.

부울함수를 간소화하면 같은 기능을 더 간단한 논리회로로 구현할 수 있다. 기본공식을 활용하거나 항 결합, 문자 소거, 중복항 첨가 등의 방법으로 복잡한 부울함수를 간단한 식으로 바꾼다.

10. 그래프

그래프의 기본 구조와 표현

그래프 G = (V, E)는 꼭지점 집합 V와 변 집합 E로 구성된다. 방향·무향 그래프, 루프와 병렬변이 없는 단순그래프, 부분그래프와 모든 꼭지점을 유지하는 신장부분그래프를 구분한다. 방향그래프에서는 진입차수와 진출차수를 사용한다.

워크는 변을 따라 이동하는 일반적인 열, 트레일은 변을 반복하지 않는 워크, 경로는 꼭지점을 반복하지 않는 트레일, 사이클은 닫힌 경로이다. 그래프는 발생행렬, 인접행렬, 인접리스트로 표현할 수 있다.

그래프의 종류와 탐색

연결그래프는 임의의 두 꼭지점 사이에 경로가 존재하고, 완전그래프 K_n은 임의의 두 꼭지점이 변으로 연결된다. 이분그래프는 꼭지점 집합을 두 부분으로 나누어 모든 변이 서로 다른 부분의 꼭지점을 잇는 그래프이고, 완전이분그래프 K_m,n은 두 부분 사이의 가능한 모든 변을 가진다. 정규그래프는 모든 꼭지점의 차수가 같다.

평면그래프는 모든 변을 교차 없이 그릴 수 있다. 오일러 투어는 모든 변을 각각 한 번 지나고 시작점으로 돌아오는 트레일이며, 해밀턴 경로는 모든 꼭지점을 한 번씩 지나는 경로이다. 각 변에 실수 가중치가 붙은 가중그래프의 최단 경로는 데이크스트라 알고리즘으로 구할 수 있다.

11. 트리

트리는 사이클이 없는 단순 연결그래프이다. 자식·부모·형제·단말·내부노드, 노드의 차수, 트리의 차수, 레벨, 높이, 무게 등의 용어를 사용한다. 트리는 중첩된 집합, 중첩된 괄호, 들여쓰기 등으로 표현할 수 있다. n개의 꼭지점을 가진 연결그래프 G가 트리일 필요충분조건은 변의 수가 n - 1인 것이다.

이진트리는 공집합이거나 각 노드가 최대 두 개의 서브트리를 갖는 루트트리이다. 완전·포화·경사 이진트리를 구분한다. 높이가 h인 포화 이진트리의 노드 수는 Σ_i=0^h2ⁱ = 2^h+1 - 1이고, n개 노드 이진트리의 최소 높이는 로그를 이용해 판단한다.

이진탐색트리는 키 값을 노드에 저장하여 검색하기 위한 이진트리이다. 트리의 활용인 최소 신장 트리(MST)는 가중그래프의 모든 꼭지점을 포함하는 신장트리 중 총 가중치가 가장 작은 트리이다. Kruskal 알고리즘은 변을 중심으로, Prim 알고리즘은 꼭지점을 중심으로 최소 신장 트리를 구성한다.

12. 조합이론

계수법칙·순열·조합

사건 A와 B가 연속하여 함께 일어나는 경우의 수는 곱의 법칙 N(A × B) = N(A)N(B)로 계산한다. A 또는 B가 일어나는 경우는 합의 법칙 N(A ∪ B) = N(A) + N(B) - N(A ∩ B)를 사용하며, 서로 배반이면 교집합 항은 0이다.

순열은 n개에서 순서를 고려해 r개를 뽑는 방법으로 P(n, r) = n!/(n-r)!이다. 중복순열은 n^r, 원순열은 (n-1)!이다. 조합은 순서를 무시하고 r개를 뽑는 방법으로 C(n, r) = n!/[r!(n-r)!]이다. 이항정리는 (x + y)ⁿ을 조합계수 C(n, k)를 이용해 전개한다.

확률·점화식·비둘기집 원리

표본공간 S에서 사건 E의 수학적 확률은 P(E) = |E|/|S|이고, 조건부 확률은 P(A|B) = P(A ∩ B)/P(B)이다. 점화식은 수열의 항 사이 관계를 나타낸 식이며, 점화식을 푼다는 것은 일반항 a_n을 n의 식으로 나타내는 것이다.

비둘기집 원리는 k개의 상자에 N개의 물체를 넣으면 적어도 하나의 상자에 ⌈N/k⌉개 이상의 물체가 들어간다는 원리이다.

13. 정수론

정수론에서는 나눗셈과 최대공약수, 나머지 연산, 소수와 소인수분해, RSA 암호를 학습한다. 나눗셈 알고리즘과 최대공약수 관련 정리를 바탕으로 정수의 구조를 분석한다.

모듈로 합동은 두 정수가 같은 법을 기준으로 같은 나머지를 갖는 관계이다. 소수는 1보다 큰 자연수 중 1과 자기 자신만을 양의 약수로 갖고, 합성수는 그 밖의 1보다 큰 자연수이다. 산술의 기본정리는 1보다 큰 모든 정수가 소수들의 곱으로 유일하게 표현됨을 보장한다.

RSA 암호에서는 페르마의 작은 정리와 나머지 거듭제곱 알고리즘을 활용한다. 큰 지수의 bⁿ mod m을 직접 계산하기보다 나머지를 유지하며 반복적으로 제곱하고 곱해 효율적으로 구한다.

14. 오토마타와 형식 언어

오토마타와 유한 오토마타

오토마타는 스스로 움직이는 기계 또는 자동장치를 뜻하며, 컴퓨터를 유한 상태 오토마타로 볼 수 있다. 일반 유한 오토마타는 입력·출력·상태·상태전이 등의 요소를 포함하는 6개 튜플로 표현한다.

결정적 유한 오토마타는 M = (I, Q, f, F, σ)의 5개 튜플이며 전이함수 f: Q × I → Q는 현재 상태와 입력에 대해 하나의 다음 상태를 정한다. 비결정적 유한 오토마타도 5개 튜플이지만 전이함수는 ε 이동을 허용하고 상태들의 집합 P(Q)를 결과로 가질 수 있다.

마르코프 연쇄

마르코프 연쇄는 마르코프 성질을 가진 이산확률과정이다. 전이확률행렬과 상태전이도로 표현하며, n단계 전이확률은 채프만-콜모고로프 방정식을 이용한다. n단계 전이확률행렬은 P⁽ⁿ⁾ = P^(n-1)P = Pⁿ이다.

형식 언어와 형식 문법

알파벳은 기호들의 유한집합이고 문자열은 기호들의 유한한 순서열이다. Σⁿ, Σ⁺, Σ^*와 언어의 연산을 구분한다. 형식문법은 형식언어를 정의하는 방법이며 G = (V, T, P, S)로 표현하고 문법 G가 생성하는 언어를 L(G)라 한다.

Chomsky 계층은 문법을 무제약 문법(Type 0), 문맥의존 문법(Type 1), 문맥자유 문법(Type 2), 정규 문법(Type 3)으로 분류한다.

15. 학습 확장 자료

강의는 학기 전체 복습을 마친 뒤 수학적 사고를 넓힐 여름방학 독서와 영상 자료를 소개한다. 골드바흐의 추측을 소재로 한 사람들이 미쳤다고 말한 외로운 수학 천재 이야기, 수학사의 흐름을 다룬 살인을 부르는 수학 공식, 라이프니츠에서 부울과 튜링으로 이어지는 계산의 역사를 다룬 수학자, 컴퓨터를 만들다가 추천 도서로 제시된다.

영상 자료로는 EBS 초대석의 수학은 세상을 푸는 언어다 - 수학자 박형주와 EBS 프로그램 문명과 수학 제2편 원론이 소개된다. 공식 암기에 머물지 않고 수학 개념이 문명과 컴퓨터의 발전에 어떻게 연결되었는지 살펴보는 데 활용할 수 있다.

핵심 개념 정리

1. 정의와 기호를 정확히 이해하고 논리적 사고와 표현을 반복 훈련한다.
2. 명제와 논리연산을 바탕으로 유효추론과 여러 증명방법을 구분한다.
3. 집합·행렬·관계·함수는 데이터를 구조화하고 변환하는 핵심 수학구조이다.
4. 부울대수는 논리와 집합의 연산구조를 디지털 논리회로로 연결한다.
5. 그래프와 트리는 네트워크, 경로, 검색, 최소 연결 문제를 모델링한다.
6. 조합이론은 경우의 수·확률·점화식·비둘기집 원리로 이산적 문제를 계산한다.
7. 정수론은 나눗셈·합동·소수의 성질을 바탕으로 RSA 암호에 활용된다.
8. 오토마타와 형식 언어는 상태 변화, 계산 과정, 언어 생성 규칙을 수학적으로 표현한다.

이산수학의 각 단원은 독립된 공식 모음이 아니다. 논리는 증명의 기반이 되고, 집합은 관계와 함수를 표현하며, 행렬과 부울대수는 관계와 회로를 계산하고, 그래프와 트리는 구조와 알고리즘을 모델링한다. 시험에서도 정의·기호·적용 조건과 단원 사이의 연결을 함께 이해하는 것이 중요하다.

예상문제 20선

1. 이산수학의 학습 목표로 가장 적절한 것은?

① 연속함수의 미분 계산만 반복한다.② 정의와 기호를 사용하지 않고 직관만 따른다.③ 실생활의 세부사항을 제거하지 않고 그대로 복사한다.④ 문제해결에 쓰이는 수학구조와 추론기법을 이해하고 활용한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
이산수학은 이산적 구조를 이해하고 문제를 모델링하며 논리적으로 표현·해결하는 역량을 기르는 과목이다.

2. 추상화에 대한 설명으로 옳은 것은?

① 문제와 무관한 내용을 더 많이 추가한다.② 핵심을 남기기 위해 관련 없는 내용을 제거하거나 단순화한다.③ 알고리즘의 단계를 의도적으로 모호하게 만든다.④ 컴퓨터에서 처리할 수 없는 형태로 바꾼다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
추상화는 문제해결에 필요한 핵심 구조를 보존하고 부수적인 세부사항을 제거하거나 단순화하는 과정이다.

3. 명제의 정의로 옳은 것은?

① 참과 거짓을 구분할 수 있는 문장 또는 수식② 모든 의문문과 명령문③ 진리값을 결정할 수 없는 표현만④ 변수 값을 정해도 진리값이 없는 식

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
명제는 반드시 참 또는 거짓이라는 진리값을 분명히 가져야 한다.

4. 수학적 귀납법의 순서로 옳은 것은?

① 귀납단계 → 반례 → 기본단계② 귀납가정 → 모순 → 전수검사③ 기본단계 → 귀납가정 → 귀납단계④ 대우 → 역 → 이

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
출발점에서 성립함을 보이고 n = k를 가정한 뒤 그 가정으로 n = k + 1의 성립을 증명한다.

5. 두 유한집합 A, B의 합집합 크기를 구하는 식은?

① |A ∪ B| = |A| + |B| - |A ∩ B|② |A ∪ B| = |A| - |B|③ |A ∪ B| = |A ∩ B|만④ |A ∪ B| = |A||B|

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
|A|와 |B|를 더하면 교집합이 두 번 세어지므로 |A ∩ B|를 한 번 뺀다.

6. 행렬곱 AB가 정의되기 위한 크기 조건은?

① A와 B의 모든 원소가 같아야 한다.② 두 행렬이 모두 영행렬이어야 한다.③ A와 B의 행 수만 같아야 한다.④ A의 열 수와 B의 행 수가 같아야 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
행렬곱의 각 원소는 A의 행과 B의 열을 내적하므로 두 벡터의 길이가 같아야 한다.

7. 동치관계가 만족해야 하는 세 성질은?

① 전사성·단사성·전단사성② 반사성·대칭성·추이성③ 교환성·결합성·분배성④ 연결성·완전성·정규성

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
한 집합 위의 관계가 반사적이고 대칭적이며 추이적이면 동치관계이다.

8. 역함수가 존재하기 위한 함수의 조건은?

① 전사이지만 단사는 아니어야 한다.② 상수함수여야 한다.③ 전사이면서 단사인 전단사함수여야 한다.④ 공역에 대응되지 않는 원소가 있어야 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
대응을 거꾸로 했을 때도 각 입력에 하나의 출력이 정해지려면 원래 함수가 일대일대응이어야 한다.

9. 부울함수를 간소화하는 주된 목적은?

① 진리값을 없애기 위해② 모든 변수를 서로 다른 문자로 바꾸기 위해③ 같은 기능의 논리회로를 더 간단하게 구현하기 위해④ 논리연산을 집합연산과 완전히 분리하기 위해

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
부울식의 항과 문자를 줄이면 동일한 출력을 더 적고 단순한 논리게이트 구성으로 구현할 수 있다.

10. 그래프에서 경로(path)의 특징은?

① 모든 변과 꼭지점을 반복해야 한다.② 모든 꼭지점이 서로 다른 트레일이다.③ 반드시 모든 꼭지점을 포함한다.④ 변이 없는 그래프만을 뜻한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
트레일은 변을 반복하지 않고, 그중 꼭지점도 반복하지 않는 트레일이 경로이다.

11. 오일러 투어와 해밀턴 경로의 핵심 차이는?

① 둘 다 면의 수만 센다.② 오일러는 색, 해밀턴은 가중치만 다룬다.③ 둘 다 모든 꼭지점의 차수가 같아야 한다.④ 오일러는 모든 변, 해밀턴은 모든 꼭지점을 기준으로 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
오일러 투어는 각 변을 한 번씩 사용하고, 해밀턴 경로는 각 꼭지점을 한 번씩 방문한다.

12. n개의 꼭지점을 가진 연결그래프 G가 트리일 필요충분조건은?

① 변의 수가 n - 1이다.② 변의 수가 n + 1이다.③ 모든 꼭지점의 차수가 n이다.④ 반드시 하나 이상의 사이클이 있다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
연결그래프에서 변이 n - 1개이면 사이클 없이 모든 꼭지점이 연결된 트리와 동치이다.

13. n개 원소 중 순서를 무시하고 r개를 뽑는 방법의 수는?

① n^r② C(n, r) = n!/[r!(n-r)!]③ P(n, r) = n!/(n-r)!④ (n-1)!만

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
조합은 순서를 고려하지 않으므로 순열의 수를 선택한 r개 원소의 배열 수 r!로 나눈다.

14. 조건부 확률 P(A|B)의 식으로 옳은 것은?

① P(A) + P(B)② P(A ∪ B)/P(A)③ P(B)/P(A ∩ B)④ P(A ∩ B)/P(B)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
B가 발생한 상황으로 표본공간을 제한하므로 A와 B가 함께 발생할 확률을 P(B)로 나눈다.

15. 비둘기집 원리에 대한 설명으로 옳은 것은?

① k개 상자에는 최대 k개 물체만 넣을 수 있다.② 모든 상자에 반드시 같은 수가 들어간다.③ k개 상자에 N개 물체를 넣으면 어떤 상자에는 적어도 ⌈N/k⌉개가 들어간다.④ N이 k보다 크면 배치가 불가능하다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
물체를 아무리 고르게 배치해도 평균의 올림값 이상을 포함하는 상자가 적어도 하나 존재한다.

16. 산술의 기본정리가 보장하는 것은?

① 1보다 큰 정수는 소수들의 곱으로 유일하게 표현된다.② 모든 정수는 하나의 소수이다.③ 합성수는 소인수를 갖지 않는다.④ 최대공약수는 언제나 1이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
소인수의 순서를 제외하면 1보다 큰 모든 정수의 소인수분해는 유일하다.

17. 결정적 유한 오토마타의 전이함수 형태는?

① f: Q × I → Q② f: Q → P(Q)만③ f: I → ∅④ f: Q × I → 모든 실수

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
결정적 오토마타에서는 현재 상태와 입력 기호가 주어지면 다음 상태가 하나로 결정된다.

18. 마르코프 연쇄의 n단계 전이확률행렬은?

① P + n② nP의 원소별 합③ P⁽ⁿ⁾ = P^(n-1)P = Pⁿ④ 항상 단위행렬

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
전이확률행렬을 n번 곱한 Pⁿ이 n단계 뒤의 상태 전이확률을 나타낸다.

19. Chomsky 계층에서 Type 3에 해당하는 것은?

① 무제약 문법② 문맥의존 문법③ 문맥자유 문법④ 정규 문법

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
Chomsky 계층은 Type 0 무제약, Type 1 문맥의존, Type 2 문맥자유, Type 3 정규 문법으로 분류한다.

20. 이산수학 단원과 컴퓨터 응용의 연결로 옳은 것은?

① 정수론 - 화면 색상 보정만② 그래프 - 컴퓨터 네트워크③ 부울대수 - 자연어 번역만④ 트리 - 연속함수 미분만

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
그래프는 꼭지점과 변으로 네트워크의 연결구조를 모델링하므로 컴퓨터 네트워크에 활용된다.