ขอบเขตเนื้อหาวิชาที่ครอบคลุมในการแข่งขัน

เนื้อหาวิชาที่ครอบคลุมในการแข่งขันแบ่งได้เป็น 3 หมวด คือ คณิตศาสตร์ พื้นฐานวิทยาการคอมพิวเตอร์ และ อัลกอริทึมโดยมีรายละเอียดของขอบเขตในแต่ละหมวดเป็นดังต่อไปนี้

1. หมวดคณิตศาสตร์

1.1 เลขคณิตและเรขาคณิต
  • จำนวนเต็ม คุณสมบัติของเลขจำนวนเต็ม (ค่าบวก ค่าลบ เลขคู่ เลขคี่ การหารลงตัว จำนวนเฉพาะ)
  • เลขเศษส่วน และร้อยละ
  • จุดเวคเตอร์ พิกัดจุดแบบคาร์ทิเชียน (Cartesian coordinates) ในตารางสองมิติที่มีพิกัดเป็นจำนวนเต็ม
  • ระยะทางแบบยูคลิด ทฤษฏีพิธากอรัส
  • ส่วนของเส้นตรง จุดตัดของเส้นตรง และคุณสมบัติพื้นฐานที่เกี่ยวข้อง
  • มุม สามเหลี่ยม สี่เหลี่ยมผืนผ้า สี่เหลี่ยมจัตุรัส วงกลม
  •  
1.2 โครงสร้างไม่ต่อเนื่อง (Discrete Structures)
  • ฟังก์ชัน ความสัมพันธ์ และเซ็ต
  • ตรรกศาสตร์พื้นฐาน
  • วิธีการพิสูจน์
  • วิธีการนับเบื้องต้น
       - กฎของการบวกและกฎของการคูณ (Sum rule and Product rule), หลักการเพิ่มเข้า-ตัดออก (Inclusion-exclusion Principle), ลำดับเลขคณิตและเรขาคณิต จำนวนแบบฟิโบนัชชิ (Fibonacci Numbers)
       - กฎรังนกพิราบ (Pigeonhole Principle) เพื่อใช้ในการหาขอบเขต
       - การเรียงสับเปลี่ยน และวิธีจัดหมู่ระดับพื้นฐาน
       - ฟังก์ชันเลขเศษส่วน (Fractional Function) และสัมประสิทธิ์ทวินาม
  • กราฟและต้นไม้
       - ต้นไม้และคุณสมบัติพื้นฐาน
       - กราฟไม่มีทิศทาง (Degree, Path, Cycle, Connectedness, Handshaking Lemma)
       - กราฟแบบมีทิศทาง (In-degree, Out-degree, Directed Path/Cycle)
       - Spanning Trees
- วิธีการเดินผ่านต้นไม้ (Traversal Strategies: Defining the Node Order for Ordered Trees)
- 'Decorated' Graphs with Edge/Node Labels, Weights, Colors
- Multigraphs และ Graphs ที่มี Self Loops

2. หมวดพื้นฐานวิทยาการคอมพิวเตอร์

2.1. พื้นฐานด้านการเขียนโปรแกรม
2.2. ทักษะการแก้ปัญหา (Problem-Solving Skill)
2.3. พื้นฐานโครงสร้างข้อมูล
  • ชนิดข้อมูลดั้งเดิม (Primitive Data Type) ได้แก่ Boolean, Signed/Unsigned Integer, Character
  • แถวลำดับ (อาเรย์ อาเรย์หลายมิติ)
  • Record/Struct
  • สตริงและการดำเนินการกับสตริง
  • Static และ Stack Allocation
  • Lined Structures (ทั้งที่เป็นแบบเส้นตรง และแบบที่แบ่งเป็นสาขาได้)
  • การสร้าง โครงสร้างกองซ้อน (Stack), คิว (Queue), ต้นไม้ และกราฟ
  • การเลือกโครงสร้างข้อมูลที่เหมาะสม
  • คิวลำดับความสำคัญ (Priority Queue), ไดนามิกเซต (Dynamic Set), ไดนามิกแมพ (Dynamic Map)
2.4. การเรียกตัวเองซ้ำ (Recursion)
  • แนวคิด
  • ฟังก์ชันทางคณิตศาสตร์ที่เรียกตัวเองซ้ำ
  • วิธีแบ่งแยกและเอาชนะ (Divide and Conquer)
  • อัลกอริทึมการย้อนรอยแบบเรียกตัวเองซ้ำ (Recursive Backtracking)

3. หมวดอัลกอริทึม

3.1. พื้นฐานการวิเคราะห์ความซับซ้อนของอัลกอริทึม(Algorithmic Complexity)
3.2. กลวิธีทางอัลกอริทึม
  • Brute-Force Algorithm
  • Greedy Algorithm
  • การแบ่งแยกและเอาชนะ
  • Backtracking (ทั้งที่เป็นแบบเรียกตัวเองซ้ำและไม่เรียกตัวเองซ้ำ)
  • Branch-and-Bound Algorithm
  • Pattern Matching and String/text Algorithm
  • Dynamic Programming
3.3. อัลกอริทึมเชิงคำนวณพื้นฐาน
  • อัลกอริทึมเชิงตัวเลขพื้นฐานที่เกี่ยวข้องกับจำนวนเต็ม เช่น Radix Conversion, Euclid’s algorithm, Primality test in O(N1/2), Sieve of Eratosthenes, Factorization, Efficient exponentiation
  • การจัดการอาร์เรย์ขั้นพื้นฐาน (รวมถึงการทำฮิสโทแกรม และ Bucket Sort)
  • Sequential และ Binary Search
  • Search by Elimination
  • การแบ่งข้อมูล (partitioning) การจัดลำดับด้วยการแบ่งข้อมูลซ้ำๆ Quick Sort
  • การเรียงข้อมูลที่มีเวลาที่แย่ที่สุดเป็น O(NlogN) เช่น Heap sort และ Merge Sort
  • Binary heap พื้นฐาน และ Binary Search Tree
  • การบรรยายโครงสร้างกราฟ เช่น Adjacency List และ Adjacency Matrix
  • Depth-first and Breadth-first Traversals of Graphs และการหาองค์ประกอบที่เชื่อมต่อกันของกราฟแบบไม่มีทิศทาง
  • Shortest Path Algorithm เช่น Dijkstra, Bellman-Ford และ Floyd-Warshall
  • Transitive Closure (Floyd’s Algorithm)
  • Minimum Spanning Tree
  • Topological Sort