Aufgabenblatt 1

Aufgabe 0

Wenn man das folgende Dreieck

			1
		3	4	9
	2	8	1	6	3
9	3	2	8	7	3	2

von oben nach unten durchläuft, so ist der Pfad von 1 -> 9 -> 6 -> 8 derjenige, welcher die höchste Summe bildet: 24. Von einer Zahl einer Ebene kann auf die Zahl in der darunterliegenden Ebene links, mittig und rechts erreicht werden.

Wie lautet die maximal erreichbare Summe in der Puzzleeingabe?

Lösungskontrolle

Anbei eine Beispiel-Eingabe auf Kursniveau, sowie die erwartete Ausgabe.

Bewertungsgrundlage

Die Bewertung der Abgabe besteht aus den folgenden Punkten, die ihr Lösungsprojekt enthalten muss:

• Eine schriftliche Ausarbeitung als PDF-Dokument in Ihrem GitLab-Projekt:
  • Analyse des Problems. Behandeln Sie die folgenden Punkte:
    • Was macht das Problem kompliziert?
    • Skizzieren Sie, falls möglich, einen naiven brute-force Lösungsansatz und ermitteln seine Laufzeit in O-Notation und seinen Speicherbedarf.
  • Beschreiben Sie ihren Lösungsansatz
    • Beschreiben Sie eingesetzte Algorithmen/Lösungsstrategien und Datenstrukturen. Zitieren Sie Sekundärquellen, die zur Lösung beigetragen haben.
    • Ermitteln Sie die Laufzeit Ihrer Lösung in O-Notation.
    • Messen Sie die Laufzeit Ihres Programms auf einem Laborrechner der Hochschule. Verändern Sie, wenn es die Aufgabenstellung erlaubt, die Eingabegröße und messen Sie erneut.
• Lösung der Problems in einem Projektordner in Ihrem GitLab-Projekt
  • Das ausschließlich von Ihnen allein geschriebene Programm soll die gestellte Aufgabe auf einem gewöhnlichen Laborrechner der Hochschule \textbf{in unter einer Minute Laufzeit lösen}.
  • Das Lösungsprojekt darf nur als Quellcode abgegeben werden.
  • Eine ausführliche Bau- und Ausführanleitung ist zwingender Bestandteil der Abgabe. Legen Sie gegebenenfalls Makefiles oder andere Bauskripte bei. Das Bauen und Ausführen des Lösungsprojekts muss in wenigen Schritten möglich sein und auf einem Laborrechner der Hochschule vorgeführt werden können.
  • Ihr Programm darf nur Ihre Lösung ausgeben. Zusätzliche Ausgabe zu Debuggingzwecken sind aus der Abgabe vorher zu entfernen. Falls Ihr Programm hilfreiche Detailinformationen zur Lösungsfindung ausgeben kann, dokumentieren Sie, wie sie gesondert aktiviert werden kann.

Seien Sie außerdem darauf vorbereitet, Ihr Projekt während des Praktikumstermins vorzustellen und dazu Fragen zu beantworten.

Abgabemodalitäten

Zur Abnahme ist die persönliche Anwesenheit erforderlich. Ihr Lösungsprojekt muss zum Abgabetermin im vorher von Ihnen eingerichtetem persönlichen, privaten GitLab-Projekt abrufbar sein.