1.
The 7 Most Influential Papers in Computer Science History이라는 글을 보았습니다. 컴퓨터과학을 전공하지 않았지만 컴퓨터기술과 관련한 일을 하는 입장에서 흥미로운 글이었습니다.
기술이 아니라 과학으로 바라보는 컴퓨터과학의 역사. 통사가 아니라 컴퓨터 과학의 역사에 흔적을 남긴 논문이라 좋았습니다. 마치 이종필 교수가 슨 물리학 클래식이라는 책이 떠올랐습니다. 누군가 이런 취지의 기획을 해서 책으로 내면 어떨가 하는 생각이 들었습니다. 이종필 교수처럼 논문 해제를 할 내공은 없고 훌륭한 분들이 정리한 글을 같이 소개합니다. 그러면서 저도 공부합니다.
2.
글중 첫번째 논문.
On Computable Numbers, with an Application to the Entscheidungsproblem (1936)
위 논문에 대한 설명입니다.
1930년대 중반의 Alan Turing과 다른 사람들로 하여금 튜링 명제(Turing thesis)라 불리는 유명한 추측(conjecture)를 만들어 내게 하였습니다. 이 가설은 기계적인 방법으로 수행될 수 있는 모든 계산은 어떤 튜링 기계에 의하여 실행될 수 있다는 것을 말합니다. 튜링 기계를 기계적인 계산에 대한 정의로 받아들이는 몇몇 논거는 다음과 같습니다.
– 모든 존재하는 컴퓨터에서 수행될 수 있는 모든 일은 또한 튜링 기계에 의하여 수행될 수 있다.
– 어느 누구도 아직 우리가 직관적 알고리즘이라 생각하는 것에 의하여 해결되지만, 튜링 기계 프로그램으로 해결될 수 없는 문제를 제시할 수 없었다.
– 기계적인 계산에 대해 여러 다른 모델들이 제안되었지만, 그들 중 어느 것도 튜링 기계보다 더 강력하지 않다.
어떤 의미에서, 튜링 명제는 물리하고가 화학의 기본 원칙들이 하는 것처럼 컴퓨터 과학에서 같은 역할을 합니다. 예를 들어, 고전저긴 물리학은 주로 Newton의 운동법칙들에 근거를 두고 있습니다. 그러한 법칙들을, 비록 무용지물이 될 수는 있지만, 참이라고 증명될 수 없습니다. 어떤 법칙을 무력화하는 것에 대한 반복된 실패는 그 법칙에 대한 우리의 확신을 강하게 합니다. 이것이 튜링 명제에 대한 입장입니다. 따라서 우리가 이 명제를 컴퓨터 과학의 기본 법칙으로 생각하는 이유가 됩니다.컴퓨터과학에서 Church-Truing thesis는 모든 효율적인 계산이나 알고리즘은 Turing machine에서 수행될 수 있다고 간단히 정의됩니다. 그것은 일반적으로 true인 것으로 가정되며 Church-Truing thesis, Church’s thesis, Church’s conjecture, Turing’s thesis라고도 알여져 있습니다.그 명제는 다시 말하면 논리와 수학에서 effective or mechanical method의 표기가 튜링기계(Turing Machine)로써 이루어질 수 있다는 것입니다. 그것은 대개 다음과 같은 요건을 만족해야 하는 것으로 가정됩니다.
1. 그 방법은 유한 갯수의 기호로서 묘사할 수 있는 간단하고 정밀한 명령어들의 유한 집합으로 구성된다.
2. 그 방법은 항상 유한 갯수의 step 내에 결과를 만들어낸다.
3. 그 방법은 주로 종이와 연필만으로도 인간에 의해 수행될 수 있다.
4. 그 방법의 수행시 명령어를 이해하고 실행하기 위해 필요한 것을 제외하고는 인간의 지능을 전혀 요구하지 않는다.
효율적인 방법이라는 표현은 직관적으로는 명확하지만 형식적으로는 정의되지는 않습니다. 왜냐하면 간단하고 정밀한 명령어란 무엇인가, 명령어를 수행하기 위해 요구되는 지능이란 것이 정확히 무엇인지가 명확하지가 않기 때문입니다.튜링은 1936년 On Computable Numbers, with an Application to the Entscheidungsproblem 라는 논문에서 튜링기계를 소개하면서 이 표현을 공식적으로 사용했습니다. 그 논문에서 결정문제는 풀 수 없다는 것을 보여줍니다. 이보다 몇달 앞서서 Church는 그의 논문을 통해서 유사한 결과를 증명는데, 그는 효율적인 계산가능성을 표현하기 위해 재귀함수(Recursive Function)와 람다 계산법(Lambda Calculus)이라는 표현을 사용했습니다. 람다 계산법은 Church와 Stephen Kleene가 처음 사용했고, recursive fucntions는 괴델과 Jacques Herbarnd가 처음 사용했습니다. 이 두가지 표현은 Church와 Kleene이 이용한 functions of positive integers의 경우에서 알 수 있듯이 같은 종류의 함수를 표현하는 것입니다. Church의 제안을 들었을때 튜링은 실제로 그의 튜링기계와 같은 종류의 함수들로 표현된다는 것을 즉시 알 수 있었습니다.
처치-튜링 명제(Church-Turing Thesis)중에서
글중 두번째 논문
A Mathematical Theory of Communication (1948)
클로드 섀넌(Claude Elwood Shannon, 1916년~2001년)은 1948년에 미국의 통신회사 벨 연구소 근무 시절에 통신의 수학적 이론(A Mathematical Theory of Communication)이라는 논문을 “벨시스템 기술 저널”이라는 사내 저널에 출판하게 되는데 이 이론이 일약 정보를 수학적으로 다루는 시초가 되는 논문으로 인정받게 된다.
그는 이때 앨런 튜링이나 폰 노이만 등과도 논의하면서 이 정보량을 엔트로피라는 이름을 붙이게 되었다(폰 노이만 제안)고 설명되어 있는데, 이를 둘러싼 자세한 이야기는 제임스 글릭의 책 인포메이션에 조금더 자세히 설명되어 있다. 이후 사람들이 이 이론에 대해 했던 열광에 비교해서는(결론의 함의하는 바가 매우 컸기 때문에), 사실 수학자였던 섀넌이 했던 고민은 단순했다. 그것은 통신회사가 어떤 정보를 전달할때 얼마의 과금을 해야하느냐에 대한 순수한 수학적인 정의다.
예를 들면 아래 두가지 정보 전송에 대한 과금은 어떻게 해야할까?
A: 00000………………………………………0 (1억개의 0)
B: 100100111010111…01011011 (random으로 나열된 1과 0의 조합 100개)
단순히 길이로 따지면 앞에 A가 더 길지만 가만히 보면 압축을 할 수가 있다. A는 0을 1억개 보내기보다는 0의 개수가 1억개라는 사실을 전달하면 불필요하게 많이 보낼 필요가 없다. 다만 B같은 경우는 완전한 random이라고 치면 압축을 할 수가 없이 그대로 보내야 한다. 결과적으로 압축을 잘하면 B가 정보량이 훨씬 많다. 돈을 더내야 한다. 그러면 얼마나 내야하는가?섀넌의 공식은 이에 대해 명확한 답을 준다. 바로 어떤 정보를 보낼때 필요한 비트수가 얼마냐로 귀결시킨다.(보내야할 정보의 카테고리와 각 카테고리의 출현 확률이 주어지는 경우를 가정한다)
정보량을 의미하는 섀넌의 엔트로피는 아래와 같이 나타난다. 어떤 많은 정보들이 각기 출현 확률이 P(x)일때 각 값들을 전송하는데 필요한 비트는 아래의 공식으로 나타내게 된다.
H(P)=H(x)=−∑P(x)logP(x) (log는 밑이 2)
사실 이 공식을 이해하기 위해서는 log와 확률 이야기를 해야하는데, 수학적인 전개가 익숙하지 않은 엔지니어 분들은 따라가기가 조금 까다롭다(Google 검색엔진 등 에 섀넌의 정보이론을 검색하면 몇가지 수학적 전개에 대한 문건들이 있긴 하다)
클로드 섀넌(Claude Shannon)의 정보 이론중에서
머신러닝과 정보이론: 작동원리의 이해에서는 섀넌의 이론이 머신러닝과 어떤 관계가 있는지를 아래와 같이 설명합니다.
보량을 수치화 할 수 있을까? 1948년 벨 연구소의 클로드 섀넌Claude Shannon은 “A mathematical theory of communication”이라는 제목의 논문을 발표한다. 지금은 “The mathematical theory”가 된 정보이론은 디지털 통신의 이론적 토대를 구축했고, 수학, 통계학, 물리학, 생물학, 그리고 머신러닝에도 큰 영향을 미치고 있다. 이론물리학자 존 훨러John Wheeler는 정보야말로 물질과 에너지보다 더 근본적인 우주의 실체라며, 유명한 문구 “it from bit”을 남긴 바 있다.
글중 세번째 논문.
A Relational Model of Data for Large Shared Data Banks (1970)
관계형 데이터베이스의 개념은 에드거 F. 커드(Edgar F. Codd) 사에 의해 1970년에 제안되었습니다. IBM의 연구원이었던 그는 “A Relational Model of Data for Large Shared Data Banks”라는 논문을 통해 관계형 데이터 모델을 소개하였습니다. 이 모델은 데이터베이스를 수학적인 집합 이론과 일치시키 는 혁신적인 접근 방식으로, 데이터의 구조와 처리를 간 하고 효율적으로 할 수 있게 해 주었습니다. 박사는 “계층형”과 “망형” 모델의 한계를 지적하며 관계형 데이터 모델의 요성을 주장 는데, 히 데이터의 비표준화된 접근방식과 유연성 부족에 비판을 했습니다.
1. 관계형 데이터 모델 (Relational Data Model)
관계형 데이터 모델은 데이터를 테이블(관계)의 형태로 표현하는 데이터베이스 모델입니다. 각 테이블은 “행(튜플)”과 “열(속성)”으로 구성되며, 이들은 현실 세계의 엔터티와 그 속성을 표현합니다. 관계형 모델은 데이터 간의 관계를 테이블 간의 “키(k )”를 통해 나타내며 이를 통해 복잡한 데이터 구조를 간단하고 이해하기 쉽게 관리할 수 있습니다.
주요 특징
1.데이터의 구조화 : 데이터를 테이블 형태로 관리하여 일관성 있고 직관적인 데이터 구조를 제공합니다.
2. 데이터 무결성 보장: 기본 키, 외래 키, 제약 조건 등을 통해 데이터의 정성과 일관성을 유지합니다.
3. 관계 표현: 테이블 간의 관계를 외래 키를 통해 명시적으로 표현하여 데이터의 연관성을 관리합니다.
4. SQL 사용: 표준화된 질의 언어인 SQL을 사용하여 데이터의 정의, 조작, 제어를 수행합니다.
5. 트랜잭션 관리: ACID 특성을 지원하여 데이터베이스의 신뢰성과 무결성을 보장합니다.
관계형 데이터 모델중에서
대형 공유 데이터 뱅크를 위한 데이터의 관계적 모델은 기계번역인 듯 하지만 논문 전체를 번역해서 소개하고 있습니다.
