Giáo trình: "Thiết kế và đánh giá thuật tóan"

Chia sẻ: Buicao Quyen | Ngày: | Loại File: PPT | Số trang:231

0
618
lượt xem
307
download

Giáo trình: "Thiết kế và đánh giá thuật tóan"

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu Giáo trình "Thiết kế và đánh giá thuật tóan" bậc cao học khoa công nghệ thông tin dành cho các bạn đang theo học hay nghiên cứu chuyên đề về tóan học.

Chủ đề:
Lưu

Nội dung Text: Giáo trình: "Thiết kế và đánh giá thuật tóan"

  1. Thiết kế và đánh giá  thuật toán Cao học, khoa công nghệ thông tin Đại học quốc gia Hà nội. Phan Thị Hà Dương Viện Toán học.  phan.haduong@gmail.com 1
  2. Chương trình Chương 1: Giới thiệu về thuật toán Chương 2: Phân tích tính hiệu quả của thuật  toán  Chương 3: Phương pháp “tham lam” Chương 4: Phương pháp “chia để trị” Chương 5: Phương pháp qui hoạch động Chương 6: Thuật toán trên đồ thị Chương 7: Phương pháp xác suất Chương 8: Về độ phức tạp tính toán 2
  3. Ví dụ: Chương 3: Phương pháp  “tham lam” I. Giới thiệu chung II. Thuật toán trên đồ thị 1) Cây bao trùm nhỏ nhất 2) Đường đi ngắn nhất III. Thuật toán sắp xếp lịch làm việc IV. Thuật toán “heurisitic” 1) Tô màu đồ thị 2) Người đưa hàng 3
  4. Sách tham khảo 4
  5. Sách tham khảo 2. Algorithmique ­ conception et analyse G. Brassard and P.Bratley, Masson, Paris ,  1987 3. Data structure and algorithms A. Aho, J. Hopcroft and J. Ullman, Addison  Wesley Publishing Company 4. Lý thuyết độ phức tạp tính toán. Phan Đình Diệu. 5
  6. Chương 1: Giới thiệu về thuật  toán I. Khái niệm thuật toán II. Một số ví dụ III. Đánh giá thuật toán trong trường hợp  xấu nhất và theo trung bình IV. Về thuật toán hiệu quả V. Một số bài toán cụ thể VI. Cấu trúc dữ liệu  6
  7. Khái niệm về thuật toán Thuật toán: Quá trình tính toán Dữ kiện vào Một dãy các bước tính toán K utế rảq a Thuật toán sắp xếp Một dãy số ã ốy cưD xps ợđs ắ ế p 7
  8. Một số từ khóa if (điều kiện) then {…} else for (điều kiện) do {…} while (điều kiện) do {…} procedure (T, a, b) {…} function(A) {… return  r; } 8
  9. Sắp xếp chèn vào 1 2   4   6   1   3 2 5   4   6   1   3 2 4   5   6   1   3 1 4   5 6  1  3 2 2   4   5   6   3 1   2   3   4   5   6 9
  10. Thuật toán xếp chèn vào Insertion­Sort (A) { for j = 2 to length (A) do {  k = A[j]; // chèn A[j] vào dãy đã sắp A[1..j­1] j = j­1; while i > 0 and A[i] > k do { A[i+1] = A[i]; I = i­1; } A{i+1} = k; } } 10
  11. Thuật toán xen kẽ (merge sort) 11
  12. Sắp xếp xen kẽ Merge­Sort(A,p,r){ 1. if p 
  13. Phân tích thuật toán Merge­Sort Đây là một thuật toán chia để trị. Chia: bước 2:  θ(1) Trị: bước 3 và 4: 2T(n/2) Hợp lại: bước 5: θ(n) Tổng kết: T(n) =   θ(1) nếu n=1 2T(n/2) + θ(n) nếu n >1 13
  14. Đánh giá thuật toán Giải quyết một bài toán.  Mô hình hóa Viết thuật toán Lập chương trình Vấn đề: Có nhiều thuật toán. Chọn thuật toán nào ? 14
  15. Phương pháp đánh giá Phương pháp thực nghiệm: Lập trình, và thử trên các ví  dụ xem thuật toán nào nhanh. Phương pháp lý thuyết: Tính toán thời gian, bộ nhớ, …  cần thiết của mỗi thuât toán dựa theo độ lớn của dữ liệu  vào. Ưu điểm: ­ không phụ thuộc ngôn ngữ lập trình, loại máy  tính        ­ Biết được tính hiệu quả của thuật toán đối với  các dữ liệu có kích thước lớn. 15
  16. Đánh giá thuật toán trong trường  hợp xấu nhất và theo trung bình Ví dụ: Sắp xếp lựa chọn Select­Sort (A){ for i=1 to n­1 do { index = i; x = T[i]; for j= i+1 to n do { if T[j] 
  17. Ví dụ Hãy chạy thuật toán Insertion­Sort Merge­Sort Đối với các bảng sau : A = [3,1,4,1,5,9,2,6,5,3] B = [1,2,3,4,5,6] C = [6,5,4,3,2,1] 17
  18. Thời gian chạy trong trường hợp xấu nhất: là  cận trên đối với mọi dữ liệu vào. Thời gian chạy trung bình: thường khó phân  tích và đánh giá hơn. 18
  19. Ví dụ: dãy Fibonacci Dãy Fibonacci được định nghĩa: F(0) = 0, F(1) = 1, và F(n) = F(n­1) + F(n­2) với n > 1. Tìm thuật toán tính số Fibonacci thứ n. 19
  20. Thuật toán thứ nhất và thứ hai fontion fib1(n){ if n 
Đồng bộ tài khoản