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

Bài giảng Phân tích và thiết kế thuật giải: Bài 2 - TS. Ngô Quốc Việt

Chia sẻ: You Can | Ngày: | Loại File: PDF | Số trang:34

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

Bài 2 trang bị cho người học những kiến thức chiến lược chia để trị. Các nội dung trình bày trong chương này gồm có: MergeSort, tập con có tổng lớn nhất, nhân 2 số nguyên lớn, tìm cặp điểm gần nhất, thuật giải Strassen - Nhân hai ma trận,... 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 Phân tích và thiết kế thuật giải: Bài 2 - TS. Ngô Quốc Việt

  1. PHÂN TÍCH THIẾT KẾ THUẬT GIẢI CHIẾN LƯỢC CHIA ĐỂ TRỊ TS. NGÔ QUỐC VIỆT 2015
  2. Nội dung 1. Giới thiệu 2. Các thuật giải chia để trị 3. Bài tập 4. Hỏi đáp. 2 Ngô Quốc Việt
  3. Giới thiệu  Chia bài toán lớn thành 2 hay nhiều “phần” nhỏ  Giải quyết mỗi phần theo cách đệ quy.  Kết hợp các lời giải “con” để tạo thành lời giải sau cùng.  Thuật giải có tối thiểu hai gọi hàm đệ quy được gọi là chia để trị. Ví dụ: thuật giải mergesort.  Các thuật giải: tính số Fibonacii theo đệ quy (có hai lời gọi đệ quy) nhưng không là chia để trị vì không có bước ‘chia’. 3 Ngô Quốc Việt
  4. Giới thiệu  MergeSort  Tập con có tổng lớn nhất  Nhân 2 số nguyên lớn  Tìm cặp điểm gần nhất  Thuật giải Strassen - Nhân hai ma trận 4 Ngô Quốc Việt
  5. Giới thiệu  Chiến lược phổ biến là chia đôi tập dữ liệu n phần tử thành hai tập con kích thước ½ n.  Giải quyết mỗi phần theo đệ quy  Kết hai lời giải con thành lời giải tổng quát với độ phức tạp tuyến tính.  Vét cạn: O(n2)  Chia để trị: O(n.log(n)). 5 Ngô Quốc Việt
  6. Minh hoạ với MergeSort  𝑇(𝑛) là số phép so sánh trong mergesort T (n)  O(n log n) 6 Ngô Quốc Việt
  7. Minh hoạ với MergeSort  Dễ dàng chứng minh với cây đệ quy 7 Ngô Quốc Việt
  8. Minh hoạ với MergeSort  Chứng minh bằng quy nạp theo n.  Đúng với n = 1.  Giả sử: T (n)  n log2 n  Chứng minh: T (2n)  O(2n log2 2n) T (2n)  2T (n)  2n  2n log2 (n)  2n  2n(log2 (2n) 1)  2n  2n log2 (2n) 8 Ngô Quốc Việt
  9. Minh hoạ với MergeSort  Chứng minh bằng quy nạp theo n.  Đúng với n = 1.  Định nghĩa:  Giả sử đúng với: 1, 2, …, n-1. n1  n / 2; n2  n / 2 9 Ngô Quốc Việt
  10. Bài toán đếm nghịch thế  Yêu cầu cơ bản: đếm nghịch thế trong một dãy.  Yêu cầu nâng cao: đếm sự khác biệt (nghịch thế) giữa hai dãy. Nguyên nhân vì khái niệm “tăng” / ”giảm” do chủ quan.  Thuật giải vét cạn: so sánh từng cặp (hãy trình bày thuật giải) T ( n)  O ( n 2 ) 10 Ngô Quốc Việt
  11. Bài toán đếm nghịch thế  Chia để trị:  Chia thành 2 dãy con.  Đếm đệ quy trong từng dãy con.  Kết hợp: tổng nghịch thế của hai dãy con 11 Ngô Quốc Việt
  12. Bài toán đếm nghịch thế 12 Ngô Quốc Việt
  13. Bài toán đếm nghịch thế  Đếm nghịch thế giữa hai nửa đã được sắp xếp. T (n)  T n / 2  T n / 2  O(n)  T (n)  O(n log n) 13 Ngô Quốc Việt
  14. Bài toán đếm nghịch thế  Cài đặt 14 Ngô Quốc Việt
  15. Bài toán Subset Sum Recursive Cho mảng n phần tử, tìm mảng con các phần tử liên tục sao cho tổng của chúng là lớn nhất (hoặc bằng giá trị T cho trước)  Vét cạn: hai vòng lặp. Vòng lặp ngoài: lấy phần tử đầu, vòng lặp trong: tìm maximum các tổng giữa phần tử đầu của vòng lặp ngoài và các phần tử của lặp trong. Độ phức tạp: 𝑂 𝑛2 .  Chia để trị: độ phức tạp 𝑂 𝑛𝑙𝑜𝑔𝑛  Chia mảng thành hai nửa  Tìm Maximum subarray sum của nửa trái  Tìm Maximum subarray sum của nửa phải  Tìm Maximum subarray sum của subarray giao giữa hai nửa, tính từ chỗ chia 15 Ngô Quốc Việt
  16. Bài toán tìm cặp điểm gần nhất  Cho n điểm trong mặt phẳng, tìm cặp điểm có khoảng cách ngắn nhất so với các cặp khác.  Giải pháp vét cạn: kiểm tra khoảng cách mọi cặp điểm p và q  𝑂(𝑛2).  Giải pháp 1: chia mặt phẳng thành 4 vùng bằng nhau  không đều. 16 Ngô Quốc Việt
  17. Bài toán tìm cặp điểm gần nhất  Chia: tập điểm thành hai nửa S1,S2 sao cho số điểm hai bên bằng nhau.  Trị: Tìm cặp gần nhất trong mỗi nửa.  Kết hợp: tìm cặp gần nhất, mỗi điểm thuộc nửa khác nhau  Vấn đề: cặp gần nhất là một điểm thuộc S1 và điểm thuộc S2  vét cạn mọi cặp có thể  𝑛 𝑛 𝑂 .𝑂 = 𝑂(𝑛2 ) 2 2 17 Ngô Quốc Việt
  18. Bài toán tìm cặp điểm gần nhất  Chia tập S thành S1 và S2 dựa trên đường thẳng dọc có hoành độ tại x trung bình.  Tìm đệ quy cặp gần nhất trên S1 và S2.  Giả sử *𝑝1 , 𝑝2 + là cặp gần nhất trong S1 và 𝑞, 𝑞2 trong S2.  Đặt 1 = 𝐷(𝑝1 , 𝑝2 ) và 2 = 𝐷(𝑞1 , 𝑞2 )  Đặt  = min(1 , ) l S1 S2 p1 1 p2 q1 q2 2 18 Ngô Quốc Việt
  19. Bài toán tìm cặp điểm gần nhất  Cải tiến: chỉ xét cặp điểm có khoảng cách nhỏ hơn  = 𝑀𝐼𝑁 của hai cặp điểm đã xét.  Chỉ xét các điểm nằm cách đường L (phân chia) ít hơn  = 𝑀𝐼𝑁. Xét theo tung độ Y.  Sắp tăng dần các điểm thoả đk trên theo tung độ Khoảng cách MIN trong ví dụ này là 12 19 Ngô Quốc Việt
  20. Bài toán tìm cặp điểm gần nhất  Sắp xếp các điểm trong dải có kích thước 2 tăng dần theo tung độ Y. Với =min(12,21). Nhận xét: gọi si là điểm trong dải 2 có khoảng cách i đến đường L. Nếu i j  Thì, khoảng cách giữa si, sj cũng lớn hơn . 20 Ngô Quốc Việt
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
5=>2