이산수학

Boolean Algebra, Logic, Set Theory

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

논리 logic

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

부울 대수 boolean algebra

논리 연산으로도 불린다. 아래와 같은 특이한 분배법칙에 주의 한다.

드모르간 법칙



식을 깔끔하게 정리할 때 가장 많이 사용됨

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

카르노 맵 Karnaugh map

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

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


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

순열, 조합

  • 순열Permutations
    n * (n - 1) * .. * (n - k)로 나타낼 수 있다.
  • 조합Combinations
    k = 3이라면 {123,132,213,231,312,321}은 모두 123 하나로 간주할 수 있으므로 순열에 즉, 를 나눈 것과 같다.

재귀

하노이의 탑:

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

그래프

ordered pair

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

Eulerian Path

한붓 그리기, 오일러 트레일 Eulerian trail 또는 오일러 패스 Eulerian path는 “Every vertex of this graph has an even degree.” 모든 정점들이 짝수의 차수를 가져야 한다. 1736년 쾨니히스베르크의 다리 문제를 풀기 위해 도입, 그래프 이론의 시초 (위키피디어)

Hamiltonian Path

Hamiltonian path 해밀턴 경로는 모든 vertex를 한 번씩 지나는 경로로 외판원(TSP) 문제는 대표적인 NP-Hard 문제다. 팩토리얼로 풀어야 하며 최적화 알고리즘이 없다. ref

최단 경로

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

다익스트라는 처음에는 시간 복잡도를 가졌으나 Min Heap으로 가 가능하다. 모든 노드(정점) 에 대해 힙에서 최소값 추출 , 각 정점마다 이웃한 정점의 최단 거리 갱신 . 플로이드-와샬 알고리즘은 가능한 모든 노드쌍들에 대한 최단거리를 구한다. 다익스트라를 확장시킨 알고리즘이 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) 글에서 그렇지 않음을 예제를 통해 잘 설명한다.

튜링 머신

입력 공리 Axiom
프로그램 추론규칙 Inference Rule
출력 정리 Theorem

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

촘스키 계층 Chomsky Hierarchy

(AI Study)

SR 플립플롭

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

(이산수학 7판, 2008)

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


2017 Book Reports · 2018 Book Reports · 2019 Book Reports · AWS · Activation, Cost Functions · CNN, RNN · C++ · Decision Tree · Docker · Go · HTML, CSS, JavaScript · Hadoop, Spark · Information Retrieval · Java · Jupyter Notebooks · Keras · LeetCode · LifeHacks · MySQL · NLP 가이드 · NLP 실험 · NLP · Naive Bayes · OAuth 2.0 · OOP · Project Management · Python Data Structure Cheatsheet · Python · RSA · Software Deployment · Support Vector Machine · TensorRT · Word Embedding · XGBoost · Scikit Learn · 거리 · 데이터 마이닝 · 데이터 사이언스 · 딥러닝 · 머신러닝 분류기 · 머신러닝 · 미래학 · 비지니스 · 사회심리학 · 수학 · 알고리즘 · 영어 · 운영체제 · 이산수학 · 인공지능 · 자료구조 · 진화생물학 · 컴파일러 · 컴퓨터시스템구조 · 통계학 응용 · 통계학 ·
is a collection of Papers I have written.
© 2000 - Sang-Kil Park Except where otherwise noted, content on this site is licensed under a CC BY-NC 4.0.
This site design was brought from Distill.