Anforderungen an ein Löseverfahren

Das Problem

Wir bearbeiten weiterhin das folgende Suchproblem:

Gegeben sind eine Reihe von Schachteln, in denen sich jeweils eine nicht bekannte Menge Gold befindet.

Gesucht ist die Schachtel, in der sich die größte Goldmenge befindet. Wenn es mehrere Schachteln mit der größten Goldmenge gibt, dann reicht es, eine der Schachteln zu bestimmen.

Zur Vefügung steht eine Vergleichswaage, mit der man das Gewicht von zwei Schachteln vergleichen kann.

Beschreibung eines Löseverfahren - Version 1

Hier ein erster Versuch, ein Verfahren zur Lösung des Problems zu formulieren:

Sortiere die Schachteln nach aufsteigendem Gewicht.
Die Schachtel mit dem größten Gewicht liegt dann ganz rechts.

Aufgabe 1

Erläutere die Schwierigkeit bei dieser Verfahrensbeschreibung.

Beschreibung eines Löseverfahren - Version 2

Hier ein zweiter Versuch, ein Verfahren zur Lösung des Problems zu formulieren:

Bei 3 Schachteln geht das so: 
Lege Schachtel A  und Schachtel B auf die Waagschalen.
Wenn Schachtel B leichter als Schachtel A ist, dann
    lege Schachtel B in die Ablage und
	lege Schachtel C auf die freie Waagschale
	Wenn Schachtel C leichter als Schachtel A ist, dann
	    Schachtel A ist die mit der größten Goldmenge
	sonst
	    Schachtel C ist die mit der größten Goldmenge
sonst
    lege Schachtel A in die Ablage und
	lege schachtel C auf die freie Waagschale
	Wenn Schachtel C leichter als Schachtel B ist, dann
	    Schachtel B ist die mit der größten Goldmenge
	sonst
	    Schachtel C ist die mit der größten Goldmenge

Aufgabe 2

Erläutere kurz den großen Nachteil, den diese Verfahrensbeschreibung hat.

Beschreibung eines Löseverfahren - Version 3

Hier ein erneuter Versuch, ein Verfahren zur Lösung des Problems zu formulieren:

Lege Schachtel A und Schachtel B auf die Waagschalen.
Wenn Schachtel B leichter als Schachtel A ist, dann
    lege Schachtel B in die Ablage und
	lege Schachtel C auf die freie Waagschale
	Wenn Schachtel C leichter als Schachtel A ist, dann
	    lege Schachtel C in die Ablage und
	    lege Schachtel D auf die freie Waagschale
		Wenn Schachtel D leichter als Schachtel A ist, dann
	        lege Schachtel D in die Ablage und
	        lege Schachtel E auf die freie Waagschale
			...
sonst
    lege Schachtel A in die Ablage und
	lege schachtel C auf die freie Waagschale
	Wenn Schachtel C leichter als Schachtel B ist, dann
	    lege Schachtel C in die Ablage
		lege Schachtel D auf die freie Waagschale
	    ...

Aufgabe 3

Vergleiche diese Verfahrensbeschreibung mit der voherigen. Erläutere, was sie besser macht. Erläutere auch die Nachteile dieser Verfahrensbeschreibung.

Beschreibung eines Löseverfahren - Version 4

Hier ein weiterer Versuch, ein Verfahren zur Lösung des Problems zu formulieren:

Aufgabe 4

Auch diese Verfahrensbeschreibung hat einen entscheidenden Nachteil. Erläutere kurz und mache einen Verbesserungsvorschlag.

Strukturierung: Der Algorithmus-Begriff

Du hast auf der Seite Ein Suchproblem eine Verarbeitungsvorschrift formuliert und dabei besonders darauf geachtet, dass sie möglichst genau ist. Solche genauen Vorschriften nennt man Algorithmen und sie bilden eine wesentliche Grundlage für Computerprogrammen.

In diesem Abschnitt hast du an vier Beispielen gesehen, wie ein Algorithmus nicht aufgebaut sein sollte. Daraus lassen sich vier Anforderungen für Algorithmen ableiten: Algorithmen sollen ausführbar, eindeutig, endlich und (in der Regel) allgemein sein.

Aufgabe 5

Halte das Gelernte in diesem Wissensspeicher fest:

• Formuliere dabei in der obersten Box eine Definition für den Begriff „Algorithmus“.
• Trage in den weiteren Boxen links ein, was man unter der jeweiligen Anforderung versteht. Schau dafür ggf. noch einmal nach, wo jeweils das Problem bei den verschiedenen Versionen auf dieser Seite lag.
• In den grauen Boxen sind Gegenbeispiele gegeben, bei denen die entsprechende Eigenschaft nicht erfüllt ist. Erkläre jeweils kurz, worin das Problem besteht.