Diskret optimering - 1

1. kursusgang, mandag den 4. september 12.30-16.15

For de der har fulgt kurset 'Diskret Matematik' på basisåret vil en del af Kapitel 1 i Schrijvers bog være en repetition.
Man kan eventuelt medbringe lærebogen fra dette basis-kursus.

12.30-13.00:

• Afsnit 1.1: korteste veje i grafer med ikke-negative kantlængder, Dijkstras algoritme.
• Afsnit 1.3: korteste veje i grafer med vilkårlige kantlængder, men uden kredse af negativ længde.
  

14.55-16.15:

• Afsnit 1.3: Bellman-Ford algoritmen.
• Afsnit 1.4: Minimum udspændende træ. Dijkstra-Prim algoritmen og Kruskals algoritme.
  

Opgaveregning:

1. Gennemgå Application 1.2. Forklar hvorfor metoden løser problemet.
2. Exercise 1.1.
3. Gennemgå Application 1.4. Forklar hvorfor metoden løser problemet.
4. Repeter betydningen af store O notationen.