ผลต่างระหว่างรุ่นของ "ข้อสอบเก่า 204512 บางส่วน"
Jittat (คุย | มีส่วนร่วม) (→คุณหมอ) |
Jittat (คุย | มีส่วนร่วม) (→คุณหมอ) |
||
แถว 26: | แถว 26: | ||
คนไข้คนหนึ่งหลังจากที่วิเคราะห์แล้วพบว่ามีเชื้อโรคทั้งสิ้น <math>N</math> ชนิด เชื้อโรคที่ <math>i</math> สำหรับ | คนไข้คนหนึ่งหลังจากที่วิเคราะห์แล้วพบว่ามีเชื้อโรคทั้งสิ้น <math>N</math> ชนิด เชื้อโรคที่ <math>i</math> สำหรับ | ||
− | + | <math>1\leq i\leq N</math> สามารถจัดการได้โดยใช้ยาใด ๆ ในเซต <math>A_i\subseteq | |
− | + | {\mathcal M}</math> ก็ได้ (นั่นคือในการให้ยาถ้าหมอสั่งยาในเซต <math>A_i</math> เชื้อโรคที่ <math>i</math> | |
− | + | ก็จะตาย) | |
คุณหมอต้องการทราบว่า สามารถใช้ยาปฏิชีวนะเพียง <math>k</math> ชนิด | คุณหมอต้องการทราบว่า สามารถใช้ยาปฏิชีวนะเพียง <math>k</math> ชนิด | ||
− | + | เพื่อฆ่าเชื้อโรคทั้งหมดในร่างกายคนไข้ได้หรือไม่ | |
* เรียกปัญหาดังกล่าวว่าปัญหา MinMed จงแสดงว่าปัญหา MinMed เป็นปัญหาในกลุ่ม NP | * เรียกปัญหาดังกล่าวว่าปัญหา MinMed จงแสดงว่าปัญหา MinMed เป็นปัญหาในกลุ่ม NP |
รุ่นแก้ไขปัจจุบันเมื่อ 13:13, 6 ตุลาคม 2553
ปัญหาห้องเก็บของ
มีห้องเก็บของ ห้อง (เมื่อ ) ต้องการนำของ ชิ้นไปเก็บในห้อง อย่างไรก็ตาม มีเงื่อนไขว่าของบางชิ้นไม่สามารถเก็บในห้องเดียวกันได้ กล่าวอย่างเป็นทางการก็คือ มีเซต ของคู่ลำดับ ที่ถ้าคู่ลำดับ ของชิ้นที่ กับของชิ้นที่ จะไม่สามารถเก็บในห้องเดียวกันได้
สำหรับปัญหานี้ เราอยากทราบว่าสามารถเก็บของทุกชิ้นไว้ในห้องโดยไม่ผิดเงื่อนไขได้หรือไม่?
จงแสดงว่าปัญหาดังกล่าวเป็นปัญหา NP-Complete อธิบายด้วยว่าทำไมการลดรูป (reduction) ที่ใช้ถึงถูกต้อง
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
คุณหมอ
คุณหมอมียาปฏิชีวนะ แบบ ให้เซต แทนเซตของยาเหล่านี้
คนไข้คนหนึ่งหลังจากที่วิเคราะห์แล้วพบว่ามีเชื้อโรคทั้งสิ้น ชนิด เชื้อโรคที่ สำหรับ สามารถจัดการได้โดยใช้ยาใด ๆ ในเซต ก็ได้ (นั่นคือในการให้ยาถ้าหมอสั่งยาในเซต เชื้อโรคที่ ก็จะตาย)
คุณหมอต้องการทราบว่า สามารถใช้ยาปฏิชีวนะเพียง ชนิด เพื่อฆ่าเชื้อโรคทั้งหมดในร่างกายคนไข้ได้หรือไม่
- เรียกปัญหาดังกล่าวว่าปัญหา MinMed จงแสดงว่าปัญหา MinMed เป็นปัญหาในกลุ่ม NP
- จงแสดงว่าปัญหา MinMed เป็นปัญหา NP-complete โดยการลดรูปจากบางปัญหา NP-complete ไปยัง MinMed
คำใบ้: พิจารณาปัญหา VertexCover ที่อธิบายได้ดังนี้ ให้กราฟ และจำนวนเต็ม หาว่ามีเซต ที่ และทุก ๆ เส้นเชื่อม มีจุดปลายอย่างน้อยหนึ่งจุดอยู่ใน หรือไม่