Diskret Optimering.


17. kursusgang, tirsdag den 16. november 12.30-16.15


Forelæsning i G5-112 ved LKJ:

12.30-13.00: Repetition.

14.55-16.15:

Resten af afsnit 12.4: mere om matroider.
Afsnit 12.5: algoritme der finder en maksimum delmængde, der er uafhængig i to matroider.

Opgaveregning:

  1. Opgave 1 i kapitel 12.

  2. Benyt den grådige algoritme til at finde en lineært uafhængig mængde af søjler i matricen i Figur 12-13 så summen af tallene i de fundne vektorer er størst mulig.

  3. En partition matroid er defineret i eksempel 12.8. Vis direkte fra definition 12.2 at dette er en matroide.

  4. Opgave 12 (b) i kapitel 12.

  5. Opgave 9 i kapitel 12.