오토마타(Automaton) : 컴퓨터와 하드웨어를 모델링하는 도구
- 입출력. 약간의 임시 기억장소를 가질 수 있음. 입력과 출력으로부터의 변환 과정에서 필요한 결정들을 내릴 수 있음.
형식 언어(Formal Language) : 생성 규칙에 따라 생성되는 모든 문장들의 집합(a set of sentences)
문법(Grammar) : 형식 언어로 문장들을 생성하기 위한 규칙들의 집합(a set of rules)
집합(Set) : 주어진 성질을 만족시키는 대상들의 모임. 집합은 대문자 원소는 소문자.
a ∈ A : a는 집합 A의 원소
합집합, 교집합, 차집합, 여집합, 부분집합 X⊆S , 진부분집합(자기 자신이 들어가지 않는 집합) Y⊂S
멱집합 2^S(집합의 모든 부분집합을 모아 놓은 것. 공집합과 원래 집합을 원소로 포함),
카타시안 곱 A X B (각 집합의 원소를 각 성분으로 하는 순서쌍들의집합)
A = {1, 2}, B {a, b, c, d}
A X B = {(1, a), (1, b) ... (2, d)}
원소나열법 S = {1,2,3,4,5}
조건제시법 S = {n|n은 자연수 1< n < 5}
오일러 다이어그램 혹은 벤다이어그램
칸토어-반슈타인 정리
|A| <= |B| 이고 |A| >= |B|이면 |A| = |B|이다.
대칭차집합 : A △ B 교집합을 뺀 합집합. xor와 비슷
관계 : 객체들 간의 연관성 표현.
=> 관계를 표현하는 대표적인 방법이 집합이다.
-집합 간 서로 다른 두 원소 간 관련사항
-집합에 대한 연산에 닫혀있다. (관계는 곱집합의 부분 집합이다.)
이항관계 R
두 집합의 곱집합 A X B의 부분집합
정의역의 원소를 치역에 할당
동치 관계 : 관계 R에서 반사 관계, 대칭 관계, 추이 관계가 모두 성립.
집합의 원소들이 같다. (a, b)에 대하여 a와 b가 같다.
반사 관계 : 집합 A의 임의 원소 a에 대하여 aRa를 만족하는 이항 관계 즉, (a, a) ∈ R
대칭 관계 : aRb이면, bRa도 만족하는 관계.
추이 관계 : aRb이고 bRc이면 aRc를 만족하는 관계.
mod 합동 : x와 t를 m으로 각각 나누었을 때 나머지가 같은 관계.
mod합동은 동치 관계.
정의역 : 관계 R의 원소 순서쌍에서 첫 번째 원소의 집합, dom(R) = {a|(a, b) ∈ R} ⊆ A
치역 : 관계 R의 원소 순서쌍에서 두 번째 원소의 집합, ran(R) = {b|(a, b) ∈ R} ⊆ B
공변역 : 관계 R의 원소인 순서쌍에서 두 번째 원소가 포함돼있는 집합, codom(R) = {b|b ∈ B} ⊆ B
함수 f: S1 -> s2
정의역 : S1의 부분집합
치역 : S2의 부분집합
정의역에 사용되는 원소는 2번 이상 사용 불가
(x,y) ∈ f and (x,z) ∈ f인 경우 y = z
전역함수 : S1의 모든 원소에 대해 정의가 되어 있음
부분함수 : S1의 일부 원소에 대해 정의가 됨
빅오 표기법 : 차수가 가장 큰 항이 영향을 미침 -> 다른 항들은 상대적으로 무시
f(n)과 g(n)이 주어졌을 때, 모든 n >= n0에 대하여 |f(n)| <= c|g(n)|을 만족하는 2개 상수 c와 n0가
존재하면 f(n) = O(g(n))이다.
상한 표시
빅 오메가 표기법 : 모든 n >= n0에 대하여 |f(n)| >= c|g(n)|을 만족하는 2개 상수 c와 n0가 존재하면
f(n) = 오메가(g(n))
하한 표시
빅 세타 표기법 : c1|g(n)| <= |f(n) <= c2|g(n)|을 만족하는 3개의 상수 c1, c2와 n0가 존재하면
g(n) = 세타(g(n))이다.
하한인 동시에 상한을 표시
그래프 : 꼭지점(vertex, node)의 집합 V와 서로 다른 꼭지점의 쌍을 연결하는 변(Edge)의 집합으로 구성되는 구조.
그래프 선상에서 꼭지점끼리는 인접. 변은 각 꼭지점에 근접.
방향 그래프 G = <V, E>. 변에 방향이 있음.
차수 : 꼭지점 v에 근접하는 변의 수.
외차수 : 방향 그래프에서 꼭지점 v를 시작으로 하는 화살표의 수 (출발)
내차수 : v를 끝으로 하는 화살표의 수 (도착)
가중치 그래프 W[u,v]
부분 그래프 : 꼭지점의 수 감소
부분신장 그래프 : 꼭지점은 그대로, 변의 수 감소
오일러 공식 : v - e + s = 2
오일러 경로 : 모든 변을 꼭 한 번씩 지나는 경로.
해밀턴 경로 : 모든 꼭지점을 꼭 한 번씩 지나는 경로.
인접행렬 : nxn행렬에서 변이 없으면 0 있으면 1
인접리스트 : 각 꼭지점에 인접하는 꼭지점들을 Linked List로 표현
다익스트라 알고리즘 : 인접 거리를 계속해서 업데이트
https://hsp1116.tistory.com/42
깊이 우선 탐색(DFS) : 끝까지 갔다가 되돌아오는 식
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
너비 우선 탐색(BFS) : 인접 노드를 우선 탐색
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
--------------------------------------------------------------------------------
명제 : 참 | 거짓을 판단할 수 있는 문장
negation : 부정
conjunction : 논리합
disjunction : 논리곱
implication : 함축 혹은 조건문(충분조건)
biconditional : 상호조건문(필요충분조건). IFF. xor과 반대
xor는 둘 중 하나만 or인지를 검사
T->F 면 F임을 인지
p->q라 할 때,
q -> p 역 converse
ㄱq -> ㄱp 대우 contrapositive
ㄱp -> ㄱq 이 inverse
p->q일 때와 ㄱq->ㄱp일 때의 값이 같은 값을 가지는지를 확인해서 동치인지를 확인할 수 있다.