Institute for Web Science and Technologies · Universität Koblenz - Landau
Institute WeST
Diese Lehrveranstaltung hat in einem vergangenen Semester stattgefunden oder findet in einem zukünftigen Semester statt. Falls Sie nach aktuellen Veranstaltungen suchen, gehen Sie zur Übersicht der Lehrveranstaltungen.

Proseminar "Sortieralgorithmen"

[zur Übersicht]

Sommersemester 2020

Sortieren von total geordneten Elementen in linearen Datenstrukturen, wie beispielsweise Sortierung eines Arrays aus Matrikelnummern oder einer verlinkten Liste bestehend aus Zeichenketten, ist eine häufig auftretende Aufgabe in vielen Anwendungen. Sortieralgorithmen bieten sich weiterhin als Anschauungsobjekte für verschiedene Programmierparadigmen und als Lernobjekte für Analysemethoden in der Informatik an. In diesem Proseminar lernen Sie, über die in der Vorlesung "Algorithmen und Datenstrukturen" bekannten Sortieralgorithmen (InsertionSort, SelectionSort, MergeSort, QuickSort, HeapSort) hinausgehend, weitere Sortieralgorithmen kennen.

Seminarthemen

Jedes Seminarthema hat einen bestimmten Sortieralgorithmus als Fokus.

Sie können die verlinkten Wikipedia-Artikel als Einstiegspunkte für eine Literaturrecherche benutzen. Es wird erwartet, dass weitere (Original-)Literatur zur Bearbeitung des Themas einbezogen wird.

Termine

Vorbesprechung: 17.02.2020 10:15 (Raum B.016)

Proseminar: Dienstags 10:15-11:45 Uhr (Raum C.209)

Teilnahme

Wenn Sie an dem Proseminar teilnehmen möchten, melden Sie sich bitte bis zum 16.02.2020 unter Nennung Ihrer 3 favorisierten Themen mit einer informellen E-Mail bei PD Dr. Matthias Thimm an. Die finale Themenvergabe findet in einer Vorbesprechung am 17.02.2020, 10:15 Uhr (Raum B.016) statt, für die eine Teilnahme erforderlich ist.

Jeder Teilnehmer erarbeitet im Vorfeld des Proseminars einen Vortrag (30 Minuten Vortragszeit, zzgl. ca. 15 Minuten Diskussion) zum gewählten Thema und hält diesen im gesamten Teilnehmerkreis. Die Präsentation soll der folgender Struktur gehorchen:

  1. Motivation und Einordnung in die Historie
  2. Konkretisierung der Problemstellung (z.B. Formalisierung des vergleichsbasierten Sortierproblems auf linearen Datenstrukturen mit Direktzugriff)
  3. Skizzierung der Algorithmenidee
  4. Beispiele
  5. Formalisierung des Algorithmus (durch Pseudocode oder Programmcode)
  6. Formale Analyse (Korrektheitsbeweis und Laufzeitanalyse, evtl. skizzenhaft an einem Beispiel)
  7. Fazit und Zusammenfassung

Beachten Sie: Die Präsentation hat das Ziel, dass alle Anwesenden die Grundidee des vorgestellten Algorithmus begreifen. Insofern sollten Beispiele den Fokus der Präsentation darstellen.

Am Ende des Proseminars, d.h. am Ende des Sommersemesters 2020, ist eine schriftliche Ausarbeitung abzugeben, die das gewählte Thema auf max. 12 Seiten präsentiert (nutzen Sie für die Ausarbeitungen bitte die LaTeX-Vorlage der LNCS Proceedings Reihe). Die Struktur der Ausarbeitung soll der Struktur der Präsentation folgen, aber dessen Inhalte weiter ausarbeiten.

Bitte beachten Sie bei der Erstellung der Präsentation und der Ausarbeitung folgende allgemeine Richtlinien (nur in Englisch verfügbar): pdf

Lehrende

  • thimm@uni-koblenz.de
  • Institutsleiter (interim)
  • B 108
  • +49 261 287-2715