1. Definitions 1.GraphG=(V,E): 두 집합으로 구성.V: 정점(Vertex)의 유한 집합. 예: V={v1,v2,…,vn}E: 정점 사이의 관계를 나타내는 이진 관계(간선). 예: E={e1,e2,…,en}그래프 종류방향 그래프(Directed Graph): E가 순서쌍으로 정의됨. ek=(vi,vj)무방향 그래프(Undirected Graph): E가 순서쌍이 아닌 집합으로 정의됨. ek={vi,vj}간선의 속성간선 e=(a,b):e는 a와 b에 연결됨.e는 a에서 나오는(out of) 간선.e는 b로 들어가는(on) 간선.a는 b와 인접(adjacent)함.(a,a): 자기 루프(loop).고립 정점(Isolated Vertex): 연결된 간선이 없는 정점. 2. Walk (경로..

1. Automata Theory 1. Alphabets알파벳 ∑: 알파벳은 하나 이상의 기호(symbol)로 이루어진 유한 집합이다. 예를들어, Σ={0,1} 또는 Σ={a,b,c} 등이 가능symbol(기호): 알파벳의 원소. 예를들어 0과 1이 symbolstring(문자열): 알파벳의 기호를 나열하여 만들어진 유한한 길이의 순서. 예를들어 010은 Σ={0,1}위에서 정의된 string2. Powers of ∑ (알파벳의 거듭제곱)알파벳 ∑의 거듭제곱은 문자열의 길이를 정의하기 위한 중요한 개념이다. Σ^1=Σ 3. Strings(문자열)Σ+: 길이가 1 이상인 모든 문자열의 집합. 이 집합은 Σn(길이 n인 문자열의 집합)을 무한히 더한 형태로 정의된다. Σ∗: 길이가 0 이상인 모든 문자열의 ..

1. Ring1. Ring 링은 비어 있지 않은 집합으로, 2가지 이항연산( 덧셈과 곱셈)이 존재하는 구조이다. 집합 R이 링이 되기 위한 조건: 덧셈: 교환법칙, 결합법칙, 항등원 존재, 역원 존재 → abelian group 곱셈: 결합법칙, 분배법칙 Ring 예시: 정수, 유리수, 실수, 복소수, 정수 행렬은 덧셈과 곱셈이 정의된 Ring의 대표적 예시이다. 예를 들어, 정수에서는 2+3=5이고, 2*3=6이다. 이러한 연산에서 덧셈 항등원은 0이고, 곱셈 항등원은 1이다. 2. Commutative Ring with UnityCommutative Ring: 모든 a,b에 대해 ab=ba(곱셈의 교환법칙)이 성립하는 ringRing with Unity: R의 모든 원소에 대해 곱셈 항등원(u)이 존..

1. Group[덧셈에서의 역원은 더해서 0이되는것, 곱셈에서의 역원은 곱해서 1이되는것. 물론 최종 결과는 모듈러(나머지)정리한것!] 1. GroupGroup의 기본 조건: Closure(닫힘성), Associativity(결합법칙), Identity(항등원), Inverse(역원)2. Abelian GroupCommutative(교환법칙) 만족하는 group을 Abelian Group이라고 한다.는 abelian group이다.3. Zn∗ 은 Abelian Group이다.4. Order of Group (군의 차수) : 군 안에 포함된 원소의 개수, ∣G∣ Infinite Order(무한 차수) Zn의 차수 : {0,1,2....,n-1} , 집합 크기=nZp∗: 소수 p에 대해,..

1. Algebra, Group, Ring 1. Algebra(대수):  집합 K와 여러 연산자들로 이루어진 구조 : 실수 집합 R과 덧셈, 뺄셈, 곱셈, 나눗셈 같은 연산자들로 정의되는 구조: Boolean 대수에서 참(True)과 거짓(False)을 AND, OR, NOT으로 연산.K: 데이터의 집합으로 |K∣는 집합의 크기(유한 또는 무한)를 나타낸다.연산자 op: 단항(Unary, i=1), 이항(Binary, i=2)연산으로 나뉜다.("연산자"는 중요한 역할을 하는데, 연산자가 결합법칙이나 항등원 등의 성질을 만족시키는 지에 따라 다양한 수학적 구조로 구분한다.)2. Identity(항등원)와 Zero(영원)항등원은 어떤 연산 ⊕에 대해, 항등원 e는 e⊕a=a⊕e=a를 만족하는 원소{Z,+}에..