Not logged in. · Lost password · Register

Page:  1  2  next 
Sto
Member since Nov 2013
69 posts
Subject: Klausur 09.08.2011
Hallo Leute,

ich habe mich gestern an die Klausur vom versucht 11.08.2011 und bin an folgenden Aufgaben deutlich gescheitert:
-Aufgabe 4) n-Damen-Problem
-Aufgabe 6) Levenshtein-Distanz

bei Aufgabe 4)
habe ich versucht das in scala umzusetzen, jedoch ist mir nicht ganz klar was bei der b) gefordert ist .
Die Funktion addQueen ss n bekommt die Liste ss aller M¨oglichkeiten, f¨ur n Spalten die
ersten m Zeilen mit m Damen zu belegen und gibt die Liste aller g¨ultigen M¨oglichkeiten
zur¨uck, jede der L¨osungen s ∈ ss um genau eine Dame (in Zeile m+1) zu erweitern.
Sie d¨urfen die in a) definierte Funktion myConcat und die vorgegebene Funktion safe
verwenden. Dar¨uber hinaus stehen Ihnen alle aus der Vorlesung bekannten Sprachkonstrukte
zur Verf¨ugung.

also addQueen(ss)(n) soll man so aufrufen können, wobei ss eine Liste ist mit Damen-besetzungen und n gibt die Groesse der Spalten (somit die groesse des Bretts) vor, habe ich das soweit richtig verstanden?

jetzt frage ich mich, von wo komm das "m" her?? und wie schaut die Umsetzung in Kombination der Funktion "safe" aus?

c) wäre wahrscheinlich nur der aufruf von addQueen(ss)(n) mit ss == eine leere liste ?!

bei Aufgabe 6)
bin ich mir nicht wirklich sicher wie die Implementierung ausschaut.

zum Feld 1 steht folgendes
Sorgen Sie in dem mit 1 markierten Feld daf¨ur, dass die einzelnen Pipeline-Stufen
m¨oglichst gleich viele Spalten der Tabelle f¨ullen. Es m¨ussen alle Spalten gef¨ullt werden.
Die Anzahl der Threads kann die Anzahl der Spalten ¨ubersteigen.

zuerst wollte ich die spalten aufteilen auf die anzahl der threads also : table.length/threads und der letzte Thread bekommt den Rest table.length%threads noch aufaddiert.

aber ich denke das ist hier nicht erwünscht weil das dann überhaupt nicht mehr gleichmaessig verteilt wäre wenn es z.b. 7 Spalten gibt und 8 Threads ... dann hätten thread[0] bis thread[6] keine spalten und Thread[7] alle restlichen 7, stimmts?

Kann mir jemand einen trick verraten wie ich so etwas umgehe?

Feld 2 :

Jeder Thread muesste sozusagen aus einer input-queue ein READY auslesen um anfangen zu dürfen und nach vollbrachter arbeit ein READY in die output-queue hineinlegen. wobei input queues[threadID] ist und output queues[threadID+1] .. letzter Thread dürfte an output nichts übergeben da es so IndexOutOfBoundsException wäre...

ist das der richtige gedanke?

Feld 3:

da bin ich eigentlich Ideenlos.. ich hätte jetzt einfach nur geraten dass man t.join(); aufrufen sollte.


Ich wäre dankbar wenn man mir hier weiterhilft und eine scala Implementierung zu Aufgabe 4 wäre sehr hilfreich zum nachvollziehen! :)
trigger
Member since Nov 2012
96 posts
Die Levenshtein Distanz würde mich auch interessieren...

Meine Synchronisation an der Queue:
if( threadId != 0) {
  queue[threadId - 1].take();
}
// blabla
if(threadId != threads - 1){
    queue[threadId].put(READY);
}

Warum ist die Anzahl der Queues gleich der Anzahl der Threads? Wenn ich z.B zwei Threads habe, dann reicht doch eine Queue ?
[hedgehogs dilemma = 42]
Member since Jan 2014
243 posts
hallo zusammen...hier mal ein lösungvorschlag für die lev-distanz  (Kasten 1)

falls jemand einen fehler sieht freue ich mich über feedback

for(int i = 0 ; i < threads; i++){
        final int threadId = i;
        queues[threadId] = new LinkedBlockingQueue<Object>();
       
                if(threads > columns) threads = columns;
        int inc = columns / threads;
       
        final int start = (i == threads - 1) ? columns: 1 + (i*inc);
            final int end =  (i == threads - 1) ? columns: (i+1)*inc;
    }
trigger
Member since Nov 2012
96 posts
Quote by [hedgehogs dilemma = 42:
]
hallo zusammen...hier mal ein lösungvorschlag für die lev-distanz  (Kasten 1)

falls jemand einen fehler sieht freue ich mich über feedback

for(int i = 0 ; i < threads; i++){
        final int threadId = i;
        queues[threadId] = new LinkedBlockingQueue<Object>();
       
                if(threads > columns) threads = columns;
        int inc = columns / threads;
       
        final int start = (i == threads - 1) ? columns: 1 + (i*inc);
            final int end =  (i == threads - 1) ? columns: (i+1)*inc;
    }

So ohne es mit eclipse überprüft zu haben:
Wenn threads > columns gilt, dann sind inc 0. Also von start 1 bis ende 0. Inc müsste, wenn ich mich nicht täusche,1 sein.
Der Letzte Thread arbeitet von columns bis columns. Da fehlt der Rest noch, falls columns%threads != 0 ist.

Ich finde die Aufgabe nicht gerade leicht.
[hedgehogs dilemma = 42]
Member since Jan 2014
243 posts
stimmt, so?

for(int i = 0 ; i < threads; i++){
        final int threadId = i;
        queues[threadId] = new LinkedBlockingQueue<Object>();
       
                if(threads > columns) threads = columns;
        int inc = columns / threads;
       
        final int start = (i == 0) ? 1: i*inc;
            final int end =  (i == threads - 1) ? columns: (i+1)*inc;
    }
lemur
Member since Oct 2013
110 posts
Hat denn jemand die Fehlersuche gemacht?
Sehe ich es richtig, dass bei c) die Verklemmung auftreten kann,
weil paid  ein Boolean-Array und kein AtomicBoolean-Array ist?
Das wäre die einzige Möglichkeit, die mir einfällt, aber ich find es merkwürdig,
weil ja nicht die Variable im Thread verändert wird, sondern der Thread die
Methode der Klasse aufruft, was nach meinem Verständnis dasselbe ist, wie,
wenn in der main einfach 10 mal die methode aufgerufen wird.
Liege ich da falsch?
This post was edited on 2014-07-20, 11:56 by lemur.
jeanorwin
Member since Oct 2013
53 posts
Mich würde auch eine Lösung für die b) interessieren. Dafür müsste doch eigentlich die Philosopher-Klasse modifziert werden? Eine andere Lösung fällt mir nicht ein.
lemur
Member since Oct 2013
110 posts
Quote by jeanorwin:
Mich würde auch eine Lösung für die b) interessieren. Dafür müsste doch eigentlich die Philosopher-Klasse modifziert werden? Eine andere Lösung fällt mir nicht ein.

Ich denke, da kann man einfach einen synchronized-Block (z.B. auf Dinner.lock) um die Zeile 97 machen.
lemur
Member since Oct 2013
110 posts
In reply to post #2
Quote by trigger on 2014-07-17, 13:32:
Meine Synchronisation an der Queue:
if( threadId != 0) {
  queue[threadId - 1].take();
}
// blabla
if(threadId != threads - 1){
    queue[threadId].put(READY);
}


ich hab da auch noch keine lösung, von der ich glaube, dass sie richtig ist, aber normal müsstest du doch prüfen, ob row != 0 ist und row != rows-1 , oder?
in der aufgabenstellung steht, dass nach jeder zeile ein READY-Object eingestellt werden muss.
[hedgehogs dilemma = 42]
Member since Jan 2014
243 posts
zur b)
Hier kann man doch einfach durch die reihenfolge der Forks die Verklemmung lösen:


Z28: if(i == 9){ guests[i] = new Philosopher(i,forks[0], forks[9]);
Z:29 }else{ guests[i] = new Philoshopher(i, forks[i], forsk[(i+1)%10]);}
[hedgehogs dilemma = 42]
Member since Jan 2014
243 posts
@ lemur:

das sollte meiner Meinung nach eigentlich passen,

weil die for schleife ja erst bei row = 1 anfängt => 0 ist ausgelassen

und das mit rows-1 braucht man nicht, da ja die queues zwischen den columns und nicht den rows geschaltet sind

=> das von trigger sollte eigentlich stimmen  ...(glaub ich)

EDIT:

das nach jeder Zeile ein Ready objekt eingefügt wird ist dadurch gewährleistet das der aufruf in der schleife ist und somit pro row automatisch gemacht wird
lemur
Member since Oct 2013
110 posts
Quote by [hedgehogs dilemma = 42:
]
das nach jeder Zeile ein Ready objekt eingefügt wird ist dadurch gewährleistet das der aufruf in der schleife ist und somit pro row automatisch gemacht wird

achso, das müsste ja tatsächlich passen, weil ja mit take() immer die liste geleert wird und erst wieder was drin ist, wenn der thread eben eine zeile fertig bearbeitet hat, sehe ich das richtig?
[hedgehogs dilemma = 42]
Member since Jan 2014
243 posts
also ich stell mir das ungefähr so vor

angenommen wir hätten nur zwei Spalten mit beliebig vielen Reihen und nur 1 Queue zum synchen.

Dann haben wir zwei threads A und B

A arbeitet jetzt jede Zeile ab und nach jeder Zeile packt er ein Ready Objekt in die Queue und signalisiert somit Thread B das Thread B die Zeile bearbeiten kann.

Thread B nimmt ja vor beginn jeder Zeile ein Ready Objekt aus der Queue, bzw. wartet solange bis dort eins auftaucht (Take wartet automatisch).

Der Vorteil an der Queue (im Gegensatz zu einem Exchanger) ist das Thread A beliebig schnell arbeiten kann.

Es kann also passieren angenommen wir haben 8 Zeilen, dass Thread A 5 bearbeitet und dann Thread B dran kommt und Thread B dann 2 bearbeitet, dann Thread A wieder 1 und dann Thread B 4
wenn Thread B dann bei Zeile 7 ankommt und versucht was aus der Queue zu nehmen ist diese leer, da ja thread A Zeile 7 noch nicht bearbeitet hat
=> Thread B blockiert .....irgendwann kommt dann wieder Thread A dran bearbeitet Zeile 7 und packt ein Ready Objekt in die Queue
=> wenn dann wieder B dran kommt ist er immernoch dabei zu versuchen ein Ready-Objekt aus der Queue zu nehmen - diesmal mit Erfolg, da thread A ja grade ein neues reingepackt hat
=> Thread B bearbeitet dann Zeile 7


hoffe dir Erklärung macht halbwegs Sinn ^^


EDIT: aber take leert die Liste eigentlich nicht sondern nimmt immer genau 1 Objekt raus
This post was edited on 2014-07-20, 13:22 by [hedgehogs dilemma = 42].
lemur
Member since Oct 2013
110 posts
cool, dann hab ich's verstanden. ich habe "leeren" geschrieben, weil ich vom idealfall ausgegangen bin, dass thread A ein ready-objekt reinpackt und thread b das wieder rausnimmt, bevor thread A das nächste reinpackt.
Gibt's Lösungsvorschläge für die c) ?
Eigentlich sind die ja die parallelisireungsaufgaben immer straight forward, aber die macht mir ganz schön schwierigkeiten
[hedgehogs dilemma = 42]
Member since Jan 2014
243 posts
bei der c) fällt mir auch nichts besseres ein als t.join

t.join bewirkt ja das auf den thread gewartet wird (also bzw. bis er mit seiner Arbeit fertig ist)
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Page:  1  2  next 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen