วิกิพีเดีย

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

การเขียนโปรแกรมเชิงแข่งขัน เป็นการเขียนโปรแกรมเพื่อแก้ไขโจทย์ปัญหาทางตรรกะหรือคณิตศาสตร์ภายใต้ข้อจำกัดบางอย่างเพื่อให้ได้คำตอบออกมา โจทย์ปัญหาส่วนใหญ่จะมีคำตอบที่แน่นอนอยู่แล้ว การเขียนโปรแกรมนี้ไม่ได้มีจุดประสงค์ในการนำโปรแกรมมาใช้งานจริง แต่เป็นการเขียนเพื่อความสนุกและวัดทักษะในการแก้ไขปัญหา อาจถือได้ว่าเป็นกีฬาความคิดรูปแบบหนึ่ง โดยมากแล้วการเขียนโปรแกรมเชิงแข่งขันจะมีขึ้นในการแข่งขันเขียนโปรแกรมซึ่งส่วนใหญ่จะจัดขึ้นผ่านทางอินเทอร์เน็ตหรือไม่ก็เครือข่ายท้องถิ่น และมักจะมีบริษัทซอฟต์แวร์และอินเทอร์เน็ตเป็นผู้สนับสนุน เช่น กูเกิล[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 เก็บถาวร 2016-02-19 ที่ เวย์แบ็กแมชชีน (อังกฤษ)
  2. ↑ Google sposor page for TCO 2012 เก็บถาวร 2012-02-16 ที่ เวย์แบ็กแมชชีน (อังกฤษ)
  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. ↑ ข้อมูลเบื้องต้นเกี่ยวกับคอมพิวเตอร์โอลิมปิกระหว่างประเทศ เก็บถาวร 2013-02-05 ที่ เวย์แบ็กแมชชีน (ไทย)
  9. ↑ [1] [2] The ioi is (not) a science olympiad (อังกฤษ)
  10. ↑ ตัวอย่างเช่นการแข่งขัน Google Code Jam ดูที่รูปแบบการแข่งขันของ Google Code Jam เก็บถาวร 2012-12-26 ที่ เวย์แบ็กแมชชีน (อังกฤษ)
  11. ↑ History - International Olympiad in Informatics ประวัติคอมพิวเตอร์โอลิมปิกโดยเว็บไซต์ทางการ (อังกฤษ)
  12. ↑ Algorithm Overview รูปแบบการแข่งขันเขียนโปรแกรมที่ท็อปโค้ดเดอร์ (อังกฤษ)
  13. ↑ Codeforces Contests รูปแบบการแข่งขันเขียนโปรแกรมที่โค้ดฟอร์ซ (อังกฤษ)
  14. ↑ Virtual Judge เก็บถาวร 2012-12-28 ที่ เวย์แบ็กแมชชีน หน้าหลักของ Hust Virtual Judge พร้อมคำอธิบายโดยย่อของระบบ (อังกฤษ)
  15. ↑ สสวท. จับมือนักเรียนคอมพิวเตอร์โอลิมปิกสร้างเว็บไซต์ www.programming.in.th อบรมเขียนภาษาซี ฟรี ! เก็บถาวร 2016-03-04 ที่ เวย์แบ็กแมชชีน (ไทย)
  16. ↑ เกี่ยวกับ programming.in.th เก็บถาวร 2016-03-08 ที่ เวย์แบ็กแมชชีน การเปิดเว็บไซต์ programming.in.th และความสัมพันธ์ระหว่าง สสวท. กับเว็บไซต์ (ไทย)
  17. ↑ Computer Olympic 2010 เก็บถาวร 2013-03-14 ที่ เวย์แบ็กแมชชีน หน้าหลักของการแข่งขัน (ไทย)
  18. ↑ การแข่งขันโค้ดจม! เก็บถาวร 2010-05-10 ที่ เวย์แบ็กแมชชีน กระทู้ประกาศการแข่งขัน Thailand Code Jom (ไทย)
  19. ↑ ACM ICPC Thailand เก็บถาวร 2012-08-16 ที่ เวย์แบ็กแมชชีน เว็บไซต์หลักของ ACM ICPC ประเทศไทย พร้อมรายชื่อมหาวิทยาลัยต่าง ๆ ที่เคยเป็นเจ้าภาพการแข่งขัน (ไทย)

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

เข้าถึงจาก "https://th.wikipedia.org/w/index.php?title=การเขียนโปรแกรมเชิงแข่งขัน&oldid=10847914"