ผู้ใช้:Chatchapol - ประวัติรุ่นแก้ไข

Chatchapol เมื่อ 19:14, 4 ตุลาคม 2553

2010-10-04T19:14:54Z

Chatchapol เมื่อ 17:57, 4 ตุลาคม 2553

2010-10-04T17:57:28Z

Chatchapol เมื่อ 17:15, 4 ตุลาคม 2553

2010-10-04T17:15:11Z

Chatchapol เมื่อ 16:53, 4 ตุลาคม 2553

2010-10-04T16:53:13Z

Chatchapol: หน้าที่ถูกสร้างด้วย '== '''204512-53/lecture13''' == '''จดบันทึกคำบรรยายโดย:''' นายชัชพล นุโย…'

2010-10-04T16:44:02Z

หน้าที่ถูกสร้างด้วย '== '''204512-53/lecture13''' == '''จดบันทึกคำบรรยายโดย:''' นายชัชพล นุโย…'

หน้าใหม่

== '''204512-53/lecture13''' ==
'''จดบันทึกคำบรรยายโดย:'''
นายชัชพล นุโยค รหัส 5214550049
นายสุรเดช วัฒนอุดมโรจน์ รหัส 5214550320

----

'''== NP Completeness =='''

----
<<

<<

'''Lemma''' : พิจารณาเซต <math>ใส่สูตรที่นี่</math>

@@ แถว 2: / แถว 2: @@
 '''จดบันทึกคำบรรยายโดย:'''
    นายชัชพล  นุโยค        รหัส 5214550049
-   นายสุรเดช  วัฒนอุดมโรจน์  รหัส 5214550320
+   นายสุรเดช  วัฒนอุดมโรจน์  รหัส 5214550324
 ----
-'''== NP Completeness =='''
+''' NP Completeness '''
 ----
-<<
+NP: Non-deterministic Polynomial time คือ เซตของ Algorithm ที่ไม่สามารถแก้ไขปัญหาได้ในเวลาที่เป็น polynomial โดยการนิยามเซตของปัญหาเพื่อประโยชน์ในการเปรียบเทียบระดับความยาก-ง่ายของ Algorithm ซึ่งเซตของปัญหาสามารถแบ่งเป็นเซต P, NP, NP-hard และ NP-complete
-<<
+ในการเปรียบเทียบ Algorithm ใดๆ เราจะทำการพิจารณา Algorithm ว่าจัดอยู่ในเซตของปัญหาใด โดยใช้เทคนิคการลดรูปของปัญหา (Reduction) ว่าเป็นกลุ่มเดียวกับปัญหาที่อยู่ในเซตหรือไม่ ถ้าอยู่ในกลุ่มเดียวกันจะกล่าวว่า Algorithm มีความยากเท่ากัน ความยาก คือ มี Algorithm ที่มีประสิทธิภาพแก้ไขปัญหาหรือไม่
 '''Lemma''' : พิจารณาเซต [[ไฟล์:NPComplete1.gif‎]] ใดๆ ให้ A เป็น imdenpendent set โดย V-A เป็น Vertec Cover

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:57, 4 ตุลาคม 2553
แถว 14:		แถว 14:

	'''Lemma''' : พิจารณาเซต [[ไฟล์:NPComplete1.gif‎]] ใดๆ ให้ A เป็น imdenpendent set โดย V-A เป็น Vertec Cover		'''Lemma''' : พิจารณาเซต [[ไฟล์:NPComplete1.gif‎]] ใดๆ ให้ A เป็น imdenpendent set โดย V-A เป็น Vertec Cover
		+
	'''Proof''' : Indenpendent set [[ไฟล์:NPComplete2.gif‎]]Vertex Cover		'''Proof''' : Indenpendent set [[ไฟล์:NPComplete2.gif‎]]Vertex Cover
		+
		+	'''นิยาม''' : ปัญหา A เป็น Polynomial time เพื่อลดปัญหา B ถ้ามี Algorithm T ที่ทำงานใน Polynomial time สำหรับทุกๆ instance X ของ A จะได้ T(x) เป็น instance ของ B
		+
		+	[[ไฟล์:NPComplete3.gif]]
		+
		+	X' = T(x) เป็น instance ของ B และ \|X'\| = Poly (\|X\|)
		+	ถ้า x เป็น instance ตอบ "Yes" ใน A
		+	=> x' เป็น instance ตอบ "Yes" ใน B
		+
		+	ถ้า x เป็น instance ตอบ "No" ใน A
		+	=> x' เป็น instance ตอบ "No" ใน B
		+
		+	'''Lemma''' : ถ้า A [[ไฟล์:NPComplete2.gif‎]]B และมี Algorithm ที่แก้ปัญหา B ได้ใน Polynomial time จะมี Algorithm ที่แก้ปัญหา A ใน Polynomial time ได้ด้วย
		+
		+	'''Proof''' : ให้ M เป็น Polynomial time Algorithm ที่แก้ปัญหา B
		+	จะได้ว่า A [[ไฟล์:NPComplete2.gif‎]] B
		+	นั้นคือ มี Polynomial time Algorithm T ที่ [[ไฟล์:NPComplete4.gif]]instance x ของ A
		+	x' = T(x) มีขนาด poly(\|x\|) และคำตอบของ x ในปัญหา A ตรงกับของ x' ในปัญหา B
		+
		+	สำหรับ Algorithm M' ดังนี้
		+
		+	M'(x) :
		+	x' = T(x)
		+	return M(x')
		+
		+
		+	แต่เนื่องจาก \|x'\| = poly(\|x\|)
		+	ดังนั้น เวลาในการคำนวณ M(x')คือ poly(\|x'\|) = poly(poly(\|x\|)) = poly(\|x\|)
		+
		+	จากนิยาม M'(x) เป็นคำตอบของ x ใน A เหลือแต่ต้องตรวจสอบว่า M' ทำงานใน Polynomial time หรือ poly(\|x\|)
		+
		+
		+	----

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:15, 4 ตุลาคม 2553
แถว 13:		แถว 13:
	<<		<<

−	'''Lemma''' : พิจารณาเซต ~~<math>a+b</math>~~	+	'''Lemma''' : พิจารณาเซต [[ไฟล์:NPComplete1.gif‎]] ใดๆ ให้ A เป็น imdenpendent set โดย V-A เป็น Vertec Cover
		+	'''Proof''' : Indenpendent set [[ไฟล์:NPComplete2.gif‎]]Vertex Cover

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 16:53, 4 ตุลาคม 2553
แถว 13:		แถว 13:
	<<		<<

−	'''Lemma''' : พิจารณาเซต <math>~~ใส่สูตรที่นี่~~</math>	+	'''Lemma''' : พิจารณาเซต <math>a+b</math>