|
'''
이론 컴퓨터 과학 {{{#!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. 개요
디지털 물리학 (영어 : digital physics)은 " 우주는 본질적으로 정보에 의해 설명가능하며, 따라서 계산 가능하다."라는 가정에 의해 만들어진 물리학 및 우주론에서 이론적 조망의 총칭이다. 이러한 가정을 세울 때, 우주는 컴퓨터 프로그램의 출력된 계산, 혹은 일종의 거대한 디지털 컴퓨터 장치로 이해된다.디지털 물리학은 다음 하나 이상의 가설을 기초로 하고 있다. 또한, 기재된 순서는 그 주장의 강도를 나타낸다.
- 우주 (혹은 현실)은 본질적으로 정보이다. (그러나 각 정보의 온톨로지 가 디지털일 필요는 없다).
- 우주 (혹은 현실)은 본질적으로 계산 가능하다.
- 우주 (혹은 현실)은 디지털로 기술 가능하다.
- 우주 (혹은 현실)은 본질에 있어서 디지털 이다.
- 우주 (혹은 현실)은 그 자체가 화려한 컴퓨터 (계산기)이다.
- 우주 (혹은 현실)은 모의 현실 시뮬레이션의 결과이다.
2. 역사
모든 컴퓨터는 정보 이론 , 통계 (열) 역학 및 양자 역학의 원리와 분명한 일관성을 이해해야한다. 이 분야의 기본적인 관계는 1957년에 Edwin Jaynes 에 의해 2개의 논문으로 제기되었다. 또한 Jaynes는 확률 이론을 "일반화 된 아리스토텔레스의 논리학"으로 재해석했다. 이 관점은 고전 논리와 해당하는 불 대수(Boolean algebra)의 논리 연산을 구현하도록 설계된 디지털 컴퓨터와 기초 물리학을 연결하는데 이론적으로 쓸만하다.우주가 디지털 컴퓨터라는 가설은 독일의 과학자 콘라트 추제가 그의 저서 <Rechnender Raum>[1]에서 처음 제기했다. 디지털 물리학이라는 용어는 Edward Fredkin이 처음으로 사용했지만, 그는 나중에 디지털 철학(Digital philosophy)라는 용어 쪽을 선호하게 되었다.
우주가 거대한 컴퓨터라고 주장한 유명 인물은 스티븐 울프럼, Juergen Schmidhuber, 1999년 노벨물리학상 수상자인 헤라르뒤스 엇호프트 등이 있다. 이 사람들은 양자 역학의 확률적 성질과 계산 가능성은 반드시 비일관성이 없다고 생각하고 있다. 양자 버전의 디지털 물리학은 최근 세스로이드, 데이비드 도이치, Paola Zizzi에 의해 제안되고있다.
관련된 것으로서 칼 프리드리히 폰 바이 체커 의 binary theory of ur-alternatives, 범 계산주의, 계산적인 우주론(computational universe theory), 존 휠러의 "It from bit", 맥스 테그마크의 수학적 우주 가설(궁극적 집합)이있다.
3. 관련 항목
3.1. 관련 개념, 가설, 이론
- A New Kind of Science ( 스티븐 울프 럼 의한 저작)
- 세포 자동자
- 처치 - 튜링 명제
- 하이퍼 컴퓨터
- 양자 컴퓨터
- 계산 가능성 원리
- 모의실험 가설
- 홀로그래피 원리
- 콘라트 주세
- 수학적 우주 가설
4. 관련 물리학자
- 스티븐 울프럼
- 맥스 테그마크
- 헤라르뒤스 엇호프트
- 에드워드 프레드킨
- 세스 로이드