ร่างสารบัญ (หนังสือแด่เขมรัตน์)

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 22:28, 4 พฤศจิกายน 2549 โดย Pramook (คุย | มีส่วนร่วม)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

เนื้อหา

หน้าปก

คอมพิวเตอร์โอลิมปิก

หน้าใน

แด่
เขมรัตน์ นิ่มปุญญกำพงษ์
เพื่อนผู้แสนดี อดีตตัวแทนประเทศไทยไปแข่งคอมพิวเตอร์โอลิมปิก เหรียญทองแดง ปี1999 ณ ประเทศตุรกี เหรียญเงิน ปี2000 ณ ประเทศจีน

คำนำ

ผู้อ่านเป้าหมาย

ผู้ที่ต้องการสอบโอลิมปิกคอมพิวเตอร์

จุดประสงค์

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

บทนำ

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

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

เซต

ดูบทความจริงได้ที่ เซต (หนังสือแด่เขมรัตน์)

ตรรกศาสตร์และการพิสูจน์

ระบบเลขฐาน

คณิตศาสตร์เิชิงการจัด

หลักการพื้นฐาน

การเรียงสับเปลี่ยนและการจัดหมู่

การเรียงสับเปลี่ยนแบบมีตัวซ้ำ

การเรียงสับเปลี่ยนแบบไม่มีตัวซ้ำ

การจัดหมู่แบบไม่มีตัวซ้ำ

การจัดหมู่ีแบบมีตัวซ้ำ

เทคนิคสตาร์แอนด์บาร์

สัมประสิทธิ์ทวินามและเอกลักษณ์ต่างๆ

แบบฝึกหัด

ความน่าจะเป็น

แซมเปิลสเปซ

แซมเปิลสเปซ (Sample Space)

แซมเปิลพ้อยท์

แซมเปิลพ้อยท์ (Sample Point)

เหตุการณ์

เหตุการณ์ (Event)

ค่าความน่าจะเป็น

ความน่าจะเป็น = จำนวนสมาชิกของเหตุการณ์ หารด้วย จำนวนสมาชิกของแซมเปิลสเปส

คุณสมบัติของความน่าจะเป็น

ฟังก์ชัน

ความสัมพันธ์

นิยาม

โดเมน-เรนจ์

ลำดับ อนุกรม

ลำดับ

ลำดับเลขคณิต

ลำดับเลขาคณิต

ลำดับฮาโมนิก

อนุกรม

อนุกรมเลขคณิต

อนุกรมเลขาคณิต

อนุกรมฮาโมนิก

ทฤษฏีกลุ่ม

Group

Ring

Field

เมตริกซ์

นิยาม

การบวกลบเมตริกซ์

การคูณเมตริกซ์

ทฤษฏีจำนวน (Number Theory)

(Kanat: Contents being edited)

การหารลงตัว (Divisibility)

นิยาม: การหารลงตัว

ตัวหารร่วมมาก (Greatest Common Divisor)

อัลกอริีทึมแบบยูคลิด

สมการไดโอแฟนไทน์เชิงเส้น

จำนวนเฉพาะ

ทฤษฎีบทมูลฐานของเลขคณิต

จำนวนเฉพาะมีอยู่มากมาย

การทดสอบจำนวนเฉพาะ

ความหนาแน่นของจำนวนเฉพาะ

คอนกรูเอนซ์ (Congruence)

แนะนำคอนกรูเอนซ์

คอนกรูเอนซ์พิสดาร

ฟังก์ชันฟีออยเลอร์และทฤษฎีบทของออยเลอร์

เรื่องน่ารู้อื่นๆ

ตัวเลขพิเศษ

การเข้ารหัสแบบ RSA

อัลกอริทึมเกี่ยวกับทฤษฎีจำนวน

โจทย์ต่างๆ

พื้นฐานการเขียนโปรแกรม

ดูบทความจริงได้ที่ พื้นฐานการเขียนโปรแกรม

ทฤษฎีการคำนวณ

ออโตมาตาจำกัดและนิพจน์เรกูลาร์

ออโมมาตาแบบพุชดาวน์และไวยากรณ์ไม่อิงบริบท

เครื่องจักรทัวริง

ความบริบูรณ์ NP (NP-completeness)

ความยาก NP (NP-hardness)

โครงสร้างข้อมูล

อาร์เรย์และลิงค์ลิสต์

คิวและสแตก

ดิสจอยนท์เซต

ฮีปทวิภาค

ต้นไม้ค้นหาแบบทวิภาค

เซตแบบพลวัต

ดิกชันนารีแบบพลวัต

ทฤษฏีกราฟ

นิยาม

กราฟแบบมีทิศทางและไม่มีทิศทาง

ดีกรี

การเก็บกราฟในหน่วยความจำ

เส้นทางและวงจร (Path and Cycle)

วงจรออยเลอร์

วงจรฮามิลโทเนียน

ต้นไม้

ต้นไม้แบบทอดข้าม

การคำนวณเชิงเรขาคณิต

จุด

ส่วนของเส้นตรง

การตัดกันของส่วนของเส้นตรง

รูปหลายเหลี่ยม

ความป่อง (convexity)

ปัญหาข้างใน/ข้างนอก

เทคนิคการออกแบบอัลกอริทึม

อัลกอริทึมแบบตะกละ

การแบ่งแยกและเอาชนะ

การย้อนรอย (backtracking)

แบรนช์แอนด์บาวนด์

ใครหาคำแปลดีกว่านี้ได้ ช่วยด้วย

ไดนามิึคโปรแกรมมิืง

การเรียงลำดับ

บับเบิลซอร์ท

ซีเลกชันซอร์ท

อินเซอร์ชันซอร์ท

เชลล์ซอร์ืท

ทรีซอร์ท

ฮีปซอร์ท

เมิร์จซอร์ท

ควิกซอร์ท

ข้อจำกัดของการเรียงลำดับข้อมูลด้วยการเปรียบเทียบข้อมูล

เรดิกซ์ซอร์ท

บักเคทซอร์ท

อัลกอริทึมสำหรับจัดการข้อความ

การค้นหาข้อมูล (Searching)

มินิแมกซ์

อัลกอริทึมเพื่อการประมาณ (จะเขียนดีไหม)

ภูมิปัญญาชาวบ้าน (heuristic) (จะเขียนดีไหม)

อัลกอริทึมเกี่ยวกับกราฟ

การค้นหาแบบลึกและการค้นหาแบบกว้าง

การหาเส้นทางที่สั้นที่สุด

การหาการไหลที่สูงที่สุด (Max Flow)

ต้นไม้ทอดข้ามน้อยสุด

ตัวอย่างข้อสอบ

รอบแรก

รอบสอง

ค่าย

ตัวแทน

References