Gierige Methoden | MathePrisma

Gierige Methoden

Allgemein

Sudokus

Wechselgeld

Allgemein

Codes

Arbeitsblatt

Aufgabe 1

a) Wir betrachten einen Münzsatz mit 5 Münzen mit den Werten

w(1) = 16, w(2) = 8, w(3) = 4, w(4) = 2, w(5) = 1.
Zeige, dass die gierige Strategie für das Wechselgeldproblem hier stets eine minimale Zahl von Münzen ergibt.
b) Verallgemeinere die Untersuchung von a) für den Fall, dass n Münzen mit den Werten

$w(1) = b^{n-1}, w(2) = b^{n-2}, ..., w(n-1) = b^{1}, w(n) = b^{0}$

vorliegen. Dabei ist $b$ eine ganze Zahl $\geq 2$ .

Aufgabe 2

Man kann jeden Bruch $\displaystyle \frac{p}{q}$ mit $1\leq p \leq q$ als sog. ägyptischen Bruch darstellen, d.h.

$\frac{p}{q} = \frac{1}{q_1} + \frac{1}{q_2} + ... + \frac{1}{q_n}.$

Dabei sind die Nenner $q_i$ paarweise verschiedene natürliche Zahlen. Die Anzahl $n$ der Glieder hängt von $p$ und $q$ ab.
a) Beschreibe einen auf einer gierigen Strategie beruhenden Algorithmus, welcher für gegebenes $p$ und $q$ die Nenner $q_i$ in der Darstellung als ägyptischer Bruch bestimmt.
b) Wie lauten hier die Eigenschaften der gierigen Wahl und der optimalen Teilstruktur?

Aufgabe 3

Auf einer sehr langen Autofahrt (z.B. von Wuppertal nach Wladiwostok) soll möglichst selten zum Tanken angehalten werden. Die Tankstellen entlang der Strecke sind mit T(i) durchnummeriert. Folgendes ist bekannt:

Das Auto besitzt den konstanten Benzinverbrauch v.
Tankstelle T(i) befindet sich an Streckenkilometer d(i)..
Der Tank besitzt einen Inhalt I.

a) Beschreibe eine gierige Strategie zur Lösung dieser Aufgabe.
b) Wie lauten hier die Eigenschaften der gierigen Wahl und der optimalen Teilstruktur?

Aufgabe 4

a) Führe alle Schritte des Huffman-Algorithmus für den nachstehenden Zeichensatz mit den angegebenen Häufigkeiten aus:

	Zeichen z	a	i	o	l	k	n	t
	h(z)	11	6	5	9	3	4	4

b) Gib mit dem in a) berechneten Codierungsbaum die Codierungen für die Wörter "koala", "aioli" und "koalition" an.

c) Wie groß ist die gewichtete externe Pfadlänge des Codierungsbaums aus a)?

Aufgabe 5

Beim Nachweis der Eigenschaft der gierigen Wahl auf der Seite Huffman-Codes 4 hatten wir einen optimalen Codierungsbaum so umgebaut, dass die Zeichen z1 und z2 Geschwister in maximaler Tiefe wurden. Wenn sie das nicht schon vor dem Umbau waren, müssen einige Zeichen mit genau den gleichen Häufigkeiten wie z1 und z2 vorkommen. Welche (Blätter in dem angegebenen Codierungsbaum) sind das?

Drucken

Das Wechselgeldproblem ist ein Beispiel für ein Optimierungsproblem. Gerade solche Probleme kann man oft mit einer gierigen Strategie lösen.

Voraussetzung

Das Optimierungsproblem lässt sich durch eine Folge von Entscheidungen lösen.

Beispiel

(bewege die Maus über das Geld ...)

Und dabei soll die Problemstellung zwei für eine gierige Strategie grundlegende Eigenschaften aufweisen:

weitere Voraussetzungen

Die Eigenschaft der gierigen Wahl:
Die Lösung des Optimierungsproblems kann dadurch erreicht werden, dass jede Entscheidung auf Grund eines lokalen Optimalitätskriteriums getroffen wird.
Die Eigenschaft der optimalen Teilstruktur:
Die Lösung des Optimierungsproblems 'enthält' Lösungen zu Optimierungsaufgaben zu Teilproblemen (vom gleichen Typ wie das Ausgangsproblem).

Beispiel

Die Eigenschaft der gierigen Wahl braucht man, damit überhaupt klar ist, was in jedem Schritt eine gierige Entscheidung darstellt.
Die Eigenschaft der optimalen Teilstruktur braucht man um nachzuweisen, dass die gierige Strategie tatsächlich zu einer Lösung der globalen Optimierungsaufgabe führt. Dieser Nachweis muss allerdings für jede Aufgabenstellung jeweils separat geführt werden.

Schau dir den Beweis der Korrektheit der gierigen Strategie bei der Wechselgeldaufgabe unter diesen Gesichtspunkten nochmals an.

Bei welchen Beobachtungen haben wir zur Begründung die Eigenschaft der gierigen Wahl verwendet?

1. Beobachtung, Begründung für die x(i)
1. Beobachtung, Begründung für die y(i)
2. Beobachtung
3. Beobachtung

Und für welche die Eigenschaft der optimalen Teilstruktur?

1. Beobachtung, Begründung für die x(i)
1. Beobachtung, Begründung für die y(i)
2. Beobachtung
3. Beobachtung