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

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 các bài toán như:
  • Cặp điểm gần nhau nhất.
  • Bài toán có dạng constructive problem: sắp xếp lịch tập luyện của đội bóng sao cho hai người bất kì trong đội đều có ít nhất một lần đối đầu với nhau.
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 các bài toán như:
  • Thay vì tìm số Fibonacci thứ N, tìm một số không phải là số Fibonacci thứ N.
  • Xác định thời điểm mà màn hình máy tính bị hư nếu biết một số pixel trên màn hình đã bị hỏng.
Đế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 các bài toán như:
  • Phân tích số.
  • Tháo lắp đĩa tạ khi thi thể hình.
  • Mua sắm ở trung tâm thương mại.
Một số bài toán ôn tập:
  • Kiểm tra lời đồn đoán rằng một chú voi to hơn thì thông minh hơn có đúng hay không.
  • Chấm điểm một bài thi sắp xếp các sự kiện lịch sử.
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ư:
  • Sắp xếp xe trên một chuyến phà.
  • Sắp xếp hành lí lên một chuyến taxi.
Tìm dãy con tăng dài nhất. Bài toán cùng chung chủ đề với LIS và cũng có thể giải được bằng LIS, 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ộ trò chơi xếp gạch, búp bê Nga.
  • Chiến lược phòng thủ của Starwars SDI.
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 các bài toán như:
  • Chuỗi Palindrome dài nhất.
  • Dãy con chung không liền kề dài nhất.
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 cấu trúc dữ liệu Hàng đợi hai đầu, cho phép thao tác ở đầu và cuối tập hợp với độ phức tạp chỉ O(1); và cách ứng dụng CTDL này vào các bài toán thực tế. Ứng dụng vào các bài toán như:
  • Tìm phần tử lớn nhất trong mỗi mảng con kích thước K.
  • Tìm mảng con ngắn nhất có tổng các phần tử lớn hơn bằng K.
  • Tìm hình chữ nhật con chứa toàn số 1 có kích thước lớn nhất trong ma trận.
Tìm hiểu khái niệm về hàm băm, bảng băm, phương pháp Polynomial để xây dựng hàm băm. Ứng dụng vào các bài toán như:
  • Tìm kiếm vị trí xuất hiện của chuỗi T trong chuỗi S.
  • Kiểm tra xâu đối xứng với độ phức tạp chỉ O(1) (chưa tính phần tiền xử lý).
  • Đếm số lần xuất hiện của các tiền tố trong chuỗi.
  • Tìm đoạn trùng nhau dài nhất của hậu tố chuỗi T và tiền tố chuỗi S.

Tìm hiểu về bảng thưa – một cấu trúc dữ liệu cho phép giải quyết các bài toán (truy vấn) theo dạng khoảng (range query) trên một tập dữ liệu cố định.

  • Tìm phần tử nhỏ nhất trong đoạn L tới R chỉ trong O(1) (chưa tính phần tiền xử lý).
  • Kiểm tra xâu đối xứng với độ phức tạp chỉ O(1) (chưa tính phần tiền xử lý).
  • Tính tổng các phần tử trong đoạn L tới R chỉ trong O(logN) (chưa tính phần tiền xử lý).
  • Tìm số đoạn từ L tới R thỏa mãn một tính chất cho trước.
  • Tính độ chênh lệch của phần tử nhỏ nhất và lớn nhất trong đoạn L tới R.
    • Một số bài toán ôn tập:
    • Tìm độ dài cạnh của ma trận vuông con đối xứng lớn nhất.
    • Tìm phần tử xuất hiện nhiều lần nhất trong đoạn từ L tới R trên mảng không giảm.
    • Tìm ký tự mà con trỏ ở 2 đầu xâu đang chỉ đến sau các lần di chuyển.
    • Giúp một nhà khoa học tìm chi phí ít nhất để mua enzyme sao cho mỗi giờ đều có enzyme để sử dụng, biết rằng chi phí để mua enzyme mỗi giờ là khác nhau, và enzyme không thể tồn tại quá h giờ.

    Tìm hiểu về cấu trúc dữ liệu Cây phân đoạn, giúp giải quyết các bài toán trên dãy số có sự thay đổi và cập nhật thường xuyên.

    Ứng dụng vào các bài toán như:

  • Tìm phần tử nhỏ nhất trong đoạn L tới R.
  • Tính tổng các phần tử trong đoạn L tới R.
  • Tính thể tích lớn nhất cho chiếc bánh sinh nhật, biết rằng một tầng bánh chỉ có thể được đặt trên tầng bánh khác có thể tích lớn hơn.
  • Kiểm tra tính “thú vị” của mảng, biết rằng một mảng thú vị khi m mảng con [Li, Ri] thỏa mãn: kết quả phép AND của tất cả phần tử trong mảng con này bằng với một số cho trước.
  • Thực hiện một loạt truy vấn sao chép một phần mảng con A sang một phần của mảng con B, rồi tìm giá trị tại vị trí x của mảng B sau tất cả truy vấn.
  • Tìm mảng con có số lượng cặp ngoặc tròn đúng lớn nhất.

    • Tìm hiểu về cấu trúc dữ liệu Fenwick Tree (hay Binary Indexed Tree – BIT) – một cấu trúc dữ liệu được sử dụng rất phổ biến trong lập trình thi đấu.

    Ứng dụng vào các bài toán như:

  • Tính tổng các phần tử trong các đoạn cho trước.
  • Tìm chiều cao lớn nhất của tháp vòng, biết rằng vòng j chỉ có thể đặt trên vòng i khi bán kính ngoài của vòng j lớn hơn bán kính trong của vòng i; và nhỏ hơn hoặc bằng bán kính ngoài của vòng i.
  • Tìm giá trị phần tử thứ k của mảng, sau một loạt các truy vấn thay đổi giá trị các phần tử theo đoạn.
  • Đếm tổng số thừa số nguyên tố của i + 1 phần tử đầu tiên và tìm tất cả “số nguyên tố ngược” có 7 chữ số trong mảng.
  • Tìm tất cả dãy con khác biệt không giảm. Với mỗi dãy con như vậy, tìm dãy “không vượt quá” dãy con này.
  • Tìm tổng khoảng cách nhỏ nhất bất kể thời điểm của n cặp điểm trên trục Ox, biết rằng điểm thứ i di chuyển trên trục Ox với vận tốc vi.

    • Tìm hiểu các thuật toán giải quyết bài toán Lowest Common Ancestor và cách áp dụng chúng vào các bài toán thực tế.

    Ứng dụng vào các bài toán như:

  • Tìm số đường đi đi qua một cạnh trên đồ thị dạng cây.
  • Tìm tổng khoảng cách nhỏ nhất đi từ c đến a và b trên đồ thị gồm n đỉnh và n cạnh 1 chiều.
  • Tìm đường đi ngắn nhất giữa đỉnh trên đồ thị dạng cây.
    • Kiểm tra cuối kỳ.