Technische Universität Braunschweig Dr. Werner StruckmannInstitut für Programmierung und Reaktive Systeme 24. Juli 2015

ProgrammierenÜbersicht

Programmieren IArt der Veranstaltung: Wintersemester, Bachelor, 6 LP, 2 VL + 2 UE + RechnerübungKurzbeschreibung: In der Vorlesung »Programmieren I« werden die Grundlagen der impe-rativen und objektorientierten Programmierung anhand der Programmiersprache »Java«vermittelt und in der Übung, in der die Teilnehmer kleine Programme selbstständig ent-wickeln sollen, angewendet.Stichwörter: Algorithmen und Programme, Programmiersprachen, Grundlagen der impe-rativen und objektorientierten Programmierung, Java, primitive Datentypen, Referenz-typen, Felder und Zeichenketten, Anweisungen, Klassen, Objekte, (statische) Attribute,(statische) Methoden, Konstruktoren, Vererbung, Schnittstellen, abstrakte Klassen, Bezie-hungen zwischen Klassen und Objekten, Rekursion, Ausnahmebehandlung, Programmkor-rektheit, Test von Programmen, Ein- und Ausgabe.

Termine:Beginn: Do. 23. Oktober 2014

Vorlesung: Mo. 15:00–16:30 Uhr PK 15.1Übung: Do. 08:00–09:30 Uhr PK 15.1

Sprechstunde: Mi. 10:30–11:30 Uhr IZ 244

Programmieren IIArt der Veranstaltung: Sommersemester, Bachelor, 6 LP, 2 VL + 2 UE + RechnerübungKurzbeschreibung: Der zweite Teil der Veranstaltung erweitert und vertieft die im erstenSemester erworbenen Kenntnisse. In den Übungen werden Datenstrukturen wie Listen,Bäume und Graphen sowie Such- und Sortierverfahren programmiert. Darüber hinauswerden die Grundlagen der Parallel- und der Grafikprogrammierung behandelt.Stichwörter: Strukturierung von Programmen, Vertiefung der objektorientierten Program-mierung, Aufzählungstypen, Annotationen, weiterführende Sprachkonzepte von Java, Da-tenstrukturen, generische Klassen, Listen, Bäume, Graphen, Hashverfahren, Such- undSortierverfahren, Parallelprogrammierung, Grafikprogrammierung, Überblick über C undC++, Zeiger, Mehrfachvererbung, Überladen von Operatoren, Ausblick.

Termine:Beginn: Di. 14. April 2014

Vorlesung: Di. 08:00–09:30 Uhr SN 19.1Übung: Fr. 11:30–13:00 Uhr SN 19.1

Sprechstunde: Mi. 10:30–11:30 Uhr IZ 244

Diese Datei wird im Laufe des Semesters wöchentlich aktualisiert!

Gliederung der Veranstaltung

Vorbemerkungen

1 Algorithmus und Programm1.1 Vom Algorithmus zum Programm1.2 Programmiersprachen1.3 Korrektheit, Komplexität und Entscheidbarkeit1.4 Software-Grundlagen

2 Erste Schritte in Java

3 Java: Grundlagen der Sprache3.1 Lexikalische Elemente3.2 Datentypen und Variable3.3 Ausdrücke3.4 Speicherung von Werten3.5 Anweisungen3.6 Beispiele aus der Praxis3.7 Ein Blick auf imperatives Programmieren

4 Objektorientierte Programmierung in Java4.1 Klassen, Objekte und Methoden4.2 Vererbung4.3 Modifikatoren4.4 Klassenvariable und statische Methoden4.5 Abstrakte Klassen

5 Rekursion/Funktionale Programmierung5.1 Einführung und Begriffe5.2 Beispiele rekursiver Methoden in Java5.3 Ein Blick auf funktionales Programmieren

6 Zuverlässigkeit von Programmen6.1 Behandlung von Ausnahmesituationen6.2 Grundlagen der Programmverifikation6.3 Die Zusicherungsanweisung6.4 Testen von Programmen

7 Klassen und Methoden zur Ein- und Ausgabe

– 2 –

8 Weiterführende Sprachkonzepte von Java8.1 Lokale und anonyme Klassen8.2 Weiteres zu den Wrapper-Klassen8.3 Aufzählungstypen8.4 Die Klassen String, StringBuffer und StringTokenizer8.5 Strukturierung von Programmen8.6 Annotationen

9 Java und Datenstrukturen9.1 Lineare Listen9.2 Generische Datentypen9.3 Keller und Schlangen9.4 Graphen9.5 Suchen und Sortieren9.6 Hash-Verfahren9.7 Persistenz von Daten9.8 Das Java Collections Framework

10 Grafikprogrammierung in Java10.1 Grundlagen10.2 Grafische Grundelemente10.3 Fensterklassen10.4 Ereignisse und Widgets10.5 Applets10.6 Die Swing-Klassen

11 Parallelprogrammierung in Java11.1 Das Problem des gegenseitigen Ausschlusses11.2 Grundlagen und Begriffe11.3 Verwaltung von Threads11.4 Kommunikation und Synchronisation11.5 Die speisenden Philosophen11.6 Das Concurrent-Paket

12 Ausblick12.1 Objektorientierte Programmierung: Entwurfsmuster12.2 Programmierparadigmen und -sprachen und Veranstaltungen12.3 Gegenstände der Softwaretechnik12.4 Java 8

Quellenverzeichnis

– 3 –

A Übungen, Ergänzungen, Fallstudien, WiederholungenA.1 Vom Algorithmus zum Programm: ProgrammentwicklungA.2 Algorithmen: KorrekheitA.3 Formatierung von ProgrammenA.4 Algorithmen: KomplexitätA.5 Java-OperatorenA.6 Abstraktion und ModellierungA.7 Fallstudie: Objektorientierung (Polynome)A.8 Objektorientierte Konzepte und Fallstudie (Punkte, Geraden)A.9 Fallstudie: Vererbung und abstrakte Klassen (Funktionen)A.10 Etwas Weiteres zur ObjektorientierungA.11 Weiteres Beispiel zur Frage der BerechenbarkeitA.12 Fallstudie: Rekursion, Backtracking (Sudoku, Blick auf Prolog)A.13 Ein erster Blick auf grafische OberflächenA.14 Klausur zu Programmieren IA.15 Einige Programme des JDKA.16 Abstrakte Datentypen (ADT)A.17 Fallstudie: Keller (Klammerstrukturen)A.18 Fallstudie: Graphen, Breitensuche (Zusammenhangskomponenten)A.19 Fallstudie: Mergesort, Divide-and-Conquer, GenerizitätA.20 Fallstudie: Graphen, Darstellung von Graphen (Brücken)A.21 Fallstudie: Skriptsprachen, JavaScriptA.22 Die Programmiersprache CA.23 Berechenbarkeit, formale Algorithmus-DefinitionA.24 Berechenbarkeit (2)A.25 Parallelprogrammierung: FairnessA.26 Alias-Name, Gültigkeit, Sichtbarkeit und Lebensdauer

B Themen der ÜbungsaufgabenB.1 1. ÜbungsblattB.2 2. ÜbungsblattB.3 3. ÜbungsblattB.4 4. ÜbungsblattB.5 5. ÜbungsblattB.6 6. ÜbungsblattB.7 7. ÜbungsblattB.8 8. ÜbungsblattB.9 9. ÜbungsblattB.10 10. ÜbungsblattB.11 11. ÜbungsblattB.12 12. ÜbungsblattB.13 13. ÜbungsblattB.14 14. Übungsblatt

– 4 –

VorbemerkungenInformatik als Wissenschaft; inhaltlicher Überblick über die Vorlesung; organisatorischeAspekte; Literaturempfehlungen.

1 Algorithmus und Programm1.1 Vom Algorithmus zum ProgrammAlgorithmusbegriff; Spezifikation; Eigenschaften von Algorithmen; Algorithmus und Pro-gramm; Programmiersprache; programmieren; grundlegende Aspekte der Entwicklung vonAlgorithmen: Paradigma, Komplexität, Korrektheit, Verifikation, Berechenbarkeit, Ent-scheidbarkeit, Church’sche These, Entwurf von Algorithmen, abstrakter Datentyp, Vari-anten des Algorithmusbegriffs, Hinweis auf Standardalgorithmen; Paradigmen zur Algo-rithmenbeschreibung: imperativ, funktional, objektorientiert und logisch; weitere Paradig-menbegriffe: prozedural, deklarativ, hybrid; Beispiel eines imperativen Algorithmus; derAlgorithmus von Euklid; Zustand; Zustandstransformation; Datenstrukturen; Typsystem;natürliche und künstliche Sprachen; Sprachen der Informatik.

1.2 ProgrammiersprachenEntwicklung der Programmiersprachen; Definition von Programmiersprachen; lexikalischeStruktur; Syntax; Semantik; Pragmatik; Klassifikation der Programmiersprachen: Ma-schinensprachen, Assembler und problemorientierte Sprachen; Implementierung von Pro-grammiersprachen: Interpreter, Compiler, Mischverfahren, Just-in-Time-Compiler; Verar-beitung von Java-Programmen.

1.3 Korrektheit, Komplexität und EntscheidbarkeitSpezifikation; Korrektheit; partielle und totale Korrektheit; Verifikation; Nachweis der par-tiellen und totalen Korrektheit des Algorithmus von Euklid; Schleifeninvariante; Test; Va-lidation; Komplexität; Komplexität des Algorithmus von Euklid; O-Notation, landauscheSymbole; Entscheidbarkeit; Herleitung der Komplexität eines Sortieralgorithmus; Halte-problem; Nachweis der Unentscheidbarkeit des Halteproblems; Berechenbarkeit; Existenznicht berechenbarer Funktionen.

1.4 Software-GrundlagenAufbau eines Rechners; Systemsoftware; Anwendungssoftware; Softwarewerkzeuge; Be-triebssystem; textuelle und grafische Oberfläche; wichtige Betriebssysteme; Dateiverwal-tungssystem; Editor; Programmierwerkzeuge; Programmierumgebungen.

– 5 –

2 Erste Schritte in JavaAbstraktion; Modellbildung; Beispiel: Kontoverwaltung; Klassen- und Objektdiagramm;Kommentare; Klasse; Objekt; Attribut; Methode; Parameter; Rückgabewert; Variable;Konstruktor; Applikation; main-Methode; Hinweis auf Applets; Regeln zur Code-Forma-tierung; Programmkommentare; der Dokumentationsgenerator javadoc; objektorientierteProgrammiersprachen; der Algorithmus von Euklid als statische Methode; Sprachmerk-male von Java; Entwicklung von Java; einige Java-Konzepte; einige Programme des JDK;Zusammenfassung der Einführung.

3 Java: Grundlagen der Sprache3.1 Lexikalische ElementeLexik; Lexem; Eingabezeichen; Unicode, Unicode-Transformationsformat; Ausgabe vonSystemeigenschaften; Kommentare; Dokumentationskommentare; Bezeichner (identifier);Regeln zur Wahl von Bezeichnern; Literale; Wahrheitswerte; Zahlen; Zeichen; Zeichen-ketten; Null-Literal; Schlüsselwörter; reservierte Wörter; Trennzeichen; Operatoren; Inter-punktionszeichen.

3.2 Datentypen und VariableStruktur von Java-Programmen; Übersicht über die Datentypen; primitive Datentypen:boolean, char, byte, short, int, long, float, double; Wertebereiche und Literale der primiti-ven Datentypen; Variable; Instanz- und Klassenvariable; lokale Variable; Deklaration undInitialisierung von Variablen; Zuweisung: Storage-Semantik, Assignment by sharing of refe-rences; Lebensdauer; Sichtbarkeit; Arrays; Deklaration, Allokation und Initialisierung vonArrays; mehrdimensionale Arrays; Strings; Referenztypen; Erzeugung von Objekten; Zu-weisung von Referenztypen; Vergleich von Referenztypen; Garbage Collector; die Begriffe»statisch«, »dynamisch« und »semidynamisch«; einschränkende und erweiternde Typkon-vertierungen; Typkonvertierungen für primitive Datentypen; impliziter und expliziter Cast.

3.3 AusdrückeAusdruck; Operand; Operator; Stelligkeit eines Operators; Rückgabewert; Priorität einesOperators; Linksassoziativität; Rechtsssoziativität; Seiteneffekt; Auswertungsreihenfolge;arithmetische, relationale und logische Operatoren; ganzzahlige Division; Zuweisungsopera-toren; Fragezeichen-Operator; cast-Operator; weitere Operatoren; Vorrangregeln für Ope-ratoren.

3.4 Speicherung von WertenBeispiele für fehlerhafte Rechnungen mit einem Java-Programm; Speicherung von Informa-tion; Byte Order; big endian, little endian; ASCII- und ISO-Latin-1-Zeichensatz; Unicode-Zeichensatz; Unicode-Transformations-Formate (UTF); Speicherung ganzzahliger Daten-

– 6 –

typen; Zweierkomplement; Gleitkommadarstellung reeller Zahlen und ihre Problematik;Beispiel; Summe von Zahlen unterschiedlicher Größenordnung; Auslöschung; Vergleich vonGleitkommazahlen; Java-Beispiel; Pseudoarithmetik; Speicherung von primitiven und Re-ferenztypen; schematisches Speicherbild.

3.5 AnweisungenDie Java Language Specification; Beispiele aus dem Kapitel zur Syntax; Übersicht überdie Java-Anweisungen; elementare Anweisungen; leere Anweisung; Block; Variablendekla-ration; definite assignment; Datenflussanalyse; Ausdruck als Anweisung; If- und Switch-Anweisung; While- und Do-Anweisung; abweisende und nicht abweisende Schleifen; For-Anweisung; erweiterte For-Anweisung; Break- und Continue-Anweisungen mit Marken;Return-Anweisung; Beispiele: größter Teiler einer Zahl, Primzahlberechnung, Vertauschenzweier Werte, Maximum zweier Zahlen, Maximum dreier Zahlen, Maximum eines Feldes,Summe ganzer Zahlen, Summe der Elemente eines Felds; Summe der Elemente einer Ma-trix; Betrag einer Zahl, Fakultät einer Zahl, Potenz, Fibonacci-Folge.

3.6 Beispiele aus der PraxisVertiefung der bisher behandelten Sprachkonzepte an Beispielen aus verschiedenen Ge-bieten: Berechnung von Zinseszinsen; Teilbarkeit; Darstellung einer natürlichen Zahl zueiner beliebigen Basis; schnelle Exponentiation; Horner-Schema; Skalarprodukt von Vek-toren; Länge eines Vektors; Produkt von Matrizen; Nullmatrix; Beispiel zu Break- undContinue-Anweisungen mit Marken; Newton-Verfahren zur Nullstellenbestimmung; Bub-blesort; Erzeugung von Pseudozufallszahlen mit der linearen Kongruenzmethode.

3.7 Ein Blick auf imperatives ProgrammierenVariable; Zustand; Wertzuweisung; Sequenz; Selektion; Iteration; Ein- und Ausgabe; Zu-stand eines Objekts; Zustand des Programms; der Algorithmus von Euklid in imperativerFassung in den Sprachen Java, JavaScript, Pascal, C, Modula-2 und Scheme; Ausblick aufKonzepte imperativer Programmiersprachen: Funktionen, Prozeduren, Datentypen, Mo-dule, Ausnahmebehandlung, Parallelverarbeitung; Algorithmus von Euklid: imperative vs.funktionale Version, funktionale Variante in Scheme und Haskell.

4 Objektorientierte Programmierung in Java4.1 Klassen, Objekte und MethodenObjekt; Zustand; statische und dynamische Eigenschaften; Schnittstelle; Dienst eines Ob-jekts; Nachricht; wert- und identitätsbasierte Objektmodelle; Kapselung und Geheimnis-prinzip; Abstraktion und Modellierung; Klasse; Objekt; Instanz; Methode; Memberva-riable; Instanzvariable; Attribut; Erzeugung und Initialisierung von Objekten; Deklara-tion von Variablen und Methoden; Zuweisung von Objekten; Semantik von Variablenund Zuweisungen; Storage-Semantik; Assignment-by-sharing; Parameter einer Methode;

– 7 –

Aufruf einer Methode; Punktnotation; this-Zeiger; Parameterübergabe; Rückgabewert ei-ner Methode; Überladen von Methoden; Signatur einer Methode; Konstruktoren; Default-Konstruktor; Verkettung von Konstruktoren; Destruktoren; get-/set-Methoden; toString;equals; typischer Aufbau einer Klasse; Beispiele: Adresskartei, Horner-Schema, Aufruf vonMethoden, Bubblesort, Newton-Verfahren, Methoden mit einer variablen Parameterzahl;Fallstudie: Polynomarithmetik.

4.2 VererbungBeziehungen zwischen Klassen; Vierecke und ihre Beziehungen; einfache Vererbung; Basis-klasse; Oberklasse; abgeleitete Klasse; Unterklasse; Spezialisierung; Generalisierung; Zu-weisungen; Polymorphie; Verdecken von Variablen; Überlagern von Methoden; dynamischeMethodensuche; die super-Notation; die Klasse Object; die Methode String toString();die Methode boolean equals(); die Methode Object clone(); Konstruktoren; der Su-perklassenkonstruktor; Reihenfolge der Aufrufe von Konstruktoren; finale Klassen; Ver-erbungshierarchien; Vererbungshierarchien als gerichtete Bäume; mehrfache Vererbung;Klassendiagramm; Objektdiagramm; Beziehungen zwischen Klassen und Objekten: derinstanceof-Operator; Beziehungen zwischen Objekten: Assoziation, Kardinalität, Multi-plizität, Aggregation, Komposition.

4.3 ModifikatorenModifikator; die Modifikatoren public, final und abstract für Klassen; die Modifikato-ren public, private, protected, static, final und abstract für Variable und Metho-den; Bemerkungen zum Einsatz von Modifikatoren; Hinweis auf weitere Modifikatoren.

4.4 Klassenvariable und statische MethodenKlassenvariable; Deklaration und Zugriff; Beispiel: Objektzähler; Konstante; Klassenme-thoden; Deklaration und Zugriff; Beispiele: Objektzähler, Tabelle der Quadratwurzeln; dieMethode main und ihr Argument; statische Konstruktoren; utility class.

4.5 Abstrakte KlassenAbstrakte und konkrete Methoden; abstrakte und konkrete Klassen; Fallbeispiel für ab-strakte Klassen und Polymorphismus: Gehaltsberechnung; polymorphe Methoden in Kon-struktoren.

5 Rekursion/Funktionale Programmierung5.1 Einführung und BegriffeRekursives Konzept; Fakultät; Motivierendes Beispiel: Berechnung der Quersumme ei-ner natürlichen Zahl durch eine iterative und eine rekursive Methode; partielle und tota-le Funktionen; Definitionsbereich; Möglichkeiten zur Definition von Funktionen: Tabelle,

– 8 –

Ausdruck; rekursive Definitionen; Ersetzungssystem; Auswertung; Formen der Rekursion:lineare Rekursion, Endrekursion, Baumrekursion, geschachtelte Rekursion, verschränkteoder wechselseitige Rekursion; Beispiele: Fakultät, Fibonacci-Folge, Algorithmus von Eu-klid, schnelle Exponentiation, Summe, Skalarprodukt; dynamische Algorithmen; operatio-nelle und denotationale Semantik einer rekursiven Definition; Innermost-, Outermost- undMixed-Auswertung; Ackermann-Funktion.

5.2 Beispiele rekursiver Methoden in JavaFallbeispiele rekursiver Methoden: Newton-Verfahren, Intervallschachtelung (Bisektion),Geldwechsel, Türme von Hanoi, das Acht-Damen-Problem; der Fragezeichen-Operator;for-Anweisungen mit Initialisierungs- und Update-Listen; Wiederholung des Bubblesort-Algorithmus; Quicksort; Wrapper-Klassen der primitiven Datentypen; einige Konstrukto-ren und Methoden der Wrapper-Klassen; Autoboxing und Unboxing.

5.3 Ein Blick auf funktionales ProgrammierenFunktionen höherer Ordnung; funktionale Algorithmen; funktionale Programmiersprachen;Lisp und Scheme; funktionale Version des Algorithmus von Euklid; Haskell; Algorithmusvon Euklid in Scheme und Haskell; Zusammenfassung der Aspekte.

6 Zuverlässigkeit von ProgrammenMotivation.

6.1 Behandlung von AusnahmesituationenDie Ausnahmen ArithmeticException und ArrayIndexOutOfBoundsException; Behand-lung von Ausnahmen; Beispiele für Ausnahmen; grundlegende Begriffe: Ausnahme, Auslö-sen einer Ausnahme, Behandeln einer Ausnahme; die try-catch-Anweisung; prinzipielleVorgehensweise; die Methode parseInt; Beispiel: Zahldarstellung zu verschiedenen Basen;Fehlerobjekte; Fortsetzen nach einer Ausnahme; mehrere catch-Klauseln; die finally-Klausel; die catch-or-throw-Regel; Weitergabe einer Ausnahme; die throws-Klausel; dieKlassen Throwable, Error, Exception, RuntimeException und ArithmeticException;die throw-Anweisung; Erzeugen und Auslösen von Ausnahmen; eigene Fehlerklassen; Bei-spiele; wichtige Javadoc-Markierungen.

6.2 Grundlagen der ProgrammverifikationHoare’sche Logik; Hoare’scher Kalkül; Nachbedingung; Vorbedingung; Schleifeninvariante;Axiomenschema; Ableitungsregeln; Zustand; partielle und totale Korrektheit; Korrektheitund relative Vollständigkeit des Kalküls; Beispiele: ganzzahlige Division mit Rest, schnelleExponentiation; abessinische Bauernmethode zur Multiplikation ganzer Zahlen.

– 9 –

6.3 Die ZusicherungsanweisungDie assert-Anweisung; Aufruf des Compilers und des Interpreters; Anwendungen derassert-Anweisung; Beispiel: ganzzahlige Division mit Rest; Anwendung in öffentlichenMethoden; Anwendung in privaten Methoden; Nachbedingungen; Vorbedingungen; Schlei-feninvariante; Kontrollflussinvariante; komplexe Zusicherungen; Klasseninvariante; beding-te Übersetzung; Ausschalten von Zusicherungen; Seiteneffekte; Einschalten von Zusiche-rungen.

6.4 Testen von ProgrammenPhasen der Software-Entwicklung; Modelle der Software-Entwicklung; Dokumente; Mo-dellierungssprachen; UML; Struktur- und Verhaltensdiagramme; Werkzeuge; Spezifikati-on; Verifikation; Sicherheits- und Lebendigkeitseigenschaften; Validierung; Test; systema-tisches Testen; Modultest; Integrationstest; Auswahl der Testdaten; Black- und White-Box-Tests; Überdeckungsmaße für White-Box-Tests; JUnit: Einführung mit Beispiel.

7 Klassen und Methoden zur Ein- und AusgabeMöglichkeiten zur Ein- und Ausgabe von Daten; Grundlagen; wahlfreier und sequentiellerZugriff; Streams; Byte- und Character-Streams; Öffnen und Schließen einer Datei; Brücken-klassen; die Stream-Basisklassen; die Klasse PrintStream; die Klasse System; die Methodeexit; System.out, System.in und System.err; Properties; Ausgabe auf dem Bildschirm;Ausgabe in eine Datei; Eingabe von der Tastatur; Lesen aus einer Datei; Pufferung derEin- und Ausgabe; die Klasse File; Transaktion; Anlegen und Löschen einer Datei; Zu-griff auf den Pfadnamen; Informationen über eine Datei; Ändern von Verzeichniseinträgen;Beispiel: rekursiver Durchlauf durch ein Verzeichnis; formatierte Ausgabe; Formatstring;Steuerzeichen; die Klasse Scanner.

8 Weiterführende Sprachkonzepte von Java8.1 Lokale und anonyme KlassenLokale Klassen; Definition und Benutzung lokaler Klassen; Beispiel; statische lokale Klas-sen; anonyme Klassen; Beispiel; Realisierung von Funktionen höherer Ordnungen durchSchnittstellen; Beispiel für anonyme Klassen; Erweiterung des new-Operators; Anwendunglokaler und anonymer Klassen.

8.2 Weiteres zu den Wrapper-KlassenWiederholung der Datentypen; Wrapper-Klassen zu den primitiven Datentypen; Konstruk-toren der Wrapper-Klassen; Wertrückgabe; parse-Methoden; Konstante und weitere Me-thoden; die Klasse Integer als Beispiel; Autoboxing und Unboxing.

– 10 –

8.3 AufzählungstypenMotivation; Aufzählungstypen; Enum-Klassen; Eigenschaften und Methoden der Aufzäh-lungstypen; selbstdefinierte Methoden in Enum-Klassen; Datenfelder in Enum-Klassen;Enum-Konstruktoren; Anwendungsmöglichkeiten für Enum-Klassen; Beispiel: Berechnungdes Wochentags eines gegebenen Datums.

8.4 Die Klassen String, StringBuffer und StringTokenizerWiederholung und Erweiterung der Klasse String; Konstruktoren; Methoden zur Zei-chenextraktion, zum Vergleich, zum Suchen und Ersetzen sowie Konvertierungsfunktionen;die Klasse StringBuffer; Unterschiede zur Klasse String; Konstruktoren; einige Metho-den der Klasse StringBuffer; Beipiel: Effizienzsteigerung bei häufiger Konkatenation; dieKlasse StringTokenizer; Konstruktoren und einige Methoden; Beispiel.

8.5 Strukturierung von ProgrammenProgrammelemente von Java; Pakete; Applikationen; Applets; Verwendung von Paketen;qualifizierter und unqualifizierter Import; statischer Import; das Paket java.lang; wichtigeJava-Pakete; Klassen des Pakets java.util; Bedeutung der Paketnamen; Erstellen eige-ner Pakete; Verzeichnisstruktur der Pakete; das Default-Paket; Zugriffsrechte für Klassen,Methoden und Variable; die CLASSPATH-Variable.

8.6 AnnotationenAnnotation; Metainformation; Annotationsprozessor; reflektive Auswertung; annotierteProgrammelemente; Annotationen vs. Kommentare vs. Modifikatoren; die vordefinier-ten Annotationen @Deprecated, @Override, @SuppressWarnings, @Retention, @Target,@Documented und @Inherited; Erstellung von Annotationen; Beispiel.

9 Java und Datenstrukturen9.1 Lineare ListenDefinition und grundlegende Eigenschaften linearer Listen; typische Listenoperationen; „li-neare Liste“ als abstrakter Datentyp; Schnittstelle und Implementierung des abstraktenDatentyps; Strukturinvariante; ausführliche Herleitung der insert-Methode mit Erhal-tung der Strukturinvariante; modifizierte Schnittstelle mit zugehöriger Implementierung;Behandlung von Elementklassen; Implementierung durch Felder; sortierte Listen; alterna-tive Implementierung mit Zeiger auf das erste Element und Zusatzinformationen; Senti-nel; Aufzählungen; Implementierung und Anwendung von Aufzählungen; zirkuläre Listen;die Josephus-Funktion; Implementierung von Datenstrukturen; Wiederholung: die KlasseObject; die Klasse Class; Kopieren von Objekten; flache und tiefe Kopien; die Methodeclone() der Klasse Object; die Schnittstelle Cloneable; Kopieren einer Liste; unverän-derliche Klassen.

– 11 –

9.2 Generische DatentypenWiederverwendbarkeit (reusability); Generizität; generische Methoden; generische Klas-sen; generische Schnittstellen; Beispiel: lineare Listen; die Klasse Number; Typebounds;Klassen als Typebounds; Schnittstellen als Typebounds; Klassen und Schnittstellen alsTypebounds; Wildcards; Invarianz; Bivarianz; Kovarianz; Kontravarianz; Übersicht; er-laubte Operationen; Wiederholung: Typkompabilität; Generizität in Java; Zusammenstel-lung kompatibler Datentypen; Kovarianz bei Array-Typen.

9.3 Keller und SchlangenKeller; LIFO-Prinzip; Anwendungen; Kelleroperationen; Implementierung eines Kellersdurch eine Liste; Implementierung eines Kellers durch ein Feld; Schlangen; FIFO-Prinzip;Anwendungen; Operationen für Schlangen; Implementierung einer Schlange durch eine Lis-te; Implementierung einer Schlange durch ein Feld; Deques; Bemerkungen zur Java-API.

9.4 GraphenGraph; Knoten; Kante; gerichteter Graph; ungerichteter Graph; bewerteter Graph; Mehr-fachkante; Zyklus; Schlinge; Attribute; Anwendungsbeispiele; Adjazenz; Grad eines Kno-tens; Pfad; Zusammenhang; vollständiger Graph; gewichteter Graph; Speicherung von Gra-phen: Kantenliste, Knotenliste, Adjazenzmatrix, Adjazenzliste; Komplexität der Operatio-nen; Variationen dieser Möglichkeiten.

9.5 Suchen und SortierenBaum; Definition; Wurzel; innerer Knoten; Blatt; Pfad; Tiefe; Anwendungen von Bäu-men; Anzahl der Knoten in einem Binärbaum; Durchlauf durch einen Binärbaum; binäreSuchbäume und ihre Implementierung; Sortieren mit binären Suchbäumen; Erzeugung vonZufallszahlen; Mergesort; Wiederholung: Bubblesort, Quicksort.

9.6 Hash-VerfahrenGrundlagen; Hash-Funktion; Hash-Tabelle; Kollision; Beispiel; Behandlung von Kollisio-nen; Hash-Verfahren ohne Überlaufbereich; lineare Verschiebung; quadratische Verschie-bung; Hash-Verfahren mit linearer Liste als Überlaufbereich; die Klasse Hashtable; dieKlasse HashMap; Dictionary: assoziativer Speicher.

9.7 Persistenz von DatenPersistenz von Daten; Serialisierung und Deserialisierung von Objekten; der Modifika-tor transient; die Schnittstelle Serializable; Anwendungen: Schreiben und Lesen vonObjekten in bzw. aus Dateien; tiefes Kopieren durch Serialisierung; Versionierung von se-rialisierten Daten; das Programm serialver; dynamisches Laden von Klassen; Beispieleaus dem Paket java.lang.reflect.

– 12 –

9.8 Das Java Collections FrameworkKollektionen; Mengen; Relationen; Funktionen; das Java Collections Framework; Überblicküber wichtige Schnittstellen, Implementierungen (abstrakte, konkrete Klassen) und Algo-rithmen: Collection, AbstractCollection, AbstractList, AbstractSet, AbstractMap,Set, SortedSet, List, Queue, Deque, Map, SortedMap, Stack, Vector, TreeSet, HashMap,Iterable, Iterator, ListIterator; Anwendung: sortierte endliche Mengen am Beispiel„Lottotipp“; Comparator; die Kollektion-Algorithmen; Beispiel: die Klasse ArrayList;ArrayList und LinkedList im Vergleich; kurzer Blick auf Heaps; Prioritätsschlangen;die Klasse PriorityQueue.

10 Grafikprogrammierung in Java10.1 GrundlagenSchnittstelle für Anwenderprogramme; API; das Abstract Window Toolkit (AWT); dieSwing-Bibliothek; Hinweis auf das Standard Window Toolkit (SWT); Möglichkeiten desAWTs; grundsätzliche Vorgehensweise; der grafische Kontext; Beispiel: ein einfaches Fens-ter; Ein-Ausgabe-Programmierung; ereignisgesteuerte Programmierung; Delegation BasedEvent Handling; Quelle eines Ereignisses; Beobachter; Single-Cast-Ereignis; Multi-Cast-Ereignis; Schließen eine Fensters; Adapter-Klassen; die Klasse WindowAdapter als Beispiel.

10.2 Grafische GrundelementeDas grafische Koordinatensystem; Benutzerbereich eines Fensters; Auswahl elementarerGrafikroutinen zur Darstellung von Text, Linien, Rechtecken, Polygonen, Ellipsen undEllipsenbögen; Schriftarten; Schriften mit Serifen; serifenlose Schriften; Schriften mit va-riabler und konstanter Zeichenbreite; Fett- und Kursivdruck; Methoden zur Ermittlungvon Font-Informationen und -Metriken; das RGB-Farbmodell; vordefinierte Farben; ge-bräuchliche Farbwerte; Erzeugung und Verwendung von Farben; die Klasse SystemColor.

10.3 FensterklassenDie Behälterklassen Component, Container, Applet, Window und Frame; Aufrufen undSchließen eines Fensters; Eigenschaften eines Fensters.

10.4 Ereignisse und WidgetsEreignis; Ereignisquelle; Beobachter; ereignisgesteuerte Programmierung; Single-Cast- undMulti-Cast-Ereignis; Adapter-Klasse; Überblick über die Ereignisklassen und Beobachter-Schnittstellen; Low-Level-Events; Widget; wichtige Widgets; Beispiele: Rollbalken, Label,Button, Textfeld, Checkbox, Checkboxgroup, Choice; Realisierung von Widgets.

– 13 –

10.5 AppletsAnwendungen und Applets; Eigenschaften von Applets; Beispiel; grundlegende Methoden;Umwandlung zwischen Anwendungsprogrammen und Applets; Beispiel.

10.6 Die Swing-KlassenDie Java Foundations Classes; AWT und Swing im Vergleich; der Peer-Ansatz; leicht- undschwergewichtige Komponenten; einfaches Beispiel mit AWT- und Swing-Klassen; Ein-ordnung der Swingklassen; die Komponentenklassen Component, Container, JComponent,FlowLayout, BorderLayout, GridLayout, Graphics, JLabel, AbstractButton, JRadioButton, JComboBox, JList, JTextComponent, JScrollPane, JPanel, JProgressBar; dieBehälterklassen JFrame, JWindow, JDialog, JApplet, JMenuBar, JToolBar, Border; Bor-derFactory, Vorgehensweise zur Erstellung von grafischen Oberflächen; Adapterklassen;Strukturierung von Behälter- und Beobachterklassen; Beispiel: Fenster mit Menü- undWerkzeugleiste. Einige weitere Swing-Klassen/Schnittstellen. Zum Beispiel JFileChooser.

11 Parallelprogrammierung in Java11.1 Das Problem des gegenseitigen AusschlussesVarianten des Algorithmusbegriffs: terminierend, nichtterminierend (reaktiv), determinis-tisch, nichtdeterministisch, approximativ, determiniert, randomisiert, sequenziell, parallel,verteilt; Einstieg in die Parallelprogrammierung; ein paar Aspekte zur Programmierungvon Nebenläufigkeit: Prozessverwaltung; Kommunikation zwischen Prozessen; Synchroni-sation von Prozessen; Eigenschaften; Sicherheit, Lebendigkeit, Fairness; das Problem desgegenseitigen Ausschlusses; elementare Aktion; Ausführung paralleler Prozesse; interlea-ving semantics; Beispiel: Betriebsmittelzuweisung; Abstraktion des Problems; verschiede-ne Lösungsansätze; Szenarium; Sicherheitseigenschaft; Lebendigkeitseigenschaft; Verklem-mung; Verschwörung; der Algorithmus von Dekker; aktives Warten.

11.2 Grundlagen und BegriffeProzess; Thread; leicht- und schwergewichtige Prozesse; sequentielle und parallele Ver-arbeitung; Parallelität; Quasi-Parallelität; Nebenläufigkeit; unabhängige und gekoppel-te Anweisungen und Prozesse; Beispiele; Prozessverwaltung; Erzeugen und Beenden vonProzessen; Kommunikation; gemeinsame Variable; Nachrichtenaustausch; Synchronisation;synchrone und asynchrone Arbeitsweise; Konzepte zur Nebenläufigkeit in Programmier-sprachen; Semaphore; Monitore; Standardaufgaben der Parallelprogrammierung; Erzeuger-Verbraucher-Problem; Leser-Schreiber-Problem; Problem der speisenden Philosophen; ei-nige Fairness Begriffe; Nebenläufigkeit in Java.

– 14 –

11.3 Verwaltung von ThreadsDie Klasse Thread; Erzeugung eines Threads durch Überlagerung von run; die Methodestart; Ende einer Anwendung; Dämonen; als “deprecated” gekennzeichnete Methoden;Transaktionen; Beenden eines Threads; weitere Methoden der Klasse Thread; Lebenszykluseines Threads; die Schnittstelle Runnable; Beispiel.

11.4 Kommunikation und SynchronisationKommunikation durch gemeinsame Variable; Synchronisation durch Monitore; Beispiel:Bankbetrieb und verlorene Buchungen; der Modifikator synchronized; synchronisierteMethoden und Blöcke; Sperren für Objekte und Klassen; Grundregel zur Synchronisati-on; Wartemenge eines Objekts; die Methoden wait und notify; Fairness; der Modifika-tor volatile; weak/strong transition/process fairness; Lösung des Erzeuger-Verbraucher-Problems; die Methode notifyAll; Beispiel: Parkhausbetrieb; Priorität eines Threads;Thread-Gruppen; Übersicht über die Methoden der Klasse Object; Programmierrichtlini-en zur Parallelprogrammierung.

11.5 Die speisenden PhilosophenProblemstellung; Lösung in Java mit wait und notifyAll.

11.6 Das Concurrent-PaketÜberblick; die Schnittstellen und Klassen Executor, Executors und ExecutorService;das Erzeuger-Verbraucher-Problem; die Schnittstellen und Klassen Lock, ReentrantLockund Condition; die Klasse ArrayBlockingQueue; die Klasse Semaphore; Nachrichtenaus-tausch; das Rendez-Vous-Konzept; Hinweis auf die Synchronizer-Klassen (zum BeispielExchange), das Unterpaket atomic und die „Concurrent Collections“; Zusammenfassung:Programmierung von Nebenläufigkeit.

12 Ausblick12.1 Objektorientierte Programmierung: EntwurfsmusterEntwurfsmuster/Design Pattern; Beispiele: die Entwurfsmuster „Singleton“, „Immutable“und „Observer“.

12.2 Programmierparadigmen und -sprachen und VeranstaltungenAnnotationen; Wiederholung der imperativen, funktionalen und objektorientierten Pro-grammierparadigmen (s. Abschnitte 1.1, 1.2, 3.7, 5.3); funktionale Programme in Scheme;das deduktive (logische) Paradigma; Fakt; Regel; Horn-Klausel; Anfrage; Ziel; kleine Bei-spiele in Prolog; Funktionen und Relationen; deklaratives Programmieren; wichtige Pro-grammiersprachen im Überblick; Veranstaltungen zur Programmierung.

– 15 –

12.3 Gegenstände der SoftwaretechnikDer Begriff „Softwaretechnik“; Software-Entwicklung; Software-Management; Software-Qualitätssicherung; die Modellierungssprache UML (Unified Modeling Language); die Dia-grammtypen der UML; Anwendungsfalldiagramm; Klassendiagramm; Objektdiagramm;Sequenzdiagramm.

12.4 Java 8Java-Entwicklung; Java-8: Closures, Lambda-Projekt.

– 16 –

Quellenverzeichnis[1] Alagić, Suad; Arbib, Michael A.: The Design of Well-Structured and Correct Pro-

grams. New York: Springer Verlag, 1978

[2] Alber, Klaus; Struckmann, Werner: Einführung in die Semantik von Program-miersprachen. Mannheim Wien Zürich: BI-Wissenschaftsverlag, 1988

[3] Barnes, David J.; Kölling, Michael: Objects First With Java. 1. Auflage. Harlow,England: Prentice Hall, 2003

[4] Bell, Douglas; Parr, Mike: Java für Studenten. 3. Auflage. München: PearsonStudium, 2003

[5] Ben-Ari, Mordechai: Grundlagen der Parallelprogrammierung. 1. Auflage. MünchenWien: Carl Hanser Verlag, 1985

[6] Ben-Ari, Mordechai: Principles of Concurrent and Distributed Programming. 2. Auf-lage. Harlow London: Addison-Wesley, 2006

[7] Bentley, Jon: Programming Pearls. Reading, Massachusetts: Addison-Wesley Pu-blishing Company, 1986

[8] Bloch, Joshua; Gafter, Neal: Java Puzzlers. 1. Auflage. Upper Sadle River NJ,Boston: Addison-Wesley Verlag, 2005

[9] Breymann, Ulrich: C++ – Einführung und professionelle Programmmierung. 9., neubearbeitete Auflage. München: Hanser Verlag, 2007

[10] Budd, Timothy: Classic Data Structures in Java. 1. Auflage. Boston: Addison-WesleyVerlag, 2001

[11] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford:Algorithmen –Eine Einführung. 3., überarb. u. erw. Auflage. München Wien: Olden-bourg Verlag, 2010

[12] Deitel, Harvey M.; Deitel, Paul J.: Java—How to Program. 6. Auflage. UpperSaddle River, New Jersey: Pearson Education International, 2005

[13] Duden: Informatik. 4. Auflage. Mannheim: Dudenverlag, 2006

[14] Ehrenberger, Wolfgang: Software-Verifikation. 1. Auflage. München: Hanser Ver-lag, 2002

[15] Esser, Friedrich: Java 6 Core Techniken. 1. Auflage. München: Oldenbourg Verlag,2008

[16] Esser, Friedrich: Scala für Umsteiger. München: Oldenbourg Verlag, 2011

– 17 –

[17] Ford, William H.; Topp, William R.: Data Structures with Java. 1. Auflage. UpperSaddle River, New Jersey: Pearson Education International, 2005

[18] Gallenbacher, Jens: Abenteuer Informatik. 2. Auflage. Heidelberg: SpektrumAkademischer Verlag, 2008

[19] Gamma, Erich; Helm, Richard; Johnson, Ralph; Vlissides, John: Design Patterns.1. Auflage. Boston: Addison-Wesley Verlag, 1995

[20] Harel, David; Feldman, Yishai: Algorithmik. 1. Auflage. Berlin Heidelberg NewYork: Springer-Verlag, 2006

[21] Henning, Peter A.; Vogelsang, Holger: Taschenbuch Programmiersprachen. 2. Auf-lage. München: Carl Hanser Verlag, 2007

[22] Hoffmann, Dirk W.: Theoretische Informatik. 1. Auflage. München: Hanser Verlag,2009

[23] Hohlfeld, Bernhard; Struckmann, Werner: Einführung in die Programmverifika-tion. Mannheim Wien Zürich: BI-Wissenschaftsverlag, 1992

[24] Kecher, Christoph: UML 2. 3., durchgesehene Auflage. Bonn: Galileo Press, 2009

[25] Krienke, Rainer: Shell-Programmierung für Unix und Linux. 3., erweiterte Auflage.München: Hanser Verlag, 2007

[26] Krüger, Guido: Handbuch der Java-Programmierung. 7. Auflage. München:Addison-Wesley Verlag, 2012

[27] Krüger, Guido; Hansen, Heiko: Java-Programmierung – Das Handbuch zu Java 8.8. Auflage. Köln: O’Reilly Verlag, 2014

[28] Lahres, Bernhard; Raýman, Gregor: Objektorientierte Programmierung. 2., aktua-lisierte und erweiterte Auflage. Bonn: Galileo Computing, 2009

[29] Lang, Hans W.: Algorithmen in Java. 2. Auflage. München: Oldenbourg Wissen-schaftsverlag, 2006

[30] Lewis, John; Chase, Joseph: Java—Software Structures. 2. Auflage. Upper SaddleRiver, New Jersey: Pearson Education International, 2005

[31] Louis, Dirk; Müller, Peter: Java — Der umfassende Programmierkurs. Köln:O’Reilly Verlag, 2014

[32] Mehlhorn, Kurt; Sanders, Peter: Algorithms and Data Structures. 1. Auflage.Berlin Heidelberg: Springer Verlag, 2008

[33] Nowak, Johannes: Fortgeschrittene Programmierung mit Java 5. 1. Auflage. Heidel-berg: Dpunkt Verlag, 2005

– 18 –

[34] Oechsle, Rainer: Parallele und verteilte Anwendungen in Java. 2., vollständig über-arbeitete und erweiterte Auflage. München: Carl Hanser Verlag, 2007

[35] Ottmann, Thomas; Widmayer, Peter: Algorithmen und Datenstrukturen. 4. Auf-lage. Heidelberg Berlin: Spektrum Akademischer Verlag, 2002

[36] Pomberger, Gustav; Dobler, Heinz: Algorithmen und Datenstrukturen. 1. Auflage.München: Pearson Studium, 2008

[37] Ratz, Dietmar; Scheffler, Jens; Seese, Detlef; Wiesenberger, Jan: GrundkursProgrammieren in Java. 6. aktualisierte und erweiterte Auflage. München Wien:Hanser Verlag, 2011

[38] Ratz, Dietmar; Scheffler, Jens; Seese, Detlef; Wiesenberger, Jan: GrundkursProgrammieren in Java. 7. überarbeitete und erweiterte Auflage. München Wien:Hanser Verlag, 2014

[39] Rechenberg, Peter: Was ist Informatik? 3. Auflage. München: Hanser Verlag, 2000

[40] Regionales Rechenzentrum für Niedersachsen RRZN (Hrsg.): Linux – Nut-zung mit der grafischen Oberfläche KDE. 1. Auflage. Hannover: Regionales Rechen-zentrum für Niedersachsen RRZN, 2000

[41] Regionales Rechenzentrum für Niedersachsen RRZN (Hrsg.): Grundlagender Programmierung. 4. Auflage. Hannover: Regionales Rechenzentrum für Nieder-sachsen RRZN, 2004

[42] Regionales Rechenzentrum für Niedersachsen RRZN (Hrsg.): Unix – EineEinführung in die Benutzung. 18. Auflage. Hannover: Regionales Rechenzentrum fürNiedersachsen RRZN, 2008

[43] Regionales Rechenzentrum für Niedersachsen RRZN (Hrsg.): Java 6(1. Band). 7. Auflage. Hannover: Regionales Rechenzentrum für Niedersachsen RRZN,2009

[44] Regionales Rechenzentrum für Niedersachsen RRZN (Hrsg.): Java 6(2. Band). 2. Auflage. Hannover: Regionales Rechenzentrum für Niedersachsen RRZN,2011

[45] Saake, Gunter; Sattler, Kai-Uwe: Algorithmen und Datenstrukturen. 4., über-arb. Auflage. Heidelberg: dpunkt.verlag, 2010

[46] Schiedermeier, Reinhard: Programmieren mit Java. 2., aktualisierte Auflage. Mün-chen: Pearson Studium, 2010

[47] Schiedermeier, Reinhard; Köhler, Klaus: Das Java-Praktikum. 1. Auflage. Hei-delberg: Dpunkt Verlag, 2008

[48] Sedgewick, Robert: Algorithms. 2. Auflage. Reading, Mass.: Addison-Wesley, 1988

– 19 –

[49] Sedgewick, Robert: Algorithmen in Java, Teil 1–4. 3. überarbeitete Auflage. Mün-chen: Addison-Wesley Verlag, Pearson Studium, 2003

[50] Sedgewick, Robert: Algorithms in Java, Part 5. 3. Auflage. Boston: Addison-WesleyVerlag, 2004

[51] Struckmann, Werner; Wätjen, Dietmar: Mathematik für Informatiker – Grund-lagen und Anwendungen. 1. Auflage. Heidelberg: Spektrum Akademischer Verlag,2007

[52] Vogt, Carsten: C für Java-Programmierer. 1. Auflage. München: Hanser Verlag,2007

[53] Weinert, Albrecht: Java für Ingenieure. 1. Auflage. München: FachbuchverlagLeipzig im Carl-Hanser-Verlag, 2001

[54] Weiss, Mark A.: Data Structures & Problem Solving Using Java. 3. Auflage. Boston:Pearson Addison Wesley, 2006

[55] Weiss, Mark A.: Data Structures and Algorithm Analysis in Java. 2. Auflage. Boston:Pearson Addison Wesley, 2007

[56] Zeller, Andreas; Krinke, Jens: Programmierwerkzeuge. 1. Auflage. Heidelberg:Dpunkt Verlag, 2000

– 20 –

A Übungen, Ergänzungen, Fallstudien, WiederholungenA.1 Vom Algorithmus zum Programm: ProgrammentwicklungDas Sieb des Eratosthenes als Beispiel für Programmentwicklung; Struktogramm (Nassi-Shneiderman-Diagramm); Programmablaufplan (PAP); der Zyklus der Programmentwick-lung; Eingabe (Kommandozeile, Tastatur, Programm) und Ausgabe (Bildschirm); einfüh-rendes Beispiel für Makefile.

A.2 Algorithmen: KorrekheitSpezifikation, Verifikation, partielle und totale Korrektheit: Algorithmus zur Division vonnatürlichen Zahlen; Algorithmus von Euklid.

A.3 Formatierung von ProgrammenRichtlinien mit Begründung zur Formatierung von Java-Programmen.

A.4 Algorithmen: KomplexitätWiederholung: Berechnung der Komplexitäten eines Algorithmus: Insertionsort; Landau-Symbole.

A.5 Java-OperatorenWiederholung; Überblick; Beispiele.

A.6 Abstraktion und ModellierungAbstraktion; Modellierung; Modellfehler; Datenfehler; Verfahrensfehler; Rundungsfehler;Numerik; Stabilität eines Algorithmus; Kondition eines Problems; Auslöschung; Lösungquadratischer Gleichungen.

A.7 Fallstudie: Objektorientierung (Polynome)Grundlagen der Objektorientierung; Klasse, Objekt, Attribut, Methode; Typischer Aufbaueiner Klasse; Überlagerung von Methoden der Klasse Object; Beispiel zur objektorientier-ten Programmierung ohne Vererbung: Polynomarithmetik (Schiedermeier, Köhler).

A.8 Objektorientierte Konzepte und Fallstudie (Punkte, Geraden)Grundlagen der Objektorientierung; Klasse, Objekt, Attribut, Methode; Zustand; Nach-richt; Klassen- und Objektdiagramme; Typischer Aufbau einer Klasse; Überlagerung vonMethoden der Klasse Object; Beziehungen zwischen Klassen: Vererbung; Beziehungen zwi-schen Klassen und Objekten: der instanceof-Operator; Beziehungen zwischen Objekten:

– 21 –

Assoziation, Multiplizität, Kardinalität, Aggregation, Komposition; Beispiel zur objektori-entierten Programmierung ohne Vererbung: Klassen für Punkte und Geraden; Erwähnungvon UML-Diagrammen.

A.9 Fallstudie: Vererbung und abstrakte Klassen (Funktionen)Verwendung abstrakter Klassen; Ebenen der Realisation; die abstrakte Klasse Funktion;verschiedene Realisierungen: Parabel, Hyperbel, Verkettung von Funktionen; Wiederho-lung: Diamond-Problem, Erwähnung von Mixin und Trait.

A.10 Etwas Weiteres zur ObjektorientierungDie Objektorientierung wird nicht in allen Sprachen identisch angeboten. Beispiel: Es gibtOO-Konstrukte, die Java nicht anbietet. Beispiele: Mixin, Trait.

A.11 Weiteres Beispiel zur Frage der BerechenbarkeitDiophantische Gleichungen.

A.12 Fallstudie: Rekursion, Backtracking (Sudoku, Blick auf Prolog)Rekursion am Beispiel „Sudoku“; Backtracking; packages; import-/package-Anweisung;Version mit Ausgabe aller Zwischenzustände; Beispiel in Prolog.

A.13 Ein erster Blick auf grafische OberflächenZeichnen von Funktionen, Kakuro.

A.14 Klausur zu Programmieren IErläuterung einer Musterlösung

A.15 Einige Programme des JDKJDK: Überblick; javac (Compiler); java (Interpreter); appletviewer (Appletviewer); jdb(Debugger); javadoc (Dokumentationsgenerator); jar (Archivierungswerkzeug); javap(Disassembler); serialver (Versionierung serialisierter Daten); native2ascii (Änderungder Kodierung).

A.16 Abstrakte Datentypen (ADT)Einsortige und mehrsortige Algebren: Gruppe, Körper, Vektorraum; Datentyp: Signatur,Axiom, Algebra; algebraische Spezifikation; abstrakte Datentypen (ADT); Kapselung; Ge-heimnisprinzip; Beispiele: Listen, Keller, Warteschlangen.

– 22 –

A.17 Fallstudie: Keller (Klammerstrukturen)Überprüfung von Klammerstrukturen nach [54]; die Klasse PushBackReader.

A.18 Fallstudie: Graphen, Breitensuche(Zusammenhangskomponenten)

Bestimmung der Anzahl der Zusammenhangskomponenten eines ungerichteten Graphendurch Breitensuche.

A.19 Fallstudie: Mergesort, Divide-and-Conquer, GenerizitätDiskussion und Vergleich verschiedener Implementierungen von Mergesort: direkte Im-plementierung für Felder eines primitives Datentyps; Implementierung für Felder einerallgemeinen Klasse; Generizität durch eine abstrakte Klasse; Verwendung einer generi-schen Methode; Wiederholung: Divide-and-Conquer-Algorithmen, Analyse des Algorith-mus, Mastertheorem, Zusicherungen, assert-Anweisung.

A.20 Fallstudie: Graphen, Darstellung von Graphen (Brücken)Ungerichtete, ungewichtete Graphen, Speicherung von Graphen, Algorithmus zur Bestim-mung der Brücken eines Graphen.

A.21 Fallstudie: Skriptsprachen, JavaScriptKommandosprachen (JCL); Skriptsprachen; Beispiele für Skriptsprachen; Merkmale vonSkriptsprachen; Einsatz von Skriptsprachen; Überblick: die JavaScript; Struktur einerHtml-Seite; Beispiel einer Html-Seite mit einem JavaScript-Programm; Hinweis auf weitereSkriptsprachen: Beispiel C-Shell, bash; Wiederholung: Sprachen der Informatik.

A.22 Die Programmiersprache CWiederholung: Die Paradigmen; Deduktives Paradigma: Beispiel in Prolog; Historie derSprache; grundlegende Eigenschaften; Standards; Erläuterung der Struktur und Überset-zung von C-Programmen; Präprozessor; Einstiegsbeispiel eines C-Programms; Anweisun-gen des Präprozessors; Java und C im Vergleich; Kontrollstrukturen; skalare und zusam-mengesetzte Datentypen; Typdefinitionen; Zeiger; Funktionen; dynamische Datenstruktu-ren; Ein- und Ausgabe; Referenztypen am Beispiel.

– 23 –

A.23 Berechenbarkeit, formale Algorithmus-DefinitionWiederholung der Begriffe: Berechenbarkeit, Entscheidbarkeit, Halteproblem, Diophan-tische Gleichungen. Formale Definition des Algorithmus: Markov-Algorithmus; Beispiel:Multiplikation. Eine Liste formaler Definitionen des Algorithmus; Church’sche These.

A.24 Berechenbarkeit (2)Satz von Rice, Aussage, Beispiele; Beweis in Datei: rice.pdf.

A.25 Parallelprogrammierung: FairnessFairness: weak-transition-fairness, strong-transition-fairness, weak-process-fairness, strong-process-fairness; Verhältnis der Fairness-Begriffe zueinander; Beispiel.

A.26 Alias-Name, Gültigkeit, Sichtbarkeit und LebensdauerNamensgebung: Anonymität, Alias-Name, Namenskollision; Gültigkeitsbereich; Sichtbar-keitsbereich; statische Eigenschaft; dynamische Eigenschaft; Lebensdauer; globale Variable;lexikalischer/statischer Scope; dynamischer Scope; Schachtelung; Java als flache Sprache;Auflösung von Namenskollisionen; hängende Referenz.

– 24 –

B Themen der Übungsaufgaben

B.1 1. Übungsblatt

Aufgabe 1: Unix-Grundlagen, an- u. abmelden, Passwortänderung.Aufgabe 2: Editor, Java-Compiler u. -Interpreter.Aufgabe 3: Editor, Java-Compiler, Fehlermeldungen.Aufgabe 4: Änderung eines Java-Ausdrucks.

B.2 2. Übungsblatt

Aufgabe 5: Unix-Grundlagen, Wiederholung.Aufgabe 6: Ein erstes Programm: Arithmetische und Vergleichsoperatoren, lineares Pro-gramm (Lösung quadratischer Gleichungen), Ein-/Ausgabe.Aufgabe 7: Ausgabeanweisung.Aufgabe 8: Compilermeldungen, Fehlersuche und -berichtigung.Aufgabe 9: Einfache Ausdrücke, Eingabe von der Kommandozeile.

B.3 3. Übungsblatt

Aufgabe 10: Kommentare.Aufgabe 11: Bezeichner.Aufgabe 12: Bezeichner, Deklarationen.Aufgabe 13: Ausdrücke und Operatoren: Zeichenketten, Konkatenation, Zuweisungsope-ratoren, bitweise Operatoren.Aufgabe 14: Einführung in das Programmieren; arithmetische Operatoren, Fallunter-scheidung, Eingabe über Kommandozeile (Zeitzone).Aufgabe 15: Einführung in das Programmieren; arithmetische Operatoren, Fallunter-scheidung, Eingabe über Kommandozeile (Zeitzone). Erweiterung der vorigen Aufgabe.Pflichtaufgabe 16: Einführung in das Programmieren; arithmetische Operatoren, Fall-unterscheidung, Eingabe über Kommandozeile (13-stellige ISBN).

– 25 –

B.4 4. Übungsblatt

Aufgabe 17: Zeichensätze, Darstellung und Speicherung von Zeichen und ganzzahligenWerten.Aufgabe 18: Literale, Speicherung von Gleitkommazahlen, der primitive Datentyp float.Operatoren, Anweisungen.Aufgabe 19: Deklarationen, primitive Datentypen.Aufgabe 20: Operatoren.Aufgabe 21: If-Anweisung.Aufgabe 22: Umsetzen eines gegebenen Algorithmus: Drei Schleifentypen von Java.Pflichtaufgabe 23: Wiederholungsanweisungen (Spiel).

B.5 5. Übungsblatt

Aufgabe 24: Anwendung einfacher Schleifen (σ-Funktion).Aufgabe 25: Anwendung einfacher Schleifen (Geburtstagsproblem).Aufgabe 26: Variable, Ausdrücke, Schleifen (fröhliche und traurige Zahlen).Aufgabe 27: Anweisungen, Ausgabe (Klasse BrowserTest).Aufgabe 28: Variable, Ausdrücke, Schleifen, Ausgabe (Mid-Square-Methode).Aufgabe 29: Klasse, Objekt, Attribut, Methode, Überlagerung von Methoden der KlasseObject (toString, equals, clone), statische Methode, Instanzmethode, typischer Aufbaueiner Klasse, Aufgabe zur objektorientierten Programmierung ohne Vererbung (Mengen,Zeichen als Elemente).Pflichtaufgabe 30: Aufgabe zur objektorientierten Programmierung ohne Vererbung(Spiel, Erweiterung der vorigen Pflichtaufgabe).

B.6 6. Übungsblatt

Aufgabe 31: Klasse, Objekt, Attribut, Methode, Methoden der Klasse Object: clone,equals, toString, Aufgabe zur objektorientierten Programmierung ohne Vererbung (Uhr-zeiten).Aufgabe 32: Vererbung, Überlagern von Methoden.Aufgabe 33: Klasse, Objekt, Attribut, Methode, Überlagerung von Methoden der KlasseObject (toString, equals, clone), statische Methode, Instanzmethode, typischer Aufbaueiner Klasse, Aufgabe zur objektorientierten Programmierung ohne Vererbung (rationaleZahlen).

– 26 –

Aufgabe 34: Abstrakte Klassen, Vererbung, Überlagern von Methoden, Schnittstellen,Polymorphismus (Figuren, Dreiecke, Kreise).Aufgabe 35: Abstrakte Klassen, Vererbung, Überlagern von Methoden, Schnittstellen,Polymorphismus (Funktion, Wertetabelle, Newton-Verfahren, Parabel).Pflichtaufgabe 36: Aufgabe zur objektorientierten Programmierung mit Vererbung (Er-weiterung der vorigen Pflichtaufgabe, Spiel).

B.7 7. Übungsblatt

Aufgabe 37: Nachvollziehen eines rekursiven Algorithmus (Geldwechsel).Aufgabe 38: Auswertung einer rekursiv definierten Funktion.Aufgabe 39: Iterative und rekursive Implementierung einer rekursiv definierten Funktion.Aufgabe 40: Diverse Auswertungen (innermost, outermost) einer rekursiv definiertenFunktion.Aufgabe 41: Implementierung eines rekursiven Algorithmus (Sortieren eines Feldes).Aufgabe 42: Ausnahmebehandlung; IllegalArgumentException; Empfehlung: Rekursion;(Ziffern-Matching).Pflichtaufgabe 43: Aufgabe zur objektorientierten Programmierung mit Rekursion, In-terface und Ausnahme (Erweiterung der vorigen Pflichtaufgabe, Spiel).

B.8 8. Übungsblatt

Aufgabe 44: Wiederholung: Programmverifikation, partielle und totale Korrektheit, Vor-und Nachbedingung, Schleifeninvariante, assert-Anweisung.Aufgabe 45: Wiederholung: C0- und C1-Überdeckungstests.Aufgabe 46: Wiederholung: Ausnahmebehandlung, assert-Anweisung, Programmveri-fikation, Test, (Ganzzahlige Arithmetik).Aufgabe 47: Wiederholung: Programmverifikation, partielle und totale Korrektheit vonProgrammen, Vor- und Nachbedingung, Scheifeninvariante, assert-Anweisung, Komple-xität.Aufgabe 48: Wiederholung: Ausnahmebehandlung, benutzerdefinierte Fehlerklasse.

B.9 9. Übungsblatt

Aufgabe 49: Wiederholung: Grundlagen des imperativen und objektorentierten Program-mierens (gemischte Zahlen).Aufgabe 50: JDK: Debugger jdb, Archivierungswerkzeug jar, Dokumentationsgeneratorjavadoc.

– 27 –

Aufgabe 51: Wiederholung: Grundlagen des imperativen und objektorentierten Program-mierens (Widerstandsnetz).Aufgabe 52: Wiederholung: Komplexität, partielle und totale Korrektheit von Program-men, assert-Anweisung (Insertionsort).Aufgabe 53: Aufzählungstypen (physikalische Einheiten).

B.10 10. Übungsblatt

Aufgabe 54: Wiederholung Rekursion: Verkannte Schwester der Fibonacci-Folge.Aufgabe 55: Programmierung linearer Listen durch Verkettungen.Aufgabe 56: Programmierung linearer Listen durch Verkettungen.Aufgabe 57: Programmierung linearer Listen durch Felder.Pflichtaufgabe 58: Programmierung linearer Listen; Anwendung: Erweiterung der vori-gen Pflichtaufgabe, Spiel.

B.11 11. Übungsblatt

Aufgabe 59: Implementierung generischer Keller durch verkettete Listen und Felder,Anwendung von generischen Kellern (Löschsymbol), Testen von Programmen.Aufgabe 60: Implementierung generischer Keller durch verkettete Listen und Felder, An-wendung von generischen Kellern (Umwandlung eines arithmetischen Ausdrucks von Infix-in Postfixnotaion mit einem Character-Keller, Auswertung des Ausdrucks in Postfixno-tation mit einem Integer-Keller).Aufgabe 61: Generische Methoden, Keller, Java Collections Framework, Rekursion vs.Iteration.Aufgabe 62: Generische Klassen und Schnittstellen, binäre Suchbäume.Pflichtaufgabe 63: Generische Datentypen; Spiel: Erweiterung der letzten Pflichtaufga-be; Programmierung generischer linearer Listen durch Verkettungen; CSV-Datei als Da-tenquelle.

B.12 12. Übungsblatt

Aufgabe 64: Binäre balancierte Suchbäume, generische Datentypen (AVL-Bäume).Aufgabe 65: Entwurf von Programmen, Java Collections Framework, gerichtete gewich-tete Graphen (Algorithmus von Dijkstra zur Bestimmung kürzester Wege).Aufgabe 66: (Un)gerichtete azyklische Graphen, generische Datentypen, erweiterte Tie-fensuche (topologische Sortierung).Pflichtaufgabe 67: Spiel: AVL-Baum, Umformulierung der letzten Pflichtaufgabe.

– 28 –

B.13 13. Übungsblatt

Aufgabe 68: Grafik: Applet und Main-Programm: Konvertierung von Celsius-Grad inFahrenheit-Grad.Aufgabe 69: Grafikausgabe und -eingabe mit der Swing-Bibliothek: kleiner ganzzahligerTaschenrechner.Pflichtaufgabe 70: Spiel: GUI, Umformulierung der letzten Pflichtaufgabe.

B.14 14. Übungsblatt

Aufgabe 71: Threads, Parallelisierung eines Divide-Conquer-Algorithmus (Quicksort).Aufgabe 72: Entwurf von Programmen, Java Collections Framework (Kakuro).Pflichtaufgabe 73: Spiel: Parallelität, Umformulierung der letzten Pflichtaufgabe.

– 29 –

Überblick über die VeranstaltungKurzbeschreibung Programmieren IKurzbeschreibung Programmieren IIGliederung der VeranstaltungVorbemerkungenAlgorithmus und ProgrammVom Algorithmus zum ProgrammProgrammiersprachenKorrektheit, Komplexität und EntscheidbarkeitSoftware-Grundlagen

Erste Schritte in JavaJava: Grundlagen der SpracheLexikalische ElementeDatentypen und VariableAusdrückeSpeicherung von WertenAnweisungenBeispiele aus der PraxisEin Blick auf imperatives Programmieren

Objektorientierte Programmierung in JavaKlassen, Objekte und MethodenVererbungModifikatorenKlassenvariable und statische MethodenAbstrakte Klassen

Rekursion/Funktionale ProgrammierungEinführung und BegriffeBeispiele rekursiver Methoden in JavaEin Blick auf funktionales Programmieren

Zuverlässigkeit von ProgrammenBehandlung von AusnahmesituationenGrundlagen der ProgrammverifikationDie ZusicherungsanweisungTesten von Programmen

Klassen und Methoden zur Ein- und AusgabeWeiterführende Sprachkonzepte von JavaLokale und anonyme KlassenWeiteres zu den Wrapper-KlassenAufzählungstypenDie Klassen String, StringBuffer und StringTokenizerStrukturierung von ProgrammenAnnotationen

Java und DatenstrukturenLineare ListenGenerische DatentypenKeller und SchlangenGraphenSuchen und SortierenHash-VerfahrenPersistenz von DatenDas Java Collections Framework

Grafikprogrammierung in JavaGrundlagenGrafische GrundelementeFensterklassenEreignisse und WidgetsAppletsDie Swing-Klassen

Parallelprogrammierung in JavaDas Problem des gegenseitigen AusschlussesGrundlagen und BegriffeVerwaltung von ThreadsKommunikation und SynchronisationDie speisenden PhilosophenDas Concurrent-Paket

AusblickObjektorientierte Programmierung: EntwurfsmusterProgrammierparadigmen und -sprachen und VeranstaltungenGegenstände der SoftwaretechnikJava 8

QuellenverzeichnisÜbungen, Ergänzungen, Fallstudien, WiederholungenVom Algorithmus zum Programm: ProgrammentwicklungAlgorithmen: KorrekheitFormatierung von ProgrammenAlgorithmen: KomplexitätJava-OperatorenAbstraktion und ModellierungFallstudie: Objektorientierung (Polynome)Objektorientierte Konzepte und Fallstudie (Punkte, Geraden)Fallstudie: Vererbung und abstrakte Klassen (Funktionen)Etwas Weiteres zur ObjektorientierungWeiteres Beispiel zur Frage der BerechenbarkeitFallstudie: Rekursion, Backtracking (Sudoku, Blick auf Prolog)Ein erster Blick auf grafische OberflächenKlausur zu Programmieren IEinige Programme des JDKAbstrakte Datentypen (ADT)Fallstudie: Keller (Klammerstrukturen)Fallstudie: Graphen, Breitensuche (Zusammenhangskomponenten)Fallstudie: Mergesort, Divide-and-Conquer, GenerizitätFallstudie: Graphen, Darstellung von Graphen (Brücken)Fallstudie: Skriptsprachen, JavaScriptDie Programmiersprache CBerechenbarkeit, formale Algorithmus-DefinitionBerechenbarkeit (2)Parallelprogrammierung: FairnessAlias-Name, Gültigkeit, Sichtbarkeit und Lebensdauer

Themen der Übungsaufgaben1. Übungsblatt2. Übungsblatt3. Übungsblatt4. Übungsblatt5. Übungsblatt6. Übungsblatt7. Übungsblatt8. Übungsblatt9. Übungsblatt10. Übungsblatt11. Übungsblatt12. Übungsblatt13. Übungsblatt14. Übungsblatt