ĐỀ CƯƠNG ÔN TẬP MÔN TOÁN RỜI RẠC
I.PHẦN 1: LÝ THUYẾT TỔ HỢP
1.Chương 1: Mở đầu (2 đ)
a.Lý thuyết tập hợp
b.Một số nguyên lý cơ bản
c.Các cấu hình tổ hợp đơn giản
(Chương này có thể cho bài tập dạng CM 1 đẳng thức sử dụng quy nạp hoặc các bài toán dùng tổ hợp)
2.Chương 2: Các bài toán tổ hợp (3 đ)
a.Bài toán đếm
(Cho dạng Bài toán đố sử dụng nguyên lý bù trừ hoặc đếm số nghiệm nguyên không âm của một hệ thức truy hồi (dạng đẳng thức hoặc bất đẳng thức truy hồi thuần nhất hoặc không))
b.Bài toán tối ưu
c.Bài toán tồn tại
Các dạng bài tập liên quan đến các phần trên
II.PHẦN 2: LÝ THUYẾT ĐỒ THỊ (5đ)
1.Chương 3: Các khái niệm về đồ thị
a.Khái niệm đồ thị
b.Đường đi, chu trình, tính liên thông của đồ thị
c.Một số dạng đồ thị đặc biệt
2.Chương 4: Biểu diễn đồ thị trên máy tính
a.Ma trận kề - Ma trận trọng số
b.Danh sách cạnh – Danh sách kề
3.Chương 6: Đồ thị và cây
a.Đồ thị Euler và đồ thị Hamilton (Các khái niệm, định lý và áp dụng trên 1 đồ thị cụ thể)
b.Cây và cây khung của đồ thị
c.Các cách duyệt cây
d.Tìm cây khung nhỏ nhất của đồ thị - Thuật toán Kruskal và thuật toán Prim (Viết giải thuật và áp dụng vào 1 bài cụ thể)
4.Chương 7: Bài toán đường đi ngắn nhất
a.Thuật toán Dijkstra (Viết giải thuật và áp dụng vào 1 bài cụ thể)
Các dạng bài tập liên quan