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

G521455030: /* NP Complete */

2010-10-08T19:22:46Z

NP Complete

G521455030: /* NP Complete */

2010-10-08T05:15:27Z

NP Complete

G521455030: /* NP Complete */

2010-10-08T05:09:05Z

NP Complete

G521455030: /* NP Complete */

2010-10-08T05:02:18Z

NP Complete

G521455030 เมื่อ 05:01, 8 ตุลาคม 2553

2010-10-08T05:01:54Z

G521455030: /* NP Complete */

2010-10-08T04:46:32Z

NP Complete

G521455030: /* NP Complete */

2010-10-08T04:39:45Z

NP Complete

G521455030 เมื่อ 04:28, 8 ตุลาคม 2553

2010-10-08T04:28:27Z

G521455030 เมื่อ 04:28, 8 ตุลาคม 2553

2010-10-08T04:28:13Z

G521455030: /* NP Complete */

2010-10-08T04:27:40Z

NP Complete

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 19:22, 8 ตุลาคม 2553
แถว 164:		แถว 164:

	[[ไฟล์:44.png]]		[[ไฟล์:44.png]]
−
−
−	~~'''SET_COVER'''~~
−
−	~~ให้ set U = {1,2,....m}~~
−	~~A = {A0,A1,...An} โดยที่ A1 <math>\sube</math> U~~
−	~~และจำนวนเต็ม K มี subset B <math>\sube</math> A~~

@@ แถว 169: / แถว 169: @@
 ให้ set U = {1,2,....m}
-A = {A0,A1,...An} โดยที่ A1  <math>&supe;</math>  U
+A = {A0,A1,...An} โดยที่ A1  <math>\sube</math>  U
-และจำนวนเต็ม K มี subset A
+และจำนวนเต็ม K มี subset B <math>\sube</math> A

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:09, 8 ตุลาคม 2553
แถว 164:		แถว 164:

	[[ไฟล์:44.png]]		[[ไฟล์:44.png]]
		+
		+
		+	'''SET_COVER'''
		+
		+	ให้ set U = {1,2,....m}
		+	A = {A0,A1,...An} โดยที่ A1 <math>&supe;</math> U
		+	และจำนวนเต็ม K มี subset A

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:02, 8 ตุลาคม 2553
แถว 81:		แถว 81:

	\|}		\|}
		+
		+
		+
		+	<br>
		+	'''Ex.''' <br>
		+	<math>(x_1 \or \lnot x_2 \or \ x_3 ) \and (\lnot x_1 \or \lnot \ x_3 \or x_4) \and (\ x_3 \or \ x_2 \or \lnot x_4)</math> <br>
		+	[[ไฟล์:11.png]]
		+
		+	จะกล่าวว่าปัญหา A สามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ (Efficiently certifiable)
		+	ถ้ามี Algorithm V ที่ทำงานใน Polynomial time
		+	* ที่ทุกๆ Yes - instance x ของ A มี Certificate C ที่
		+	\|C\| = poly (\|X\|) และ V (x,c) = 1
		+	* ที่ทุกๆ No - instance x ของ A สำหรับทุกๆ Certificate C ที่
		+	V(x,c) = 0
		+
		+
		+	[[ไฟล์:22.png]]
		+
		+	''' Decision Problems (ปัญหาที่ตอบ yes/no) '''
		+
		+
		+	'''P (Polynomial)'''
		+
		+	ปัญหา A จะอยู่ในกลุ่ม P
		+
		+	ถ้ามี Algorithm ที่ทำงานใน Polynomial time ที่แก้ ปัญหา A
		+
		+
		+	'''NP (Nondeterministic Polynomial)'''
		+	ปัญหา A จะอยู่ในกลุ่ม NP
		+
		+	ถ้า A สามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ
		+
		+
		+	'''ตัวอย่าง SAT อยู่ใน NP'''
		+	Algorithm V ที่รับ CNF <math>\varnothing</math>
		+
		+	และ assignment เป็น certificate จะสามารถตรวจคำตอบของปัญหาได้โดย
		+
		+	ถ้า <math>\varnothing</math> ทำให้เป็นจริงได้ จะมี assignment ที่ทำให้ V ตอบ Yes
		+
		+	แต่ ถ้า <math>\varnothing</math> ไม่สามารถทำให้เป็นจริงได้ ไม่ว่าจะใช้ assignment ได้ V จะตอบ No เสมอ
		+
		+
		+	'''ปัญหา Composite'''
		+	ให้จำนวนเต็ม N , N เป็นจำนวนประกอบหรือไม่
		+
		+	พิสูจน์ว่า Composite เป็น NP
		+
		+	(ต้องมี 2 อย่าง คือ Certificate , Verificate)
		+
		+	*ให้ตัวประกอบ 2 ตัว x,y ของ N เป็น Certificate
		+
		+	*Algorithm V ที่ตรวจคำตอบ คำนวน x,y และ ตรวจว่าเท่ากับ N หรือไม่
		+
		+
		+	'''นิยาม''' ปัญหา A เป็น NP - hard ก็ต่อเมื่อ
		+
		+	สำหรับทุกๆ ปัญหา B ที่เป็น NP
		+
		+	B <math>\leqslant</math> P A
		+
		+
		+	'''นิยาม''' ปัญหา A เป็น NP - Complete ก็ต่อเมื่อ
		+	1 A ต้องเป็น NP
		+	2 A เป็น NP-hard
		+
		+
		+	[[ไฟล์:33.png]]
		+
		+
		+
		+	'''Cook - Lavin'''
		+	SAT เป็น NP-Complete
		+	*ถ้า A <math>\leqslant</math>p B และ B <math>\leqslant</math>p C แล้ว A <math>\leqslant</math>p C ด้วย
		+
		+	*ถ้า A เป็น NP-Complete และ A <math>\leqslant</math>p B ได้ B เป็น NP-Hard
		+
		+	จะพิสูจน์ ปัญหา A เป็น NP-Complete (มี 2 ขั้น)
		+	1 พิสูจน์ว่า A เป็น NP
		+	2 หาปัญหา NP-Complete B , แล้วพิสูจน์ B <math>\leqslant</math>p A
		+
		+	[[ไฟล์:44.png]]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:01, 8 ตุลาคม 2553
แถว 81:		แถว 81:

	\|}		\|}
−
−
−	~~<br>~~
−	~~'''Ex.''' <br>~~
−	~~<math>(x_1 \or \lnot x_2 \or \ x_3 ) \and (\lnot x_1 \or \lnot \ x_3 \or x_4) \and (\ x_3 \or \ x_2 \or \lnot x_4)</math> <br>~~
−	~~[[ไฟล์:11.png]]~~
−
−	~~จะกล่าวว่าปัญหา A สามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ (Efficiently certifiable)~~
−	~~ถ้ามี Algorithm V ที่ทำงานใน Polynomial time~~
−	* ที่ทุกๆ Yes - instance x ของ A มี Certificate C ที่
−	~~\|C\| = poly (\|X\|) และ V (x,c) = 1~~
−	* ที่ทุกๆ No - instance x ของ A สำหรับทุกๆ Certificate C ที่
−	~~V(x,c) = 0~~
−
−
−	~~[[ไฟล์:22.png]]~~
−
−	~~''' Decision Problems (ปัญหาที่ตอบ yes/no) '''~~
−
−
−	~~'''P (Polynomial)'''~~
−
−	~~ปัญหา A จะอยู่ในกลุ่ม P~~
−
−	~~ถ้ามี Algorithm ที่ทำงานใน Polynomial time ที่แก้ ปัญหา A~~
−
−
−	~~'''NP (Nondeterministic Polynomial)'''~~
−	~~ปัญหา A จะอยู่ในกลุ่ม NP~~
−
−	~~ถ้า A สามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ~~
−
−
−	~~'''ตัวอย่าง SAT อยู่ใน NP'''~~
−	~~Algorithm V ที่รับ CNF <math>\varnothing</math>~~
−
−	~~และ assignment เป็น certificate จะสามารถตรวจคำตอบของปัญหาได้โดย~~
−
−	~~ถ้า <math>\varnothing</math> ทำให้เป็นจริงได้ จะมี assignment ที่ทำให้ V ตอบ Yes~~
−
−	แต่ ถ้า <math>\varnothing</math> ไม่สามารถทำให้เป็นจริงได้ ไม่ว่าจะใช้ assignment ได้ V จะตอบ No เสมอ
−
−
−	~~'''ปัญหา Composite'''~~
−	~~ให้จำนวนเต็ม N , N เป็นจำนวนประกอบหรือไม่~~
−
−	~~พิสูจน์ว่า Composite เป็น NP~~
−
−	~~(ต้องมี 2 อย่าง คือ Certificate , Verificate)~~
−
−	*ให้ตัวประกอบ 2 ตัว x,y ของ N เป็น Certificate
−
−	*Algorithm V ที่ตรวจคำตอบ คำนวน x,y และ ตรวจว่าเท่ากับ N หรือไม่
−
−
−	~~'''นิยาม''' ปัญหา A เป็น NP - hard ก็ต่อเมื่อ~~
−
−	~~สำหรับทุกๆ ปัญหา B ที่เป็น NP~~
−
−	~~B <math>\leqslant</math> P A~~
−
−
−	~~'''นิยาม''' ปัญหา A เป็น NP - Complete ก็ต่อเมื่อ~~
−	~~1 A ต้องเป็น NP~~
−	~~2 A เป็น NP-hard~~
−
−
−	~~[[ไฟล์:33.png]]~~
−
−
−
−	~~'''Cook - Lavin'''~~
−	~~SAT เป็น NP-Complete~~
−	*ถ้า A <math>\leqslant</math>p B และ B <math>\leqslant</math>p C แล้ว A <math>\leqslant</math>p C ด้วย
−
−	*ถ้า A เป็น NP-Complete และ A <math>\leqslant</math>p B ได้ B เป็น NP-Hard
−
−	~~จะพิสูจน์ ปัญหา A เป็น NP-Complete (มี 2 ขั้น)~~
−	~~1 พิสูจน์ว่า A เป็น NP~~
−	~~2 หาปัญหา NP-Complete B , แล้วพิสูจน์ B <math>\leqslant</math>p A~~
−
−	~~[[ไฟล์:44.png]]~~

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 04:46, 8 ตุลาคม 2553
แถว 161:		แถว 161:
	1 พิสูจน์ว่า A เป็น NP		1 พิสูจน์ว่า A เป็น NP
	2 หาปัญหา NP-Complete B , แล้วพิสูจน์ B <math>\leqslant</math>p A		2 หาปัญหา NP-Complete B , แล้วพิสูจน์ B <math>\leqslant</math>p A
		+
		+	[[ไฟล์:44.png]]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 04:39, 8 ตุลาคม 2553
แถว 146:		แถว 146:
	1 A ต้องเป็น NP		1 A ต้องเป็น NP
	2 A เป็น NP-hard		2 A เป็น NP-hard
		+
		+
		+	[[ไฟล์:33.png]]

@@ แถว 1: / แถว 1: @@
 จดบันทึกคำบรรยายโดย:
- นายเสกสิทธิ์ สุวรรณ    รหัสนักศึกษา  5214550332 <br>
+นายเสกสิทธิ์ สุวรรณ    รหัสนักศึกษา  5214550332 <br>
- นางสาวสลิตตา นกขุนทอง  รหัสนักศึกษา 5214550308
+นางสาวสลิตตา นกขุนทอง  รหัสนักศึกษา 5214550308
 == '''NP Complete''' ==

@@ แถว 86: / แถว 86: @@
 '''Ex.''' <br>
 <math>(x_1 \or \lnot x_2 \or  \ x_3 ) \and (\lnot x_1 \or \lnot \ x_3  \or  x_4) \and (\ x_3 \or \ x_2 \or \lnot x_4)</math> <br>
 จะกล่าวว่าปัญหา A สามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ (Efficiently certifiable)
 ถ้ามี Algorithm V ที่ทำงานใน Polynomial time
@@ แถว 92: / แถว 94: @@
 * ที่ทุกๆ No - instance x ของ A สำหรับทุกๆ Certificate C ที่
    V(x,c) = 0
 ''' Decision Problems (ปัญหาที่ตอบ yes/no) '''