shared int var=0; proc1(){
var++;
} proc2(){
if (var==1){
var=2;
} assert(var==2);
}
→ stimmt offensichtlich nicht, wenn proc2 zuerst laeuft. Das sollte ich noch mit einem parallelen endlichen Automaten beweisen. Zeichnen Sie ein ein Sortiernetzwerk → Batchers Merging Netzwerk hingemalt, das sorting Netzwerk wollte er dann gar nicht mehr.
(n,0)=0; (2n,k)=(2n,k-1) Hier wusste ich nicht so genau, was er will, also hab ich erstmal bisschen was allgemeines ueber DP erzaehlt (Problem mit Divide and Conquer herunterbrechen und zwischenergebnisse speichern und wiederverwenden). Dann hab ich ihm gesagt, dass ja immer nur 0 rauskommen kann. Daraufhin hat er mir noch eine Zeile gezeigt: (n,k)=(n-1,k) Ich hab ihm erklaert, dass ich nicht glaube, dass die Formel stimmt, und das man das so auch nicht mit Divide and Conquer loesen kann. Ich hab eben nochmal nachgeschaut, was Catalan Zahlen sind, und festgestellt, dass die Formel fuer die n-te Catalan Zahl lautet: C_n = (2n,n)-(2n,n-1), wobei die Klammern Binomialkoeffizienten sind. Was er mir da gezeigt hat, war also ziemlicher Unsinn. Diese Frage hat dann auch zum Glueck nicht gezaehlt.
-Any algorithm running on a PRIORITY-CRCW with p(n) processors in time t(n) can be simulated on an EREW in time t(n)O(log(p(n)) without increasing the number of processors. -Any algorithm running on a PRIORITY-CRCW can be simulated by a COMMON-CRCW with no loss of parallel time provided sufficiently many processors are available.