3. Studiensemester

2 Pflicht-Präsenz(en)

Einsendeaufgabe(n)

Pflichtchat(s)

Allgemein

Lerngebiet:
Informatik: Algorithmen und Datenstrukture
Niveaustufe:
Bachelor
Studiensemester:
3
Kreditpunkte:
5 cp
Status:
Pflichtmodul
Häufigkeit des Angebotes:
Nur einmal im Jahr
Lehrsprache:
Deutsch
Lehrende:
Prof. Dr. Günter Totzauer

Teilnahmevoraussetzungen

Obligatorische:
Mathematische Grundlagen, Programmieren

Modulinhalte

Das Studienmodul gibt eine Einführung in das Fach Algorithmen und Datenstrukturen. Das Ziel dabei ist einerseits, einige Algorithmen und einige Datenstrukturen kennenzulernen und sie zu verstehen. Im Vordergrund stehen Such- und Sortieralgorithmen und die dynamische Datenstrukturen Listen, Bäume und Hashtabellen. Alle Algorithmen werden in so genanntem Pseudocode dargestellt. Darüber hinaus geht es aber auch um die Analyse von Algorithmen. Eine Technik zu deren Verifikation wird kurz eingeführt, die Verfahren zur Bestimmung ihrer Komplexität bzgl. Laufzeit und Speicherplatz werden dagegen tiefergehend diskutiert. Hierfür werden einige Komplexitätsmaße eingeführt und diese auf alle vorgestellten Algorithmen angewendet.

Lerneinheiten

    • Einleitung (Arbeitsaufwand ca. 10 h)
      • Was ist ein Algorithmus?
      • Darstellung von Algorithmen
    • Analyse von Algorithmen(Arbeitsaufwand ca. 20 h)
      • Verifikation
      • Komplexität
      • Asymptotische Notation
      • Optimalität
    • Rekursion Arbeitsaufwand ca. 10 h
      • Lineare Rekursion
      • Divide and Conquer
    • Suchen und Sortieren (Arbeitsaufwand ca. 40 h)
      • Problemspezifikation
      • Sequentielles Suchen
      • Binäres Suchen
      • Suchen und Optimalität
      • Bubble-Sort
      • Merge-Sort
      • Quick-Sort
      • Sortieren und Optimalität
      • Sortieren durch Abzählen
    • Dynamische Datenstrukturen (Arbeitsaufwand ca. 40 h)
      • Abstrakte Datentypen
      • Verkettete Listen
      • Binäre Bäume
      • Binäre Heaps
      • Konstruktion und Erhalten eines Heaps
      • Heap-Sort
      • Prioritäts-Warteschlangen
    • Hashverfahren Datenstrukturen (Arbeitsaufwand ca. 20 h)
      • Adresstabelle mit direktem Zugriff

Präsenz

Pflichtpräsenzen:
2 von 3
Zeitaufwand:
Inhalte:
Besprechung inhaltlicher Fragen zum Studienmodul Besprechung ausgewählter Übungsaufgaben und gemeinsame Bearbeitung weiterer Beispiele Klärung sonstiger Fragen Klausurvorbereitung
Art:
fakultativ
Teilnahme:
erfordert physische Anwesenheit

Prüfung

Einsendeaufgaben:

Erfolgreiche Bearbeitung von 3 Einsendeaufgaben, wobei jede Einsendeaufgabe bestanden sein muss, d.h. mindestens 50% der erreichbaren Punktzahl.

Leistungsnachweise:
Prüfungsform:
Klausur (120 min)

Literatur

  • Algorithmen - eine Einführung
    Corman, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.
    Oldenbourg Verlag, München 2007
    2. Auflage
    ISBN 978-3-486-58262-8
  • Computer Algorithms - Introduction to Design and Analysis
    Baase, Sara; van Geldern, Allen
    Addison Wesley Longman Inc., Mass. 2000
    3rd Edition
    ISBN 0-201-612244-5
  • Algorithmik
    Schöning, Uwe
    Spektrum Akademischer Verlag Heidelberg 2001
    ISBN 3-8274-1092-4

Hinweise

Medien-/Lernform

Multimedial aufbereitetes Online-Studienmodul zum Selbststudium mit zeitlich parallel laufender Online-Betreuung (E-Mail, Chat, Einsendeaufgaben u. a.) sowie Präsenzphasen

Hinweise

Verantwortliche

Prof. Dr. Friedhelm Seutter (Ostfalia Hochschule Wolfenbüttel)