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	
MID0001	GRUNDLAGEN DER PROGRAMMIERUNG	

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

II. Lehrkräfte der Universität
Name und	Wiss.	Position	Lehrstuhl	Lehrveranstaltung	
Vorname	Grad			V	S	L	
TRÎMBIŢAŞ Maria-Gabriela	Dr.	Lekt.	Systeme	*			

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

III. Ziele der Disziplin
1.	Kenntnisse und Sicherheit im Umgang mit Grundelementen moderner Programmiersprachen erwerben
2.	Fähigkeiten entwickeln zur Umsetzung einfacher Problemstellungen in eine algorithmische Lösung,
3.	Kenntnisse über Spezifikationstechniken, Komplexitätsanalyse und Algorithmenentwurf erwerben; 
4.	Fähigkeiten ausbilden für die Spezifikation und Entwurf von einfachen Datenstrukturen und Algorithmen	

IV. Inhalte der Disziplin
1.	Algorithmen und Beschreibung von Algorithmen 
2.	Spezifikation bzw. Entwurf von Algorithmen
3.	Die Formulierung in einem Pseudocode und Implementierung in Pascal
4.	Die Korrektheit eines Algorithmus 
5.	Entwurfstechnologie: die schrittweise Verfeinerung 
6.	Entwurfsvorgehensweise: Top down, Botom up
7.	 Entwurfsmethoden für Algorithmen: Teile und Herrsche, Backtracking, Greedy, Dynamische Programmierung, heuristische Methoden.
8.	Rekursion
9.	Abstrakte Datentypen (ADT) 
10.	Komplexität von Berechnungen, O-Notation
11.	Sortieralgorithmen, Maximal- und Durchschnittskomplexität
12.	Suchalgorithmen, Maximal- und Durchschnittskomplexität	

V. Pflichtliteratur
1. Frentiu, M., H.F. Pop, Fundamentals of Programming, Cluj University Press, 2006, 220 pagini
2. M.Frentiu si altii, Manualul incepatorului in Programarea Pascal, Ed. Microinformatica, Cluj-Napoca, 1995, 252 pagini, ISBN 973-9215-04-1
3. M.Frentiu si altii, Programare Pascal. Programe ilustrative, probleme propuse, pentru elevi si studenti, Ed. Promedia, 1995, 229 pagini, ISBN 973-96862-1-4.
4. M.Frentiu, V.Prejmereanu, Algoritmica si programare, Lito. Univ. Babes-Bolyai, Cluj-Napoca, 1995, 261 pagini.
5. Frentiu, M., I.Lazar, S.Motogna si V.Prejmereanu, vol.I - Elaborarea algoritmilor, 1997, 188 pagini; vol.II - Programare Pascal, 392 pagini; Ed.Universitatii Babes-Bolyai, Cluj-Napoca.
6. M.Frentiu si B.Parv, Elaborarea programelor. Metode si tehnici moderne, Ed.Promedia, Cluj-Napoca, 1994, 217 pag.
7. Kasa, Z., Algoritmusok tervezese, Ed. Studium, Cluj, 1994.
8. Knuth, D., Tratat de programarea calculatoarelor, Ed. Tehnica (Algoritmi fundamentali;  Cautare si sortare)
9. Livovschi, L., H.Georgescu, Sinteza si analiza algoritmilor, Editura St. si Enciclopedica, Bucuresti, 1986.
10.Vaduva, I., Baltac, V., V.Florescu, I.Floricica, M.Jitaru, Ingineria programarii, Editura Academiei   RSR, Bucuresti, 1985 
11. Sedgewick, R: Algorithmen, Addison-Wesley,1998 (Bibliothek)
12. Wirth, N Algorithmen und Datenstrukturen, Pascal Version, 5 Auflage, B.G. Teubner Stuttgart 
      (Bibliothek)	

VI. Thematik der wöchentlichen Lehrveranstaltungen
1.Grundlagen   (1 Vorlesung  + 1 Seminar – S1) [1, ch. 1; 5,1] (S1-S14 sind die 14 Semesterwochen)
Algorithmenbegriffe, 
Programmiersprachliche Konstrukte zur Algorithmenspezifikation, 
ausgewählte Algorithmenprobleme
Pseudocode

2. Unterprogramme – Funktionen  (1 Vorlesung + 1 Seminar - S2) [1, ch. ]
Konzept
Parameter
Lebensdauer (Gültigkeitsbereich) von Namen
Der exit-Status
Endlichkeit von Programmen
Seiteneffekte
Kommandozeilenparameter
Ein- und Ausgabefunktionen
Debuggen auf Quelltextebene

3. Pascal  (2 Labor – S1,2,3) [1, ch.3; 5,2]
Datentypen
Anweisungen
Ein-/Ausgabe
Struktur eines Pascal-Programms

4. Der Software-Lebenszyklus(1 Vorlesung + 1 Seminar – S3) [1, ch. 2,3,4; 5,6,7]
Lebenszyklus-Phasen
Problemdefinition
Anforderungsanalyse
Spezifikation
Software-Entwurf
Implementation 
Verifikation von Software
Software-Wartung 
Softwarequalitätssicherung
Testplanung und Testdokumentation 
Testen von Software
Statischer Test
Dynamischer Test

5. Entwicklung und Darstellung des Algorithmus(1 Vorlesung + 1 Seminar+ 1 Labor – S4) [1, ch. 4]
Programmstrukturen
Programmablaufplan
Struktogramm
Programmentwicklung

6. Rekursion(1 Vorlesung + 1 Seminar+ 1 Labor – S5) [3, ch. 3,4; 5,5]
Rekursion und Iteration 
Beispiel : Rekursive Traversierung von Bäumen
Grundlegende rekurrente Beziehungen
Beseitigung der Rekursion

7. Teile und herrsche(1 Vorlesung + 1 Seminar+ 1 Labor – S6) [1, ch. 5; 5,5]
Allgemeiner Algorithmus 
Beispiel: Erzeugung von Turnierpaarungen
Teilproblemgröße und Aufwand
Master Theorem

8. Abstrakte Datentypen(1 Vorlesung + 1 Seminar+ 1 Labor – S6) [1, ch. 5; 5,3]
Abstrakte Datentypen und deren Implementierung: axiomatische und programmiersprachliche Spezifikation
Pascal Unit

9. Backtracking Verfahren(1 Vorlesung + 1 Seminar+ 1 Labor – S7) [1, ch. 7; 5,44]
Allgemeiner Algorithmus 
Zug des Pferdes
Zeit- und Speicheraufwand
8-Damen-Problem
Aufwand für das 8-Damen-Problem

10. Greedy – Verfahren(1 Vorlesung + 1 Seminar+ 1 Labor – S7) [1, ch. 7; 5,42]
Allgemeiner Algorithmus 
Beispiel: Geldrückgabe mit möglichst wenigen Münzen
Beispiel: Das Problem des Handlungsreisenden
Greedy-Algorithmus als Heuristik

11.Dynamische Programmierung(1 Vorlesung + 1 Seminar+ 1 Labor – S8) [1, ch. 7; 5,42]
Das Rucksack-Problem
Das Produkt mehrere Matrizen
Zeit- und Speicheraufwand

12. Analyse und Implementation von Algorithmen(1 Vorlesung – S9) [1, ch. 6; 5,6,7]
Algorithmenanalyse: Mathematische Grundlagen, 
Komplexitätsklassen,
Laufzeitberechnungen
Analyse des durchschnittlichen Falles
Näherungsweise und asymptotische Ergebnisse
Empirische Analyse
Auswahl eines Algorithmus

13. Sortieralgorithmen(3 Vorlesungen + 3 Seminare+ 3 Labor – S10,11,12) [1, ch. 8; 5,8,9,10,12,13]
Sortieren, intern, extern, stabil
Sortieren durch direktes Einfügen
Zeit und Speicheraufwand
Sortieren durch direkte Auswahl
Zeit und Speicheraufwand
Sortieren durch direktes Austauschen
Zeit und Speicheraufwand
MergeSort; Kenngrößen der Leistungsfähigkeit
Sortieren durch Austauschen und Zerlegen (Quicksort)
Zeit und Speicheraufwand
Counting sort
Zeit und Speicheraufwand
RadixSort
Zeit und Speicheraufwand

14.Suchalgorithmen(2 Vorlesungen + 2 Seminare+ 2 Labor – S13,14) [1, ch. 8; 5,14]
Sequentielle Suche
Zeit und Speicheraufwand
Binäre Suche
Zeit und Speicheraufwand
Suchen in einem Binärbaum
Zeit und Speicheraufwand 

VII. Didaktische Methoden
Die Darstellung der Thematik, der Vortrag, das Unterrichtsgespräch, Beweise an der Tafel, die Beschreibung, die Erklärung, die Diskussion der Problemstellungen, die Dokumentation, individuelles Studium, Teamarbeit.

VIII. Beurteilung der studentischen Leistungen
Die Kontrollarbeit ist in der 8. Woche eingeplant. Die Thematik dafür ist diejenige, welche für Vorlesung und Seminar bis 8. Woche vorgesehen ist.
Die Gesamtnote für die Disziplin Grundlagen der Programmierung wird aufgrund der Leistungen nach der Formel EN = (N1+ N2+ N3)/3 berechnet, wobei N1 =(K+ S+L)/3 (K= die Note in der Kontrollarbeit, S = die Note für die aktive Mitarbeit, L = die Note für das Lösen der Laboraufgaben während des Semesters), N2 = die Note in der praktischen Prüfung und N3 die in der schriftlichen Abschlussarbeit erzielte Note bezeichnet.
Ein Student muss an mindestens 80% der Laborstunden teilnehmen. Es werden bei der Prüfung nur die Studenten akzeptiert, welche N1>= 5 haben. Um die Prüfung zu bestehen müssen N2 und N3 >= 5 sein.
Siehe auch:
\\win\Labor\Germana\An1\Grundlagen\Anforderungen.doc	

IX. Zusatzliteratur
1.	Knuth, D.E., Tratat de programare a calculatoarelor. Algoritmi fundamentali. Ed.Tehnica, Bucuresti 1974 (Bibliothek)
2.	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

	
	Dekan,						Lehrstuhlleiter,

	Datum,						Verantwortliche Lehrkraft,
	1.10.2010						Lect. Dr.  TRÎMBIŢAŞ Maria-Gabriela