Algorithmen und Datenstrukturen

Neuigkeiten

  • 12.11.19 - Neues Übungsblatt (02) ist online.
  • 12.11.19 - Folien für Kapitel 03 (Sortieren) sind online.

Archiv

  • Beginn der Vorlesung am Donnerstag, 31. Oktober 2019.
  • Ausgabe erstes Übungsblatt: Donnerstag, 31. Oktober 2019 (1. Vorlesung).
  • Beginn der Übung am Mittwoch, 6. November.
  • 05.11.19 - Neues Übungsblatt (01) ist online.

Organisation

Vorlesungen: Donnerstag, 17:15 - 18:45, Raum 46-110, ab 31.10.2019

Übungen: Mittwoch, 8:15 - 9:45, Raum 46-260, ab 06.11.2019

Abgabe der Übung: Montag Abend

  • Theorie: Übungskasten 4. Stock zwischen 32 & 34
  • Praxis: Upload in Exclaim

Organisation der Übung und Zulassung: siehe unten

KIS-Eintrag

Dozent

Dr. rer. nat. Patrick Michel

Tutorin

Danielle Korth

Inhalt

Implementierung und Verwendung grundlegender Datenstrukturen und ihrer Operationen. Algorithmus Begriff und grundlegende Algorithmen auf Datenstrukturen. Verständnis von Zeit- und Platzbedarf eines Verfahrens / einer Operation. Verwendung von Sortier- und Suchverfahren für den Zugriff auf Anwendungsdaten. Rekursive Programmierung, Modellierung mit Graphen, etc.

(siehe auch Modulhandbuch)

Anmeldung

Zur Übung müssen sich alle Studenten anmelden. Hierzu verwenden wir das Exclaim System, das auch für die Abgabe der praktischen Übungen genutzt wird.

Vorlesungsmaterial

Hier sind die Folien und andere Materialen aus der Vorlesung verfügbar.

No. Kapitel Normal 2 auf 1 Kommentare
 Organisatorisches PDF PDF
01 Algorithmen – Grundlagen PDF PDF
02 Komplexitätsanalyse PDF PDF
03 Sortieren PDF PDF

Hier sind die Quelldateien für das AlgoDat System, die in der Vorlesung geschrieben/präsentiert wurden. Wenn nicht anders angeben liegen die Dateien im package exercise/lecture und damit im Pfad app/exercise/lecture im System.

Kapitel Datei Kommentar
01 Euklidischer_Algorithmus.java
02 Lineare_Suche.java

Übungsmaterial

Hier sind die Übungsblätter und die dazu notwendige Materialien.

Blatt Abgabe Material Kommentare
Blatt 00 04/06.11. algodat-v1 “Hinweise zu den Praktischen Übungen” unten beachten!
Blatt 01 11/13.11. algodat-v2 “Neue Übungsmaterialien pro Blatt” unten beachten!
Blatt 02 18/20.11. algodat-v2.1 Nur UI neu (Ordner public), V2.1

Übungen und Zulassungsvoraussetzung

Die Übungsblätter werden wöchentlich ausgegeben, wenn möglich schon vor der Übung am Mittwoch, spätestens aber zur Vorlesung am Donnerstag. Sie sind in Gruppen zu bearbeiten und im Laufe des Montags abzugeben.

  • Theoretische Aufgaben werden auf Papier in den Übungskasten im vierten Stock zwischen Gebäude 34 und 32 abgegeben.
  • Praktische Aufgaben sind in den vorbereiteten Quelldateien zu ergänzen und online im Exclaim System hochzuladen.

Die praktischen Aufgaben werden vom Abgabesystem übersetzt und geprüft; Akzeptiert werden nur Abgaben die auch übersetzt werden können. Der Tutor gibt im Laufe des Dienstags Feedback zu den hochgeladenen Aufgaben.

Bis zur Übung am Mittwoch können die praktischen Aufgaben weiter bearbeitet und verbessert werden. In der Übung werden theoretische und praktische Teile gemeinsam besprochen und Gruppen können im Anschluss Verbesserungen ihrer Lösungen vom Tutor abnehmen lassen.

Um zur Klausur zugelassen zu werden müssen alle bis auf zwei Übungsblätter sinnvoll bearbeitet werden. Das bedeutet, dass alle Aufgaben von der Gruppe bearbeitet wurden und in entscheidenden Teilen korrekt gelöst wurden. Der Tutor entscheidet ob die theoretische und praktische Abgabe diese Kriterien erfüllen und trifft die Entscheidung spätestens nachdem die Gruppe nach der Übung am Mittwoch Gelegenheit hatte weitere, laufende Lösungen vorzuführen.

Hinweise zu den Praktischen Übungen

In den praktischen Übungen sollen Sie die zum Download bereit gestellten Quellen ergänzen und zur Abgabe ins Exclaim System hochladen. Damit Exclaim die Abgabe übersetzen kann, dürfen Sie weder die Klasse umbennen, noch die öffentlichen Methoden, noch die Klasse in ein anderes Paket verschieben.

Sie dürfen gerne neue öffentliche Methoden hinzufügen (um diese über die Oberfläche zum Testen zu verwenden) oder Hilfsmethoden zur Strukturierung Ihres Codes!

  • Zur Abgabe laden Sie für jede Aufgabe getrennt die Klasse der Aufgabe in das System. Sollten Sie Hilfsklassen verwenden oder auf späteren Blättern sonst weitere Klassen zur Lösung notwendig sein, müssen Sie diese ebenfalls hochladen. Insbesondere müssen Sie keine sonst zur Verfügung gestellten Klassen (wie Person, etc.) hochladen!

  • Zur Bearbeitung der Aufgaben können Sie einen beliebigen Text Editor verwenden, wir empfehlen Ihnen aber eine Entwicklungsumgebung wie IntelliJ Idea oder Eclipse. Beide sind in kostenlosen Versionen verfügbar.

  • Schließlich brauchen Sie ein Java 8 JDK (z.B. von Oracle oder ein OpenJDK). Unter Windows kann das JDK in Version 8 schwer zu bekommen sein; sollten Sie Probleme damit haben melden Sie sich bitte per E-Mail! Nach Installation des JDK stellen Sie sicher, dass der Java Interpreter und der Java Compiler im Pfad sichtbar sind: Führen Sie in einem Terminal die beiden Befehle java -version und javac -version aus und überprüfen Sie die ausgegebene Version (bzw. das beide Befehle überhaupt verfügbar sind).

  • Das AlgoDat-System: In der ZIP-Datei von Blatt 00 befindet sich das in der Vorlesung gezeigte System. Wenn Sie ein Java 8 JDK installiert haben und sich beide oben genannten Befehle ausführen lassen, dann können Sie das System starten, indem Sie ./sbt run im Terminal eingeben (Linux / Mac OS X) oder den Befehl sbt.bat run ausführen (Windows). Geben Sie nur ./sbt bzw. sbt.bat ein, landen Sie in der SBT-Shell und können von dort mit der Eingabe run das System starten.

Beim allerersten Start brauchen Sie eine Internet Verbindung und etwas Geduld, da alle nötigen Bibliotheken und Quellen für das System automatisch heruntergeladen und lokal installiert werden. Ist dieser Vorgang einmal abgeschlossen ist er für den Rest des Semesters nicht mehr notwendig!

Solange das System läuft, können Sie:

  • Unter der URL http://localhost:9000 auf die UI zugreifen und damit arbeiten.
  • Ändern Sie etwas im Code der aktuellen Aufgabe und führen dann eine Methode über die UI aus, wird Ihr Code im Terminal automatisch übersetzt und ausgeführt. Auf der UI sehen Sie entweder das Ergebnis der Ausführung oder den Fehler beim Übersetzen.
  • Sie können das System im Hintergrund laufen lassen, da es im Leerlauf keine Last erzeugt.

Tipp: Sie können ein integriertes Terminal in Ihrer IDE benutzen, um von dort das System zu starten und brauchen damit nicht ein weiteres Fenster im Hintergrund zu verwalten.

Alternativ zum AlgoDat-System können Sie die Übungsaufgaben auch manuell (oder in Ihrer IDE) übersetzen und durch eine main Methode testen. Führen Sie dazu im app Ordner Befehle wie javac exercise/sheet_00/Sortierung.java aus, gefolgt von einem passenden java Kommando zum Ausführen Ihrer main. In diesem Fall sind nur die beiden Ordner exercise und model (enthalten im app Order) relevant, die Sie hier für Blatt 00/01/02 separat herunterladen können.

Neue Übungsmaterialien pro Blatt

Für jedes Übungsblatt gibt es neue Quelldateien für die Übungen und oft auch ein Update zum AlgoDat-System, mit neuen Funktionen und/oder behobenen Fehlern in der Anwendung. Für Blatt 02, zum Beispiel, finden sie alles notwendige im Archiv algodat-v2.1.

Das jeweils neue Archiv für ein Übungsblatt enthält diese Unterschiede zur jeweiligen Vorgängerversion:

  • Die Quelldateien des aktuellen Übungsblatts XY im Ordner app/exercise/sheet_XY.
  • Die aktuelle Version der Oberfläche (UI) im Ordner public.
  • Die aktuelle Version des Backends (Servers) im Ordner app/controllers bzw. conf.

Sie können also entweder diese vier Ordner jeweils in Ihrem bestehenden Projekt ersetzen oder mit dem entpackten Ordner des Übungsblatts neu anfangen (und Ihren alten app/exercise Ordner übernehmen). In beiden Fällen fällt das initiale Herunterladen weg und das System sollte deutlich schneller starten.

Ob Sie das System in der aktuellen Version des Übungsblatts betreiben, sehen Sie auf der Seite unten rechts (ab V2): Hier sollte unter anderem die (Major-)Version der Oberfläche mit der des Backends übereinstimmen. Sie brauchen jeweils nur die neuste Version des Systems und sie sollte mit allen Vorlesungs- und Übungsquellen abwärtskompatibel sein.