Bài giảng Phân tích thiết kế giải thuật: Chương 1 - Trịnh Huy Hoàng

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

Thêm vào BST

Báo xấu

120
lượt xem 8
download

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

Mời các bạn tham khảo bài giảng Phân tích thiết kế giải thuật: Chương 1 do Trịnh Huy Hoàng biên soạn sau đây để bổ sung thêm kiến thức về các phương pháp phân tích thuật toán. Bài giảng phục vụ cho các bạn chuyên ngành Công nghệ thông tin và những bạn quan tâm tới lĩnh vực này.

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 thiết kế giải thuật: Chương 1 - Trịnh Huy Hoàng

Chương 1: Các phương pháp phân tích thuật toán Trịnh Huy Hoàng Khoa Công nghệ thông tin Đại học Sư phạm TPHCM 1
Nội dung  Một số kiến thức Toán cần thiết  Thuật toán là gì?  Vai trò của phân tích thuật toán  Các phương pháp phân tích thuật toán  Bộ khung cho quá trình phân tích thuật toán – Mã giả – RAM – Thời gian thực hiện chương trình – Độ phức tạp của chương trình 2
Một số kỹ thuật Toán học thường dùng  Chứng minh qui nạp – Chứng minh mệnh đề đúng với trường hợp đầu tiên (n=n0) – Giả sử mệnh đề đúng đến trường hợp thứ k (n=k) – Chứng minh mệnh đề đúng với trường hợp thứ k+1 (n=k+1) – Kết luận mệnh đề đúng với mọi trường hợp (mọi n >= n0) 3
Một số kỹ thuật Toán học thường dùng (tt)  Các tổng dãy số thường dùng n n(n 1) Dãy số học i n (n 1) (n 2) ... 2 1 0 i 0 2 n xn 1 1 Dãy hình học xi if x 1 i 0 x 1 i 1 x if |x|
Thuật toán là gì?  “Thuật toán là một thủ tục tính toán được định nghĩa rõ ràng để biến đổi các đầu vào thành các đầu ra nhằm đạt được quan hệ đầu vào – đầu ra mong muốn” Input Algorithm Output  Ví dụ: input: Dãy số. output: Dãy số đã được sắp xếp thứ tự. 5
Thuật toán là gì? (tt)  “Nếu cho trước một bài toán, thì một cách giải bài toán được phân định ra thành một số hữu hạn bước, có kết thúc cuối cùng và đạt được kết quả mong muốn gọi là thuật toán” (Vũ Đức Thi, 1999) 6
Vai trò của việc phân tích thuật toán  Phân tích thuật toán = Xác định các đặc trưng liên quan đến hiệu năng. (Dự đoán tài nguyên được yêu cầu.) – Thời gian, bộ nhớ, đường truyền … – Thời gian thi hành (running time) là quan tâm chính bởi nó là tài nguyên quan trọng nhất và không thể phục hồi.  Tại sao phải phân tích thuật toán? – Chọn cách hiệu quả nhất trong số các thuật toán có thể có cho cùng một vấn đề. – Liệu một giải pháp tốt nhất có thời gian thi hành chấp nhận được trong thực tế hay không? – Liệu một thuật toán đã được tối ưu hay chưa? – Liệu có một thuật toán nào khác tốt hơn không? 7
Phân tích thực nghiệm  Dựa trên thời gian thực thi của thuật toán đã được cài đặt trên các đầu vào cụ thể.  Phụ thuộc vào môi trường phần cứng (vi xử lý, xung nhịp đồng hồ, RAM, đĩa cứng,…) và phần mềm (hệ điều hành, ngôn ngữ lập trình, biên dịch hoặc thông dịch,…) 8
Phân tích thực nghiệm (tt)  Hạn chế: – Các thực nghiệm chỉ được tiến hành trên một số các đầu vào để kiểm tra. Chúng cần phải có tính đại diện cao. – Rất khó để so sánh tính hiệu quả của hai thuật toán trừ khi chúng chạy trên cùng một môi trường phần cứng và phần mềm. – Cần phải cài đặt và thi hành thuật toán 9
Ý tưởng  Có một bộ khung phân tích thỏa – Xem xét tất cả đầu vào có thể – Cho phép đánh giá hiệu quả tương đối của hai thuật toán bất kỳ độc lập với môi trường phần cứng và phần mềm – Có thể được tiến hành bằng cách nghiên cứu mô tả cấp cao của thuật toán mà không cần phải thật sự cài đặt và thi hành thuật toán đó 10
Mục tiêu  Liên kết mỗi thuật toán với một hàm f(n) để đặc trưng thời gian thực thi của thuật toán đó với n là kích thước đầu vào.  Cũng là mục tiêu của môn học 11
Các thành phần của bộ khung  Một ngôn ngữ: để mô tả các thuật toán  Một máy tính: để thi hành các mô tả thuật toán bởi ngôn ngữ ở trên  Một độ đo: để biểu đạt thời gian thực thi của bản mô tả thuật toán trên máy tính 12
Ngôn ngữ: ngôn ngữ mã giả  Mô tả thuật toán ở cấp cao để người đọc có thể hiểu đồng thời rõ ràng cô đọng súc tích.  Dựa trên các cấu thành chung của ngôn ngữ C, C++, Java. 13
Cấu thành của mã giả  Biểu thức: – kí hiệu toán học chuẩn – phép gán là “←” – so sánh bằng là “=“.  Khai báo hàm: – Algorithm Tên_Thuật_Toán(tham số 1, tham số 2,…)  Cấu trúc điều kiện: – If điều_kiện then Các hành động 14
Cấu thành của mã giả (tt)  Vòng lặp while: – While điều_kiện do Các hành động  Vòng lặp repeat: – Repeat Các hành động – Until điều_kiện  Vòng lặp for – For định_nghĩa_biến_tăng do Các hành động 15
Cấu thành của mã giả (tt)  Truy xuất mảng: – A[i]: phần tử thứ i của mảng A. Bắt đầu từ 0. – Lưu ý phần tử đầu tiên của mảng có nghĩa là phần tử 1.  Gọi hàm: – tên_hàm(các_tham_số)  Kết thúc hàm: – Return giá_trị: trả về giá trị cho hàm gọi hàm này 16
Ví dụ: Tìm phần tử lớn nhất của mảng  Algorithm arrayMax(A, n):  Input: Một mảng A lưu n >=1 số nguyên  Output: Phần tử lớn nhất trong A  currentMax ← A[1]  for i ← 2 to n do  if currentMax < A[i] then  currentMax ← A[i]  return currentMax 17
Máy tính: Mô hình máy tính truy xuất ngẫu nhiên  Cấu tạo: CPU nối với một bộ nhớ. Bộ nhớ bao gồm các ô nhớ. Mỗi ô nhớ có thể lưu 1 số (không giới hạn kích thước), 1 kí tự hoặc 1 địa chỉ.  Hỗ trợ các thao tác cơ sở: – Gán giá trị vào biến – Gọi một phương thức – Thi hành một thao tác số học (cộng, trừ,…) – So sánh hai số – Truy xuất phần tử mảng – Kết thúc hàm – Tham chiếu đối tượng 18
Mô hình máy tính truy xuất ngẫu nhiên  Các thao tác cơ sở có thời gian thi hành gần bằng nhau.  Các thao tác cơ sở có thời gian thi hành không phụ thuộc kích thước đầu vào của nó.  Thời gian thực thi của thuật toán = Số lượng các thao tác cơ sở của thuật toán đó trong mô hình máy tính truy xuất ngẫu nhiên (RAM)  Được gọi là độ phức tạp của thuật toán 19
Độ phức tạp thuật toán  Độphức tạp thuật toán thường phụ thuộc vào: – Kích thước của input (đầu vào)  Số phần tử của dãy  Số đỉnh và cạnh trong đồ thị – Các đặc trưng khác của dữ liệu đầu vào  Dãy gần như đã có thứ tự hay chưa? 20