Tài liệu Lý thuyết lập lịch và ứng dụng giải pháp quyết bài toán lập lịch cho cpu

ĐẠ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