FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

FGI Nachrichtenkomplexität

FGI Nachrichtenkomplexität 2007-02-07 20:50
enco
Moin, ich arbeite gerade FGI nach und verstehe eine Sache nicht:

es geht um den Algorithmus 8.1 auf der Seite 301. Auf der Seite 304 unten wird zu diesem Algorithmus seine Nachrichtenlaufzeit hergeleitet und ein Beispiel durchgerechnet. Dem Beispiel nach werden nur die Nachrichten der Form <M> als Nachrichten gezählt.

Meine Frage ist: weiß jemand warum alle anderen Nachrichten wie z.B. <reject> oder <parent> nicht in der Nachrichtenkomplexität berücksichtigt werden?


Re: FGI Nachrichtenkomplexität 2007-02-08 00:51
ethrandil
Wenn es so ist wie du sagst, dann nehme ich an dass er diese Nachrichten hier weglässt. Das geht in diesem Fall, da ja höchstens pro <M>-Nachricht eine oder zwei weitere Nachrichten (parent/reject) dazukommen.
An der Laufzeit in O-Notation ändert das herzlich wenig.

Prinzipiell müsste man aber alle Nachrichten betrachten, so weit ich weiß. Macht ja keinen Sinn sonst.

mfg
- eth

Re: FGI Nachrichtenkomplexität 2007-02-08 09:35
enco
@ethrandil Danke für die Antwort

In diesem Beispiel ist das wirklich so, dass sich die Nachrichtenkomplexität in O - Notation durch Weglassen dieser Nachrichten nicht verändert.

Auf Seite 304 wird jedoch ein Beispiel durchgerechnet, bei dem ein konkreter Fall betrachtet und eine genaue Anzahl der Nachrichten berechnet wird. Und da werden, wie ich oben bereits beschrieben habe, nur <M> - Nachrichten aber keine <reject> oder <parent> zu den Nachrichten gezählt.

Man kann sich aber leicht Algorithmen vorstellen, deren Nachrichtenkomplexität sich in O - Notation durch Weglassen der genanten Nachrichten verändert.

Naja, habe jetzt ne Mail an meinen Übungsgruppenleiter geschickt. Mal sehen, was er sagt.