제 13강 근사 알고리즘(튜링기계,다항시간,클래스P,클래스NP)

학습 목표

1. 튜링기계, 다항 시간 알고리즘, 판정 문제의 개념을 이해할 수 있다.

2. 클래스 P와 클래스 NP의 개념을 이해할 수 있따.

3. NP-완전 문제와 NP-하드 문제의 개념과 종류를 이해할 수 있다.

4. NP- 하드 문제의 다양한 근사 알고리즘을 이해할 수 있따.

 

주요 용어

결정론적 튜링기계, 비결정론적 튜링 기계, 쉬운 문제, 어려운 문제, 다항 시간 알고리즘, 판정 문제, 클래스 P, 변환, NP-완전문제(외판원문제, 0/1 배낭 문제, CNF 만족성 문제, 해밀토니언 사이클 문제, 퀘 채우기 문제, 파티션 문제, 클리크 판정 문제, 버텍스 커버문제), NP-하드 문제, NP-완전성, 근사 알고리즘

 

7.1 기본 개념

7.1.1. 튜징기계(Turing machine)

- 컴퓨터의 이론적 모델

- 구성요소 > 테이프, 기호, 헤드, 상태, 규칙

   - 무한한 길이의 테이프, 유한한 개수의 기호와 상태, 상태와 기호에 따른 헤드의 동작을 정해둔 규칙

   - 현재 상태와 읽은 기호에 따라 헤드가 테이프에 기호를 쓰거나 좌우로 이동

- 주어진 테이프와 규칙에 따라 동작하는 튜링 기계

  = 주어진 입력과 알고리즘으로 동작하는 컴퓨터

 

(1) 결정론적 튜링기계 = 순차 처리 컴퓨터

 - 테이프의 위치를 바꾸거나 쓰인 기호를 바꿀 때 한 가지 상태로만 변경 가능

 

(2) 비 결정론적 튜링 기계 = 병렬 처리 컴퓨터

 - 하나 이상의 상태로 바뀔 수 있거나 혹은 바뀔 상태가 없을 수 있음

  - 연산 결과가 상황에 따라 달라질 수 있는 연산을 수행

 

7.1.2 다항 시간 polynomial time 알고리즘

>알고리즘의 수행 시간이 입력 크기에 대한 다항식으로표현

   - O(1), O(logn), O(n), O(nlogn), O(n^2).......O(N^k)...

  - O(2^n) > 지수 시간 알고리즘

 

> 문제 난이도

- 쉬운 tractable 문제

  : 결정론적 튜링 기계를 이용한 다항 시간 알고리즘이 존재하는 문제

 

- 어려운 intractable 문제

 :  결정론적 튜링 기계를 이용한 다항 시간 알고리즘의 존재 여부를 알 수 없는 문제

 

7.1.3 판정문제

> 문제 형태에 따른 분류

- 판정 decision 문제

 : 예 혹은 아니오 중 하나를 답으로 요구하는 형태의 문제

 : 예) n x n 이 n + n 보다 작은 자연수 n 이 존재하는가?

 

- 최적화 optimization 문제

 :  최솟값 또는 최댓값을 구한는 형태의 문제

 :  예) n x n 이 n + n 보다 작은 자연수 n 을 모두 찾으시오.

 

 

 

 

7.2 클래스 P 와 클래스 NP

> 클래스 P

 - 결정론적 튜링 기계를 이용하여 다항 시간에 해결할 수 있는 모든 판정 문제의 집합

  : 쉬운 문제의 판정 문제 버전을 원소를 갖는 집합

  : 주어진 그래프에서 정점 a 에서 정점 e까지의 최단 거리는 10보다 작은가?

 

>클래스 NP

 -비결정론적 튜링 기계를 이용하여 다항 시간에 해결할 수 있는 모든 판정 문제의 집합 

  : 최단 경로 문제의 판정 문제 버전

  : 외판원 문제 > 주어진 가중 그래프에서 모든 정점을 한 번씩만 방문하고 처음 정점으로 돌아오는 비용이 50 보다 작은 경로가 존재하는가?

 

> 클래스 P 와 클래스 NP 의 관계