Kursinformation TTIT33

TTIT33 Algoritmer och optimering

Plan för optimeringsseminarierna 2006:

Seminarie 1-2: Introduktion, problemformulering, grafisk lösning, komplexitet.
Litteratur: Kap 1, 2, 3, 13.1.
Uppgifter: A: 2.7.2, 3.5.2, 3.5.4, 3.5.11. B: 2.7.1, 2.7.3, 3.5.5, 3.5.1.

Seminarie 3-4: Grundläggande teori, linjärprogrammering, simplexmetoden.
Litteratur: Kap 4, 5.
Uppgifter: LP-teori: A: 4.10.3, 4.10.4, 5.11.1, 5.11.4. B: 4.10.1, 4.10.5, 5.11.2, 5.11.3.
Simplexmetoden: A: 5.11.11, 5.11.12, 5.11.13, 5.11.18. B: 5.11.6, 5.11.7, 5.11.8.

Seminarie 5: LP-dualitet och känslighetsanalys.
Litteratur: Kap 6.
Uppgifter: A: 6.10.2, 6.10.8, 6.10.4, 6.10.20, 6.10.12, 6.10.21. B: 6.10.1, 6.10.3, 6.10.13, 6.10.17.

Seminarie 6-7: Optimering i grafer, billigaste uppspännande träd, handelsresandetur, brevbärartur.
Litteratur: Kap 7.
Uppgifter: A: 7.10.1, 7.10.3, 7.10.5, 7.10.9, 7.10.4. B: 7.10.2, 7.10.10, 7.10.11.

Seminarie 8-10: Billigaste väg, flöden i nätverk.
Litteratur: Kap 8, 9.
Uppgifter: Billigaste väg: A: 8.4.1, 8.4.2, 8.4.11, 8.4.10. B: 8.4.7a,b, 8.4.8.
Maxflöde: A: 9.4.1, 9.4.10, 9.4.14a. B: 9.4.2, 9.4.3.
Minkostnadsflöde, tillordning. A: 9.4.8, 9.4.15, 9.4.5, 9.4.18. B: 9.4.6, 9.4.7, 9.4.19, 9.4.20.

Seminarie 11-12: Heltalsproblem, trädsökning, plansnittning.
Litteratur: Kap 10, 11, 12.
Uppgifter: A: 11.4.13, 12.6.4, 11.4.12, 11.4.1, 7.10.16. B: 11.4.4, 11.4.8, 12.6.3, 11.4.17.

Seminarie 13-14: Komplexitet, heuristiker.
Litteratur: Kap 13, 14.
Uppgifter: A: 13.3.1, 14.9.3, 14.9.1a,c. B: 13.3.4, 14.9.7.

Repetition. 15.1.1, 15.1.7, 15.2.1, 15.2.3.

Utvidgning. 10.3.1, 15.1.2, 15.1.5, 15.2.7, 15.2.8.

Uppgifterna är uppdelade i kategori A (viktiga uppgifter) och B (bra uppgifter). Uppgifter ur A-gruppen tas upp på lektionstid. Resterande A-uppgifter samt B-uppgifterna räknas självständigt, på lektionstid och/eller hemma. Många fler övningsuppgifter i kompendiet är relevanta. Ett aktivt hemarbete är en förutsättning för bra resultat på kursen.


Kurslitteratur:
Kaj Holmberg: Kombinatorisk optimering med linjärprogrammering (kompendium, HT 2006), Bokakademin.

Sidansvarig: Kaj Holmberg
Senast uppdaterad: 2009-09-18