T.2 · คณิตศาสตร์เชิง rời, ความน่าจะเป็น และวิธีการเชิงตัวเลข

เตรียมสอบ GRE ระดับปริญญาตรี วัตถุประสงค์ภายในขอบเขต ETS ที่ทบทวนนี้คือการสอนต้นฉบับ ไม่ใช่การทดสอบหรือตัวทำนายคะแนนอย่างเป็นทางการ

ความรู้พื้นฐาน: การนับจำนวนเบื้องต้น, ความน่าจะเป็น, สมการผลรวมซ้ำ และการหาอนุพันธ์

• ใช้การนับจำนวน, สมการผลรวมซ้ำ, การคิดเกี่ยวกับกราฟ และตรรกะ
• คำนวณความน่าจะเป็นและคุณสมบัติของการแจกแจง
• ใช้การประมาณค่าเชิงตัวเลขและประเมินความผิดพลาด

สมการผลรวมซ้ำ (recurrence): กฎที่เชื่อมพจน์ของลำดับเข้ากับพจน์ก่อนหน้า

เหตุการณ์ที่ไม่สามารถเกิดขึ้นร่วมกันได้ (mutually exclusive): เหตุการณ์ที่ไม่สามารถเกิดขึ้นพร้อมกันได้

เลือกโมเดลการนับก่อน: การเลือก r วัตถุที่แตกต่างกันแบบเรียงลำดับใช้ n(n−1)⋯(n−r+1), ส่วนเซตย่อยที่ไม่เรียงลำดับใช้ C(n,r) กราฟง่ายเต็มรูปแบบที่มี n จุดยอดมีหนึ่งเส้นเชื่อมสำหรับคู่จุดยอดที่ไม่เรียงลำดับแต่ละคู่ ซึ่งให้ n(n−1)/2 เส้น;若有 loops หรือ multiple edges จะเปลี่ยนโมเดล สำหรับ n เส้นในตำแหน่งทั่วไปบนระนาบ เส้นที่ k ตัดเส้นก่อนหน้า k−1 เส้นที่จุดที่แตกต่างกันและเพิ่มพื้นที่ใหม่ k พื้นที่ รวมทั้งหมดคือ 1+n(n+1)/2; เส้นขนานหรือสามเส้นตัดกันที่จุดเดียวกันจะทำให้การนับนี้ไม่ถูกต้อง

ใช้ส่วนเสริมในการนับอย่างน้อยหนึ่งครั้ง และกำหนดเงื่อนไขต่อประชากรที่เหลือจริงหลังจากการสุ่มโดยไม่แทนที่ สำหรับ r ผลลัพธ์ iid ที่เลือกจาก n ค่าที่มีความน่าจะเป็นเท่ากัน ความน่าจะเป็นที่ทั้งหมดจะแตกต่างกันคือ n(n−1)⋯(n−r+1)/n^r เมื่อ r≤n ส่วนเสริมของมันนับผลลัพธ์ที่ซ้ำกัน สำหรับการนับแบบ binomial ที่มี N การทดลองที่เป็นอิสระและโอกาสสำเร็จคงที่ p ค่าเฉลี่ยคือ Np และความแปรปรวนคือ Np(1−p) ความน่าจะเป็นที่เท่ากันเพียงอย่างเดียวไม่足以确立ความเป็นอิสระ

สมการผลรวมซ้ำอธิบายค่าที่ตามมาจากค่าก่อนหน้าและต้องการข้อมูลเริ่มต้นเพียงพอที่จะกำหนดลำดับ แยกตัวชี้ออกจากค่า: a_n=2a_(n−1) พร้อม a_0=3 ให้ a_n=3·2^n การคิดเกี่ยวกับกราฟและอัลกอริทึมมักใช้เพื่อบ่งชี้ว่าจุดยอดหรือขั้นตอนใหม่เพิ่มอะไรเข้าไป สูตรปิดควรสอดคล้องทั้งกับสมการผลรวมซ้ำและเงื่อนไขเริ่มต้น การจับคู่พจน์ที่สังเกตได้น้อยๆ ไม่ได้พิสูจน์它为ทุกตัวชี้

การประมาณค่าเชิงตัวเลขต้องใช้ข้อโต้แย้งเรื่องความผิดพลาด Bisection รักษาช่วงที่มีสัญญาณเปลี่ยนสำหรับฟังก์ชันต่อเนื่องและลดครึ่งความกว้างของแต่ละขั้นตอน; อาจไม่มีศูนย์ถ้าความล้มเหลวของความต่อเนื่อง การอัปเดต Newton คือ x_new=x−f(x)/f′(x) ซึ่งต้องการอนุพันธ์ที่ไม่เป็นศูนย์ที่จุดปัจจุบัน; การลู่เข้าไม่เกิดอัตโนมัติจากทุกค่าเริ่มต้น ค่า residual ของการประมาณและความผิดพลาดใน x นั้นต่างกัน ควรระบุสมมติฐานของวิธีการและเกณฑ์หยุดทำงาน แทนที่จะ treating extra displayed decimals ว่าเป็นความแม่นยำ

สำหรับ f(x)=x²−2 และ x₀=1, ขั้นตอนของนิวตันให้ 1−(1−2)/2=1.5. ค่าถัดไปคือ 1.5−0.25/3=1.4167. ค่าเหล่านี้ประมาณ sqrt(2), แต่ f′(0)=0 ทำให้จุดเริ่มต้นเป็นศูนย์ไม่ถูกต้อง

เหตุการณ์ที่มีความน่าจะเป็นบวกไม่สามารถเป็นอิสระต่อกันและเป็นเหตุขัดแย้งกันได้พร้อมกัน

การสุ่ม 4 ครั้งที่มีฉลากเป็นอิสระต่อกันและมีความน่าจะเป็นเท่ากันจากสัญลักษณ์ 5 ตัว โดยมีการนำกลับมาใช้ใหม่ จงหาความน่าจะเป็นที่จะมีอย่างน้อยสองครั้งที่ได้ค่าเหมือนกัน เปรียบเทียบจำนวนการจัดลำดับและการเลือกแบบไม่เรียงลำดับของสัญลักษณ์ที่แตกต่าง 4 ตัว

วิธีทำตัวอย่าง

มี $5^4$ สายการสุ่มที่เป็นไปได้เท่าๆ กัน สายที่ไม่ซ้ำกันมี $5\cdot4\cdot3\cdot2=120$ สาย

การเลือกแบบเรียงลำดับที่แตกต่างกันมี 120 แบบ; เซตย่อยแบบไม่เรียงลำดับมี $\binom54=5$ แบบ แต่ละเซตย่อยปรากฏใน $4!=24$ รูปแบบการจัดลำดับ การหารด้วย $4!$ เหมาะสมสำหรับการนับแบบไม่เรียงลำดับเท่านั้น ไม่ใช่ส่วนแบ่งของความน่าจะเป็นจากการสุ่ม

ใช้วิธีทอนช่วงเพื่อหาค่า $f(x)=x^3-2$ บน $[1,2]$ ให้ช่วงที่คงไว้สองแรกแรกและขอบเขตของความคลาดเคลื่อนของจุดกึ่งกลางหลังจากทอนช่วงสิบครั้ง ควรใช้วิธีการทอนช่วงสำหรับ $1/x$ บน $[-1,1]$ เพียงแค่จากการเปลี่ยนเครื่องหมายเพียงอย่างเดียวหรือไม่?

ตรวจสอบหลังทำแบบฝึกหัดแล้ว

พหุนามนี้เป็นฟังก์ชันต่อเนื่อง; $f(1)<0<f(2)$ จุดกึ่งกลางแรกคือ $1.5$ ซึ่งมีค่าบวก จึงเก็บช่วง $[1,1.5]$ ไว้ จุดถัดไปคือ $1.25$ ซึ่งมีค่าลบ เก็บช่วง $[1.25,1.5]$ ไว้ หลังจากการแบ่งครึ่งสิบครั้ง ความกว้างจะเท่ากับ $2^{-10}$ และจุดกึ่งกลางของช่วงที่คงไว้นั้นจะต่างจากรากในช่วงนั้นไม่เกิน $2^{-11}=1/2048$ ขอบเขตความคลาดเคลื่อนใช้ช่วงนี้ ไม่ใช่ค่าคงค้างเล็กน้อยเพียงอย่างเดียว สำหรับ $1/x$ ค่าศูนย์เป็นจุดเอกฐานและไม่รากใด มีฟังก์ชันต่อเนื่องบนช่วงไม่ได้ เครื่องหมายตรงปลายคู่ขัดแย้งกันไม่อาจใช้วิธีการนี้ได้