문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 컴퓨터공학 (문단 편집) ==== [[이론 컴퓨터 과학]] / [[수학]] ==== [include(틀:이론 컴퓨터 과학)] [include(틀:수학기초론)] [include(틀:이산수학)] '''이론 컴퓨터 과학''' 또는 '''이론 전산학(영어: theoretical computer science)'''은 [[컴퓨터과학]] 및 [[수학]]의 한 분야로, 컴퓨터나 계산 과정의 추상적이고 근본적인 원리를 연구하는 학문이다. 컴퓨터과학의 이론적 토대는 수학에 기반을 두고있고, 하위 분류 중 가장 큰 줄기로 '''계산 이론(計算理論, Theory of computation)'''이 있으며 계산이론은 크게는 '''계산 복잡도(Computational complexity) 이론'''와 '''계산 가능성 이론(computability theory) 이론''' 2가지로 분류한다. 컴퓨터 관련 학문을 제대로 공부한다는 것은 수학적 논리를 공부한다는 것과 같은 말이다. 컴퓨터를 다루는 언어와 기법이 모두 수학이기 때문이다. 컴퓨터학과의 경우 색다른 커리큘럼의 수학을 배울 수 있다. 특히 다른 공학분야와는 다르게 공식을 암기하여 풀수있는 문제풀이를 익히는게 아니라 [[증명]]에 쓰이는 논리적 사고능력을 가르는것이 중요하다.[* 가끔 학교 수학 성적은 낮은데도 컴퓨터과학 지식과 프로그래밍 실력이 나쁘지 않은 사람이 존재하는데 실제로는 입시, 시험 같은곳에 필요한 공식, 문제풀이를 익히지 못한 거지, 응용과 추리 같은 것을 바탕으로 하는 사고력은 좋은 경우이다. 이런 사람의 경우 적성이 있기에 대학수학을 제대로 공부하면 잘 할 확률이 높다. ] 선형대수, 이산수학, 확률론, 통계학, 정수론, 미분기하학 쪽에 치중해서 배우게 되는데... ~~이쯤되면 그냥 [[수학과]] 아닌가???~~[* 괜히 수학과생들의 복수전공 1지망 분야가 컴퓨터겠는가? 보통은 수학과에서 컴퓨터 같이 공부하던 학생들이 컴퓨터를 공부하러 관련대학원으로 오는 식이지만, 가끔 역으로 컴퓨터전공 학생이 수학과 강의에 맛 들이고 이쪽 과목들을 듣다가 자기 이뻐하는 수학과 교수한테 영입당하는 경우도 있다. 서로의 분야에의 진입장벽이 다른 공학계열과의 진입장벽에 비해서도 그리 높지 않기 때문에 가능한 일.] 게다가 컴퓨터 과학의 경우 공부하는 분야에 따라서 필요한 수학도 천차만별이다. 또한 [[확률론]], [[통계학]], [[선형대수]]는 Computer Science 전반에 쓰인다 생각하면 좋다. '''분야를 막론하고''' 수학적인 기호들을 읽는데 능숙하지 못하거나, 수학적인 논리에 미숙하다거나 하면 전산학을 제대로 공부하기 '''매우 힘들다. 시스템 계열'''에서도 수학적 증명이 등장하는 마당에[* 운영체계의 피터슨 해법이나 램포트 빵집 알고리즘, 분산체계의 팍소스 알고리즘 등에 등장한다.], 웬만해서는 대학에서 강제 필수인 기초 이산수학, 알고리즘 디자인/분석 및 복잡도 이론 등으로 가면 더욱 그렇다. 특히나 컴퓨터 그래픽이나 온갖 [[기계학습]]류[* 컴퓨터 비전, [[자연 언어 처리]], [[데이터 마이닝]] 등 ] 분야로 가면 모든 분야의 전산학자들이 기본적으로 우려 먹는 이산수학 알고리즘들은 물론이고 공대생들이나 물리학도들이 흔히 써먹는 선형대수학이나 다중미적분, 미분기하학 등도 '''아주 많이 쓴다.''' 특히 기계학습의 경우, 보다 이론적인 쪽으로 가면 [[측도론]]을 쓰기 시작한다. 하다못해 [[프로그래밍 언어]]론을 공부하는 데에도 쓰인다. 프로그래밍 언어에 정의되어 있는 온갖 데이터 타입들에 대한 연산 규칙 및 증명 등을 해야할 때 필요하다. 학부 졸업 후 일반 기업에 취직을 하는 것이 아닌 석박사 학위 취득을 위한 대학원[* 슈도코드 수준이 아니라 논문의 절반이 수식으로 도배되어 있는 경우가 태반이다.]에 입학하여 세부 전공으로 '''이론 전산학'''을 선택할 경우 대학 [[미적분학]], [[미분방정식]], [[통계학]], [[확률론]], [[수치해석학]], [[선형대수학]], [[이산수학]], [[정수론]]은 기본실력으로 깔고 가야 고생이 덜하며 심지어 시뮬레이션 영역까지 접근할 경우 [[미분기하학]], [[동역학]], [[유체역학]]이 필요할 수도 있다. 대학원, 교수/학자/연구원 등의 레벨로 가면, 하다 못해 시스템 계열 분야라도 더욱 수학을 깊게 공부해 본 사람들이 많다. 특히 이름 있는 프로그래머, 전산학자들은 열이면 열 수학과나 수학을 많이 쓰는 전공 출신이다. 아래 예시에 특별히 적혀있지 않는 한 학사나 석사에만 이름을 올린 사람들은 최종적으로 전산학 박사학위를 취득했다. '''수학 혹은 응용수학''' * 박사: [[앨런 튜링]], [[존 폰 노이만]], 스티븐 쿡, 리처드 카프, 래즐리 램포트, 로버트 타르잔, 존 매카시, [[도널드 커누스]] * 석사: 켄 톰슨[* 최종학력], 마이클 I. 조던[* 최종학력 인지과학 박사] * 학사: [[데니스 리치]][* 물리학 학사 학위도 취득], 바바라 리스코프, 마테이 자하리아[* 전산학 복수전공], 데이비드 브럼리 '''물리학''' * 박사: [[에츠허르 다익스트라]], 앤드루 태넌범, 톰미 자아콜라 * 석사: 이홍락[* 전산학 석사학위도 취득] * 학사: 존 F. 캐니[* 전산학 복수전공; 전기공학 학사 학위를 나중에 따로 취득해서 학사 학위가 두 개다], 데니스 리치[* 응용수학 학사 학위도 취득] '''전기공학''' * 박사: 마틴 헬맨, 리 페이페이 * 학사: 존 F. 캐니[* 물리학/전산학 복수전공 및 전기공학으로 학사 학위 두개 취득], 지텐드라 말리크, 김태수 [* 전산학 학사 학위도 취득] * '''[[https://namu.wiki/w/%EC%9D%B4%EB%A1%A0%20%EC%BB%B4%ED%93%A8%ED%84%B0%20%EA%B3%BC%ED%95%99#s-2.1|계산 이론]]'''(Theory of computation) * 계산학습이론(Computational Learning Theory): [[기계학습]]과 [[https://namu.wiki/w/%EC%9D%B4%EB%A1%A0%20%EC%BB%B4%ED%93%A8%ED%84%B0%20%EA%B3%BC%ED%95%99#s-2.1|계산이론]]이 결합된 분야. * '''[[이산수학]]''' * '''[[자료구조]]론''' : [[컴퓨터과학]]에서 컴퓨터의 메모리와 CPU를 활용해 데이터를 구조적으로 처리하는 순서와 표현하는 방식을 다루는 이론으로 알고리즘의 분류에 포함된다. * '''[[알고리즘]]론''': 알고리즘의 [[시간 복잡도]]및 [[공간 복잡도]]를 주로 다룬다. 시간 복잡도의 경우 처리해야 하는 데이터가 많아질수록 필연적으로 알고리즘의 실행이 끝나는 속도가 느려지는데, 늘어나는 처리 데이터에 비례해서 얼마나 알고리즘의 '''실행 속도'''가 느려지느냐가 관건이다. 예를 들어, n 만큼의 데이터를 처리해야 할때 [math(> {\mathcal O}(n^{2}))] 복잡도를 가진다면, 처리해야 하는 데이터의 양에 제곱을 한 만큼 비례해서 알고리즘이 느려진다. 공간복잡도의 경우 처리해야하는 데이터에 비례해서 알고리즘이 얼마나 많은 양의 '''메모리'''를 필요로 하는가가 관건이다. * [[정보이론]]/부호이론: 정보이론은 정보의 양을 측정하고 최적화된 코드에 대한 기대 길이를 측정하는 것인데, 머신러닝에서는 확률분포를 알아내는데 쓰인다. 부호이론의 경우 유한체를 이용해 순환 코드(cyclic code)와 BCH코드를 다룬다. * [[정수론]]: 암호 분야에 사용 된다. * [[집합론]] * [[그래프(이산수학)|그래프 이론]] * [[조합론]] * [[확률론]] * [[수리논리학]]: 분야를 가리지 않고 등장하기 때문에 중요하다. 일부 학자들은 비표준 논리학, [[오토마타]], [[계산이론]], 증명 이론까지 다룬다. * [[오토마타 이론]]: 기초적인 automaton과 결정가능성, 그리고 [[튜링머신]]에 대해 배운다. * 유형론(type theory) * 도메인 이론(domain theory) * '''[[수치해석]]학''' * [[해석학(수학)|해석학]] * '''[[미적분학]]''' * [[미분방정식]]: 컴퓨터 그래픽스에서 물체의 움직임에서 사용하기도 하고, 계산 과학 분야에서도 사용한다. * [[함수]]와 [[측도론]]: 기계학습에 쓰인다. * '''[[확률론]]과 [[통계학]]''' * [[대수학]] * '''[[선형대수학]]''' * [[환(대수학)|환론]]: [[논리 연산]]이 대수 구조와 공리가 [[잘 정의됨|잘 정의]]되어 있는 환이므로, 환론을 어느 정도 공부해야 한다. * [[범주론]] * [[최적화 이론]] * [[암호학]] * [[네트워크 이론]] * [[기하학]] * 이산/계산 기하학 : 컴퓨터를 이용해서 물체를 어떻게 표현 할 할지 연구하는 분야이다. 컴퓨터 그래픽에서 대표적으로 많이 사용하고 최근에는 컴퓨터 비전, 기계학습, 인공지능 분야에서도 사용된다. * 이산 미분 기하학 * [[정보기하학 ]] * [[양자정보과학]], [[양자컴퓨터|양자컴퓨팅]][* 서울대학교 컴퓨터공학부 김태현 교수가 관련연구를 하고있다. 양자정보 및 양자컴퓨팅 연구실 [[https://quiqcl.snu.ac.kr/|홈페이지]] ] : 양자 컴퓨팅은 [[컴퓨터 과학]], [[물리학]], [[수학]]의 여러 측면으로 이루어진 종합적 분야로서 양자역학을 활용해 기존의 컴퓨터보다 빠르게 복잡한 문제를 해결할 수 있다. * 전산논리학(logic in computer science) : 전산논리학(logic in computer science)은 기호 논리학의 확장으로서 추론 과정을 컴퓨터의 계산 능력을 이용해 진행하는 것을 함께 다룬다. 컴퓨터를 이용한 추론 과정은 자연 언어로 표현된 명제에 대한 추론 과정과 궁극적으로는 차이가 없다. 그러나 자연 언어로는 현실적으로 불가능한 복잡한 추론 과정을 다룰 수 있고, 인간이 직접 다루기에는 너무 방대한 분량의 명제들도 한꺼번에 다룰 수 있다. * [[자동정리증명]] : 자동정리증명(自動定理證明, Automated theorem proving, ATP) 또는 자동 연역(Automated deduction)은 자동 추론 연구의 한 분야로, 수학적 정리들을 컴퓨터 프로그램을 통해 형식적으로 증명하는 것, 또는 그에 대한 연구를 가리킨다. 수학적 증명에 대한 자동화된 추론은 컴퓨터 과학 발전의 주요 원동력이었다. 위와 같이 수학 전반+α을 다루기 때문에 [[수학]] 전공자들의 복수전공에서 다른 공학 분야보다 용이하다. 실제로 이쪽은 교수부터 수학 전공자인 경우가 많다. 다만, [[한국]]에서는 거의 죽은 분야에 가깝다. 한국의 경우, 교육열이 입시에 쏠려있어, 고교수학에 매우 강하며 실제 대학에서도 이런 경향이 이어져 고교 때 배우는 미적분을 많이 다루는 [[해석학(수학)|해석학]]과 같은 분야쪽에 쏠리는 경향이 강하다. 비표준 논리학은 수학에서 해석학과 거리가 가장 먼 분야로 볼 수 있으며, 덕분에 한국에서 이쪽 전공 교수 자체가 별로 없다. 다만 [[철학과]]까지 범위를 넓혀보면 그나마 숫자가 좀 늘어나긴 한다. 즉 철학과에도 수리 논리학은 물론이고, 비표준 논리학도 건드려본 논리학 전공 교수들이 있다. 참고로 논리학은 원래 철학의 한 분야지만, 국내 수학과 내에 논리학 전공 교수가 많지 않듯이, 국내 철학과에서도 논리학 전공 교수가 많진 않다. 당연히 [[컴퓨터과학]]에서도 마찬가지. 국내는 이쪽 관련 인프라가 열악하므로 이쪽을 전공하고 싶다면 해외로 나가는 수밖에 없다. 하지만 최근 대학에서 이론 전산학을 연구하는 교수들이 조금씩 늘어가고 있다.[* 연세대학교의 한요섭, 안형찬 교수, 카이스트의 마틴 지글러, 정지원 교수 ,유니스트의 Vigneron Antoine 교수, 서울대학교의 박근수 교수 등이 있다.]저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기