ĐỀ CƯƠNG CHI TIẾT KHÓA HỌC
Disjoint Sets là cấu trúc dữ liệu rất hữu dụng, được dùng làm nền tảng cho một số thuật toán như Kruskal, Prim, 2 thuật toán tìm cây khung nhỏ nhất trên đồ thị.
Ứng dụng vào các bài toán như:
- Tạo chuỗi có thứ tự từ điển nhỏ nhất từ chuỗi gốc, với quy tắc các ký tự tương đương được cho trước.
- Xác định liệu sự tồn tại của một đường truyền có cần thiết trong một mạng lưới truyền mạng.
- Hiện thực các truy vấn đặc biệt trên mảng.
- Xác định con đường cần đóng cửa và con đường cần xây mới tương ứng để đảm bảo luôn có đường đi giữa các thành phố bất kỳ.
- Xác định một cách giải của Nurikabe puzzle có hợp lệ hay không.
Prim là thuật toán giải quyết bài toán xác định cây khung có trọng số nhỏ nhất dựa trên tư tưởng tham lam.
Ứng dụng vào các bài toán như:
- Xác định số tiền lớn nhất chính phủ có thể tiết kiệm được trong việc thắp sáng các con đường trong thành phố.
- Xác định hiệu suất sử dụng cần thiết của bình sạc xe để đi giữa các thành phố bất kỳ.
- Xây dựng đất nước GraphLand bởi các đường bộ nối các thành phố, các đường sắt nối các tỉnh, để đạt được chi phí xây dựng nhỏ nhất.
- Tìm chi phí tối thiểu để đi hết một số thành phố từ một thành phố cho trước.
- Xác định giá trị cây khung nhỏ nhất của một đồ thị cập nhật thêm cạnh liên tục ứng với mỗi truy vấn.
Giống như Prim, thuật toán Kruskal cũng tìm cây khung nhỏ nhất dựa trên tư tưởng tham lam nhưng không phụ thuộc vào điểm bắt đầu.
Ứng dụng vào các bài toán như:
- Tính đường đi ngắn nhất giữa các cặp con đường trong thành phố.
- Xác định số con đường tối thiểu cần xây dựng và tối đa hóa độ bền của máy sử dụng để xây dựng từng con đường này sao cho có đường đi giữa 2 thị trấn bất kỳ.
- Tính toán chi phí tối thiểu để xây dựng hệ thống phân cấp trong một công ty.
- Xác định chi phí tối thiểu trong việc đặt các đồng vàng và đồng bạc trên các con đường trong vương quốc để làm hài lòng bọn cướp.
- Hiện thực các thao tác trên một rừng.
Sau ba buổi học lý thuyết sẽ là một buổi làm bài tập để ôn lại kiến thức của cả ba buổi trên.
Ứng dụng vào các bài toán như:
- Tính tổng số thuốc cần chuẩn bị cho khách uống phải sữa hư trong buổi tiệc.
- Ứng dụng các thuật toán liên quan đến đồ thị để kiểm tra có đường đi giữa 2 ô trong bảng cho trước.
- Tính tổng các chữ số của các số trong khoảng cho trước.
- Tìm hành trình để tải trọng của xe lưu thông trên đường đó là lớn nhất.
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 các bài toán như:
- Xác định ‘vòng tròn’ những người thực hiện cuộc gọi trực tiếp hoặc gián tiếp với nhau.
- Xác định số domino tối thiểu cần tác động để làm đổ tất cả các domino cho sẵn.
- Xác định tập hợp các đỉnh sao cho tất cả các đỉnh còn lại đều có đường đi đến nó trong đồ thị.
- Tìm số police checkpoint cần đặt để bảo vệ thành phố và giảm thiểu chi phí.
- Giúp chính quyền thành phố xác định xem có bao nhiêu cách khác nhau để thực hiện kế hoạch cải tổ thỏa mãn các yêu cầu đặt ra.
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ư:
Tham lam là một kĩ thuật thường được sử dụng trong thi đấu. Dùng để giải quyết các vấn đề lựa chọn và tối ưu hóa. Phương pháp này hoạt động bằng cách chọn lựa phương án tốt nhất, có vẻ hợp lý nhất tại mỗi bước định hướng, mà hy vọng sẽ dẫn tới kết quả tối ưu toàn cục.
Ứng dụng vào các bài toán như:
- Tính số lần chơi ít nhất để đạt được 2-star rating trong một trò chơi điện tử.
- Tính số lượng bảo vệ một trung tâm nghiên cứu cần thuê để tất cả mọi nơi trong trung tâm đều được canh gác.
Bài kiểm tra giữa khoá học để kiểm tra lại kiến thức đã học từ Lecture 01 đến Lecture 07
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 các bài toán như:
- Xác định các hãng xe có giá nằm trong một khoảng cho trước.
- Xác định số nguyên lớn nhất không vượt quá giới hạn cho trước với điều kiện không có chữ số nào lặp nhiều hơn hai lần.
- Xác định số cách sắp xếp domino vào hộp thỏa mãn ràng buộc cho trước.
- Điền các phép tính cộng, trừ, nhân, chia vào các phân số cho trước để tạo thành phép tính đúng.
- Tìm cách tác động vào các bóng đèn trên bảng quảng cáo để đạt được số bóng đèn sáng là nhiều nhất.
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ư:
Tiếp tục làm một buổi bài tập ứng dụng vào các bài toán như:
- Xác định số cách hoàn thành một trò chơi liên quan đến đồ thị.
- Xác định số đỉnh lớn nhất có thể đi qua từ đồ thị được xây dựng trong đề bài.
- Xác định thứ tự của một chuỗi trong danh sách từ được xây dựng theo quy ước của đề bài.
- Kiểm tra sự tồn tại của đường đi chứa một số số cục vàng trên đường.
- Ứng dụng sự liên thông của đồ thị để xác định số học sinh ít nhất cần thầy giáo thông báo trực tiếp để thông tin này được truyền đi cho cả lớp.
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ư:
Bài kiểm tra cuối kỳ toàn khoá học:
- Bài toán chi tiêu mua sắm.
- Tìm lợi nhuận trong trò chơi Jackpot.
