www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Technische Informatik" - EREW-Pram Algorithmus
EREW-Pram Algorithmus < Technische Inform. < Praktische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Technische Informatik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

EREW-Pram Algorithmus: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 16:22 Di 04.05.2004
Autor: Gloomer

Hi zusammen.....
nachdem es in Mathe ja mittlerweile bei mir gut läuft ( Gott und lernen sei Dank :D) hab ich nun mal ein etwas anderes Problem.
Und zwar muss ich einen Algorithmus für eine EREW-Pram Maschine schreiben, die das Boolesche ODER berechnet für n Ausdrücke mit Hilfe von nur n/2 Prozessoren.....
ich hab bis jetzt echt nur das UND hinbekommen und hab mal wieder nen Brett vorm Kopp....   ich häng den Algorithmus für das UND mal hier rein, damit ihr ne Starthilfe habt :D

Algorithmus UND <EREW-PRAM>
{ berechnet das boolesche UND in O(n/N + log N) Schritten}
global: A: array[0..n-1] of boolean
U: boolean;
n: integer;
local: N, p: integer {initialisiert}
count,i: Integer;
u: boolean;
n_lokal: integer
begin
{O(log N):}
n_lokal:=get(n) with Algorithmus ReadX {


           Algorithmus ReadX <EREW-PRAM>
          { liest X nach x in O(log N)}
      
         global: A: array[0..n-1] of integer; {A[0] = X}

          local: N, p: integer; {initialisiert}
               x,count: integer;
          begin
if (p<1) then {     p0}
x:= A[0]; {read A0}
if (1<=p<2) then {     p1}
x:= A[p-0]; {read A0}
else if (p<1) then {p0}
A[1]:= x; {A1 write}
if (2<=p<4) then {     p2,p3}
x:= A[p-1]; {read A0,A1}
else if (p<2) then {p0,p1}
A[p+2]:= x; {A2,A3 write}
{WrittenCount= 4 {A0..A3}}
{=ReadCount=4 {p0..p3}}
{=:count}
for (count:=16; count*2 < N; count:=count*2) do
if (count <= p < count*2) then {p[count]..p[count*2-1]}
x:= A[p-count]; {read  A[0]..A[count-1]}
else if (p<count) then {p[0]..p[count-1]}
A[p+count]:= x; {A[count]..[count*2-1]}
if (count <= p < N) then {p[count]..p[count*2-1]}
x:= A[p-count]; {read  A[0]..A[count-1]}
           end.};

{O(n/N):}
u:=A[p];
for i:=0 to n_lokal/N do
u:= u AND A[p*n_lokal div N+i];
A[p]:=u; {A[0]..A[N-1] enthalten die Verknüpfungen}
{O(log N):}
for count:=0 to log N do
{if [mm] p A[p]:=A[p*2] AND A[p*2+1];
if p=0 then
U:=A[0]
end.



        
Bezug
EREW-Pram Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 01:51 Mi 05.05.2004
Autor: Paulus

Hallo gloomer

ich verstehe zwar dein Programm nicht so ganz (die Bedeutung von p kenne ich nicht so genau, auch verstehe ich nicht, warum bei der for-Schleife mit 16 begonnen wird, und hier:

if (1<=p<2) then {     p1}
x:= A[p-0]; {read A0}

sollte es meiner Meinung nach auch eher so heissen:

if (1<=p<2) then {     p1}
x:= A[p-0]; {read A1}

(oder ist das gemeint?:

if (1<=p<2) then {     p1}
x:= A[p-1]; {read A0}

Auch verstehe ich nicht, wann eine geschweifte Klammer als Kommentar gilt, und wann nicht.

Aber wie dem auch sei, falls dein Algorithmus wirklich getestet ist und das korrekte Resultat liefert, so glaube ich, dass für das ODER lediglich die neuntletzte Zeile

u:= u AND A[p*n_lokal div N+i];

durch

u:= u OR A[p*n_lokal div N+i];

ersetzt werden muss.

ich hoffe, ich irre mich nicht. Ich setze den Status der Frage jedenfalls auf "teilweise beantwortet, damit auch noch Andere auf die Frage aufmerksam werden.



Bezug
                
Bezug
EREW-Pram Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:01 Mi 05.05.2004
Autor: Gloomer

hi und danke erstmal paulus für deine antwort.... werde deinen tip mal einbauen und sehn ob es klappt....

zu den andern sachen:
die for scheleife beginnt bei 16 weil.... weiss auch net :) war irgendwie aus der aufabenstellung zu entnehmen, musst ich auch erst drauf kommen....

das mit den geschweiften klammern scheint ein copy/paste fehler zu sein... normalerweise sind die für kommentare gedacht...

und dann natürlich die sache mit dem A0 lesen :)  da hab ich mich tatsächlich vertippt und p-1 ist natürlich korrekt ;)

ich melde mich nochmal wenn es geklappt hat alles zu verbauen
cya

Bezug
                
Bezug
EREW-Pram Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:43 Mi 05.05.2004
Autor: Marc

Hallo gloomer!

> Hallo gloomer
>  
> ich verstehe zwar dein Programm nicht so ganz (die
> Bedeutung von p kenne ich nicht so genau, auch verstehe ich
> nicht, warum bei der for-Schleife mit 16 begonnen wird, und
> hier:

Ja, ich kann mir auch nicht vorstellen, dass das Programm korrekt ist und out-of-the-box funktioniert (das soll wahrscheinlich ein theoretisches Programm sein, oder?)

> Aber wie dem auch sei, falls dein Algorithmus wirklich
> getestet ist und das korrekte Resultat liefert, so glaube
> ich, dass für das ODER lediglich die neuntletzte Zeile
>  
> u:= u AND A[p*n_lokal div N+i];
>
> durch
>
> u:= u OR A[p*n_lokal div N+i];
>
> ersetzt werden muss.

Und --denke ich-- AND durch OR in der viertletzten Zeile ersetzen.
An dieser Stelle sollen ja wahrscheinlich die Teilergebnisse der n/2-Prozessoren zusammengesetzt werden (obwohl ich die Schleife auch nicht verstehe; da würde ich erwarten, dass der Schleifenrumpf irgendwie von "count" abhängt, so wird doch log(N) Mal dasselbe ausgeführt.

Noch zwei Anmerkungen:

a OR b = NOT (NOT(a) AND NOT(b))
So könnte man dein bestehendes Programm für AND bequem auch für OR benutzen.

Desweiteren kann auf die weitere Berechnung des Endergebnisses verzichtet werden, wenn es bereits feststeht:
True OR b = True
Das bedeutet: Wenn dein Zwischenergebnis bereits True ist, kann die Beachtung weiterer Operanden nicht mehr daran ändern.
Ähnliches gilt auch für AND:
False AND b = False

Viele Grüße,
Marc

Bezug
                        
Bezug
EREW-Pram Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:59 Mi 05.05.2004
Autor: Paulus


> Hallo gloomer!
>  
>  
> Und --denke ich-- AND durch OR in der viertletzten Zeile
> ersetzen.
>  An dieser Stelle sollen ja wahrscheinlich die
> Teilergebnisse der n/2-Prozessoren zusammengesetzt werden
> (obwohl ich die Schleife auch nicht verstehe; da würde ich
> erwarten, dass der Schleifenrumpf irgendwie von "count"
> abhängt, so wird doch log(N) Mal dasselbe ausgeführt.
>  

Autsch! ;-) Das habe ich mir auch überlegt, aber in der späten Nacht wieder verschlafen. (gibt es kein Smily, das schläft?)

Danke, Marc, für die Korrektur!  :-)



Bezug
                                
Bezug
EREW-Pram Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:03 Mi 05.05.2004
Autor: Gloomer

jo, also.....
habe mal meinen tutor gefragt wegen der schleife.... der wusste auch net warum das auch so funktioniert ( hab ich halt mal glück gehabt ), er meinte aber da wäre egal, da es darauf nicht in der aufgabe ankam....
die von marc erwähnte zeile hatte ich beim neutippen auch entdeckt und umgeschrieben :D
der vorzeitige abbruch soll nicht passiern marc, da in der aufgabenstellung steht er soll ausnahmslos alle variablen testen.... find ich persönlich auch dumm aber egal.....
jedenfalls läuft er nun der algo...
thx

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Technische Informatik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]