FH Graubünden PH Graubünden

Zeitplan beim Kochen

Algorithmisches Denken in der Primarschule

Zusammenfassung

Planung ist alles! Wir kennen die Situation alle gut: Beim Mittagessen in der Mensa kann es kaum schnell genug gehen. Viele Leute drängeln sich und stehen in Schlangen vor der Essensausgabe. Die meisten von uns kennen die Situation nur aus der Perspektive der Gäste. In dieser Unterrichtseinheit versetzen wir uns in die Lage eines Restaurants, das mit einem grossen Besucherandrang zu kämpfen hat. Im Verlaufe der Übung werden Sie verschiedene Techniken entdecken, die es Ihnen erlauben, sonst sehr zeitintensive Aufgaben schneller zu erledigen. Die Idee beruht auf dem Konzept der Problemzerlegung: mit mehreren Leuten lässt es sich bequem parallel arbeiten, was (mit einem guten Plan) die Arbeit wesentlich beschleunigen kann.

Ziel dieser Unterrichtseinheit ist es, dass die Lernenden sich verschiedener Mechanismen bewusst werden, die es erlauben, Arbeit in parallelen Teilen schneller zu erledigen. Das zugrundeliegende Konzept nennen wir Scheduling (der Begriff kommt aus dem Englischen und bedeutet auf Deutsch Zeitplanerstellung). Dabei werden verschiedene Algorithmen analysiert und evaluiert. Die Evaluation dient dazu, sich über die Vor- und Nachteile der verschiedenen Algorithmen klar zu werden.

Beispielsequenz

Walter führt in einem kleinen Bistros am See das Restaurant. Er liebt es, andere Leute mit seinen selbstgemachten Köstlichkeiten zu verwöhnen. Auf dem Speiseplan stehen die folgenden Speisen, deren Herstellung jeweils unterschiedlich lange dauert:

Walter ist kein Fan von Multitasking, weshalb er zuerst ein Gericht fertigkochen will bevor er das nächstes beginnt. Aber leider bildet sich vor dem Bistro langsam eine Schlange mit hungrigen Menschen wie in Abbildung 1 dargestellt.

.image2.png.
Abbildung 1. Die Schlange vor dem Bistro

Aufgabe 1

Wie lange dauert es, bis Walter die Wünsche aller Gäste erfüllen kann?

Ab jetzt wird parallelisiert

Auweia! Einige der Kunden wollen nicht mehr länger warten und haben sich entschlossen, stattdessen zur Konkurrenz zu gehen... Walter überlegt sich eine neue Strategie: Anstatt selbst zu kochen, sammelt er alle Bestellungen und stellt seine Neffen Tim, Tom und Teddy an, die ihn in er Küche unterstützen sollen. Zu dritt sollte das Kochen massiv beschleunigt werden; die drei Brüder arbeiten parallel und können jeweils drei Gerichte gleichzeitig kochen. Sie einigen sich darauf, dass Tim alle Lasagnen, Tom alle Makkaroni und Teddy alle Kebabs übernehmen wird.

.image3.png.
Abbildung 2. Tim, Tom und Teddy sind die hilfsbereiten Küchenassistenten

Aufgabe 2

Wie lange dauert es, bis Tim, Tom und Teddy gemeinsam die Wünsche aller Gäste erfüllt haben?

Aufgabe 3

Wir berechnen nun, um wie viele Minuten sich die Kochzeit dank der Hilfe von Tim, Tom und Teddy beschleunigt. Bestimmen Sie für die Bestellungen

wie viele Minuten jeweils gespart werden.

Was fällt Ihnen auf hinsichtlich Arbeitsteilung zwischen Tim, Tom und Teddy?

Aufgabe 4

Walter fällt auf, dass Tim mit seiner Lasagne oftmals länger beschäftigt ist als Tom mit seinen Makkaroni. Finden Sie eine Bestellung, in welcher Tim früher fertig ist als Tom. Versuchen Sie anschliessend eine allgemeine Regel zu finden, ab wie vielen bestellten Portionen Makkaroni Tom länger beschäftigt ist als Tim mit seiner Lasagne.

Aufgabe 5

Tim behauptet, zu dritt seien sie immer schneller als Walter alleine. Stimmt diese Behauptung? Wenn ja, begründen Sie bitte; wenn nein, suchen Sie ein Beispiel, bei dem die drei Brüder gleich lange beschäftigt sind wie Walter allein.

Eine neue Strategie

So viele Kunden und allen wollen sie dasselbe: Lasagne. Tim bereut, dass er sich für dieses Rezept gemeldet hat – seine Brüder sitzen schmunzelnd neben dem Herd und machen gar nichts. Nicht fair! Walter beschliesst, dem armen Jungen zu helfen und verkündet: Wir verteilen die Bestellungen nun fairer auf euch drei – es soll niemandem langweilig werden! Walter schlägt vor, dass Bestellungen entgegengenommen werden und jeder der drei Brüder sich reihum um einen Teil der Bestellungen kümmert. Tim nimmt die Bestellungen von Kunde 1, 4, 7,... entgegen. Tom übernimmt die Bestellungen von Kunde 2, 5, 8,... und Teddy erhält alle Bestellungen von Kunde 3, 6, 9,...

.image4.png.
Abbildung 3. Hoffentlich bald eine bessere Arbeitsaufteilung...

Aufgabe 6

Die Bestellungen

kommen in gegebener Reihenfolge in die Küche. Wie lange sind Tim, Tom und Teddy jeweils mit Kochen beschäftigt?

Aufgabe 7

Entwerfen Sie eine Bestellung, die die Aufträge möglichst schlecht auf die drei Brüder verteilt.

Aufgabe 8

Wie schlimm kann die Verteilung maximal werden? Wie viel mehr Arbeit kann einer der drei Jungs maximal haben als die anderen beiden bei einer Bestellung mit 12 Gerichten? Finden Sie eine generelle Aussage, unabhängig von der der Anzahl Gerichte?

Eine noch fairere Verteilung

Walter behauptet, er habe eine noch bessere Strategie gefunden, um die drei Jungs möglichst fair mit Aufträgen zu versorgen: Er schlägt vor, die Bestellungen nach den Gerichten zu ordnen (zuerst alle Lasagnen, dann alle Makkaroni, zuletzt alle Kebabs) und diese dann wieder der Reihe nach auf die drei Jungs zu verteilen. So sei garantiert, dass niemand ausschliesslich lange Aufträge habe, während ein anderer nur kurze Aufträge habe.

Beispiel: Die Bestellung «LMKMLKKMM» wird sortiert in die folgende Reihenfolge: LLMMMMKKK, die dann wie folgt auf die drei Brüder verteilt wird: Tim (LMK), Tom (LMK), Teddy (MMK):

.image5.png.
Abbildung 4. Hoffentlich bald eine bessere Arbeitsaufteilung...

Aufgabe 9

Ermitteln Sie für die Bestellungen

wie lange Tim, Tom und Teddy jeweils beschäftigt sind und vergleichen Sie dies mit der Zeit, die die drei mit der vorherigen Strategie in Aufgabe 6 benötigt haben, um dieselben Bestellungen zu bewältigen.

Aufgabe 10

Finden Sie die schlimmstmögliche Bestellung bestehend aus 6 Gerichten, die dazu führt, dass einer der Jungs mehr arbeiten muss als die anderen beiden und vergleichen Sie diesen Wert mit dem Resultat aus Aufgabe 8.

Lösungen zu den Aufgaben

Aufgabe 1

Die Bestellungen übersetzen sich zu \(45+15+5+15+45+5+5+15+15+15+45+5 = 230\) Minuten. Das entspricht insgesamt fast vier Stunden. Das ist viel zu lange für die Gastronomie.

Aufgabe 2

Mit Tim, Tom und Teddy können wir die Arbeit nun parallelisieren. Tim erhält alle Lasagne-Jobs (wovon es im Beispiel drei gibt, aufsummiert dauert es somit 135 Minuten), Tom erhält alles Makkaroni (wovon es fünf gibt, 75 Minuten insgesamt), und Teddy übernimmt alles Kebabs (wovon es ebenfalls fünf gibt, 25 Minuten). Da die drei Brüder alle parallel arbeiten, sind sie nach insgesamt 135 Minuten fertig. Sie brauchen also exakt so lange, wie Tim für die Zubereitung der drei Lasagnen benötigt.

Aufgabe 3

Wir erhalten folgende Tabelle:

Bestellungen Zeit (Walter) Zeit (Tim, Tom, Teddy) Unterschied
LMMLMLKKKMMK 230 Minuten 135 Minuten 95 Minuten
KMLLMLMKKLMKK 265 Minuten 180 Minuten 85 Minuten
KKKLMLMMMMKK 190 Minuten 90 Minuten 100 Minuten

Es fällt auf, dass nur wenige Lasagne-Bestellungen schon ausreichen, dass Tim mit deren Zubereitung zum Flaschenhals wird. Haben alle drei ähnlich viele Bestellungen (was in diesen drei Beispielen der Fall ist), entstehen grosse Wartezeiten. Dies stammt daher, dass Tim für die Zubereitung einer Lasagne sehr viel länger braucht als seine zwei Kollegen bei deren Gerichten. Wir beobachten, dass in diesen drei Beispielen die Bestellungen grundsätzlich recht fair auf die drei Freunde verteilt werden (keiner der drei hat massiv mehr oder weniger Bestellungen). Diejenige Situation welche in dieser Hinsicht am Extremsten ausfällt, ist die Aufgabe c, in welcher nur %% DK c? zwei Bestellungen Lasagne gemacht werden im Gegensatz zu je fünf Bestellungen Makkaroni und Kebap. Betrachten wir die Auswertung, so sehen wir, dass gerade diese Situation besonders zeiteffizient zu sein scheint.

Aufgabe 4

Eine mögliche Bestellung in der Tim schneller fertig ist als Tom ist die folgende: LMMMM Generell können wir sagen, dass in der Zubereitungszeit jede Portion Lasagne 3 Portionen Makkaroni entspricht. Falls es also mehr als dreimal so viele Makkaroni-Bestellungen gibt als Lasagnen-Bestellungen, wird Tom länger beschäftigt sein als Tim.

Aufgabe 5

Tims Aussage ist falsch. Es kann vorkommen, dass sie gleich lange beschäftigt sind wie Walter es allein wäre, wenn die Bestellungen sehr einseitig ausfallen und nur einer von drei Jungen arbeiten kann während die anderen beiden warten. Beispiele wo dies der Fall ist, sind:

Aufgabe 6

Wir erhalten die folgende Tabelle.

Bestellungen Zeit Tim Zeit Tom Zeit Teddy
LMLMLMKKMKLMKKM LMKKK (75 min) MLKLK (115 min) LMMMM (105 min)
MMLLMMMLMKKMLML MLMKL (125 min) MMLKM (95 min) LMMML (135 min)
LMMLKKLMKKKKKKK LLLKK (145 min) MKMKK (45 min) MKKKK (35 min)

Aufgabe 7

Wir erhalten folgende Tabelle:

Bestellung Zeit Tim Zeit Tom Zeit Teddy
LKKLKKLKKLKK LLLL (180 min) KKKK (20 min) KKKK (20 min)

Aufgabe 8

Da alle drei Arbeiter jeweils vier Aufträge entgegennehmen können, ist die kleinstmögliche Aufgabe KKKK für zwei der Arbeiter (dafür benötigen sie \(4 · 5=20\) Minuten). Der längstmögliche Auftrag mit vier Bestellungen ist LLLL was insgesamt \(4 · 45=180\) Minuten dauert. Generell ist die schlechtest-mögliche Aufteilung jene, die den einen Arbeiter voll auslastet und alle anderen Arbeiter minimal auslastet. Eine Lasagne-Bestellung entspricht jeweils 9 Kebab-Bestellungen. Somit kann der Unterschied zwischen dem am stärksten und schwächsten ausgelasteten Arbeiter nie mehr als Faktor 9 ausmachen.

Aufgabe 9

In Aufgabe 6 haben wir die folgenden Zeiten beobachtet:

Bestellungen Zeit Tim Zeit Tom Zeit Teddy
LMLMLMKKMKLMKKM LMKKK (75 min) MLKLK (115 min) LMMMM (105 min)
MMLLMMMLMKKMLML MLMKL (125 min) MMLKM (95 min) LMMML (135 min)
LMMLKKLMKKKKKKK LLLKK (145 min) MKMKK (45 min) MKKKK (35 min)

Für die Bestellung LMLMLMKKMKLMKKM (sortiert: LLL LMM MMM MKK KKK) erhalten wir die folgenden Resultate (schlechter als zuvor):

Zeit Tim Zeit Tom Zeit Teddy
LLMMK (125 min) LMMKK (85 min) LMMKK (85 min)

Für die Bestellung MMLLMMMLMKKMLML (sortiert: LLL LLM MMM MMM MKK) erhalten wir die folgenden Resultate (gleich wie zuvor):

Zeit Tim Zeit Tom Zeit Teddy
LLMMM (135 min) LLMMK (125 min) LMMMK (95 min)

Für die Bestellung LMMLKKLMKKKKKKK (sortiert: LLL MMM KKK KKK KKK) erhalten wir die folgenden Resultate (besser als zuvor):

Zeit Tim Zeit Tom Zeit Teddy
LMKKK (75 min) LMKKK (75 min) LMKKK (75 min)

Aufgabe 10

In diesem System ist es nicht mehr möglich, gleich schlechte Verteilungen zu erstellen wie zuvor in Aufgabe 8. Übrig bleibt noch, die Aufträge so zu verteilen, dass einer der Jungs langwierigere Aufgaben erhält, während die anderen Jungs die jeweils nächstschnelleren Kategorien zugeordnet bekommen. Ein Beispiel, bei dem dies der Fall ist, ist:

LMMMKK

In dieser Aufgabe erhält Tim die Aufträge (LM), während Tom und Teddy beide die Aufträge (MK) zugewiesen erhalten.

Didaktischer Kommentar

Algorithmisches Denken bedeutet, sich Lösungswege für gegebene Problemstellungen zu überlegen, diese zu evaluieren und schrittweise zu verbessern. In dieser Unterrichtseinheit werden die Lernenden mit einem typischen Scheduling-Problem konfrontiert: Mehrere Arbeiten prasseln auf ein System ein und dieses soll die Aufgaben möglichst schnell erledigen. Besteht das System nur aus einem einzigen Arbeiter, kann die Gesamtdauer nicht reduziert werden. Stehen allerdings mehrere Arbeiter zur Verfügung, lassen sich die Aufträge auf die Arbeiter verteilen und parallel bearbeiten. Im Optimalfall kann so die Gesamtbearbeitungsdauer gleichmässig auf die Anzahl Arbeiter verteilt werden. Zum Erreichen des Optimums ist es sehr zentral, wie die Arbeiten auf die einzelnen Arbeiter verteilt werden. In dieser Unterrichtseinheit werden verschieden Verteilungsmöglichkeiten ausprobiert und analysiert.

Die Unterrichtseinheit enthält die folgenden Aspekte des algorithmischen Denkens.

Zurück PDF Übungen als PDF