Kollinearität herstellen |
| 13.10.2010, 05:07 | Gast12452421 | Auf diesen Beitrag antworten » |
| Kollinearität herstellen ich sitze seit Tagen an einer Aufgabe zu Kollinarität aus einer Informatikvorlesung: There are n distinct points 0, 1, 2, . . ., n − 1 on a two-dimensional plane. Each point i represents a mobile robot and its position is controlled by a process Pi, that can read the position of the points (i − 1) and (i+1) in addition to its own, and redefine its own position. The goal of the following algorithm is to make the n points collinear (i.e., they fall on the same straight line) from arbitrary initial positions. Process P0 does not do anything — every other process Pi(1 ≤ i ≤ n − 1) executes the following program: program align {for i} do (i-1, i, i+1) are not collinear ➔ move i so that (i-1, i, i+1) are aligned od Will the points be aligned if there is a central scheduler? What happens with distributed schedulers and fine grained atomicity? Justify your answer. Zur erklärung bei einem central scheduler, kann immer nur ein Prozess das programm ausführen. Beim distributed scheduler, können praktisch alle Prozesse ihre Berechnung parallel ausführen. Also erst alle (i-1, i, i+1) are not collinear und dann move i so that (i-1, i, i+1) are aligned. Meine Lösung besagt eher das die Lösung approximiert wird. Bsp. (1|0),(2|10),(3|100),(4|1000) (also Kollinear auf der x-Achse aber nicht in der y-Achse) Bsp für Central scheduler (nur y-Achse): 0, 50, 100, 1000 (3ten Wert) 0, 50, 525, 1000 (2ten Wert) 0, 262.5, 525, 1000 (3ten Wert) 0,262.5, 631.25, 1000 (2ten Wert) 0,315.625, 631.25, 1000 .... also konvergiert gegen (0, 333+(1/3), 666+(2/3),1000) Gleiches Beispiel für Distributed Scheduler (diesmal aus Excel kopiert): 0 10 100 1000 0 50 505 1000 0 252,5 525 1000 0 262,5 626,25 1000 0 313,125 631,25 1000 0 315,625 656,5625 1000 0 328,28125 657,8125 1000 0 328,90625 664,140625 1000 0 332,0703125 664,453125 1000 0 332,2265625 666,0351563 1000 0 333,0175781 666,1132813 1000 ... also konvergiert gegen (0, 333+(1/3), 666+(2/3),1000) Da das natürlich in beiden fällen nur konvergiert, wüde ich ob die Punkte in einer linie liegen mit nein beantworten. Es wird nur mit beliebiger Genauigkeit approximiert. Oder habe ich da einen Denkfehler? Gibt es eine bessere Lösung? |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
