HUMBOLDT-UNIVERSITÄT ZU BERLIN
MATHEMATISCH - NATURWISSENSCHAFTLICHE fAKULTÄT II
INSTITUT FÜR INFORMATIK
ARBEITSGRUPPE SPEZIFIKATION, Verifikation UND TESTtheorie
Prof. Dr. Holger Schlingloff
|
|
SS 2010
Skriptum zur Vorlesung
Grundlagen der Programmierung
Inhalt
Kapitel 0: Einführung 4
0.1 Inhalt der Vorlesung, Organisatorisches, Literatur 4
0.2 Einführungsbeispiel 8
0.3 Was ist Informatik? 15
Kapitel 1: Mathematische Grundlagen 20
1.1 Mengen, Multimengen, Tupel, Funktionen, Halbordnungen 20
1.2 Induktive Definitionen und Beweise 24
1.3 Alphabete, Wörter, Bäume, Graphen 27
Kapitel 2: Informationsdarstellung 32
2.1 Bits und Bytes, Zahl- und Zeichendarstellungen 32
2.2 Sprachen, Grammatiken, Syntaxdiagramme 41
2.3 Darstellung von Algorithmen 46
Kapitel 3: Rechenanlagen 53
3.1 Historische Entwicklung 53
3.2 von-Neumann-Architektur 61
3.3 Aufbau PC/embedded system, Speicher 65
Kapitel 4: Programmiersprachen und –umgebungen 70
4.1 Programmierparadigmen 70
4.2 Historie und Klassifikation von Programmiersprachen 73
4.3 Java und Groovy 75
4.4 Programmierumgebungen am Beispiel Eclipse 77
Kapitel 5: Applikative Programmierung 80
5.1 λ-Kalkül 80
5.2 Rekursion, Aufruf, Terminierung 81
Kapitel 6: Konzepte imperativer Sprachen 86
6.1 Variablen, Datentypen, Ausdrücke 86
6.2 Anweisungen und Kontrollstrukturen 90
6.3 Sichtbarkeit und Lebensdauer von Variablen 92
Kapitel 7: Objektorientierung 94
7.1 abstrakte Datentypen, Objekte, Klassen 94
7.2 Klassen, Objekte, Methoden, Datenfelder, Konstruktoren 98
7.3 Vererbung, Polymorphismus, dynamisches Binden 102
Kapitel 8: Modellbasierte Softwareentwicklung 106
8.1 UML Klassendiagramme und Zustandsmaschinen 106
8.2 Codegenerierung und Modelltransformationen 106
Kapitel 9: Spezielle Programmierkonzepte 107
9.1 Benutzungsschnittstellen, Ereignisbehandlung 107
9.2 Abstrakte Klassen, Interfaces, generische Typen 113
9.3 Fehler, Ausnahmen, Zusicherungen 114
9.4 Parallelität 117
Kapitel 10: Algorithmen und Datenstrukturen 124
10.1 Listen, Bäume, Graphen 124
10.2 Graphalgorithmen 131
10.3 Suchen und Sortieren 134
Hinweis zur Nutzung dieses Skriptes:
Achtung, drucken Sie das Skript (noch) nicht aus! Es wird parallel zur Vorlesung erstellt und laufend aktualisiert. Wenn Sie jetzt schon ihren Drucker bemühen, ist das entweder eine Verschwendung von Papier (weil Sie es später nochmal drucken) oder sie erhalten ein evtl. inkonsistentes Dokument (wenn Sie verschiedene Teile zusammenheften).
Mit Abschluss des Semesters wird Ihnen das gesamte Skript zur Verfügung stehen!
Dieses Dokument enthält außerdem Hyperlinks zu weiteren Quellen im Internet, die in Word oder mit dem Acrobat Reader durch Anklicken abrufbar sind. Für die Aktualität der Links übernehme ich keinerlei Gewähr..
HS, 22.4.2010
Kapitel 0: Einführung 0.1 Inhalt der Vorlesung, Organisatorisches, Literatur
Die Vorlesung „Grundlagen der Programmierung“ hat laut der Modulbeschreibung des Bachelor-Studienganges Informatik folgende Lern- und Qualifikationsziele:
Studierende verstehen die Funktionsweise von Computern und die Grundlagen der Programmierung. Sie beherrschen eine objektorientierte Programmiersprache und kennen andere Programmierparadigmen.
Daraus ergeben sich folgende Vorlesungsinhalte:
-
Grundlagen: Algorithmus, von-Neumann-Rechner, Programmierparadigmen
-
Konzepte imperativer Programmiersprachen: Grundsätzlicher Programmaufbau; Variablen: Datentypen, Wertzuweisungen, Ausdrücke, Sichtbarkeit, Lebensdauer; Anweisungen: Bedinge Ausführung, Zyklen, Iteration; Methoden: Parameterübergabe; Rekursion;
-
Konzepte der Objektorientierung: Objekte, Klassen, Abstrakte Datentypen; Objekt -Variablen/-Methoden, Klassen -Variablen/-Methoden; Werte und Referenztypen; Vererbung, Sichtbarkeit, Überladung, Polymorphie; dynamisches Binden; Ausnahmebehandlung; Oberflächenprogrammierung; Nebenläufigkeit (Threads)
-
Einführung in eine konkrete objektorientierte Sprache (z.B. JAVA): Grundaufbau eines Programms, Entwicklungsumgebungen, ausgewählte Klassen der Bibliothek, Programmierrichtlinien für eigene Klassen, Techniken zur Fehlersuche (Debugging)
-
Einfache Datenstrukturen und Algorithmen: Listen, Stack, Mengen, Bäume, Sortieren und Suchen
-
Softwareentwicklung: Softwarelebenszyklus, Software-Qualitätsmerkmale
-
Alternative Konzepte: Zeiger, maschinennahe Programmierung, alternative Modularisierungstechniken
Die Vorlesung (4 SWS) ist nur mit begleitender Übung (2 SWS), Praktikum (2 SWS),
Selbststudium, Vorlesungsmitschrift, Hausaufgaben (in Zweiergruppen bearbeitet, korrigiert
und bewertet, in der Übung besprochen) sinnvoll. Als Prüfung findet eine Abschlussklausur (120 Minuten Dauer) statt; die Zulassung zur Klausur ist an die Erreichung einer bestimmten Punktzahl in Übungen und Praktikum gebunden.
Für die erfolgreiche Teilnahme gibt es 12 Studienpunkte nach dem ECTS-System (European Credit Transfer System). Ein Studienpunkt (SP) entspricht 30 Zeitstunden Arbeitsaufwand; d.h., der Gesamtaufwand liegt bei ca. 360 Arbeitsstunden:
-
Vorlesung Grundlagen der Programmierung;
4 SWS, 6 SP, 60 Anwesenheitsstunden (4h/Woche), 120 h Aufbereitung (8h/Woche)
-
Übung Grundlagen der Programmierung;
2 SWS, 3 SP, 30 Anwesenheitsstunden (2h/Woche), 60 h Aufbereitung (4h/Woche)
-
Praktikum Grundlagen der Programmierung;
2 SWS, 3 SP, 30 Anwesenheitsstunden (2h/Woche), 60 h Aufbereitung (4h/Woche)
Für die Übungen wird 14-tägig ein Übungsblatt verfügbar gemacht, dessen Lösungen zwei Wochen später elektronisch abzugeben sind. Das Aufgabenblatt wird in den Übungen vor- und nachbesprochen. Für die Bearbeitung eines Aufgabenblattes sind also ca. 8h erforderlich.
Während für Vorlesung und Übung die Anwesenheit obligatorisch ist, kann beim Praktikum auf eine Anwesenheit verzichtet werden, wenn der/die Teilnehmer anderweitig über einen Rechner (Laptop) verfügt, auf dem die Aufgaben bearbeitet werden können. Die Gesamtzeit für die Bearbeitung der Praktikumsaufgaben beträgt ca. 6h/Woche.
Literaturhinweise
Leider gibt es kein einzelnes Buch, welches genau den Stoff der Vorlesung enthält.
Als Literatur zur Vorlesung empfehle ich das Buch von Gumm und Sommer.
(Aktuell: 8. Auflage; frühere Auflagen gibt es zum Teil im Sonderangebot)
Als Ergänzung dazu ist nachfolgend eine Liste relevanter Lehrbücher angegeben..
Lehrbücher: Einführung in die Informatik -
M. Broy: Informatik, eine grundlegende Einführung. Band 1: Programmierung und Rechnerstrukturen, Band 2: Systemstrukturen und theoretische Informatik. Springer-Lehrbuch (+ Aufgabensammlung) (Monumentalwerk)
-
P. Levi, U. Rembold: Einführung in die Informatik für Naturwissenschaftler und Ingenieure, Hanser, (konzise)
-
G. Goos: Vorlesungen über Informatik (vier Bände: Bd. 1: Grundlagen und funktionales Programmieren, Bd. 2: Objektorientiertes Programmieren und Algorithmen, Bd. 3: Berechenbarkeit, formale Sprachen, Spezifikationen, Bd. 4: Paralleles Rechnen und nicht-analytische Lösungsverfahren)
-
F. L. Bauer, G. Goos: Informatik - Eine einführende Übersicht, 4. Auflage.
Bd. 1+2, Springer („der Klassiker“, etwas veraltet)
-
L. Goldschlager, A. Lister: Informatik, Eine moderne Einführung. Hanser Studienbücher, (ebenfalls etwas veraltet; in der Bibliothek 40 Ex. vorhanden)
-
F. Kröger: Einführung in die Informatik – Algorithmenentwicklung. Springer Lehrbuch(formale Grundlagen, keine OO-Konzepte, als Ergänzung empfohlen)
-
H. Balzert: Lehrbuch Grundlagen der Informatik (als Ergänzung der Vorlesungsthemen)
-
H.-J. Appelrath, J. Ludewig: Skriptum Informatik - Eine konventionelle Einfürung. Teubner/VdF (+ Aufgabensammlung) (Betonung auf „konventionell“!)
-
A. Aho, J. Ullman: Informatik - Datenstrukturen und Konzepte der Abstraktion. (deutsche Fassung von: Foundations of Computer Science) Thomson Publishing / Computer Science Press (für Fortgeschrittene)
-
R. Sedgewick: Algorithmen in Java (auch für Fortgeschrittene)
Lehrbücher: Programmieren in Groovy
In der Vorlesung „Grundlagen der Programmierung“ und besonders im zugehörigen Praktikum sollen auch Programmierkenntnisse unterrichtet werden. Trotzdem ist diese Veranstaltung auf keinen Fall ein Programmierkurs; es wird erwartet, dass sich die Studierenden selbständig in programmiersprachliche Details an Hand geeigneter Lehrmaterialien (Bücher oder Online-Handbücher) einarbeiten.
Als notationelle Basis dient dabei zunächst die Skriptsprache Groovy, die auf der verbreiteten Programmiersprache Java aufbaut und einige moderne Erweiterungen vorsieht. Später gehen wir dann auf Java zurück. Das Haupt-Referenzbuch zu Groovy ist das Buch von König et. al.
Weitere Bücher zu Groovy sind
-
K. Barclay, J. Savage: Groovy Programming: An Introduction for Java Developers Morgan Kaufmann, 2006.
-
S. Davis: Groovy Recipes – Greasing the Wheels of Java. Pragmatic Bookshelf, 2008.
-
V. Subramaniam: Programming Groovy: Dynamic Productivity for the Java Developer. Pragmatic Bookshelf, 2008.
-
C. Judd, J. Nusairat: Beginning Groovy and Grails: From Novice to Professional. Apress 2008.
-
B. Abdul-Jawad: Groovy and Grails Recipes – a Problem-Solution Approach. Apress 2008.
Darüber hinaus gibt es zu Groovy eine umfangreiche Online-Dokumentation, siehe http://groovy.codehaus.org/Documentation.
Literatur zu Java
Zum Erlernen der Programmiersprache Java kann entweder das Buch von Bell und Parr oder das von Bishop dienen. Wer sich intensiver mit Java auseinander setzen möchte, dem sei das Buch von Gosling als ultimative Referenz empfohlen.
-
J. Bishop: Java lernen (dt. Ausgabe von Java Gently), Addison Wesley / Pearson, 2. Aufl. 2001 (südafrikanisches Flair)
-
K. Arnold, J. Gosling, D. Holmes: Die Programmiersprache Java (dt. Ausgabe von The Java Programming Language). Addison-Wesley 1996 („die Referenz“)
-
D. Barnes, M. Kölling: Objektorientierte Programmierung mit Java (deutsche Ausgabe von: Objects First with Java - A Practical Introduction using BlueJ). Prentice Hall / Pearson, Sept. 2003 (für Vorlesung empfohlen)
-
D. Bell, M. Parr: Java für Studenten – Grundlagen der Programmierung. Prentice Hall / Pearson, 3. Aufl. 2003 (systematischer Java-Lehrgang)
-
E.-E. Doberkat, S. Dißmann: Einführung in die objektorientierte Programmierung mit Java. Oldenbourg-Verlag, 2. Auflage 2002 (Wiener Hofzwerge betreiben Informatik)
-
H. W. Lang: Algorithmen in Java. Oldenbourg-Verlag 2003
-
Küchlin, Weber: Einführung in die Informatik – Objektorientiert mit Java
Dostları ilə paylaş: |