✨Lập trình thi đấu

nhỏ|300x300px| [[Petr Mitrichev (trái) và Gennady Korotkevich (phải), hai lập trình viên thi đấu nổi tiếng trong một cuộc thi.]] Lập trình thi đấu () là một môn thể thao trí tuệ trong đó những người tham gia sẽ cố gắng lập trình theo các yêu cầu được cung cấp. Các cuộc thi thường được tổ chức qua Internet hoặc mạng cục bộ. Những người tham gia được gọi là lập trình viên thi đấu (sport programmers). Lập trình thi đấu được công nhận và bảo trợ bởi nhiều công ty phần mềm và Internet đa quốc gia, chẳng hạn như Google và Facebook.

Trong một cuộc thi lập trình, bên tổ chức thường đưa ra một tập hợp các vấn đề logic hoặc toán học, còn được gọi là câu đố hoặc thử thách cho các thí sinh (số lượng thí sinh có thể là vài chục người hoặc thậm chí hàng trăm đến hàng ngàn). Thí sinh được yêu cầu viết các chương trình máy tính có khả năng giải quyết các vấn đề này. Việc đánh giá chủ yếu dựa trên số vấn đề đã giải quyết và thời gian đã bỏ ra để hoàn thành lời giải, nhưng cũng có thể bao gồm các yếu tố khác (chất lượng của kết quả đầu ra, thời gian thực thi, sử dụng bộ nhớ, kích thước chương trình, v.v.).

Lịch sử

Một trong những cuộc thi lâu đời nhất được biết đến là International Collegiate Programming Contest (ICPC) bắt đầu từ những năm 1970 và đã mở rộng tới 88 quốc gia trong phiên bản năm 2011.

Từ năm 1990 đến 1994, Owen Astrachan, Vivek Khera và David Kotz đã tổ chức một trong những cuộc thi lập trình phân tán dựa trên Internet đầu tiên, lấy cảm hứng từ ICPC.

Sự quan tâm đến lập trình thi đấu đã phát triển mạnh kể từ năm 2000 với hàng chục nghìn người tham gia (xem Các cuộc thi nổi bật), điều này liên quan chặt chẽ đến sự phát triển của Internet, giúp tổ chức cuộc thi quốc tế trực tuyến và loại bỏ các giới hạn địa lý.

Tổng quan

Mục tiêu của lập trình thi đấu là viết mã nguồn chương trình máy tính để giải quyết các vấn đề được đưa ra. Đa số các vấn đề xuất hiện trong các cuộc thi lập trình liên quan đến toán học hoặc logic. Các vấn đề thường thuộc một trong những loại sau: tổ hợp, lý thuyết số, lý thuyết đồ thị, lý thuyết trò chơi sử dụng thuật toán, hình học tính toán, phân tích chuỗi và cấu trúc dữ liệu. Các vấn đề liên quan đến lập trình ràng buộc và trí tuệ nhân tạo cũng phổ biến trong một số cuộc thi.

Bất kể loại vấn đề, quá trình giải quyết một vấn đề có thể chia thành hai bước chính: xây dựng một thuật toán hiệu quả và triển khai thuật toán bằng một ngôn ngữ lập trình phù hợp (các ngôn ngữ lập trình được phép dùng khác nhau giữa các cuộc thi). Đây là hai kỹ năng thường được kiểm tra nhiều nhất trong các cuộc thi lập trình.

Ở hầu hết cuộc thi, việc đánh giá được thực hiện tự động bởi các máy chủ của bên tổ chức, thường được gọi là trình chấm hay hệ thống chấm bài (judge). Các lời giải được nộp bởi thí sinh sẽ được chạy trên trình chấm với một tập hợp các test case (thường là bí mật). Thông thường, trình chấm sẽ đánh giá theo nguyên tắc "đúng hoặc sai hoàn toàn", có nghĩa rằng một lời giải được chấp nhận ("Accepted") chỉ khi nó đạt kết quả tốt trên tất cả test case được chạy bởi trình chấm, và nếu không sẽ bị từ chối. Tuy nhiên, một số cuộc thi có thể cho phép việc chấm điểm theo phần, dựa trên số lượng test case đúng, chất lượng của kết quả, hoặc một số tiêu chí khác đã được chỉ định. Một số cuộc thi khác chỉ yêu cầu thí sinh nộp kết quả tương ứng với dữ liệu đầu vào đã được cung cấp, trong trường hợp này trình chấm chỉ cần phân tích kết quả được nộp.

Các hệ thống chấm bài trực tuyến (online judge) là môi trường mà ở đó diễn ra quá trình kiểm tra. Các hệ thống chấm bài trực tuyến có danh sách xếp hạng cho thấy người dùng có số lượng lời giải được chấp nhận nhiều nhất và/hoặc thời gian thực thi ngắn nhất cho một vấn đề cụ thể.

Các cuộc thi nổi bật

Cuộc thi thuật toán

Phần lớn cuộc thi ở trên thường được tổ chức thành nhiều vòng. Các cuộc thi thường khởi đầu bằng và kết thúc ở vòng chung kết tại chỗ. Những thí sinh dẫn đầu tại IOI và ICPC sẽ nhận được huy chương vàng, bạc và đồng. Trong các cuộc thi khác, giải thưởng tiền mặt được trao cho những người hoàn thành có thứ hạng cao nhất. Các cuộc thi cũng thu hút sự quan tâm của các nhà tuyển dụng từ nhiều công ty phần mềm và Internet, những công ty này thường chiêu mộ các thí sinh bằng những lời mời làm việc tiềm năng.

Trí tuệ nhân tạo và học máy

• Kaggle – cuộc thi về khoa học dữ liệu và học máy.
• CodeCup – cuộc thi AI về board game được tổ chức hàng năm kể từ năm 2003. Quy luật của trò chơi được công bố vào tháng 9 và giải đấu cuối cùng được tổ chức vào tháng 2.
• Google AI Challenge – cuộc thi dành cho sinh viên diễn ra từ năm 2009 đến 2011.
• Halite – Một thử thách lập trình AI được tài trợ bởi Two Sigma, Cornell Tech, and Google.
• Russian AI Cup – cuộc thi lập trình trí tuệ nhân tạo mở.
• CodinGame – tổ chức các cuộc thi lập trình bot theo mùa.

Cuộc thi tập trung vào công nghệ nguồn mở

• Danh sách có thể không đầy đủ

Nền tảng trực tuyến

Cộng đồng lập trình trên khắp thế giới đã xây dựng và duy trì nhiều nguồn tài nguyên trên internet phục vụ cho lập trình thi đấu. Họ cung cấp các cuộc thi độc lập với giải thưởng nhỏ hoặc không. Ngoài ra, các bài toán đã được lưu trữ trước đây cũng là nguồn tài liệu phổ biến để đào tạo về lập trình thi đấu. Một số tổ chức thường xuyên mở các cuộc thi lập trình, bao gồm:

Lợi ích và chỉ trích

Tham gia vào các cuộc thi lập trình có thể tăng sự hứng thú của sinh viên đối với việc nghiên cứu ngành khoa học máy tính. Những kỹ năng mà họ thu được thông qua các cuộc thi lập trình giống như ICPC cũng cải thiện cơ hội nghề nghiệp, bởi vì chúng giúp vượt qua các "cuộc phỏng vấn về kỹ thuật", thường đòi hỏi ứng viên giải quyết các vấn đề lập trình và thuật toán phức tạp ngay tại chỗ.

Tuy vậy cũng có những sự chỉ trích về lập trình thi đấu, đặc biệt từ các nhà phát triển phần mềm chuyên nghiệp. Ngoài ra, vì chỉ cung cấp các câu đố thuật toán nhỏ với lời giải tương đối ngắn, các cuộc thi lập trình như ICPC và IOI có thể không dạy mọi người những kỹ năng tốt trong ngành kỹ thuật phần mềm, vì các dự án phần mềm trong thực tế thường có hàng nghìn dòng mã và được phát triển bởi các nhóm lớn trong thời gian dài. Peter Norvig đã đề cập rằng dựa trên dữ liệu có sẵn, việc giành chiến thắng trong các cuộc thi lập trình có mối tương quan tiêu cực với hiệu suất của một lập trình viên trong công việc của họ tại Google (mặc dù các người chiến thắng trong các cuộc thi có cơ hội cao được tuyển dụng). Sau đó, Norvig tuyên bố rằng tương quan này chỉ được quan sát trên một tập dữ liệu nhỏ, nhưng không thể xác minh sau khi xem xét một tập dữ liệu lớn hơn.

Một quan điểm khác là thay vì "lãng phí" thời gian để thi đấu quá nhiều, giải các bài toán đã có lời giải, các lập trình viên có tiếng nên đầu tư thời gian của họ vào việc giải quyết các vấn đề trong thực tế.

Đọc tiếp

• Halim, S., Halim, F. (2013). Competitive Programming 3: The New Lower Bound of Programming Contests. Lulu.
• Laaksonen, A. (2017). Guide to Competitive Programming (các chủ đề dành cho sinh viên đại học trong ngành khoa học máy tính). Cham: Springer International Publishing.
• Xu, X. (2020) The development, prosperity and decline of Olympic in Informatics. Xuất bản trực tuyến.
• Kostka, B. (2021). Sports programming in practice. Đại học Wrocław.