อัลกอริทึม รอยตาม และ หลักฐานความถูกต้อง
แนะนำใหม่| English | ความหมาย |
|---|---|
| algorithm/ˈælɡərɪθəm/ | อัลกอริทึม |
| boundary test/ˈbaʊndəri test/ | การทดสอบขอบเขต |
อะไรจะอธิบายการสังเกตนี้ได้?
- อัลกอริทึมอาจทำงานได้สำหรับตัวอย่างหนึ่งแต่ล้มเหลวที่ขอบเขต การทดสอบควรออกแบบจากสเปก ไม่ใช่แค่ทางเดินที่เป็นสุข (happy path) เท่านั้น
- เริ่มต้นด้วยการทำนาย ระบุปริมาณหรือลักษณะที่คุณจะเปรียบเทียบ แล้วตัดสินใจว่าหลักฐานอะไรที่จะแยกแยะคำอธิบายสองแบบได้
สร้างโมเดล
- อัลกอริทึมคือขั้นตอนที่จำกัดและชัดเจนสำหรับงานหนึ่งๆ การติดตาม (trace) บันทึกการเปลี่ยนแปลงสถานะ ความคงสภาพของลูป (loop invariant) อธิบายคุณสมบัติที่ถูกรักษาไว้ในการวนซ้ำแต่ละรอบและช่วยในการพิสูจน์ความถูกต้อง
- algorithm: กระบวนการจำกัดจำนวนขั้นตอนในการแก้ปัญหาที่กำหนด; boundary test: การทดสอบที่ขอบเขตของช่วงค่าเข้าที่ยอมรับได้
ก่อนใช้ binary search แบบปกติกับรายการ ต้องมีเงื่อนไขใด?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Binary search ทิ้งครึ่งของรายการโดยการเทียบกับค่าตรงกลาง ซึ่งใช้ได้ก็ต่อเมื่อรายการเรียงลำดับภายใต้กฎการเปรียบเทียบ ค่าซ้ำกันได้ และความยาวใดก็ได้
จับคู่แต่ละคำศัพท์เทคนิคกับความหมายที่แม่นยำ
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ใช้นิยามเพื่อแยกแยะปริมาณและกระบวนการที่เกี่ยวข้อง
เลือกหลักฐานมาทดสอบสมมติฐาน
- กำหนดเงื่อนไขอินพุตและผลลัพธ์ที่คาดหวัง ใช้กรณีขอบเขต ชุดข้อมูลว่างเมื่ออนุญาต ข้อมูลซ้ำ และค่าที่ไม่ถูกต้อง แยกอัลกอริทึมที่ผิด ออกจากการนำไปใช้ที่ผิด หรือข้อกำหนดที่ไม่สมบูรณ์
- ติดตามการค้นหาในรายการเรียงลำดับสมมติขนาดเล็ก ระบุ().'มาตรฐานการอ้างอิงดัชนี' สำหรับการค้นหาแบบเบี่ยง二分 (binary search) อัปเดตขอบเขตเพื่อให้ช่วงที่เหลือเล็กลง Reject อินพุตที่ไม่เรียงลำดับเว้นแต่การจัดเรียงจะเป็นส่วนหนึ่งของงาน
นิสัยสองอย่างใดทำให้การตรวจสอบหรือแบบจำลองในกรณีนี้รองรับได้มากขึ้น?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
การระบุเงื่อนไขและสมมติฐานช่วยให้ผู้อื่นทำงานซ้ำได้โดยถูกต้อง และการบันทึกหลักฐานรองรับช่วยให้พวกเขาตรวจสอบข้อสรุปได้ การซ่อนผลลัพธ์ที่ขัดแย้งกันจะกำจัดหลักฐานที่อาจทลายข้อสรุปที่ผิดพลาด และข้อมูลจากตัววัดเพียงหนึ่งค่าไม่สามารถใช้ยืนยันข้ออ้างที่กว้างขวางได้
ทำงานจากปริมาณที่ทราบค่า
- ระบุค่าที่ทราบและหน่วยของมัน เลือกความสัมพันธ์โดยพิจารณาว่าข้อสมมติฐานสอดคล้องกับเคสนี้ แล้วจัดรูปสมการก่อนแทนค่า
- ที่ทราบ: การค้นหาเชิงเส้นของรายการ 8 รายการ อาจต้องการ 8 ครั้งเปรียบเทียบเมื่อ itemCount ที่หาอยู่เป็นรายการสุดท้ายหรือไม่มีอยู่ การเพิ่มขนาดรายการสองเท่าจะเพิ่มจำนวนครั้งเปรียบเทียบในกรณี worst-case สองเท่าภายใต้โมเดลนี้ การค้นหาแบบเบี่ยง二分 ลดช่วงลงประมาณครึ่งหนึ่งในแต่ละขั้นตอนแต่ต้องใช้โครงสร้างที่จัดลำดับเหมาะสม
การค้นหาเชิงเส้นสแกน 14 รายการทั้งหมดโดยไม่พบ-match เกิดการเปรียบเทียบ itemCount กี่ครั้ง? ใช้ลำดับเดียวกัน: ปริมาณที่ทราบ → โมเดล → ความสัมพันธ์ → แทนค่า → หน่วยและการตีความ
การค้นหาแบบเชิงเส้นตรวจสอบทั้งหมด 14 พจน์โดยไม่พบสิ่งที่ต้องการ จงหาว่ามีการเปรียบเทียบจำนวน多少次?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ผลลัพธ์คือ 14 การเปรียบเทียบ ทราบแล้ว: การค้นหาแบบเชิงเส้นบน 14 รายการโดยไม่พบรายการ ต้องเปรียบเทียบทุกรายการก่อนจะมั่นใจว่าไม่มีรายการอยู่ ดังนั้นจำนวนการเปรียบเทียบ = 14 การค้นหาที่ไม่สำเร็จมีค่าใช้จ่ายเท่ากับความยาวทั้งหมดเสมอ
ตรวจสอบข้อสรุปและขอบเขต
- การทดสอบตัวอย่างสำเร็จไม่ได้พิสูจน์ความถูกต้องสำหรับอินพุตที่ถูกต้องทั้งหมด อย่านำไวยากรณ์伪โค้ดเฉพาะ Cambridge มาใช้ในหลักสูตร IB โดยไม่มีแหล่งที่มาของหลักสูตร
- กลับไปที่การสังเกตเดิม อธิบายว่าผลลัพธ์นี้สนับสนุนสิ่งใด มีเงื่อนไขใดบ้าง และเป็นอย่างไรในการทดสอบคำอธิบายอื่นที่ขัดแย้งกัน
ตัวอย่างทดสอบสำเร็จหนึ่งกรณีพิสูจน์ได้ว่าอัลกอริทึมถูกต้องสำหรับทุกอินพุตที่ถูกต้อง คำกล่าวนี้ไม่ถูกต้อง: การทดสอบผ่านหนึ่งกรณีแสดงว่าอัลกอริทึมทำงานกับอินพุตนั้นได้เท่านั้น ความถูกต้องต้องการการพิสูจน์เหนืออินพุตที่ถูกต้องทั้งหมดหรือการใช้หลักคณิตศาสตร์ - กรณีขอบเขตเช่นรายการว่างและค่าขอบเขตคือจุดที่โค้ดที่ไม่ได้ทดสอบมักล้มเหลว
อัลกอริทึม การติดตาม และหลักฐานความถูกต้อง: กำหนดเงื่อนไขอินพุตและผลลัพธ์ที่คาดหวัง ใช้กรณีขอบเขต ชุดข้อมูลว่างเมื่ออนุญาต ข้อมูลซ้ำ และค่าที่ไม่ถูกต้อง แยกอัลกอริทึมที่ผิด ออกจากการนำไปใช้ที่ผิด หรือข้อกำหนดที่ไม่สมบูรณ์
ตัวอย่างการทดสอบสำเร็จเพียงตัวอย่างหนึ่งพิสูจน์ได้ว่าอัลกอริทึมถูกต้องสำหรับทุกอินพุตที่มีข้อถูก
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การทดสอบผ่านหนึ่งครั้งแสดงเพียงว่าอัลกอริทึมทำงานได้กับอินพุตนั้นเท่านั้น ความถูกต้องต้องการการพิจารณาเหนืออินพุตที่ถูกต้องทั้งหมดหรือการพิสูจน์ - กรณีขอบเขต เช่น รายการว่างและค่าขอบเขต คือจุดที่โค้ด没有被ทดสอบจะล้มเหลว
กระบวนการจำกัดที่แก้ปัญหาที่กำหนด: เขียนคำศัพท์เทคนิค
Difficulty 1/5 · 100 coins + a small bonus on first completion today
อัลกอริทึมหมายถึง กระบวนการจำกัดจำนวนขั้นตอนในการแก้ปัญหาที่กำหนดให้