ข้อสอบเก่า 204512 บางส่วน - ประวัติรุ่นแก้ไข

Jittat: /* คุณหมอ */

2010-10-06T13:13:32Z

คุณหมอ

Jittat: /* คุณหมอ */

2010-10-06T13:13:17Z

คุณหมอ

Jittat เมื่อ 13:11, 6 ตุลาคม 2553

2010-10-06T13:11:08Z

Jittat เมื่อ 13:08, 6 ตุลาคม 2553

2010-10-06T13:08:35Z

Jittat: หน้าที่ถูกสร้างด้วย '== ปัญหาห้องเก็บของ == มีห้องเก็บของ $k$ ห้อง (เมื่…'

2010-10-06T13:05:57Z

หน้าที่ถูกสร้างด้วย '== ปัญหาห้องเก็บของ == มีห้องเก็บของ <math>k</math> ห้อง (เมื่…'

หน้าใหม่

== ปัญหาห้องเก็บของ ==

มีห้องเก็บของ <math>k</math> ห้อง (เมื่อ <math>k\geq 3</math>) ต้องการนำของ <math>n</math> ชิ้นไปเก็บในห้อง อย่างไรก็ตาม
มีเงื่อนไขว่าของบางชิ้นไม่สามารถเก็บในห้องเดียวกันได้ กล่าวอย่างเป็นทางการก็คือ มีเซต
<math>A</math> ของคู่ลำดับ ที่ถ้าคู่ลำดับ <math>(i,j)\in A</math> ของชิ้นที่ <math>i</math> กับของชิ้นที่ <math>j</math>
จะไม่สามารถเก็บในห้องเดียวกันได้

สำหรับปัญหานี้ เราอยากทราบว่าสามารถเก็บของทุกชิ้นไว้ในห้องโดยไม่ผิดเงื่อนไขได้หรือไม่?

จงแสดงว่าปัญหาดังกล่าวเป็นปัญหา NP-Complete อธิบายด้วยว่าทำไมการลดรูป (reduction) ที่ใช้ถึงถูกต้อง

'''Hint:''' อาจลดรูปปัญหา 3-COLOR ไปยังปัญหาห้องเก็บของ

@@ แถว 26: / แถว 26: @@
 คนไข้คนหนึ่งหลังจากที่วิเคราะห์แล้วพบว่ามีเชื้อโรคทั้งสิ้น <math>N</math> ชนิด เชื้อโรคที่ <math>i</math> สำหรับ
-  <math>1\leq i\leq N</math> สามารถจัดการได้โดยใช้ยาใด ๆ ในเซต <math>A_i\subseteq
+<math>1\leq i\leq N</math> สามารถจัดการได้โดยใช้ยาใด ๆ ในเซต <math>A_i\subseteq
-  {\mathcal M}</math> ก็ได้ (นั่นคือในการให้ยาถ้าหมอสั่งยาในเซต <math>A_i</math> เชื้อโรคที่ <math>i</math>
+{\mathcal M}</math> ก็ได้ (นั่นคือในการให้ยาถ้าหมอสั่งยาในเซต <math>A_i</math> เชื้อโรคที่ <math>i</math>
-  ก็จะตาย)
+ก็จะตาย)
 คุณหมอต้องการทราบว่า สามารถใช้ยาปฏิชีวนะเพียง <math>k</math> ชนิด
-  เพื่อฆ่าเชื้อโรคทั้งหมดในร่างกายคนไข้ได้หรือไม่
+เพื่อฆ่าเชื้อโรคทั้งหมดในร่างกายคนไข้ได้หรือไม่
 * เรียกปัญหาดังกล่าวว่าปัญหา MinMed จงแสดงว่าปัญหา MinMed เป็นปัญหาในกลุ่ม NP

@@ แถว 23: / แถว 23: @@
 == คุณหมอ ==
-คุณหมอมียาปฏิชีวนะ $M$ แบบ ให้เซต ${\mathcal  M}=\{1,2,\ldots,M\}$ แทนเซตของยาเหล่านี้
+คุณหมอมียาปฏิชีวนะ <math>M</math> แบบ ให้เซต <math>{\mathcal M}=\{1,2,\ldots,M\}</math> แทนเซตของยาเหล่านี้
-  คนไข้คนหนึ่งหลังจากที่วิเคราะห์แล้วพบว่ามีเชื้อโรคทั้งสิ้น $N$ ชนิด เชื้อโรคที่ $i$ สำหรับ
+คนไข้คนหนึ่งหลังจากที่วิเคราะห์แล้วพบว่ามีเชื้อโรคทั้งสิ้น <math>N</math> ชนิด เชื้อโรคที่ <math>i</math> สำหรับ
-   $1\leq i\leq N$ สามารถจัดการได้โดยใช้ยาใด ๆ ในเซต $A_i\subseteq
+   <math>1\leq i\leq N</math> สามารถจัดการได้โดยใช้ยาใด ๆ ในเซต <math>A_i\subseteq
-   {\mathcal M}$ ก็ได้ (นั่นคือในการให้ยาถ้าหมอสั่งยาในเซต $A_i$ เชื้อโรคที่ $i$
+   {\mathcal M}</math> ก็ได้ (นั่นคือในการให้ยาถ้าหมอสั่งยาในเซต <math>A_i</math> เชื้อโรคที่ <math>i</math>
    ก็จะตาย)
-  คุณหมอต้องการทราบว่า สามารถใช้ยาปฏิชีวนะเพียง $k$ ชนิด
+คุณหมอต้องการทราบว่า สามารถใช้ยาปฏิชีวนะเพียง <math>k</math> ชนิด
    เพื่อฆ่าเชื้อโรคทั้งหมดในร่างกายคนไข้ได้หรือไม่
-* เรียกปัญหาดังกล่าวว่าปัญหา {\sc MinMed} จงแสดงว่าปัญหา {\sc MinMed} เป็นปัญหาในกลุ่ม NP
+* เรียกปัญหาดังกล่าวว่าปัญหา MinMed จงแสดงว่าปัญหา MinMed เป็นปัญหาในกลุ่ม NP
-* จงแสดงว่าปัญหา {\sc MinMed} เป็นปัญหา NP-complete โดยการลดรูปจากบางปัญหา NP-complete ไปยัง {\sc MinMed}
+* จงแสดงว่าปัญหา MinMed เป็นปัญหา NP-complete โดยการลดรูปจากบางปัญหา NP-complete ไปยัง MinMed
-'''คำใบ้:''' พิจารณาปัญหา {\sc VertexCover} ที่อธิบายได้ดังนี้ ให้กราฟ
+'''คำใบ้:''' พิจารณาปัญหา VertexCover ที่อธิบายได้ดังนี้ ให้กราฟ <math>G=(V,E)</math> และจำนวนเต็ม <math>k</math> หาว่ามีเซต <math>C\subseteq V</math> ที่ <math>|C|=k</math> และทุก ๆ เส้นเชื่อม <math>e\in E</math> มีจุดปลายอย่างน้อยหนึ่งจุดอยู่ใน <math>C</math> หรือไม่

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

	เราจะเรียกปัญหานี้ว่า “ปัญหาตัวแทนสตริง” จงแสดงว่าปัญหานี้เป็นปัญหา NP-Complete		เราจะเรียกปัญหานี้ว่า “ปัญหาตัวแทนสตริง” จงแสดงว่าปัญหานี้เป็นปัญหา NP-Complete
		+
		+
		+	== คุณหมอ ==
		+
		+	คุณหมอมียาปฏิชีวนะ $M$ แบบ ให้เซต ${\mathcal M}=\{1,2,\ldots,M\}$ แทนเซตของยาเหล่านี้
		+
		+	คนไข้คนหนึ่งหลังจากที่วิเคราะห์แล้วพบว่ามีเชื้อโรคทั้งสิ้น $N$ ชนิด เชื้อโรคที่ $i$ สำหรับ
		+	$1\leq i\leq N$ สามารถจัดการได้โดยใช้ยาใด ๆ ในเซต $A_i\subseteq
		+	{\mathcal M}$ ก็ได้ (นั่นคือในการให้ยาถ้าหมอสั่งยาในเซต $A_i$ เชื้อโรคที่ $i$
		+	ก็จะตาย)
		+
		+	คุณหมอต้องการทราบว่า สามารถใช้ยาปฏิชีวนะเพียง $k$ ชนิด
		+	เพื่อฆ่าเชื้อโรคทั้งหมดในร่างกายคนไข้ได้หรือไม่
		+
		+	* เรียกปัญหาดังกล่าวว่าปัญหา {\sc MinMed} จงแสดงว่าปัญหา {\sc MinMed} เป็นปัญหาในกลุ่ม NP
		+
		+	* จงแสดงว่าปัญหา {\sc MinMed} เป็นปัญหา NP-complete โดยการลดรูปจากบางปัญหา NP-complete ไปยัง {\sc MinMed}
		+
		+	'''คำใบ้:''' พิจารณาปัญหา {\sc VertexCover} ที่อธิบายได้ดังนี้ ให้กราฟ
		+	$G=(V,E)$ และจำนวนเต็ม $k$ หาว่ามีเซต $C\subseteq V$ ที่ $\|C\|=k$ และทุก
		+	ๆ เส้นเชื่อม $e\in E$ มีจุดปลายอย่างน้อยหนึ่งจุดอยู่ใน $C$

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:08, 6 ตุลาคม 2553
แถว 11:		แถว 11:

	'''Hint:''' อาจลดรูปปัญหา 3-COLOR ไปยังปัญหาห้องเก็บของ		'''Hint:''' อาจลดรูปปัญหา 3-COLOR ไปยังปัญหาห้องเก็บของ
		+
		+
		+	== รหัสพันธุกรรม ==
		+	ในการศึกษาเกี่ยวกับรหัสพันธุกรรมนั้น เรามักจะพิจารณาสายรหัสพันธุกรรมเป็นสตริงของตัวอักษร {A,G,T,C} โดยในปัญหานี้เราจะสนใจสตริงความยาว m เท่านั้น ในการวิเคราะห์กลุ่มของสิ่งมีชีวิต เรามักจะได้สตริงเหล่านี้มาเป็นจำนวนมาก อย่างไรก็ตามเนื่องจากค่าใช้จ่ายและเวลาในการวิเคราะห์รหัสพันธุกรรมสายหนึ่งนั้น ค่อนข้างสูง เราจึงต้องการจะลดจำนวนสตริงที่จะวิเคราะห์โดยละเอียดลง โดยสตริงที่คล้าย ๆ กัน เราจะเลือกตัวแทนมาแค่สตริงเดียว ในการวัดว่าสตริงคู่ใดคล้ายกันหรือไม่ เราจะพิจารณาจากจำนวนตำแหน่งที่มีตัวออักษรเหมือนกันในสองสตริงนั้น ยกตัวอย่างเช่นสตริง AGAAG กับสตริง ATATG มี 3 ตำแหน่งที่เหมือนกัน ถ้าจำนวนของตำแหน่งนี้มากกว่าหรือเท่ากับ k เราจะนับว่าสตริงคู่นั้น “คล้ายกันระดับ k ”
		+
		+	ปัญหาที่เราต้องการแก้คือ: ให้เซต S ของสตริง n สตริง ที่มีความยาว m และค่าคงที่ k และ l , มีเซตของสตริง ที่มีจำนวน l สตริง และทุก ๆ สตริง s ใน S มีสตริง x ใน T ที่คล้ายกันระดับ k กับ s หรือไม่?
		+
		+	เราจะเรียกปัญหานี้ว่า “ปัญหาตัวแทนสตริง” จงแสดงว่าปัญหานี้เป็นปัญหา NP-Complete

ข้อสอบเก่า 204512 บางส่วน - ประวัติรุ่นแก้ไข

Jittat: /* คุณหมอ */

Jittat: /* คุณหมอ */

Jittat เมื่อ 13:11, 6 ตุลาคม 2553

Jittat เมื่อ 13:08, 6 ตุลาคม 2553

Jittat: หน้าที่ถูกสร้างด้วย '== ปัญหาห้องเก็บของ == มีห้องเก็บของ k ห้อง (เมื่…'

Jittat: หน้าที่ถูกสร้างด้วย '== ปัญหาห้องเก็บของ == มีห้องเก็บของ $k$ ห้อง (เมื่…'