Folie 1 - Heinz Nixdorf Institut

Folie 1 - Heinz Nixdorf Institut

HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity Algorithmen und Komplexitt Teil 1: Grundlegende Algorithmen WS 08/09 Friedhelm Meyer auf der Heide Vorlesung 4, 21.10.08 Friedhelm Meyer auf der Heide 1 Organisatorisches HEINZ NIXDORF INSTITUTE

University of Paderborn Algorithms and Complexity Neue bungsgruppe, Di 16-18, F2 211 Zustzlicher bungsgruppenleiter: Ralf Petring wird durch Adrian Ogiermann untersttzt 30% der Punkte der -Bltter sind Voraussetzung zur Zulassung zur mndlichen Prfung. Friedhelm Meyer auf der Heide 2 HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity

Greedy Algorithmen Friedhelm Meyer auf der Heide 3 Greedy Algorithmen HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity Friedhelm Meyer auf der Heide 4 Greedy-Algorithmen

HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity Wir wissen: Greedy-Algorithmen fr z.B. Bruchteil Rucksack und Minimale Spannbume sind optimal. Greedy-Algorithmen fr z.B. 0-1 Rucksack ist sehr schlecht. Greedy-Algorithmen fr z.B. Bin Packing (First Fit, Best Fit) sind 2-Approximationen, also gut, wenn auch nicht optimal. Kann man einem Problem ansehen, ob der zugehrige Greedy-Algorithmus optimal ist? Friedhelm Meyer auf der Heide 5

Wann sind Greedy-Algorithmen optimal? HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity Friedhelm Meyer auf der Heide 6 Beispiele fr Teilmengensysteme HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity

Friedhelm Meyer auf der Heide 7 Teilmengensysteme und der kanonische Greedy-Algorithmus HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity Der kanonische G.A. fr Rucksack ist sehr schlecht (haben wir gezeigt) Der kanonische G.A. fr MST ist optimal, haben sie in DuA gezeigt: Kruskals Algorithmus Kann man dem Teilmengensystem ansehen, ob der kanonische G.A. eine optimale Lsung liefert? Friedhelm Meyer auf der Heide

8 Greedy-Algorithmen und Matroide HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity Bem: Alle maximalen Mengen eines Matroids sind gleich gro. Bew: bungsaufgabe Das Teilmengensystem fr Rucksackproblem ist kein Matroid. Das Teilmengensystem fr MST ist ein Matroid! Friedhelm Meyer auf der Heide 9

Das MST-Matroid HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity Satz: Das Teilmengensystem fr MST ist ein Matroid. Beweis: (i) 2 U (klar) (ii) B 2 U, A B ) A 2 U (klar) Wir mssen die Austauscheigenschaft nachweisen. Friedhelm Meyer auf der Heide 10

Die Austauscheigenschaft des MST-Matroids HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity Z.z: Bew: Friedhelm Meyer auf der Heide 11 Matroide und der Kanonische Greedy-Algorithmus HEINZ NIXDORF INSTITUTE

University of Paderborn Algorithms and Complexity ! siehe Tafel B\A ! siehe Tafel Friedhelm Meyer auf der Heide 12 Noch ein interessantes Matroid: Matching fr links-knotengewichtete bipartite Graphen HEINZ NIXDORF INSTITUTE University of Paderborn

Algorithms and Complexity Gegeben sei ein bipartiter, gewichteter Graph G=(L [ R, K, w) mit positiven Knotengewichten w(e) fr die Knoten aus L. Ein Matching in G ist eine Menge von paarweise disjunkten Kanten. Ein maximales Matching ist eins mit maximalem Gewicht (seiner linken Knoten.) Friedhelm Meyer auf der Heide 13 Das bipartite-Matching Matroid

HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity Whle E=L. B L ist in U, falls es ein Matching mit linker Seite B in G gibt. Satz: (E,U) ist ein Matroid. Bew: (i) 2 U (klar) (ii) B 2 U, A B ) A 2 U (klar) Wir mssen die Austauscheigenschaft nachweisen. Friedhelm Meyer auf der Heide 14

Beweis der Austauscheigenschaft HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity Whle E=L. B L ist in U, falls es ein Matching mit linker Seite B in G gibt. Z.z.: Bew: Betrachte die Kantenmengen X und Y, die zu den Matchings fr A und B gehren. Betrachte den durch X [ Y induzierten Graphen H. H besteht aus isolierten Kanten, die rot, blau oder rot/blau sein knnen. disjunkten Wegen, die aus abwechselnd roten und blauen Kanten bestehen.

H hat mehr rote als blaue Kanten Also: Es gibt rote isolierte Kante (mit linkem Knoten v 2 B\A) oder Weg der Lnge > 1 mit mehr roten als blauen Kanten. Friedhelm Meyer auf der Heide 15 HEINZ NIXDORF INSTITUTE Beweis der Austauscheigenschaft University of Paderborn Algorithms and Complexity Also: Es gibt rote isolierte Kante (mit linkem Knoten v 2 B\A) oder Weg P der Lnge > 1 mit mehr roten als blauen Kanten.

Im ersten Fall: A [ {v} 2 U Im zweiten Fall: P hat ungerade Lnge, beginnt und endet mit roter Kante v 2 B\A A [ {v} 2 U, da die roten Kanten ein Matching bilden. Friedhelm Meyer auf der Heide 16 bungsaufgabe HEINZ NIXDORF INSTITUTE University of Paderborn Algorithms and Complexity

Nutzen sie obige berlegungen, um einen effizienten Algorithmus zur Berechnung eines maximalen Matchings in einem (links Knoten-)gewichteten bipartiten Graphen anzugeben. Bem: Es ist auch nicht zu schwierig, maximale Matchings bzgl. Kantengewichten zu berechnen. (Augmenting Paths Methode; wir kommen darauf spter zurck, wenn wir ber Flussprobleme reden.) Die zugrunde liegende Struktur ist dann der Durchschnitt zweier Matroide. Friedhelm Meyer auf der Heide 17 HEINZ NIXDORF INSTITUTE University of Paderborn

Algorithms and Complexity Thank you for your attention! Friedhelm Meyer auf der Heide Heinz Nixdorf Institute & Computer Science Department University of Paderborn Frstenallee 11 33102 Paderborn, Germany Tel.: +49 (0) 52 51/60 64 80 Fax: +49 (0) 52 51/62 64 82 E-Mail: [email protected] http://www.upb.de/cs/ag-madh Friedhelm Meyer auf der Heide 18

Recently Viewed Presentations

  • Brainstem glioma

    Brainstem glioma

    Brainstem glioma Chodorma CJD Cystic Hematoma De Morsier Syndrome Dysembryoplastic Neuroepithelial Tumor Dysembryoplastic Neuroepithelial Tumor (DNET) Epidermoid Erdheim-Chester disease GBM from a PXA PRES with diffusion abnormality Nonaneurysmal Perimesencephalic Bleed Hydranencephaly Basilar tip thrombosis Central neurocytoma Bilateral Accustic Shwannomas in...
  • Motor Control Using 555 Timer - Electronics Simplified!!

    Motor Control Using 555 Timer - Electronics Simplified!!

    WATER LEVEL CONTROLLER USING 555 TIMER By, Department of TCE/ECE JNNCE , Shimoga OBJECTIVE: Automatic Control of AC Motor Thus Preventing overflow from Over Head Tank.
  • Osmosis Aim: How does osmosis occur through a semi-permeable ...

    Osmosis Aim: How does osmosis occur through a semi-permeable ...

    Arial Calibri Times New Roman Office Theme Osmosis Aim: How does osmosis occur through a semi-permeable membrane? Objectives: Students should be able to. 1-Define osmosis, semi-permeable membrane & passive transport 2-Explain the concept of osmosis & passive transport. 3-Define &...
  • Figure 14.1a Gross Anatomy of the Spinal Cord

    Figure 14.1a Gross Anatomy of the Spinal Cord

    Gross Anatomy of the Spinal Cord. Features of the Spinal Cord. 45 cm in length. Passes through the foramen magnum. Extends from the brain to L. 1. Consists of:
  • COSC 6341 Information Retrieval - Computer Science

    COSC 6341 Information Retrieval - Computer Science

    COSC 6341 Information Retrieval Project Presentation What is Collection Wide Information? (CWI) What is Dissemination ? Dissemination Spreading Making known Distribution Examples of Distributed Archive Models A distributed Technical Report Archive in an University Documentation for a large distributed project...
  • Differential Effects of Reciprocity and Attitude Similarity ...

    Differential Effects of Reciprocity and Attitude Similarity ...

    Differential Effects of Reciprocity and Attitude Similarity Across Long-Versus Short-Term Mating Contexts Andrew T Lehr, Glenn Geher The Journal of Social Psychology Washington: Aug 2006. Vol. 146, Iss. 4; pg. 423, 17 pgs Reciprocity The tendency in people to become...
  • One to One Communication…. - Colorado FFA

    One to One Communication…. - Colorado FFA

    Ag Communications One to One Communication One to One Communication Communicating with one other person One to One Communication Face to Face Conversations Telephone Calls Interviews Verbal Aspects Conversation- talking about various matters of interest to both parties, these are...
  • Verbals and Verbal Phrases - Tracie Wright

    Verbals and Verbal Phrases - Tracie Wright

    Verbals and Verbal Phrases. A gerund is a word that looks like a verb but acts as a noun. It ends in -ing. Ex. Inventing can be dangerous. A gerund phrase includes a gerund plus its modifiers and complements. Ex....