Bài giảng NP - Complete trình bày một số bài toán tối ưu rời rạc; lớp P; lớp NP; NP-đầy đủ; bài toán CNF-SAT. Để nắm chi tiết nội dung nghiên cứu mời các bạn cùng tham khảo bài giảng. | NP - Complete Một số bài toán tối ưu rời rạc Bài toán người du lịch Cho n điểm trên mặt phẳng thành phố giữa hai thành phố bất kỳ được xác định một thông số là chi phí đi lại. Một hành trình là một cách đi xuất phát từ một thành phố nào đó qua n thành phố và quay về nơi xuất phát. OP Optimization Problem Tìm hành trình có tổng chi phí bé nhất. DP Decision Problem Có tồn tại một hành trình với chi phí D 2013-11-25 2 Một số bài toán tối ưu rời rạc Bài toán tô màu đồ thị Cho đồ thị G V E . OP Số màu ít nhất để tô đồ thị G DP Cho số nguyên K. Có tồn tại hay không cách tô màu đồ thị G với số màu không quá K Một cách tô màu đồ thị là một phương án gán cho mỗi đỉnh một màu sao cho hai đỉnh liền kề có hai màu khác nhau. 2013-11-25 3 Một số bài toán tối ưu rời rạc Bài toán cái túi Cho n đồ vật với kích thước là các số nguyên s1 s2 . sn và các túi với kích thức là số nguyên T. OP Tìm số túi ít nhất để xếp các đồ vật. DP Cho số nguyên K. Có tồn tại cách xếp các đồ vật vào không quá K túi với sức chứa T 2013-11-25 4 Một số bài toán tối ưu rời rạc Bài toán tập con Cho số nguyên dương T và tập X gồm n số nguyên dương a1 a2 . an. OP Xác định tập con của X sao cho tổng của chúng gần nhất và không quá T. DP Có tồn tại tập con sao cho tổng kích thước đúng bằng T. 2013-11-25 5 Một số bài toán tối ưu rời rạc Bài toán phân công công việc Giả thiết có n công việc Mỗi thời điểm chỉ thực hiện một công việc Thời gian thực hiện t1 t2 . tn Thời hạn hoàn thành d1 d2 . dn tính từ khi bắt đầu công việc đầu tiên Mức phạt đối với mỗi công việc bị chậm là p1 p2 . pn. Phân công công việc là một hoán vị của tập J 1 2 . n J 1 J 2 . J n . Tổng giá trị phạt của phân công n P if t 1 . t j d j then p j else 0 j 1 OP Tìm lịch sắp xếp công việc có giá trị hàm phạt thấp nhất P min. DP Cho trước k xác định lịch có mức phạt không quá k P k. 2013-11-25 6 Lớp P Thuật toán có độ phức tạp O f n nếu với mọi bộ số liệu có độ dài n số phép tính phải thực hiện không quá C f n với C gt 0. Thuật toán có độ phức tạp O
