[컴퓨터과학의이해🧮] 계산 이론 (12장)

교재 : 컴퓨터 과학 총론 (13th Edition)

(책으로 공부하며 작성한 글입니다.)

 

1. 함수와 함수의 계산

- 수학에서 함수(function)는 가능한 입력 값의 집합과 출력 값의 집합 사이에서 하나의 가능한 입력에는 하나의 출력만이 배정되는 대응 관계를 말한다. 

- 주어진 입력에 대해 함수가 배정하는 출력을 결정하는 과정을 함수의 계산이라 부른다. 

- 수학에서 도출된 중요한 결론 중 하나는 어떤 함수들은 너무 복잡해서 이들의 경우 입력 값에 기초하여 출력을 결정하기 위해 사용할 수 있는 잘 정의된 단계 과정이 존재하지 않는다는 것이다. -> 계산 불가능한 함수

 

2. 튜링 기계 (Turing machine)

1) 튜링 기계의 원리

- 읽기/쓰기 헤드를 사용하여 테이프 상에 기호를 읽고 쓸 수 있는 제어장치로 이루어져 있다. 

- 튜링 기계의 계산이 이루어지는 동안 아무 때라도 기계는 유한한 개수의 조건(상태) 중 어느 하나에 있어야 한다. 

- 튜링 기계 계산은 초기 상태라 불리는 특별한 상태에서 시작하며, 정지 상태라 불리는 특별한 상태에 도달하면 멈춘다. 

- 튜링 기계의 계산은 기계의 제어장치에 의해 실행되는 일련의 단계들로 이루어진다. 

 

2) 처치-튜링 논제

- 튜링 기계로 계산될 수 있는 함수를 튜링 계산 가능(Turing computable)하다고 표현한다. 

- 튜링의 가설은 튜링 계산 가능한 함수들의 집합은 계산 가능한 함수들의 집합과 동일하다는 것이다.

- 위 가설은 처치-튜링 논제(Church-Turing thesis)로 지칭된다. 

- 오늘날 처치-튜링 논제는 인정되고 있다. 

- 계산 기계들의 능력과 한계에 대한 통찰을 제공한다. 

 

3. 보편적 프로그래밍 언어 (universal programming language)

1) 기본 골격 언어

- 기본 골격 언어를 개발함에 있어 목표는 최대한 단순한 언어를 개발하는 것이다.

- 규약을 사용함으로써 기본 골격 언어의 모든 변수는 동일한 타입을 갖게 된다. 

(서로 다른 타입 사이의 변환 연산이나 변수의 이름과 그에 연계된 속성을 기술하기 위한 별도의 선언문이 필요 없다.)

- 기본 골격 언어를 위한 번역기가 변수 이름을 다른 용어와 구별할 수 있도록 기본 골격 언어 구문이 설계되어 있다. 

 

2) 기본 골격 언어를 이용한 프로그래밍

- 기본 골격 언어를 제시하는 목표는 무엇이 가능한지를 조사한다. 

- 기본 골격 언어는 기본 연산들을 표현할 수 있다.  

 

3) 기본 골격 언어의 보편성

- 계산 가능한 임의의 함수는 기본 골격 언어로 작성된 프로그램에 의해 계산될 수 있다. 

- 기본 골격 언어는 보편적 프로그래밍 언어이고, 이론적으로 범용 프로그래밍 언어로 사용될 수 있다. 

- 기본 골격 언어와 같은 언어들은 응용 프로그래밍 환경에서는 실용적이지 않지만, 이론 컴퓨터과학에서는 유용하게 사용된다. 

 

4. 계산 불가능한 함수

1) 정지 문제 (halting problem)

- 어떤 프로그램이 특정 조건에서 시작한다면 종료할 것인지를 미리 예측하는 문제이다. 

- 어떤 프로그램이 종료할 것인지는 변수들의 초기값에 따라 달라질 수 있다. 

ex)

while (x)

{

x++;

}

 

- 따라서 어떤 프로그램의 실행이 종료될 것인지를 예측하려면 초기 값들에 대해 보다 정확히 표현할 필요가 있다. 

- 이를 위해 자기참조(self-reference) 기법을 이용한다. ; 자신을 참조하는 객체를 이용한다. 

- 기본 골격 언어 프로그램에서 모든 변수를 프로그램 자체에 대한 인코딩 표현으로 초기화하여 실행하여 종료하면, 그 프로그램은 자체 종료성(self-terminating)을 갖는다고 정의된다. (프로그램이 자신을 입력으로 시작할 때 그 실행이 종료된다면 자체 종료성을 갖는다.)

- 정지 문제란 기본 골격 언어 프로그램이 자체 종료성을 갖는지 여부를 결정하는 문제이며, 이 문제에 대해 해답할 수 있는 알고리즘은 없다. 

- 정지 문제가 요구하는 것은 모든 기본 골격 언어 프로그램에 대해 자체 종료성을 갖는지 여부를 결정할 수 있는 하나의 일반적인 알고리즘이다. 

- 특정 프로그램에 대해 자체 종료성을 갖는지를 결정하기 위한 몇 개의 고립된 통찰이 모든 경우에 적용될 수 있는 하나의 일반적인 방법이 존재한다는 것을 의미하는 것은 결코 아니다. 

 

2) 정지 문제의 해결 불가능성 

- 정지 함수가 계산 가능하다면, 이를 계산할 수 있는 기본 골격 언어 프로그램이 존재해야 한다. 

- 정지함수가 계산 가능하다는 가정은 거짓이기 때문에, 정지함수는 계산 가능하지 않다. 

- 정지함수를 해결 불가능한 문제(unsolvable problem)라고 할 수 있다.

 

5. 문제의 복잡도

1) 복잡도의 측정

- 빅-세타 표기법으로 알고리즘들을 실행에 필요한 시간에 따라 분류했다. 

- 알고리즘의 복잡도 측정

• 알고리즘 안의 의사결정 및 분기(branching)의 양으로 기준 
• 요구되는 저장공간의 양으로 기준 - 공간 복잡도(space complexity)
• 실행 시 수행되는 단계의 수를 측정

- 시간 복잡도 (time complexity)

: 컴퓨터가 소요하는 시간을 기준으로 한다. 

• 어떤 문제의 복잡도에 대해 알려진 사항을 표현하기 위해 빅-세타 표기법의 변형인 빅-오 표기법(big-O notation)을 사용한다. 

 

2) 다항식적 문제와 비다항식적 문제

- 다항식적 문제 (polynomial problem)

• f(n) 자체가 다항식이거나 f(n)이 어떤 다항식에 의해 한계가 정해지며 어떤 문제가 O(f(n))에 속하는 경우
• 모든 다항식적 문제의 집합을 P로 나타낸다. 
• 어떤 문제가 다항식적 문제라는 것은 그 문제를 해결하기 위해 필요한 시간과 관련된 표현이다. 

- 해결 곤란한 문제 (intractable problem) : 이론적으로는 해결 가능하지만 P에 속하지 않아 엄청난 시간복잡도를 갖는 문제

 

3) NP 문제

- 비결정적 다항식적 문제 (nondeterministic polynomial problem) 또는 NP 문제 (NP problem)

• 비결정적 알고리즘에 의해 다항식적 시간 안에 해결될 수 있는 문제
• NP 클래스의 집합을 NP라 표시한다. 
• P에 속하는 모든 문제들도 NP에 속한다. (임의의 결정적 알고리즘 성능에 영향을 미치지 않는 비결정적 명령을 추가할 수 있음)
• 모든 NP 문제가 P에 속하는지 여부는 미해결 문제이다. 

- 클래스 NP가 클래스 P와 실제로 동일한지에 대한 의문을 해결하기 위한 노력을 통해 클래스 NP 안에 NP 완전 문제(NP-complete problem)라는 또 다른 클래스가 존재한다는 것을 알게 되었다. 

• NP 완전 문제들은 이들 중 어느 한 문제에 대해서라도 다항식적 시간 해법이 존재할 경우, NP에 속하는 모든 문제들에 다항식적 시간 해법이 존재한다는 성질을 갖는다. 
• 그 결과로 클래스 NP는 클래스 P와 같게 될 것이다. 

- 많은 중요한 계산 문제들이 해결 곤란 또는 NP 클래스로 분류되며, 따라서 대부분의 경우 적절한 시간 내에 해결될 수 없다. 

- 알고리즘이 알려져 있지 않거나 적절한 시간 내에 문제를 해결하지 못하는 경우 통계적 기법이나 휴리스틱(heuristic) 기법이 이용될 수 있다. 

6. 공개키 암호

https://0yeonjae2.tistory.com/entry/IT%EA%B0%9C%EB%A1%A0-%EB%B3%B4%EC%95%88%EA%B3%BC-%EC%95%94%ED%98%B8%ED%99%94?category=535579 

[IT개론] 보안과 암호화

(위 글을 참고하시면 좋습니다.)

 

- 큰 정수의 인수를 결정하기 위한 효율적인 방법을 찾지 못한 것을 암호학에서 이용하고 있다.

- 이를 이용한 암호화 방법은 RSA 알고리즘이라 불리는데, RSA 알고리즘에서는 암호화 키(encrypting key)를 이용해 암호화하고, 복호화 키(decrypting key)라고 불리는 값을 이용해 메세지를 복호화한다. (공개키 암호화 시스템 (public-key encrytion) 시스템)

 

1) 모듈로 연산

- RSA 공개키 암호화 시스템의 기술에서 x를 m으로 나눈 나머지를 표현하기 위해 x 모듈로(modulo) m 또는 x mod m 으로 읽는 x % m 표현을 사용한다.

- p와 q가 소수이고, m이 0과 pq 사이의 정수일 경우, 임의의 양의 정수 k에 대해 다음과 같은 식이 성립한다. 

1 = m^(k(p-1)(q-1)) % pq

 

2) RSA 공개키 암호

(1) 두 개의 소수 p,q를 선택하고 그 곱을 n으로 표시한다. 

(2) 어떤 양의 정수 k에 대해 e*d = k(p-1)(q-1)+1을 만족하는 두 개의 다른 양의 정수 e와 d를 선택한다. 

(e와 n은 암호화에 사용하고, d와 n은 복호화에 사용할 것이다. p,q는 암호화 시스템의 구축 과정에서만 사용된다.)

* 메시지는 ASCII나 유니코드를 이용해 비트 패턴으로 인코딩되어 있으며, 2진수로 해석될 때 n보다 작다고 가정

(3) 2진수로 해석된 메시지가 나타내는 값이 m이라고 가정하면, 이 메시지의 암호화된 버전은 2진수 값 c = (m^e) % n이 된다. (암호회된 메시지는 m^e를 n으로 나눈 나머지의 2진수 표현에 해당한다.)

(4) 2진수로 c를 나타내는 메시지를 복호화하기 위해 (c^d) %n을 계산한다. 

 

- RSA 시스템의 보안성은 암호화 키 e와 n을 안다고 해서 복호화 키 n,d를 계산할 수 없다는 가정에 기초한다.

- 복호화 키를 찾을 수는 있지만 이에는 많은 시간이 소요된다.

- 현재까지 그 누구도 복호화 키를 모르는 상태에서 RSA 암호에 기초하여 만들어진 메시지를 효율적으로 복호화하는 방법을 찾지 못했다. 

- RSA 방식에 기초한 공개키 암호화가 인터넷상에서 통신 프라이버시 보호를 위해 널리 사용되고 있다.