You’re helping a group of ethnograp

You’re helping a group of ethnographers analyze some oral history data they’ve collected
by interviewing members of a village to learn about the lives of people who’ve
lived there over the past two hundred years.
From these interviews, they’ve learned about a set of n people (all of them now decreased),
whom we’ll denote P1; P2; : : : ; Pn. They’ve also collected facts about when
these people lived relative to one another. Each fact has one of the following two froms:
• For some i and j, person Pi died before person Pj was born; or
• for some i and j, the life spans of Pi and Pj overlapped at least partially.
Naturally, they’re not sure that all these facts are correct; memories are not so good,
and a lot of this was passed down by word of mouth. So what they’d like you to
determine is whether the data they’ve collected is at least internally consistent, in the
sense that there could have existed a set of people for which all the facts they’ve learned
simultaneously hold.

Give an effective algorithm to do this: either it should produce proposed dates of
birth and death for each of the n people so that all the facts hold true, or it should
report (correctly) that no such dates can exist – that is, the facts collected by the
ethnographers are not internally consistent.

ผลลัพธ์ (ไทย) 1:

คุณกำลังช่วยกลุ่มของ ethnographers วิเคราะห์ข้อมูลปากบางได้เก็บรวบรวมโดยการสัมภาษณ์ข้อมูลส่วนตัวสมาชิกของหมู่บ้านเพื่อเรียนรู้เกี่ยวกับชีวิตของคนได้อาศัยมีกว่าสองร้อยปีจากการสัมภาษณ์เหล่านี้ พวกเขาได้เรียนรู้เกี่ยวกับชุด n คน (ทั้งหมดตอนนี้ ลดลง),ซึ่งเราจะแสดง P1 P 2 : : : ; พีเอ็น นอกจากนี้พวกเขายังได้รวบรวมข้อเท็จจริงเกี่ยวกับเวลาคนเหล่านี้อาศัยสัมพันธ์กัน ข้อเท็จจริงแต่ละมี froms สองต่อไปนี้อย่างใดอย่างหนึ่ง:• I และ j คนพี่เสียชีวิตก่อนเกิดบุคคลพีเจ หรือ• i และ j ครอบคลุมชีวิตของพี่และพีเจซ้อนกันในบางส่วนธรรมชาติ พวกเขาไม่แน่ใจว่า ข้อเท็จจริงทั้งหมดถูกต้อง ความทรงจำไม่ดีและล็อตนี้ถูกส่งผ่านลงปาก ดังนั้น จะต้องให้กำหนดคือว่าข้อมูลที่ได้เก็บรวบรวมอย่างน้อยภายในสอดคล้องกัน ในการความรู้สึกที่มีไม่มีอยู่ชุดของผู้ใดทั้งหมดสืบพวกเขาได้เรียนรู้ค้างไว้พร้อมกันอัลกอริทึมมีประสิทธิภาพทำให้: อย่างใดอย่างหนึ่งจึงควรผลิตวันเสนอเกิดและตายของแต่ละคนเพื่อให้ข้อเท็จจริงทั้งหมดถือเป็นจริง หรือควรรายงาน (ถูกต้อง) ว่า วันดังกล่าวไม่สามารถมีอยู่นั่นคือ ข้อเท็จจริงที่รวบรวมโดยการethnographers จะไม่สอดคล้องกันภายใน

ผลลัพธ์ (ไทย) 2:

คุณกำลังช่วยกลุ่มของ ethnographers วิเคราะห์บางข้อมูลประวัติบุคคลที่พวกเขาได้เก็บรวบรวม
โดยการสัมภาษณ์สมาชิกของหมู่บ้านที่จะเรียนรู้เกี่ยวกับชีวิตของผู้คนที่เคย
อาศัยอยู่ที่นั่นที่ผ่านมาสองร้อยปี.
จากการสัมภาษณ์เหล่านี้พวกเขาได้เรียนรู้ เกี่ยวกับชุดของ n คน (ทั้งหมดของพวกเขาในขณะนี้ลดลง)
ผู้ที่เราจะได้แสดง P1; P2; :::; Pn พวกเขายังได้รวบรวมข้อเท็จจริงเกี่ยวกับเมื่อ
คนเหล่านี้อาศัยอยู่เมื่อเทียบกับอีกคนหนึ่ง ความเป็นจริงแต่ละคนมีหนึ่งต่อไปนี้สอง froms:
•สำหรับบาง i และ j คนพี่เสียชีวิตก่อนคน Pj เกิด; หรือ
•สำหรับบาง i และ j, ช่วงชีวิตของพี่และ Pj ซ้อนทับอย่างน้อยบางส่วน.
ธรรมชาติที่พวกเขาไม่แน่ใจว่าข้อเท็จจริงทั้งหมดเหล่านี้ถูกต้อง; ความทรงจำที่ไม่ดีเช่นนั้น
และจำนวนมากนี้ถูกส่งผ่านลงมาจากคำพูดจากปาก ดังนั้นสิ่งที่พวกเขาอยากให้คุณ
ตรวจสอบไม่ว่าจะเป็นข้อมูลที่พวกเขาได้เก็บรวบรวมอย่างน้อยภายในที่สอดคล้องกันใน
แง่ที่ว่าอาจมีอยู่ชุดของคนที่ข้อเท็จจริงทั้งหมดที่พวกเขาได้เรียนรู้
ไปพร้อม ๆ กันถือ. ให้มีประสิทธิภาพ ขั้นตอนวิธีการทำเช่นนี้ทั้งที่มันควรจะผลิตเสนอวันเกิดและการตายของแต่ละคน n เพื่อให้ข้อเท็จจริงทั้งหมดถือเป็นจริงหรือมันควรรายงาน (ถูกต้อง) ว่าไม่มีวันดังกล่าวสามารถอยู่ได้ - นั่นคือข้อเท็จจริงที่เก็บรวบรวมโดยethnographers ไม่สอดคล้องภายใน

ผลลัพธ์ (ไทย) 3:

คุณช่วยกลุ่ม ethnographers วิเคราะห์ประวัติบุคคลพวกเขาได้เก็บรวบรวมข้อมูลโดยการสัมภาษณ์สมาชิก
ของหมู่บ้านเพื่อเรียนรู้เกี่ยวกับชีวิตของผู้คนที่เคย
อยู่ที่ผ่านมาสองร้อยปี .
จากการสัมภาษณ์นี้ พวกเขาได้เรียนรู้เกี่ยวกับชุดของคน ( ทุกคนตอนนี้ลดลง )
ที่เราจะแสดงถึง P1 ; P2 ; : : : ; อื่นๆ พวกเขายังรวบรวมข้อเท็จจริงเกี่ยวกับเมื่อ
คนเหล่านี้อาศัยอยู่ญาติอีกคนหนึ่ง ในความเป็นจริงมีหนึ่งต่อไปนี้สองไปจาก :
- สำหรับผมและ J , คนปี่เสียชีวิตก่อนท่าน PJ เกิด ;
- สำหรับฉัน และ เจ ชีวิตช่วง พี และ พีเจจำนวนอย่างน้อยบางส่วน
ธรรมชาติ พวกเขาไม่แน่ใจว่าข้อเท็จจริงทั้งหมดเหล่านี้จะถูกต้องและความทรงจำ ไม่ได้ดังนั้นดี
และมากถูกส่งผ่านด้วยคำพูดจากปากดังนั้นสิ่งที่พวกเขาต้องการให้คุณ
พิจารณาคือ ว่าข้อมูลที่พวกเขารวบรวมได้เป็นอย่างน้อยภายในที่สอดคล้องกันใน
รู้สึกว่าอาจมีอยู่ชุดของผู้คน ซึ่งข้อเท็จจริงทั้งหมดที่พวกเขาได้เรียนรู้
พร้อมกันค้างไว้

ให้อัลกอริทึมที่มีประสิทธิภาพที่จะทำอย่างใดอย่างหนึ่งควรเสนอวันที่ผลิต
เกิดและการตายของแต่ละคนเพื่อให้ข้อเท็จจริงทั้งหมด N ไว้จริงหรือมันควรรายงาน ( ถูกต้อง ) ที่ไม่มีวันดังกล่าวสามารถอยู่และนั่นคือ ข้อเท็จจริงที่รวบรวมโดย
ethnographers ไม่สอดคล้องภายใน