Bài toán NP

Xem 1-20 trên 20 kết quả Bài toán NP
  • Bài Giảng điện tử Phân tích và thiết kế giải thuật. Tiến sĩ Dương Tuấn Anh. Chương 6: Những bài toán NP đầy đủ. Đối với nhiều bài toán chúng ta có những giải thuật hữu hiệu để giải. Tuy nhiên, có rất nhiều bài toán khác không có giải thuật hữu hiệu để giải.

    pdf0p kieuphong21055 14-09-2010 149 63   Download

  • Lớp bài toán P (polynomial time) Lớp P là lớp bài toán quyết định giải được trong thời gian đa thức trên máy Turing tất định, hay lớp những bài toán dễ (có lời giải chấp nhận được). Lớp bài toán NP Là lớp bt quyết định giải được trong thời gian đa thức trên máy Turing không tất định

    ppt25p thedaigiapro 13-12-2012 73 13   Download

  • Chương 7 trình bày về vấn đề NP-đầy đủ. Các nội dung chính trong chương này gồm có: Giải thuật thời gian đa thức tất định và không tất định, vấn đề NP-đầy đủ, định lý Cook, một số bài toán NP-đầy đủ, một số kỹ thuật để đối phó với những bài toán NP-đầy đủ. Mời các bạn cùng tham khảo.

    ppt25p youcanletgo_01 04-01-2016 11 4   Download

  • Bài giảng Lý thuyết độ phức tạp - Chương 3: Chứng minh các kết quả của bài toán NP - Đầy đủ" cung cấp cho người đọc các kiến thức: Các khái niệm, các bài toán NP - Complete. Mời các bạn cùng tham khảo nội dung chi tiết.

    pdf21p doinhugiobay_18 08-03-2016 24 3   Download

  • Nhằm giúp các bạn có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu về Công nghệ thông tin, mời các bạn cùng tham "Bài giảng Phân tích thiết kế giải thuật - Chương 37: Giải thuật xấp xỉ" dưới đây. Nội dung bài giảng cung cấp cho các bạn những kiến thức về cách tiếp cận một bài toán NP-đầy đủ, bài toán che phủ đỉnh, giải thuật xấp xỉ, ... Hy vọng đây là tài liệu tham khảo hữu ích cho các bạn.

    ppt21p gaudinh2015 27-11-2015 23 2   Download

  • Tham khảo tài liệu 'các bài toán np – khó và np - đầy đủ', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

    doc14p vuthithuy11a 26-11-2011 136 43   Download

  • Giải thuật thời gian đa thức tất định và không tất định...

    pdf0p lqtien 29-08-2011 69 16   Download

  • Chương này đề cập đến giải thuật xấp xỉ. Những nội dung chính trong bài giảng gồm có: Các khái niệm P, NP, NP-complete; giải thuật xấp xỉ với hệ số xấp xỉ; minh họa với các bài toán phủ đỉnh, TSP, chu trình Hamilton. Mời các bạn tham khảo.

    pdf55p tangtuy12 02-06-2016 13 1   Download

  • Bài viết Về độ phức tạp tính toán của một bài toán liên quan đến tập rút gọn trên bảng quyết định trình bày về một bài toán co-NP - đầy đủ liên quan đến các tập rút gọn trên bảng quyết định. Chúng ta gọi A là tập tựa rút gọn trên bảng quyết định DS với tập thuộc tính C U {d} và d là thuộc tính quyết định nếu A chứa một tập rút gọn nào đó.

    pdf5p maiyeumaiyeu26 23-12-2016 5 1   Download

  • Nội dung bài giảng: 1. Giải thuật thời gian đa thức tất định và không tất định 2. Vấn đề NP-đầy đủ 3. Định lý Cook 4. Một số bài toán NP-đầy đủ 5. Một số kỹ thuật để đối phó với những bài toán NP-đầy đủ

    ppt25p lucky156 04-06-2010 150 66   Download

  • Bài giảng "Lý thuyết độ phức tạp: Lý thuyết NP - Đầy đủ" trình bày các nội dung: Bài toán quyết định, ngôn ngữ và lược đồ mã hóa, máy Turing tất định và lớp P, tính toán không tất định và lớp NP, mối quan hệ giữa lớp P và lớp NP,... Mời các bạn cùng tham khảo nội dung chi tiết.

    pdf41p doinhugiobay_18 08-03-2016 33 22   Download

  • Bài giảng "Lý thuyết độ phức tạp: Lý thuyết NP - Đầy đủ" cung cấp cho người đọc các kiến thức: Xác định 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ời gian đa thức và những bài toán không giải được,... Mời các bạn cùng tham khảo.

    pdf23p doinhugiobay_18 08-03-2016 30 8   Download

  • Bài toán tìm cây khung chi phí định tuyến nhỏ nhất (Minimum Routing Cost Spanning Tree - MRCST) có thể được tìm thấy trong nhiều bài toán thiết kế mạng. Trong trường hợp tổng quát, bài toán MRCST đã được chứng minh là NP- khó. Bài báo này đề xuất thuật toán giải bài toán MRCST được phát triển dựa trên sơ đồ thuật toán bầy ong.

    pdf12p binhminhmuatrenngondoithonggio 09-06-2017 17 3   Download

  • Mời các bạn cùng tham khảo "Bài giảng Phân tích thiết kế giải thuật - Chương 12: NP-Đầy Đủ" để nắm bắt được những nội dung về khái niệm cơ bản NP-Đầy Đủ, hình thức hóa khái niệm bài toán, bài toán trừu tượng, bài toán quyết định, bài toán tối ưu, mã hóa.

    ppt48p gaudinh2015 27-11-2015 5 1   Download

  • Bài toán quyết định (Decision Problem - DP) là bài toán chỉ có câu trả lời là có hoặc không (hay còn gọi là trả lời nhị phân). Mỗi thể hiện của bài toán nghĩa là mỗi trường hợp cá biệt của bài toán có một trả lời. Một bài toán quyết định Π đơn giản bao gồm một tập hợp DΠ các thể hiện và tập con YΠ Í DΠ là các thể hiện đúng.Một bài toán quyết định phát biểu dưới dạng: Instance: … Question:…...

    ppt0p thedaigiapro 13-12-2012 161 60   Download

  • Rút gọn thuộc tính là một bài toán quan trọng trong lý thuyết tập thô. Bài toán tìm rút gon tối thiểu của một hệ thống thông tin nói chung, và bài toán rút gọn của một hệ thống thông tin không đầy đủ nói riêng là một bài toán NP -khó. Lý do chính là do s tổ hợp các thuộc tính. ự Trong bài báo này, chúng tôi ề xuất một thuật toán rút gọn tập thuộc tính. Thuật toán là sự đ phát triển các kết quả của Cheng Degang và cộng sự trong hệ quyết định...

    pdf6p phalinh17 13-08-2011 72 17   Download

  • Những bài toán NP đầy đủ-Đối với nhiều bài toán chúng ta có những giải thuật hữu hiệu để giải, tuy nhiên, có rất nhiều bài toán khác không có giải thuật hữu hiệu để giải

    pdf0p augi16 13-02-2012 36 12   Download

  • Bài báo này nghiên cứu về bài toán định tuyến đa điểm (multicast) cho mạng cảm biến không dây nhiệm vụ tuần hoàn (DC-WSN). Đặc điểm của loại mạng cảm biến không dây này là các nút cảm biến hoạt động tuần hoàn theo chu kỳ và không bắt buộc phải hoạt động liên tục. Bài toán này đã được chứng minh thuộc lớp NP-khó.

    pdf14p dieutringuyen 07-06-2017 6 2   Download

  • Dạng 3: Chứng minh ba điểm thẳng hàng: BÀI TOÁN 3: Cho tam giác ABC nội tiếp trong một đường tròn (O). M ; N ; P lần lượt là cá điểm chính giữa các cung nhỏ AB ; BC ; CA . MN và NP cắt AB và AC theo thứ tự ở R và S. Chứng minh rằng: RS // BC và RS đi qua tâm của đường tròn nội tiếp tam giác ABC. Cách giải 1: (Hình 1) Gợi ý: Đây là một bài toán hình tương đối khó đối với học sinh nếu không có tư duy...

    pdf6p paradise10 29-12-2011 316 59   Download

  • Bài toán mượn/ khoá kênh tần số mạng di động tế bào là bài toán thuộc loại NP-Hard. Trong mạng di động tế bào, tỉ số cuộc gọi tới, thời gian thực hiện cuộc gọi và truyền thông overhead giữa BS và MCS là không tõ ràng và xác định. Một phương pháp điều khiển mượn kênh tần số thông minh trong mạng di động tế bào trên cơ sở hệ mờ-Nơ ron

    pdf11p tuanlocmuido 13-12-2012 28 7   Download

Đồng bộ tài khoản