contestada

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 deceased), whom we'll denote P_1, P_2,..., P_n. They've also collected facts about when these people lived relative to one another. Each fact has one of the following two forms:
For some i and j, person P, died before person Pj was born; or for some i and j, the life spans of P_i and P_j 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 efficient 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.

Respuesta :

Answer:

Algorithm given below

Explanation:

Algorithm:

proc create-node( event )

     out-adj-list[event] <- empty-list

     in-degree[event] <- 0

   endproc

   proc create-edge( start, end )

     push( out-adj-list[ start ], end )

     in-degree[ end ] <- in-degree[ end ] + 1

   endproc

   for p \in { P_i }

     create-node( birth[p] )

     create-node( death[p] )

     create-edge( birth[p], death[p] )

   endfor

   for (p, q) \in DiedBefore

     create-edge( death[p], birth[q] )

   endfor

   for (p, q) \in Coexisted

     create-edge( birth[p], death[q] )

     create-edge( birth[q], death[p] )

   endfor

   eligible-node-list <- empty-list

   for p \in { P_i }

     if in-degree[ birth[p] ] = 0

       push(eligible-node-list, birth[p])

     endif

   endfor

   event-date-separation = 200yrs / (2*|{P_i}|)

   order <- 0

   while eligible-node-list is non-empty

     event = pop(eligible-node-list)

     order <- order + 1

     dates[ event ] = START_DATE + order * event-date-separation

     for following-event \in out-adj-list[event]

       in-degree[ following-event ] <- in-degree[ following-event ] - 1

if in-degree[ following-event ] = 0

                       push( eligible-node-list, following-event )

           endif

     endfor

   endwhile

   if order < 2*|{P_i}|

     return INCONSISTENT_DATA

   else

     return CONSISTENT_DATA, dates

   endif

lhmarianateixeira

In this exercise we have to use the knowledge of computational language in python to write the code.

We have the codes in the attached image.

The code in python can be found as:

proc create-node( event )

    out-adj-list[event]

    in-degree[event]

  endproc

  proc create-edge( start, end )

    push( out-adj-list[ start ], end )

    in-degree[ end ] <- in-degree[ end ] + 1

  endproc

  for p \in { P_i }

    create-node( birth[p] )

    create-node( death[p] )

    create-edge( birth[p], death[p] )

  endfor

  for (p, q) \in DiedBefore

    create-edge( death[p], birth[q] )

  end

for

  for (p, q) \in Coexisted

    create-edge( birth[p], death[q] )

    create-edge( birth[q], death[p] )

  end

for

  eligible-node-list

  for p \in { P_i }

    if in-degree[ birth[p] ] = 0

      push(eligible-node-list, birth[p])

    end

if

  end

for

  event-date-separation = 200yrs / (2*|{P_i}|)

  order <- 0

  while eligible-node-list is non-empty

    event = pop(eligible-node-list)

    order

    dates[ event ] = START_DATE + order * event-date-separation

    for following-event \in out-adj-list[event]

      in-degree[ following-event ]

in-degree[ following-event ] - 1

if in-degree[ following-event ] = 0

                      push( eligible-node-list, following-event )

          endif

    endfor

  endwhile

  if order < 2*|{P_i}|

    return INCONSISTENT_DATA

  else

    return CONSISTENT_DATA, dates

See more about python at brainly.com/question/26104476

Ver imagen lhmarianateixeira

Otras preguntas