Vorlesung Grundlagen der Informatik 2

Zurück zur Übersicht ...

Titel
Grundlagen der Informatik 2
Title (in english)
Fundamentals of Computer Sciences 2
Kürzel (Prüfungsamt)
GDI2
Art der Lehrveranstaltung
Vorlesung (Pflichtfach)
gehört zu
Lehrende(r)
Fakultät
Wird gehalten
im Sommersemester
empfohlenes Semester
IN2
Credits
6 CP
Semesterwochenstunden
4 SWS
zugehöriges Praktikum
Leistungsnachweis(e)
WiSe 2014 (IN2, freigegeben am 16.10.2014)
SoSe 2014 (IN2, freigegeben am 03.04.2014)

Ziele

Die Studierenden beherrschen die Grundlagen von Algorithmen und Datenstrukturen.

Die Studierenden erlangen Kenntnisse grundlegender Datenstrukturen und Verarbeitungstechniken unter Einbeziehung externer Speichermedien und die Fähigkeit, sie anzuwenden (Komplexität und Effizienz von Algorithmen; Suchen und Sortieren; Lineare und Dynamische Strukturen; Bäume; Graphen; Algorithmen auf externen Medien; Anwendungen).

Im Praktikumsteil werden Übungsaufgaben zu den wesentlichen in der Vorlesung systematisch vorgestellten Algorithmen gemeinsam erarbeitet.

Inhalte

1     Einleitung
1.1   Algorithmen und Datenstrukturen
1.2   Komplexitätstheorie
1.3   Primzahlen, Zufallszahlen

2     Lineare Datenstrukturen
2.1   Lineare Liste
2.2   Suche in Zeichenfolgen
2.3   Stack-basierte Algorithmen

3     Bäume
3.1   Baumstrukturen
3.2   Binärbaum
3.3   Heap
3.4   Klassifikation von Sortierverfahren

4     B-Baum-Familie
4.1   "Paging" von Binärbäumen
4.2   Erweiterungen

5     Graphen
5.1   Grundbegriffe
5.2   Elementare Graphenalgorithmen
5.3   Algorithmen auf gewichteten Graphen
5.4   Fluss in Netzwerken

6     Gestreute Speicherung
6.1   Hash-Algorithmus
6.2   Kollisionsauflösung
6.3   Erweiterbares Hashing
6.4   Kryptographische hash-Funktionen

7     Externe Medien
7.1   Dateikonzepte
7.2   Nebenläufige Verarbeitung
7.3   Indexsequentielle Speicherung
7.4   Indizierte Dateien

Empfohlene Literatur

Cormen/Leiserson/Rivest/Stein Algorithmen - eine Einführung
Oldenbourg, München 2004
Folk/Zoellick File Structures
Addison Wesley Longman, Reading 1992, 2nd ed.
Reß /Viebeck Datenstrukturen und Algorithmen   (C++)
Hanser, München 2000
Saake/Sattler Algorithmen und Datenstrukturen  (Java)
Dpunkt, Heidelberg 2002
Sedgewick, R. Algorithmen in Pascal/C/C++
Addison Wesley Longman, Bonn 1992 ff

Arbeitsaufwand

Voraussetzungen

Modul Grundlagen der Informatik 1 (empfohlen)

Form der Wissensvermittlung

Seminaristischer Unterricht, Praktikum