| '''이론 컴퓨터 과학 {{{#!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 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 ||수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · C/C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구
및
기타논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템 · Git · GitHub)
1. 개요
情報理論 / information theory정보 이론은 데이터의 통신, 처리, 추출, 응용을 연구하는 분야다.
2. 상세
1920년대 Harry Nyquist와 Ralph Hartley에 의해 처음 정립되었으며, 1940년대에 클로드 섀넌(Claude Shannon)이 더욱 구체화했다. 1948년 섀넌은 Bell Systems Technical Journal에 "A Mathematical Theory of Communication"이라는 논문을 제출하면서, 정보라는 것이 어떻게하면 절대적인 정확도로, 그리고 고유하게 정량화 될 수 있는지 보여주었다. 그에 따르면 본질적으로 모든 종류의 의사소통(Communication), 예컨대 신호, 텍스트, 라디오 신호, 그리고 사진까지 모두 비트(bits)로 변환될 수 있다. 이 논문은 디지털 시대의 청사진을 제공했다고 평가받고 있다.추상적으로 정보는 불확정성의 해상도(the resolution of uncertainty)라고 생각될 수 있다. 불확정성이 큰 것일수록 유의미한 정보가 담겨있고, 불확정성이 작으면 유의미한 정보가 적다고 이해할 수 있다. 노이즈가 있는 채널을 통한 정보교환의 경우에 이러한 정보의 추상적인 개념은 1948년 클로드 섀넌이 형식화했다. 이 경우 정보는 가능한 메세지의 집합으로 생각되며, 이때 정보이론의 목표는 이 메세지를 노이즈가 있는 채널을 통해 전달한뒤 메시지를 수신하는 측에서 오차확률을 최소화하는 방법을 연구하는 것이 된다.
섀넌의 주요한 연구결과중 하나인 '노이즈 채널 코딩 정리'는, 노이즈가 있는 어떠한 채널이든간에 각 채널에는 고유한 채널용량(channel capacity)이 존재해서 채널용량의 한계를 벗어나지 않는 비율(rate, 단위는 일반적으로 bits/s)에 한해서는 정보를 오차없이 얼마든지 보낼 수 있다는 것을 밝히고 있다. 이 채널용량을 정의한 것이 섀넌의 업적중에서도 가장 중요한 것중에 하나인데, 채널용량이 존재한다고 예언함으로써 정보이론에서 무엇을 연구해야 하며 무엇이 달성될 수 있는지 예언한 셈이다[1].
정보이론은 확률론, 통계학, 컴퓨터과학, 통계역학, 정보공학 그리고 전기전자공학의 교차점에 위치해있다. 정보이론의 하위분야로는 소스코딩, 알고리즘 복잡도 이론, 알고리즘 정보 이론 등이 있다.
3. 정보 엔트로피
정보이론에서 핵심 측정량은 정보 엔트로피이다. 엔트로피는 무작위 변수 혹은 무작위 과정의 결과에 포함되어있는 불확정성의 양을 정량화한다. 예를들어, 양쪽 면이 나올확률이 같은 동전은, 6개의 면이 나올확률이 같은 주사위보다 적은 정보량을 제공하며, 따라서 적은 엔트로피를 가진다. 엔트로피 이외에도 정보이론에서 중요시하는 측정량으로는 상호정보, 채널용량, 상대 엔트로피가 있다.
단, 열역학에서의 엔트로피와는 개념이 조금 다르다.
4. 응용
일상에서 흔히 사용하는 ZIP파일은 정보이론의 소스코딩/데이터 압축의 대표적인 응용중에 하나이며, DSL은 정보이론의 채널 코딩/오류 탐지 및 수정의 응용중 하나이다. 이러한 응용들은 보이저호 탐사, CD의 발명, 스마트폰과 현대 인터넷의 발전 등에도 큰 기여를 했다.언어학에서도 정보이론을 활용하는데, 소음이 많은 공간에서도 대화가 가능한 이유 등을 설명할 수 있다. 음향적 손실이 많은데도 대화가 가능한 것은 언어를 통한 의사소통이 정보량이 많은 음절/어절을 포착하는 과정이기 때문으로 설명될 수 있고, 화자와 청자 또한 이러한 사실에 민감하기 때문에 주변에 소음이 많을 때 엔트로피가 높은 단위를 말할 때 과잉조음하는 등의 전략을 취한다.
딥러닝에서 또한 정보이론을 손실함수를 정의할 때, 정보이론의 엔트로피를 많이 사용한다. Cross entropy나 KL-divergence등 데이터들의 분포의 차이를 식으로 표현하기 위해 많이 사용하는 편이다.
5. 관련 문서
[1] What made possible, what induced the development of coding as a theory, and the development of very complicated codes, was Shannon's Theorem: he told you that it could be done, so people tried to do it. (Interview with Fano, R. 2001)