Giáo trình: "Thiết kế và đánh giá thuật tóan"
lượt xem 317
download
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.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Giáo trình: "Thiết kế và đánh giá thuật tóan"
- 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” 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
- 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 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
- 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 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
- 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){ 1. 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. 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
- 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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo trình Kỹ thuật dạy Sinh học: Phần 1 - TS. Phan Đức Duy
30 p | 295 | 58
-
thiết kế và đánh giá thuật toán - trần tuấn minh -6
16 p | 163 | 47
-
Giáo trình Kỹ thuật dạy Sinh học: Phần 2 - TS. Phan Đức Duy
78 p | 188 | 46
-
thiết kế và đánh giá thuật toán - trần tuấn minh -3
16 p | 155 | 26
-
thiết kế và đánh giá thuật toán - trần tuấn minh -7
16 p | 97 | 19
-
thiết kế và đánh giá thuật toán - trần tuấn minh -2
16 p | 105 | 14
-
thiết kế và đánh giá thuật toán - trần tuấn minh -5
16 p | 93 | 9
-
thiết kế và đánh giá thuật toán - trần tuấn minh -1
16 p | 68 | 8
-
thiết kế và đánh giá thuật toán - trần tuấn minh -8
10 p | 88 | 8
-
Giáo trình phân tích khả năng ứng dụng nguyên lý mạch dao động dùng cổng logic p4
11 p | 68 | 6
-
Giáo trình phân tích mối quan hệ giữa đường kính mặt nhận nhiệt và thời gian được biểu diễn trên đồ thị quan hệ p1
5 p | 83 | 6
-
Giáo trình hướng dẫn chuyển đổi tuyến tính của một hàm liên thuộc có dạng tuyến tính từng đoạn p4
9 p | 74 | 5
-
Giáo trình phân tích khả năng phát triển thiết kế theo đường cong chuyển tiếp của lực ly tâm p1
5 p | 71 | 3
-
Giáo trình phân tích quy trình tổng quan mối quan hệ giữa đường kính và thời gian đồ thị quan hệ p1
5 p | 66 | 3
-
Thiết kế và sử dụng Rubrics làm công cụ đánh giá trong quá trình dạy học Toán ở trường trung học phổ thông
6 p | 41 | 3
-
Quy trình thiết kế đánh giá thực trong dạy học môn Toán theo hướng phát triển năng lực cho học sinh tiểu học
5 p | 22 | 3
-
Một số phim tư liệu hỗ trợ dạy học môn Tự nhiên & Xã hội với chủ đề thực vật và động vật: Từ quy trình thiết kế đến thực nghiệm sư phạm
9 p | 24 | 2
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