1강
알고리즘 표현 언어 - 의사코드(순차문, 조건문, 반복문), 프로그래밍 언어, 순서도
알고리즘을 자유롭게 표현하는건 순서도
의사코드 - 프로그래밍 언어를 흉내내어 작성한 코드
순서도는 알고리즘의 작동방식을 도식화한다.
2강
조건명제에서 p가 F면 q의 T,F여부 상관없이 T
모순명제는 진리값이 언제나 F인 명제
p이고 p->q이면 q이다.
p or q이면 p이다 (x) p and q이면 p 이다
3강
공리 : 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정, 별도의 증명 X 참으로 이용
증명 : 특정한 공리들을 가정, 제안된 명제가 참임을 입증
정리 : 공리로부터 증명된 명제
- 보조정리 : 정리를 증명하는 과정 중에 사용되는 증명된 명제
- 따름정리 : 정리로부터 쉽게 도출되는 부가적인 명제
직접증명법 (연역법)
명제 변형 X 증명, 공리와 정의, 정리를 논리적으로 직접 연결하여 증명
수학적 귀납법
자연수 n에 대한 명제의 성질을 증명
기본단계 => 귀납가정 => 귀납단계
기본단계 : n의 출발점에서 명제가 성립하는가 확인
귀납가정 : n = k 일 때, 명제가 성립한다고 가정
귀납단계 : n = k + 1 일 때도 명제가 성립함을 증명
간접증명법
증명해야 할 명제를 증명하기 쉬운 형태로 변형하여 증명
대우증명법 : P -> Q => ~Q -> ~P
모순증명법 : P -> Q 증명 시, ~P를 가정하면 모순 발생
-귀류법 : 오류로 귀착 , 배리법 : 이치에 어긋나게 됨
반례 증명법 : 전체 한정자가 포함된 명제가 거짓임을 증명
존재 증명법 : 존재 한정자가 포함된 명제가 참임을 증명
- 구성적 존재 증명법 : 명제함수를 증명할 때 P(x)를 참으로 만드는 x를 찾거나 찾는 과정
- 비구성적 존재 증명법 : 명제함수를 증명할 때 P(x)를 참으로 만드는 x를 찾지 않고 우회적으로 명제가 타당함을 보임
다양한 증명방법
전수 증명법 : 명제에서 유도될 수 있는 경우의 수가 적을 때 일일이 모든 경우의 수를 조사
조합적 증명법 : 두 집합의 원소의 개수가 동일함을 증명
- 전단증명 : 원수가 n개인 집합 A와 원소가 m개인 집합 B를 찾은 후, 두 집합이 1:1 관계로 n = m임을 증명
- 중복산정 : 동일한 집합의 원소를 두 가지 방법으로 세어 결과가 n과 m이면 n = m임을 증명
컴퓨터 이용 증명법 : 증명하기 복잡한 경우 컴퓨터의 데이터 처리능력을 사용
ex)4색 정리직접증명법은 명제를 변형하지 않고 증명하는 방법으로 연역법이라고 한다.
모든 자연수n에 대해 명제가 성립합을 증명하려면 수학적 귀납법이 유용하다.
전수증명법은 명제로부터 유도될 수 있는 경우의 수가 적을 때 모든 경우에 대해 참인지 확인하는 방법이다.
4강
X가 Y에 포함되는 집합임을 증명하려면 임의의 원소 x에 대해 항상 x∈y를 만족한다.
부분집합 : A의 모든 원소가 B의 원소라면 A는 B의 부분집합 (𝑨 ⊆ 𝑩 ⇔ ∀x 또는 𝐀 ⊂ 𝑩 )
진부분집합 : 𝑨 ⊆ 𝑩, 𝑩 ⊆ 𝑨 ⇔ 𝑨 ⊆ 𝑩, 𝑨 ≠ 𝑩
상동 : 𝑨 = 𝑩 ⇔ 𝑨 ⊆ 𝑩 𝒂𝒏𝒅 𝑩 ⊆ 𝑨
서로소 : 서로 겹치는 원소가 없는 사이
분할 : 집합을 공집합이 아닌 부분집합들로 나눌 때 그 집합의 모든 원소들이 각각 나눠진 부분집합들 중 하나에만 포함될 경우 전체 집합을 그 집합의 분할이라고 함
멱집합 : 집합의 모든 부분집합들의 집합 ( P(A) 로 표기)
집합연산
-합집합 : 전체 집합 | 𝑨 ∪ 𝑩 = {𝒙 ∈ 𝑼｜𝒙 ∈ 𝑨 ∨ 𝒙 ∈ 𝑩}
-교집합 : 집합끼리 겹치는 부분집합 | 𝑨 ∩ 𝑩 = {𝒙 ∈ 𝑼｜𝒙 ∈ 𝑨 ∧ 𝒙 ∈ 𝑩}
-차집합 : 집합에서 교집합을 제거한 집합 | 𝑨 − 𝑩 = {𝒙 ∈ 𝑼｜𝒙 ∈ 𝑨 ∧ 𝒙 ∉ 𝑩}
-여집합 : 집합의 반전되는 영역 | 𝑨 𝒄 = 𝑼 − 𝑨 = {𝒙 ∈ 𝑼｜𝒙 ∉ 𝑨}
-대칭차집합 : 합집합에서 교집합을 제거한 집합 | 𝑨⨁𝑩 = {𝒙 ∈ 𝑼｜𝒙 ∈ 𝑨 ∪ 𝑩 ∧ 𝒙 ∉ 𝑨 ∩ 𝑩}
-곱집합 : 𝑨 × 𝑩 = 𝒂, 𝒃 𝒂 ∈ 𝑨, 𝒃 ∈ 𝑩 }
집합의 대수법칙
1. 집합의 크기에 관한 성질
합집합의 크기 : |𝑨 ∪ 𝑩| = |𝑨| + |𝑩| − |𝑨 ∩ 𝑩|
서로소인 집합의 합집합의 크기 : |𝑨 ∪ 𝑩| = |𝑨| + |𝑩|
2. 포함관계 및 항등식
원소 논증 : ∀𝒙 ∈ 𝑿 → 𝒙 ∈ Y
집합의 항등식 : 교환법칙, 결합법칙, 분배법칙, 항등법칙, 보수법칙, 이중보수법칙, 멱등법칙, 전체 합계 법칙, 드모르간의 법칙, 홉수 법칙, 𝑼와 ∅의 여집합, 차집합법칙
5강
합의 연산법칙 : 교환법칙, 결합법칙, 항등원, 역원
스칼라곱 연산법칙 : 결합법칙, 분배법칙 행렬은 곱연산의 교환법칙이 성립되지 않는다.
행렬의 곱 : 𝑨(𝒎 × 𝒏 행렬)와 𝑩(𝒏 × 𝒍)의 행렬의 곱 𝑨𝑩는 𝒎 × 𝒍 행렬
가우스 소거법
역행렬이 존재한다면 방정식의 해를 구할 수 있음
행 교환, 행 스케일링, 행 대체 연산
행제형 행렬 : 영영행이 아닌 행은 위에, 각 행의 선도원소가 오른쪽으로, 선도원소 아래는 0인 행렬
소거행제형행렬 : 모든 선도원소가 1이고, 선도원소가 있는 열에서 선도원소만 0이 아닌 행제형행렬
교차(meet) : 원 부울행렬의 교차 연산은 각 원소를 논리곱(AND)으로 계산하며, aij∧bij로 정의,
두 행렬의 같은 위치 원소가 모두 1일 때만 결과 행렬의 해당 원소가 1
행렬의 종류
- 영행렬: 모든 원소가 0으로 이루어진 행렬로, 행렬 연산에서 0의 역할을 함.
- 스칼라행렬: 대각원소가 모두 같은 값(스칼라)이고, 나머지 원소는 모두 0인 대각행렬
- 부울행렬: 모든 원소가 0 또는 1인 행렬
- 정방행렬: 행과 열의 수가 같은 n×n 행렬
- 대각행렬: 정방행렬에서 주대각선 이외의 모든 원소가 0인 행렬
- 단위행렬(항등행렬): 대각원소가 모두 1이고 나머지는 0인 정방행렬
- 대칭행렬: 전치행렬과 자기 자신이 같은, 즉 a₍ᵢⱼ₎ = a₍ⱼᵢ₎인 정방행렬
- 역대칭행렬(반대칭행렬): a₍ᵢⱼ₎ = -a₍ⱼᵢ₎이고, 대각원소가 모두 0인 정방행렬
- 상삼각행렬: 주대각선 아래의 모든 원소가 0인 정방행렬
- 하삼각행렬: 주대각선 위의 모든 원소가 0인 정방행렬
- 전치행렬: 행과 열을 서로 바꾼 행렬
- 역행렬: 행렬 곱셈에서 단위행렬이 되는 역원 행렬
- 계수행렬: 연립일차방정식에서 변수 계수만으로 이루어진 행렬
- 확대행렬(첨가행렬): 계수행렬에 등식의 우변 상수항을 추가한 행렬
6강
관계의 방향을 잘봐야하고 역방향은 R'(위 작대기)
관계의 표현은 화살표 도표, 방향그래프, 부울행렬 등으로 가능한데, 방향그래프는 A에서 A로가는 관계인거 체크.
관계의 종류
역관계 : 현재 관계의 역으로 된 관계
𝑿, 𝒀 ∶ 집합 𝑹 ∶ 𝑿에서 𝒀로의 관계
𝑹 −𝟏 ∶ 𝑹의 역관계(inverse relation)
𝑹 −𝟏 = {(𝒚, 𝒙) | (𝒙, 𝒚) ∈ 𝑹 } ⊂ 𝒀 × 𝑿
합성관계
𝑨, 𝑩, 𝑪 ∶ 집합 𝑹 ∶ 𝑨에서 𝑩로의 관계, 𝑺 ∶ 𝑩에서 𝑪로의 관계
𝑹과 𝐒의 합성관계(composition relation)
𝑺 ∘ 𝑹 = {(𝒂, 𝒄) | 𝒂 ∈ 𝑨, 𝒃 ∈ 𝑩, 𝒄 ∈ 𝑪, (𝒂, 𝒃) ∈ 𝑹, (𝒃, 𝒄) ∈ 𝑺 }
𝑺 ∘ 𝑹 ⊂ 𝑨 × 𝑪 (𝑨에서 𝑪로의 관계)
𝑴𝑹은 𝒎 × 𝒏 부울행렬
𝑴𝑺은 𝒏 × 𝒑 부울행렬
𝑴𝑺∘𝑹은 𝒎 × 𝒑 부울행렬
=> 𝑴𝑺∘𝑹 = 𝑴𝑹⊙𝑴𝑺
동치관계 : 반사적, 대칭적, 추이적인 관계
동치류 : 동치관계에 있는 집합
𝑨 ∶ 집합
𝑹 ∶ 𝑨에서의 동치관계
𝑨의 임의의 원소 𝒂에 대해서 |𝒂| = {𝒙 ∈ 𝑨 (𝒂, 𝒙) ∈ 𝑹} 를 𝒂의 동치류
7강
전사함수는 공역=치역, 단사함수는 1대 1
x에서 y방향이 상, 반대가 역상
역함수 : 전단사함수인 경우 역관계의 함수
계승함수 : 양의 정수 n에 대해 n!로 표기하며, 1부터 n까지 모든 자연수를 곱한 값(팩토리얼)
바닥함수 : 실수 x에 대해 x보다 작거나 같으면서 가장 큰 정수를 구하는 함수
|𝒙| = 𝒎𝒂𝒙 {𝒎 ∈ ℤ | 𝒎 ≤ 𝒙 }
천장함수 : 실수 x에 대해 x보다 크거나 같으면서 가장 작은 정수를 구하는 함수
|𝒙| = 𝒎𝒊𝒏 {𝒏 ∈ ℤ | 𝒙 ≤ 𝒏 }
나머지 함수 : 정수 n과 양의 정수 m에 대해 n을 m으로 나눴을때 나머지를 구하는 함수
8강
기호별 진리표 다시 제대로 봐두기
디지털 논리회로 : 디지털 신호로 입력하여 논리연산을 통해 디지털 신호로 출력
AND 게이트 : 논리곱, F = X· Y
OR 게이트 : 논리합, F = X + Y
NOT 게이트 : 논리부정, F = X'
NAND 게이트 : F = 𝑿' + 𝒀'
NOR 게이트 : F = X'· Y'
XOR 게이트 : 배타적 논리합, F = 𝑿'𝒀 + 𝑿𝒀'
XNOR 게이트 : F = 𝑿'𝒀' + 𝑿𝒀
부울대수
| 항등법칙 | 항등원(0, 1)과 연산 시 자기 자신이 됨 | X+0=X , |
| 지배법칙 | 0 또는 1과 연산 시 결과가 0 또는 1이 됨 | X+1=1 , |
| 멱등법칙 | 같은 값을 더하거나 곱해도 값이 변하지 않음 | X+X=X , |
| 부정법칙 | 변수와 그 보수의 연산 결과 | X+X′=1 , X⋅X′=0 , (X′)′=X |
| 교환법칙 | 항의 순서를 바꿔도 결과가 같음 | , X⋅Y=Y⋅X |
| 결합법칙 | 결합 순서를 바꿔도 결과가 같음 | X+(Y+Z)=(X+Y)+Z , X⋅(Y⋅Z)=(X⋅Y)⋅Z |
| 분배법칙 | 곱셈과 덧셈의 분배가 가능 | X⋅(Y+Z)=X⋅Y+X⋅Z X+Y⋅Z =(X+Y)⋅(X+Z) X+Y⋅Z=(X+Y)⋅(X+Z) |
| 드모르간 법칙 | AND/OR와 보수의 변환 관계 | (X+Y)′ = X ′⋅Y ′ (X⋅Y)′ = X ′+ Y′ |
| 흡수법칙 | 일부 항이 다른 항에 흡수됨 | X+X⋅Y=X , X⋅(X+Y)=X |
쌍대성 원리 : 부울식에서 논리합(+)과 논리곱(·), 논리상수 1과 0을 서로 바꾸면 원래 부울식의 쌍대(dual)식을 얻는다는 원리
부울함수의 보수
- 드모르간 법칙: 부울함수의 보수는 드모르간 법칙을 이용해 구할 수 있음
- (X+Y)′=X′⋅Y′
- (X⋅Y)′=X′+Y′
- 쌍대성 원리 이용:
- 먼저 함수 F의 쌍대(dual)를 구함
- 쌍대식에서 정상형(예: X)과 보수형(예: X')을 서로 바꿈
부울함수의 대수적 간소화
항결합 : 두개의 항을 결합하여 하나의 항으로 만드는 방법
문자소거 : 중복된 문자를 제거
중복항 첨가 : 부울함수의 진리값이 변하지 않도록 하면서 간소화를 위한 적절한 항을 첨가
9강, 10강
그래프는 꼭지점과 변으로 구성
병렬변 : 두 꼭지점을 연결하는 변이 복수개
루프 : 동일한 꼭지점을 연결하는 변
고립된 꼭지점 : 어떠한 변도 연결 X 꼭지점
동형 : 꼭지점과 변의 이름을 제외하고는 모두 동일한 그래프
방향 그래프 : 변이 방향을 가지는 그래프
무향 그래프 : 변이 방향이 없는 그래프
단순 그래프 : 루프와 병렬 변을 가지지 않는 무향 그래프
𝑮 = 𝑽, 𝑬 , 𝑯 = (𝑽 ′ , 𝑬′)
(1) 𝑽 ′ ⊆ 𝑽, 𝑬 ′ ⊆ 𝑬 ⇒ 𝑯를 𝑮의 부분 그래프(subgraph)
(2) 𝑽 ′ = 𝑽, 𝑬 ′ ⊆ 𝑬 ⇒ 𝑯를 𝑮의 신장 부분 그래프 (spanning subgraph)
총 차수 : 인접한 변의 개수
진입차수 : 들어오는 변의 개수
진출차수 : 나가는 변의 개수
path ⊂ trail ⊂ walk
워크 : 꼭지점과 변들을 순서대로 나열
트레일 : 워크의 변들이 서로 다른 것
닫힌 트레일 : 변들이 서로 다르면서 처음과 끝의 꼭지점이 동일함
사이클 : 닫힌 트레일 중에서 마지막 바로 전 꼭지점까지 모두 서로 다를경우. 포함된 변의 개수를 사이클의 길이라고 한다.
경로 : 워크의 꼭지점이 모두 다른 것
그래프 종류
완전 그래프 : 그래프에 속한 모든꼭지점이 다른 꼭지점과 인접한 경우
이분 그래프 : 그래프의 V가 V1, V2로 분할되어있고, 모든 변들이 V1과 V2꼭지점을 연결하는 경우
완전 이분 그래프 : 양쪽의 모든 꼭지점이 변으로 연결되어있을때
k-정규 그래프 : 모든 꼭지점들이 동일한 수의 인접한 꼭지점을 갖는 그래프
그래프 표현
발생 행렬 : 꼭지점을 행으로 변을 열로 하여 발생관계를 표현
인접 행렬 : 꼭지점을 행과 열로 하여 꼭지점과 꼭지점 사이의 인접관계를 표현
인접 리스트 : 각 꼭지점에 인접하는 꼭지점들을 차례로 연결 리스트로 표현
그래프의 탐색
평면그래프 : 모든 변을 서로 교차하지 않게 그릴 수 있는 그래프 (정규, 완전 그래프)
ex) 오일러의 공식, 4색 정리
오일러 투어 : 그래프의 모든 변을 각각 한 번씩만 지나는 트레일(경로)
- 연결 그래프가 오일러 투어를 가지기 위해서는 모든 꼭지점의 차수는 짝수
해밀턴 경로 : 그래프의 모든 꼭지점을 한 번씩만 지나는 경로
그래프의 활용
가중 그래프 : 그래프의 각 변에 실수값(가중치)이 붙여진 그래프
ex) 최단 경로 문제, 최소 신장 트리 문제
총 차수는 모든 꼭지점의 차수의 합
v−e+f=2 꼭지점-변+면 = 2
11강
트리 : 사이클이 없는 단순 연결 그래프
Trivial Tree : 꼭지점 하나로 구성된 트리
Empty Tree : 꼭지점이 하나도 없는 트리
Forest : 한 개 이상의 트리로 구성된 트리
루트 트리 : 루트라 부르는 노드가 존재하며 나머지 노드들이 서로 분리된 집합으로 나뉘는 트리
트리 -> 루트 트리 (서브트리, 루트 노드)
이진 트리
공집합이거나 모든 노드가 최대 2개의 서브트리를 갖는 루트 노드인 트리
완전 이진 트리 : 왼쪽 노드부터 차례로 채워진 이진트리 다 채워지지 않아도됨!
- 같은 노드 수를 갖는 트리 중 최소 높이
-n개의 노드를 갖는 이진 트리의 최소 높이 : 𝑯𝒎𝒊𝒏 = |𝒍𝒐𝒈𝟐n|
포화 이진트리 : 모든 노드가 채워진 이진 트리
이진 탐색 트리
정의 : 모든 노드가 탐색을 위한 키값을 가지며 왼쪽 서브트리의 키값들은 해당 키값보다 작아야 한다
검색:
1. 루트 노드로 설정
2. 주어진 키를 비교
-일치 : 키 반환, 탐색 멈추기
-노드보다 작으면 : 왼쪽 자식을 탐색 노드로 설정, 왼쪽이 없을 경우 키 없음을 반환하며 탐색 멈추기
-노드보다 크면 : 오른쪽 자식을 탐색 노드로 설정, 오른쪽이 없을 경우 키 없음을 반환하며 탐색 멈추기
3. 2번 과정을 반복
트리의 활용
신장 트리 : 그래프의 모든 꼭지점을 포함하는 트리
최소 신장 트리 : 모든 변의 가중치 합을 총 가중치라 할 때, 가장 작은 신장 트리
Kruskal 알고리즘
간선(변) 중심, 가중치가 가장 낮은 간선부터 선택해 사이클 없이 트리를 만듬
- 모든 간선을 가중치 오름차순으로 정렬합니다.
- 가장 작은 간선부터 하나씩 선택해 트리에 추가합니다.
- 이때 사이클이 생기지 않도록(Union-Find 등으로) 검사합니다.
- 모든 정점이 연결될 때까지(간선 수가 정점 수-1이 될 때까지) 반복합니다.
Prim 알고리즘
꼭지점 중심, 한 정점에서 시작해 인접한 가장 작은 가중치의 간선을 선택하며 트리를 확장
- 임의의 정점 하나를 트리에 추가
- 트리에 연결된 정점에서 인접한 간선 중 가중치가 가장 작은 간선을 선택해, 연결된 정점을 트리에 추가
- 모든 정점이 트리에 포함될 때까지 반복
트리의 무게 - 리프노드의 수
트릐의 차수는 트리 내 각 노드의 차수중 최대차수 (워크북 11장 2번)
12강
곱의 법칙(AND, Multiplication Principle)
- 두 사건 A, B가 각각 m, n가지 방법으로 일어날 때, A와 B가 연속적으로 일어나는 전체 경우의 수는 m×n
합의 법칙(OR, Addition Principle)
- 두 사건 A, B가 동시에 일어날 수 없을 때(서로소), A 또는 B가 일어날 경우의 수는 m+n입니다.
- 만약 겹치는 경우가 있다면, ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣로 계산
집합의 합집합 크기(포함-배제 원리)
- 두 집합 :
∣A∪B∣=∣A∣+∣B∣−∣A∩B∣ - 세 집합 A,B,C:
∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣ - 만약 집합이 서로소(교집합 없음)라면, 단순히 모두 더하면 됨.
∣A∪B∣=∣A∣+∣B∣
순열
순열, 중복순열, 원순열
조합
𝟎 ≤ 𝒓 ≤ 𝒏을 만족하는 정수 𝒓, 𝒏 에 대하여, 𝒏개의 원소를 갖는 집합에서 𝒓 개의 원소를 순서 없이 뽑는 경우의 수
이산확률
표본공간: 실험의 모든 결과의 집합
사건: 표본공간의 부분집합
수학적 확률 :
표본공간 𝑺가 유한하며 각 사건이 발생할 가능성이 모두 동일 하다고 가정할 때 사건 𝑬(⊂ 𝑺) 가 발생할 확률
조건부 확률 :
표본공간 𝑺에 두 사건 𝑨, 𝑩가 있고, 𝑷 𝑩 > 𝟎이라고 하자. 사건 𝑩가 발생했다는 가정하에 사건 𝑨가 발생할 확률
점화식
점화식 : 수열의 항 사이에서 성립하는 관계식
비둘기집 원리 : n+1마리 이상의 비둘기를 n개의 집에 넣으면, 어떤 집에는 반드시 2마리 이상이 들어간다는 원리
13강
나눗셈
a, b가 정수, a가 0이 아닐 때, b=ac 를 만족시키는 정수 c가 있다면 a가 b를 나머지 없이 나눈다
=> a는 b의 약수(인수), 배수는 a|b로 표현
최대공약수 : d = gcd(a, b)로 표현, 0이 아닌 두 정수 a,b에 대해 d|a, d|b인 최대의 양의 정수 d를 a와 b의 최대 공약수
gcd(a,b) = 1인 경우, a,b는 서로소
베주의 항등식 : 적어도 하나는 0이 아닌 두 정수 a,b가 gcd(a, b) = d라 할 때, ax + by = d를 만족하는 정수 x, y 존재
- a,b가 서로소 => gcd(a,b) = 1 => ∃𝒙, 𝒚 ∈ 𝒁, 𝒂𝒙 + 𝒃𝒚 = 1
유클리드 호제법(알고리즘)
- 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘
- 두수가 서로 상대방 수를 나눠 원하는 수를 얻는 알고리즘
- a,b,q,r 가 정수면, a = bq + r이면 gcd(a,b)=gcd(b,r)
나머지 연산
나머지 함수 : 정수 n과 양의 정수 m에 대해 n을 m으로 나눴을 때 나머지를 구하는 함수, n mod m으로 표기
모듈로 합동 : a, b가 정수 m이 양의 정수면, a-b가 m으로 나눠떨어지면 a와 b는 모듈로-m 합동, a = b(mod m)으로 표기
a mod m = b mod m이 필요충분조건
소수와 소인수분해
소수 :1보다 큰 자연수 p는 p의 양의 인수가 1과 p뿐일 때
합성수 :1보다 크면서 소수가 아닌 자연수
소인수 : 주어진 자연수의 약수 중에서 소수인 것
소인수분해 : 합성수를 소인수들의 곱으로 표현
소수 판별법
- 만약 n이 합성수라면, n의 소인수 중 하나는 루트n보다 같거나 작다
가장 큰 소수 찾기
- 𝟐^𝒑 − 𝟏 (단, 𝒑는 소수 | 합성수일 경우 소수가 아님)
소수 정리
RSA 암호
14강
오토마타
자동장치, 스스로 움직이는 기계 컴퓨터 : 유한상태 오토마타
튜링머신 : 인간 사고과정을 구현하는 오토마타, 컴퓨터의 수학적 모델, 테이프, 헤드, 상태기록부, 유한한 표로 구성, 상태의 개수는 유한
형식언어 : 프로그래밍 언어들의 일반적인 특성들을 추상화
형식문법 : 프로그래밍 언어의 생성 규칙을 추상화
- 형식 언어: 유한한 기호(예: 알파벳)들을 조합해 만든 문자열들의 집합
- 형식 문법: 이 문자열들을 어떻게 만들지에 대한 규칙들, 즉, 언어를 생성하는 법칙
유한 오토마타 : 6개의 튜플로 구성
입력기호의 유한집합, 출력기호의 유한집합, 상태의 유한집합, 전이함수, 출력함수, 초기상태
마르코프 연쇄
마르코프 연쇄는 시간에 따라 상태가 바뀌는 확률적 모델. 유한 오토마타와 비슷하지만, 각 전이가 확률로 결정됨
- 마르코프 성질: 무기억성! 미래 상태는 오직 현재 상태에만 의존, 과거는 상관없음.
- 정상 마르코프 연쇄: 시간의 변화에 무관하다는 성질전이 확률의 불변성).
- 이산 확률 과정: 시간 흐름이 뚜렷하게 구분됨. (예: X₁, X₂, ..., Xn)
- 전이확률: 현재 상태에서 다음 상태로 전이될 확률.
유한 오토마타와 마르코프 연쇄는 상태 + 전이라는 구조는 같지만,
- 유한 오토마타는 결정적(입력에 따라 상태가 정해짐),
- 마르코프 연쇄는 확률적(다음 상태가 확률로 결정됨).
표현 방법
전이확률 행렬 (Transition Matrix)
확률을 숫자로 정리한 표, 현재 상태가 1일 때, 다음 상태가 1일 확률: 0.7, 상태 2일 확률: 0.3
상태 전이도 (State Diagram)
상태들을 원으로 그리고, 화살표로 전이 확률을 표시해요. 유한 오토마타의 상태 그래프와 거의 같음.
n단계 전이확률과 채프만-콜모고로프 방정식
- 어떤 상태에서 n단계 후에 다른 상태로 갈 확률을 구하는 공식
- 이를 통해 마르코프 연쇄가 시간이 지났을 때 어떻게 변할지 예측할 수 있음
- 이 개념은 구글의 페이지랭크(PageRank) 알고리즘에도 쓰임.
→ 웹 페이지가 얼마나 자주 방문될지, 어떤 페이지가 중요한지 계산할 때 사용.
촘스키 계층 (Chomsky Hierarchy)
형식 문법을 네 가지 유형으로 나눈 계층 구조로 아래로갈수록 더 단순한 구조(제 3유형이 가장 단순)
| 촘스키계층, 형식문법 | 형식언어 | 오토마타 | ||
| 0형 (무제약 문법) | 아무 제한 없음, 재귀열거언어 | α → β (α, β는 어떤 문자열도 가능) | 튜링머신 | |
| 1형 (문맥 의존 문법) | 문맥에 따라 변형, 문맥 의존 언어 | α → β (길이: | 선형 유한 오토마타 | |
| 2형 (문맥 자유 문법) | A만 왼쪽에 옴, 문맥 자유 언어 | A → β (A는 변수, β는 기호들의 조합) | 푸시 다운 오토마타 | |
| 3형 (정규 문법) | 가장 단순함, 정규언어 | A → α 또는 A → αB (α는 터미널, B는 변수) | 유한 상태 오토마타 |