분류 전체보기377 [이산수학] 정규언어, 정규표현 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. [알고리즘] Dynamic 프로그래밍과 예제들 우리가 여태 배워온 것들은 아래와 같다. - D&C 기법 - Backtracking 기법 : 어떤 결정의 연속을 통해 문제의 답을 점차적으로 만들어가는 것. Recursion을 돌린다. -> 문제에 대한 일반화가 필요함. // 이번시간에 배울 것 - Recursion은 항상 옳은가? - 쓸데 없이 많은 Recursive call을 줄여보자. - 점화식을 이용한 효율적 구현 >> Dynamic program (동적 계획법) Dynamic Programming을 사용한 알고리즘 - Fibonacci number 계산 - Longest Increasing Subsequence(LIS) - Subset Sum ---------------------------------------------------------.. 2020. 5. 13. [알고리즘] D&C 기법의 예시와 좋은 pivot이란? (지난주) D&C기법? 같은 문제의 더 작은 instance로 recursion 하는 방법. D&C 알고리즘의 시간 복잡도 분석 1. 점화식을 찾아라 ( 재귀하는 부분 & 나머지 부분 ) -> T(n) = r*T(n/c)+O(f(n)) 형태 2. 점화식을 풀어라 ( Recursion tree , Master Theorem 등) Mater Theorem : 점화식이 T(n) = r*T(n/c) + O(f(n)) 형태를 만족할 때만 적용 가능, f(n)과 n^(log c r)을 비교 - f(n) = Ω(n^(logc r+ε) >> T(n) = O(f(n)) - f(n) = Θ(n^(log c r) >> T(n) = O(f(n) * log n) - f(n) = O(n^(log c r-ε) >> T(n) = O.. 2020. 5. 11. [알고리즘] D&C 기법, Recursion tree와 Master Theorem //저번 시간 Recursion : simple and delegate! 자기 자신으로 reduce 하는 전략 Reduction >> 다른 문제의 알고리즘을 활용한다. Recursive algorithms : Correctness : induction으로 증명한다. Time Complexity Analysis : 점화식을 구한다. ---------------------------------------------------------------------------- //이번 시간 1. Divide and Conquer //패턴(결국엔 recursion) 알고리즘 설계, 문제 해결 기법 n이 주어지면 -1씩 줄어드는 것이 아닌 더 덩어리가 크게 나누어진다. 2. D&C (divide and conquer).. 2020. 5. 8. 이전 1 ··· 53 54 55 56 57 58 59 ··· 63 다음
