Das Rucksackproblem
5.4 Das RucksackproblemProblemstellung:
Eingabe: Ganzzahlige Volumina a1, . . . , an > 0, Nutzenwertec1, . . . , cn > 0, ganzzahlige Volumenschranke b.
Aufgabe: Packe die Objekte in einen Rucksack von Volumen b, so dassder Gesamtnutzen maximiert wird. (Wird gleich noch formalisiert.)
Wir betrachten zwei Problemvarianten:
1 Rucksackproblem mit Wiederholungen. (Von jedem Objekt sindbeliebig viele Kopien vorhanden.)
2 0-1-Rucksackproblem. (Jedes Objekt ist genau einmal vorhanden.)
Im Gegensatz zum fraktionalen Rucksackproblem (Kap. 3.1) ist es hiernicht erlaubt, Objekte zu teilen.Der Losungsvektor (x1, . . . , xn) muss also ganzzahlig sein.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 44
Das Rucksackproblem Mit Wiederholungen
Das Rucksackproblem mit Wiederholungen
Eingabe: Ganzzahlige Volumina a1, . . . , an > 0, Nutzenwertec1, . . . , cn > 0, ganzzahlige Volumenschranke b.
Aufgabe: Wahle x1, . . . , xn ∈ N mit∑1≤i≤n
xiai ≤ b,
∑1≤i≤n
xici moglichst groß.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 45
Das Rucksackproblem Mit Wiederholungen
Ansatz: Dynamische Programmierung.
Identifizierung von nutzlichen Teilproblemen:
Fur d = 0, . . . , b sei w(d) := maximaler erreichbarer Nutzenwert furVolumen a1, . . . , an, Nutzenwerte c1, . . . , cn, und Rucksackgroße d .
Klar: w(0) = 0.
Bellman’sche Optimalitatsgleichungen:
w(d) =
{0, d = 0
max ({ci + w(d − ai ) | 1 ≤ i ≤ n, ai ≤ d} ∪ {0}) , sonst.
Laufzeit: O(n · b). (Fur jedes d , 1 ≤ d ≤ b, muss ein Maximumuber ≤ n + 1 Werte gebildet werden.)
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 46
Das Rucksackproblem Mit Wiederholungen
Interessant: Wie berechnet man den Losungsvektor x1, . . . , xn?
Dafur legen wir ein Array I [0..b] an.
I [d ] gibt ein i ∈ {1, . . . , n} an, welches ci + w(d − ai ) maximiert. (Wennkein solches Objekt existiert, setzen wir I [d ]← 0.)
Wir nutzen den folgenden Algorithmus zur Berechnung desLosungsvektors:
1 Initialisiere ein Array X [1..n] mit 0’en
2 d := b
3 while d > 0 do
4 X [I [d ]]++
5 d := d − aI [d ]
Ausgabe: X [1..n].
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 47
Das Rucksackproblem Mit Wiederholungen
Beispiel:
b = 10:i 1 2 3 4ai 6 3 4 2ci 30 14 16 9
d 0 1 2 3 4 5 6 7 8 9 10w(d) 0 0 9 14 18 23 30 32 39 44 48I [d ] 0 0 4 2 4 2 1 2 1 1 4
Rekonstruierte Bepackung: x1 = 1, x2 = 0, x3 = 0, x4 = 2.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 48
Das Rucksackproblem Mit Wiederholungen
Resultat
Satz 5.4.1
Das Rucksackproblem mit Wiederholungen (mit Ausgabe einer optimalenLosung) ist in Zeit O(n · b) und Platz O(b) losbar.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 49
Das Rucksackproblem 0-1-Variante
Das 0-1-Rucksackproblem
Eingabe: Ganzzahlige Volumina a1, . . . , an > 0, Nutzenwertec1, . . . , cn > 0, ganzzahlige Volumenschranke b.
Ausgabe: I ⊆ {1, . . . , n} derart, dass∑
i∈I ai ≤ b und∑
i∈I ci moglichstgroß.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 50
Das Rucksackproblem 0-1-Variante
Ansatz: Dynamische Programmierung.
Identifizierung von nutzlichen Teilproblemen:
Fur 1 ≤ k ≤ n und 0 ≤ v ≤ b definieren wir
m(k , v) := max{∑
i∈Ici | I ⊆ {1, . . . , k} ∧
∑i∈I
ai ≤ v}.
Das Teilproblem P(k, v) besteht darin, ein I ⊆ {1, . . . , k} mit∑
i∈I ai ≤ vzu finden, das
∑i∈I ci maximiert.
Wir suchen also nach einer Auswahl, die nur Objekte Nummer 1, . . . , kbenutzt, eine modifizierte Gewichtsschranke v einhalt, und den Nutzenmaximiert.
Trivial: m(0, v) = 0 fur alle v .
P(n, b) ist das Gesamtproblem.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 51
Das Rucksackproblem 0-1-Variante
Eigenschaft”
Optimale Substruktur“:
Sei I optimale Losung fur P(k , v), d. h.:
m(k , v) =∑
i∈I ci , I ⊆ {1, . . . , k},∑
i∈I ai ≤ v .
Dann tritt einer der folgenden Falle ein.
1. Fall: k ∈ I . – Dann ist I − {k} optimale Losung furP(k − 1, v − ak), d. h.:
m(k , v)− ck =∑
i∈I−{k}
ci = m(k − 1, v − ak).
2. Fall: k 6∈ I . – Dann ist I optimale Losung fur P(k − 1, v),d. h.:
m(k , v) = m(k − 1, v).
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 52
Das Rucksackproblem 0-1-Variante
Beweis: Indirekt.
1. Fall: k ∈ I . – Annahme: I − {k} nicht optimal fur P(k − 1, v − ak).Dann gabe es eine bessere Teilmenge J ⊆ {1, . . . , k − 1} mit∑
i∈J ai ≤ v − ak und∑
i∈J ci >∑
i∈I−{k} ci .Dann ware aber J ∪ {k} eine bessere Losung fur P(k , v) als I ,Widerspruch.
2. Fall: k 6∈ I . – Annahme: I nicht optimal fur P(k − 1, v).Dann gabe es eine bessere Teilmenge J ⊆ {1, . . . , k − 1}. Dann ware aberJ auch besser als I fur P(k , v), Widerspruch.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 53
Das Rucksackproblem 0-1-Variante
Die optimale Losung fur P(k , v) enthalt also eine optimale Losung furP(k − 1, v ′) fur ein v ′ ≤ v .
Eigenschaft”
Optimale Substruktur“!
Bellman’sche Optimalitatsgleichungen:
m(k , v) =
m(k − 1, v − ak) + ck , falls v ≥ ak und diese Summe
großer als m(k − 1, v) ist;∗
m(k − 1, v), sonst.
fur 1 ≤ k ≤ n, 0 ≤ v ≤ b;
m(0, v) = 0, fur 0 ≤ v ≤ b.
∗ In diesem Fall ist k Element jeder optimalen Losung von P(k, v).
Wir berechnen alle m(k, v) mittels einer iterativen Prozedur.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 54
Das Rucksackproblem 0-1-Variante
5.4.2 Algorithmus DP-Zero-One-Knapsack(a1, . . . , an, c1, . . . , cn, b)Eingabe: a1, . . . , an: Volumina; c1, . . . , cn: Nutzenwerte; b: SchrankeAusgabe: I ⊆ {1, . . . , n}: Optimale legale Auswahl.Datenstrukturen: m[0..n,0..b]: integer;(1) for v from 0 to b do m[0,v] ← 0;(2) for k from 1 to n do(3) for v from 0 to b do(4) if v − ak ≥ 0(5) then s ← m[k−1,v−ak] + ck else s ← 0;(6) if s > m[k−1,v](7) then m[k,v] ← s;(8) else m[k,v] ← m[k−1,v];
(∗ Konstruktion der optimalen Menge: ∗)(9) I ← ∅; r ← m[n,b];(10) for k from n downto 1 do(11) if m[k−1,r−ak] + ck > m[k−1,r](12) then r ← r− ak; I ← I ∪ {k};(13) return I.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 55
Das Rucksackproblem 0-1-Variante
Korrektheit des ermittelten Wertes m[n,b] ergibt sich aus denBellman’schen Optimalitatsgleichungen durch Induktion uber k .
Korrektheit der ausgegebenen Menge I folgt aus der obigen Uberlegung,dass die Bedingung
m(k − 1, v − ak) + ck > m(k − 1, v)
entscheidend ist fur die Frage, ob k in der optimalen Losung von P(k, v)enthalten ist oder nicht, und mit Induktion.
Laufzeit des Algorithmus: O(n · b).
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 56
Das Rucksackproblem 0-1-Variante
Beispiel:
b = 6:i 1 2 3 4
ai 3 4 2 1
ci 4 6 2 5
m[k , v ]:v : 0 1 2 3 4 5 6
k = 0 0 0 0 0 0 0 0
1 0 0 0 4 4 4 4
2 0 0 0 4 6 6 6
3 0 0 2 4 6 6 8
4 0 5 5 7 9 11 11
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 57
Das Rucksackproblem 0-1-Variante
Ablesen von I aus dem Array m[0..n,0..b]:
Benutze m(k − 1, v − ak) + ck > m[k − 1, v ] als Kriterium.
(Eingerahmte Eintrage der Tabelle.)
m[4, 6] = 11 > 8 = m[3, 6],also I := {4}, v := 6 - 1 = 5
m[3, 5] = 6 6> 6 = m[2, 5],m[2, 5] = 6 > 4 = m[1, 5],
also I := I ∪ {2}, v := 5 - 4 = 1
m[1, 1] = 0 6> 0 = m[0, 1].
Resultat: Optimale Menge ist I = {2, 4}.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 58
Das Rucksackproblem 0-1-Variante
Man kann auf die Speicherung des gesamten Arrays m verzichten.
Man halt immer nur die letzte Zeile, und aktualisiert die Eintrage vonrechts nach links.(Rechts vom Arbeitspunkt v : Eintrage m(k, v ′), links davon: Eintragem(k − 1, v ′).)
Eine Bitmatrix b[1..n,0..b] fuhrt mit, ob Objekt k fur eine optimaleBepackung notwendig ist oder nicht.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 59
Das Rucksackproblem 0-1-Variante
5.4.3 Algorithmus DP-Zero-One-Knapsack(a1, . . . , an, c1, . . . , cn, b)Eingabe: a1, . . . , an: Volumina; c1, . . . , cn: Nutzenwerte; b: SchrankeAusgabe: I ⊆ {1, . . . , n}: Optimale legale Auswahl.Datenstrukturen: m[0..b]: integer; b[1..n,0..b]: Boolean;(1) for v from 0 to b do m[v] ← 0;(2) for k from 1 to n do(3) for v from b downto 0 do(4) if v − ak ≥ 0 then s ← m[v−ak] + ck else s ← 0;(5) if s > m[v]
(6) then m[v] ← s; b[k,v] ← 1;(7) else b[k,v] ← 0;
(∗ Konstruktion der optimalen Menge: ∗)(8) I ← ∅; r ← m[b];(9) for k from n downto 1 do(10) if b[k,r] = 1 then(11) r ← r−ak; I ← I ∪ {k};(12) return I.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 60
Das Rucksackproblem 0-1-Variante
Resultat
Satz 5.4.4
Das 0-1-Rucksackproblem (mit Ausgabe der optimalen Losung) ist in ZeitO(nb) losbar.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 61
Das Rucksackproblem 0-1-Variante
Wie gut sind diese beiden Algorithmen?
Die Große, nicht die Bitlange der Gewichtsschranke b geht in dieLaufzeit ein.
Wir nennen Algorithmen mit einer Laufzeit O(p(n,B)), wo n die(strukturelle) Große der Eingabe und B eine obere Schranke fur einigeoder alle Zahlenkomponenten der Eingabe, und p ein Polynom in zweiVariablen ist, pseudopolynomiell.
Die Existenz eines pseudopolynomiellen Algorithmus fur dasRucksackproblem widerspricht nicht der Tatsache, dass das0-1-Rucksackproblem wahrscheinlich keinen Polynomialzeitalgorithmus hat(nachstes Semester: NP-Vollstandigkeit!): Die naturliche Eingabegroßeberucksichtigt log b und nicht b.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 62
TSP
5.5. Traveling Salesperson1
Eingabe: Vollstandiger, gerichteter Graph mit Kantengewichten ai ,j ≥ 0.(Also eine Matrix ((ai ,j))1≤i ,j≤n.)
Gesucht: Eine gunstigste”Rundreise“, bei der jede Stadt (also jeder
Knoten) genau einmal besucht wird und zum Startpunkt zuruckgekehrtwird.
Formal: Gesucht ist eine Permutation π von {1, . . . , n}, so dass
c(π) =∑
2≤i≤naπ(i−1),π(i) + aπ(n),π(1)
minimal unter allen moglichen Permutationen.
1Das Problem, was ihr beim Sommerfest 2012 losen solltet!
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 63
TSP
Ein Beispiel
A B
C D
E
2
2
1
4
32
3
2
24
Kurzeste Tour: (A,B,E ,C ,D,A) mit Lange 10.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 64
TSP
Klar: Wir konnen den Anfangspunkt fest wahlen. (Hier: Tour startet imKnoten 1.)
Naiver Ansatz: Probiere alle (n − 1)! mogliche Rundtouren aus.
Wir entwickeln einen sehr viel besseren Algorithmus, basierend auf
”Dynamischer Programmierung“.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 65
TSP
Zentrale Frage: Wie sehen sinnvolle Teilprobleme aus?
Wir betrachten P(S , `) mit S ⊆ {1, . . . , n}, 1 ≤ ` ≤ n, wobei 1, ` ∈ S .
P(S , `) fragt nach dem kurzesten, einfachen Weg von 1 durch alleKnoten in S mit Ende `.
Basisfalle: P({1}, 1) = 0,P(S , 1) =∞ fur |S | > 1.
Am Ende: Lange einer kurzesten Rundtour:
min(P({1, . . . , n}, `) + a`,1 | 1 ≤ ` ≤ n).
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 66
TSP
Fur |S | > 1 gilt:
P(S , j) = min(P(S − {j}, i) + ai ,j | i ∈ S − {j}).
Iterativ programmiert sieht der Algorithmus wie folgt aus:
1 P({1}, 1)← 0
2 for s ← 2 to n do
3 foreach S ⊆ {1, 2, . . . , n} with |S | = s and 1 ∈ S do
4 P(S , 1)←∞5 foreach j ∈ S , j 6= 1 do
6 P(S , j)← min(P(S − {j}, i) + ai ,j | i ∈ S − {j}).
7 return min(P({1, . . . , n}, `) + a`,1 | 1 ≤ ` ≤ n)
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 67
TSP
ResultatSatz 5.5.1
Das Problem Traveling Salesperson kann mittels dynamischerProgrammierung in Zeit O(2n · n2) gelost werden.
(Dies ist eine wesentliche Verbesserung gegenuber dem naiven Ansatz mitLaufzeit O(n!).)
Beweis
Die Anzahl aller Teilmengen von {1, . . . , n} ist 2n.
Zu jeder solcher Teilmenge gibt es maximal n Teilprobleme.
Jedes Teilproblem kann in Zeit O(n) gelost werden.
Fur Zuhause: Wie konstruiert man eine optimale Rundtour (also dieKnotenfolge)?
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 68
Matrixkettenmultiplikation
Das folgende Problem wurde in der Vorlesung nicht besprochen und istdeswegen nicht prufungsrelevant. Es stellt jedoch ein weiteres schonesBeispiel fur einen auf dem Paradigma
”Dynamische Programmierung“
basierenden Algorithmus dar.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 68
Matrixkettenmultiplikation
5.6 Optimale Matrizenmultiplikation
Sei A1 = (αij)1≤i≤r0,1≤j≤r1 eine r0 × r1-Matrix, A2 = (βjk)1≤j≤r1,1≤k≤r2
eine r1 × r2-Matrix.
Berechne Produkt A1 · A2 =: C = (γik)1≤i≤r0,1≤k≤r2 .
Standardmethode (nicht Strassen-Methode o.a.):
γik =∑
1≤j≤r1
αijβjk ,
fur 1 ≤ i ≤ r0, 1 ≤ k ≤ r2. – r0r1r2 Multiplikationen.
”Kosten“: c(r0, r1, r2) := r0r1r2
Gesamtzeit = Θ(r0r1r2).
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 69
Matrixkettenmultiplikation
Gegeben: A1,A2, . . . ,Ak , wobei Ai eine ri−1 × ri -Matrix ist.
Aufgabe
Berechne A1A2 . . .Ak , moglichst kostengunstig.
Die Matrizenmultiplikation ist assoziativ. Bei der Berechnung von A1A2A3
entstehen Kosten von
Kosten r0r1r2 + r0r2r3 bei der Reihenfolge (A1A2)A3 undKosten r0r1r3 + r1r2r3 bei der Reihenfolge A1(A2A3).
Beispiel: (r0, r1, r2, r3) = (5, 10, 3, 10):Kosten 300 bei der ersten Reihenfolge, 800 bei der zweiten.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 70
Matrixkettenmultiplikation
Problem:
Eingabe: Dimensionen r0 × r1, r1 × r2, . . ., rk−1 × rk von MatrizenA1, . . . ,Ak .Ausgabe: Eine (
”optimale“) Klammerung, die bei der Berechnung von
A1 · · ·Ak die Gesamtkosten (Anzahl aller Multiplikationen von Zahlen)minimiert.
Seien c(r0, . . . , rk) die Kosten bei optimaler Klammerung, wobei k ≥ 2und r0, r1, . . . , rk ≥ 1 beliebige ganze Zahlen sind.
Fur k = 1 setzen wir c(r0, r1) := 0 fur alle r0, r1.
Klar: c(r0, r1, r2) = r0r1r2.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 71
Matrixkettenmultiplikation
Die optimale Losung des Klammerungsproblems hat die Form
(A1 · · ·A`)︸ ︷︷ ︸irgendwie
geklammert
(A`+1 · · ·Ak)︸ ︷︷ ︸irgendwie
geklammert
fur ein 1 ≤ ` < k (das wir nicht kennen!).
Zentrale Beobachtung (”
Optimale Substruktur“):
Die Klammerungen in den Teilen A1 · · ·A` bzw. A`+1 · · ·Ak mussenoptimale Kosten fur die Teilprobleme liefern.
Ware z. B. die Teilklammerung von A1 · · ·A` nicht optimal, dann konnteman durch Verbesserung dieses Teils die Gesamtkosten senken.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 72
Matrixkettenmultiplikation
Aus dieser Beobachtung ergibt sich: Es gibt ein `, 1 ≤ ` < k mit
c(r0, . . . , rk) = c(r0, . . . , r`) + c(r`, . . . , rk) + r0r`rk︸ ︷︷ ︸außerste
Matrizenmult.
.
Das `, das die Summe auf der rechten Seite minimiert, ist das richtige.
Mussen: Optimale Klammerungen bzw. ihre Kosten fur die TeilproblemeA1 · · ·A` und A`+1 · · ·Ak berechnen.
Ansatz: Betrachte die Teilprobleme TP(i , j), das TeilproduktAi · · ·Aj , 1 ≤ i ≤ j ≤ n, mit minimalen Kosten zu berechnen.
Parameter zu TP(i , j): ri−1, . . . , rj .
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 73
Matrixkettenmultiplikation
Beobachtung (”
Optimale Substruktur“), angewendet auf dasTeilproblem, liefert:
Rekursionsformel
Basisfall: c(ri−1, ri ) = 0, fur 1 ≤ i ≤ k .
Schrittfall:
c(ri−1, . . . , rj) = mini≤`<j
{c(ri−1, . . . , r`) + c(r`, . . . , rj) + ri−1r`rj},
fur 1 ≤ i < j ≤ k .
”Bellman’sche Optimalitatsgleichungen.“
(Checke diese Gleichung fur j = i + 1!)
Iterative Auflosung der Rekursionsformel!
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 74
Matrixkettenmultiplikation
MatrixOptimal((r0, . . . , rk))Eingabe: Dimensionsvektor (r0, . . . , rk)Ausgabe: Kosten c(r0, . . . , rk) bei der optimalen Klammerung
l[1..k,1..k]: Plan zur Ermittlung der optimalen Unterteilung;Datenstruktur: Matrizen C[1..k,1..k], l[1..k,1..k](1) for i from 1 to k do(2) C[i,i] ← 0;(3) for i from 1 to k − 1 do(4) C[i,i+1] ← ri−1 · ri · ri+1;(5) for d from 2 to k − 1 do(6) for i from 1 to k − d do(7) bestimme das `, i ≤ ` < i+d,(8) das C = C[i,`] + C[`+ 1,i+d] + ri−1 · r` · ri+d minimiert;(9) l[i,i+d] ← dieses `;(10) C[i,i+d] ← das minimale C ;(11) Ausgabe: C[1..k,1..k] und l[1..k,1..k].
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 75
Matrixkettenmultiplikation
Korrektheit: Man beweist durch Induktion uber d = 0, 1, . . . , k − 1 mitHilfe der Bellman’schen Optimalitatsgleichung, dass C[i,i + d] die Zahlc(ri−1, . . . , ri+d) enthalt.
Ubung: Man zeige, dass mit Hilfe der l[i,j]-Werte die optimaleKlammerung in Linearzeit ermittelt werden kann.
Laufzeit: Die Minimumssuche in Zeile (8) kostet Zeit O(k); (6)–(10) und(5)–(10) ergibt sich eine Laufzeit von Θ(k3).
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 76
Matrixkettenmultiplikation
Beispiel:
(r0, . . . , r4) = (3, 2, 2, 5, 6)
C: l:i 1 2 3 4
1 0 12 42 1082 0 20 803 0 604 0
1 2 3 4
1 * * 2 22 * * 33 * *4 *
Optimale Klammerung: (M1M2)(M3M4).
Kosten: 108 Multiplikationen.
FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 77