본문 바로가기

학교 공부/이산수학10

[이산수학] 정규언어, 정규표현 Finite State Automaton A = (Q, ∑, δ, q0, F) - DFA δ : Q x ∑ -> Q - NFA δ : Q x ∑ -> 2^Q // 멱집합(다음 상태가 없거나, 또는 여러 개) NFA는 사람에게 편하다 -> 컴퓨터 DFA로 변환할 수 있다. (=> 두 오토마타가 인식하는 스트링 집합은 동일하다.) Subset Contrauction algorithm : NFA -> DFA - Q^d = 2Q //상태 집합 - ∑^d = ∑ //입력 기호 집합 - q0^d = {q0} //초기 상태 - F^d = {S∈Q^d | S∩F≠공집합} // 승인 상태 집합 - δ^d : Q^d x ∑ -> Q^d는 상태 전이 함수이다. // 상태 전이 함수 NFA를 DFA로 변환하시오 1) NFA .. 2020. 6. 2.
[이산수학] 유한상태 오토마타(FSA)의 종류, NFA와 DFA > 언어, 문법, 오토마타의 관계를 이해해야 한다. 언어는 문자열들을 정의 -> 문법은 언어에 속한 문자열들을 생성 -> 오토마타는 문자열들을 승인 자연어? 정형언어? 우리는 c, java와 같이 기계 처리를 할 수 있는 정형 언어를 배울 것이다. 언어란? 문자열들의 집합이다. ∑를 기호들의 집합이라고 한다. ∑*는 그럼 모든 문자열의 집합이다. 언어 L∈∑*이다. (*는 공집합까지 포함하므로 λ∈∑*로 표현할 수 있다.) 정규문자의 존재? ∑ = {a,b} L1 = {(ab)ⁿ | n≥0}= (ab)* L2 = {aⁿ | n≥0} = a* L3 = {aⁿbⁿ | n≥0} ≠ (a*b*)이기 때문 // 정규 표현 부재 언어의 결합 두 언어 L1과 L2의 결합 L1L2는 {uv | u∈L1, v∈L2} Q.. 2020. 5. 20.
[이산수학] 님(nim) 게임 > (게임 규칙) - 여러 그룹이 존재 - '나'부터 시작 - 1개 혹은 전부를 제거 가능 - 최소 하나 이상의 돌이 제거 - 마지막 돌 제거하는 사람이 진다. (게임은? Botton-up 방식으로 진행) // 단말노드에서 루트 노드로 1단계 : 단말 노드에 값 배정 2단계 : Min-Max 적용을 위해 위 노드의 값을 반복하여 정한다. 3단계 : 루트 노드가 +1이면 승리, -1이면 패배 4단계 : 1에 기여한 경로가 승리 전략이다. (예제 1) 위 그림은 앞서 이야기했던 게임 규칙을 적용해 (221)개의 돌이 있을 때, 트리를 그린 것이다. 이것을 보면서 (221)개의 돌이 있을 때 게임의 승리 전략을 알아보자. 트리에서 네모(나), 동그라미(상대방)를 의미한다. 마지막 노드가 내 차례라면, 돌이 1.. 2020. 5. 14.
[이산수학] 최소 신장트리와 프림/크루스칼 알고리즘 트리는 그래프의 유형이다. 1. 무방향 2. 모든 정점 연결 3. 비순환 루트 트리(Rooted Tree, top) : 지정된 한 개의 정점을 갖는다. 뿌리 보다는 top이라고 생각하자. (->정상에 있는 정점) 루트 트리와 관련된 용어 // 정점 - 부모 정점 : 바로 위 정점 - 조상 정점 : 위에 있는 정점 모두 - 자식 정점 : 바로 아래 정점 - 후손 정점 : 아래 있는 정점 모두 - 형제 정점 : 같은 부모 - 단말 정점 또는 잎 : 터미널 vertices, 마지막 노드 - 비단말 또는 내부 정점 : 단말 정점을 제외한 것 - 부 트리 ** 만약 단말 정점인데 부트리를 구하라? >> 본인 자신 정점뿐 m-가지 루트 트리 : 자식이 최대 m개(m=2이면 이진트리) 포화 m-가지 트리에는 각각 m.. 2020. 5. 6.
[이산수학] 방향그래프, 그래프 탐색과 구현 11. 방향그래프 12. 강한연결요소 13. 비순환그래프 14. 그래프탐색 15. 그래프구현 --------------------------------------------------------------------------------- ⑪ 방향그래프 : 간선의 끝에 방향을 추가 G = (V, E) V : 노드(nodes)라고 부른다. E : 아크(arcs)라고 부른다. //★관계를 순서쌍으로 표현한다.★ 예제) G = (V,E) V = {1,2,3,4} E = { (1,2), (2,1), (2,5), (3,1), (3,4), (4,2), (5,4), (5,5) } 차수 : 정점에 연결된 간선의 수 //사람으로 따지면 인기인 고립된 사람으로 취급함 deg = indeg+outdeg - indeg(v) .. 2020. 5. 6.
[이산수학] 외판원문제(TSP문제)와 그래프 동형 6. TSP 문제 7. 매칭 8. 그래프동형 9. 평면그래프 10. 그래프색칠 ----------------------------------------------------------------------------------------- ⑥ TSP(Traveling Salesman Problem) : 외판원 방문 문제 : 모든 도시를 한 번만 방문하고, 출발점으로 다시 돌아오는 최단 경로 >> 최소비용의 헤밀턴 사이클 찾기 ★TSP의 어려움★ : 도시 수가 많을수록 최적의 해를 계산하는 데에 엄청난 시간이 소요된다. 해밀턴 순환의 총 수 = (n-1)! / 2 "팩토리얼 증가" 해결 방안 타협 >> 품질 vs 비용 Naive algorithm vs Greedy algorithm (숲전체) (나무) Be.. 2020. 5. 6.

티스토리툴바