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
•
Nội dung môn học
•
Phần 1: KT phân tích và thiết kế 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 1: KỸ THUẬT PHÂN TÍCH 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)
Chương 2: KỸ THUẬT THIẾT KẾ GIẢI THUẬT
– Kĩ thuật quay lui (Backtracking)
2
– Kĩ thuật tìm kiếm địa phương (Local Search)
– B r u t
C h ư ơ n g 4 : G i Ả I T H U Ậ T S O K H Ớ P C H U Ỗ I
•
– Cây AVL
– D-Cây
– B
– Cây 2-4
e Phần 2: Các chủ đề nâng cao - F Chuơng 3: CÂY CÂN BẰNG o r c e
– Cây đỏ đen
– K
o y e r - M o o r e
•
n u t h - M o r r i s - P r a t t
C h u ơ n g
5 :
C Á C
G I Ả I
T H U Ậ T
H Ì N H
– C
H Ọ C
á c
k h á i
n i ệ m
c ơ
b ả n
t r o n g
h ì n h
– C
h ọ c
á c
g i ả i
t h u ậ t
t r ê n
đ i ể m
v à
đ ư ờ n g
– C
t h ẳ n g
á c
g i ả i
t h u ậ t
t ì m
b a o
– G
l ồ i
i ả i
t h u ậ t
“ g ó i
– G
q u à ”
i ả i
t h u ậ t
•
G r a h a m
C h ư ơ n g
6 :
M Ậ T
– M
M Ã
ậ t
m ã
đ ố i
x ứ n g
v à
b ấ t
đ ố i
– M
x ứ n g
ậ t
m ã
R S A
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:
thang điểm (tham khảo)
Thang điểm 10 9.0 – 10 8.0 - 8.9 7.0 - 7.9 6.0 - 6.9 5.0 - 5.9 4.5 – 4.9 4.0 - 4.4 <4.0
Điểm chữ A B+ B C+ C D+ D F
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 Chương 1: KT Phân tích GT
9/1 S
Chương 2: KT thiết kế GT
16/1 C
Chương 2: KT thiết kế GT (tt)
23/1 S
30/1 S
Chương 3: Cây Cân Bằng
Chương 3: Cây Cân Bằng (tt)
6/2 S
Chương 4: So khớp chuỗi
13/2 S
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
lAho, A. V. , J. E. Hopcroft, J. D. Ullman. Data Structure and Algorihtms, 1983.
lR. Sedgewick, Algorithms in Java, Addision-Wesley, 2004. Chapter 1.
lR. Sedgewick, Algorithms , 1987.
lGoodrich, Tamassia, Algorithm Design,
2002.
lwww.codeproject.com
Tham khảo web
• cây AVL - demo giải thuật
http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html
• 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.html
• RSA - demo giải thuật
http://www.cs.uri.edu/cryptography/RSA/RSA.html
http://cisnet.baruch.cuny.edu/holowczak/classes/9444/rsademo/rsademo.htm
Tham khảo web (tt)
• Demo Tìm kiếm chuỗi
http://www.enseignement.polytechnique.fr/informatique/profs/Jean-Jacques.Levy/00/pc4/strmatch/e.html
Boyer Moore
http://www.prism.gatech.edu/~jgirata3/boyermoore/
• Demo Tìm bao lồi
http://www.cse.unsw.edu.au/~lambert/java/3d/
http://www.cs.princeton.edu/courses/archive/fall08/cos226/demo/ah/GrahamScan.html
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
