Praktische Informatik 2
Practical Computer Science 2
|
Modulnummer
IBGP-PI2
|
Bachelor
|
Zugeordnet zu Masterprofil
|
Modulbereich
:
Praktische und Technische Informatik
Modulteilbereich
:
(keine Angabe)
|
Anzahl der SWS
V |
UE |
K |
S |
Prak. |
Proj. |
∑ |
2 |
2 |
0 |
0 |
0 |
0 |
4 |
|
Kreditpunkte
:
6
|
Turnus
angeboten in jedem SoSe
|
Formale Voraussetzungen
:
-
|
Inhaltliche Voraussetzungen
:
Praktische Informatik 1
|
Vorgesehenes Semester
:
2. Semester
|
Sprache
:
Deutsch
|
Ziele
:
- Typische Datenstrukturen identifizieren und problemadäquat einsetzen können.
- Datenstrukturen und Algorithmen in Java umsetzen können.
- Wesentliche Algorithmen der Informatik erklären, anwenden und modifizieren können.
- Algorithmische Alternativen bezüglich der Eignung für ein Problem beurteilen können.
- Grundbegriffe der formalen Verifikation erläutern können.
- Die Komplexität von einfachen Algorithmen analysieren können.
- Eine komplexe Entwicklungsumgebung nutzen können.
- Generische und funktionale Konzepte in eigenen Programmen einsetzen können.
- In Gruppen Probleme analysieren und gemeinsam Lösungsstrategien entwickeln und präsentieren können.
Die Vorlesungen Praktische Informatik 1 und 2 vermitteln essenzielles Grundwissen und Basisfähigkeiten, deren Beherrschung für nahezu jede vertiefte Beschäftigung mit Informatik – sowohl in der industriellen Anwendung, als auch in der Forschung – Voraussetzung ist.
|
Inhalte
:
- Algorithmen: Begriff des Algorithmus – Beschreibung von Algorithmen – Algorithmische Umsetzung kanonischer Operationen auf Datenstrukturen – Grundlegende Strategien: Greedy, Divide-and-Conquer, Backtracking, dynamische Programmierung
- Komplexität von Algorithmen – O(n)-Notation und asymptotische Analyse
- Suchen und Sortieren auf Arrays: Binäre Suche – Quicksort und weitere Sortieralgorithmen – Komplexitätsvergleiche
- Mengen – Multimengen – Relationen – Funktionen: Datenstrukturen und Algorithmen zur Realisierung kanonischer Operationen (z.B. Mengenalgebra)
- Listen – Stapel – Warteschlangen: Datenstrukturen zur Realisierung (Arrays versus Verkettung und dynamische Speicherallokation für Elemente), Algorithmen zur Realisierung kanonischer Operationen (Listentraversion, Anfügen, Einfügen, Löschen, Suchen, Stack-Operationen, FIFO-Warteschlangenoperationen)
- Bäume: Binäre Bäume, AVL-Bäume, Rot-Schwarz-Bäume, B-Bäume – Suchen, Einfügen, Löschen, Traversion
- Hashing: Hash-Array, Hashfunktion, Hash Buckets, offenes Hashing
- Graphen: ungerichtete, gerichtete, gewichtete Graphen – Repräsentation durch Knoten- und Kantenlisten, durch Adjazenzmatrizen, Adjazenzlisten – Algorithmen auf Graphen: Breitensuche, Tiefensuche, kürzeste Wege auf gewichteten Graphen: Dijkstras Algorithmus, minimal aufspannende Bäume: Algorithmen von Prim et al. und Kruskal
- Spezifikation von Programmen: Vor- und Nachbedingungen – Invarianten
- Verifikation: Partielle und totale Korrektheit sequenzieller Programme – Formale Verifikation, z.B. Hoare Logik (Pre-/Postconditions) – Eigenschaftsbeweis durch Strukturelle Induktion
Lehrveranstaltung(en):
- 03-IBGP-PI2 Praktische Informatik 2: Algorithmen und Datenstrukturen
|
Unterlagen (Skripte, Literatur, Programme usw.)
:
- G. Saake und K.-U. Sattler: Algorithmen und Datenstrukturen. dpunkt.verlag, Heidelberg (2004)
- R. Schiedermeier: Programmieren mit Java. Pearson, München (2005)
Weitere Informationen (Beispielprogramme, Musterlösungen, im WWW verfügbare Literatur) sind auf der Web-Seite der Veranstaltung zu finden.
|
Form der Prüfung
:
KP, PL1: 70\%, PL2: 30\%, Portfolio, Klausur
|
Arbeitsaufwand
Präsenz |
56 |
Übungsbetrieb/Prüfungsvorbereitung |
124 |
Summe |
180 h |
|
Lehrende:
Dr. T. Röfer, N.N.
|
Verantwortlich
Prof. Dr. U. Bormann
|