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

Bài giảng Cơ sở dữ liệu giải thuật: Bài 11 - Thiết kế thuật toán

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

74
lượt xem
3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cơ sở dữ liệu giải thuật: Bài 11 - Thiết kế thuật toán làm rõ các chiến lược thiết kế thuật toán, thuật toán tiêu biểu, quy hoạch động, cấu trúc chung của phương pháp quy hoạch động, bài toán ba lô.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Cơ sở dữ liệu giải thuật: Bài 11 - Thiết kế thuật toán

Bài 11: Thi t k thu t toán<br /> Gi ng viên: Hoàng Th i p<br /> Khoa Công ngh Thông tin –<br /> i h c Công Ngh<br /> <br /> Các chi n lư c thi t k thu t toán<br /> •<br /> <br /> Chia-<br /> <br /> -tr (Divide-and-conquer)<br /> <br /> •<br /> <br /> – Chia bài toán thành các bài toán<br /> kích thư c nh có th gi i quy t<br /> c l p. Sau ó k t h p nghi m<br /> các bài toán kích thư c nh thành<br /> nghi m bài toán g c<br /> – Thu t toán<br /> quy<br /> <br /> •<br /> <br /> Quy ho ch ng (Dynamic<br /> programming)<br /> – Gi i bài toán l n d a vào k t qu<br /> bài toán con. Tránh l p l i vi c<br /> gi i cùng m t bài toán con b ng<br /> cách lưu nghi m các bài toán con<br /> trong m t b ng<br /> – Thu t toán l p<br /> <br /> diepht@vnu<br /> <br /> Tham ăn (Greedy method)<br /> – Th c hi n t ng bư c m t. T i m i<br /> bư c, ch n phương án ư c xem<br /> là t t lúc ó.<br /> – Không ph i t t c các thu t toán<br /> tham ăn u cho k t qu t i ưu<br /> toàn c c<br /> <br /> •<br /> <br /> Các chi n lư c khác<br /> – Quay lui<br /> – Thu t toán ng u nhiên<br /> <br /> 2<br /> <br /> Thu t toán tiêu bi u<br /> • Chia-<br /> <br /> -tr<br /> <br /> – Tìm ki m nh phân (binary<br /> search)<br /> – S p x p tr n (merge sort)<br /> – S p x p nhanh (quick sort)<br /> <br /> • Quy ho ch<br /> <br /> ng<br /> <br /> – Tìm dãy con tăng dài nh t<br /> (longest increasing<br /> subsequence)<br /> – Bài toán ba lô<br /> (backpacker/knapsack)<br /> – Bài toán ngư i bán hàng<br /> (traveling salesman)<br /> <br /> diepht@vnu<br /> <br /> – Tìm dãy con chung c a hai<br /> dãy s (longest common<br /> subsequence)<br /> <br /> • Tham ăn<br /> – Xây d ng mã Huffman<br /> (Huffman encoding)<br /> – Tìm cây bao trùm nh nh t<br /> (minimum spanning tree)<br /> <br /> 3<br /> <br /> 1. Fibonacci(n)<br /> <br /> diepht@vnu<br /> <br /> 4<br /> <br /> Tìm s Fibonacci th n<br /> •<br /> •<br /> <br /> Algorithm Fib(n)<br /> Input n<br /> Output s Fibonacci th n<br /> if n = 0 then return 0<br /> else if n = 1 then return 1<br /> else<br /> return Fib(n – 2) + Fib(n – 1)<br /> <br /> Fn= Fn-1+ Fn-2<br /> F0 =0, F1 =1<br /> – 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …<br /> <br /> •<br /> <br /> quy<br /> <br /> Th t c tính<br /> quy tr c ti p<br /> th c hi n ch m do tính l p<br /> nhi u l n.<br /> <br /> F(6) = 8<br /> F(5)<br /> <br /> F(4)<br /> <br /> F(4)<br /> F(3)<br /> F(2)<br /> F(1)<br /> diepht@vnu<br /> <br /> F(3)<br /> F(2)<br /> <br /> F(1) F(1)<br /> <br /> F(3)<br /> <br /> F(2) F(1)<br /> <br /> F(0) F(1)<br /> <br /> F(0)<br /> <br /> F(2)<br /> F(1)<br /> <br /> F(2)<br /> <br /> F(1) F(1)<br /> <br /> F(0)<br /> <br /> F(0)<br /> <br /> F(0)<br /> 5<br /> <br />
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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