Feedback
Sitemap
English
Studienplan
Mensa
Webmail
Hochschule intern (Login)Vorlesung Grundlagen der Informatik 2
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
- Präsenzzeit: 5 SWS / 56,5 h
- Vor- und Nachbereitung: 123,5 h
Voraussetzungen
Modul Grundlagen der Informatik 1 (empfohlen)Form der Wissensvermittlung
Seminaristischer Unterricht, Praktikum