Chuyện thi ACM/ICPC và học thuật toán

Chuyện thi ACM/ICPC và học thuật toán

Đồng thời không phải là song song – Concurrency is not Parallelism.

ACM/ICPC là gì?

ACM-ICPC (ACM International Collegiate Programming Contest ) là cuộc thi lập trình quốc tế lâu đời và danh giá nhất dành cho sinh viên các trường đại học và cao đẳng trên toàn cầu. Đây là một cơ hội cho sinh viên các trường đại học và cao đẳng thể hiện và rèn luyện các kỹ năng giải quyết vấn đề và lập trình. Sau khi các trải qua các vòng chung kết khu vực, các đội tuyển xuất sắc nhất khắp các châu lục sẽ được chọn ra để tham dự vòng chung kết toàn cầu ACM-ICPC World Final, nhằm mục đích tìm ra đội tuyển vô địch thế giới. (Theo Wikipedia.org)

ACM-ICPC thi ở đâu?

Thành phố Nha Trang.

Ở Việt Nam kỳ thi ACM/ICPC toàn quốc (khu vực Châu Á Thái Bình Dương) thường được tổ chức cùng với kỳ thi Olympic tin học sinh viên. Năm 2015  kỳ thi diễn ra ở Hà Nội, 2016 ở Nha Trang, và năm tới là Thành phố Hồ Chí Minh.

Sinh viên làm sao để được dự thi?

Để được dự thi bạn phải có kiển thức thuật toán nhất định, ngoài ra trong đội của bạn phải có người đọc hiểu tiếng anh. Bạn phải vượt qua các kỳ thi sơ loại ba miền Bắc  – Trung – Nam, sau đấy đến vòng toàn quốc online, tiếp theo đến  vòng ACM/ICPC khu vực Châu Á Thái Bình Dương. Và đội sáng giá nhất sẽ tham dự ACM-ICPC World Final để tìm ra nhà vô địch thế giới.

Bạn được gì sau khi thi?

Với áp lực thi chỉ trong vòng 5 giờ đồng hồ, cùng với việc cả đội 3 người chỉ được sử dụng duy nhất một máy tính, đội bạn sẽ phải đề ra những chiến thuật để có thể làm bài tốt nhất. Sau khi thi đội bạn sẽ gắn kết hơn. Khổng Tử đã nói “Ba người cùng đi tất sẽ có người có thể làm thầy của ta”, bạn sẽ học được rất nhiều từ những người bạn. Bạn còn được nhận giấy chứng nhận tham dự kỳ thi. Các nhà tuyển dụng trên toàn thế giới đánh giá cao ứng viên có giấy chứng nhận này.

ACM/ICPC là một kỳ thi giúp thí sinh đánh giá được kỹ năng lập trình, cũng như tư duy thuật toán của bản thân.

Kỳ thi ACM/ICPC yêu cầu rất cao về thuật toán. Không có thuật toán không thi được!

Tại sao phải học thuật toán (một cách cẩn thận)

Có một người thầy nói với tôi rằng người lập trình cũng như người mãi võ vậy. Nếu như công nghệ là 1 môn võ, thì thuật toán phía sau chính là nội công. Một môn võ có thể học dăm bữa nửa tháng, nhưng tu luyện nội công thì cần rất nhiều thời gian. Việc học một môn võ mới sẽ đơn giản đi rất nhiều khi có nội công. Tất nhiên không nội công vẫn học võ được, và không có tư duy thuật toán vẫn học được công nghệ nhưng khó để thành lập trình viên giỏi. Một lập trình viên giỏi không thể không hiều đằng sau dòng code mình vừa viết là cái gì. Thực tế sinh viên CNTT Việt Nam hiện nay thường chú trọng vào học công nghệ, thực hành ứng dụng mà quên đi bản chất thực sự. Ví dụ như là không phải ai hiểu Quicksort trong thư viện hay dùng. Ngay cả người hiểu Quicksort chưa chắc đã viết lại đúng ngay từ lần code đầu tiên.

Nhân chuyện học thuật toán, nên học thuật toán như thế nào?

Tôi là sinh viên năm hai và tôi không nói tôi giỏi về thuật toán, nhưng tôi biết cần phải làm gì để có nội công cao hơn, ngoài việc tìm hiểu, học các công nghệ mới tôi vẫn dành thời gian để trau dồi nội công. Ban đầu tôi đi cơ bản từ sắp xếp, tìm kiếm, sau đấy học quay lui, vét cạn, rồi học đồ thị hay quy hoạch động… Dần dần đến các bài toán phức tạp hơn cần cần kiến thức nhiều hơn. Và một điều lưu ý rằng nếu muôn học tốt thuật toán thì bạn phải ít nhiều biết toán học. Sẽ có nhiều ý kiến cho rằng việc học thuật toán khô khan, nhưng với tôi thì không nghĩ vậy. Không có thứ gì khô khan, chỉ là mình có thấy được sự thú vị từ nó hay không mà thôi.

Tôi lấy ví dụ một bài toán:

Sắp 8 quân hậu vào bàn cờ vua 8×8 sao cho không có quân nào ăn nhau. Nếu với những quân cờ và bàn cơ tôi nghĩ bạn “khó” tìm ra lời giải dù chỉ là một cách, trong khi thuật toán có thể giúp ta tìm ra tất cả 92 cách sắp khác nhau.


Nếu bạn bắt đầu học thì hãy bắt đầu từ những bài toán cơ bản sắp xếp tìm kiếm, đọc các cuốn sách cơ bản cho người mới bắt đầu như: cấu trúc dữ liệu và giải thuật (Lê Minh Hoàng), Tài Liệu Chuyên Tin (GS Hồ Sĩ Đàm)… Và đừng quên làm mới nó lên để không cảm thấy khô khan.

Và cuối cùng tôi xin gửi tặng các bạn tập đề ACM/ICPC vòng online năm 2016 tại đây.
Bài viết không thể tránh được sai sót, mong được bạn đọc góp ý.