Informatik 2 - Algorithmen und Datenstrukturen

NUMMER: 150322
KÜRZEL: INFO2
DOZENT: Prof.‘in Dr. Maike Buchin
FAKULTÄT: Fakultät für Mathematik
SPRACHE: Deutsch
SWS: 6 SWS
CREDITS: 8 CP
WORKLOAD: 240 h
ANGEBOTEN IM: jedes Sommersemester

INFOS

Informatik 2 – Vorlesung (4 SWS)
Informatik 2 – Übung (2 SWS)


PRÜFUNGUNGSFORM

Schriftliche Modulabschlussprüfung über 150 Minuten


LERNFORM

Hörsaalvorlesung mit Medienunterstützung und praktische Übungen am Rechner


LERNZIELE

Nach dem erfolgreichen Abschluss des Moduls

- können Studierende Algorithmen formal beschreiben und deren Korrektheit beweisen
- können Studierende die Laufzeit und den Speicherbedarf von Algorithmen und Daten-strukturen analysieren und bewerten
- kennen Studierende grundlegende Datenstrukturen
- kennen Studierende grundlegende Schemata zum Entwurf von Algorithmen
- sind Studierende in der Lage, Algorithmen und Datenstrukturen für spezifische Probleme zu entwickeln
- haben die Studierenden die Grundlagen der Programmiersprache Java kennengelernt


INHALT

Die Vorlesung gibt einen systematischen Überblick über den Entwurf und die Analyse von Algorithmen und Datenstrukturen. Dazu werden zunächst grundlegende Methoden der Analyse (insbesondere Korrektheit, Laufzeit und Speicherbedarf) von Algorithmen vorgestellt. Anschließend werden einige Algorithmen zum Sortieren und Suchen analysiert. Ebenfalls werden verschiedene grundlegende Datenstrukturen (Listen, Felder, Suchbäume und Heaps) vorgestellt. Schließlich werden Graphen betrachtet, und zwar ihre Darstellung und diverse Algorithmen auf Graphen (Durchläufe, kürzeste Wege, minimale Spannbäume).

In den Übungen lernen die Studierenden sowohl die theoretische Analyse von Algorithmen und Datenstrukturen als auch deren praktische Umsetzung in eine moderne Programmiersprache (z.B. Java).


VORAUSSETZUNGEN

keine


VORAUSSETZUNGEN CREDITS

Bestandene Modulabschlussprüfung


EMPFOHLENE VORKENNTNISSE

Inhalte der Module Informatik 1 und Mathematik 1, insbesondere Programmieren und lineare Algebra


LITERATUR

1. Dietzfelbinger, K. Mehlhorn, P. Sanders:
„Algorithmen und Datenstrukturen – Die Grundwerkzeuge“, Springer Verlag
2. T. H. Cormen, C. E. Leiserson, R. Rivest, C. Stein:
„Algorithmen – Eine Einführung“, Oldenbourg Verlag


Computer Science 2 - Algorithms and Data Structures

NUMMER: 150322 KÜRZEL: INFO2 DOZENT: Prof.‘in Dr. Maike Buchin FAKULTÄT: Fakultät für Mathematik SPRACHE: German SWS: 6 SWS CREDITS: 8 CP WORKLOAD: 240 h ANGEBOTEN IM: each summer semester

INFOS

Computer Science (Informatik 2) –
Lecture (4 SWS)
Computer Science (Informatik 2) –
Excersise (2 SWS)


PRÜFUNGUNGSFORM

Written final exam of 150 minutes


LERNFORM

Lecture with media support and practical exercises on the computer


LERNZIELE

After successfully completing the module
- students can formally describe algorithms and prove their correctness
- students can analyze and evaluate the runtime and storage requirements of algorithms and data structures
- students know basic data structures
- students know basic schemes for designing algorithms
- students are able to develop algorithms and data structures for specific problems
- the students got to know the basics of the Java programming language


INHALT

The lecture gives a systematic overview of the design and analysis of algorithms and data structures. For this purpose, basic methods of analysis (especially correctness, runtime and memory requirements) of algorithms are presented. Then some algorithms for sorting and searching are analyzed. Various basic data structures (lists, fields, search trees and heaps) are also presented. Finally, graphs are considered, specifically their representation and various algorithms on graphs (runs, shortest paths, minimal spanning trees)
In the exercises, students learn both the theoretical analysis of algorithms and data structures and their practical implementation in a modern programming language (e.g. Java).


VORAUSSETZUNGEN

None


VORAUSSETZUNGEN CREDITS

Passed examination


EMPFOHLENE VORKENNTNISSE

Contents of the modules Computer Science 1 (Informatik 1) and Mathematics 1 (Mathematik 1), in particular programming and linear algebra


LITERATUR

1. M. Dietzfelbinger, K. Mehlhorn, P. Sanders:
„Algorithmen und Datenstrukturen – Die Grundwerkzeuge“, Springer Verlag
2. T. H. Cormen, C. E. Leiserson, R. Rivest, C. Stein:
„Algorithmen – Eine Einführung“, Oldenbourg Verlag