B.1 · การคิดเชิงคำนวณ

International Baccalaureate · IB Diploma · Computer Science · SL · หัวข้อ 5

5.1

ขอบเขตและเงื่อนไขก่อนเข้าเรียน

SL ที่รองรับ: จุดเน้น การประเมินผลครั้งแรก 2027 เป้าหมาย; PDFทางการแสดงค่า 403; เอกสารสรุปสั้นๆ ที่จัดเก็บไว้ล่วงหน้าคือผลการประเมินสุดท้าย 2026 คู่มือที่เหลือ การประเมิน และข้อกำหนดเชิงปฏิบัติยังคงมีข้อจำกัดตามบันทึกไว้

สิ่งจำเป็น: อ่านปริมาณและหน่วยที่กำหนด ใช้เลขคณิตและเงื่อนไขโมเดลด้านล่าง บทเรียนแต่ละบทพัฒนาวิธีการของตนเองก่อนการถ่ายโอนแบบอิสระ

นี่คือตัวอย่างการสอนดั้งเดิมหรือที่ระบุว่าเป็นเรื่องfictional อย่างชัดเจน ไม่ใช่การวัดค่าจริงหรือการสืบสวนผู้เรียนที่ได้รับการประเมินเสร็จสมบูรณ์

5.2

อัลกอริทึม การติดตาม และหลักฐานความถูกต้อง

อะไรจะเป็นคำอธิบายสำหรับการสังเกตนี้?

อัลกอริทึมอาจทำงานได้สำหรับตัวอย่างหนึ่งแต่ล้มเหลวที่ขอบเขต การทดสอบควรออกแบบจากสเปก ไม่ใช่แค่ทางเดินที่เป็นสุข (happy path) เท่านั้น
เริ่มต้นด้วยการทำนาย ระบุปริมาณหรือลักษณะที่คุณจะเปรียบเทียบ แล้วตัดสินใจว่าหลักฐานอะไรที่จะแยกแยะคำอธิบายสองแบบได้

สร้างโมเดล

อัลกอริทึมคือขั้นตอนที่จำกัดและชัดเจนสำหรับงานหนึ่งๆ การติดตาม (trace) บันทึกการเปลี่ยนแปลงสถานะ ความคงสภาพของลูป (loop invariant) อธิบายคุณสมบัติที่ถูกรักษาไว้ในการวนซ้ำแต่ละรอบและช่วยในการพิสูจน์ความถูกต้อง
algorithm: กระบวนการจำกัดจำนวนขั้นตอนในการแก้ปัญหาที่กำหนด; boundary test: การทดสอบที่ขอบเขตของช่วงค่าเข้าที่ยอมรับได้

อัลกอริทึม การติดตาม และหลักฐานความถูกต้อง: แผนภาพกรณีศึกษาต้นฉบับ

เลือกหลักฐานที่นำมาทดสอบได้

กำหนดเงื่อนไขอินพุตและผลลัพธ์ที่คาดหวัง ใช้กรณีขอบเขต ชุดข้อมูลว่างเมื่ออนุญาต ข้อมูลซ้ำ และค่าที่ไม่ถูกต้อง แยกอัลกอริทึมที่ผิด ออกจากการนำไปใช้ที่ผิด หรือข้อกำหนดที่ไม่สมบูรณ์
ติดตามการค้นหาในรายการเรียงลำดับสมมติขนาดเล็ก ระบุ().'มาตรฐานการอ้างอิงดัชนี' สำหรับการค้นหาแบบเบี่ยง二分 (binary search) อัปเดตขอบเขตเพื่อให้ช่วงที่เหลือเล็กลง Reject อินพุตที่ไม่เรียงลำดับเว้นแต่การจัดเรียงจะเป็นส่วนหนึ่งของงาน

เริ่มจากปริมาณที่ทราบแล้ว

ระบุค่าที่ทราบและหน่วยของมัน เลือกความสัมพันธ์โดยพิจารณาว่าข้อสมมติฐานสอดคล้องกับเคสนี้ แล้วจัดรูปสมการก่อนแทนค่า
ที่ทราบ: การค้นหาเชิงเส้นของรายการ 8 รายการ อาจต้องการ 8 ครั้งเปรียบเทียบเมื่อ itemCount ที่หาอยู่เป็นรายการสุดท้ายหรือไม่มีอยู่ การเพิ่มขนาดรายการสองเท่าจะเพิ่มจำนวนครั้งเปรียบเทียบในกรณี worst-case สองเท่าภายใต้โมเดลนี้ การค้นหาแบบเบี่ยง二分 ลดช่วงลงประมาณครึ่งหนึ่งในแต่ละขั้นตอนแต่ต้องใช้โครงสร้างที่จัดลำดับเหมาะสม

ตัวอย่าง:

การค้นหาเชิงเส้นสแกน 14 รายการทั้งหมดโดยไม่พบ-match เกิดการเปรียบเทียบ itemCount กี่ครั้ง? ใช้ลำดับเดียวกัน: ปริมาณที่ทราบ → โมเดล → ความสัมพันธ์ → แทนค่า → หน่วยและการตีความ

ตรวจสอบข้อสรุปและขอบเขต

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

เตือน:

การทดสอบตัวอย่างสำเร็จหนึ่งครั้งพิสูจน์อัลกอริทึมว่าถูกต้องสำหรับอินพุตที่ถูกต้องทั้งหมด ข้อความนี้ไม่จริง: การทดสอบตัวอย่างสำเร็จไม่ได้พิสูจน์ความถูกต้องสำหรับอินพุตที่ถูกต้องทั้งหมด อย่านำไวยากรณ์伪โค้ดเฉพาะ Cambridge มาใช้ในหลักสูตร IB โดยไม่มีแหล่งที่มาของหลักสูตร

จุดสำคัญ:

อัลกอริทึม การติดตาม และหลักฐานความถูกต้อง: กำหนดเงื่อนไขอินพุตและผลลัพธ์ที่คาดหวัง ใช้กรณีขอบเขต ชุดข้อมูลว่างเมื่ออนุญาต ข้อมูลซ้ำ และค่าที่ไม่ถูกต้อง แยกอัลกอริทึมที่ผิด ออกจากการนำไปใช้ที่ผิด หรือข้อกำหนดที่ไม่สมบูรณ์

ลายเส้นที่ดำเนินการได้และขอบเขต

def first_index(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1
print(first_index([4, 7, 4], 4))
print(first_index([4, 7, 4], 9))
print(first_index([], 4))

ผลลัพธ์ที่คาดหวัง:

0
-1
-1

ลูปจะทดสอบค่าดัชนี 0 ก่อน จะหยุดเมื่อพบการจับคู่ และจะคืนค่า −1 ก็ต่อเมื่อตรวจสอบรายการจนหมด ดังนั้นหากมีข้อมูลซ้ำกันจะได้ค่าดัชนีตัวแรก หากเป็นรายการว่างจะไม่มีการทำงานภายในลูป

คำศัพท์ ฝึกฝน