계산 이론 개론 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
[[:Category:계산 이론 개론]]

==개요==
해당 문서에서는 기계적 계산(machine computation)에서 등장하는 추상적인 개념들을 소개한다. 이를 위해 다루는 주제는 유한 오토마타(finite automata), 정규 표현식(regular expressions), 형식 언어(formal languages) 등을 포함한다.

==[[Logic and Proofs]]==
수학적 명제(Assertion)의 구조에 익숙해지기 위해서는 명제 연결자(Propositional connectives)와 수량자(Quantifier) 등의 개념에 익숙해져야 한다. 또한 어떤 명제가 주어졌을 때, 이를 바탕으로 다른 명제를 증명하는 구조 역시 중요하다. 이러한 개념과 구조 등은 [[Logic and Proofs]] 문서에 자세히 설명된다.

==Mathematical Objects==
수학적인 명제혹은 주장들은 각종 수학적인 객체들에 대한 문장이나 진술로 해석될 수 있다. 따라서 수학적인 객체에 대한 이해는 매우 중요하며, 이에 따라 해당 문단에서는 각종 수학적 객체들에 대해 설명한다.
* [[Sets]]: 순서가 없는 객체들의 모임을 의미한다.
* [[Functions and Relations|Functions]]: 입력이 주어지면 이에 따라 출력을 내는 "블랙박스"로 이해할 수 있다.
* [[Functions and Relations|Relations]]: 어떤 객체 혹은 객체의 쌍에 대해 "참/거짓"을 판별하는 속성을 의미한다.
* [[Sets#Derived Constructions|Ordered Pairs and Tuples]]: 순서가 정해진 객체들의 모임을 의미한다.
* [[Natural Numbers]]: 0, 1, 2, 3, … 같은 기본적인 수 체계이다.

==[[Finite Automata]]와 [[Regular Languages]]==
[[Finite Automata|Finite Automaton]]<ref>단수형이 automaton, 복수형이 automata이다.</ref>은 유한한 메모리를 가진 단순한 계산 장치를 수학적으로 모델링한 것이며, FSM(Finite State Machine)의 가장 기본적인 형태이다. 이는 단순한 계산 장치이며, "유한 메모리"이기 때문에 무한한 기억이나 복잡한 연산이 불가능하고, 오직 현재 상태와 입력에 따라 동작만 결정된다는 특징이 있지만, 다양한 활용 분야를 가지고 있다.

자세한 내용은 [[Finite Automata]] 문서를 참조하십시오. 또한 finite automata를 이용하면, [[Regular Languages]]를 정의할 수 있다. Regular languages와 관련된 개념으로는 아래의 것들이 있다:
* [[Languages]]
* [[Regular Expressions]]
* [[Generalized NFA]]
* [[Grammars]]
* [[Nondeterministic Finite Automata]]
* [[Chomsky Normal Form]]
* [[CYK Algorithm]]
* [[Pushdown Automaton]]

==각주==