Bài giảng Thiết kế và đánh giá thuật toán

Chia sẻ: Trinh Van Giang | Ngày: | Loại File: PPT | Số trang:231

Thêm vào BST

Báo xấu

238
lượt xem 68
download

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

Thuật toán , còn gọi là giải thuật, là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán. Nói cách khác, thuật toán là một bộ các qui tắc hay qui trình cụ thể nhằm giải quyết một vấn đề trong một số bước hữu hạn, hoặc nhằm cung cấp một kết quả từ một...

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 Thiết kế và đánh giá thuật toán

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
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
Ví dụ: Chương 3: Phương pháp “tham lam” Giới thiệu chung I. Thuật toán trên đồ thị II. Cây bao trùm nhỏ nhất 1) Đường đi ngắn nhất 2) Thuật toán sắp xếp lịch làm việc III. Thuật toán “heurisitic” IV. Tô màu đồ thị 1) Người đưa hàng 2) 3
Sách tham khảo 4
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
Chương 1: Giới thiệu về thuật toán Khái niệm thuật toán I. Một số ví dụ II. Đánh giá thuật toán trong trường hợp III. xấu nhất và theo trung bình Về thuật toán hiệu quả IV. Một số bài toán cụ thể V. Cấu trúc dữ liệu VI. 6
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
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
Sắp xếp chèn vào 2 4 6 1 3 5 5 4 6 1 3 2 2 4 5 6 1 3 4 5 6 1 3 2 2 4 5 6 3 1 1 2 3 4 5 6 9
Thuật toán xếp chèn vào InsertionSort (A) { for j = 2 to length (A) do { k = A[j]; // chèn A[j] vào dãy đã sắp A[1..j1] j = j1; while i > 0 and A[i] > k do { A[i+1] = A[i]; I = i1; } A{i+1} = k; } } 10
Thuật toán xen kẽ (merge sort) 11
Sắp xếp xen kẽ MergeSort(A,p,r){ if p
Phân tích thuật toán MergeSort Đâ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
Đánh giá thuật toán Giải quyết một bài toán. Viết thuật toán Mô hình hóa Lập chương trình Vấn đề: Có nhiều thuật toán. Chọn thuật toán nào ? 14
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
Đá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 SelectSort (A){ for i=1 to n1 do { index = i; x = T[i]; for j= i+1 to n do { if T[j]
Ví dụ Hãy chạy thuật toán InsertionSort MergeSort Đố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
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
Ví dụ: dãy Fibonacci Dãy Fibonacci được định nghĩa: F(0) = 0, F(1) = 1, và F(n) = F(n1) + F(n2) với n > 1. Tìm thuật toán tính số Fibonacci thứ n. 19
Thuật toán thứ nhất và thứ hai fontion fib1(n){ if n