Đề cương ôn tập thiết kế thuật toán

Thầy giáo gửi cho mọi người nội dung ôn tập cuối kỳ :
tải tại đây

ĐỀ CƯƠNG ÔN TẬP


MÔN: Thiết kế và đánh giá thuật toán

Lớp: K51A2 – A3

Người soạn: Lê Trọng Vĩnh

Chỉnh sửa: Nguyễn Thị Hồng Minh

Cấu trúc của đề thi: Đề thi gồm hai câu

Câu 1: (Lý thuyết) Trình bày ý tưởng và lược đồ tổng quát của
một phương pháp nào đó (liệt kê ở dưới). Cho ví dụ minh họa. (3 điểm)

Câu 2:(bài tập ) Áp dụng phương pháp ở câu 1 cho một bài toán (các bài
toán được liệt kê với các phần phía sau). Câu này có các phần

i) Trình bày thuật toán, ý nghĩa các, các biến … được sử dụng (3 điểm)

ii) Viết các hàm và thủ tục bằng một ngôn ngữ lập trình (2.5 điểm)

iii) Phân tích và tính độ phức tạp của thuật toán(1.5 điểm)


1. Độ phức tạp của thuật toán
Giải công thức đệ qui tính độ phức tạp bằng phương pháp thế.

2. Quay lui vét cạn
- Xếp hậu
- Liệt kê tổ hợp
- Liệt kê chỉnh hợp lặp và không lặp

3. Nhánh cận
- Máy ATM (còn gọi là rút tiền, đổi tiền …)
- Xâu ABC
- Người du lịch bán hàng TSP

4. Tham lam
- Máy ATM
- Người bán hàng du lịch TSP
- Lập lịch

5. Chia để trị
- Tính độ lệch của một dãy số
- Lát nền
- Sắp xếp mảng bằng phương pháp trộn

6. Qui hoạch động

- Cái túi
- Biến đổi xâu
- Di chuyển từ tây sang đông
_________________________________________________________


Chúc các em thi tốt ,thầy lun tin tưởng ở các em! Cố lên nhé

akkkkkk. de nay hi on kieu gi moi xong.huhu.