이산수학

• Boolean Algebra, Logic, Set Theory
  • 논리 ^logic
  • 부울 대수 ^{boolean algebra}
    • 드모르간 법칙
  • 카르노 맵 ^{Karnaugh map}
• 순열, 조합
• 재귀
• 그래프
  • 최단 경로
  • Minimum Spanning Tree
  • Binary Tree
• 귀납, 연역
  • 수학적 귀납법 ^{mathematical induction}
• 오토마타
  • 튜링 머신
  • 촘스키 계층 ^{Chomsky Hierarchy}
  • SR 플립플롭

Boolean Algebra, Logic, Set Theory

부울 대수, 논리, 집합론은 서로 불가분의 관계에 있다.

논리 ^logic

명제 ^proposition, 공리 ^axiom, 조건 명제 ^implication(~라면)

부울 대수 ^{boolean algebra}

논리 연산으로도 불린다. 아래와 같은 특이한 분배법칙에 주의 한다. \(A+(B\cdot{C}) = (A+B)\cdot(A+C)\)

드모르간 법칙

\((A\cdot{B})^\prime=A^\prime+B^\prime\)
\((A+B)^\prime=A^\prime\cdot{B}^\prime\)
식을 깔끔하게 정리할 때 가장 많이 사용됨

쌍대성 ^duality: 두 개의 다른 변수가 같은 수학적 관계(등식,방정식,수식,공식,함수 등)를 취함

카르노 맵 ^{Karnaugh map}

불 대수 위의 함수를 단순화 하는 방법으로 모리스 카르노가 1953년에 소개. 변수가 3개 이상일때 진리표^{truth table}을 이용한 최소항 전개^minterm로 직접 계산하는 것에 비해 이미 단순화된 형태로 매우 빠르고 쉽게 계산할 수 있다. 관련 분야: 논리 회로 설계 ^{Logic gates design}, 이산수학

• 00, 01, 11, 10 순으로 기입한다.
• 맨 오른쪽은 맨 왼쪽과 연결된다.
• 1, 2, 4개 단위로 묶는다.
• 변하지 않는 값을 취한다. (위키피디어)

도넛 형태로 연결되어 있음에 주의. 만약 연결된 상태로 계산하지 않으면 추가로 단순화 과정을 거쳐야 한다.

순열, 조합

• Permutations, Combinations

재귀

하노이의 탑: \(H(n)=H(n-1)+1+H(n-1)\)

(프로그래머, 수학으로 생각하라, 2018)

그래프

ordered pair \(G = (V, E)\)

• 동형 ^isomorphic: vertices 동일, edges 동일, degrees counts 동일 (SO)
  

• Eulerian Path, Hamiltonian Path 『파이썬 알고리즘 인터뷰』 참고

최단 경로

다익스트라 ^Dijkstra 알고리즘은 벨먼-포드 ^Bellman-Ford 알고리즘과 동일한 작업을 수행하고 실행속도도 더 빠르다. 하지만 다익스트라 알고리즘은 가중치가 음수인 경우는 처리할 수 없다.

다익스트라는 처음에는 \(O(V^2)\) 시간 복잡도를 가졌으나 Min Heap으로 \(O((V+E)logV)\)가 가능하다. 모든 노드(정점) \(O(V)\)에 대해 힙에서 최소값 추출 \(O(logV)\), 각 정점마다 이웃한 정점의 최단 거리 갱신 \(O(ElogV)\). 플로이드-와샬 알고리즘은 가능한 모든 노드쌍들에 대한 최단거리를 구한다. 다익스트라를 확장시킨 알고리즘이 A* 알고리즘이다. (나무위키)

Minimum Spanning Tree

모든 vertex를 지나는 엣지 가중치의 합이 최소인 신장트리
A planar ^평면 graph and its minimum spanning tree. (Wikipedia)

• Prim’s algorithm
  solution set과 non-solution set 사이를 연결하는 가중치가 가장 작은 edge를 뽑아 해당 vertex를 solution set에 넣어가며 완성. greedy algorithm으로 Priority Queue → Heap으로 구현
  (위키피디어)

• Kruskal’s algorithm
  분석 대상 노드에 연결된 edge를 가중치가 가장 작은 순부터 나열하여 트리 속성이 깨지지 않는지 여부를 체크하며 완성(cyclic 하면 배제)

Binary Tree

• 포화 이진 트리 ^{Full Binary Tree} is a tree in which every node has either 0 or 2 children.
  
• 완전 이진 트리 ^{Complete Binary Tree} every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. (e.g. Binary Heap)
  

귀납, 연역

• 귀납^induction: you start with your own experience and then generalize a rule. 경험으로 규칙을 일반화한다. 실험 과학자 마이클 패러데이. 대표적인 귀납주의자 프랜시스 베이컨.
• 연역^deduction: you start with a rule and then apply it to new situations. 규칙으로 상황에 적용한다.
• 귀류법 ^{proof by contradiction}: 모순에 의한 증명

수학적 귀납법 ^{mathematical induction}

모든 자연수가 어떤 주어진 성질을 만족시킨다는 명제를 증명하는 방법의 하나이다. 가장 작은 자연수(문맥에 따라 0일 수도 1일 수도 있다)가 그 성질을 만족시킴을 증명한 뒤, 만약 어떤 자연수가 만족시키면 바로 다음 자연수 역시 만족시킴을 증명하기만 하면, 모든 자연수에 대한 증명이 끝난다. (위키피디어)

1부터 1000까지의 자연수가 적힌 1000개의 블록을 갖고 도미노를 만든다고 생각해보자. 아래와 같인 원칙에 따라 도미노를 세운다.

1. 블록을 세우는 순서는 블록에 적힌 수의 순서를 따른다.
2. 어떤 블록이 넘어지면 바로 다음에 있는 블록이 꼭 넘어가도록 블록을 세운다.

이와 같은 원칙을 바탕으로 도미노를 세운 후 1000개의 블록을 모두 넘어뜨리기 위해서 해야 할 일은 제일 처음에 위치한 1이 적힌 블록을 건드려 넘어뜨리는 일 하나이다. (수학의 바이블 수학 I)

오토마타

자동장치, 자동기계의 의미로, 기계 내부의 구성이나 동작에 대한 세부 사항을 배제하고, 입력과 출력에 대한 사항만 명시되는 추상적인 기계로 FSM을 위한 수학적 모델이다.
논문

게임 AI에 FSM 대신 Hierarchical FSM, 나아가 Behavior Trees로 simple and scalable solution for editing logic 하는 트렌드인듯.

Decision Trees와 달리 Behavior Trees는 동작 상태에 대한 액션이 설정되어 있어 훨씬 복잡하다. 게다가 If any condition fails, the traversal returns to the parent 한다.

(GameDev SO)

결국 flowchart가 FSM이 아닌가 하는 생각을 한적이 있는데, A flowchart is not a state machine(PDF)

마찬가지로 Markov Chain vs FSM: Markov chains can be represented by finite state machines. The transitions in a Markov chain are probabilistic rather than deterministic(rather than FSMs).

튜링 머신

공리: 증명이 필요 없는 자명한 진리

촘스키 계층 ^{Chomsky Hierarchy}

(AI Study)

SR 플립플롭

논리 회로 책에 나와야 할 내용이 아닌가 싶은데, Johnsonbaugh의 이산수학 책에 나온다.

(이산수학 7판, 2008)

오토마타 챕터에서 이전 상태의 ‘기억’을 유한 상태 기계로 표현.

Last Modified: 2021/06/08 13:03:45