Phân tích và thiết kế thuật toán (SP 609)

1Giới thiệu môn học &kế hoạch hoàn thành môn họcPHÂ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 K21PGS. TS. Trần Cao ĐệKHOA CNTT & TTNăm 20152Nội dung môn họcPhầ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 quanSự cần thiết phải phân tích giải thuậtThời gian thực hiện của giải thuậtTỉ suất tăng và độ phức tạp của giải thuậtCách tính độ phức tạpPhân tích các chương trình đệ quyChương 2: KỸ THUẬT THIẾT KẾ GIẢI THUẬTTổng quanKĩ 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 caoChuơng 3: CÂY CÂN BẰNGCây AVLD-Cây Cây 2-4Cây đỏ đenChương 4: GiẢI THUẬT SO KHỚP CHUỖI Brute-ForceBoyer-MooreKnuth-Morris-PrattChuơ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ồiGiả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ã RSAKế hoạch học- đánh giáLý thuyết: Thời lượng: 8 buổi học + 1 thiThự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: 3thang điểm (tham khảo)Thang điểm 10 Điểm chữ9.0 – 10A8.0 - 8.9B+7.0 - 7.9B6.0 - 6.9C+5.0 - 5.9C4.5 – 4.9D+4.0 - 4.4D<4.0F5Thi hết môn Tự luận (không xem tài liệu): Áp dụng giải thuậtMinh họa giải thuậtViết giải thuậtTrình bày ý tưởng áp dụngPhân tích độ phức tạp GT (GKỳ)6Lịch họcNgàyBuổinội dung9/1SGiới thiệu môn học – lịch họcChương 1: KT Phân tích GT16/1CChương 2: KT thiết kế GT23/1SChương 2: KT thiết kế GT (tt)30/1S Chương 3: Cây Cân Bằng6/2SChương 3: Cây Cân Bằng (tt) 13/2SChương 4: So khớp chuỗiSKT giữa kỳ; Chương 5: Giải thuật hình học; CChương 6: Mật mãTheo lịch khoa SP Thi hết mônTà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.www.codeproject.comTham khảo web cây AVL - demo giải thuậtây (2,4) - demo giải thuật ây đỏ đen - demo giải thuật - demo giải thuật khảo web (tt) Demo Tìm kiếm chuỗi Moore Tìm bao lồi ông tin về GVPGS. TS. Trần Cao ĐệBộ môn CNTT - Khoa CNTT&TT-ĐHCTEmail: tcde@cit.ctu.edu.vnĐịa chỉ: Số 1, Lý Tự Trọng, Ninh Kiều, Cần ThơChúc các bạn thành công!