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)
C
h
ư
ơ
n
g
4
:
G
i
Ả
I
T
H
U
Ậ
T
S
O
K
H
Ớ
P
C
H
U
Ỗ
I
–B
r
u
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: <Tùy theo Khoa SP sắp> 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
<4.0 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ỳ)