intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trường ĐH Văn Lang

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:79

Thêm vào BST
Báo xấu
30
lượt xem 7
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 Giới thiệu và đánh giá giải thuật, cung cấp cho người học những kiến thức như: một số nhóm giải thuật cơ bản; các vấn đề phân tích giải thuật; cấu trúc ngôn ngữ máy tính; giới thiệu phân tích giải thuật. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trường ĐH Văn Lang

  1. KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU & GIẢI (Data Structure and Algorithm) THUẬT CHƯƠNG 1: GIỚI THIỆU VÀ ĐÁNH GIÁ GIẢI THUẬT GVGD: HỌC KỲ I – NĂM HỌC 2020-2021 KHÓA 25T-IT
  2. 01. MỘT SỐ NHÓM GIẢI THUẬT CƠ BẢN 02. CÁC VẤN ĐỀ PHÂN TÍCH GIẢI THUẬT NỘI DUNG 03. CẤU TRÚC NGÔN NGỮ MÁY TÍNH 04. GIỚI THIỆU PHÂN TÍCH GIẢI THUẬT
  3. MỘT SỐ NHÓM GIẢI THUẬT PHỔ BIẾN 1. GIẢI THUẬT BRUTE FORCE ( VÉT CẠN) 2. GIẢI THUẬT CHIA ĐỂ TRỊ 3. GIẢI THUẬT QUY HOẠCH ĐỘNG 4. GIẢI THUẬT GREEDY ( THAM LAM) 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 5. GIẢI THUẬT HEURISTIC 6. GIẢI THUẬT XÁC SUẤT 3 KHOA CÔNG NGHỆ THÔNG TIN
  4. 1. GIẢI THUẬT BRUTE FORCE ( VÉT CẠN) • Giải thuật áp dụng giải quyết những vấn đề mang tính xâu chuỗi ( tăng dần) cần xem xét tất cả các trường hợp xảy ra. • Ví dụ: Tìm giá trị M trong một danh sách chưa có thứ tự L 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 4 KHOA CÔNG NGHỆ THÔNG TIN
  5. 1. GIẢI THUẬT BRUTE FORCE ( VÉT CẠN) • Ưu điểm lớn nhất của giải thuật này là đơn giản. • Dể dàng chứng minh sự đúng đắn: bằng cách phân tích hết không gian nghiệm, nên nếu tồn tại một đáp án thì chắc chắn giải thuật sẽ tìm thấy. • Thông thường trong thực tế giải thuật này thường được dùng để tìm giải 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com thuật hiệu quả hơn. • Cần bao nhiêu phép so sánh cần để tìm giá trị M trong danh sách L trong trường hợp xấu nhất? 5 KHOA CÔNG NGHỆ THÔNG TIN
  6. 2. GIẢI THUẬT CHIA ĐỂ TRỊ • Giải thuật chia để trị bao gồm: • Chia nhỏ vấn đề thành những vấn đề nhỏ giống nhau. • Tiếp tục tìm đáp án trong những không gian nhỏ. • Cuối cùng kết hợp các đáp án riêng lẻ thành một đáp án lớn cho vấn đề 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com chính. • Công cụ chính thường dùng cho giải pháp chia để trị là đệ quy: • Vấn đề chính được giảm thành một trường hợp cơ sở đơn giản nhất. • Một trường hợp cơ sở được giải quyết, sau đó những vấn đề đơn giản hơn có thể giải quyết. 6 KHOA CÔNG NGHỆ THÔNG TIN
  7. 2. GIẢI THUẬT CHIA ĐỂ TRỊ (ví dụ) • Hãy tìm một người tên N trong danh sách L được sắp xếp theo bảng chữ cái: • Giải thuật chia để trị sẽ thực hiện như sau: 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com • Nếu danh sách L chỉ có một phần tử sẽ được so sánh và trả về kết quả. • Còn lại chia danh sách thành hai phần LeftHalf và RightHalf. ▪ Nếu N lớn hơn phần tử cuối cùng của LeftHalf lặp lại quá trình với RightHalf. ▪ Còn lại thì lặp lại quá trình trên LeftHalf. 7 KHOA CÔNG NGHỆ THÔNG TIN
  8. 2. GIẢI THUẬT CHIA ĐỂ TRỊ (ví dụ) 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 8 KHOA CÔNG NGHỆ THÔNG TIN
  9. 3. GIẢI THUẬT QUY HOẠCH ĐỘNG • Giải thuật thực hiện như sau: ▪ Chia vấn đề thành những vấn đề con. ▪ Giải quyết các vấn đề con và nhớ kết quả của nó. ▪ Kết hợp thành đáp án cho vấn đề chính. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com • Giải thuật phù hợp với các bài toán cần sử dụng nhiều lần vấn đề con khi tính toán giải pháp cho vấn đề chính. 9 KHOA CÔNG NGHỆ THÔNG TIN
  10. 3. GIẢI THUẬT QUY HOẠCH ĐỘNG • Giải thuật thực hiện như sau: ▪ Chia vấn đề thành những vấn đề con. ▪ Giải quyết các vấn đề con và nhớ kết quả của nó. ▪ Kết hợp thành đáp án cho vấn đề chính. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com • Giải thuật phù hợp với các bài toán cần sử dụng nhiều lần vấn đề con khi tính toán giải pháp cho vấn đề chính. 10 KHOA CÔNG NGHỆ THÔNG TIN
  11. 3. GIẢI THUẬT QUY HOẠCH ĐỘNG tính số Fibonacci • Đầu tiên, nếu dùng giải thuật brute-force để tính toán chuỗi số Fibonacci, giá trị Fib(n) sẽ phụ thuộc vào tất cả giá trị phía trước Fib(n-1), Fib(n-2), Fib(n-3)… 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 11 KHOA CÔNG NGHỆ THÔNG TIN
  12. 3. GIẢI THUẬT QUY HOẠCH ĐỘNG tính số Fibonacci • Đối với trường hợp này chúng ta dùng giải thuật quy hoach động để nhớ các giá trị phụ. • Trước khi tính toán một giá trị, giải thuật kiểm 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com tra đáp án đã được ghi nhận (nhớ) chưa? • Nếu rồi sẽ dùng giá trị lưu, còn chưa sẽ tính toán và nhớ lại. 12 KHOA CÔNG NGHỆ THÔNG TIN
  13. 3. GIẢI THUẬT QUY HOẠCH ĐỘNG tính số Fibonacci • Việc nhớ yêu cầu dùng một cấu trúc dữ liệu giúp dễ dàng tìm kiếm. • Để nhận ra lợi ích từ việc ghi lại các giá trị và tra cứu các giá trị được tính toán trước, điều quan trọng là để các cấu trúc dữ liệu này hoạt động 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com hiệu quả • Việc lựa chọn cấu trúc dữ liệu sẽ tác động đến hiệu quả tổng thể của các giải pháp • Cấu trúc dữ liệu sẽ được đề cập sau trong phần môn học… 13 KHOA CÔNG NGHỆ THÔNG TIN
  14. 4. GIẢI THUẬT THAM LAM • Bài toán yêu cầu tìm kết quả tốt nhất từ một tập hợp các khả năng, ví dụ: tuyến đường rẻ nhất, khoảng cách ngắn nhất, số đồng xu ít nhất. • Chiến lược tham lam: Ở mỗi bước, hãy thực hiện lựa chọn tối ưu cục bộ và 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com hy vọng đạt được giải pháp tối ưu toàn cục. 14 KHOA CÔNG NGHỆ THÔNG TIN
  15. 4. GIẢI THUẬT THAM LAM • Vấn đề tối ưu hóa là một vấn đề mà đề bài cần tìm, nhưng không chỉ là một giải pháp mà còn là giải pháp khả thi tốt nhất. • Các thuật toán tham lam thường hoạt động đủ tốt để tối ưu hóa vấn đề. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com • Các thuật toán tham lam hoạt động bằng cách xác định giải pháp cho một vấn đề nhỏ trung gian • Bạn xác định giải pháp tốt nhất có thể cho vấn đề trung gian, không tính đến kết quả tương lai • Chiến lược là bằng cách chọn mức tối ưu cục bộ tại mỗi bước, để đạt được mức tối ưu toàn cục. 15 KHOA CÔNG NGHỆ THÔNG TIN
  16. 4. GIẢI THUẬT THAM LAM – ví dụ • Giả sử rằng chúng tôi muốn đổi một số số tiền thành số lượng tối thiểu đồng xu gồm penny (0.01USD), nickel(0.05USD), dime(0.1USD) và quarter(0.25USD) 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com • Chúng ta cần tìm A(Pennies) + B(Nickles) + C(Dimes) + D(Quarters) = số tiền cần đổi …như vậy tổng của : A+B+C+D là số đồng xu nhỏ nhất có thể. 16 KHOA CÔNG NGHỆ THÔNG TIN
  17. 4. GIẢI THUẬT THAM LAM – ví dụ • Chiến lược tham lam hoạt động như sau: • Bắt đầu với đồng quarter(0.25) và sử dụng càng nhiều xu càng tốt mà không vượt quá số tiền yêu cầu. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com • Nếu không đạt được tổng tiền, thì tiếp tục sử dụng càng nhiều xu dimes(.10) càng tốt mà không vượt quá số tiền yêu cầu. • Nếu không đạt được tổng số, thì tiếp tục sử dụng như nhiều xu niken (0.05) có thể mà không vượt quá số tiền yêu cầu. • Nếu không đạt được tổng số, thì tiếp tục sử dụng như nhiều xu penny (0.01) cần thiết để đạt được số tiền yêu cầu. 17 KHOA CÔNG NGHỆ THÔNG TIN
  18. 4. GIẢI THUẬT THAM LAM – ví dụ 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 18 KHOA CÔNG NGHỆ THÔNG TIN
  19. 4. GIẢI THUẬT THAM LAM – phân tích • Giải thuật có vấn đề thú vị như cần tối ưu hóa đủ cho hầu hết các trường hợp và vấn đề có thể giải quyết thông qua tối ưu hóa các bài toán con. • Dễ hiểu và dễ phát triển thuật toán khả thi. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com • Có thể khó để cho thấy nó hoạt động, khi nó hoạt động và tại sao nó hoạt động… • Bản chất của mọi bằng chứng thuật toán tham lam là để cho thấy rằng giải pháp tổng thể tốt nhất có thể là đạt được thông qua tối ưu hóa các vấn đề phụ 19 KHOA CÔNG NGHỆ THÔNG TIN
  20. 4. GIẢI THUẬT THAM LAM – phân tích • Trong một số trường hợp, các thuật toán tham lam sẽ không mang lại giải pháp tối ưu • Trong một số trường hợp, nó có thể mang lại câu trả lời chưa tốt. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com • Trong một số trường hợp, giải thuật không trả lời được. • Xét lại ví dụ trước, hãy tưởng tượng các xu chúng ta có là 0,25, 0,10 và 0,04 xu • Bằng trực giác, chúng ta có thể đổi được 0,41 xu tiền lẻ thành 1x 0,25 + 4x0,04 • Thuật toán tham lam sẽ thất bại hoàn toàn – cần đổi với 0,39 hoặc 0,43 xu, như nó sẽ đã cam kết sử dụng một xu 20 KHOA CÔNG NGHỆ THÔNG TIN
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2