Die Aufgaben von Blatt 4 drehen sich um Place & Route; d.h. Kernighan-Lin- und Lee-Algorithmus. Viel mehr Stoff ist wegen der ganzen Feiertage diesmal nicht zusammen gekommen.

Es empfiehlt sich, die Aufgaben anzuschauen, da man dann erst wirklich versteht, wie die Algorithmen funktionieren. Gerade bei Kernighan-Lin ist das der Fall.

Fragen können wie immer hier im Forum gepostet werden!

Viele Grüße,
Linus

Nachdem das in der Übung mit dem Vorrechnen von Aufgabe 1 vom Blatt 4 ja nicht so gut geklappt hat, sind wir die Musterlösung noch einmal durchgegangen. Dabei haben wir festgestellt, dass sie doch weitestgehend richtig war. Nur in der letzten Zeile hatte sich ein Fehler eingeschlichen, wodurch die Gesamtkosten nach der 2. Iteration des Algorithmus nicht wieder die gleichen waren wie vorher. Da das manuelle Nachrechnen an der Tafel dann eben nicht stattfand, wie es wünschenswert gewesen wäre, habe ich die Musterlösung von Aufgabe 1 zum Runterladen auf die Vorlesungsseite gestellt.

Bei Aufgabe 4 war die Musterlösung, die ich aus einem alten Bestand übernommen hatte, tatsächlich falsch. Da hat sich wohl beim Erstellen einfach jemand verzählt. Die richtige Antwort lautet: Reihenfolge CAB mit Kosten von 47.

Viele Grüße,
Linus