Bài giảng Giới thiệu môn học và kế hoạch hoàn thành môn học Phân tích và thiết kế thuật toán - PGS.TS. Trần Cao Đệ

Chia sẻ: Lê Kim Luông | Ngày: | Loại File: PPTX | Số trang:11

Thêm vào BST

Báo xấu

74
lượt xem 5
download

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

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. Mời các bạn cùng tham khảo.

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 Giới thiệu môn học và kế hoạch hoàn thành môn học Phân tích và thiết kế thuật toán - PGS.TS. Trần Cao Đệ

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 1
C h ư ơ n Nội dung môn học g 4 : G Phần 1: KT phân tích và thiết kế giải thuật i Ả • Chương 1: KỸ THUẬT PHÂN TÍCH GIẢI THUẬT I – Tổng quan T – Sự cần thiết phải phân tích giải thuật H U – Thời gian thực hiện của giải thuật Ậ T – Tỉ suất tăng và độ phức tạp của giải thuật S – Cách tính độ phức tạp O – Phân tích các chương trình đệ quy K H • Chương 2: KỸ THUẬT THIẾT KẾ GIẢI THUẬT Ớ P – Tổng quan C – Kĩ thuật chia để trị (Divide and Conquer) H U – Quy hạch động (dynamic programming) Ỗ I – Kĩ thuật “tham ăn” (greedy) – Kĩ thuật quay lui (Backtracking) – B 2 r – Kĩ thuật tìm kiếm địa phương (Local Search)
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ữ 9.0 – 10 A 8.0 - 8.9 B+ 7.0 - 7.9 B 6.0 - 6.9 C+ 5.0 - 5.9 C 4.5 – 4.9 D+ 4.0 - 4.4 D
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ỳ) 5
Lịch học Ngày Buổi nội dung Giới thiệu môn học – lịch học 9/1 S 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 6
Tài liệu tham khảo l Aho, A.V. , J. E. Hopcroft, J. D. Ullman. Data Structure and Algorihtms, 1983. l R. Sedgewick, Algorithms in Java, Addision-Wesley, 2004. Chapter 1. l R. Sedgewick, Algorithms , 1987. l Goodrich, Tamassia, Algorithm Design,
Tham khảo web • cây AVL - demo giải thuật http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT • cây (2,4) - demo giải thuật http://www.cs.unm.edu/~rlpm/499/ttft.html • cây đỏ đen - demo giải thuật http://gauss.ececs.uc.edu/RedBlackTester/redblack.htm
Tham khảo web (tt) • Demo Tìm kiếm chuỗi http://www.enseignement.polytechnique.fr/inform Boyer Moore http://www.prism.gatech.edu/~jgirata3/boyermoo • Demo Tìm bao lồi http://www.cse.unsw.edu.au/~lambert/java/3d/
Thông tin về GV PGS. TS. Trần Cao Đệ • Bộ môn CNTT - Khoa CNTT&TT-ĐHCT • Email: tcde@cit.ctu.edu.vn • Địa chỉ: Số 1, Lý Tự Trọng, Ninh Kiều, Cần Thơ 10
Chúc các bạn thành công!