204512-53/lecture4 - ประวัติรุ่นแก้ไข

Campong: /* Multiplie Polynomials */

2010-10-07T10:52:55Z

Multiplie Polynomials

Campong: /* Multiplie Polynomials */

2010-10-07T10:33:08Z

Multiplie Polynomials

124.121.178.190: /* Ball and Bin */

2010-08-26T03:21:49Z

Ball and Bin

Molecule เมื่อ 04:55, 18 สิงหาคม 2553

2010-08-18T04:55:01Z

Campong เมื่อ 12:45, 17 สิงหาคม 2553

2010-08-17T12:45:47Z

Campong เมื่อ 12:41, 17 สิงหาคม 2553

2010-08-17T12:41:56Z

Campong เมื่อ 12:21, 17 สิงหาคม 2553

2010-08-17T12:21:05Z

Cpe0079: /* Fast Fourier transform (FFT) */

2010-08-12T17:39:59Z

Fast Fourier transform (FFT)

Cpe0079 เมื่อ 17:16, 12 สิงหาคม 2553

2010-08-12T17:16:26Z

Cpe0079 เมื่อ 17:15, 12 สิงหาคม 2553

2010-08-12T17:15:48Z

@@ แถว 121: / แถว 121: @@
 [http://www.calculusinmotion.com/DEMO-factor_squares/factor_squares.html]
 <br/>
 == Fast Fourier transform (FFT) ==

@@ แถว 116: / แถว 116: @@
 <math> f_{x_3} = (x^{3+2}y^{2+5})+(17x^{3+1}y^{2+3})+(2x^{1+2}y^{1+5})+((2*17)x^{1+1}y^{1+3})</math> <br/>
 <math> f_{x_3} = (x^{5}y^{7})+(17x^{4}y^{5})+(2x^{3}y^{6})+(34x^{2}y^{4})</math> <br/>
 == Fast Fourier transform (FFT) ==

@@ แถว 96: / แถว 96: @@
 #โดยเฉลี่ยแล้วมีถังว่างกี่ถัง  ต้องการหาจำนวนถังว่างซึ่งเป็นตัวแปรสุ่ม ซึ่งจะไม่มีค่าจนกว่าจะได้ทำการทดลอง  แต่เราสามารถพูดถึงคุณสมบัติบางอย่างได้บ้างเหมือนกันแม้ว่าจะไม่ได้ทดลอง   เวลาพูดถึงตัวแปรสุ่มมีคุณสมบัติอย่างหนึ่งที่มีความหมายคือ ค่า Expectation ของมัน (หรืออาจเรียกว่า ค่าเฉลี่ยตัวแปรสุ่ม)<br />
 ::สำหรับตัวแปรสุ่ม x ใดๆ <br />
-::<math>E[x] = \sum_{i=-\infty}^\infty 1×Pr[x=i]</math><br />
+::<math>E[x] = \sum_{i=-\infty}^\infty i×Pr[x=i]</math><br />
 ::ในการค่าค่า expectation ของจำนวนถังว่างเมื่อมี n ถังลูกบอล m ลูก จะยากมาก เนื่องจากมันขึ้นต่อกันอยู่ ในการวิเคราะห์ จะใช้คุณสมบัติที่สำคัญของ expectation คือ linearity of expectation คือ<br />
 ::สำหรับตัวแปรสุ่ม x,y ใดๆ จะขึ้นต่อกันก็ได้ หรือไม่ขึ้นต่อกันก็ได้ เช่นจำนวนถังว่าง กับจำนวนถังที่ไม่ว่าง<br />

←รุ่นแก้ไขก่อนหน้า	รุ่นแก้ไขเมื่อ 04:55, 18 สิงหาคม 2553
แถว 9:	แถว 9:


	+	== Integer Multiplication ==
	+
	+	การคูณเลข n x m bits
	+	ให้ X และ Y เป็นเลข n และ m bits ตามลำดับ
	+
	+	ซึ่งสามารถเขียนได้ในรูป <math> X = A + B </math> และ <math> Y= C + D </math>
	+
	+	[[ไฟล์:lec4_integer_x.png]]
	+
	+	[[ไฟล์:lec4_integer_y.png]]
	+
	+
	+	ผลคูณของ X และ Y สามารถเขียนได้ในรูป
	+
	+	<math> X \dot Y = A \cdot C \cdot2^n + (B \cdot C + A \cdot D) 2^m + B \cdot D</math>
	+
	+	ซึ่งเขียนเป็น recurrent relation ได้เป็น
	+
	+	<math>T(n) = 4T(\frac{n}{2}) + c \cdot n = O(n^2)</math>
	+
	+
	+	[[ไฟล์:lec4_recurrent_n_div_2.png]]
	+
	+
	+	จำนวนครั้งของการคูณ คือ AC, BC, AD, BD => 4 ครั้ง
	+
	+	<math>2^n , 2^m</math> เป็นการ shift bit
	+
	+	factor 2 ตัวของการแก้ปัญหาด้วยวิธีการ Divide & Conquer คือ
	+	1. จำนวนปัญหาที่แบ่งได้ ปัญหาลดขนาดไปได้แค่ไหน
	+	2. จำนวนปัญหาย่อยที่เกิดขึ้น หลังจากการแบ่งปัญหาใหญ่
	+
	+	การทำให้ algorithm นี้เร็วขึ้นได้ด้วยการใช้ Divide & Conquer ทำได้โดย ทำให้ตัวหารเพิ่มขึ้น หรือไม่ก็ทำให้ตัวคูณลดลง
	+	ซึ่งมีวิธีการที่ทำให้การคูณลดเหลือ สามครั้งได้
	+	และ จะทำให้ได้ Recurrent เป็น
	+
	+	<math>T(n) = 3T(\frac{n}{2}) + c \cdot n</math>
	+
	+	สำหรับ <math>T(n) = 3T(\frac{n}{2}) + c \cdot n</math> ได้ <math> O(n^log_{2}^{3}) = O(n^{1.58})</math>
	+	ซึ่งแย่กว่า Linear แต่ดีกว่า <math> n^2 </math>
	+
	+
	+	สมมติว่าถ้าทำให้สามารถลดงานได้เป็น n/3 (แต่จำนวนการคูณเท่าเดิม)
	+	<math>
	+	T(n) = 4T(n/3) + cn
	+	=> O(n^{log_{4}3})
	+	</math>
	+
	+
	+	จำนวนการคูณที่ลดเหลือ 3 ครั้ง ทำให้ลดลงทุกๆ ชั้นของการเรียกตัวเอง ทำให้ <math> O(n^2) => O(n^{1.58}) </math>
	+	เร็วขึ้นประมาณ 1000 เท่า

@@ แถว 68: / แถว 68: @@
 == Fast Fourier transform (FFT) ==
 คือ Algorithm ที่ใช้สำหรับหาผลคูณของสมการ Polynomial Degree-d เช่นผลคูณของสมการ Polynomial Degree เท่ากับ 2 <br/><br/>
-<math>(1+2x+3x^2).(2+x+4x^2)= 2+5x+12x^2+11x^3+12x^4</math><br/><br/>
+<math>(1+2x+3x^2)*(2+x+4x^2)= 2+5x+12x^2+11x^3+12x^4 </math> <br/><br/>
-ถ้า <math>A(x)=a_0+a_1x+...+a_dx^d</math> และ <math>B(x)=b_0+b_1x+...+b_dx^d</math><br/><br/>
+ถ้า <math> A(x)=a_{0}+a_{1x}+...+a_{dx}^d </math> และ <math> B(x)=b_0+b_{1x}+...+b_{dx}^d </math><br/><br/>
-จะได้ผลคูณเท่ากับ <math>C(x) = A(x).B(x)=c_0+c_1x+...+c_{2d}x^{2d}</math>
+จะได้ผลคูณเท่ากับ <math> C(x) = A(x)*B(x)= c_{0}+c_{1x}+...+c_{2d}x^{2d} </math>
-ซึ่งจะหาค่า coefficients <math>c_k</math> ได้จาก<br/><br/>
+ซึ่งจะหาค่า coefficients <math> c_{k} </math> ได้จาก<br/><br/>
-<math>c_k=a_0b_k+a_1b_{k-1}+...+a_kb_0 = \sum_{i=0}^k a_ib_{k-i}</math> <br/><br/>
+<math> c_k=a_0b_k+a_1b_{k-1}+...+a_kb_0 = \sum_{i=0}^k a_ib_{k-i} </math> <br/><br/>

@@ แถว 52: / แถว 52: @@
 [[ไฟล์:2553w04_ball&bin02.jpg|center|400px|]]
 :4.  ถ้าเราไม่ต้องการให้มีถังว่างจะต้องโยนลูกบอลกี่ลูก ……หมดคาบ <br/>
 ==Multiplie Polynomials ==
 Polynomials คือ สมการที่มีตัวแปลเป็นเลขยกกำลัง <math> f_x = a_{i}^n+...+a_{i+m}^{n-c}</math> <br />เช่น <math>f_x = 3x^3y^2+\frac{5x^2}{y}+96x  </math><br/>
@@ แถว 58: / แถว 59: @@
 <math>f_{x_1} = x^3y^2+2xy</math> เป็นสมการที่ 1 <br/>
 <math>f_{x_2} = x^2y^5+17xy^3</math> เป็นสมการที่ 2 <br/>
-เมื่อต้องการ <math>f_{x_3} = f_x1 * f_x2 </math>จะได้ว่า <br/>
+เมื่อต้องการ <math>f_{x_3} = f_{x_1} * f_{x_2} </math>จะได้ว่า <br/>
 <math> f_{x_3} = (x^3y^2+2xy)*(x^2y^5+17xy^3)</math> <br/>
 <math> f_{x_3} = (x^3y^2*(x^2y^5+17xy^3))+(2xy*(x^2y^5+17xy^3))</math> <br/>
+<math> f_{x_3} = (x^3y^2*x^2y^5)+(x^3y^2*17xy^3)+(2xy*x^2y^5)+(2xy*17xy^3)</math> <br/>
 == Fast Fourier transform (FFT) ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:39, 12 สิงหาคม 2553
แถว 53:		แถว 53:
	:4. ถ้าเราไม่ต้องการให้มีถังว่างจะต้องโยนลูกบอลกี่ลูก ……หมดคาบ <br/>		:4. ถ้าเราไม่ต้องการให้มีถังว่างจะต้องโยนลูกบอลกี่ลูก ……หมดคาบ <br/>
	== Fast Fourier transform (FFT) ==		== Fast Fourier transform (FFT) ==
		+	คือ Algorithm ที่ใช้สำหรับหาผลคูณของสมการ Polynomial Degree-d เช่นผลคูณของสมการ Polynomial Degree เท่ากับ 2 <br/><br/>
		+	<math>(1+2x+3x^2).(2+x+4x^2)= 2+5x+12x^2+11x^3+12x^4</math><br/><br/>
		+	ถ้า <math>A(x)=a_0+a_1x+...+a_dx^d</math> และ <math>B(x)=b_0+b_1x+...+b_dx^d</math><br/><br/>
		+	จะได้ผลคูณเท่ากับ <math>C(x) = A(x).B(x)=c_0+c_1x+...+c_{2d}x^{2d}</math>
		+	ซึ่งจะหาค่า coefficients <math>c_k</math> ได้จาก<br/><br/>
		+	<math>c_k=a_0b_k+a_1b_{k-1}+...+a_kb_0 = \sum_{i=0}^k a_ib_{k-i}</math> <br/><br/>