PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT

Chia sẻ: No Comment | Ngày: | Loại File: PPT | Số trang:125

Thêm vào BST

Báo xấu

594
lượt xem 58
download

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

Quicksort là một phương pháp xếp thứ tự theo kiểu “chia để trị”. Nó thực hiện bằng cách phân hoạch một tập tin thành hai phần và sắp thứ tự mỗi phần một cách độc lập với nhau. Giải thuật có cấu trúc như sau: Cung cấp kiến thức và kỹ năng trong việc phân tích độ phức tạp tính toán của giải thuật.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT

1 PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT ANALYS AND DESIGN ALGORITHMS
Mục tiêu môn học 2 Cung cấp kiến thức và kỹ năng trong  việc phân tích độ phức tạp tính toán của giải thuật. Tìm hiểu các chiến thuật thiết kế giải  thuật
Nội dung môn học 3 Phân bổ thời gian Số Ghi Lý Nội dung TT Tự Bài tiết chú thuyế Tập học t Các khái niệm căn bản về phân tích 1 6 6 0 10 độ phức tạp giải thuật Phân tích độ phức tạp của một số giải 2 8 8 3 20 thuật sắp thứ tự và tìm kiếm Phân tích độ phức tạp của một số giải 3 9 9 3 20 thuật trên cấu trúc dữ liệu Phân tích độ phức tạp của một số giải 4 5 5 3 20 thuật đồ thị Các chiến lược thiết kế giải thuật 5 8 8 3 15 Vấn đề NP-đầy đủ 6 9 9 3 20 TỔNG 60 60 0 105
Đánh giá kết quả 4 Kiểm tra giữa kỳ: Tự luận 1. Điểm Kiểm tra giữa kỳ < 4  không được thi kết thúc môn   học lại Kiểm tra cuối kỳ: Tự luận 1. Bài tập lớn: làm các bài tập 2. Điểm Đề tài < 4  không được thi kết thúc môn  học lại 3. Thi kết thúc môn: Tự luận 4. Kiểm tra thường kỳ 5.
Tài liệu học tập 5 Giáo trình:   [1] Cormen, T. H., Leiserson, C. E, and Rivest, Introduction to Algorithms, The MIT Press, 1997. Tham khảo:   [2] Sedgewick, Algorithms in C+ , Addison- + Wesley, 1998  [3] Weiss, M.A, Data Structures and Algorithm Analysis in C , The Benjamin/Cummings P ublishing, 1993
Nhắc nhở một số quy định 6 Đi học đúng giờ  Đeo thẻ SV  Không để chuông điện thoại reo trong giờ học  Không nghe điện thoại, nhắn tin trong giờ học  Không nói chuyện riêng, làm ồn khi nghe giảng  Mang đầy đủ tài liệu học tập của môn học (khi học LT  và TH): giáo trình, bài tập, tập chép bài (hoặc slide bài giảng), usb để lưu bài tập Phải làm bài tập ở nhà   Nếu vi phạm: Nhắc nhở chung  Bị mời ra khỏi lớp  6 Xóa tên khỏi môn học
Trao đổi thông tin 7 Địa chỉ mail: • Kimchi_12041972@yahoo.com Địa chỉ download tài liệu: • http://my.opera.com/LinhChi10/blog/
Chương 1: 8 CÁC KHÁI NIỆM CĂN B ẢN VỀ PHÂN TÍCH ĐỘ PHỨC TẠP GIẢI THUẬT
Nội dung 9  Thuật ngữ và Khái Niệm  Các định nghĩa về độ phức tạp  Kỹ thuật chia-để-trị và giải thuật đệ quy  Phương trình truy hồi và cách giải phương  trình truy hồi Vài thí dụ minh hoạ về phân tích độ phức tạp  giải thuật
Thuật ngữ và khái niệm 10 10  Cấu trúc dữ liệu  Thuật toán  Độ phức tạp của thuật toán 
Cấu trúc dữ liệu 11 11 (1) Sự tổ chức hợp lý của các thành phần dữ liệu,  (2) Tập các thao tác để truy cập các thành ph ần dữ  liệu. Ví dụ:  Mảng (Array)  Danh sách liên kết (Linked List)  Ngăn xếp (Stack)  Hàng đợi (Queue)  Cây (Tree)  …  (1) the logical arrangement of data elements, combined with  (2) the set of operations we need to access the elements. 
Thuật ngữ và khái niệm 12 12 Cấu trúc dữ liệu   Thuật toán   Độ phức tạp của thuật toán
Thuật toán 13 13 Giải thuật hay thuật toán là dãy các thao tác xác  định nhằm giải một bài toán nào đó. Ví dụ: Tính tổng các số nguyên lẻ từ 1n  Input: Số nguyên n Output: Tổng các số nguyên lẻ từ 1n B1: S=0  B2: i=1  B3: Nếu i>n thì sang B7, ngược lại sang B4  B4: S=S+i  B5: i=i+2  B6: Quay lại B3  B7: Tổng cần tìm là S 
Các đặc trưng của Thuật toán 14 14 INPUT: Có các bộ dữ liệu đầu vào thuộc một tập  hợp dữ liệu nào đó. OUTPUT: Xuất dữ liệu đầu ra theo yêu cầu của bài  toán Tính xác định: Mỗi bước của thuật toán hoàn toàn  xác định, được mô tả chính xác và cho kết quả xác định Tính dừng: Thuật toán phải kết thúc sau hữu hạn  bước. Tính phổ dụng: Thuật toán áp dụng được cho mọi  bộ dữ liệu đầu vào thuộc tập hợp dữ liệu
Mối quan hệ của CTDL và thuật toán 15 15 CTDL + Thuật toán = Chương trình
Các phương pháp biểu diễn giải thuật 16 16 Diễn đạt bằng ngôn ngữ tự nhiên  Biểu diễn bằng sơ đồ khối  Biểu diễn bằng Giả mã, thông thường dùng  ngôn ngữ tựa PASCAL; Ngôn ngữ lập trình cấp cao (High programming  languages) như Pascal, C/C++ vv
Các phương pháp biểu diễn giải thuật 17 17 Ví dụ: Tìm x trong dãy a1, a2, ...., an  Đầu vào: Số x, dãy n số a1, a2, ..., an  Đầu ra: Một giá trị logic true hoặc false  Search(x, a, n) 1 for i ←1 to n 2 do if ai= x then return true  4 return false
Thuật ngữ và khái niệm 18 18 Cấu trúc dữ liệu   Thuật toán  Độ phức tạp của thuật toán (algorithm complexity) 
Độ phức tạp của thuật toán 19 19 Độ phức tạp của giải thuật là chi phí về tài  nguyên của hệ thống (chủ yếu là thời gian, bộ nhớ, CPU, đường truyền) cần thiết để thực hiện giải thuật Phân tích giải thuật (Analyzing of Algorithm) là  quá trình tìm ra những đánh giá về tài nguyên cần thiết để thực hiện giải thuật
Thời gian thực hiện thuật toán 20 20 Độ phức tạp về thời gian của giải thuật:  Được qui về đếm số lệnh cần thực thi của giải thuật  Đó là một hàm T(n) phụ thuộc vào kích thước n của input  Coi như có một máy trừu tượng (abstract machine) để thực hiện giải thuật