ขอบเขตเนื้อหาฯของการแข่งขัน


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

1. หมวดคณิตศาสตร์
1.1 เลขคณิตและเรขาคณิต
    + จำนวนเต็ม คุณสมบัติของเลขจำนวนเต็ม (ค่าบวก ค่าลบ เลขคู่ เลขคี่ การหารลงตัว จำนวนเฉพาะ)
    + เลขเศษส่วน และร้อยละ
    + จุดเวคเตอร์ พิกัดจุดแบบคาร์ทิเชียน (Cartesian coordinates) ในตารางสองมิติที่มีพิกัดเป็นจำนวนเต็ม
    + ระยะทางแบบยูคลิด ทฤษฏีพิธากอรัส
    + ส่วนของเส้นตรง จุดตัดของเส้นตรง และคุณสมบัติพื้นฐานที่เกี่ยวข้อง
    + มุม สามเหลี่ยม สี่เหลี่ยมผืนผ้า สี่เหลี่ยมจัตุรัส วงกลม

1.2 โครงสร้างไม่ต่อเนื่อง (Discrete Structures)
    + ฟังก์ชัน ความสัมพันธ์ และเซ็ต
    + ตรรกศาสตร์พื้นฐาน
    + วิธีการพิสูจน์
    + วิธีการนับเบื้องต้น
      - กฎของการบวกและกฎของการคูณ (Sum rule and Product rule), หลักการเพิ่มเข้า-ตัดออก (Inclusion-exclusion Principle), ลำดับเลขคณิตและเรขาคณิต จำนวนแบบฟิโบนัชชิ (Fibonacci Numbers)
      - กฎรังนกพิราบ (Pigeonhole Principle) เพื่อใช้ในการหาขอบเขต
      - การเรียงสับเปลี่ยน และวิธีจัดหมู่ระดับพื้นฐาน
    + กราฟและต้นไม้
      - ต้นไม้และคุณสมบัติพื้นฐาน
      - กราฟไม่มีทิศทาง (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