ĐỀ CƯƠNG CHI TIẾT KHÓA HỌC
Tìm hiểu về các kiến thức cơ bản của hình học như là điểm, vector; đoạn thẳng, đường thẳng; hình tròn.
Ứng dụng vào các bài toán như:
- Tìm giao điểm của các đường thẳng được xác định bằng 2 điểm trên mặt phẳng.
- Tìm số điểm có tọa độ là số nguyên trên đoạn thẳng AB.
- Tìm xem liệu có giao điểm nào trong các cặp đường thẳng cho trước mà có hoành độ nằm trong khoảng từ x1 đến x2.
Tiếp tục các nội dung về hình học: đa giác, đa giác lồi và bao lồi. Tìm hiểu thuật toán Graham’s Scan và Monotone chain (hay Andrew’s Algorithm) để tìm bao lồi của một tập điểm cho trước.
Ứng dụng vào các bài toán như:
- Tìm đường kính nhỏ nhất của “sọt rác” để bỏ vừa “miếng rác”.
- Tính tỉ lệ phần trăm diện tích bị lãng phí khi bỏ một “viên gạch” vào một chiếc “hộp” hình đa giác lồi có diện tích nhỏ nhất có thể.
- Cho danh sách các địa điểm văn phòng của 2 công ty. Tìm 2 văn phòng để đặt làm trụ sở của 2 công ty, sao cho khoảng cách giữa 2 trụ sở này là xa nhất.
Heavy-Light Decomposition (HLD) là một kỹ thuật trong lĩnh vực lập trình chấm (competitive programming) và thuật toán đồ thị. Nó được sử dụng để giải quyết hiệu quả các bài toán trên cây (tree) bằng cách chia cây thành các đoạn con nhỏ hơn, từ đó giảm đáng kể số lượng phép toán thực hiện và tăng tốc độ thực thi các truy vấn trên cây.
Một số bài toán của HLD:
- Truy vấn đường đi: Tìm đường đi giữa hai đỉnh trên cây.
- Truy vấn cập nhật: Cập nhật giá trị của một đỉnh trên cây.
- Truy vấn đoạn con: Tính tổng hoặc một giá trị biểu diễn của một đoạn con của cây.
Một số bài tập ôn tập:
- Kiểm tra xem một điểm nằm bên trong hay bên ngoài đường tròn.
- Cho mảng 𝑎 với kích thước 𝑛 ⋅ 𝑇. Biết rằng với 𝑖 > 𝑛 thì ai = ai − 𝑛. Tìm dãy con không giảm dài nhất của mảng a.
- Đếm số cặp dây điện giao nhau, biết rằng dây điện được kết nối với nhau qua các cột điện.
- Tìm số phần tử lớn nhất của một “good segment” của dãy A, biết rằng “good segment” khi đoạn con này có thể được chia thành tối đa K đoạn con có tổng không vượt quá S.
Tìm hiểu về Edit Distance, hay có thể hiểu là “khoảng cách” của 2 chuỗi và thuật toán quy hoạch động để tính khoảng cách này.
Ứng dụng vào các bài toán sau:
- Tính số lượng thao tác ít nhất cần thực hiện để biến xâu đã cho thành xâu đối xứng.
- Tính số lượng thao tác ít nhất cần thực hiện để biến xâu X thành xâu Y, với các xâu chỉ bao gồm các ký tự A, G, T và C.
- Tìm thứ tự các thao tác để biến xâu S thành xâu T, mà số thao tác cần thực hiện là ít nhất.
Tìm hiểu dạng bài toán quy hoạch động với trạng thái, trong đó ta cần xử lý bài toán trên một tập hợp nhỏ các phần tử mà mỗi phần tử có thể được chọn hoặc không.
Ứng dụng vào các bài toán sau:
- Tìm cách ghép 2*N điểm trên mặt phẳng tọa độ sao cho tổng khoảng cách giữa các cặp điểm là nhỏ nhất.
- Tìm đường đi Hamilton có trọng số nhỏ nhất của một đồ thị.
- Tìm xem liệu tồn tại cách ghép M miếng gỗ có chiều khác nhau thành một hình vuông hay không.
- Tìm số công tắc nhỏ nhất để có thể tắt tất cả đèn, biết rằng mỗi công tác sẽ tắt được các đèn khác nhau.
Tìm hiểu kỹ thuật sử dụng quy hoạch động giải quyết các bài toán trên cây, dựa vào mối quan hệ giá trị giữa các node để xác định kết quả bài toán của mỗi node hoặc toàn bộ cây.
Ứng dụng vào các bài toán sau:
- Tìm một tập các đỉnh trên cây sao cho tổng giá trị là lớn nhất và không có 2 đỉnh nào kề nhau.
- Với mỗi đỉnh, tính tổng khoảng cách từ đỉnh đó đến các đỉnh còn lại trên cây.
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
Tìm hiểu dạng bài toán quy hoạch động trên chữ số.
Ứng dụng vào các bài toán sau:
- Đếm số lượng số nguyên X sao cho A ≤ X ≤ B và tổng các chữ số của X đúng bằng K.
- Đếm số lượng số nguyên X sao cho A ≤ X ≤ B mà X không chứa 2 chữ số liên tiếp giống nhau.
- Đếm số lượng số nguyên X sao cho A ≤ X ≤ B mà X chỉ chứa chữ số d ở vị trí chẵn.
Tìm hiểu cấu trúc cây tìm kiếm nhị phân tối ưu (Optimal Binary Search Tree – OBST), định lý Yao và cách tối ưu hóa bài toán OBST.
Ứng dụng vào các bài toán sau:
- Tìm cách chặt một thanh gỗ thành n đoạn, mỗi đoạn có độ dài ai sao cho chi phí là nhỏ nhất.
- Chi phí cho một nhát chặt bằng độ dài của thanh gỗ trước khi chặt.
- Tìm số đồng tiền vàng lớn nhất mà tên cướp biển có thể lấy được, trước khi mỏ vàng bị giải tỏa…
Phân tích các bài toán, từ đó rút ra cách có thể ứng dụng bao lồi để tối ưu thuật giải quy hoạch động.
Ứng dụng vào các bài toán sau:
- Cho M truy vấn, mỗi truy vấn cho một số 𝑥, tìm giá trị 𝑦 lớn nhất sao cho điểm (𝑥, 𝑦) là điểm thuộc một trong các đường thẳng đã cho.
- Cho N hình chữ nhật (N ≤ 106), hình chữ nhật thứ i được giới hạn bởi 4 điểm trên mặt phẳng tọa độ. Mỗi hình có thêm giá trị 𝑎𝑖. Yêu cầu chọn ra một tập các hình sao cho tổng diện tích phần hợp của các hình đó trừ cho tổng giá trị 𝒂 của các hình được chọn là lớn nhất.
- Tìm tổng chi phí thấp nhất để gom N chiếc lá về đúng K đống lá, với chi phí để gom một chiếc lá bằng tích khổi lượng của chiếc lá và khoảng cách nó di chuyển.
Một số bài tập ôn tập:
- Tìm số con đường tối đa để đi từ đỉnh 1 tới đỉnh N, nhưng mỗi cạnh chỉ được thuộc duy nhất 1 con đường và được đi qua đúng 1 lần.
- Tính băng thông giữa 2 máy tính trong mạng.
- Tính chi phí nhỏ nhất để chuẩn bị và in K bài tập trong N ngày, biết rằng mỗi ngày có chi phí để chuẩn bị và in có thể khác nhau.
Persistent data structures là được dùng để thiết kế cấu trúc dữ liệu, cho phép lưu giữ và truy xuất các phiên bản trước của cấu trúc dữ liệu, ngay cả sau khi thực hiện các cập nhật và sửa đổi. Trong cấu trúc dữ liệu thông thường, bất kỳ thay đổi nào đối với cấu trúc đều dẫn đến sự thay đổi của phiên bản hiện tại của dữ liệu, nhưng với cấu trúc dữ liệu persistent, các phiên bản trước đó được giữ lại và các phiên bản mới được tạo ra để phản ánh các cập nhật.
Tìm hiểu các khái niệm về luồng, luồng cực đại. Tìm hiểu phương pháp Ford-Fulkerson, thuật toán Edmonds-Karp, thuật toán Dinic để giải quyết bài toán luồng cực đại trên mạng (Maximum Flow Problem).
Ứng dụng vào các bài toán sau:
- Tìm số trạm xe buýt ít nhất để phá hủy sao cho thời gian để quân đội đi từ đỉnh 1 tới đỉnh 𝑛 không qua 𝑘 phút.
- Tìm tốc độ truy cập lớn nhất của một máy tính trong mạng.
- Tìm chi phí nhỏ nhất để phá hủy sự kết nối của 2 máy tính trong mạng.
Tìm hiểu và giải quyết bài toán Minimum Cost Flow: tìm luồng cực đại thông qua mạng và có chi phí nhỏ nhất.
Ứng dụng vào các bài toán sau:
Trong đồ thị có n đỉnh và m cạnh vô hướng, tìm 2 đường đi phân biệt để đi từ 1 tới n và ngược lại mà không sử dụng 1 cạnh 2 lần, với tổng trọng số là nhỏ nhất
Tìm ra thời gian nhỏ nhất có thể để truyền được đúng D đơn vị dữ liệu từ máy chủ 1 đến N.
Kiểm tra cuối kỳ.
