ETH - EducETH - "Greedy" und "Teile und Herrsche" (Leitprogramm)

Inhalt
In der Informatik können verschiedene Lösungsansätze oft auf einen gemeinsamen Nenner gebracht werden. In diesem Leitprogramm werden zwei Methoden vorgestellt, mit denen Algorithmen für unterschiedliche Probleme entworfen werden können.

Dauer
ca. 8 Lektionen

Erforderliches Vorwissen

Grundlegende Programmierkenntnisse.
Die Lösungen für die Programmieraufgaben sind in Java geschrieben. Bei einigen Aufgaben müssen die Lernenden bestehendem Java Code ergänzen. Sie sollten deshalb Variablen, Schleifen, Kontrollstrukturen und Arrays kennen.
Kenntnis der Begriffe Menge und Funktion.

Download

Leitprogramm (PDF, 2.9 MB)

Daten zur Unterrichtseinheit

Schlagwörter

Greedy, Teile und Herrsche, Algorithmen, divide and conquer, Leitprogramm, Rucksackproblem, knapsack problem, minimaler Spannbaum, Minimum Spanning Tree, Algorithmus von Kruskal, Handelsreisender, Travelling Salesman, Binäre Suche, Binary Search, Merge Sort, nächste Nachbarn, Nearest Neighbours, Java

Schultyp, Schulstufe

Gymnasium, Fachhochschule

Sprache

deutsch

Entstehung der Unterrichtseinheit

September 2005

Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.

Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to a newer browser.
More information