| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
형식 언어(形式言語, formal language)는 형식언어이론(形式言語理論,formal language theory)을 알파벳 및 특수기호를 포함하는 예약된 기호열 집합에 기반한 결합(추론 또는 연산)으로서의 형식 언어 문법에 관한 논리적 이론의 구현이라고 정의해 본다면 형식 언어를 정의하는 방법에는 구조와 범위가 무결성에 기반하여 명확하게 규정되고 정의된 인공 언어를 말한다. 자연 언어에서의 생성 문법 등과 컴퓨터 프로그래밍 언어의 오토마타(automata) 등이 있다.논리학, 언어학, 수학, 컴퓨터과학 등에서 주로 다룬다.
2. 언어 형식
인공 언어인 형식 언어에서 언어 형식은 자연 언어에서 문법에 해당하는 것으로 볼 수 있으며, 이를 통해서 형식 언어를 정의함으로써 구조와 범위가 무결성을 갖도록 설계할 수 있다.2.1. 퍼스트 오더 로직
퍼스트 오더 로직(1st order logic) 또는 1차 술어논리(first-order predicate logic)의 주요 원리중 하나이자 형식 언어에서의 드모르간 법칙의 예논리학 : [math( \neg (\text{부정}), \lor (\text{논리합}), \land (\text{논리곱}) )]
[math(\neg (p \lor q) = \neg p \land \neg q)]
[math(\neg (p \land q) = \neg p \lor \neg q)]
[math(\neg (p \lor q) = \neg p \land \neg q)]
[math(\neg (p \land q) = \neg p \lor \neg q)]
2.2. 기호논리학의 예
기호논리학(Symbolic Logic) 또는 1차 술어 논리(first-order predicate logic)에서의 추론 형식의 예| 추론 형식 | 논리식 | 예 |
| F1 | 삼단논법 | 가언([math(\to)], [math(\supset)]), 선언([math(\lor)]), 연언([math(\land)]), 정언 명제([math(\subset)]) 등 명제논리 |
| F2 | 드모르간의 법칙 | [math(\neg (p \lor q) = \neg p \land \neg q)] [math(\neg (p \land q) = \neg p \lor \neg q)] |
| F3 | 단순화 논리 | 이중부정([math(\neg\neg)]) ,논리곱 논법 등 |
| F4 | 양화사 논리 | 존재양화사 [math(\exist)] (existential quantifier) 보편양화사 [math(\forall)] (universal quantifier) |
| F5 | 등호 논리 | [math(g=m)] |
기호논리(Symbolic Logic)의 추론 예
| 자연언어 | 형식 언어 | 추론 형식 |
| 만일 비가 온다([math(\rm A)])면, 소풍을 가지([math(\rm B)]) 않는다. | [math(\rm A \to \neg B)] | F1 (가언 명제) |
| 소풍을 가지 않는다면, 우리는 학교에 가야([math(\rm C)])된다. | [math(\rm \neg B \to C)] | F1 (가언 명제) |
| 비가 오지 않는다([math(\rm \neg A)]), 그리고 우리는 학교에 가지([math(\rm \neg C)]) 않는다. | [math(\rm \neg A \land ¬C)] | F1 (연언 명제), F3(단순화 논리) |
| 비가 온다([math(\rm A)]) 또는 우리는 학교에 간다([math(\rm C)]) | [math(\rm \neg \left ( \neg A \lor \neg C \right ) = A \lor C)] | 이중부정(F3),드모르간의 법칙(F2), 등호 논리(F5) |
| 비가 오지 않는다([math(\rm \neg A)]) 우리는 소풍을 간다([math(\rm C)]) | [math(\rm A \subset C)] | 정언 명제 (F1, 결론) |