Giai thuat va danh gia do phuc tap thuat toan

Giải thuật và đánh giá độ phức tạp thuật toán

Upload bởi: nduykhang

Mã tài liệu: 189048

Số trang: 0

Định dạng: zip

Dung lượng file:

Chuyên mục: Kỹ thuật - Công nghệ

Đến trang tải tài liệu này

Info

Thuật toán cho bài toán tối ưu hóa thường bao gồm một dãy các bước, với một tập các chọn lựa tại mỗi bước. Với nhiều bài toán tối ưu hóa, quả là quá thừa khi sử dụng qui hoạch động để xác định các chọn lựa tốt nhất, thay vì thế ta có thể sử dụng các thuật toán hiệu quả và đơn giản hơn. Trước hết, thuật toán tham lam luôn thực hiện các chọn lựa có vẻ tốt nhất. Nghĩa là nó thực hiện lựa chọn tối ưu cục bộvới hi vọng chọn lựa này sẽ dẫn đến một giải pháp tối ưu toàn cục. Trong chương này sẽ đưa ra sơ đồ chung thiết kế thuật toán tham lam và cách chứng minh tính đúng đắn của nó đồng thời đưa ra một số ví dụ điển hình cho việc thiết kế thuật toán tham lam.
Có nhiều bài toán tổng quát xuất hiện trong toán học rời rạc. Chẳng hạn tìm số lớn nhất trong một dãy số nguyên cho trước, liệt kê hết tất cả các tập hợp con của một tập hợp cho trước, xếp lại một dãy số nguyên theo thứ tự tăng dần hoặc giảm dần... Khi được giao một bài toán như vậy, thì trước hết chúng ta phải xây dựng một mô hình dịch bài toán đó sang ngữ cảnh toán học. Các cấu trúc được dùng trong những mô hình này chủ yếu là các cấu trúc tập hợp, dãy, hàm, hoán vị, tổ hợp ... và cấu trúc đồ thị là phần chúng ta sẽ học trong chương sau.
Lập được mô hình toán học thích hợp mới chỉ là bước bắt đầu của quá trình giải. Để hoàn tất quá trình này còn cần phải có một phương pháp sử dụng mô hình để đi tới lời giải. Bước này đòi hỏi phải thích hợp với công cụ máy tính chúng ta dùng. Cái đòi hỏi ở đây là những bước đi cụ thể theo đúng thủ tục đòi hỏi của máy tính và cấu trúc dữ liệu của ta để đi tới lời giải bài toán ban đầu. Một dãy các bước như vậy được gọi là thuật toán. Ta sẽ đưa ra cách mô tả thuật toán theo sơ đồ cũng như theo thuật ngữ lập trình.
Một vấn đề quan trọng của thuật toán là ta phải đánh giá và so sánh được các thuật toán với nhau. Nói chung tiêu chuẩn để đánh giá một thuật toán là tốt hay không chủ yếu dựa trên độ phức tạp của nó, tức là dựa trên số thời gian cần dùng để thực hiện nó. Trong phần sau, chúng ta sẽ đưa ra các bước cần thực hiện để đánh giá độ phức tạp của thuật toán. Khái niệm độ phức tạp này chưa phải là khái niệm dựa trên khái niệm chính xác về thuật toán xây dựng trên cơ sở máy tính Turing trừu tượng.

GỢI Ý

Những tài liệu gần giống với tài liệu bạn đang xem

So sánh độ phức tạp của thuật toán QuickSort ...

Upload: gaconthuongme_xt

📎 Số trang: 2
👁 Lượt xem: 872
⬇ Lượt tải: 18

Tìm tài liệu

Info

GỢI Ý

QUAN TÂM

CHUYÊN MỤC

KhoTri thức số

Về chúng tôi

MENU

LIÊN HỆ

098 333 9285