ĐỀ CƯƠNG CHI TIẾT KHÓA HỌC

Sắp xếp topo là một cách sắp xếp các đỉnh trong đồ thị có hướng sao cho nếu tồn tại đường đi từ đỉnh u đến đỉnh v trong đồ thị thì u phải đứng trước v trong cách sắp xếp này.
Ứng dụng vào một số bài toán trong thi đấu như:
Tìm hiểu các khái niệm về thành phần liên thông mạnh, cầu, khớp, thuật toán Tarjan để liệt kê các thành phần liên thông mạnh của đồ thị có hướng.
Ứng dụng vào một số bài toán trong thi đấu như:
Quay lui, đệ quy quay lui là một kỹ thuật, thuật toán được thiết kế dựa trên ý tưởng đệ quy. Xuất phát từ một lời giải rỗng, cố gắng mở rộng lời giải ra theo từng bước.
Ứng dụng vào một số bài toán trong thi đấu như:
Phương pháp sinh là phương pháp giải quyết bài toán liệt kê tập các tổ hợp có thứ tự.
Ứng dụng vào một số bài toán trong thi đấu như:
Nhánh cận là một kỹ thuật dùng để tối ưu hóa đệ quy quay lui, xác định điều kiện tối ưu của bài toán mà dừng mở rộng cấu hình không đưa đến lời giải tốt.
Ứng dụng vào một số bài toán trong thi đấu như:
Tìm hiểu các khái niệm về chu trình Hamilton, chu trình Euler, thuật toán Fleury và các hướng cải tiến liên quan.
Ứng dụng vào một số bài toán trong thi đấu như:
Tìm hiểu quan hệ đồng dư của số nguyên, hiện thực định lý Fermat nhỏ và tổng quát hơn là định lý Euler.
Ứng dụng vào một số bài toán trong thi đấu như:
Tìm hiểu về thuật toán Euclidean, Euclidean mở rộng, ứng dụng giải phương trình Diophante.
Ứng dụng vào các bài toán thao tác các phép tính trên phân số.
Tìm hiểu các thuật toán nổi tiếng liên quan đến số nguyên tố: Sàng nguyên tố Eratosthenes, Segmented Sieve. Hiện thực cách phân tích ra các thừa số nguyên tố của một số, và tìm hiểu về Phi hàm Euler.
Ứng dụng vào một số bài toán trong thi đấu như:
Kỳ thi giữa kỳ.

Chia để trị lấy ý tưởng từ đệ quy, giải quyết một bài toán bằng cách phân chia và giải các bài toán con có cùng tính chất.
Ứng dụng vào một số bài toán trong thi đấu như:
Từ bài toán cổ điển về dãy số Fibonacci, làm quen với hai cách cài đặt bài toán quy hoạch động. Ngoài ra biết cách lưu vết tổng các phần tử đứng trước nó trong một mảng, được sử dụng hỗ trợ giải quyết nhiều bài toán.
Ứng dụng vào một số bài toán trong thi đấu như:
Đến với chủ đề quy hoạch động đầu tiên là bài toán đổi tiền, một dạng bài toán xuất hiện sự trùng lặp khi tính toán lại các bài toán con.
Ứng dụng vào một số bài toán trong thi đấu như:
Ứng dụng vào một số bài toán như:
Tìm dãy con chung dài nhất. Chủ đề liên quan đến việc lưu trữ kết quả các bài toán con, sau đó sử dụng phối hợp để tính ra kết quả bài toán mong muốn.
Ứng dụng vào một số bài toán như:
Tìm dãy con tăng dài nhất. Bài toán cùng chung chủ đề với LCS và cũng có thể giải được bằng LCS, nhưng ta sẽ được học thêm cách tối ưu việc tìm kiếm giúp độ phức tạp thuật toán giảm đi đáng kể.
Ứng dụng vào các bài toán như:
Bài toán liên quan đến tối ưu hoá tổ hợp, thường gặp trong các vấn đề cần phân bổ nguồn tài nguyên. Mặc dù ta có giải bài toán Knapsack cơ bản với kĩ thuật Branch and Bound trong buổi 6, ở buổi này, ta sẽ được học công thức quy hoạch động với độ phức tạp thời gian tối ưu và thường được ứng dụng nhiều hơn.
Ứng dụng vào các bài toán như:
Ứng dụng vào các bài toán như:
Kiểm tra cuối kỳ
