|
4.แรงบันดาลใจจากตัวอย่างของศิษย์เก่า จากมหาวิทยาลัยคอร์เนล วลาดิมีร์ นาโบคอฟ
การที่เพื่อนของคุณกลายมาเป็นนักวิจัยผีเสื้อมือสมัครเล่นนั้น เมื่อถึงเวลาที่พวกเขากลับมาพร้อมตัวอย่างของผีเสื้อแต่ละสายพันธุ์ ทำให้ยากมากที่จะแยกว่าแต่ละะสายพันธุ์นั้นแตกต่างกันอย่างไร แต่จะว่าไปแล้วสายพันธุ์ต่างอื่นๆ ก็คงไม่ต่างไปจากสายพันธุ์อื่นมากนัก
วันหนึ่งพวกเขากลับมาพร้อมกับผีเสื้อ และพวกเขาเชื่อว่าแต่ละอันัั้นประกอบด้วยสองชนิดที่แตกต่างกันซึ่งเราจะเรียก A และ B ในการอธิบายต่อไปนี้
พวกเขาต้องการที่จะแบ่งตัวอย่างออกเป็นสองกลุ่มในแต่ละกลุ่มนั้นแยกเป็นส่วนๆว่า
ส่วนไหนอยู่ในกลุ่ม A และกลุ่มไหนอยู่ในกลุ่ม B
มันยากสำหรับพวกเขาในการแยกชื่อตัวอย่างลงไปในหนึ่งๆ สายพันธุ์ ฉะนั้นพวกเราตัดสินใจที่จะนำวิธีนี้ต่อไป
สำหรับคู่ของแต่ละตัวอย่าง พวกเขาศึกษาอย่างระมัดระวังในทุกๆ ด้าน หากพวกเขามีความมั่นใจมากพอที่จะด่วนสรุปตัดสินใจว่า
ช่วยแปลต่อให่ทีว่าถูกไหม
4.inspired by the example of that great Cornellian, Vladimir Nabokov, some
of your frien.ds have become amateur lepidopterists (they study butterflies).
Often when they return from a trip with specimens of butterf~es,
it is very difficult for them to tell how many distinct species theyve
caught--thanks to the fact that many species look very similar to one
another.
One day they return with n butterflies, and they believe that each
belongs to one of two different species, which well call A and B for
purposes of this discussion. Theyd like to divide the n specimens into
two groups--those that belong to . A and those that belong to B--but its
very hard for them to directly label any one specimen. So they decide to
adopt the following approach.
For each pair of specimens i and j, they study them carefully side by
side. If theyre confident enough in their judgment, <- แปลถึงนี่
_____________________________________________________________________________
then they 1abe! the
pair (i,j) either"same" (meaning they believe them both to come from
the same species) or "different" (meaning they believe them to come from
different species). They also have the option of rendering no judgment
on a given pair, in which case well call the pair ambiguous.
So now they have the collection of n specimens, as well as a collection
of m judgments (either "same" or "different") for the pairs that were not
declared to be ambiguous. Theyd like to know if this data is consistent
with the idea that each butterfly is from one of species A or B. So more
concretely, well declare the m judgments to be consistent if it is possible
to label each specimen either A or B in such a way that for each pair (i,j)
labeled "same," it is the case that i andj have the same label; and for each
pair (i,j) labeled "different," it is the case that i andj have different labels.
Theyre in the middle of tediously working out whether their judgments
are consistent, when one of them realizes that you probably have an
algorithm that would answer this question right away.
Give an algorithm with running time O(m + n) that determines
whether the m judgments are consistent.
3. The algorithm described in Section 3.6 for computing a topological ordering
of a DAG repeatedly finds a node with no incoming edges and deletes
it. This will eventually produce a topological ordering, provided that the
? input graph really is a DAG.
But suppose that were given an arbitrary graph that may or may not
be a DAG. Extend the topological ordering algorithm so that, given an
input directed graph G, it outputs one of two things: (a) a topological
ordering, thus establishing that a is a DAG; or (b) a cycle in G, thus
establishing that a is not a DAG. The nmning time of your algorithm
should be O(m + n) for a directed graph with n nodes and m edges.
ไม่รู้ไปเอามาจากไหนพิมพ์ถูกมั้งผิดมั้งไม่แน่ใจ
| จากคุณ |
:
รูลบี้
|
| เขียนเมื่อ |
:
7 ธ.ค. 55 13:58:36
A:1.2.165.145 X: TicketID:307546
|
|
|
|
มือใหม่หัดแปล
