| '''이론 컴퓨터 과학 {{{#!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. 개요
Von Neumann architecture존 폰 노이만이 제시한 컴퓨터 구조. 프로그램 내장 방식이라고도 불리며, 이론상 튜링 머신과 같은 일을 할 수 있다.[1]
폰 노이만 구조가 등장하기 이전의 극초창기 전자식 컴퓨터는 스위치를 설치하고 전선을 연결하여 데이터를 전송하고 신호를 처리하는 식으로 프로그래밍을 하였다. 그러나 이러한 프로그래밍 방식은 매우 번거로웠다. 컴퓨터에 무언가 다른 일을 시키기 위해서는 문자 그대로 수많은 스위치를 조작하고 전선을 다른 위치로 옮겨 꽂는 복잡한 노가다를 반복해야만 했다. 따라서 시간도 매우 많이 걸릴 뿐더러 작업 과정에서 실수하기도 쉬웠다.
폰 노이만 구조의 디지털 컴퓨터에서는 "저장된 프로그램"(stored-program)의 개념이 도입되었다. 이는 프로그램을 구성하는 명령어들을 임의 접근이 가능한 메모리상에 실행 순서대로 배열하고, 동시에 조건 분기[2]를 무제한으로 허용[3]한다는 것을 뜻한다. 폰 노이만 구조에서는 실행 코드와 데이터가 따로 구분되어 있지 않고, 모두 같은 메모리 속에 혼재되어 있다. 실행 코드와 데이터를 분리하는 건 파일 시스템, 다시 말해 운영체제의 몫이다.[4]
폰 노이만 구조는 중앙처리장치(CPU), 메모리, 프로그램 이 세 가지 구성요소로 이루어져 있다.
2. 역사
1944년, 모클리(Mauchly)와 에커트(Eckert)는 최초의 범용 전자 컴퓨터 에니악(ENIAC)을 개발하면서 "스위치 설치와 전선 연결" 방식[5]의 커다란 단점을 깨달았다. 그래서 이들은 EDVAC을 설계하면서 프로그램을 기억장치에 저장하고 명령을 불러오는 방법을 연구했고 이를 메모로 남겼다. 폰 노이만은 에니악 제작에 뛰어들면서 에드박 이야기를 듣고 <에드박에 관한 보고서 초안>을 작성한다. 그리고 폰 노이만에게 에니악을 소개시켜줬던 골드스타인 장교가 이 글을 배포해 버렸다. 문제는 그 보고서에 폰 노이만 자신의 이름밖에 없었다는 것.그 이후 모클리와 에커트는 EMCC라는 회사를 세우고 UNIVAC을 팔아 성공하지만, 돈이 바닥나자 회사와 에니악 특허 사용권을 레밍턴랜드에 팔고, 그 보고서에 있던 에니악의 설계 때문에 에니악의 특허도 무효가 되어 버렸다. 물론 폰 노이만은 "폰 노이만 구조"의 제창자로서 이름을 날렸다. 모클리와 에커트는 폰 노이만 구조의 실제 창시자가 본인들인 것을 알 수 있게 공개 해명해달라고 여러 차례 폰 노이만에게 요구했으나 묵살당했다.[6][7] 이러한 이유로 "폰 노이만 구조"가 아니라 "에커트 구조"라고 불러야 한다는 사람들도 있다.
이후 폰노이만의 보고서를 통해 또 다른 내장 프로그램 방식 애드삭도 만들어졌다. 많은 대중들이 폰노이만 본인이 애드박 또는 애드삭을 만들었다고 잘못 알려져있는데, 이는 사실이 아니다. 애드박은 프레스퍼 에커트, 존 모클리가 만들었고 애드삭은 모리스 윌크스가 만들었다. 폰노이만은 에니악 프로젝트 막단에 자문위원으로 참여한 인물로, 에니악의 후속버전인 애드박 개발과정에서 작성한 보고서를 통해 폰노이만 구조가 세상에 처음 소개된 것으로 알려진다. #
이 엄청난 편의성 때문에 현재 거의 모든 컴퓨터들은 폰노이만 구조를 따르고 있다. 폰노이만 구조를 따르지 않는 대표적인 경우는 클라우드 컴퓨팅 같이 네트워크가 필수인 경우인데, 이마저도 개별 노드(컴퓨터)는 여전히 폰노이만 구조를 따르고 있다. FPGA, ASIC 역시 폰노이만 구조는 아니지만, 어차피 이들에는 소프트웨어로 볼만한 것이 없기에 중요하게 고려하지 않아도 된다.
3. 장점
컴퓨터에 다른 작업을 시키려고 할 때 굳이 하드웨어(전선)를 재배치할 필요 없이 소프트웨어(프로그램)만 교체하면 되기 때문에 범용성이 크게 향상된다는 것이다. 전선을 일일이 교체하면 교체인원도 많이 필요하고 시간도 많이 잡아먹는 등 여러모로 불편함이 있지만[8], 폰노이만 구조를 도입하면 프로그램을 교체하는 것으로 모든 일이 끝난다. 소프트웨어의 복제도 용이하기에, 다른 하드웨어라도 일단 호환성만 보장된다면 같은 작업을 수행하게 하는 것도 가능하다.4. 단점
폰노이만 병목현상이 있다. 우선 메모리의 값을 읽고 쓰는 구조이기 때문에 기억장치에 병목현상이 생길 수밖에 없다. 메모리 계층 구조[9]나 NUMA, DMA같은 것들이 모두 이러한 문제를 조금이나마 완화하기 위해 도입된 기술들이다. 또한 코드를 순차로 실행하기 때문에 정해진 입력에 따라 정해진 값만을 출력하는 멍청한 구조, 즉 '결정적 유한 오토마타'의 한계에 묶이기 쉽다. GIGO가 나온 이유도 그렇고. 같은 이유로 난수생성도 우리가 원하는 진짜 난수를 생성하려면 특수한 하드웨어 없이는 불가능. 이건 SIMD 구조도 마찬가지라, CUDA 같은 병렬 처리 아키텍처도 예외는 아니다.인공지능의 부각으로 폰노이만 구조는 컴퓨터공학과는 동떨어진 영역에도 문제가 되고 있다. 바로 미러 테스트를 수행하기 어렵다는 점. 물질(육체)과 비물질(정신)의 분리가 어려운 동물과는 달리 인공지능은 물질(하드웨어)과 비물질(소프트웨어)의 분리가 용이하기에, 미러 테스트에 전적으로 필요한 '같은 개체의 다른 상'을 인공지능에는 만들 수 없다. 테스트를 위해 AI를 복제해봤자 '같은 개체의 다른 상'이 아닌 '별개의 개체'로 작동할 뿐. 이는 인공 의식과 관련하여 '인공지능의 자아'를 관찰하기 어렵다는 근본적인 문제로 이어진다.
4.1. 해결책과 한계
폰노이만 병목현상을 해결하기 위해 약간의 변형을 가하여, 메모리를 명령어가 저장되는 곳과 데이터를 저장하는 곳으로 구분한 하버드 아키텍처가 있다. 현대의 컴퓨터는 외부는 폰노이만 구조를 쓰고 있으나 CPU 내부는 하버드 아키텍처를 적용[10]해서 속도를 향상시킨 것이 많다. 그러나 이것 또한 폰노이만 구조를 기반으로 만들어진 것이기 때문에 병목현상만 어느 정도 해결할 뿐 메모리 속의 프로그램을 순차로 실행하는 근본 구조는 변하지 않는다. 난해한 프로그래밍 언어들 중 일부는 이러한 구조를 비판하기 위해 만들어지기도 하는데, 대표격으로 꼽히는 것이 'Java2K'이다.다른 시도도 있다. 뉴로모픽 컴퓨팅이라고 하여, 인간과 같은 고등동물의 뇌 구조를 모방한 인공신경망 형태의 집적회로를 만들어 기존의 컴퓨터 구조가 지닌 한계를 극복하려는 것이다. 뉴런은 하나하나가 작은 컴퓨터와도 같은데, 이를 모방하여 연산과 기억 기능이 통합된 유닛을 수없이 많이 준비하여 그물망처럼 병렬로 연결한 다음 각 유닛을 이벤트 구동(event-driven) 방식으로 작동시키는 것이다. 다만 이런 방식은 이전 결과에 종속적인 연산이 존재하면 아예 사용할 수 없는 등의 한계가 존재해[11], 2014년 IBM 등에서 선도하여 연구하는 정도에 그치고 있다. 2024년 현재도 상용화된 사례는 전무하고 체감 성능이 드러나는 것도 빨라야 2030년대에 이뤄질 것이라 전망되는 정도. 물론 이런 새로운 아키텍처가 폰노이만 구조의 종말을 뜻하는 건 아니고, GPGPU처럼 CPU의 특정 애플리케이션을 보조하는 식으로 쓰일 것이다.
[1] 이를 “튜링 완전하다”라고 한다.[2] 조건에 따라 메모리의 특정 위치에 있는 명령어를 불러와 실행하는 것.[3] 조건 분기가 무제한으로 허용되는 기계는 튜링 완전하다. 여기서 무제한이라는 말은 횟수 제한이 없다는 것이다.[4] 파일을 분리해 한 쪽을 실행 코드로, 다른 쪽을 데이터로 보면 쉽다.[5] 현대의 FPGA와 개념은 거의 동일하지만, 1940년대에는 논리회로를 사람이 손수 짜줘야 했다.[6] 이는 폰 노이만은 이 구조는 튜링 머신의 구현일 뿐이므로 이것의 진정한 창시자는 앨런 튜링이라고 생각했기 때문으로 보인다. 실제로 로스알라모스에서 폰 노이만의 동료였던 스탠 프랭클(Stan Frankel)에 따르면 폰 노이만은 스탠 프랭클 자신과 주변 사람들에게 이러한 근본 개념이 모두 앨런 튜링으로부터 나온 것이라고 강조했다고 한다. 그런 관점에서 본다면 폰 노이만 입장에서는 자기가 직접 창안한 아이디어도 아닌 것을 가지고 엉뚱한 사람들이 와서 자기네를 창시자라고 인정해 달라며 요구한 셈이니 그냥 무시했을 수도 있다.[7] 다만 에커트와 모클리는 1944년 EDVAC 설계 당시까지 앨런 튜링의 업적을 모르고 있었다고 한다. 하지만 그걸 감안한다 해도 그들을 이러한 구조의 최초 창시자로 인정하기에는 무리가 있다. 앨런 튜링의 튜링 머신 아이디어가 담긴 논문은 이미 1936년에 나왔으며, 또 1937년에 콘라드 추제(Konrad Zuse)가 제출한 특허 2건에 프로그램과 데이터를 동일한 기억장치에 저장하여 사용한다는 아이디어가 담겨 있었기 때문이다. 후대에 많은 영향을 미친 아이디어가 비슷한 시기에 여러 곳에서 독립적으로 나타나는 것은 역사에서 종종 찾아볼 수 있는 일이다.[8] 에니악이 이러한 구조를 가지고 있다.[9] 레지스터 > 캐시 메모리 > RAM > HDD/SSD(보조기억장치) 식의 계층구조[10] 예를 들면 인텔 코어 i 시리즈 CPU를 살펴보면 1세대~9세대 기준 각 코어의 L1 캐시 메모리는 명령어용 32KB, 데이터용 32KB로 나뉘어 있다.[11] 일반항을 쓰지 않고 정석대로 피보나치 수열을 구하는 것이 대표적인 연산 종속의 예로, n-1번째를 구하지 않고는 n번째를 구할 수 없다. 당연히 이런 연산은 병렬 컴퓨터에서 효율이 떨어질 수 밖에 없다.