Tối ưu Rời Rạc - Seminar@Optima

Tối ưu rời rạc là bộ môn nghiên cứu về các bài toán tối ưu trong đó các biến số có tính rời rạc, ví dụ như là số nhị phân hay số nguyên. Tối ưu rời rạc có rất nhiều ứng dụng trong thực tế.

Trang web này tập trung các slide bài giảng và bài tập của môn tối ưu rời rạc giảng dạy tại trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội.

Mã google classroom ptlnavr (cần dùng gmail để đăng ký, không dùng được email hus)

Tuần 1

Slides bài giảng:

• Giới thiệu chung
• Độ phức tạp tính toán

Bài tập về nhà: Bài tập 1

Tuần 2

Slides bài giảng:

• Đồ thị và duyệt đồ thị

Tuần 3

Slides bài giảng:

• Cây bao trùm. Demo.

Bài tập về nhà: Bài tập 2

Tuần 4

Slides bài giảng:

• Bài toán đường đi ngắn nhất. Demo.

Bài tập về nhà: Bài tập 3

Tuần 5+6

Chữa bài tập 2, 3.

Slides bài giảng:

• Bài toán luồng cực đại, lát cắt cực tiểu.
• Ví dụ 1.
• Ví dụ 2.
• Stanford
• Kozen

Bài tập về nhà: Bài tập 4

Tuần 7

Slides bài giảng:

• Bài toán ghép cặp. Hungarian method.

Bài tập về nhà: Bài tập 5

Tuần 8

Slides bài giảng:

• Bài toán ghép cặp bền vững (hôn nhân bền vững)
• Chữa bài tập 4

Đăng ký đề tài thuyết trình

• Bước 1: Xem danh sách đã đăng ký tại đây.
• Bước 2: Đăng ký đề tài của nhóm tại link

Các nhóm phải chọn các chủ đề khác nhau. Khi đăng ký cần xem lại danh sách đăng ký xem có trùng với nhóm khác hay không, nếu trùng thì phải chọn chủ đề khác. Mỗi chủ đề thuyết trình là một ứng dụng thực tế của một trong các bài toán được học trong môn học này (có thể chọn cả các bài toán sẽ học từ tuần thứ 8 trở đi). Mỗi nhóm sẽ phải tìm kiếm dữ liệu ứng với chủ đề lựa chọn, lập trình thực thi thuật toán giải quyết ứng dụng trên tập dữ liệu đó.

Ví dụ khi muốn tìm hiểu về ứng dụng của cây bao trùm, có thể xem trên https://en.wikipedia.org/wiki/Minimum_spanning_tree#Applications để tìm hiểu về các ứng dụng. Nếu chọn ứng dụng Handwriting recognition thì google Handwriting recognition minimum spanning tree để tìm thông tin.

Tương tự một vài ứng dụng của bài toán luồng cực đại có thể tìm thấy tại https://en.wikipedia.org/wiki/Maximum_flow_problem#Real_world_applications. Các bạn cũng có thể google trực tiếp maximum flow applications.

Tuần 9 

• Thi giữa kì

Tuần 10-12

Slides bài giảng:

• Bài toán tối ưu nguyên 1, Mosek modeling
• Bài toán tối ưu nguyên 2 – Thuật toán nhánh cận: slide, chapter, wolsey
• Bài toán tối ưu nguyên 3: cutting planes method, total unimodularity
• Sudoku code, pulp

Bài tập về nhà: Bài tập 6

Tuần 13

Slides bài giảng:

• Bài toán TSP: slide chính, một số ứng dụng, chứng minh thuật toán xấp xỉ 1.5, một số thuật toán heuristics

Tuần 14-15

Thuyết trình dự án

• Mỗi nhóm có 15 phút thuyết trình và 5 phút trả lời câu hỏi
• Toàn bộ slide và code của các nhóm phải được copy lên cùng 1 máy tính có cổng phù hợp với phòng học (các nhóm cần tự kiểm tra trước).