Home › รายละเอียดคอมพิวเตอร์โอลิมปิก

รายการเนื้อหาที่เกี่ยวข้องกับคอมพิวเตอร์โอลิมปิกทั้งหมด (อัพเดทล่าสุดปี 2009)

รายการเนื้อหาทั้งหมดที่เกี่ยวข้องกับคอมพิวเตอร์โอลิมปิกทั้งหมดนี้มาจาก ioi2009.org

เนื้อหาที่เพิ่มเติมจากเดิมเขียนอยู่ในรูปตัวเอียง :: นอกจากนี้เนื้อหาที่ไม่จำเป็นและไม่ใช่ในการแข่งขัน ขอไม่แปลมา ณ ที่นี้ (กรุณาดูในไฟล์ต้นฉบับเอง)
หมายเหตุ: มีต้นฉบับหลักสูตรของ IOI 2009 แนบท้าย หากพบว่าบริเวณใดแปลผิด กรุณาแจ้งให้ทราบที่ thailandoi.team@gmail.com ด้วยครับ

  1. เลขคณิตและเรขาคณิต
    1.1. จำนวนเต็ม กระบวนการทางพีชคณิต (รวมทั้งการยกกำลัง) การเปรียบเทียบค่า
    1.2. สมบัติของจำนวนเต็ม (จำนวนบวก-ลบ, จำนวนคู่-คี่, การหารลงตัว, จำนวนเฉพาะ-ประกอบ)
    1.3. เศษส่วนและร้อยละ
    1.4. จุด เวกเตอร์ พิกัดบนระนาบสองมิติ
    1.5. ระยะห่างแบบยุคลิด ทฤษฎีบทของพีทาโกรัส
    1.6. ส่วนของเส้นตรง จุดตัดของเส้นตรง
    1.7. มุม
    1.8. สามเหลี่ยม สี่เหลี่ยมผืนผ้าและจัตุรัส วงกลม
    1.9. รูปหลายเหลี่ยม (รวมทั้งรูปด้านเท่ามุมเท่า รูปหลายเหลี่ยมนูน จุดภายในและภายนอกรูปเหลี่ยม)

  2. เซต ความสัมพันธ์ และฟังก์ชัน
    2.1. ฟังก์ชัน (ฟังก์ชันทั่วถึง, ฟังก์ชันหนึ่งต่อหนึ่ง, ฟังก์ชันผกผัน, ฟังก์ชันประกอบ)
    2.2. ความสัมพันธ์ (การสะท้อน, ความสมมาตร, การถ่ายทอด, ความสมมูล, ความสัมพันธ์อันดับเชิงเส้น/ทุกส่วน, ลำดับอักษร)
    2.3. เซต (แผนภาพเวนน์-ออยเลอร์, ส่วนเติมเต็ม, ผลคูณคาร์ทีเชียน, พาวเวอร์เซต)
    2.4. หลักการช่องนกพิราบ

  3. ตรรกะเบื้องต้น
    3.1. ตรรกศาสตร์ประพจน์
    3.2. ตัวเชื่อมทางตรรกศาสตร์
    3.3. ตารางแสดงค่าความจริง
    3.4. ตรรกศาสตร์ภาคแสดง
    3.5. ตัวบ่งปริมาณสำหรับทุกตัว ตัวบ่งปริมาณสำหรับตัวมีจริง
    3.6. อนุมานด้วยการยืนยันบรรพบท (Modus ponens) และการปฏิเสธอนุบท (Modus tollens)

  4. กระบวนการพิสูจน์
    4.1. การดำเนินการทางตรรกศาสตร์: ประพจน์มีเงื่อนไข บทกลับ ตัวผกผัน ประพจน์แย้งสลับที่ นิเสธของประพจน์ และประพจน์ที่เป็นข้อขัดแย้ง
    4.2. การพิสูจน์โดยตรง เช่น การใช้ตัวอย่างค้าน การพิสูจน์แย้งสลับที่ การพิสูจน์โดยหาข้อขัดแย้ง
    4.3. การอุปนัยทางคณิตศาสตร์ และการอุปนัยทางคณิตศาสตร์แบบเข้ม
    4.4. บทนิยามเวียนเกิดทางคณิตศาสตร์ (รวมทั้ง บทนิยามเวียนเกิดที่นิยามร่วมกัน)

  5. หลักการนับเบื้องต้น
    5.1. กฎการบวก-กฎการคูณ หลักการเพิ่มเข้า-หักออก การก้าวหน้าทางเลขคณิตและเรขาคณิต จำนวนฟิโบนักชี
    5.2. หลักการช่องนกพิราบ (เพื่อใช้ในการหาขอบเขต)
    5.3. การเรียงสลับที่และการจัดกลุ่ม
    5.4. ฟังก์ชันเศษส่วน สัมประสิทธิ์พหุนาม
    5.5. เอกลักษณ์ปาสคาล ทฤษฏีบททวินาม

  6. กราฟและต้นไม้
    6.1. ต้นไม้และสมบัติพื้นฐาน
    6.2. กราฟไม่มีทิศทาง (ระดับขั้น, วิถี, วัฏจักร, การเชื่อมโยง, วิถี/วงจรออยเลอร์, วิถี/วัฏจักรแฮมิลตัน, บทตั้งของการจับมือกัน)
    6.2. กราฟมีทิศทาง (ระดับขั้นเข้า, ระดับขั้นออก, วิถีมีทิศทาง, วัฏจักรมีทิศทาง, การเชื่อมโยง, วิถี/วงจรออยเลอร์, วิถี/วัฏจักรแฮมิลตัน)
    6.3. ต้นไม้แผ่ทั่ว
    6.4. การท่องกราฟ
    6.5. กราฟที่จุดยอดและเส้นเชื่อมมีน้ำหนักหรือสี
    6.6. กราฟที่มีลูปหรือมีจุดยอดสองจุดที่มีเส้นเชื่อมมากกว่า 1 เส้น

  7. โครงสร้างของภาษาคอมพิวเตอร์
    7.1. วากยสัมพันธ์เบื้องต้นและลักษณะการทำงานของภาษาระดับสูง
    7.2. ตัวแปร ประเภทของตัวแปร นิพจน์ และการกำหนดค่า
    7.3. การรับข้อมูลเข้าและแสดงข้อมูลออกอย่างง่าย
    7.4. โครงสร้างแบบเงื่อนไขและทำซ้ำ
    7.5. ฟังก์ชันและการส่งผ่านค่าพารามิเตอร์
    7.6. การแตกปัญหาเชิงโครงสร้าง

  8. อัลกอริทึมและการแก้ปัญหา
    8.1. กลยุทธ์การแก้ปัญหาโจทย์ (เข้าใจการวางแผนและการตรวจสอบ, การแบ่งแยกปัญหาที่สนใจ, การทำให้อยู่ในรูปทั่วไป-กรณีพิเศษ, ความแตกต่างระหว่างแต่ละกรณี, การกระทำย้อนกลับ)
    8.2. บทบาทของอัลกอริทึมในการแก้โจทย์ปัญหา
    8.3. กลยุทธ์การ Implement สำหรับอัลกอริทึม
    8.4. กลยุทธ์การแก้จุดบกพร่องโปรแกรม
    8.5. หลักการเบื้องต้นและสมบัติของอัลกอริทึม (ทั้งในแง่ของความถูกต้องและประสิทธิภาพ)

  9. โครงสร้างข้อมูลเบื้องต้น
    9.1. แบบชนิดข้อมูลปฐมฐาน (บูลีน, จำนวนเต็มที่มีเครื่องหมายและไม่มีเครื่องหมาย, อักขระ)
    9.2. แถวลำดับ
    9.3. ระเบียน
    9.4. สายอักขระและการประมวลผลสายอักขระ
    9.5. การจองพื้นที่แบบสถิตและแบบกองซ้อน
    9.6. โครงสร้างเชื่อมโยง (เชิงเส้นและกิ่งก้าน)
    9.7. การ Implement โครงสร้างเชื่อมโยงโดยใช้หน่วยความจำสถิต
    9.8. กลยุทธ์การ Implement กองซ้อนและแถวคอย
    9.9. กลยุทธ์การ Implement กราฟและต้นไม้
    9.10. กลยุทธ์การเลือกใช้โครงสร้างข้อมูลที่ถูกต้อง
    9.11. แบบชนิดข้อมูลนามธรรม แถวคอยแบบมีลำดับความสำคัญ เซตแบบพลวัต แมพแบบพลวัต

  10. การเขียนโปรแกรมเวียนซ้ำ
    10.1. หลักการเบื้องต้นของการเวียนซ้ำ
    10.2. ฟังก์ชันคณิตศาสตร์เวียนเกิด
    10.3. ขั้นตอนการเวียนซ้ำเบื้องต้น
    10.4. หลักการแบ่งแยกและปกครอง
    10.5. การกระทำย้อนรอยแบบเวียนซ้ำ

  11. การวิเคราะห์อัลกอริทึม
    11.1. การระบุอัลกอริทึม เงื่อนไขตั้งต้น เงื่้อนไขสุดท้าย ความถูกต้อง ความยืนยง
    11.2. การวิเคราะห์ขอบเขตบนของความซับซ้อน
    11.3. สัญกรณ์โอใหญ่
    11.4. ชั้นความซับซ้อนพื้นฐาน (คงตัว, ลอการิทึม, เชิงเส้น, $ O(N \lg N) $, กำลังสอง, กำลังสาม, ยกกำลัง)
    11.5. การแลกเปลี่ยนระหว่างเวลาและหน่วยความจำในอัลกอริทึม

  12. กลยุทธ์เชิงอัลกอริทึม
    12.1. การวนลูปอย่างง่าย
    12.2. การถึกหาคำตอบโดยตรงอย่างละเอียด
    12.3. อัลกอริทึมเชิงละโมบ
    12.4. การแบ่งแยกและปกครอง
    12.5. การกระทำย้อนรอย (ทั้งเวียนเกิดและไม่เวียนเกิด)
    12.6. การแตกแขนงและกำหนดขอบเขต
    12.7. การตรวจสอบหาสตริงและอัลกอริทึมเกี่ยวกับสตริง
    12.8. กำหนดการพลวัต
    12.9. อัลกอริทึมการประมาณวิยุต

  13. อัลกอริทึมการคำนวณพื้นฐาน
    13.1. อัลกอริทึมพื้นฐานเชิงจำนวน (การแปลงเลขฐาน, อัลกอริทึมของยูคลิด, การตรวจสอบจำนวนเฉพาะใน $ O(\sqrt{N}) $, ตะแกรงของเอราทอสเทนีส, การแยกตัวประกอบ, การหาค่ายกกำลังอย่างมีประสิทธิภาพ)
    13.2. กระบวนการบวก ลบและคูณอย่างง่าย ของแบบชนิดข้อมูลจำนวนเต็มซึ่งไม่เที่ยง (Arbitrarily precise)
    13.3. การจัดดำเนินการกับแถวลำดับอย่างง่าย (การเติมให้เต็ม, การเลื่อนค่า, การหมุน, การผันกลับ, การแปลงขนาด, การหามากที่สุด-น้อยที่สุด, ผลรวมส่วนเติมหน้า, ฮิสโทแกรม, การเรียงลำดับจากที่ฝากข้อมูล)
    13.4. การดำเนินการเชิงลำดับ การค้นหาเชิงลำดับ และการค้นหาเชิงทวิภาค
    13.5. การค้นหาโดยใช้การกำจัดออกและใช้ความชัน
    13.6. อัลกอริทึมเรียงลำดับข้อมูลแบบกำลังสอง (ซีเลคชันซอร์ต, อินเซอร์ชันซอร์ต)
    13.7. อัลกอริทึมการแบ่งส่วนและการเรียงลำดับข้อมูลโดยใช้การแบ่งส่วน (ควิกซอร์ต)
    13.8. อัลกอริทึมเรียงลำดับข้อมูลแบบ $ O(N \lg N) $ (ฮีปซอร์ต, การเรียงลำดับผสาน)
    13.9. โครงสร้างข้อมูลฮีปเชิงทวิภาค
    13.10. ต้นไม้ค้นหาทวิภาค
    13.11. ต้นไม้เฟนวิค “ต้นมะนาว” หรืออาจเรียกต้นไม้ดรรชนีเชิงทวิภาค (Fenwick tree, Binary indexed tree, segment tree, interval tree)
    13.12. การแทนกราฟด้วยการเก็บข้อมูล (Adjacency list, Adjacency matrix)
    13.13. การท่องต้นไม้แบบอันดับ
    13.14. อัลกอริทึมการค้นหาในแนวลึกและการค้นหาในแนวกว้างในการท่องกราฟ การหาความเชื่อมต่อของกราฟไม่มีทิศทาง
    13.15. อัลกอริทึมหาวิถีที่สั้นที่สุด (Dijkstra’s algorithm, Bellman-Ford’s algorithm, Floyd-Warshall’s algorithm)
    13.16. การหาจุดยอดของกราฟที่ไปถึงกันได้ (Floyd’s algorithm)
    13.17. ต้นไม้แผ่ทั่วที่น้อยที่สุด (Jarník-Prim’s algorithm, Kruskal’s algorithm)
    13.18. การเรียงลำดับเชิงทอพอโลยี
    13.19. อัลกอริทึมค้นหาวิถีหรือวงจรออยเลอร์

  14. การคำนวณเบื้องต้น ออโตมาตาและไวยากรณ์ (ปัจจุบันยังไม่มี แต่อาจมีในอนาคตได้)
    14.1. เครื่องสถานะจำกัด, ไวยากรณ์ไม่พึ่งบริบท
    14.2. ออโตมาตาจำกัด, นิพจน์ปรกติ, ระบบการเขียนแก้ใหม่

  15. การวิเคราะห์อัลกอริทึมที่ซับซ้อน
    14.1. พื้นฐานของเกมเชิงการจัด และ Minimax algorithm สำหรับการแก้ปัญหาการเล่นเกมที่ดีที่สุด

  16. อัลกอริทึมเชิงเรขาคณิต (บนระนาบสองมิติ)
    15.1. ส่วนของเส้นตรง: สมบัติและจุดตัด
    15.2. การบอกตำแหน่งของจุดเทียบกับรูปเหลี่ยมอย่างง่าย
    15.3. การค้นหา Convex hull
    15.4. การกวาดเชิงระนาบ

  17. ทักษะการเขียนโปรแกรมและการใช้คอมพิวเตอร์
    16.1. เขียนโปรแกรมจากขั้นตอนวิธีของโปรแกรมที่ออกแบบไว้
    16.2. กำหนดให้โปรแกรมรับข้อมูลและส่งข้อมูลทางไฟล์
    16.3. ออกแบบโปรแกรมโดยใช้ Library ที่อนุญาต
    16.4. เขียนโปรแกรมโดยใช้ Editor ที่กำหนดให้
    16.5. คอมไพล์โปรแกรมที่เขียนได้เอง
    16.6. แก้จุดบกพร่องโปรแกรมที่ตนเองเขียนได้
    16.7. เข้าใจขั้นตอนการพัฒนาโปรแกรม และสามารถกำหนดหลักไมล์ในการพัฒนาโปรแกรม
    16.8. แปลงคำอธิบายภาษาพูดของโจทย์ปัญหาเป็นโมเดลทางคอมพิวเตอร์ได้ รวมทั้งความต้องการทางด้านประสิทธิภาพ
    16.9. ใช้เทคนิคเพื่อเพิ่มโอกาสตรวจสอบข้อผิดพลาดของโปรแกรม
    16.10. ตรวจสอบบางส่วนของโปรแกรม (Unit testing)
    16.11. แบ่งเวลาสำหรับแต่ละกิจกรรมได้เหมาะสม
    16.12. เปรียบเทียบความเสี่ยงของแต่ละทางเลือกในการแก้ปัญหาที่ต่างกัน
    16.13. จัดการกับโค้ดแต่ละเวอร์ชันและสถานะการพัฒนาโปรแกรมนั้นได้
    16.14. ให้เหตุผลถึงความถูกต้องและประสิทธิภาพของโปรแกรมได้
    16.15. ทราบกระบวนการประมวลของโปรแกรม พื้นฐานโครงสร้างของคอมพิวเตอร์ พื้นฐานการใช้งานคอมพิวเตอร์ พื้นฐานการจัดการกับไฟล์ ซอฟต์แวร์ที่ใช้ในการพัฒนาโปรแกรม