Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Matematică
Programul de studii: Matematică informatică -linia de studiu germană
Limba de predare: Germană

SYLLABUS

I. Allgemeine Daten
Kennnummer	Disziplin	
MIE0001	ALGORITHMEN UND DATENSTRUKTUREN	

Semester	Stunden: C+S+L	Kategorie	Status	
2	2+1+0	Grundvorlesung	Pflichtvorlesung	

II. Lehrkräfte der Universität
Name und	Wiss.	Position	Lehrstuhl	Lehrveranstaltung	
Vorname	Grad			V	S	L	
TRÎMBITAS Maria-Gabriela	Dr.	Lekt.	Sisteme Informatice	*			

Assozierte Lehrkräfte
Name und	Wiss.	Institution	Position	Lehrveranstaltung	
Vorname	 			V	S	L	

III. Ziele der Disziplin
•	Studium des Konzeptes  ”Abstrakter Datentyp (ADT)” und den bei der, Entwicklungen von Programmen am meisten verwendeten abstrakten Datentypen
•	Studium der Datenstrukturen, mit deren Hilfe diese abstrakten Datentypen implementiert werden können (Felder, verkettete Listen, binäre Bäume, Hash-Tabellen, u.s.w.)
•	Die Technik der Projektierung und Entwicklung von Software unter Anwendung abstrakter Datentypen zu beherrschen
•	Fähigkeiten entwickeln, Daten zu verarbeiten, welche in verschiedene Datenstrukturen gespeichert sind: Felder, Datensätze, Zeichenketten, verkettete Listen, Stapel, Schlangen, Hash-Tabellen, Bäume und Graphen
•	Aufwand berechnen lernen für statische und dynamische Speicherzuweisung der unterschiedlichen Datenstrukturen
•	Fähigkeiten ausbilden, die geeignete Datenstruktur für eine Anwendungsentwicklung auszuwählen
•	Fähigkeiten entwickeln für die Projektierung und Implementierung der Algorithmen für die studierten Datenstrukturen 
•	Die Gewohnheit bilden, die Komplexität eines Algorithmus abzuschätzen 

Am Ende des Lernprozesses sollen die Lernenden die vorher erwähnten Fähigkeiten und Fertigkeiten beherrschen	
IV. Inhalte der Disziplin
•	Berechnungskomplexität eines Algorithmus.
•	Elementare Datenstrukturen: Feld, Datensatz. 
•	Sortieralgorithmen.
•	Verkettete Listen. Stapeln. Schlangen. Prioritätswarteschlangen.
•	Wörterbücher. Hashing. Die Datenstruktur des Heaps.
•	Binäre Bäume. Binäre Suchbäume. Spezialisierte Datenstrukturen (AVL-Bäume, Rot-Schwarz-Bäume).

V. Pflichtliteratur
1.	THOMAS H. CORMEN, CHARLES E. LEISERSON, RONALD RIVEST, CLIFFORD STEIN, Algorithmen – Eine Einführung, 2., korrigierte Auflage 2007. XXII, 1188 S., Oldenbourg Wissenschaftsverlag, ISBN 978-3-486-58262-8
2.	HOROWITZ, E.: Fundamentals of Data Structures in C++. Computer Science Press, 1995. 
3.	MOUNT, DAVID M.: Data Structures. University of Maryland, 1993. 
4.	AMBSBURY, WAYNE: Data Structures. From Arrays to Priority Queues, 1993. 
5.	STANDISH, T.A.: Data Structures, Algorithms & Softwae Principles in C, Addison-Wesley, 1995
6.	SEDGEWICK, R: Algorithmen, Addison-Wesley,1998 (Bibliothek)
7.	WIRTH, N Algorithmen und Datenstrukturen, Pascal Version, 5 Auflage, B.G. Teubner Stuttgart (Bibliothek)
8.	Frentiu, M., Pop, H.F., Serban, G.: Programming Fundamentals, Ed. Presa Universitara Clujeana, Cluj-Napoca, 2006

VI. Thematik der wöchentlichen Lehrveranstaltungen
1. Einführung. Datenstrukturen. Statische, semi-statische und dynamische Strukturen (1Vorlesung – S1 + 1 Seminar – S1 / S2) [1, ch. 1, 2] (S1-S14 sind die 14 Wochen des 2. Semesters)
-	Abstrahierung und Einkapselung der Daten 
-	Dynamische Mengen
-	Berechnungskomplexität
2. Datentypen: Teilbereich, Operationen und Repräsentierung der Daten (1Vorlesung – S2) [6, ch. 5; 7,3]
-	Abstrakte Datentypen: Teilbereich und Operationen
-	Anforderungen, Schnittstelle, Implementierung(en)
-	Projektierung der abstrakten Datentypen
Das Feld
-	Beschreibung, Eigenschaften
-	Folgen, Teilfolgen, Sequenzen, Matrizen
-	Dynamische Folgen: Operationen: Einfügen/Löschen, sequentielle und binäre Suche
-	Mischen
-	Sortieren: Insertion-, Selection-, Quick-, Mergesort, Counting Sort, Radixsort, Bucketsort, u.s.w.
3. ADT Menge  (1 Vorlesung – S3)  [1, ch. 5]
-	Grundbegriffe 
-	Anwendungen der Mengen
-	ADT Menge: Spezifizierung und Implementierung
-	Darstellungen der Mengen mit Hilfe von Felder oder boolische Vektoren (Bit-Vektoren), verketteten Listen, Hash-Tabellen, binären Bäume.
4. ADT - Wörterbuch (1 Vorlesung – S4+ 1 Seminar – S3 / S4) [4, ch. 6]
-	Grundbegriffe
-	Anwendungen der Wörterbücher
-	ADT Wörterbuch: Spezifizierung und Implementierung
-	Darstellungen der Wörterbücher mit Hilfe von boolischen Felder, verketteten Listen, Hash-Tabellen, binären Bäume.
-	Sortierte Wörterbücher (sorted map)
5. ADT- Liste (2 Vorlesungen – S5, S6+ 2 Seminare – S5/ S6 , S7/ S8) [1, ch. 11; 7,3]
-	Grundbegriffe
-	Anwendungen der Listen
-	ADT Liste: Spezifizierung und Implementierung
-	Darstellungen der Listen mit Hilfe von Felder und verketteten Listen
-	Sortierte Listen
Verkettete Liste
-	Beschreibung, Eigenschaften
-	Dynamisch allokierte einfach-, doppeltverkettete und zyklische Listen 
-	Darstellung mit parallelen Verkettungsfelder
-	Operationen: Einfügen/Löschen, Suche, Traversierung 
6. ADT Stapel (1 Vorlesung – S7) [1, ch. 11; 7,3]
-	Grundbegriffe 
-	Anwendungen der Stapeln
-	ADT Stapel: Spezifizierung und Implementierung
-	Darstellungen der Stapeln mit Hilfe von Felder und verketteten Listen
7. ADT Warteschlange ( S7) [1, ch. 11; 7,11]
-	Grundbegriffe
-	Anwendungen der Warteschlangen
-	ADT Warteschlange: Spezifizierung und Implementierung
-	Darstellungen der Warteschlangen mit Hilfe von Feldern und verketteten Listen
8. ADT Prioritätswarteschlange (1 Vorlesung – S8+ 1 Seminar – S9 / S10) [1, ch. 7; 7,11]
-	Grundbegriffe
-	Anwendungen der Prioritätswarteschlangen 
-	ADT Prioritätswarteschlange: Spezifizierung und Implementierung
-	Darstellungen der Prioritätswarteschlangen mit Hilfe von Felder und verketteten Listen
9. Hashtabelle (hash-table) (1 Vorlesung– S9, S10+ 1 Seminar – S11 / S12) [1, ch. 12; 7,16]
-	Beschreibung, Eigenschaften
-	Hash-Funktionen
-	Getrennte Verkettung
-	Lineares Austesten
-	Doppeltes Hashing
-	Operationen: Suchen, Einfügen/Löschen eines Elementes
10. ADT Baum (1 Vorlesung – S11 + 1 Seminar – S13 / S14) [1, ch. 13; 7,4]
-	Grundbegriffe
-	Anwendungen der Bäume
-	ADT Baum: Spezifizierung und Implementierung
-	Darstellung von Bäumen mit Hilfe der Verkettungen
-	ADT Baum mit verschiedenen Eigenschaften

Binärer Baum
-	Beschreibung, Eigenschaften
-	Binäre Bäume. Binäre Suchbäume
-	Operationen: Suchen, Einfügen/Löschen eines Elementes, Traversieren 
11. Heaps  (1 Vorlesung – S12) [1, ch. 7; 7,11]
-	Die Datenstruktur des Heaps
-	Darstellung eines Heaps als vollständiger binärer Baum
-	Darstellung der Prioritätswarteschlangen unter Verwendung von Heaps
-	Heapsort
12. Ausgeglichene binäre Suchbäume (1 Vorlesung – S13) [1, ch. 14; ; 7,15]
-	AVL-Bäume, 
-	Rot-Schwarz-Bäume
13. ADT Graph (1 Vorlesung – S14) [1, ch. 1,23; 7,29]
-	Grundbegriffe
-	Anwendungen der Graphen
-	ADT Graph: Spezifizierung und Implementierung

VII. Didaktische Methoden
Frontalunterricht, Konversationen, Projektarbeit, Übungen, Vortrag, Unterrichtsgespräch, Beweise an der Tafel, Beschreibung, Erklärung, die Diskussion der Problemstellungen, Dokumentation, individuelles Studium, Teamarbeit.

VIII. Beurteilung der studentischen Leistungen
Die Kontrollarbeit ist in der 10. Woche eingeplant. Die Thematik dafür ist diejenige welche für Vorlesung und Seminar bis 10. Woche vorgesehen ist.
Jeder Student muss:
•	ein Projekt ausarbeiten (N1 – 20% der Endnote), 
•	die Kontrollarbeit während des Semesters (N2 – 20% der Endnote) schreiben
•	eine schriftliche Prüfung (N3 – 60% der Endnote) bestehen. 
•	Die Endnote EN =  (2*N1+2*N2+6*N3)/10
Ein Student muss an mindestens 80% der Übungsstunden teilnehmen. Es werden bei der Prüfung nur die Studenten akzeptiert welche N1 >= 5 haben. Um die Prüfung zu bestehen müssen N3 und die EN >= 5 sein.

IX. Zusatzliteratur
1.	AMBSBURY, WAYNE: Data Structures. From Arrays to Priority Queues, 1993. (Bibliothek)
2.	BRUNO R. PREISS, Data Structures and Algorithms with Object-Oriented Design Patterns in C++, 1997.	

	Datum,						Verantwortliche Lehrkraft,
	1.05.2007						Lect. Dr. TRÎMBITAS Maria-Gabriela