ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Nguyễn Văn Kiên
LÝ THUYẾT LẬP LỊCH VÀ ỨNG DỤNG GIẢI QUYẾT BÀI
TOÁN LẬP LỊCH CHO CPU
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
1
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
Thái Nguyên 2013
LỜI CẢM ƠN
Em xin chân thành cảm ơn Trƣờng Đại Học Công Nghệ Thông Tin và truyền
thông đã tạo điều kiện cho em thực hiện luận văn này.
Em cũng xin chân thành cảm ơn tới toàn thể thầy cô giáo ở Viện công nghệ
thông tin và trƣờng Đại học công nghệ thông tin và truyền thông đã tận tình giảng dạy
và hƣớng dẫn, trang bị cho em những kiến thức cần thiết trong quá trình thực hiện luận
văn đƣợc thành công.
Dựa trên sự chỉ bảo tận tình của T.S Vũ Vinh Quang dựa trên những kiến thức
đã học, và tìm hiểu đƣợc, em đã hoàn thành luận văn theo đúng thời gian quy định. Tuy
nhiên trong quá trình thiết kế và thực hiện luận văn không tránh khỏi sai sót, do thời
gian có hạn và khả năng còn hạn chế. Em mong quý thầy cô và các bạn thông cảm và
có những ý kiến quý báu nhằm hoàn thiện hơn cho sản phẩm.
Em xin chân thành cảm ơn.
Thái nguyên, ngày 18 tháng 7 năm 2013
Học viên
Nguyễn Văn Kiên
2
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
LỜI CAM ĐOAN
Em xin cam đoan luận văn tốt nghiệp: “Lý thuyết lập lịch và ứng dụng giải
quyết bài toán lập lịch cho CPU” do em tự thực hiện dƣới sự hƣớng dẫn của thầy giáo
Vũ Vinh Quang. Các kết quả và số liệu hoàn toàn trung thực.
Ngoài các tài liệu tham khảo đã dẫn ra ở cuối luận văn em đảm bảo rằng không
sao chép các công trình hay luận văn tốt nghiệp của ngƣời khác. Nếu phát hiện có sự
sai phạm với điều cam đoan trên, em xin hoàn toàn chịu trách nhiệm.
3
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
MỤC LỤC
LỜI CẢM ƠN.................................................................................................................. 1
LỜI CAM ĐOAN ............................................................................................................ 3
MỤC LỤC ....................................................................................................................... 4
LỜI NÓI ĐẦU ................................................................................................................. 6
CHƢƠNG 1 ..................................................................................................................... 8
MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN VÀ ĐỘ PHỨC TẠP THUẬT
TOÁN .............................................................................................................................. 8
1.1. Khái niệm cơ bản ...................................................................................................... 8
1.1.1. Thuật toán ...................................................................................................... 8
1.1.2. Kh¸i niÖm vÒ ®é phøc t¹p thuËt to¸n. ............................................................ 8
1.1.3. Cách tính độ phức tạp .................................................................................. 12
1.2. Vấn đề phân lớp các bài toán.................................................................................. 13
1.2.1. Tổng quan về sự phân lớp các bài toán ....................................................... 13
1.2.2. Khái niệm dẫn về đƣợc ................................................................................ 16
1.3. Lớp các bài toán P và NP ....................................................................................... 16
1.3.1. Một số khái niệm ......................................................................................... 16
1.3.2. Một số bài toán đã đƣợc chứng minh là NP – khó, NP - đầy đủ ................. 21
1.4. Thuật toán xấp xỉ .................................................................................................... 23
1.4.1. Các khái niệm .............................................................................................. 23
1.4.2. Thuật toán - xấp xỉ tuyệt đối .................................................................... 24
1.4.3. Thuật toán - xấp xỉ.................................................................................... 26
CHƢƠNG 2 ................................................................................................................... 28
LÝ THUYẾT LẬP LỊCH .............................................................................................. 28
2.1. Mô hình bài toán lập lịch ........................................................................................ 28
2.2. Các thuật toán lập lịch kinh điển ............................................................................ 32
2.3. Một số thuật toán lập lịch cho CPU ....................................................................... 34
2.3.1. Mô hình bài toán lập lịch cho CPU ............................................................. 34
2.3.2. Một số thuật toán lập lịch cho CPU ............................................................ 35
4
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
2.3.2.1. Lập lịch FCFS........................................................................................... 35
2.3.2.2. Lập lịch SJF .............................................................................................. 37
2.3.2.3. Lập lịch theo độ ƣu tiên ............................................................................ 40
2.3.2.4. Lập lịch RR............................................................................................... 43
2.3.2.5. Lập lịch với hàng đợi nhiều cấp ............................................................... 46
2.3.2.6. Lập lịch hàng đợi phản hồi đa cấp............................................................ 48
CHƢƠNG 3 ................................................................................................................... 51
KẾT QUẢ CÀI ĐẶT MỘT SỐ THUẬT TOÁN LẬP LỊCH CPU .............................. 51
3.1. Giới thiệu sơ lƣợc về ngôn ngữ lập trình C# và công cụ lập trình Visual Studio. ................ 51
3.1.1.Giới thiệu về ngôn ngữ lập trình C# ............................................................. 51
3.1.2. Giới thiệu về công cụ lập trình Visual Studio ............................................. 54
3.2. Phân tích thuật toán cài đặt CPU ............................................................................ 56
3.2.1. Thuật toán FCFS.......................................................................................... 56
3.2.2 Thuật toán SJF .............................................................................................. 57
3.2.3. Thuật toán RR.............................................................................................. 59
3.2.4. Sơ đồ thuật toán CPU .................................................................................. 60
3.3. Kết quả cài đặt thuật toán CPU .............................................................................. 60
3.3.1. Các thành phần của chƣơng trình ................................................................ 60
3.3.2. Cấu trúc chi tiết ........................................................................................... 61
3.3.3. Sử dụng chƣơng trình. ................................................................................. 63
KẾT LUẬN ................................................................................................................... 66
TÀI LIỆU THAM KHẢO ............................................................................................. 67
PHỤ LỤC ...................................................................................................................... 68
I. Thuật toán cài đặt ....................................................................................................... 68
II. Các hàm và phƣơng thức cơ bản của chƣơng trình. ................................................. 77
5
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
LỜI NÓI ĐẦU
Máy tính điện tử ra đời vào những năm 40 của thế kỷ XX. Ban đầu, phạm vi sử
dụng máy tính còn rất hẹp, đa phần chỉ nhằm phục vụ mục đích nghiên cứu khoa học.
Hơn nữa, để vận hành hệ thống cần phải sử dụng các công cụ phần cứng đặc biệt và
thao tác vận hành rất phức tạp.
Cùng phát triển song song với sự phát triển của kỹ thuật điện tử, các thế hệ máy
tính về sau đƣợc cải tiến ngày một tinh vi hơn, có tốc độ xử lý nhanh hơn, kích thƣớc
nhỏ gọn hơn, tiêu tốn ít năng lƣợng hơn và đã làm nên một cuộc cách mạng trong lĩnh
vực xử lý, tính toán, điều khiển động…Với các hệ máy tính này đòi hỏi phải có sự điều
khiển, vận hành một cách tự động để phát huy hiệu quả của nó một cách tối ƣu nhất.
Nhƣ vậy, cần phải có một chƣơng trình phần mềm đảm bảo việc giải quyết các vấn đề
trên. Đó chính là các hệ điều hành máy tính.
Mỗi hệ điều hành đều cần có thuật toán lập lịch cho riêng chúng. Thuật toán thƣờng
đƣợc thực hiện để cân bằng cho hệ thống máy tính đƣợc hiệu quả. Sự cần thiết của thuật
toán lập lịch xuất phát từ yêu cầu cho hầu hết các hệ thống hiện đại để thực thi nhiều hơn
một công việc tại cùng một thời điểm và có thể truyền tải nhiều luồng dữ liệu một lúc. Trong
môi trƣờng thời gian thực, chẳng hạn nhƣ các hệ thống nhúng điều khiển tự động trong
ngành công nghiệp (Robot) thì lập lịch cũng phải đảm bảo rằng quá trình có thể đáp ứng
đúng thời hạn, điều này là rất quan trọng để giữ hệ thống ổn định.
Việc nghiên cứu các thuật toán lập lịch dành CPU này mở ra nhiều hƣớng mới
cho khoa học và ứng dụng của nó trong thực tiễn cuộc sống. Đƣợc sự đồng ý của Thầy
hƣớng dẫn, Em chọn đề tài “Lý thuyết lập lịch và ứng dụng giải quyết bài toán lập lịch
cho CPU” làm đề tài luận văn cao học. Nội dung chính của đề tài bao gồm:
Chƣơng 1: Trình bày một số khái niệm về thuật toán và các nguyên tắc đánh giá
độ phức tạp của thuật toán, vấn đề phân lớp các bài toán theo độ phức tạp của thuật
toán. Đầy là phần lý thuyết quan trọng làm cơ sở để nghiên cứu trong các chƣơng tiếp
sau của luận văn.
6
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
Chƣơng 2: Trình bày lý thuyết cơ bản về bài toán lập lịch, các thuật toán giải bài
toán lập lịch cơ bản và trọng tâm là trình bày một số thuật toán lập lịch cho CPU. Đây
chính là nội dung trọng tâm của luận văn
Chƣơng 3: Đƣa ra kết quả cài đặt các thuật toán lập lịch cho CPU trên nền ngôn
ngữ Visual Studio 10.
Nội dung đề tài là một lĩnh vực rộng và khó, với khoảng thời gian không nhiều
cùng với kiến thức của bản thân còn hạn chế, trong đề tài này mới chỉ đề cập đến việc
nghiên cứu thuật toán lập lịch chủ yếu là trên một máy và ứng dụng cho lập lịch CPU.
7
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
CHƢƠNG 1
MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN
VÀ ĐỘ PHỨC TẠP THUẬT TOÁN
Trong chƣơng 1, luận văn sẽ trình bày một số kiến thức cơ bản về thuật toán và
độ phức tạp thuật toán, vấn đề phân lớp các bài toán dựa trên độ phức tạp thuật toán.
Các kiến thức này đã đƣợc tham khảo trong các tài liệu [3], [4]. Đây là các kiến thức
quan trọng để trình bày tiếp các nội dung trong chƣơng 2 và chƣơng 3 của luận văn.
1.1. Khái niệm cơ bản
1.1.1. Thuật toán
Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác đƣợc sắp xếp
theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ dữ liệu đầu vào
(Input) của bài toán, ta nhận đƣợc kết quả (Output) cần tìm.
Ta đã biết 2 mô hình tính toán là máy Turing và máy xử lý thuật toán viết bằng
ngôn ngữ tựa ALGOL. Ứng với hai mô hình tính toán này có 2 cách biểu diễn thuật
toán:
+ Thuật toán đƣợc biểu diễn bằng ngôn ngữ máy Turing.
+ Thuật toán đƣợc biểu diễn bằng ngôn ngữ tựa ALGOL.
1.1.2. Kh¸i niÖm vÒ ®é phøc t¹p thuËt to¸n.
a. Chi phí phải trả cho một quá trình tính toán
Trong quá trình xử lý thuật toán, ngƣời ta thƣờng quan tâm tới chi phí cho thời
gian tính toán và chi phí cho không gian chứa dữ liệu tính toán (bộ nhớ).
- Chi phí thời gian chính là tổng thời gian cần thiết để thực hiện xong một quá
trình tính toán.
+ Với máy Turing: Chi phí thời gian là số bƣớc chuyển hình trạng từ hình trạng
đầu q0 đến hình trạng kết thúc qn .
8
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
+ Với thuật toán tựa Algol: Chi phí thời gian là số các phép tính cơ bản cần thực
hiện trong quá trình tính toán.
- Chi phí không gian chính là số ô nhớ cần để thực hiện hoàn chỉnh trong quá
trình tính toán.
Gọi A là một thuật toán tƣơng ứng với một mô hình tính toán, gọi e là bộ dữ liệu
vào đã đƣợc mã hóa theo cách nào đó. Khi đó thuật toán A tính trên bộ dữ liệu e cần
phải trả về giá thời gian và giá không gian trong đó ta kí hiệu
+ t A (e ) là giá phải trả về thời gian tính toán
+ lA (e ) là giá về không gian của bộ nhớ cần thiết sử dụng
Khi đó tổng giá phải trả của thuật toán A tính trên bộ dữ liệu e chính bằng :
T(A)= t A (e ) + lA (e )
b. Các khái niệm về độ phức tạp của thuật toán
Độ phức tạp trong trƣờng hợp xấu nhất
Cho một thuật toán A với đầu vào n, khi đó:
- Độ phức tạp về bộ nhớ trong trƣờng hợp xấu nhất đƣợc định nghĩa là:
LA (n ) = max{lA (e) || | e | £ n } tức là chi phí lớn nhất về bộ nhớ.
- Độ phức tạp thời gian trong trƣờng hợp xấu nhất đƣợc định nghĩa là :
T A (n ) = max{t A (e) || | e | £ n } tức là chi phí lớn nhất về thời gian.
Độ phức tạp trung bình
Là tổng số các độ phức tạp khác nhau ứng với các bộ dữ liệu chia cho tổng số.
Độ phức tạp tiệm cận
Thuật toán A với đầu vào n gọi là có độ phức tạp O(f(n)) nếu $ hằng số C,
N 0 :T A (n ) £ C .f (n ), " n ³ N 0 tức là T A (n ) có tốc độ tăng là O(f(n))
9
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
10
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
Độ phức tạp đa thức (Polynomial)
Thuật toán đƣợc gọi là có độ phức tạp đa thức nếu tồn tại đa thức P(n) mà
T A (n ) £ C .P (n ), " n ³ N 0 .
Thuật toán đa thức
Thuật toán đƣợc gọi là đa thức nếu độ phức tạp về thời gian trong trƣờng hợp
xấu nhất của nó là đa thức.
Việc đánh giá đúng độ phức tạp của bài toán là một vấn đề hết sức phức tạp. Vì
vậy ngƣời ta thƣờng quan tâm đến việc đánh giá độ phức tạp thời gian trong trƣờng
hợp xấu nhất của bài toán.
Một số quy ước kí hiệu về độ phức tạp thuật toán
Kí hiệu
Độ phức tạp
O(1)
Độ phức tạp hằng số
O(log n )
Độ phức tạp logarit
O(n )
Độ phức tạp n
O(n log n )
Độ phức tạp nlogn
O (n k )
Độ phức tạp đa thức
O (2n )
Độ phức tạp hàm mũ
O(n !)
Độ phức tạp giai thừa
Ghi chú
11
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
1.1.3. Cách tính độ phức tạp
a. Các quy tắc cơ bản
Quy tắc cộng: Nếu T1(n) và T2(n) là thời gian thực hiện 2 chương trình P1, P2
và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của đoạn 2 chương trình đó
nối tiếp nhau là T(n)=O(max(f(n),g(n))
Quy tắc nhân: Nếu T1(n) và T2(n) là thời gian thực hiện 2 đoạn chương trình
P1, P2 và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của 2 đoạn chương trình
đó lồng nhau là T(n)=O(f(n).g(n)).
Quy tắc tổng quát để phân tích một chƣơng trình
- Thời gian thực hiện của mỗi lệnh gán, READ, WRITE là O(1)
- Thời gian thực hiện của một chuỗi tuần tự các lệnh đƣợc xác định bằng quy tắc
cộng,thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh.
- Thời gian thực hiên cấu trúc IF là thời gian lớn nhất thực hiện câu lệnh sau
THEN hoặc ELSE và thời gian kiểm tra điều kiện, thƣờng là thời gian kiểm tra điều
kiện là O(1).
- Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực
hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian thực
hiện vòng lặp là tích số lần lặp với thời gian thực hiện thân vòng lặp.
Chú ý: Độ phức tạp thuật toán không chỉ phụ thuộc vào kích thƣớc, thời gian
mà còn phụ thuộc vào tính chất của dữ liệu vào.
c. Độ phức tạp của các chƣơng trình đệ quy
Với các chƣơng trình chƣơng trình đệ quy, trƣớc hết ta cần thành lập các
phƣơng trình đệ quy, sau đó giải các phƣơng trình đệ quy. Nghiệm của phƣơng trình đệ
quy là thời gian thực hiện chƣơng trình đệ quy đó.
12
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
Thành lập phƣơng trình đệ quy:
Phƣơng trình đệ quy là một phƣơng trình biểu diễn mối liên hệ giữa T(n) và
T(k) trong đó:
T(n) là thời gian thực hiện với kích thƣớc dữ liệu nhập là n,
T(k) là thời gian thực hiện với kích thƣớc dữ liệu nhập là k, k1 đƣợc thay thế bởi biểu thức của T(1). Vì T(1) luôn là
hằng nên ta có công thức của T(n) chứa các số hạng chỉ liên quan tới n và các hằng số.
Định lý: (Về nghiệm của phƣơng trình truy hồi)
Cho a, b, c nguyên, dƣơng. Khi đó nghiệm của phƣơng trình truy hồi:
ìï b nÕu n = 1
ï
T (n ) = ïí
ïï aT( n ) + bn nÕu n > 1, n = c k
ïïî
c
Có dạng:
ìï O (n ) nÕu a < c
ïï
T(n) = T (n ) = ïí O (n logc n ) nÕu a = c
ïï
ïï O(n logca ) nÕu a > c
ïî
1.2. Vấn đề phân lớp các bài toán
1.2.1. Tổng quan về sự phân lớp các bài toán
Độ phức tạp của thuật toán chính là yếu tố cơ sở để phân loại vấn đề bài toán.
Một cách tổng quát, mọi bài toán đều có thể chia làm 2 lớp lớn là: giải đƣợc và không
giải đƣợc. Lớp giải đƣợc chia làm 2 lớp con. Lớp con đầu tiên là các bài toán có độ
phức tạp đa thức: nghĩa là bài toán có thể giải đƣợc bằng thuật toán có độ phức tạp đa
13
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
thức (hay nói ngắn gọn: lớp đa thức) đƣợc xem là có lời giải thực tế. Lớp con thứ hai là
những bài toán có độ phức tạp không phải là đa thức mà lời giải của nó đƣợc xem là
thực tế chỉ cho những số liệu đầu vào có chọn lựa cẩn thận và tƣơng đối nhỏ. Cuối
cùng là những bài toán thuộc loại NP chƣa phân loại một cách chính xác là thuộc lớp
bài toán có độ phức tạp đa thức hay có độ phức tạp không đa thức.
Do đó, ta có sự phân lớp các bài toán do 2 tác giả Cook và Karp đề xuất năm
1970-1971 nhƣ sau:
a. Lớp bài toán có độ phức tạp đa thức (lớp P) : Là lớp các bài toán có thể giải đƣợc
bằng thuật toán đơn định trong thời gian đa thức (Deterministic polynomial).
Lớp bài toán có độ phức tạp đa thức là lớp bài toán có độ phức tạp là O(nk) hoặc
nhỏ hơn O(nk). Chẳng hạn nhƣ các bài toán có độ phức tạp là O(nlog2n) đƣợc xem là
các bài toán thuộc lớp đa thức vì nlog2n bị chặn bởi n2. Nhƣ vậy các bài toán có độ
phức tạp hằng O(1), phức tạp tuyến tính O(n) và logarit O(nlog an) đều là các bài toán
thuộc lớp đa thức. Còn các bài toán có độ phức tạp lũy thừa O(an) hoặc giai thừa O(n!)
là không thuộc lớp đa thức.
Tuy độ phức tạp chỉ là số đo về độ tăng chi phí ứng với độ tăng của dữ liệu đầu
vào nhƣng nó cũng cho chúng ta một đánh giá tƣơng đối về thời gian thực hiện thuật
toán. Các thuật toán thuộc lớp đa thức đƣợc xem là các bài toán có lời giải thực tế. Lời
giải thực tế đƣợc hiểu rằng là chi phí về mặt thời gian và không gian cho việc giải bài
toán là chấp nhận đƣợc trong điều kiện hiện tại. Bất kỳ một bài toán nào không thuộc
lớp này thì đều có chi phí rất lớn.
Chính vì lý do này, một bài toán đƣợc xem là có thể giải đƣợc trên thực tế hay
không phụ thuộc vào độ phức tạp của bài toán có phải là đa thức hay không.
b. Lớp bài toán có độ phức tạp trên đa thức
Trong thực tế, nhiều bài toán thực sự có lời giải lại không thuộc lớp của bài toán
đa thức. Ví dụ: Cho một tập hợp có n phần tử, hãy liệt kê tất cả các tập con khác trống
của tập hợp này. Bằng toán học, ngƣời ta đã chứng minh đƣợc rằng số tập con của một
14
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
tập hợp có n phần tử là 2n-1. Lời giải tuy đã có nhƣng khi thể hiện lời giải này bằng bất
kỳ thuật toán nào thì phải tốn ít nhất 2n-1 bƣớc. Dễ thấy rằng độ phức tạp của bài toán
này cỡ O(2n). Nhƣ vậy bài toán này không thuộc lớp của bài toán đa thức. Với n vào
khoảng 16, số bƣớc cần thiết chỉ khoảng vài chục ngàn là hoàn toàn giải đƣợc trên các
máy tính hiện nay. Nhƣng khi phần tử lên tới 32 thì ta đã tốn một số bƣớc lên tới 4 tỷ,
chỉ thêm một phần tử nữa thôi chúng ta lại tốn thêm 8 tỷ bƣớc. Với số lƣợng bƣớc nhƣ
vậy, du chạy trên một siêu máy tính cũng phải tốn một thời gian đáng kể. Các bài toán
không thuộc lớp đa thức chỉ giải đƣợc với một độ lớn dữ liệu đầu vào nhất định.
Định nghĩa
Một bài toán đƣợc giải bằng thuật toán không đơn định đa thức đƣợc gọi là bài
toán thuộc lớp NP.
Theo định nghĩa trên thì bài toán ngƣời bán hàng là bài toán thuộc lớp NP. Cho
đến nay ngƣời ta chƣa chứng minh đƣợc rằng tồn tại hay không một thuật toán tự
quyết có độ phức tạp đa thức cho bài toán ngƣời bán hàng rong. Vì vậy, bài toán này
(là một bài toán NP) chƣa thể xếp đƣợc vào lớp đa thức. Do đó, lớp bài toán NP chƣa
thể phân loại thuộc lớp đa thức hay không.
Dĩ nhiên, lớp bài toán NP cũng chứa những bài toán thuộc lớp đa thức thực sự,
bởi vì nếu một bài toán đƣợc giải bằng thuật toán tự quyết có độ phức tạp đa thức thì
chắc chắn khi dùng thuật toán không tự quyết thì cũng sẽ có độ phức tạp đa thức.
Nhƣ vậy P NP.
15
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
Nhƣng hiện nay chƣa chứng minh đƣợc P là tập con thực sự của NP, vấn đề P =
NP hay không hiện là một trong số các vấn đề mở nổi tiếng nhất và cũng đắt giá nhất
trong Toán học và trong Tin học lý thuyết.
1.2.2. Khái niệm dẫn về đƣợc
Cho hai bài toán A, B
Định nghĩa 1: Bài toán A được gọi là dẫn về được bài toán B sau thời gian đa
thức nếu có một thuật toán đa thức để giải bài toán B thì cũng có một thuật toán đa
thức để giải bài toán A.
Nghĩa là: Bài toán B “khó hơn” bài toán A hay A “dễ hơn” B hay A là trƣờng
hợp riêng của B. Kí hiệu A B.
Phép quy dẫn có tính chất bắc cầu: A B và B C A C.
Tƣ tƣởng quy dẫn đã giải thích vai trò quan trọng của lớp bài toán P. Nếu ta có
bài toán A thuộc lớp P và một bài toán B có thể quy dẫn về A, thế thì B cũng thuộc vào
P. Nghĩa là P là đóng đối với phép quy dẫn.
Định nghĩa 2 : Bài toán A được gọi là “khó tương đương” bài toán B nếu A B
và B A. Kí hiệu A ~ B.
1.3. Lớp các bài toán P và NP
1.3.1. Một số khái niệm
a. Bài toán quyết định: Bài toán quyết định là bài toán mà đầu ra chỉ có thể là “Yes”
hoặc “No” (Đúng/sai, 0/1, chấp nhận/từ chối).
Ví dụ: Bài toán về tính nguyên tố: ” Hỏi số nguyên n có là số nguyên tố hay
không?”. Khi đó ta có n = 23 là bộ dữ liệu vào “Yes”, còn n = 24 là bộ dữ liệu vào “
No” của bài toán.
b. Bài toán NP – Khó (NP – Hard)
16
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
Bài toán A được gọi là NP- khó nếu như tồn tại thuật toán đa thức để giải bài
toán A thì kéo theo sự tồn tại thuật toán đa thức để giải mọi bài toán trong NP.
Hay: A là NP – Khó nếu nhƣ B A, với mọi bài toán B NP
Một cách không hình thức, có thể nói rằng nếu ta có thể giải đƣợc một cách hiệu
quả một bài toán NP – Khó cụ thể thì ta cũng có thể giải hiệu quả bất kỳ bài toán nào
trong NP bằng cách sử dụng thuật toán giải bài toán NP-Khó nhƣ là một chƣơng trình
con.
c. Bài toán NP - đầy đủ (NP – complete, NPC)
Một bài toán quyết định A đƣợc gọi là NP - đầy đủ nếu nhƣ
i) A là bài toán trong NP,
ii) Mọi bài toán trong NP đều có thể quy dẫn về A.
Lƣu ý: Khái niệm NP - đầy đủ đòi hỏi bài toán nhất thiết phải có dạng quyết
định.
Ta có bức tranh tạm thời đầy đủ về phân lớp các bài toán trên hình sau:
NP
NPC
NP-khó
P
H×nh 1: Sù ph©n líp c¸c bµi to¸n
d. Phƣơng pháp chứng minh một bài toán là NP - đầy đủ
- Cách 1: Theo định nghĩa (rất khó).
- Cách 2: áp dụng bổ đề sau:
17
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
Bổ đề: Giả sử bài toán A là NP - đầy đủ, bài toán B thuộc NP và bài toán A quy
dẫn về B. Khi đó bài toán B cũng là NP - đầy đủ.
Ví dụ: Bài toán xếp balô(KNASPACK) NPC Chứng minh bài toán lập lịch
NPC.
Bài toán lập lịch (Bài toán phạt):
Input: Có n công việc xử lý trên một máy.
ri : Thời điểm bắt đầu công việc xử lý i
d i : Hạn định hoàn thành công việc i.
t i : Thời gian xử lý công việc i, t i £ di - ri
bi : Thời gian bắt đầu xử lý.
ci : Thời gian kết thúc công việc i, t i = ci - bi
nếu ci £ di , công việc i là xử lý đúng hạn.
nếu ci > di , công việc i là xử lý quá hạn(bị phạt).
wi : Tiền phạt.
Output: Hãy sắp xếp các công việc theo một thứ tự nhất định để theo đó chờ đến
lƣợt xử lý, sao cho lƣợng tiền phạt là ít nhất.
Kí hiệu
ìï 0
U i = ïí
ïï 1
î
Khi đó yêu cầu :
nếu
nếu
ci £ d i
(đúng hạn)
(quá hạn)
ci > d i
n
å
U i Wi ® min
i= 1
n
Ta có thể viết bài toán trên ngắn gọn nhƣ sau : n | 1 | å U i Wi , kí hiệu là phạt.
i= 1
18
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
Bài toán này rõ ràng là giải đƣợc bằng phƣơng pháp “vét toàn bộ”. Nhƣng thực
tế khó giải vì nó thuộc lớp NP_đầy đủ.
Để chứng minh bài toán “phạt” là NP - đầy đủ, chỉ cần chứng minh rằng bài
toán KNAPSACK là bài toán phạt vì ta đã biết KNAPSACK là NP_đầy đủ. Nói một
cách khác KNAPSACK là trƣờng hợp riêng của bài toán phạt.
Nhắc lại bài toán KNAPSACK:
Input: n đồ vật với thể tích a1,a2,…an cần nhét vào balô có thể tích B.
Output: Tìm nhóm đồ vật có thể nhét vừa balô trên.
($ T Í {1, 2,..., n } mà
å
iÎ T
ai = B )
Để chứng minh KNAPSACK bài toán phạt trƣớc hết ta diễn đạt nó bằng ngôn
ngữ của bài toán phạt. Cụ thể mỗi vật i ở KNAPSACK đƣợc xem là một công việc
trong bài toán phạt, chúng đồng thời đƣợc nhập vào hệ thống. Mọi công việc có hạn
định nhƣ nhau và bằng B. Thời gian t i thực hiện công việc i bằng tiền phạt w i và bằng
thể tích a i của vật.
Tóm lại ta có thể biểu diễn bài toán nhƣ sau:
Input:
- n công việc đồng thời đƣợc xử lý ri = 0, " i = 1, 2,..., n
- mỗi công việc i ( 1 £ i £ n ) đƣợc biết di = B , t i = wi = ai , " i = 1, 2,..., n
- máy làm việc liên tục cho đến khi mọi công việc đƣợc xử lý xong.
- tại mỗi thời điểm máy chỉ xử lý đƣợc một công việc.
- khi đang xử lý công việc i, không đƣợc phép ngắt nó để thực hiện một công
việc khác.
19
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
Output: Hãy lập lịch để máy xử lý các công việc sao cho lƣợng tiền phạt là ít
nhất:
n
å
U i Wi là nhỏ nhất.
i= 1
Chứng minh:
Giải đƣợc bài toán phạt bằng thuật toán đơn định đa thức thì cũng giải đƣợc
KNAPSACK bằng thuật toán đơn định đa thức và ngƣợc lại.
Giả sử giải đƣợc bài toán phạt tức là lịch biểu mà
n
å
WiU i là nhỏ nhất, vậy thì:
i= 1
n
å
i= 1
n
WiU i =
å
ai - b
i= 1
20
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
- Xem thêm -