0 Daumen
680 Aufrufe

Aufgabe:

Es geht weniger um eine Aufgabe und mehr um eine kleine allgemeine Verständnisfrage die für euch Mathematiker bestimmt total einfach zu beantworten, sozusagen trivial ist. Und zwar: was bedeuten die 2x2 bzw 2x4 Matritzen (aus 1 bzw. -1 bestehend). Ich verstehe nicht so recht was die da zu suchen haben....

for (i = 0; i <= n; i++) { 
...
}
$$\left\{i \in Z ;\left[\begin{array}{cc}{-1} & {1} \\ {1} & {0}\end{array}\right]\left[\begin{array}{l}{i} \\ {n}\end{array}\right] \geq\left[\begin{array}{l}{0} \\ {0}\end{array}\right]\right\}$$

In general:

\( P=\left\{\vec{x} \in K^{n} ; A \cdot \vec{x} \leq B \cdot \vec{n}+\vec{b}\right\} \)


Iteration space:

$$\begin{array}{l}{P=\left\{\vec{x} \in K^{n} ; A \cdot \vec{x} \leq \vec{b}\right\}} \\ {P=\left\{\vec{x} \in Z^{2} ; A \cdot \vec{x} \leq \vec{b} \right\} }\end{array} = \left\{ (i, j)^{T} \in Z^{2} ;\left[\begin{array}{cc}{1} & {0} \\ {-1} & {0} \\ {0} & {1} \\ {1} & {-1}\end{array}\right]\left[\begin{array}{c}{i} \\ {j}\end{array}\right] \leq\left[\begin{array}{c}{N-1} \\ {0} \\ {N-1} \\ {0}\end{array}\right] \right \}$$


For locality: Sweep vertically

for (i = 0; i <= 5; ++i)
for (j = i; j <= 7; ++j)
Z[j][i] = 0;

Polyhedron:

$$\left[\begin{array}{cc}{1} & {0} \\ {-1} & {0} \\ {-1} & {1} \\ {0} & {-1}\end{array}\right]\left[\begin{array}{l}{i} \\ {j}\end{array}\right]+\left[\begin{array}{l}{0} \\ {5} \\ {0} \\ {7}\end{array}\right] \geq\left[\begin{array}{l}{0} \\ {0} \\ {0} \\ {0}\end{array}\right]$$

Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

Hier wurden die Bedingungen im Schleifenkopf als Matrixungleichung geschrieben.

Bei der ersten for(int i=0; i <= n; i++) fängst du mit i = 0 an und inkrementierst dann solange bis i = n. Also gilt

$$ 0≤i \text{ und } i≤n$$

bzw

$$ 0≤i \text{ und } 0≤n-i$$

Das kannst du auch schreiben als

$$ \begin{pmatrix}-1&1\\1&0\end{pmatrix} \begin{pmatrix} i \\ n \end{pmatrix} ≥ \begin{pmatrix}0\\0\end{pmatrix}$$

Bei der zweiten Schleife genauso.

Avatar von

Danke - dann muss ich mir nochmal genau vor Augen führen wie das funktioniert - sinngemäß ist es aber schon mal eine große Hilfe. Danke für die Antwort.

Naja wenn du die linke Seite ausmultiplizierst dann steht da:

$$\begin{pmatrix}-i+n\\i\end{pmatrix}≥ \begin{pmatrix}0\\0\end{pmatrix} $$

Und jetzt die beiden Zeilen einzeln lesen. Dann bekommst du genau die beiden Bedingungen oben.

Bei der zweiten Matrix erhältst du

i ≥ 0, -i+5≥0, -i+j≥0, -j+7≥0

Diese vier Ungleichen beschreiben eindeutig die im Schleifenkopf durchlaufenen (i,j)

Eigentlich sehr logisch. Wäre ohne dich aber nicht darauf gekommen. Vielen Dank für deine Bemühungen!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community