ผลต่างระหว่างรุ่นของ "204512/บรรยาย 2"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 4 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน)
แถว 1: แถว 1:
 +
{{หัวคำบรรยาย|204512}}
 +
'''จดบันทึกคำบรรยายโดย:''' ''(กรุณาใส่ด้วย)''
 
== เกริ่นนำ ==
 
== เกริ่นนำ ==
 
 
หลักการของ Divide and Conquer Algorithm ประกอบไปด้วย 3 ส่วนดังนี้
 
หลักการของ Divide and Conquer Algorithm ประกอบไปด้วย 3 ส่วนดังนี้
 
:1.แตกย่อยปัญหาเป็นชิ้นเล็ก หลายชิ้น
 
:1.แตกย่อยปัญหาเป็นชิ้นเล็ก หลายชิ้น
แถว 130: แถว 131:
 
เราให้ Matrix ของ <math>\omega</math> ตรงกลางนั้นชื่อว่า M โดยมันมีรูปแบบที่เรียกว่า Vandermonde Matrix ที่ระบุว่า Matrix ในรูปแบบนี้จะมี Inverse เสมอ
 
เราให้ Matrix ของ <math>\omega</math> ตรงกลางนั้นชื่อว่า M โดยมันมีรูปแบบที่เรียกว่า Vandermonde Matrix ที่ระบุว่า Matrix ในรูปแบบนี้จะมี Inverse เสมอ
  
การพิสูจน์สมการการ Interpolate นั้นทำโดยการมอง Matrix M เป็น Matrix ที่ Map เวคเตอร์จาก Space หนึ่งๆ ไปอีก Space หนึ่ง ซึ่งหากทุกแกนของ Space ใหม่นั้นตั้งฉากกันทั้งหมด เราจะสามารถบอกได้ว่าการ Inverse จะทำให้ได้ค่าเดิม คือ Coefficient กลับมาเสมอ
+
การพิสูจน์สมการการ Interpolate นั้นทำโดยการมอง Matrix M เป็น Matrix ที่ Map เวคเตอร์จาก Space หนึ่งๆ ไปอีก Space หนึ่ง ซึ่งหากทุกแกนของ Space ใหม่นั้นตั้งฉากกันทั้งหมด เราจะสามารถบอกได้ว่าการ Inverse จะทำให้ได้ค่าเดิม คือ Coefficient กลับมาเสมอ และสามารถใช้สูตร
 +
 
 +
<center><math>M_n(\omega)^{-1} = \frac{1}{n} M_n(\omega^{-1})</math></center>
 +
 
 +
ซึ่ง <math>\omega^{-1}\,</math> ก็ยังคงเป็น Root of Unity อยู่ ทำให้เราสามารถใช้อัลกอลิธึ่มเดิมทำงานได้ต่อไป
 +
 
 +
ขั้นตอนต่อไปคือการพิสูจน์ว่าแมทริกซ์ M นั้นทุก Column (ซึ่งเป็นเวคเตอร์) ตั้งฉากกันทั้งหมด โดยสามารถทำได้จากการทำ inner product ตามสมการ
 +
 
 +
<center><math>u \cdot v^* = u_0 v_0^* + u_1 v_1^* + \cdots + u_{n-1} v_{n-1}^*</math> โดยที่ <math>v^* \,</math> คือ Conjugate ของ <math>v \,</math></center>
 +
 
 +
โดยที่การทำ inner product จะให้ผลลัพธ์สูงสุดเมื่อเวคเตอร์ขนานกัน และให้ผลลัพธ์เป็นศูนย์เมื่อเวคเตอร์ตั้งฉากกัน
 +
 
 +
ในกรณีของ M ที่กล่าวถึงข้างต้น เมื่อเราเลือกคอลัมน์ i และ j ใดๆ มาหามุมระหว่างกันแล้วจะได้ inner product ว่า
 +
 
 +
<center><math>1+\omega^{i-j}+\omega^{2(i-j)}+\cdots+\omega^{(n-1)(i-j)}</math></center>
 +
 
 +
ซึ่งเป็นอนุกรมเลขาคณิตที่มีอัตราส่วนเป็น <math>\omega^{(i-j)}</math> ทำให้เราได้ผลลัพธ์ของอนุกรมเป็น <math>\frac{1 - \omega^{n(i-j)}}{1-\omega^{i-j}}</math> แต่เนื่องจาก <math>\omega</math> เป็น Root of Unity ทำให้<math>\omega^n = 1</math> เสมอ อนุกรมนี้จึงได้ 0 ทั้งหมดนี้เราจึงได้พิสูจน์ว่าเราสามารถใช้อัลกอลิธึ่ม FFT ในการทำ Interpolate สมการกลับมาได้ และทำให้อัลกอลิธึ่มรวมใช้เวลาการทำงานอยู่ใน <math>\mathcal{O}(n\log{n})</math>
 
----
 
----
  

รุ่นแก้ไขปัจจุบันเมื่อ 05:09, 9 สิงหาคม 2550

บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

จดบันทึกคำบรรยายโดย: (กรุณาใส่ด้วย)

เกริ่นนำ

หลักการของ Divide and Conquer Algorithm ประกอบไปด้วย 3 ส่วนดังนี้

1.แตกย่อยปัญหาเป็นชิ้นเล็ก หลายชิ้น
2.ทำการแก้ปัญหาย่อยเหล่านี้ด้วยวิธีการที่คล้ายกัน
3.คำตอบสุดท้ายหาได้จากการสรุปคำตอบทั้งหมดของทุกปัญหาย่อย

ดังจะเห็นได้จากปัญหาทั้งในชีวิตประจำวัน และปัญหาทางทฤษฎีคอมพิวเตอร์ สามารถเปรียบเทียบกรรมวิธี Divide and Conquer Algorithm กับ Lagacy Algorithm ได้ว่ามีประสิทธิ์ภาพต่างกันมากน้อยเพียงใด ซึ่งวิธีที่เปรียบเทียบเป็นที่นิยมโดยทั่วไปคือการหา Big O Notation มาเปรียบเทียบกัน


การวิเคราะห์เปรียบเทียบ Algorithm โดยการหา Big O Notation

Definition 1

 
T of n is in Big-Oh of f of n iff there're constants and such that
for all
กราฟแสดงตัวอย่าง Big-Oh ตามนิยาม
เช่น

จะเห็นได้ว่า definition 1 เป็นจริงได้เมื่อ

โดยทั่วไปแล้ว Big-Oh คือการแสดง Upper Bound ของฟังก์ขั่น ขณะที่ Big-Omega () เป็นการแสดงถึง Lower Bound ของฟังก์ชั่น


ตัวอย่างปัญหา ที่ใช้กรรมวิธีแก้ไขแบบ Divide & Conquer

Multiplication

การคูณกันของ ที่เป็น binary number ขนาด n-bit สามารถแยกออกได้เป็น

  • สามารถสังเกตได้ว่า ประกอบไปด้วยพจน์ที่คูณกัน 4 ชุด

นิยาม Function ของเวลาที่ใช้ในการคำนวณตัวเลข n-bit เป็น

ภาพตัวอย่างการแตกปัญหาออกเป็นส่วนๆ ตามการคำนวณตามวิธีปรกติ


จากภาพ Tree มีความสูง ทำให้ได้ว่า

Gauss ได้เสนอวิธีการคูณในอีกรูปแบบหนึ่งที่ใช้การคูณเพียงสามครั้งจาก ทำให้อัลกอลิธึ่มได้รับการปรับปรุงเป็น ซึ่งเมื่อคำนวณในรูปแบบเดียวกับ Tree ด้านบนโดยถือว่าแต่ละ node จะมีลูกอยู่ 3 ชุดแทนที่จะเป็น 4 ชุด เราจะได้ว่า

Merge Sort

Merge Sort เป็นอัลกอลิธึ่มแบบ Devide-and-Conquer อีกอันหนึ่งที่ อาศัยการแบ่งข้อมูลออกเป็นส่วนเล็กๆ แล้วเรียงลำดับให้ถูกต้อง แล้วจึงนำข้อมูลที่เรียงแล้วกลับมาต่อกัน

กระบวนการทำ Merge Sort มีสามขั้นคือ

  • การแบ่งส่วนข้อมูล ได้ทำได้ทันที
  • การเรียงข้อมูล ที่แบ่งไปครึ่งๆ แล้ว ใช้เวลา
  • การนำข้อมูลที่เรียงแล้วสองชุดมาต่อกันใช้เวลา

โดยรวมแล้ว Merge Sort ใช้เวลาในการทำงาน

หรือก็คือ

Fast Furier Transform

กราฟแสดงการหาสมการผลลัพธ์จากการคูณค่าในแต่ละจุดของสมการตั้งต้น ภาพจากWalterzorn.com

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

  • สมการ Polynomial ที่มี degree เป็น d ใดๆ สามารถสร้างขึ้นจากการหาค่าผลของสมการที่ตำแหน่งต่างๆ จำนวน d+1 ตำแหน่ง
  • เมือนำสมการ Polynomial degree d สองสมการมาคูณกัน เราจะได้สมการ Polynomial degree เป็น 2d
  • ดังนั้นหากเราหาค่าของสมการตั้งต้นสองสมการจำนวน 2d+1 จุด แล้วนำมาคูณกัน สุดท้ายแล้วเราจะได้ค่า 2d+1 จุดที่สามารถนำไป Interpolate กลับมาเป็นสมการผลคูณของ Polynomial สองสมการได้

Devide and Conconquer

เริ่มจากพิจารณาสมการ Polynomial degree-n ใดๆ เช่น เราสามารถหาค่าของจุดต่างๆ จำนวน n จุดได้ โดยหาค่าทั้งในฝั่งบวกและลบไปพร้อมๆ กัน เช่นพิจารณาจุด เราจะสามารถแยกพิจารณากรณีคู่และคี่ไปพร้อมๆ กันได้โดยการแยกตัวประกอบเพื่อให้ทุกพจน์มี degree เป็นคู่เสมอ ดังเช่นตัวอย่าง

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


จากข้างบนทำให้เราสามารถย่อยป้ญหาให้เล็กลงครึ่งหนึ่งได้ แต่ในระบบจำนวนจริงเราไม่สามารถแบ่งปัญหาให้เล็กลงไปกว่าครึ่งได้อีกเพราะการยกกำลังสองในครั้งแรกก็ทำให้เลขทุกตัวกลายเป็นจำนวนบวกไปหมด แต่เราสามารถใช้จำนวนเชิงซ้อนในรูปแบบ Root of Unity เพื่อให้สามารถแบ่งปัญหาลงไปเรื่อยๆ ได้โดยการใช้ Root of Unity มีคุณสมบัติที่น่าสนใจสองประการคือ

  • มีคู่ตรงข้ามเสมอ ทำให้สามารถยกกำลังสองเพื่อหาค่าทั้งสองค่าในครั้งเดียวได้
  • การยกกำลังสองในแต่ละครั้งจะทำให้ได้ Root of Unity ในอับดับที่ เสมอ

การคำนวณค่าของการคูณสมการ Polynomial ใดๆ จึงสามารถทำได้ โดยพิจารณาว่าสมการผลลัพธ์จะมี degree เป็นเท่าใด แล้วเลือกใช้งาน Root of Unity ในลำดับที่สูงกว่านั้นทำให้สามารถคำนวณหาค่าของทุกจุดได้ในเวลาเพียง

Interpolation

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

แต่คุณสมบัติของฟังก์ขั่น FFT ที่เราใช้ในการพิจารณาค่าในส่วนที่แล้ว มีคุณสมบัติที่น่าแปลกคือ

จาก เราจะได้ว่า ซึ่งเนื่องจากสมการในการ Interpolate นั้นเป็นสมการเดียวกับที่ใช้ในการพิจารณาค่าทำให้เราได้ว่าอัลกอลิธึ่มนี้มีความเร็ว เสมอ

Proof of Interpolation

การที่เราสามารถพิจารณาค่าจำนวน n จุดของสมการ Polynomial ได้นั้น เราสามารถมองว่าเป็นการคูณกันระหว่าง Matrix ของ Coeffient และ Matrix ของตัวแปร ดังสมการต่อไปนี้

เราให้ Matrix ของ ตรงกลางนั้นชื่อว่า M โดยมันมีรูปแบบที่เรียกว่า Vandermonde Matrix ที่ระบุว่า Matrix ในรูปแบบนี้จะมี Inverse เสมอ

การพิสูจน์สมการการ Interpolate นั้นทำโดยการมอง Matrix M เป็น Matrix ที่ Map เวคเตอร์จาก Space หนึ่งๆ ไปอีก Space หนึ่ง ซึ่งหากทุกแกนของ Space ใหม่นั้นตั้งฉากกันทั้งหมด เราจะสามารถบอกได้ว่าการ Inverse จะทำให้ได้ค่าเดิม คือ Coefficient กลับมาเสมอ และสามารถใช้สูตร

ซึ่ง ก็ยังคงเป็น Root of Unity อยู่ ทำให้เราสามารถใช้อัลกอลิธึ่มเดิมทำงานได้ต่อไป

ขั้นตอนต่อไปคือการพิสูจน์ว่าแมทริกซ์ M นั้นทุก Column (ซึ่งเป็นเวคเตอร์) ตั้งฉากกันทั้งหมด โดยสามารถทำได้จากการทำ inner product ตามสมการ

โดยที่ คือ Conjugate ของ

โดยที่การทำ inner product จะให้ผลลัพธ์สูงสุดเมื่อเวคเตอร์ขนานกัน และให้ผลลัพธ์เป็นศูนย์เมื่อเวคเตอร์ตั้งฉากกัน

ในกรณีของ M ที่กล่าวถึงข้างต้น เมื่อเราเลือกคอลัมน์ i และ j ใดๆ มาหามุมระหว่างกันแล้วจะได้ inner product ว่า

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


แหล่งข้อมูล​อื่น​

อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia

อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia

Inner Product ใช้ในการพิสูจน์เรื่อง Manipulation