LÝ THUYẾT ĐỘ PHỨC TẠP

LÝ THUYẾT NP - ĐẦY ĐỦ

(THE THEORY OF NP - COMPLETENESS)

Giáo viên : PGS TSKH Vũ Đình Hoà

The theory of NP-Completeness

1

MỞ ĐẦU TÌNH HUỐNG

 Bạn được làm thuê cho một công ty với tư cách là nhà

thiết kế thuật toán.

 Công ty sẽ tham gia thị trường cạnh tranh “bandersnatch

cao cấp”.

 Có phương pháp nào để tạo ra một tập các quy cách kĩ

thuật cho mỗi bài toán của thị trường bandersnatch đặt

ra?

MỞ ĐẦU PHẢI LÀM GÌ?

 Xác định chính xác bài toán = tham vấn

phòng bandersnatch.

 Lao vào công việc với đầy bầu nhiệt

huyết

MỞ ĐẦU KẾT QUẢ

 Vài tuần trôi qua

 Giấy tờ tràn ngập

 Không tìm được bất kì thuật toán nào

 phải mất hàng năm để xây dựng một thuật toán cho một

modun

 Có rất nhiều modun cho bài toán

MỞ ĐẦU PHẢI LÀM THẾ NÀO

 Nếu viết báo cáo rằng

→Bạn sẽ bị sa thải’

 Cần chứng minh rằng bài toán được giao là không thể giải

dễ dàng được

“Tôi thật ngu ngốc vì không thể tìm được thuật toán nào”

MỞ ĐẦU LỜI KHUYÊN

 Việc chứng minh tính không thể giải được = chứng minh

không tồn tại một thuật toán hữu hiệu.

 Lý thuyết sau đây chỉ ra rằng cần chứng minh bài toán của

bạn là bài toán NP-đầy đủ.

 Nó có độ khó tương đương với độ khó lớp các bài toán

khác mà nhiều chuyên gia phải bó tay.

MỞ ĐẦU LỜI KHUYÊN

 Tính NP-đầy đủ cho ta thấy:

→Khả năng tìm ra thuật toán tốt cho bài toán khó. →Cách chuyển hướng tiếp cận: giải gần đúng hoặc tìm lời giải cho những trường hợp đặc biệt

BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN

 Một bài toán/vấn đề là gì?:

→Một câu hỏi có tính tổng quát cần được trả lời.

→Thường chứa một số tham số hay biến tự do chưa được

xác định giá trị.

→Miêu tả:(1) các tham số, (2) các yêu cầu về câu trả lời.

BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN

 Bài toán:

→Ví dụ: Bt “Người du lịch”.

٧ Các thành phố

٧ Các khoảng cách

? Yêu cầu: tìm hoán vị tròn

sao cho tổng trọng số cạnh:

nhỏ nhất.

٭ Ý nghĩa:

BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN

 Một dữ kiện/input của bài toán:

5

9

10

6

3

9

Sắp xếp:

Là lời giải:

BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN

 Thuật toán:

→Gồm các thủ tục “từng bước-từng bước” giải quyết bài toán. →Có thể xem như một chương trình viết bằng ngôn ngữ máy.

 Một TT giải quyết được bài toán П nếu nó có lời giải

cho mọi dữ kiện/input I của bài toán đó.

BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN

 Thuật toán:

Thế nào là một TT hiệu quả (efficiency)?

 Chạy được với tất cả các input.

 Thời gian tính toán nhanh nhất. Yêu cầu về thời gian có tính quyết định xem một thuật toán có hiệu quả để đưa vào thực tế hay không

BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN

 Thuật toán: Yêu cầu về thời gian

 Có thể miêu tả hàm một biến (Kích thước của một bài

toán cụ thể)

 Đo kích thước của bài toán cụ thể theo cách thông

thường

–Để tính một cách chính xác thì phải xét cả số các khoảng  Ex, bài toán “người thương gia đi du lịch” có kích thước cách và độ lớn các khoảng cách giữa các thành phố.

là số lượng m các thành phố.

BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN

 Lược đồ mã hóa:

kí tự.

 Miêu tả đầu vào của một bài toán cụ thể bằng một chuỗi

 Độ dài đầu vào của trường hợp I của bài toán П là số kí tự

 Độ dài này là cách đo hình thức của kích thước bài toán

trong chuỗi kí tự của lược đồ mã hóa.

cụ thể П(I).

BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN

 Lược đồ mã hóa:

 Ví dụ: Bài toán người thương gia đi du lịch.

٭Sử dụng bộ kí tự:

{c, [, ], /, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

“c[1] c[2] c[3] c[4] // 10 / 5 / 9 // 6 / 9 // 3”

٭Chuỗi mã hóa:

٭ Độ dài đầu vào là 32.

chuỗi tương tự, không phải chuỗi rời rạc.

٭ Các trường hợp bài toán phức tạp, có thể mã hóa bằng

BÀI TOÁN, THUẬT TOÁN VÀ ĐỘ PHỨC TẠP MỘT SỐ KHÁI NIỆM CƠ BẢN

 Hàm thời gian:

Cho mỗi kích thước đầu vào một lượng thời gian lớn nhất

để giải quyết trường hợp của bài toán đó

THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC

 1 hàm f(n) là O(g(n)) khi hằng c, k:

 1 thuật toán thời gian đa thức có độ phức tạp là O(p(n))

|f(n)|<=c.|g(n)| n>=k

với p(n) là một hàm đa thức.

 1 thuật toán thời gian lũy thừa nếu hàm phức tạp thời gian

 n chỉ kích thước đầu vào

(bao gồm cả một số hàm phức tạp thời gian không

đa thức như )

của nó không có giới hạn.

THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC

 Bảng so sánh một số hàm phức tạp thời gian

lũy thừa và đa thức.

Size n

10

20

30

40

50

60

Time complexity function

.00002s

.00003s

.00004s

.00005s

.00006s

.00001s

.0001s

.0004s

.0009s

.0016s

.0025s

.0036s

.001s

.008s

.0027s

.064s

.125s

.216s

.1s

3.2s

24.3s

1.7m

5.2m

13.0m

.001s

1.0s

17.9m

12.7d

35.7y

366c

1.3 x 1013 c

2 x 108 c

.059s

58m

6.5y

3855c

THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC

 Ảnh hưởng của công nghệ máy tính đến các hàm phức tạp

thời gian

Computer 100 times faster

Present computer

Computer 1000 times faster

1000N1

100N1

Time complexity function n

31.6N2

n2

10N2 4.64N3

n3

10N3

N1 N2 N3

3.98N4

n5

2.5N4

N5+6.64

N5+9.97

2n

N6+4.19

N6+6.29

3n

N4 N5 N6

THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC

 Một bài toán là không thể giải được nếu quá khó để

tìm ra một thuật toán thời gian đa thức để giải

quyết nó.

 Với kích thước bài toán có hạn thì việc so sánh

giữa thuật toán đa thức hữu hiệu và thuật toán lũy

thừa không hữu hiệu có nhiều ngoại lệ.

 Ex: xem bảng so sánh ở slide trước, thuật toán 2n

nhanh hơn thuật toán n5 với n<=20.

THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC

 Một số nhận xét

 Độ phức tạp về thời gian được định nghĩa trong trường

hợp xấu nhất

 Một thuật toán 2n nghĩa là có ít nhất một trường hợp bài

toán cỡ n cần bằng ẫy thời gian.

 Hầu hết trong thực tế cần ít thời gian hơn nhiều.

 Thuật ngữ “intratability” chỉ có nghĩa tương đối vì:

THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC

 Một số nhận xét

 Ex1, thuật toán đơn hình (simplex) cho lập trình

tuyến tính có độ phức tạp lũy thừa [Klee & Minty,

1972], [Zadeh, 1973] nhưng lại có thành tích ấn

tượng về việc chạy nhanh trong thực tế.

 Ex2, thuật toán “Branch and bound” cho bài toán

Knapsack có độ phức tạp lũy thừa nhưng lại thành

công khiến nhiều người ngạc nhiên.

THUẬT TOÁN THỜI GIAN ĐA THỨC VÀ NHỮNG BÀI TOÁN KHÔNG GIẢI ĐƯỢC

 BÀI TẬP:

 Viết thuật toán xác định số n cho trước có phải số

nguyên tố hay không và tính thời gian chạy máy

tính như hàm số với biến là kích thước biểu diễn

input đầu vào.