bvd Live! Tập 3 - Chia để trị (phần 1)
đã đăng vào 11, Tháng 6, 2022, 22:45
Vào lúc 8h tối thứ ba (14/06/2022), mình sẽ tổ chức buổi trình bày thứ ba trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022.
Chủ đề của tập 3, tập 4, và có thể là tập 5 là "Chia để trị."
Để có thể theo dõi được bài trình bày này, các bạn cần nắm được phương pháp chứng minh quy nạp, cách phân tích độ phức tạp tính toán, cách viết hàm đệ quy. Nếu được thì các bạn cũng nên tìm hiểu trước về hàm lô-ga-rít.
Ở buổi trình bày này, các bạn sẽ được làm quen với:
- Hàm lô-ga-rít và ứng dụng trong một số bài tập tin học.
- Tìm kiếm nhị phân và ứng dụng trong các bài toán tìm giá trị lớn nhất hoặc nhỏ nhất.
- Cách tính nhanh ~x^n~ với ~n~ lớn.
- Thuật toán Mergesort để sắp xếp dãy số trong ~O(n\log{n})~ trong trường hợp xấu nhất.
- Cách giải bài toán cặp điểm gần nhất (và bài toán đếm số cặp nghịch thế nếu có thời gian)
- Phân tích độ phức tạp tính toán của một thuật toán sử dụng phương pháp Chia để trị bằng phương pháp hình chữ nhật.
Nội dung của một số bài trình bày tiếp theo:
- Cây phân đoạn (Segment Tree) dưới góc nhìn của phương pháp Chia để trị.
- Cách nhân nhanh hai đa thức trong ~O(n^{1.6})~ và ứng dụng.
- Giới thiệu sơ qua về phương pháp Chia để trị trên cây và Chia để trị trên đa giác.
Địa điểm tham gia livestream: Kênh Voice general của server Discord From VNOI with love. Các bạn có thể tham gia server qua link https://discord.gg/WDgKQcHjQC
Các bạn có thể xem lại các tư liệu của bài trình bày (gồm video bài trình bày, slides đã chỉnh sửa, hình ảnh được sử dụng và nháp) tại đây.
Bình luận
Tập 3.5 - Cài đặt thuật toán Mergesort và thuật toán tìm cặp điểm gần nhất.
Mình đã tải lên thư mục "Coding videos" (truy cập bằng cách vào link trên) ba video:
Cài đặt thuật toán Mergesort để giải bài SORTSTRING.
Mô phỏng thuật toán Mergesort
Cài đặt thuật toán giải bài toán tìm cặp điểm gần nhất bằng phương pháp Chia để trị (bao gồm một số lỗi sai cần tránh và một số mẹo khi đọc / in số thực trong C++)
Nếu code trong video không rõ, bạn có thể xem code mẫu trong thư mục "Sample code."
Nhưng mà "tại đây" không có link mà anh.
Anh vừa mới cập nhật link.