Pro Informatik 2009: Objektorientierte Programmierung Tag 11 · Tag 12 – Objektorientierung II. Wiederholung OOP, Innere Klassen, Anonyme Klassen, Vererbung, Typverträglichkeit,

Pro Informatik 2009: Objektorientierte ProgrammierungTag 11

Marco Block-Berlitz, Miao Wang

Freie Universität Berlin, Institut für Informatik

31.08.2009

2Pro Informatik 2009: Objektorientierte Programmierung

Agenda

Tag 11 – BerechenbarkeitProgrammiersprachen, Algorithmus, Berechenbarkeit, Registermaschinen, Turingmaschine, Halteproblem, Laufzeitanalyse, O-NotationJava-Dokumentation, Einführung in Eclipse

Tag 12 – Objektorientierung IIWiederholung OOP, Innere Klassen, Anonyme Klassen, Vererbung, Typverträglichkeit, Verdecken, Ersetzen, Identifizieren, Überladen, Die Klasse ObjectGenerizität

Tag 13 – Spezifikation und VerifikationFormale Verfahren zur Spezifikation und Verifikation imperativer Programme, Assertions, partielle und totale Korrektheit, Hoare-Kalkül, Umwandlung von Rekursion zu IterationVerschiedene Übungen zum Hoare-Kalkül

Tag 14 – Software-EngineeringIterative Softwareentwicklung, UML, Softwareentwicklung im TeamEntwicklungswerkzeuge, Entwurfsmuster

Tag 15 – ProgrammiertechnikenTop-Down, Bottom-Up, Rekursion, Brute Force, Greedy, Teile und Herrsche,Dynamisches Programmieren, MemoisationKlausurvorbereitung


Agenda

Tag 16 – DatenstrukturenAbstrakte Datentypen, ADT Folge: Stack, Queue, Liste, ADT Menge: Bäume: Binärbäume, Suchbäume, AVL-Bäume, Prioritätswarteschlangen, Heap, GraphenADTs in Java

Tag 17 – SortieralgorithmenInsertionSort, BubbleSort, SelectionSort, ShellSort, MergeSort, QuickSort, Binary Tree Sort, HeapSortUntere Schranke für vergleichsbasierte Sortierverfahren, BucketSort, CountingSort, RadixSort

Tag 18 – SuchalgorithmenBinärsuche, Breitensuche, Tiefensuche, Backtracking Klausurvorbereitung

Tag 19 – Klausur

Tag 20 – Letzter TagWeitere Projekte am Fachbereich, Klausurnachbesprechung, Grillen?


Organisatorisches

Kontakt:Miao Wang

Email: [email protected]

Büro: R 136

Tutorien:SR 005, 006, 049 (Laptops)

RR K38, K44, K46 (Pool-Rechner)

Achtung: Am 04.09 ist SR 005 besetzt

Übungen:Übungszettel mit Abgabe

Programmierprojekt in Gruppen (2er, 3er)

Klausur:Vorletzter Vorlesungstag: Do, 10.09.2009

Voraussetzung: Bearbeitung der Übungen, 20 € Kursgebühr

Scheinnote entspricht Klausurnote

mailto:[email protected]�


BERECHENBARKEIT


Programmiersprachen


Programmiersprachen

Programmierparadigma

deklarativ(beschreibend, logisch)

imperativ(befehls-, problemorientiert, prozedural)

funktional(z.B. Haskell)

relational(z.B. Prolog)

prozedural(z.B. Pascal)

objektorientiert(z.B. Java)

f 0 = 1f x = x*f(x-1)

member(X,L):-concat(L1,[X|L2],L)

y = 1;while (x>1) {

y = x * y;x = x – 1;

}

Person p = new Person(“Hans”, 41);

Keine Zuweisungen, keine Kontrollstrukturen, oftmals Rekursion.

„ausführbare Spezifikation“

Zur Lösung eines Problems müssen die verfügbaren Operationen des Rechners durch geschickte Kombinationen verbunden werden.

„rechnernahe Implementierung“


Relevante Programmiersprachenim Studium an der FU

1959 Lisp

1965 Basic

1971 Pascal

1972 C

1975 Prolog

1985 C++

1987 Perl

1990 Haskell

1995 Delphi

1995 Java

2000 C#

relational

prozedural

prozedural

prozedural

relational

objektorientiert

objektorientiert

funktional

objektorientiert

objektorientiert

objektorientiert

Hohe Relevanz für Studium am Fachbereich Mathematik/Informatik an der FU-Berlin


Funktionale vs. Imperative Programmierung

Funktionale Programme: Definition von Ausdrücken (expressions)

Berechnung: Auswertung von Ausdrücken (liefern Wert)

Variablen: Namen für Ausdrücke oder Werte

Imperative Programme: Anweisungsfolgen (Befehle, statements)

a1, a2, a3, …imperare (lat.) = befehlen

Berechnung/Programmausführung: Ausführung der Anweisungen, bewirkt Effekte durch Änderung von Zuständen von Variablen (u.a.)

Variablen: Namen von Behältern für Werte (d.h. Speicherzellen), enthalten einen Wert, der durch einen anderen Wert ersetzt werden kann.

f 0 = 1f x = x*f(x-1)

y = 1;while (x>1) {

y = x * y;x = x – 1;

}


Funktionale vs. Imperative Programmierung

x=3f (x-1)

systematische Veränderung vonzwei Speicherzellen

x = 2f (x-1)

x = 1f (x-1)

x = 0f (0)=1

1*1

2*1

3*2

x=3;

y = 1;while (x>1) {

y = x * y;x = x – 1;

}

X

Y

1

6

vier unterschiedliche Werte mit dem Namen x, es wird kein y benötigt

f 3 hat den Wert 6 (und f 2 = 2 )

f 0 = 1f x = x*f(x-1)

y = 1;while (x>1) {

y = x * y;x = x – 1;

}


Haskell

Oft sehen Programme in Haskell sehr elegant aus und dienen der Spezifikation von höheren Programmiersprachen.

In Haskell wird die Unterscheidung von Datentypen geschult.

Als Beispiel sehen wir die member-Funktion

und die Fakultäts-Funktion

Der QuickSort-Algorithmus läßt sich sehr kurz formulieren:

member :: Int -> [Int] -> Boolmember b [] = Falsemember b (a:x) = (a==b) || member b x

fac :: Int -> Intfac 0 = 1fac n = n * fac (n-1)

qSort [] = []qSort (a:x) = qSort[y|y


Spezifikation einer Funktion

Mathematik: Spezifikation einer Funktion

Informatik: funktionales Programm

Informatik: imperativer Algorithmus und imperatives Programm

Haskell

f(x) = 1 , für x=0x * f(x-1) , für x>0{ undefiniert für x1) {

y = x * y;x = x – 1;

}

setze y=1;solange x>1, wiederhole:

setze y auf x*yund x auf x-1


Logische Programmierung mit Prolog

Prolog ist die „Sprache der KI“. Wir können Regeln definieren und automatisch schlussfolgern. Prolog ist eine sehr mächtige Sprache, da eine automatische, optimierte Suche hinter den Kulissen arbeitet. Es folgen ein paar Beispiele.

Ist X Element einer Liste L?

Definition des member-Prädikats:

Prolog

member(X, [X|T]).member(X, [Y|T]) :- member (X, T).

?member (c, [a,b,c]).yes

?member (X, [a,b]).X=a;X=b;

Literaturhinweis:PROLOG - Programming for Artificial Intelligence", 3.Auflage, Pearson Verlag, 2001


Logische Programmierung mit Prolog

Die Konkatenation von Listen lässt sich elegant formulieren

Mit Hilfe des concat-Prädikats, können wir member ausdrücken

Wir können Elemente von Listen entfernen und neue Listen beschreiben

Mit del können wir sogar insert ausdrücken

Oder kurz mal alle Permutationen

Mehr dazu in Vorlesung: „Künstliche Intelligenz“

Prolog

concat ([], L, L).concat ([X|L1], L2, [X|L3]) :- concat(L1, L2, L3).

member(X, L) :- concat(_, [X|_], L).

del(X, [X|Tail], Tail).del(X, [Y|Tail], [Y|Tail2]) :- del(X, Tail, Tail2).

insert(X, List, List_with_X) :- del(X, List_with_X, List).

perm([],[]).perm([X|L],P) :- perm(L, L1), insert(X,L1,P).


C als Implementierungsprache für UNIX entwickelt (Kernighan, Ritchie, ATT Labs, 1970)

ursprünglich reine Systemimplementierungssprache, Bedeutung erst durch Verbreitung UNIX

Heute noch oft benutzt für Betriebssyteme, Echtzeitsysteme, hardwarenahe Systeme

Später (Bjarne Stroustrup, 1979) weiterentwickelt zu C++ mit Objektorientierung

Liste von Hello-World Programmen: http://de.wikipedia.org/wiki/Liste_von_Hallo-Welt-Programmen/Programmiersprachen

C/C++

#include

int main(void) {printf("Hallo Welt!\n");return 0;

}

#include #include

int main() {std::cout


Skriptsprachen sind Programmiersprachen, die vor allem für kleine, überschaubare Programmier-aufgaben gedacht sind. Sie sind meist wenig restriktiv, was die Sprachelemente angeht.

Eigenschaften

• oft interpretiert

• liberale Typen, oft kein Zwang zur Deklaration von Variablen

• implizite Typwandlung

• automatische Speicherverwaltung

Anwendungen

• einfache Aufgaben

• Prototyp erstellen (rapid prototyping)

• Betriebssystemkommandosprache

Beispiele

• Python, PHP, Perl, Ruby, Javascript ( ≠ Java !), Tcl, Bash, C-Shell, Basic, …, Lisp (?)

Skriptsprachen


Algorithmus (algorithm) benannt nach AlKhwarizmi (arab. Mathematiker, 9.Jhd.)

Ein Algorithmus abstrahiert von Rechnerhardware und konkreter Programmiersprache und ist imperativ (!). Ein Algorithmus ist ein schrittweises Verfahren zur Lösung einer Klasse gleichartiger Problemen mit folgenden Eigenschaften:

1. Jeder Einzelschritt ist für ausführenden Instanz eindeutig verständlich und ausführbar

2. Das Verfahren ist endlich beschreibbar

3. Optional: Der nächste auszuführende Schritt ist eindeutig bestimmt

4. Optional: Das Verfahren terminiert

5. Optional: Das Verfahren ist determiniert

6. Optional: Das Verfahren ist deterministisch

Gilt Punkt 3, so ist der Algorithmus sequentiell, ansonsten nichtsequentiell (concurrent).

Gilt Punkt 4, so ist der Algorithmus terminierend, ansonsten nichtterminierend.

Gilt Punkt 5, so ist der Algorithmus determiniert, ansonsten nicht determiniert.

Gilt Punkt 6, so ist der Algorithmus deterministisch, ansonsten nichtdeterministisch.

Traditioneller Algorithmusbegriff


Sequentiell?

Termination?

Determiniert?Der Algorithmus liefert stets das gleiche Ergebnis bei gleichen Startbedingungen und Eingaben

Deterministisch?Während des Algorithmus ist der nächste Handlungsschritt eindeutig definiert.

Traditioneller Algorithmusbegriff

y=0;x=3;while (x>1) {

y=y*x}

y=11;x=3;m=0;while (y>=x) {

y=y-x || m=m+1;}

Reihenfolge beliebig


Vom Algorithmus zum ausführbaren Programm

Programm als Quellcode in höherer ProgrammierspracheIdee/Algorithmus

Programm in Maschinensprache

Ausführbares Programm

Programmieren (Coding)

Übersetzung (Compiler)

Binden mit anderen (Hilfs-)Programmen(Linker)

Compiler (z.B. C, C++)



Programm als Quellcode in höherer ProgrammierspracheIdee/Algorithmus

Interpretierer

Programmieren (Coding)

Interpreter (z.B. Prolog, C#, Java)

Heute: Keine klare Trennung mehr zwischen Übersetzung und Interpretation, meist erst Übersetzung in Byte-Code / Intermediate Language

Interpretation


Java:


Java BytecodeJava-Quellcode

JVM

Interpretation

javac

Übersetzung (Compiler)

class xyz {…

}

bnc 0xE.. sto 0xF..

plattformunabhängigerMaschinencode

plattformabhängigerMaschinencode

Intel, Sun, SparcWin / Mac / Solaris / Linux


Berechenbarkeit

Definition: „Eine Funktion ist berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet“

Sei T der Definitionsbereich von f

A berechnet f, wenn Eingabe n in T liegt und A nach einer endlichen Zahl von Schritten f(n) liefert

Liegt n nicht in T, so terminiert A nicht

f ist somit eine partielle Funktion

Frage: Welche Funktionen sind berechenbar? Gibt es Funktionen, die überhaupt nicht berechenbar sind?

Funktion fEingabe n Ausgabe f(n)

Algorithmus A

Literaturhinweis:Theoretische Informatik – kurzgefaßt, 3. Auflage, Uwe Schöning, Spektrum Akademischer Verlag, 2001


Entscheidbarkeit

Definition: „Eine Funktion ist entscheidbar, wenn sie eine charakteristische Funktion repräsentiert und diese entscheidbar ist“

Entscheidbar: f gibt ja aus, wenn n in T - ansonsten nein

Semi-entscheidbar: f gibt ja aus, wenn n in T – ansonsten undefiniert

Unentscheidbar

Funktion fEingabe nja wenn n in T

nein sonst

Algorithmus A


Turingmaschine

Die Turingmaschine dient als einfaches Rechnermodell:

• Ein unendlich langes Speicherband mit Feldern, auf dem jeweils ein Zeichen gespeichert werden kann

• Ein programmierbaren Schreib-Lesekopf, der sich auf dem Band feldweise bewegen kann und die Zeichen lesen oder ändern kann


Nicht entscheidbare Probleme: Halteproblem

Das Halteproblem von Turingmaschinen ist ein Standardbeispiel für ein nicht entscheidbares Problem [Alan Turing, 1936]:

Kann man ein Programm A entwickeln, das als Eingabe ein anderes Programm B und einen Eingabewert n erhält und entscheiden kann, ob das andere Programm B terminiert?

Antwort: Nein


BeweisAngenommen es gibt ein Programm A, welches folgendes tut:

Und ein Programm T:

Was passiert, wenn eine Turingmaschine T(T) aufruft?

Dann liefert T(T) entweder Ja oder bleibt in einer Endlosschleife

Terminiert T(T) und liefert Ja, dann lieferte A(T,T) Nein. Das bedeutet wiederum, dass T(T) nicht terminiert. Widerspruch!

Terminiert T(T) nicht, dann lieferte A(T,T) Ja. Das bedeutet wiederum, das T(T) terminiert.Widerspruch!

Es gibt keine Turingmaschine, die das Halteproblem entscheiden kann!

Nicht entscheidbare Probleme: Halteproblem

A(Programm B, Eingabe n):if A(n) terminiert return Ja else return Nein

T(Programm X):while A(X,X) == Ja continueelse return Ja


Registermaschine

Die Registermaschine (RAM-Modell) ist ein weiteres Rechnermodell, das etwas ähnlicher ist zu heutigen Rechnern als die Turingmaschinen:

• Ein Befehlszeiger p

• Eine Eingabe n

• Eine Ausgabe o

• Ein unendlich großer, durchnummerierter Registerspeicher: r1, r2, r3, etc..

Operationen werden durch den Befehlssatz einer Programmiersprache festgelegt.


LOOP-Registermaschine

Befehlssatz einer LOOP-Registermaschine

Beispiel: Multiplikation xi = xj * xk

Mit LOOP-Programmen kann man genau die primitiv rekursiven Funktionen fk :: Nk → Nberechnen.

Aber das sind bekanntlich nicht alle berechenbaren Funktionen.

xi = xj + cxi = xj – cLOOP xi {}

c: konstante natürliche ZahlAddition wie üblichSubtraktion:xi erhält den Wertxj – c, wenn xj – c ≥ 0sonst 0

LOOP xi {xi = xi - 1}LOOP xj {xi = xi + xk}


Primitiv Rekursive Funktionen

1. Die k-stellige Nullfunktion, die immer 0 ausgibt:

2. Die Nachfolgerfunktion

3. Die k-stellige Projektionen

4. Die Kompositionm-stellige Funktion gm n-stellige Funktionen h

5. Die primitive Rekursion zweier Funktionen

Alle primitiv-rekursiven Funktionen sind im intuitiven Sinn berechenbar. Sie schöpfen aber nicht alle intuitiv berechenbaren Funktionen aus. Beispiel: Die Ackermannfunktion.


Ackermannfunktion

Die Ackermannfunktion (Ackermann 1926) ist eine extrem schnell wachsende mathematische Funktion, die berechenbar ist, aber nicht primitiv rekursiv:

Literaturhinweis:Theoretische Informatik – kurzgefaßt, 3. Auflage, Uwe Schöning, Spektrum Akademischer Verlag, 2001


WHILE-Registermaschine

Damit die Registermaschine, alle intuitiv berechenbaren Funktionen realisieren kann, ist eine Spracherweiterung nötig.

Die WHILE-Registermaschine kann alle berechenbaren Funktionen realisieren und somit auch alleLOOP-Programme.

xi = xj + cxi = xj – cWHILE (xi ≠ 0) {}

Führe solange aus bis xi den Wert 0 hat


GOTO-Registermaschine

Alternativ gibt es den GOTO-Befehlssatz.

Die Klasse der GOTO-Programme ist gleich der Klasse der WHILE-Programme

xi = xj + cxi = xj – cif xi=c then GOTO MjGOTO MjHALT

Literaturhinweis:Go To Statement Considered Harmful, E. W. Dijkstra, Communications of the ACM, Vol.11, No.3, 1968, pp. 147–148


LAUFZEITANALYSE


Laufzeitanalyse

Die Laufzeit T(n) eines Algorithmus ist die maximale Anzahl der Schritte bei einer Eingabegröße n.

Wie man die Größe einer Eingabe misst, muss konkret festgelegt werden, z.B. für Sortieralgorithmen wählt man sinnvollerweise die Anzahl der zu sortierenden Objekte.

Welche Schritte dabei gezählt werden (z.B. arithmetische Operationen, Vergleiche, Speicherzugriffe,

Wertzuweisungen) hängt sehr stark von dem verwendeten Modell oder der verwendeten Programmiersprache ab. Sogar ein Compiler kann Einfluss auf die Anzahl der Schritte haben.

Oft unterscheiden sich die Laufzeiten des gleichen Algorithmus’ unter Zugrundelegung verschiedener Modelle um konstante Faktoren. Das Ziel der Laufzeitanalyse besteht darin, den Einfluss solcher modell- und implementierungsabhängiger Faktoren auszublenden und damit einen davon unabhängigen Vergleich von Laufzeiten zu ermöglichen.

Literaturhinweis:Algorithmen – kurz gefasst, Uwe Schöning, Spektrum Akademischer Verlag, 1997


Konstante Laufzeit

Einfaches Beispiel:

Die Funktion constFunction benötigt in Bezug auf die Eingabegröße n 2 Arbeitsschritte.

Unabhängig von der Eingabe benötigt die Funktion konstant viele Arbeitsschritte. Wir sprechen dann von konstanter Laufzeit.

Auch constFunction2 benötigt eine konstante Anzahl an Arbeitsschritten. Von der asymptotischen Laufzeit her unterscheiden sich die beiden Funktionen nicht.

int constFunction (int[] n) {int i = 2*12+2; // 2 Schritte return i;

}

int constFunction2 (int[] n) {int i = 0; // 1 Schrittwhile(i < 10) { // 10 mal

i++; // 1 Schritt}return i;

}


Lineare Laufzeit

Einfaches Beispiel:

Die Funktion sumFunction benötigt in Bezug auf die Eingabegröße n folgende Arbeitsschritte:

sumFunction(n) = 1 + n * 1 = n+1

Für diese Fälle wollen wir konstante Werte, die keinen signifikanten Einfluss haben, weglassen. Für dieses Beispiel ergebe sich sumFunction(n) = n, dann sprechen wir von linearer Laufzeit.

int sumFunction (int[] n) {int sum = 0; // 1 Schrittfor (int i=0; i


Asymptotische Betrachtung

Vergleich von Laufzeiten bezieht sich auf das langfristige Verhalten.

Konstanten können daher ignoriert werden.

Bei der asymptotischen Betrachtung interessieren wir uns für den höchsten Term,z.B. O(n4 + 7000n3 + 900n2 + 10000n + 1000000) = O(n4)


O-Notation

Die Landau-Symbole werden verwendet, um Laufzeiten für Algorithmen anzugeben und vergleichen zu können:

Asymptotische Schranken in O-Notation:


O-Notation


Asymptotische Laufzeitklassen

Unsere constFunction liegt also in O(2) = O(1)

Unsere sumFunction liegt in O(n+2) = O(n)

Welche Laufzeiten haben folgende Funktionen?

• Finden des Maximums aus einem Array mit n natürlichen Zahlen

• Finden des Minimums aus einem Array mit n reellen Zahlen

• Multiplikation einer mxn Matrix mit einer nxk Matrix

int constFunction (int[] n) {int i = 2*12+2; // 2 Schritte return i;

}



Asymptotische Laufzeitklassen

Übliche Laufzeiten:

Kannst du diese Laufzeiten der Größe nach sortieren?


Speicherbedarfanalyse

Genauso wie über die Laufzeit eine asymptotische Analyse geführt werden kann, so geht das auch mit dem Speicherbedarf.

Die Summe eines Zahlenarrays: Laufzeit liegt in O(n), Speicherbedarf in O(n).

Berechnung der n-ten Potenz (naiv): Laufzeit liegt in O(n), Speicherbedarf bei O(1)



PAUSE


Java Dokumentation

Die wichtigsten Anlaufstellen:

• Java 2 Platform, Standard Edition, v 1.4.2 API Specificationhttp://java.sun.com/j2se/1.4.2/docs/api/

• Java 2 Platform Standard Edition 5.0 API Specificationhttp://java.sun.com/j2se/1.5.0/docs/api/

• Java™ Platform, Standard Edition 6 API Specificationhttp://java.sun.com/javase/6/docs/api/

• Galileo Computing Openbook: Java ist auch eine Insel (8. Auflage) http://openbook.galileocomputing.de/javainsel8/

• B. Eckel: Thinking in Java , Prentice Hall, 2006http://www.codeguru.com/java/tij/

• Java-Tutorial von Sunhttp://java.sun.com/docs/books/tutorial/

Bei Fragen:

• unser Forum: http://www.java-uni.de/forum/

http://java.sun.com/j2se/1.4.2/docs/api/�http://java.sun.com/j2se/1.5.0/docs/api/�http://java.sun.com/javase/6/docs/api/�http://openbook.galileocomputing.de/javainsel8/�http://www.codeguru.com/java/tij/�http://java.sun.com/docs/books/tutorial/�http://www.java-uni.de/forum/�


Eclipse

Eclipse ist eine integrierte Entwicklungsumgebung (IDE) für Java

www.eclipse.org

http://www.eclipse.org/�


Eclipse

Roadmap:• Eclipse installieren

• Eclipse starten und kennenlernen

• Einstellungen

• Workspace und Projekte

• Views und Perspektiven

• Klasse erstellen

• Interface erstellen

• In Eclipse Methodendokumentation anschauen

• Auto-Generator

• Refactoring

• Shortcuts

• Jar erstellen

• Debuggen

�Pro Informatik 2009: Objektorientierte Programmierung�Tag 11AgendaAgendaOrganisatorischesBerechenbarkeitProgrammiersprachenProgrammiersprachenProgrammiersprachenRelevante Programmiersprachen�im Studium an der FUFunktionale vs. Imperative ProgrammierungFunktionale vs. Imperative ProgrammierungHaskellHaskellPrologPrologC/C++SkriptsprachenTraditioneller AlgorithmusbegriffTraditioneller AlgorithmusbegriffVom Algorithmus zum ausführbaren ProgrammVom Algorithmus zum ausführbaren ProgrammVom Algorithmus zum ausführbaren ProgrammBerechenbarkeitEntscheidbarkeitTuringmaschineNicht entscheidbare Probleme: HalteproblemNicht entscheidbare Probleme: HalteproblemRegistermaschineLOOP-RegistermaschinePrimitiv Rekursive FunktionenAckermannfunktionWHILE-RegistermaschineGOTO-RegistermaschineLaufzeitanalyseLaufzeitanalyseKonstante LaufzeitLineare LaufzeitAsymptotische BetrachtungO-NotationO-NotationAsymptotische LaufzeitklassenAsymptotische LaufzeitklassenSpeicherbedarfanalysePAUSEJava DokumentationEclipseEclipse

Documents

Pro Informatik 2009: Objektorientierte Programmierung Tag 11 · Tag 12 – Objektorientierung II. Wiederholung OOP, Innere Klassen, Anonyme Klassen, Vererbung, Typverträglichkeit,