Algorithmen, Datenstrukturen und Datenabstraktion W21/22
to Whiteboard Site

Description

Inhalt

  • Analyse von Sortierverfahren: Mergesort, Quicksort, u.a.
  • ADTs Prioritätswarteschlange und Wörterbuch und zugehörige Datenstrukturen: Heaps, Hashing, binäre Suchbäume, B-Bäume, u.a.
  • Algorithmen auf Graphen: Breiten- und Tiefensuche, topologisches Sortieren, minimale Spannbäume, kürzeste Wege.
  • Algorithmen für Mengen von Zeichenketten.
  • Speicherverwaltung.
  • Verschiedene Entwurfstechniken für Algorithmen: teile-und-herrsche, greedy, dynamische Programmierung.
  • Mathematische Analyse von Algorithmen bezüglich ihres Ressourcenbedarfs: Laufzeit, Speicherplatz.

Literatur

  • P. Morin: Open Data Structures, an open content textboox.
  • A. Gogol-Döring, T. Letschert: Algorithmen und Datenstrukturen für dummies, Wiley, 2020
  • M. Dietzfelbinger, K. Mehlhorn, P. Sanders. Algorithmen und Datenstrukturen: Die Grundwerkzeuge, Springer, 2014. (englisch, deutsch)
  • T. H. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms, MIT Press, 2009.
  • R. Sedgewick: Algorithms in Java (Part 1–5), Addison-Wesley, 2003.
  • G. Saake, S. Sattler: Algorithmen und Datenstrukturen, dpunkt.verlag, 2013.
  • M.T. Goodrich, R. Tamassia: Data Structures and Algorithms in Java, Wiley, 2014.
Basic Course Info

Course No Course Type Hours
19300201 Vorlesung 4
19300202 Übung 2

Time Span 19.10.2021 - 31.03.2022
Instructors
Günter Rote

Study Regulation

0084b_k120 2006, BSc Mathematik (Mono), 120 LPs
0084c_k120 2010, BSc Mathematik (Mono), 120 LPs
0086c_k150 2014, BSc Informatik (Mono), 150 LPs
0086d_k135 2014, BSc Informatik (Mono), 135 LPs
0087b_k90 2009, BSc Informatik (Kombi), 90 LPs
0087d_k90 2015, BSc Informatik (Kombi), 90 LPs
0088b_m60 2006, BSc Informatik (Kombi), 60 LPs
0088d_m60 2015, MSc Informatik (Kombi), 60 LPs
0396b_MA120 2015, MSc Wirtschaftsinformatik (Mono), 120 LPs
0496a_MA120 2016, MSc Computational Science (Mono), 120 LPs
0511a_m72 2016, MSc Informatik (Lehramt), 72 LPs
0511b_m72 2019, M-Ed Fach 2 Informatik (Lehramt an Gymnasien - Quereinstieg), 72 LP

Algorithmen, Datenstrukturen und Datenabstraktion W21/22
to Whiteboard Site

Main Events

Day Time Location Details
Tuesday 14-16 T9/Gr. Hörsaal 2021-10-19 - 2022-02-15
Thursday 14-16 T9/Gr. Hörsaal 2021-10-21 - 2022-02-17

Accompanying Events

Day Time Location Details
Monday 10-12 T9/SR 006 Seminarraum David Wellner
Monday 14-16 T9/051 Seminarraum David Wellner
Monday 14-16 T9/053 Seminarraum Übung X03 - findet nicht statt
Monday 16-18 Online https://fu-berlin.webex.com/meet/f.jezuita Fabian Jezuita
Tuesday  8-10 T9/051 Seminarraum Tamara Fischer
Tuesday 10-12 T9/053 Seminarraum David Wellner
Tuesday 10-12 T9/051 Seminarraum Tamara Fischer
Tuesday 12-14 T9/051 Seminarraum Übung X07 - findet nicht statt
Tuesday 12-14 T9/053 Seminarraum David Wellner
Tuesday 16-18 Online https://fu-berlin.webex.com/meet/f.jezuita (urspr. T9/046 Seminarraum) Fabian Jezuita
Tuesday 16-18 T9/049 Seminarraum Übung X10 - findet nicht statt
Wednesday 10-12 Online siehe Ankündigung Sebastian Salokat
Wednesday 12-14 Online siehe Ankündigung Sebastian Salokat
Friday  8-10 T9/SR 006 Seminarraum Übung X11 - findet nicht statt

Algorithmen, Datenstrukturen und Datenabstraktion W21/22
to Whiteboard Site

Most Recent Announcement

2022-02-01:  Klausur 24.2. 14 Uhr online

Die Klausur am Donnerstag 24.2. um 16 Uhr (Korrektur: um 14 Uhr, wie geplant) wird als Online-Klausur stattfinden.

Wir werden voraussichtlich am Mittwoch, den 9.2. von 13-15 Uhr eine technische Probeklausur machen.

Machen Sie sich mit dem Ablauf vertraut, der auf der Wiki-Seite beschrieben ist.



Published by: Günter Rote
Older announcements

2021-11-21
Published by: Günter Rote
Präsenztutorien, Vorgehen bei Corona-Verdacht

Wie Sie wissen, ist die Corona-Lage ernst. Wir wollen die Möglichkeit der Präsenztutorien aufrechterhalten und deshalb gemeinsam die Schutzmaßnahmen konsequent einhalten. Dazu gehört auch, dass Sie bei Auftreten der Covid-typischen Krankheitszeichen die Universität nicht aufsuchen (wie natürlich bei behördlich angeordneter oder selbst auferlegter Quarantäne.) Besuchen Sie in einem solchen Fall als Ersatz eines der Online-Tutorien. Die Netzadressen der Webex-Treffen finden sie bei der Beschreibung der Bereiche, und auch in vergangenen Ankündigungen. Wechseln Sie nicht die Gruppenzuordnung im MyCampus, und geben Sie Ihre Lösungen bei Ihrer angestammten Gruppe ab.

Auch die Tutorinnen und Tutoren halten sich an diese Vorsichtsmaßnahmen; daher kann es vorkommen, dass eine Übungsgruppe kurzfristig online statt in Präsenz stattfindet. Dafür bitte ich um Verständnis.


2021-10-20
Published by: Günter Rote
Auflauf der Übungen: Bewertung und Abgabe

Jeden Dienstag wird ein Übungsblatt ins Netz gestellt (unter Ressourcen); Der Abgabetermin ist Freitag der darauffolgenden Woche, 12:00 Uhr. Die Abgabe erfolgt nach Absprache mit dem Tutor/der Tutorin entweder in das Fach des Tutors im großen Briefkasten in der Takustraße 9, 1. Stock, oder online per MyCampus. Programmieraufgaben werden nur online abgegeben.

Diese Übungsaufgaben müssen in Zweiergruppen mit einem Partner/einer Partnerin aus der gleichen Übungsgruppe bearbeitet werden. (Verwenden Sie das Forum zur Partner*innensuche.) Die Aufgaben sollten dabei von der Gruppe in wirklicher Zusammenarbeit gelöst werden. Jede/r von beiden muss dabei die eingereichten Lösungen verstanden haben und in der Lage sein, sie wiederzugeben. Ein Gedankenaustausch mit anderen Gruppen und das Studium von Lehrbüchern oder Quellen aus dem Internet ist dabei ausdrücklich erlaubt, die Lösungen müssen aber dann selbständig erarbeitet werden. Beim ersten Abschreiben (auch nur einer einzigen Aufgabe) von anderen Gruppen oder anderen Quellen wird der betreffende Übungszettel mit null Punkten bewertet. Im Wiederholungsfall wird die Übung als nicht bestanden bewertet.

Für die Aufgaben, die sie während der Übungsstunden in Kleingruppen bearbeiten, gibt es separate Übungsblätter, die kurz vor den Übungen ebenfalls im Netz stehen. Diese Aufgaben werden nicht bewertet.

  • Für die Bestätigung der aktiven Teilnahme sind notwendig:
    1. mindestens 60 % der Punkte der Übungsblätter.
    2. mindestens 20 % der Punkte auf jedem einzelnen Übungsblatt mit höchstens einer Ausnahme
    3. Teilnahme an den Besprechungen und Diskussionen im Tutorium, oder als Alternative Erstellen eines kreativen Projekts zum Stoff der Veranstaltung (z.B. Gestaltung eines Videos, Simulation und Visualisierung eines Algorithmus).
  • Für die Bestätigung der regelmäßigen Teilnahme ist notwendig:
    • Teilnahme an den Tutorien mit höchstens zwei Ausnahmen

(Das erste Übungsblatt steht schon im Netz, und ebenfalls das Video von der ersten Vorlesung, und zwar unter Syllabus/Lehrplan.)


2021-10-18
Published by: Günter Rote
Ablauf der Veranstaltung Algorithmen, Datenstrukturen und Datenabstraktion

Liebe Studierende,

herzlich willkommen bei der Vorlesung Algorithmen, Datenstrukturen und Datenabstraktion im Wintersemester 2021/22.

Die Lehrveranstaltung (Vorlesung und Übung) wird auf Grundlage der aktuellen Beschlüsse der FU Berlin als Präsenzveranstaltung durchgeführt.

Für Sie als Teilnehmende in Präsenz gelten die 3G-Regeln (geimpft, genesen, oder getestet). Ich selbst bin vollständig geimpft und werde dies auch Ihnen gegenüber nachweisen. Ich werde Ihren 3G-Status vor Beginn jeder Lehrveranstaltung stichprobenweise kontrollieren. Bitte kommen Sie entsprechend ein paar Minuten früher. Der Nachweis eines negativen Tests muss jeweils für die Tage der Vorlesung erfolgen und bei jeder Teilnahme vorgelegt werden (siehe auch Dritte SARS-CoV-2-Infektionsschutzmaßnahmenverordnung in der aktuellen Fassung – https://www.berlin.de/corona/massnahmen/verordnung). Es sind nur Tests zertifizierter Leistungserbringer nach § 6 Absatz 1 der Coronavirus-Testverordnung zugelassen (keine Selbsttest, siehe auch COVID-19-Schutzmaßnahmen-Ausnahmenverordnung – SchAusnahmV – https://www.gesetze-im-internet.de/schausnahmv).

Sie müssen bei Teilnahme zudem auch im Hörsaal eine (neu:) medizinische Maske (oder FFP2-Maske) tragen, da die Mindestabstände unterschritten werden, siehe https://www.fu-berlin.de/sites/coronavirus/faq/campus/. Für die Kontaktverfolgung verwenden wir die Web-Anwendung a.nwesen.de (siehe https://anwesende.imp.fu-berlin.de/ und auch https://www.fu-berlin.de/campusleben/campus/2021/210928-app-anwesenheit/index.html). Bringen Sie dafür ein Smartphone oder einen Laptop mit.

Wir werden den Hörsaal regelmäßig lüften. Bitte wählen Sie Ihre Bekleidung entsprechend aus.

Die Vorlesungen werden mit Kamera aufgenommen und über Webex gestreamt. Hier sind die Zugangsdaten: https://fu-berlin.webex.com/fu-berlin/j.php?MTID=m50ee39bd32fa5a93f9944fe4ec9b2230 Meeting-Kennnummer: 2733 952 1311 Passwort: 2-3-Baum
Überdies gibt es Videos und Folien von der Vorlesung vom letzten Jahr: http://www.inf.fu-berlin.de/lehre/WS20/ALP3/Inhaltsverzeichnis.html. Das soll Teilnehmenden, die nicht in Präsenz teilnehmen können, die Teilnahme ermöglichen. Ich bitte um Nachsicht bei eventuellen technischen Anfangsschwierigkeiten, da ich mit dem System noch keine Erfahrung habe.

Die Klausur wird nach aktuellem Stand als Präsenzprüfung durchgeführt werden.

Bei den Übungen werden Sie in der Übungsstunde Aufgaben unter Anleitung gemeinsam in Kleingruppen diskutieren und bearbeiten, und weitere Übungen zu Hause in Zweiergruppen. Ein Teil der Übungsgruppen findet online statt. Dazu gibt es eine getrennte Ankündigung.

Ich freue mich darauf, Sie am Dienstag, 19.10.21, bei unserer ersten Vorlesung zu begrüßen.

Günter Rote


2021-10-18
Published by: Günter Rote
Organisation der Übungen

Liebe Studierende,

Wir haben 6 Übungsgruppen in Präsenz und 4 Online-Übungsgruppen geplant. Sie können sich ab sofort für die Übungsgruppen anmelden. Die Übungen beginnen nächste Woche, also ab Montag, den 25. Oktober.

Für Teilnehmende in Präsenz gelten die 3G-Regeln (geimpft, genesen, oder getestet). Die Tutoren und Tutorinnen sind vollständig geimpft. Der 3G-Status wird vor Beginn jeder Lehrveranstaltung kontrolliert. Bitte kommen Sie entsprechend ein paar Minuten früher. Der Nachweis eines negativen Tests muss jeweils für die Tage der Vorlesung erfolgen und bei jeder Teilnahme vorgelegt werden (siehe auch Dritte SARS-CoV-2-Infektionsschutzmaßnahmenverordnung in der aktuellen Fassung – https://www.berlin.de/corona/massnahmen/verordnung). Es sind nur Tests zertifizierter Leistungserbringer nach § 6 Absatz 1 der Coronavirus-Testverordnung zugelassen (keine Selbsttest, siehe auch COVID-19-Schutzmaßnahmen-Ausnahmenverordnung – SchAusnahmV – https://www.gesetze-im-internet.de/schausnahmv).

Sie müssen zudem auch in den Seminarräumen eine (neu:) medizinische Maske (oder FFP2-Maske) tragen, da die Mindestabstände unterschritten werden, siehe https://www.fu-berlin.de/sites/coronavirus/faq/campus/. Für die Kontaktverfolgung verwenden wir die Web-Anwendung a.nwesen.de (siehe https://anwesende.imp.fu-berlin.de/ und auch https://www.fu-berlin.de/campusleben/campus/2021/210928-app-anwesenheit/index.html). Bringen Sie dafür ein Smartphone oder einen Laptop mit.

Wir werden die Seminarräume regelmäßig lüften. Bitte wählen Sie Ihre Bekleidung entsprechend aus