Bài giảng Phân tích và thiết kế thuật toán gồm 5 chương: Kỹ thuật phân tích giải thuật, kỹ thuật thiết kế giải thuật, cây cân bằng, giải thuật so khớp chuỗi, các giải thuật hình học, mật mã. Bài giảng sau đây sẽ giới thiệu môn học & kế hoạch hoàn thành môn học. . | 1 Giới thiệu môn học & kế hoạch hoàn thành môn học PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN (SP 609) Lớp LL và PP dạy học bộ môn Toán K21 PGS. TS. Trần Cao Đệ KHOA CNTT & TT Năm 2015 2 Nội dung môn học Phần 1: KT phân tích và thiết kế giải thuật Chương 1: KỸ THUẬT PHÂN TÍCH GIẢI THUẬT Tổng quan Sự cần thiết phải phân tích giải thuật Thời gian thực hiện của giải thuật Tỉ suất tăng và độ phức tạp của giải thuật Cách tính độ phức tạp Phân tích các chương trình đệ quy Chương 2: KỸ THUẬT THIẾT KẾ GIẢI THUẬT Tổng quan Kĩ thuật chia để trị (Divide and Conquer) Quy hạch động (dynamic programming) Kĩ thuật “tham ăn” (greedy) Kĩ thuật quay lui (Backtracking) Kĩ thuật tìm kiếm địa phương (Local Search) Phần 2: Các chủ đề nâng cao Chuơng 3: CÂY CÂN BẰNG Cây AVL D-Cây Cây 2-4 Cây đỏ đen Chương 4: GiẢI THUẬT SO KHỚP CHUỖI Brute-Force Boyer-Moore Knuth-Morris-Pratt Chuơng 5: CÁC GIẢI THUẬT HÌNH HỌC Các khái niệm cơ bản trong hình học Các giải thuật trên điểm và đường thẳng Các giải thuật tìm bao lồi Giải thuật “gói quà” Giải thuật Graham Chương 6: MẬT MÃ Mật mã đối xứng và bất đối xứng Mật mã RSA Kế hoạch học- đánh giá Lý thuyết: Thời lượng: 8 buổi học + 1 thi Thực hành: tự thực hành Thời lượng: 6 buổi Đánh giá : Kiểm tra giữa kỳ (30 phút): 30% Thi: Tự luận (120 phút) Đánh giá: 70%. Ngày thi: 3 thang điểm (tham khảo) Thang điểm 10 Điểm chữ – 10 A - B+ - B - C+ - C – D+ - D < F 5 Thi hết môn Tự luận (không xem tài liệu): Áp dụng giải thuật Minh họa giải thuật Viết giải thuật Trình bày ý tưởng áp dụng Phân tích độ phức tạp GT (GKỳ) 6 Lịch học Ngày Buổi nội dung 9/1 S Giới thiệu môn học – lịch học Chương 1: KT Phân tích GT 16/1 C Chương 2: KT thiết kế GT 23/1 S Chương 2: KT thiết kế GT (tt) 30/1 S Chương 3: Cây Cân Bằng 6/2 S Chương 3: Cây Cân Bằng (tt) 13/2 S Chương 4: So khớp chuỗi S KT giữa kỳ; Chương 5: Giải thuật hình học; C Chương 6: Mật mã Theo lịch khoa SP Thi hết môn Tài liệu tham khảo Aho, A. V. , J. E. Hopcroft, J. D. Ullman. Data Structure and Algorihtms, 1983. R. Sedgewick, Algorithms in Java, Addision-Wesley, 2004. Chapter 1. R. Sedgewick, Algorithms , 1987. Goodrich, Tamassia, Algorithm Design, 2002. Tham khảo web cây AVL - demo giải thuật cây (2,4) - demo giải thuật cây đỏ đen - demo giải thuật RSA - demo giải thuật Tham khảo web (tt) Demo Tìm kiếm chuỗi Boyer Moore Demo Tìm bao lồi 10 Thông tin về GV PGS. TS. Trần Cao Đệ Bộ môn CNTT - Khoa CNTT&TT-ĐHCT Email: tcde@ Địa chỉ: Số 1, Lý Tự Trọng, Ninh Kiều, Cần Thơ Chúc các bạn thành công!
