홈 > 강의소개
이산수학
신흥철 교수
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
숙명여자대학교
Microsoft
현) 유니와이즈 전임교수
AI가 이끄는 스마트한 학습 경험, AI 튜터와 함께 더 빠르고, 더 깊게 학습하세요.
긴 강의 내용을 AI가 핵심만 요약하여 복습 시간을 단축시킵니다.
강의에서 가장 중요한 키워드와 개념을 자동으로 추출해 제공합니다.
학습한 내용을 바탕으로 AI가 생성한 퀴즈를 풀며 이해도를 점검합니다.
모르는 부분을 24시간 언제든 AI 튜터에게 질문하고 답변을 받습니다.
총 14개 챕터, 42강으로 구성되어 있습니다.
| 제목 | 강의시간 | 상세내용 |
|---|---|---|
| 1장. 명제와 논리 | ||
|
[1강] 명제
|
0:
23:
04
|
|
|
명제와 논리의 기본 개념 및 연산
• 명제와 논리 연산자: 참/거짓으로 구분되는 명제 정의 및 진릿값, 부정·논리곱·논리합·배타적 논리합 등의 기본 논리 연산자 기능. • 합성명제와 연산자 우선순위: 명제 결합을 통한 합성명제 구조 및 논리 연산자 간 우선순위(괄호, 부정, 논리곱/합) 적용 원리. • 항진명제, 모순명제, 사건명제: 항상 참/거짓 또는 가변적인 합성명제 유형 구분 및 진리표를 통한 진릿값 체계적 분석. |
||
|
[2강] 명제. 논리적 동치
|
0:
38:
53
|
|
|
논리적 동치와 조건명제 규칙
• 조건명제 규칙: `p → q`의 진리값 정의 및 충분/필요조건 파악, 쌍방조건명제 `p ↔ q`의 필요충분조건 이해. • 명제의 역, 이, 대우: `p → q`와 `¬q → ¬p`의 논리적 동치성 및 `p ≡ q`의 개념과 활용. • 논리적 동치 법칙: 항등, 드모르간, 분배 등 주요 법칙을 이용한 복합 명제 간략화 및 증명 절차. |
||
|
[3강] 변수를 포함한 명제와 한정자. 논리
|
0:
32:
38
|
|
|
변수 포함 명제, 한정자 및 논리적 추론 법칙
* 명제함수: 변수 포함 명제의 진릿값 판별 함수로, 논의영역과 한정자를 통해 명제 범위 정의. * 한정자: 명제함수의 논의 영역 내 진릿값을 정의하는 전칭(∀) 및 존재(∃) 기호로, 복합 명제 해석에 핵심. * 논리적 추론 법칙: 참인 전제에서 결론을 도출하는 긍정논법, 부정논법, 삼단논법 등 유효추론 원리. |
||
| 2장. 증명 | ||
|
[4강] 증명
|
0:
38:
05
|
|
|
수학적 증명 방법론
* 수학적 증명 정의: 공리, 정의, 정리 등 명제의 참을 확인하는 기본 원리와 논리적 사고 기반 확립. * 주요 증명법 유형: 직접증명법과 간접증명법(대우, 모순, 반례, 존재)의 개념 및 적용 전략 학습. * 수학적 귀납법: 자연수에 대한 명제 증명을 위한 기본가정, 귀납가정, 귀납단계의 체계적 활용. |
||
| 3장. 집합 | ||
|
[5강] 집합의 개념 및 종류
|
0:
42:
22
|
|
|
집합의 개념과 종류
• 집합 개념: 명확한 기준과 원소 기반 정의, 원소나열법/조건제시법 표기, 기수, 유한/무한, 상등 관계의 핵심 원리. • 집합 종류: 전체집합, 공집합, 부분집합, 진부분집합의 정의와 특징 분석. • 집합 포함관계: 집합 간의 관계를 규정하는 5가지 핵심 정리 및 증명 원리 학습. |
||
|
[6강] 집합의 연산
|
0:
39:
52
|
|
|
집합의 연산과 기수
• 집합 연산 기초: 합집합, 교집합, 차집합, 여집합 등 기본 연산의 정의, 표기법, 서로소 관계 이해 • 기수 계산 원리: 두 개 및 세 개 집합의 합집합과 교집합 기수 계산 공식 및 중복 보정 방법 적용 • 특수 집합 연산: 곱집합(순서쌍)과 멱집합(부분집합의 집합)의 개념, 기수, 특징 분석 |
||
|
[7강] 집합의 대수법칙과 분할
|
0:
42:
03
|
|
|
집합의 대수법칙과 분할
* 집합의 대수법칙: 명제 논리 기반의 항등, 지배, 분배, 드모르간 등 집합 연산의 기본 원리 및 법칙 학습 * 주요 법칙 증명: 드모르간, 흡수법칙 및 대칭 차집합의 논리적 증명 과정을 통해 복잡한 집합 연산 응용력 강화 * 집합의 분할: 주어진 집합을 공집합이 아닌 서로소 부분집합으로 나누는 정의와 성질을 이해하여 집합 분류 체계 확립 |
||
| 4장. 수의 표현 | ||
|
[8강] 수와 그 성질. 수 체계
|
0:
47:
38
|
|
|
수의 표현과 수체계 기초
* **수의 종류 및 연산 특성**: 자연수부터 복소수까지의 수 개념 정의와 닫힘, 교환, 결합, 분배 법칙 등 수 연산의 기본 성질 분석. * **수체계 정의 및 표현**: 기수와 자릿값 원리를 기반으로 10진수, 2진수, 8진수, 16진수 등 다양한 수체계의 표현 구조 이해. * **수체계 간 변환 및 사칙연산**: 10진수와 타 진수 체계 간 변환 절차 및 각 수체계별 덧셈, 뺄셈, 곱셈, 나눗셈 연산 방법 습득. |
||
|
[9강] 보수의 표현 및 연산
|
0:
59:
52
|
|
|
컴퓨터에서의 데이터 표현과 보수 연산
* 보수 개념: 1의 보수와 2의 보수 정의를 통해 컴퓨터 음수 표현 및 뺄셈 연산을 덧셈으로 변환하는 기본 원리. * 데이터 표현 방식: 부호화-절대치, 1의 보수, 2의 보수 표현의 특징, 0 처리의 유일성, 데이터 범위 및 초과(Overflow) 문제점. * 보수 연산 처리: 1의 보수 덧셈 시 End-around carry, 2의 보수 덧셈 시 캐리 무시 원리를 통해 뺄셈을 정확히 구현하는 컴퓨터의 연산 메커니즘. |
||
|
[10강] 수의 표현 요약
|
0:
17:
51
|
|
|
수 체계 변환 및 보수 연산
• 수 체계 변환: 10진수 정수부와 소수부를 2진수로 변환하는 절차 및 원리 이해 • 보수 연산: 컴퓨터 뺄셈을 덧셈으로, 음수를 표현하는 1의 보수 및 2의 보수 원리 및 연산 절차 학습 • 보수의 10진수 변환: 1의 보수와 2의 보수 값을 10진수 음수로 정확하게 해석하는 변환 방법론 숙지 |
||
| 5장. 행렬 | ||
|
[11강] 행렬의 개념. 연산. 종류. 행렬식
|
1:
08:
32
|
|
|
행렬 개념, 연산, 종류 및 행렬식
• 행렬 개념 및 연산: 2차원 배열로서의 행렬 정의, 덧셈·스칼라 곱·행렬 곱셈 등 기본 연산 절차 및 성질 분석 • 주요 행렬 종류: 영행렬·단위행렬·정사각행렬·전치행렬·부울행렬 등 각 행렬의 정의와 고유 특성 이해 • 행렬식 계산 원리: 정사각행렬의 스칼라 값인 행렬식 정의, 소행렬·여인수를 활용한 고차 행렬식 계산 방법 숙지 |
||
|
[12강] 역행렬. 연립 1차 방정식
|
0:
30:
10
|
|
|
역행렬 및 연립 1차 방정식 해법
* 역행렬 정의 및 계산: $AB=BA=I$ 만족, $\det(A) \neq 0$ 조건 하 행렬식 및 여인수 전치를 활용한 계산 원리. * 연립 1차 방정식 해법: $AX=B$ 첨가행렬 구성, 가우스 소거법과 가우스 조르단 소거법을 통한 체계적인 해 도출 절차. * 가우스 조르단 소거법 응용: $\begin{pmatrix} A & I \end{pmatrix}$ 형태 변환을 통해 역행렬 $A^{-1}$을 계산하는 방법론 이해. |
||
| 6장. 관계 | ||
|
[13강] 관계의 개념. 표현. 성질
|
0:
40:
59
|
|
|
관계의 개념, 표현 및 성질
* 관계 개념: 두 집합 원소 간 순서쌍 집합이자 곱집합 부분집합으로, 정의역, 공변역, 치역 정의 및 이항/n항/역관계 유형 분류. * 관계 표현: 화살표 선도, 좌표도표, 관계행렬, 방향그래프 등 관계 구조 시각화 절차 요약. * 관계 성질: 반사, 비반사, 대칭, 반대칭, 추이성 등 관계의 고유 특성 정의 및 부등호 관계를 통한 의미 분석. |
||
|
[14강] 합성관계
|
0:
51:
21
|
|
|
합성관계 개념 및 연산
• 합성관계: 두 관계의 정의와 연결 조건, 관계 행렬의 부울곱 연산을 통한 계산 원리 • 관계의 거듭제곱: $R^n$ 정의와 반복 부울곱 계산, 추이관계 성립 조건 ($R^n \subseteq R$) 분석 • 관계 연산: 합집합, 교집합, 차집합의 정의 및 관계 행렬을 이용한 부울 연산 구조 |
||
|
[15강] 관계의 폐포. 동치관계
|
0:
54:
05
|
|
|
관계의 폐포와 동치관계
• 관계의 폐포: 특정 성질을 만족하도록 관계를 확장하는 개념으로, 반사·대칭·추이 폐포의 정의와 원리 분석. • 연결 관계($R^*$): 관계의 추이 폐포를 나타내며, 관계 행렬의 부울 곱과 합을 활용한 계산 절차 요약. • 동치 관계: 반사·대칭·추이 세 성질을 모두 만족하는 관계로, 전체 집합을 상호 배타적인 동치류로 분할하는 원리 제시. |
||
|
[16강] 부분순서관계
|
0:
35:
22
|
|
|
부분순서관계와 하세도표
• 부분순서관계: 반사성, 반대칭성, 추이성을 만족하는 원소 간 순서 정의 및 모든 원소 쌍 비교 시 완전순서로 분류 • 하세도표: 부분순서관계를 반사 및 추이적 관계를 생략한 위계적 배치로 시각화하여 관계 구조를 간결히 표현 • 극대/극소/최대/최소 원소: 하세도표 내에서 원소 간 비교 가능성을 기준으로 집합의 특성 및 구조를 분석하는 핵심 원소 정의 |
||
| 7장. 함수 | ||
|
[17강] 함수의 개념 및 성질에 따른 분류
|
0:
39:
58
|
|
|
7장. 함수의 개념과 분류
• 함수 정의: 정의역 모든 원소를 공변역 단 하나의 원소에 대응시키는 규칙과 정의역, 공변역, 치역 구조 분석. • 함수 연산: 합과 곱 연산 시 정의역이 교집합으로 결정되는 원리 및 함수의 분류 체계 이해. • 단사·전사·전단사 함수: 일대일 대응, 공변역 전체 커버 등 각 함수의 핵심 성질과 판별 조건 학습. |
||
|
[18강] 합성함수
|
0:
37:
32
|
|
|
합성함수 정의 및 성질
• 합성함수 정의: 두 함수를 순차 적용하여 새로운 함수를 생성하며, 선행 함수의 공변역과 후행 함수의 정의역 일치 조건 필수. • 합성함수 성질: 교환법칙 불성립, 결합법칙 성립; 정의역은 선행 함수, 공변역은 후행 함수를 따르는 구조 분석. • 합성함수의 단사성, 전사성, 전단사성: 개별 함수의 성질 전이 조건과, 합성함수의 성질이 개별 함수에 미치는 영향 분석. |
||
|
[19강] 함수의 종류
|
0:
36:
26
|
|
|
함수의 다양한 종류와 핵심 특성
* **항등함수:** 입력값을 그대로 반환하며, 합성함수 연산 시 본래 함수의 성질을 유지하는 핵심 함수. * **역함수:** 전단사함수일 때만 존재하며, 원래 함수의 작동을 역으로 변환하고 항등함수와 합성 관계를 가짐. * **상수/특성/바닥/천정함수:** 정의역 원소를 단일 값에 매핑(상수), 집합 소속 여부를 0/1로 표현(특성), 실수를 최대/최소 정수로 변환(바닥/천정)하는 특수 함수들. |
||
| 8장. 그래프 | ||
|
[20강] 그래프 개념
|
0:
31:
09
|
|
|
Summary Content:
그래프의 개념 및 종류 • 그래프 기초: 꼭짓점·변으로 구성된 자료 구조이며 인접·경로·순환 등 핵심 용어 정의. • 그래프 유형: 다중·방향·가중치 속성으로 분류되며 각 유형의 특성과 활용 방안 분석. • 그래프 차수: 꼭짓점에 근접하는 변의 수이며, 차수 합 공식 및 홀수점 정리로 구조적 특성 파악. |
||
|
[21강] 그래프의 종류
|
0:
41:
16
|
|
|
그래프의 다양한 종류와 특성
• 그래프 기본 구조: 부분/부분신장 그래프는 포함 관계, 동형 그래프는 구조적 동일성 정의. • 연결성 및 평면성: 연결 그래프는 경로 존재, 평면 그래프는 변 교차 없는 표현과 오일러 공식($v-e+s=2$) 관계 정리. • 특수 그래프 유형: 완전 그래프는 모든 꼭짓점 연결, 정규 그래프는 차수 동일, 이분/완전이분 그래프는 꼭짓점 분리 및 변 연결 방식 정의. |
||
|
[22강] 오일러와 해밀턴
|
0:
32:
14
|
|
|
오일러 및 해밀턴 그래프의 정의와 특성
• 오일러 그래프 정의 및 조건: 모든 변을 한 번씩 지나는 경로/순환을 포함하며, 모든 꼭짓점 차수 짝수 또는 홀수점 수 0/2개인 연결 그래프의 특성. • 해밀턴 그래프 정의 및 조건: 모든 꼭짓점을 한 번씩 지나는 경로/순환을 포함하며, 완전 그래프($K_n$)는 항상 존재하고 완전 이분 그래프($K_{n,n}$)는 조건부 존재함. • 오일러와 해밀턴 그래프 비교: 변 중심 순회(오일러)와 꼭짓점 중심 순회(해밀턴)의 기본 개념 및 존재 조건 분석. |
||
|
[23강] 그래프의 표현 및 활용
|
0:
41:
48
|
|
|
그래프 표현 및 탐색 알고리즘
• 그래프 표현 방식: 인접행렬과 인접리스트를 통한 그래프 데이터의 구조화 및 특징 분석. • 최단경로 알고리즘: Dijkstra 알고리즘을 활용한 최단경로 탐색 절차와 거리 업데이트 원리 이해. • 그래프 탐색 기법: 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 원리 및 탐색 순서 차이점 비교. |
||
| 9장. 트리 | ||
|
[24강] 트리의 개념
|
0:
22:
09
|
|
|
트리의 개념과 정의
• 트리 개념 정의: 비순환 연결 그래프로, 특정 루트 노드를 가지며 모든 노드 사이에 유일한 단순 경로가 존재하는 데이터 구조. • 트리 관련 용어: 노드, 루트, 부모, 자식, 잎, 중간 노드, 레벨, 높이 등 트리의 구성 요소와 관계를 정의. • 트리의 구조적 특징: 노드 수와 변의 수 관계 (e=v-1) 및 유일 경로 존재 등 트리를 정의하는 여러 동치 조건의 수학적 원리 학습. |
||
|
[25강] 이진 트리. 이진 탐색 트리
|
0:
50:
58
|
|
|
이진 트리와 이진 탐색 트리의 이해
• 이진 트리: 부모 노드 최대 2개인 트리 구조, 완전·포화·편향 이진 트리로 분류하며 노드 수 계산 원리 적용 • 이진 트리 구현 및 순회: 배열·연결 리스트 구현 방식, 전위·중위·후위 순회 절차를 통해 모든 노드 방문 • 이진 탐색 트리: 데이터 키 값 기반 노드 배치 원리로 효율적 탐색을 가능하게 하는 특수 이진 트리 |
||
|
[26강] 트리의 활용
|
0:
39:
57
|
|
|
트리 활용: 최소 신장 트리와 허프만 코드
* 최소 신장 트리(MST): 그래프의 모든 꼭짓점을 최소 비용으로 연결하는 구조를 프림 및 크루스칼 알고리즘으로 구현. * 허프만 코드: 문자 빈도 기반 가변 길이 인코딩으로 데이터 압축 효율을 극대화하며, 허프만 알고리즘으로 생성. |
||
| 10장. 순열, 조합, 확률 | ||
|
[27강] 합의 법칙과 곱의 법칙. 순열
|
0:
35:
01
|
|
|
순열의 개념, 공식 및 응용
• 합의 법칙·곱의 법칙: 독립 사건의 합과 동시 발생 사건의 곱을 통한 경우의 수 계산 기본 원리. • 순열: 서로 다른 $n$개 중 $r$개를 순서대로 나열하는 절차와 특정 조건(이웃·비이웃) 적용 방법. • 중복순열·같은 원소를 포함하는 순열: 중복 허용 및 동일 원소 포함 조건에 따른 순열 공식과 경우의 수 계산 구조. |
||
|
[28강] 조합. 이항계수
|
1:
06:
39
|
|
|
조합 및 이항계수 기본 개념
• 조합 및 중복조합: 순서/중복 유무에 따른 원소 선택 방법, 그룹 분할 원리 및 관련 공식 활용. • 이항정리: 이항식의 거듭제곱 전개 일반식, 이항계수 정의 및 주요 성질 이해. • 파스칼의 삼각형: 이항계수 시각화, $n-1Cr-1 + n-1Cr = nCr$ 점화 관계 및 생성 원리. |
||
|
[29강] 확률
|
0:
44:
27
|
|
|
확률의 정의, 덧셈 정리 및 곱셈 정리 이해
• 확률의 정의: 표본공간과 특정 사건의 발생 가능성을 수치화하고 계산하는 기본 원리. • 확률의 덧셈 정리: 배반사건과 여사건 개념을 활용하여 복합 사건의 합집합 확률을 계산하는 방법. • 확률의 곱셈 정리 및 조건부 확률: 사건의 동시 발생 확률과 특정 조건 하의 사건 발생 가능성을 분석하는 원리. |
||
|
[30강] 확률분포
|
0:
29:
55
|
|
|
확률분포의 정의, 평균, 분산 및 표준편차
• 확률변수·확률분포: 사건의 결과를 수치화하는 변수와 그 값의 확률 대응관계를 확률질량함수로 정의 • 기댓값: 확률변수의 각 값과 확률을 곱한 합으로 확률변수의 평균값을 계산 • 분산·표준편차: 기댓값으로부터 데이터가 흩어진 정도를 편차 제곱의 기댓값으로 측정하고, 그 제곱근으로 산포도를 표현 |
||
|
[31강] 점화관계
|
0:
32:
25
|
|
|
점화관계의 개념과 피보나치, 하노이 탑
• 점화관계 정의: 수열 항의 선행 항 종속성 기반 규칙으로, 다음 항 정의 및 수학적 증명을 통해 점화식 유도 원리. • 피보나치 수열, 하노이 탑: 각 문제의 점화식($f_n = f_{n-1} + f_{n-2}$, $H_n = 2H_{n-1} + 1$)을 도출하여 문제 해결 및 계산 절차 분석. • 계산 복잡도: 점화관계 문제에서 $2^N, N!$ 등 높은 복잡도와 $N^2, N \log N$ 등 효율적 복잡도 유형을 비교 분석. |
||
| 11장. 부울대수와 논리게이트 | ||
|
[32강] 부울대수와 부울함수의 표현
|
0:
47:
14
|
|
|
부울대수와 정규식
• 부울대수 기초: 0과 1 기반 논리 계산 체계 정의, 부울변수, 연산자, 부울함수, 연산 순서 학습. • 부울대수 법칙: 항등, 흡수, 드모르간 등 주요 법칙 이해 및 부울식 간략화를 통한 회로 설계 효율성 증대. • 최소항과 정규식: $n$개 리터럴 부울곱 최소항 정의와 정규식(DNF) 표현, 일반 부울함수 정규식 변환 절차 습득. |
||
|
[33강] 정규식의 간략화. 논리게이트
|
0:
35:
30
|
|
|
정규식 간략화 및 논리 게이트
* **정규식 간략화:** 논리회로의 효율성, 경제성, 신뢰성 확보를 위한 복잡한 부울 함수 최소항식 변환 과정. * **부울대수법칙·카르노맵:** 부울 함수를 대수적 연산 및 시각적 맵핑을 통해 정규식으로 간략화하는 핵심 방법론. * **논리 게이트:** NOT, AND, OR, NAND, NOR, XOR, XNOR 등 부울 논리 기반 회로의 기본 요소와 이를 활용한 부울 함수 표현 원리. |
||
| 12장. 알고리즘 | ||
|
[34강] 알고리즘의 개념 및 효율성
|
0:
32:
46
|
|
|
알고리즘의 개념 및 효율성 분석
• 알고리즘 개념: 문제 해결을 위한 명령어 집합 정의 및 입력, 출력, 정확성 등 7가지 핵심 특성 이해. • 알고리즘 표현: 순서도와 의사코드 활용, 복잡도 개념으로 문제 해결 효율성 평가. • Big-O 표기법: 시간 복잡도 분석 도구 정의 및 최악의 경우 실행 시간 예측, 복잡도 간 관계 이해. |
||
|
[35강] 다양한 알고리즘 (1)
|
0:
38:
56
|
|
|
다양한 알고리즘: 유클리드 및 재귀 알고리즘
• 유클리드 알고리즘: 최대공약수(GCD) 계산을 위한 모듈러 연산 기반의 효율적인 반복 절차와 증명 원리. • 재귀 알고리즘: 자기 자신을 호출하여 문제를 해결하며, 명확한 종료 조건과 입력 크기 감소가 필수. • 재귀 효율성: 피보나치 수열에서 지수 함수적($O(2^n)$) 시간 복잡도를 보여 성능 분석의 중요성 부각. |
||
|
[36강] 다양한 알고리즘 (2)
|
0:
46:
38
|
|
|
탐색 알고리즘 개요 및 비교 분석
* 탐색 알고리즘: 데이터 집합 내 특정 원소를 찾는 체계적 과정으로 순차 탐색과 이진 탐색으로 분류. * 순차 탐색: 정렬되지 않은 데이터를 처음부터 비교하는 방식으로, 시간 복잡도는 $O(n)$. * 이진 탐색: 정렬된 데이터에서 탐색 범위를 절반씩 줄여 $O(\log n)$의 효율적인 시간 복잡도로 원소를 탐색. |
||
|
[37강] 다양한 알고리즘 (3)
|
1:
20:
01
|
|
|
정렬 알고리즘 주요 개념 및 시간 복잡도 분석
• 정렬 알고리즘 기초: 버블 및 삽입 정렬의 $O(n^2)$ 시간 복잡도를 가지는 인접 비교와 삽입 원리를 학습. • 퀵/합병 정렬: 분할 정복 기반 $O(n \log n)$ 효율성의 피벗 분할 및 재귀적 합병 메커니즘을 분석. • 시간 복잡도 분석: $f(n) = 2f(n/2) + n$ 재귀 관계식으로 $O(n \log n)$ 유도 과정 및 퀵 정렬의 $O(n^2)$ 최악 조건 이해. |
||
| 13장. 그룹과 정보전송 | ||
|
[38강] 준그룹과 그룹
|
0:
40:
06
|
|
|
그룹과 준그룹의 개념 및 성질
* **그룹 이론 기초**: 준그룹(이진 연산, 결합 법칙), 모노이드(항등원), 그룹(역원)의 단계별 대수 구조 정의 및 조건 이해. * **가환그룹 및 소거 성질**: 그룹에 교환 법칙이 추가된 가환그룹 개념과 그룹 내에서 성립하는 소거 법칙 특성 분석. * **부분그룹**: 그룹의 부분집합 중 항등원 포함, 닫힘, 역원 조건을 만족하는 핵심 하위 구조 정의 및 예시. |
||
|
[39강] 그룹의 곱과 몫
|
0:
43:
40
|
|
|
그룹의 곱, 몫, 정규 부분그룹
• 그룹의 곱: 두 그룹의 Cartesian product가 각 성분별 연산을 통해 새로운 그룹을 형성하는 원리 탐구 • 합동 관계 및 몫 그룹: 그룹 연산과 호환되는 동치 관계인 합동 관계를 기반으로 몫 그룹의 정의와 구조를 파악 • 정규 부분그룹: 좌잉여류와 우잉여류가 일치하는 부분그룹으로 몫 그룹 구성의 핵심 개념을 이해 |
||
|
[40강] 2진 정보의 전송
|
0:
49:
43
|
|
|
2진 정보 전송 및 오류 검출 원리
• 코드화 함수 개념: 2진 메시지에 오류 검출 및 정정을 위한 여유 비트를 추가하며 이진 연산으로 정의 • 해밍 거리 및 최소 거리: 코드화 메시지 간 차이를 측정하여 코드의 오류 검출 능력을 정량화하는 원리 • 해밍 (7, 4) 코드: 특정 패리티 비트 구조를 활용해 1비트 오류를 교정하고 2비트 오류를 검출하는 방식 |
||
| 14장. 형식 언어와 오토마타 | ||
|
[41강] 형식 언어. 문법과 의미
|
0:
43:
49
|
|
|
형식 언어와 오토마타의 기본 개념 및 문법 계층 구조
* 형식 언어 기본: 알파벳, 문자열, 언어 정의 및 클린/양의 폐포로 구성되는 언어의 원리 이해. * 문법 구성 및 유도: 비단말/단말 기호, 생성 규칙, 시작 기호로 이루어진 문법의 유도 및 축약 과정 파악. * 촘스키 계층 구조: 문법 규칙 제약(Type 0-3)에 따른 언어 분류 및 각 타입별 인식기(튜링 머신, LBA, PDA, FA) 특징 분석. |
||
|
[42강] 문법의 표기법. 정규 표현과 유한 오토마타
|
0:
44:
56
|
|
|
문법 표기법 및 정규 표현과 유한 오토마타
• 문법 표기법 (BNF, EBNF): 형식 언어의 구조를 정의하고 기술하는 핵심 원리 학습 • 정규 표현: 타입 3 문법 언어를 표현하는 연산, 대수학적 성질 및 문법 변환 절차 분석 • 유한 오토마타: 정규 언어 인식 모델(DFA, NFA) 정의 및 상태 전이도 표현, 정규 문법·정규 표현과의 상호 변환 관계 이해 |
||
신흥철 교수님
이산수학
