การเขียนโปรแกรมเชิงแข่งขัน

จากวิกิพีเดีย สารานุกรมเสรี

การเขียนโปรแกรมเชิงแข่งขัน เป็นการเขียนโปรแกรมเพื่อแก้ไขโจทย์ปัญหาทางตรรกะหรือคณิตศาสตร์ภายใต้ข้อจำกัดบางอย่างเพื่อให้ได้คำตอบออกมา โจทย์ปัญหาส่วนใหญ่จะมีคำตอบที่แน่นอนอยู่แล้ว การเขียนโปรแกรมนี้ไม่ได้มีจุดประสงค์ในการนำโปรแกรมมาใช้งานจริง แต่เป็นการเขียนเพื่อความสนุกและวัดทักษะในการแก้ไขปัญหา อาจถือได้ว่าเป็นกีฬาความคิดรูปแบบหนึ่ง โดยมากแล้วการเขียนโปรแกรมเชิงแข่งขันจะมีขึ้นในการแข่งขันเขียนโปรแกรมซึ่งส่วนใหญ่จะจัดขึ้นผ่านทางอินเทอร์เน็ตหรือไม่ก็เครือข่ายท้องถิ่น และมักจะมีบริษัทซอฟต์แวร์และอินเทอร์เน็ตเป็นผู้สนับสนุน เช่น กูเกิล[1][2] เฟซบุ๊ก[3] และไอบีเอ็ม[4]

การตัดสินผลโดยทั่วไปจะดูที่จำนวนโจทย์ที่ทำได้กับเวลาที่ใช้ในการเขียนโปรแกรมรวมทั้งหมด และอาจจะมีปัจจัยอื่น ๆ ที่นำมาพิจารณาด้วย เช่น ขนาดของโปรแกรม เวลาในการทำงานของโปรแกรม หรือการเทียบคำตอบกันระหว่างผู้เข้าแข่งขันด้วยกันเอง

ประวัติ[แก้]

การเขียนโปรแกรมเชิงแข่งขันเป็นกีฬาที่เพิ่งเกิดขึ้นไม่นานเมื่อเทียบกับกีฬาความคิดชนิดอื่น ๆ เนื่องจากสาขาวิทยาการคอมพิวเตอร์ก็เป็นสาขาที่เพิ่งเกิดขึ้นไม่นานเมื่อเทียบกับสาขาวิทยาศาสตร์อื่น ๆ เช่นกัน หนึ่งในการแข่งขันที่เก่าแก่ที่สุดคือ ACM ICPC ซึ่งเริ่มต้นแข่งขันขึ้นในทศวรรตที่ 1970 ปัจจุบันการแข่งขันดังกล่าวมีประเทศเข้าร่วมกว่า 90 ประเทศแล้ว[5]

ความสนใจในการเขียนโปรแกรมเชิงแข่งขันเพิ่มขึ้นอย่างรวดเร็วหลังปี 2000[ต้องการอ้างอิง] ซึ่งก็เกิดขึ้นจากการที่อินเทอร์เน็ตเริ่มเป็นที่แพร่หลาย ส่งผลให้สามารถจัดการแข่งขันออนไลน์ได้โดยไม่มีปัญหาด้านสถานที่

ภาพรวม[แก้]

เป้าหมายของการเขียนโปรแกรมเชิงแข่งขันคือการเขียนและส่งรหัสต้นฉบับของโปรแกรมคอมพิวเตอร์เพื่อแก้ปัญหาต่าง ๆ ที่ผู้ออกโจทย์กำหนดให้ ปัญหาที่ใช้ในการแข่งขันจะเกี่ยวกับตรรกะหรือคณิตศาสตร์ เช่น คณิตศาสตร์เชิงการจัด ทฤษฎีจำนวน ทฤษฎีกราฟ เรขาคณิต สตริง โครงสร้างข้อมูล[6][7] และในการแข่งขันบางรายการจะนิยมปัญหาเกี่ยวกับปัญญาประดิษฐ์เป็นอย่างมาก

กระบวนการในการแก้โจทย์ปัญหาจะประกอบไปด้วย 2 ขั้นตอน คือการออกแบบขั้นตอนวิธีที่ใช้ในการแก้ปัญหา ซึ่งจะต้องให้ผลลัพธ์ถูกต้องและมีประสิทธิภาพเพียงพอภายใต้ข้อจำกัดที่ให้มา ซึ่งส่วนมากก็ได้แก่พื้นที่หน่วยความจำที่มีจำกัด และเวลาในการทำงานที่จำกัด อีกขั้นตอนในการแก้โจทย์ปัญหาก็คือการอิมพลีเมนต์โปรแกรมจากขั้นตอนวิธีที่คิดขึ้นมา โดยส่วนใหญ่แล้วผู้จัดการแข่งขันจะจำกัดภาษาโปรแกรมที่ให้ใช้ในการแข่งขันไว้เพียงบางภาษาเท่านั้น[8]

กระบวนการตรวจโปรแกรมของผู้เข้าแข่งขันจะตรวจอัตโนมัติด้วยโปรแกรมของผู้จัดการแข่งขัน โดยโปรแกรมทั้งหมดที่ผู้เข้าแข่งขันส่งมาให้ตรวจจะถูกนำมาทดสอบกับชุดทดสอบหลาย ๆ ชุดที่เป็นความลับ หากผลลัพธ์ที่ได้จากโปรแกรมถูกต้องทั้งหมดก็จะถือว่าโปรแกรมของผู้เข้าแข่งขันนั้นถูกต้อง กล่าวคือเป็นการทดสอบแบบกล่องดำนั่นเอง และด้วยการตรวจโปรแกรมเช่นนี้จึงทำให้มีผู้ไม่เห็นด้วยที่จะรวมการแข่งขันเขียนโปรแกรมคอมพิวเตอร์เป็นหนึ่งในการแข่งขันวิทยาศาสตร์[9]

การให้คะแนนก็มีหลากหลายรูปแบบ เช่น โปรแกรมต้องทำงานถูกต้องสำหรับทุก ๆ ชุดทดสอบจึงจะถือว่าผ่าน หรือบางการแข่งขันอาจมีการให้คะแนนเพียงบางส่วนในกรณีที่โปรแกรมให้ผลลัพธ์ถูกต้องในบางชุดทดสอบเท่านั้น หากโจทย์ปัญหาไม่ใช่ปัญหาค่าดีสุดหรือปัญหาที่มีคำตอบเพียงรูปแบบเดียว อาจมีการให้คะแนนโดยนำคำตอบมาเทียบกับคำตอบผู้เข้าแข่งขันคนอื่นหรือคำตอบของผู้จัดการแข่งขันเองว่าคำตอบของใครดีกว่า และตัดเป็นคะแนนออกมา นอกจากนี้บางการแข่งขันไม่จำเป็นต้องส่งรหัสต้นฉบับของโปรแกรมเลยด้วยซ้ำ แต่ให้ส่งคำตอบสำหรับข้อมูลนำเข้าที่กำหนดให้แทน ซึ่งการจะได้คำตอบนั้นส่วนใหญ่ก็ต้องเขียนโปรแกรมช่วยหาคำตอบอยู่ดี[10]

ประเภท[แก้]

การเขียนโปรแกรมเชิงแข่งขันอาจแบ่งได้เป็น 3 ประเภทคือ การแข่งขันนอกสถานที่ การแข่งขันออนไลน์ และระบบตรวจออนไลน์ โดยการแข่งขันนอกสถานที่ส่วนมากจะมีรางวัลตอบแทน ในขณะที่อีก 2 ประเภทมักจะไม่มีรางวัลตอบแทน อย่างไรก็ดี การที่ผู้เข้าแข่งขันสามารถทำคะแนนได้ดีหรือแก้โจทย์ปัญหาได้เป็นจำนวนมากก็จะเป็นการสร้างโอกาสและดึงดูดบริษัทคอมพิวเตอร์หรืออินเทอร์เน็ตทั้งหลายให้เข้ามาจ้างงานได้

การแข่งขันนอกสถานที่[แก้]

การแข่งขันนอกสถานที่คือการแข่งขันที่ผู้เข้าแข่งขันจะต้องเดินทางไปยังสถานที่ซึ่งผู้จัดการแข่งขันเตรียมไว้ให้และเข้าแข่งขัน โดยส่วนมากแล้วการแข่งขันเหล่านี้จะมีรางวัลแก่ผู้เข้าร่วมแข่งขัน เช่น เงิน หรือรางวัลเป็นเหรียญ ตัวอย่างการแข่งขันประเภทนี้คือ

  • IOI หรือ คอมพิวเตอร์โอลิมปิก เป็นหนึ่งในการแข่งขันที่เก่าแก่ที่สุด โดยผู้เข้าแข่งขันจะเป็นผู้แทนของแต่ละประเทศจำนวน 4 คน จำกัดให้ผู้เข้าแข่งขันเป็นนักเรียนระดับมัธยมศึกษาเท่านั้น[11]
  • ACM ICPC เป็นหนึ่งในการแข่งขันที่เก่าแก่ที่สุด ผู้เข้าแข่งขันจะต้องเป็นนักเรียนระดับมหาวิทยาลัย โดยแข่งเป็นทีม แต่ละทีมมีสมาชิก 3 คน สนับสนุนโดยไอบีเอ็ม[5]
  • Topcoder Open เป็นการแข่งขันที่เริ่มในปี 2004 โดยท็อปโค้ดเดอร์

ทั้งนี้ การแข่งขันนอกสถานที่บางรายการอาจจะมีการคัดเลือกผู้เข้าแข่งขันมาจากการแข่งขันออนไลน์ก่อน ส่วนมากจะเป็นในรายการแข่งขันที่มีผู้เข้าแข่งขันจำนวนมาก ทำให้ต้องมีการแข่งขันออนไลน์หลาย ๆ รอบเพื่อคัดเลือกผู้เข้าแข่งขันให้เหลือน้อยลง และผู้เข้าแข่งขันที่ผ่านจนถึงรอบชิงชนะเลิศจะได้ไปแข่งนอกสถานที่ เช่น

  • Google Code Jam เป็นการแข่งขันที่เริ่มในปี 2003 ซึ่งทั้งจัดและสนับสนุนโดยกูเกิล[1]
  • Facebook Hacker Cup เป็นการแข่งขันที่เริ่มในปี 2011 ซึ่งทั้งจัดและสนับสนุนโดยเฟซบุ๊ก[3]

การแข่งขันออนไลน์[แก้]

การแข่งขันออนไลน์คือการแข่งขันที่ผู้เข้าแข่งขันสามารถเข้าร่วมได้ผ่านทางอินเทอร์เน็ตได้ ส่วนมากจะไม่มีรางวัลตอบแทน

  • ท็อปโค้ดเดอร์ (Topcoder) เป็นบริษัทสัญชาติสหรัฐอเมริกาซึ่งจัดการแข่งขันออนไลน์ รวมถึงทำธุรกิจในด้านการเขียนโปรแกรมด้วย การแข่งขันของท็อปโคดเดอร์มีความโดดเด่นจากระบบการแข่งขันซึ่งหลังจบการแข่งเขียนโปรแกรมจะมีการแข่งขันหาข้อผิดพลาดของผู้เข้าแข่งขันคนอื่น หากสามารถหาข้อผิดพลาดได้ก็จะได้คะแนนเพิ่มขึ้น[12]
  • โค้ดฟอร์ซ (Codeforces) เป็นเว็บสัญชาติรัซเซียซึ่งจัดการแข่งขันถี่มาก (ประมาณทุก ๆ 2 อาทิตย์) มีความโดดเด่นจากระบบการแข่งขันที่สามารถหาข้อผิดพลาดของผู้เข้าแข่งขันคนอื่นได้ตลอดระยะเวลาการแข่งขัน[13]

โดยส่วนใหญ่แล้วเว็บแข่งขันออนไลน์ก็จะมีระบบตรวจออนไลน์ด้วย โดยนำโจทย์จากการการแข่งขันออนไลน์รอบก่อน ๆ มาให้ฝึกหัด

ระบบตรวจออนไลน์[แก้]

ระบบตรวจออนไลน์คือเว็บที่รวบรวมโจทย์ต่าง ๆ ไว้เผื่อให้ฝึกหัดการเขียนโปรแกรม โจทย์อาจจะเป็นโจทย์จากการแข่งขันที่จบแล้ว หรือโจทย์ที่ตั้งใจเขียนมาลงในระบบตรวจออนไลน์โดยเฉพาะก็ได้

  • SPOJ ระบบตรวจออนไลน์สัญชาติโปแลนด์ซึ่งมีโจทย์เพื่อฝึกฝนการเขียนโปรแกรมมากมาย และมีบริการให้กับผู้จัดการแข่งขันในการจัดการแข่งขันเขียนโปรแกรมออนไลน์ด้วย
  • UVa Online Judge มีโจทย์กว่า 3,500 ข้อ มาจากการแข่งขันเขียนโปรแกรมออนไลน์ต่าง ๆ
  • Hust Virtual Judge เว็บสัญชาติจีน เป็นเว็บจำลองการแข่งขันออนไลน์เสมือนโดยไปดึงโจทย์และชุดทดสอบมาจากแหล่งต่าง ๆ[14]

ในประเทศไทย[แก้]

ในประเทศไทย การแข่งขันเขียนโปรแกรมส่วนมากโดยเฉพาะอย่างยิ่งในระดับชั้นมัธยมศึกษาเกิดจากการส่งเสริมของสถาบันส่งเสริมการสอนวิทยาศาสตร์และเทคโนโลยี (สสวท.) เพื่อผลักดันโครงการคอมพิวเตอร์โอลิมปิกของประเทศไทย ความสนใจในการเขียนโปรแกรมเชิงแข่งขันนี้เพิ่มขึ้นเป็นอย่างมากจากการที่ประเทศไทยได้เป็นเจ้าภาพในการจัดการแข่งขันคอมพิวเตอร์โอลิมปิกนานาชาติครั้งที่ 23 ในปี 2011 โดยได้มีการเปิดเว็บไซต์ระบบตรวจออนไลน์ programming.in.th[15][16] การแข่งขันออนไลน์และนอกสถานที่ IOI Thailand League 2010[17] หรือการแข่งขัน Thailand Code Jom ที่เลียนแบบการแข่งขัน Google Code Jam[18] เป็นต้น เพื่อส่งเสริมให้นักเรียนระดับชั้นมัธยมศึกษาสนใจในการเขียนโปรแกรม ส่วนในระดับชั้นมหาวิทยาลัยก็จะมีการแข่งขัน ACM ICPC ซึ่งคณะวิศวกรรมศาสตร์ของมหาวิทยาลัยต่าง ๆ มักจะเข้าร่วมด้วย[19]

อ้างอิง[แก้]

  1. 1.0 1.1 Google Code Jam (อังกฤษ)
  2. Google sposor page for TCO 2012 (อังกฤษ)
  3. 3.0 3.1 Facebook HackerCup (อังกฤษ)
  4. ACM International Collegiate Programming Contest World Finals Sponsored by IBM (อังกฤษ)
  5. 5.0 5.1 ICPC FACT SHEET - Second Release - 28 December 2012 ข้อมูลเบื้องต้นและสถิติของ ACM ICPC จัดทำในวันที่ 28 ธันวาคม 2012 (อังกฤษ)
  6. IOI Syllabus สรุปเนื้อหาที่ใช้ในการแข่งขัน IOI ซึ่งเป็นหนึ่งในการแข่งขันเขียนโปรแกรมที่เก่าแก่ที่สุด (อังกฤษ)
  7. CS 97SI: Introduction to Competitive Programming Contests - Stanford สรุปเนื้อหาที่สอนในวิชาการเขียนโปรแกรมเชิงแข่งขันของมหาวิทยาลัยสแตนฟอร์ด (อังกฤษ)
  8. ข้อมูลเบื้องต้นเกี่ยวกับคอมพิวเตอร์โอลิมปิกระหว่างประเทศ (ไทย)
  9. [1] [2] The ioi is (not) a science olympiad (อังกฤษ)
  10. ตัวอย่างเช่นการแข่งขัน Google Code Jam ดูที่รูปแบบการแข่งขันของ Google Code Jam (อังกฤษ)
  11. History - International Olympiad in Informatics ประวัติคอมพิวเตอร์โอลิมปิกโดยเว็บไซต์ทางการ (อังกฤษ)
  12. Algorithm Overview รูปแบบการแข่งขันเขียนโปรแกรมที่ท็อปโค้ดเดอร์ (อังกฤษ)
  13. Codeforces Contests รูปแบบการแข่งขันเขียนโปรแกรมที่โค้ดฟอร์ซ (อังกฤษ)
  14. Virtual Judge หน้าหลักของ Hust Virtual Judge พร้อมคำอธิบายโดยย่อของระบบ (อังกฤษ)
  15. สสวท. จับมือนักเรียนคอมพิวเตอร์โอลิมปิกสร้างเว็บไซต์ www.programming.in.th อบรมเขียนภาษาซี ฟรี ! (ไทย)
  16. เกี่ยวกับ programming.in.th การเปิดเว็บไซต์ programming.in.th และความสัมพันธ์ระหว่าง สสวท. กับเว็บไซต์ (ไทย)
  17. Computer Olympic 2010 หน้าหลักของการแข่งขัน (ไทย)
  18. การแข่งขันโค้ดจม! กระทู้ประกาศการแข่งขัน Thailand Code Jom (ไทย)
  19. ACM ICPC Thailand เว็บไซต์หลักของ ACM ICPC ประเทศไทย พร้อมรายชื่อมหาวิทยาลัยต่าง ๆ ที่เคยเป็นเจ้าภาพการแข่งขัน (ไทย)

แหล่งข้อมูลอื่น[แก้]