Vào lúc 8h tối thứ tư tuần này (08/06/2022), mình sẽ tổ chức buổi trình bày thứ hai trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022.
Chủ đề của buổi thứ hai là "Đánh giá hiệu quả thuật toán." Để có thể theo dõi bài trình bày này, bạn cần nắm được cách chứng minh mệnh đề chứa dấu ~\forall, \exists~ và mệnh đề "nếu ... thì ..." (đã được trình bày ở bài đầu tiên), nắm được khái niệm thuật toán, và biết một số bất đẳng thức đơn giản như ~\forall x \in \mathbb{R}: x^2 \geq 0~ và bất đẳng thức trung bình cộng - trung bình nhân.
Ở buổi trình bày này, các bạn sẽ được làm quen với:
- Cách phân tích độ phức tạp của một thuật toán.
- Biểu diễn độ phức tạp bằng kí pháp chữ ~O~ lớn. Sử dụng kí pháp chữ ~O~ lớn để đánh giá xem thuật toán có chạy đủ nhanh trong thời gian quy định hay không.
- Một số kĩ thuật tăng tốc độ chạy của thuật toán như lợi dụng hằng số nhỏ của ~\sum i^k~, sử dụng
bitset
, hai con trỏ, và chia căn đơn giản.
Đị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 2.5 - Cách lập trình một thuật toán chia căn
https://drive.google.com/file/d/1fKN0vN8ZAAxeZL32MBN4B7lLU7TYuDrh/view?usp=sharing
Qua video này, hy vọng các bạn không những nắm được cách lập trình để giải bài toán được giới thiệu trong tập 2 mà còn thu thập được một số mẹo khi lập trình, cũng như cách kiểm thử một chương trình trong các kì thi chấm offline như kì thi Học sinh giỏi thành phố, quốc gia, ...
Các bạn có thể vào link sau, rồi vào thư mục Sample code để tìm các đoạn code được mình viết trong tập 2.5
https://drive.google.com/drive/folders/19vgJNUe3cNR5loLdyYV-n6oYaVEAw8Jp?usp=sharing