ĐỀ CƯƠNG CHI TIẾT KHÓA HỌC
Tìm hiểu thuật toán Knuth-Morris-Pratt tìm vị trí chuỗi T xuất hiện trong chuỗi S.
Ứng dụng vào các bài toán sau:
- Xác định cách chia xâu S thành nhiều xâu con bằng nhau nhất.
- Đếm số lần xuất hiện của một mẫu kích thước X × Y trong ma trận N × M.
- Tìm xâu ngắn nhất chứa cả 3 xâu s1, s2 và s3.
Tìm hiểu cách xây dựng mảng Z-Function của một chuỗi và ứng dụng nó giải quyết các bài toán về chuỗi.
Ứng dụng vào các bài toán sau:
- So khớp chuỗi, tìm vị trí chuỗi P xuất hiện trong chuỗi S.
- Đếm số xâu con phân biệt của một chuỗi.
- Tìm số cách chọn K xâu con liên tiếp bằng nhau của một chuỗi.
- Tìm chu kỳ nhỏ nhất của một chuỗi.
Tìm hiểu cấu trúc dữ liệu cây tiền tố dùng để lưu trữ danh sách các phần tử trên cây.
Ứng dụng vào các bài toán sau:
- Lưu trữ một lượng từ ngữ lớn.
- Gợi ý tìm kiếm trên các công cụ tìm kiếm.
- Chức năng Auto Complete.
- Tìm kiếm nhanh các chuỗi có tiền tố là chuỗi T.
- Tìm từ xuất hiện nhiều lần nhất và có tiền tố là chuỗi T.
Một số bài tập ôn tập:
- Tính tổng P = C(N, 0)−C(N, 1)+C(N, 2)−C(N, 3)+...+C(N, N).
- Đếm số lượng hình chữ nhật con trong ma trậm N × M sao cho có 1 cách sắp xếp trên các xâu trên hàng và cột đều là xâu đối xứng.
- Kiểm tra xem 2 chuỗi có cùng số lượng xâu con phân biệt hay không.
Tìm hiểu cấu trúc dữ liệu mảng hậu tố - một loại cấu trúc dạng mảng rất mạnh để giải quyết các bài toán xử lý chuỗi ; thuật toán Prefix Doubling và cách tối ưu hóa thuật toán này để xây dựng mảng hậu tố.
Ứng dụng vào các bài toán sau:
- Tìm độ dài tiền tố chung lớn nhất giữa các hậu tố liên tiếp (Longest Common Prefix)
- Tìm chuỗi con T dài nhất xuất hiện ít nhất 2 lần trong chuỗi (Longest Repeated Substring).
- Tìm xâu con chung dài nhất giữa hai chuỗi.
- Tìm xâu con chung dài nhất giữa K chuỗi.
- Đếm số lượng xâu con phân biệt của một chuỗi.
- Tìm xâu con trong S mà có thứ tự từ điển thứ k.
- Đếm số lượng các xâu con phân biệt bắt đầu bằng mỗi chữ cái.
Tìm hiểu thuật toán Manacher ứng dụng vào các bài toán xâu con đối xứng.
Ứng dụng vào các bài toán sau:
- Tìm xâu con đối xứng dài nhất trong một chuỗi (Longest Palindromic Substring).
- Tìm và in ra số lượng xâu con là xâu đối xứng dài nhất của một chuỗi.
- Đếm số lượng xâu con đối xứng phân biệt của một chuỗi.
- Đếm số lượng xâu con đối xứng tạo thành số nguyên chia hết cho 3 trong một chuỗi gồm các chữ số.
Tìm hiểu về số học và lý thuyết số, nghịch đảo nhân modulo. Một số khái niệm về tổ hợp, số tổ hợp, số hoán vị, nghịch đảo nhân.
Tổ hợp học có ứng dụng rộng rãi trong các lĩnh vực như xác suất, thống kê, lý thuyết đồ thị, lý thuyết thông tin, và trong nhiều bài toán thực tế như xếp ba lô, xếp hàng, tối ưu hóa, mã hoá, và nhiều lĩnh vực khá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
Tìm hiểu các khái niệm từ cơ bản về tính xác suất như không gian mẫu, biến cố, quy tắc nhân, quy tắc cộng,… đến nâng cao như biến ngẫu nhiên, giá trị kỳ vọng, tính tuyến tính của kỳ vọng,…
Ứng dụng vào các bài toán sau:
- Tính xác suất để tung N đồng xu để được chính xác K đồng xu ra mặt đầu.
- Chọn ngẫu nhiên một số p trong đoạn [pL , pR], và một số v trong đoạn [vL , vR]. Tính xác suất để đoạn [min(v, p), max(v, p)] có đúng k số may mắn.
- Tính xác suất để quả banh cuối cùng sau các thủ thuật của nhà ảo thuật là màu đen.
Tìm hiểu nguyên lý bao hàm – loại trừ dùng để tính kích thước tập hợp gộp (hợp) của các tập hợp con.
Ứng dụng vào các bài toán sau:
- Tính tổng các phần tử trong đoạn [L, R] trên mảng.
- Đếm số lượng số nguyên trong đoạn [L, R] mà nguyên tố cùng nhau với N.
- Đếm số bộ nghiệm thỏa mãn phương trình x1 + x2 + ⋯ + xm = k.
- Đếm số lượng hoán vị tốt của n cặp số nguyên cho trước.
- Đếm số bộ 4 số có UCLN bằng 1 trên dãy gồm N số.
- Tìm các số từ 1 đến N không chia hết cho bất kỳ số nào trong dãy cho trước.
- Đếm số lượng các mảng con nguyên tố cùng nhau trên mảng.
Tìm hiểu về dãy số Catalan, cách xây dựng dãy số Catalan và các ứng dụng của dãy số này.
Ứng dụng vào các bài toán sau:
- Đếm số cây BST khác nhau với các node là các số « perfect power » nằm trong đoạn [a, b], biết rằng số m là « perfect power » khi tồn tại x > 1 và y > 1, sao cho m = xy.
- Đếm số cách để một nhóm N người xếp thành vòng tròn có thể bắt tay với nhau mà không đè lên nhau.
- Tìm số hoán vị phân biệt tăng dần của N số.
Một số bài tập ôn tập:
- Đếm số các số trong khoảng [n, m] sao cho số đó không chia hết cho a hoặc (a+d) hoặc (a+2d) hoặc (a+3d) hoặc (a+4d).
- Tính giá trị dự đoán số người đang đứng trên thang cuốn ở thời điểm thứ t.
- Tính xác suất con mã sau k nước đi vẫn ở trên bàn cờ.
Tìm hiểu các phép toán trên ma trận như phép nhân ma trận, phép lũy thừa, … và các ứng dụng các phép toán này trong lập trình thi đấu.
Ứng dụng vào các bài toán như:
- Tính số Fibonacci thứ N với độ phức tạp O(logn).
- Tính số Tribonacci thứ N với độ phức tạp O(logn).
- Tính nhanh các bài toán mà Fn có thể tính bằng đa thức: Fn= ai * Fn-1.
Tìm hiểu, phân tích các dạng bài tập cơ bản nhất trong lý thuyết trò chơi.
Ứng dụng vào các bài toán sau:
- Cho biết người chơi nào sẽ thắng trong các trò chơi.
- Biết luật trò chơi như sau : A và B sẽ thay phiên lấy 1 hoặc nhiều số liên tiếp từ bên trái hoặc bên phải trong mảng. Tính chêch lệch tổng các số nguyên lấy ra của A và B.
Tìm hiểu, phân tích các dạng bài tập khác trong lý thuyết trò chơi.
Ứng dụng vào các bài toán sau:
Cho biết người chơi nào sẽ thắng trong các trò chơi.
- Có 2 đống sỏi với số sỏi lần lượt là X và Y (X, Y ≤1018). Ở mỗi lượt, người chơi sẽ chọn 1 giá trị k, lấy 2k viên sỏi từ 1 đống bất kì, đem k viên bỏ vào đống còn lại và k viên thì bỏ đi. Alice và Brown chơi luân phiên nhau, Alice chơi trước, cả 2 đều chơi theo cách tối ưu.
- Có N túi bi, túi thứ i chứa 𝑎𝑖 viên bi có màu i. Alice và Bob chơi luân phiên lần lượt, Alice chơi trước. Tại mỗi lượt, người chơi sẽ lấy ra một số bi bất kì từ các túi sao cho các viên bi phải khác màu nhau. Người chơi không thể thực hiện bước đi sẽ là người thua cuộc.
Kiểm tra cuối kỳ.
