Tìm tài liệu

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 InsertSort

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

Upload: gaconthuongme_xt

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

XEM TÀI LIỆU
Thiết kế và đánh giá thuật toán

Thiết kế và đánh giá thuật toán

Upload: conmummy

📎 Số trang: 122
👁 Lượt xem: 403
⬇ Lượt tải: 16

XEM TÀI LIỆU
Thiết Kế Và Đánh Giá Giải Thuật

Thiết Kế Và Đánh Giá Giải Thuật

Upload: dichthuatcongchungunitrans2010

📎 Số trang: 122
👁 Lượt xem: 381
⬇ Lượt tải: 16

XEM TÀI LIỆU
Thuật Toán Thuật Giải

Thuật Toán Thuật Giải

Upload: mrngocanh86

📎 Số trang: 98
👁 Lượt xem: 330
⬇ Lượt tải: 18

XEM TÀI LIỆU
Giáo Trình Thuật Toán Và Giải Thuật

Giáo Trình Thuật Toán Và Giải Thuật

Upload: ngoisaoden882002

📎
👁 Lượt xem: 412
⬇ Lượt tải: 17

XEM TÀI LIỆU
Thuật Toán Thuật Giải PRC

Thuật Toán Thuật Giải PRC

Upload: samacnong

📎 Số trang: 508
👁 Lượt xem: 379
⬇ Lượt tải: 16

XEM TÀI LIỆU
Thuật Toán Thuật Giải PDF

Thuật Toán Thuật Giải PDF

Upload: mhpham2006

📎 Số trang: 99
👁 Lượt xem: 307
⬇ Lượt tải: 18

XEM TÀI LIỆU
Giải thuật gen và một số bài toán về giải thuật gen

Giải thuật gen và một số bài toán về giải ...

Upload: lotusbk85

📎 Số trang: 109
👁 Lượt xem: 1047
⬇ Lượt tải: 16

XEM TÀI LIỆU
Các độ đo độ phức tạp phần mền

Các độ đo độ phức tạp phần mền

Upload: ngotuongvy

📎 Số trang: 64
👁 Lượt xem: 1209
⬇ Lượt tải: 16

XEM TÀI LIỆU
Bài tập lớn môn Trí tuệ nhân tạo : Giải thuật Heuristic và bài toán trò chơi

Bài tập lớn môn Trí tuệ nhân tạo : Giải ...

Upload: gocnhinsanco

📎 Số trang: 20
👁 Lượt xem: 4919
⬇ Lượt tải: 44

XEM TÀI LIỆU
Giải thuật và Lập trình

Giải thuật và Lập trình

Upload: buichithien

📎 Số trang: 316
👁 Lượt xem: 385
⬇ Lượt tải: 16

XEM TÀI LIỆU
Giải Thuật

Giải Thuật

Upload: themoon2183

📎
👁 Lượt xem: 395
⬇ Lượt tải: 16

XEM TÀI LIỆU

QUAN TÂM

Những tài liệu bạn đã xem

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: nduykhang

📎 Số trang: 0
👁 Lượt xem: 541
⬇ Lượt tải: 21

XEM TÀI LIỆU

CHUYÊN MỤC

Kỹ thuật - Công nghệ
Giải thuật và đánh giá độ phức tạp thuật toán 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 zip Đăng bởi
5 stars - 189048 reviews
Thông tin tài liệu 0 trang Đăng bởi: nduykhang - 07/02/2024 Ngôn ngữ: Việt nam, English
5 stars - "Tài liệu tốt" by , Written on 07/02/2024 Tôi thấy tài liệu này rất chất lượng, đã giúp ích cho tôi rất nhiều. Chia sẻ thông tin với tôi nếu bạn quan tâm đến tài liệu: Giải thuật và đánh giá độ phức tạp thuật toán