Luận Văn Thạc Sĩ Hiệu Suất Của Thuật Toán Xấp Xỉ Đối Với Một Số Bài Toán Tối Ưu Trên Đồ Thị

Hiệu Suất Của Thuật Toán Xấp Xỉ Đối Với Một Số Bài Toán Tối Ưu Trên Đồ Thị​

Các bài toán tối ưu có nhiều ứng dụng trong lý thuyết và thực tế như trong quy hoạch tuyến tính, toán học, logic. . . Khi nghiên cứu những bài toán tối ưu, ta mong muốn tìm được nghiệm tối ưu trong thời gian đa thức. Tuy nhiên, nhiều bài toán tối ưu quan trọng thuộc lớp NP-khó. Đối với những bài toán này, ta không hi vọng có thuật toán tìm nghiệm tối ưu trong thời gian đa thức, trừ phi P = NP. Vì vậy, mục tiêu đưa ra là tìm được nghiệm càng gần tối ưu càng tốt trong thời gian đa thức. Để đạt được điều này, người ta thường sử dụng thuật toán xấp xỉ. Để đánh giá hiệu suất của thuật toán xấp xỉ, ta thường xem xét hiệu suất trong trường hợp xấu nhất hoặc trong hầu hết mọi trường hợp. Hiệu suất trong trường hợp xấu nhất cũng chính là hiệu suất trong mọi trường hợp của bài toán. Hiệu suất này được gọi là hiệu suất tuyệt đối. Hiệu suất được xem xét trong hầu hết mọi trường hợp cho ta thông tin về hiệu suất đảm bảo đối với thuật toán xấp xỉ.

• Luận văn thạc sĩ Toán học
• Chuyên ngành Toán ứng dụng
• Người hướng dẫn khoa học: TS. Trần Vĩnh Đức
• Tác giả: Nguyễn Thị Hồng Hạnh
• Số trang: 57
  
• Kiểu file: PDF
• Ngôn ngữ: Tiếng Việt
• Đại học sư phạm Hà Nội 2 2017

Link Download
http://thuvien.hpu2.edu.vn/index.php?language=vi&nv=tailieu&op=Triet-hoc/Aristote-13668
https://drive.google.com/drive/folders/1yLBzZ1rSQoNjmWeJTM6cEZ3WGQHg04L1