이 문서는 토막글입니다.토막글 규정을 유의하시기 바랍니다. '''이론 컴퓨터 과학
{{{#fff
Theoretical Computer Science
'''
|
- [ 펼치기 · 접기 ]
이론
| 기본 대상
| 수학기초론(수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론) · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학] · 선형대수학
| 다루는 대상과 주요 토픽
| 계산 가능성 이론
| 재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버
| 오토마타 이론
| FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임
| 계산 복잡도 이론
| 점근 표기법 · 튜링 기계^고전, PRAM, 양자, 비결정론적^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법)
| 수학적 최적화
| 조합 최적화
| 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
| 볼록 최적화
| 내부점 방법 · 경사하강법
| 선형계획법
| 심플렉스법
| 정보이론
| 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
| 컴퓨팅 방법론
| 병렬 컴퓨팅(병렬 아키텍처 · 암달의 법칙 · 병렬 알고리즘) · 분산 컴퓨팅(분산 알고리즘 · 클러스터 컴퓨팅 · 그리드 컴퓨팅 · 클라우드 컴퓨팅) · 멀티코어 컴퓨팅 · 대칭형 다중 처리(SMP)
| 암호학
| 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호
| 대칭키 암호화 방식
| 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
| 공개키 암호화 방식
| 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
| 프로그래밍 언어이론
| 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 컴파일러 이론
| 주요 알고리즘 및 자료구조
| 기초
| 정렬 알고리즘 · 순서도 · 탐색 알고리즘
| 추상적 자료형 및 구현
| 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^
| 계산 수론 및 암호학
| 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘
| 계산기하학
| 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN
| 그래프 이론
| 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
| 정리
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학
|
|
오토마타 이론에서 다루는 유의미한 형태의 오토마타로, 일반적으로 Input Line과 Automata와 Stack Memory 공간이 있는 Automata를 말한다.
Chomsky Hierarchy에서 Type-2 에 해당하는 Context-Free 문법을 recognize 가능한 Automata다.
인간의 언어가 기본적으로 문맥자유언어(Context-Free Language)라고 가정하기 때문에
NLP 분야에서 많이 쓰인다. Charniak Parser 같은 대표적인 NLP 파서들이 문법자유언어 기반. 물론 현대의
NLP는 확률론을 기반으로 하기 때문에 문법자유언어에 확률을 끼얹은 Probabilistic Context-Free Grammar를 사용한다.
이 문서의 내용 중 전체 또는 일부는 2023-12-24 07:45:44에 나무위키
푸시다운 오토마타 문서에서 가져왔습니다.
이 문서의 내용 중 전체 또는 일부는 2023-12-24 07:45:44에 나무위키 푸시다운 오토마타 문서에서 가져왔습니다.