Homepage
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
