Algorithmen und Programmieren II SoSe 2008 · Algorithmen und Programmieren II SoSe 2008 Dozent: H. Schweppe hs/ät/inf.fu-berlin.de Sprechstunde Mi. 14-15, R 169 Sekretariat 168

Algorithmen und Programmieren IISoSe 2008

Dozent: H. Schweppe hs/ät/inf.fu-berlin.deSprechstunde Mi. 14-15, R 169Sekretariat 168

Übungskoordination: Ingo Dagefördedagefoerd/ät/inf.fu-berlin.de

hs / fub - alp2-1 2

Inhalte im ÜberblickEntwurf & Implementierung imperativer und objektorientierter Algorithmen- Zentrale syntaktische und semantische Konzepte

imperativer Programmiersprachen- Grundkonzepte objektorientierter Programmierung- Systematische Programmentwicklung

(Programmiermethodik)Theoretische Grundlagen der imperativen Progr.- Imperatives Berechenbarkeitsmodell: Registermaschine- Spezifikation und Verifikation- Asymptotische Laufzeit

hs / fub - alp2-1 3

Organisation

VL Mo. und Do. 8-10Tutorien in kleinen Gruppen (zu verschiedene Zeiten)Bis Ende der Woche in elektronische Übungslisten eintragen!

hs / fub - alp2-1 4

TutorienMo 8-10 SR055 Michael Waldvogel (25 Anmeldungen)

Di 10-12 SR051 Michael Waldvogel(16 Anmeldungen) Di 12-14 SR051 Karima Habassi (25 Anmeldungen) Di 14-16 SR051 Karima Habassi (16 Anmeldungen)

Mi 10-12 SR055 Patrick Neumann ( 8 Anmeldungen) Mi 12-14 SR055 Patrick Neumann(25 Anmeldungen) Mi 12-14 Arnimallee 6 SR009 Maurice Wolter (20 Anmeldungen)Mi 14-16 SR055 Maurice Wolter (25 Anmeldungen)

Stand der Anmeldungen: 13.4. 12:00

hs / fub - alp2-1 5

Zielgruppe: Bachelorstudiengänge 2. Sem.

hs / fub - alp2-1 6

Organisation (2)

Achtung: Eintrag in CMS für Bachelor zwingend!Abmelden innerhalb von 4 Wochen möglich

Übungsblätter in der Regel donnerstags, Abgabe eine Woche später (Do. 16:00)

hs / fub - alp2-1 7

Scheinkriterien(1) Regelmäßige Teilnahme an VL und Tutorium

Anwesenheit in Tutorien ≥ 80% der Termine, Liste!

(2) Aktive Teilnahme Mindestens eine Lösung vorstellen, n-1 von n Übungsblättern bearbeiten, insgesamt mindestens 50% derPunkteMindestens 3 von 4 Kurztests erfolgreich.(Schriftlicher 15 min-Test zu Beginn von Tutorien)

(1) Klausur (17.7.2008) Note der Klausur = GesamtnoteSonderregelung: wer besonders aktiv an Tutorien teilnimmt, kann Gesamtnote um maximal 1 verbessern. Bestnote 1,0

hs / fub - alp2-1 8

LernzieleProgrammieren "im Kleinen"- "vom Problem zum Programm":

Algorithmen entwerfen und in Java implementieren- Grundkonzepte von imperativen und objektorientierten

Programmiersprachen beherrschen(Typen, Anweisungen, Unterprogramme und Parameterübergabe, Zeigertypen, Biblotheken)

- Korrektheit analysieren, Tests entwerfen und ausführen- Elemente der Objektorientierung:

Klassen, Objekte, Vererbung und DatenabstraktionTheoretische Grundlagen kennen- Registermachine als Berechenbarkeitsmodell- Hoare-Kalkül zur Spezifikation / Verifikation

hs / fub - alp2-1 9

zu beachten:Wichtiges Lernziel ist die Fähigkeit, imperative und objektorientierte Algorithmen in Java zu programmieren...... aber dies ist kein Java-ProgrammierkursVerwendet wird Java 1.6 - Java Development Kit (JDK) ist auf (fast) allen

Institutsrechnern installiert Empfehlenswert: auch auf eigenem PC installieren

- Java ist Plattform-unabhängig (d.h. hier unabhängigvom Betriebssystem)

Gelegentlich andere Beispiele in anderen (imperativen) Sprachen und Haskell

Unterschied Algorithmus – Programm?

hs / fub - alp2-1 10

Literatur• D. Gries, P. Gries: Multimedia Introduction to Programming UsingJava Springer-Verlag 2005

• D.Gries: The science of programming, Springer, 3.Auflage, 1985.

• Weiss, Mark A.: Data Structures & Problem Solving using Java, Addison Wesley, 1998

• T. Cormen, C. Leiserson, R. Rivest: Introduction to AlgorithmsMIT Press ; alles über Algorithmen, nichts zu Programmiersprachen

Zu Berechenbarkeit:- U. Schöning: Theoretische Informatik kurz gefasst,

Spektrum Akad. Vlg., Hdg.; ISBN: 3827402506, 29,50


Bücher zu JavaZu Java:

Arnold, K./Gosling, J.: The Java Programming Language, Addison Wesley, 2005. D. Barnes, M.Kölling: Java lernen mit BlueJ, Eine Einführung in die Objektorientierte Programmierung, 3. Auflage, PearsonR. Morelli, R. Walde: Java, Java, Java - Object-OrientedProblem Solving, 3rd. edition, Prentice Hall / Pearson Sun The Java Tutorial (online) M. Block: Java-Intensivkurs, Springer 2007 B. Eckel: Thinking in Java, Prentice Hall 2006 (Online-Version)

C. Ullenboom: Java ist auch eine Insel, Galileo Computing, 5. Auflage 2006 (Online-Version)


Ergänzende Literatur

• J. Bentley: Programming Pearls, 2nd edition, Addison Wesley / Pearson

• M. Broy: Informatik. Eine grundlegende Einführung .(Bände 1- 4) Springer- Verlag, 1992 - 1995

• P. Pepper: Grundlagen der Informatik. Oldenbourg, 1992

• H.-J. Appelrath, J. Ludewig: Skriptum Informatik, Teubner 1991

• G. Goos: Vorlesungen über Informatik (Band 1-2), Springer-Verlag 95/96.


Java ProgrammierungKommandozeile z.B. javac <ProgrammName>.javaoder java <ausführbaresProgramm>

Entwicklungsumgebungen- Eclipse (sehr komplex, aber nützlich)- BlueJ (einfach, nur für Java-Programme)- Netbeans (sun)- ... und viele andere


1 Einführung1.1 Programmiersprachen

Programmierparadigmen

deklarativ

funktionalz.B. Haskell

relational("logisch")z.B. Prolog

imperativ

prozeduralz.B. C oder Pascal

objektorientiertz.B. Java, C++, C#

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

y = 1;while (x>1){y = x * y;x = x – 1; }

Ich verwende Konzepte, Definitionen, Folien, Algorithmen von K.P. Löhr aus dem SoSe 2004. Für Fehler bin ich allein verantwortlich.


Ausdrücke, Anweisungen, Variablenf 0 = 1f x = x*f(x-1)

Funktionale Programme: Definition von Ausdrücken (expresssions).Berechnung: Auswertung von Ausdrücken (liefern Wert).Variablen: Namen für Ausdrücke oder Werte.f 3 hat den Wert 6 (und f 2 = 2 )

y = 1;while (x>1){y = x * y;x = x – 1;}

Imperative Programme: Anweisungsfolgen (Befehl, statement).Berechnung: Ausführung von Anweisung (haben Effekt).Variablen: Namen von Behältern für Werte (d.h. Speicherzellen).y nimmt für x=3 während der Ausführung die Werte 1, 3, 6 an.


f 3x=3 f (x-1)

Wert:2*3

x = 2f (x-1)

2*1

x=1f (x-1)

1*1

x=0f (0)=1

Funktional: vier unterschiedlicheWerte mit dem Namen x

3

y = 1;while (x>1) {y=x*y;x=x-1;

}

x=3

x 3

y 1

261

Speicherzellenmit Namen x und y

Imperativ: systematische Ver-änderung von zwei Speicherzellen

Warum braucht man hier kein "y" ?


BerechnungsmodelleFunktionale Programmierung

Imperative Programmierung

Funktionen berechnen durch Reduktion

Was kann man berechnen?λ-Kalkül oder rekursive Funktionen als Berechnungsmodell

Berechnung durch Folgen von Anweisungen (Befehlen)

Berechnungsmodell ähnlich Universalrechnern(Speicher, Anweisungsfolge als Programm, Befehlszähler)→ Registermaschine als Rechnermodell (siehe Abschnitt 2)


Zustände und UniversalrechnerImperative Sprachen sind eng mit dem Universalrechnerkonzept verwandt: benannte Speicherzelle = Variable

Maschinenbefehle: load , store, add,…

count..

load $r1,countadd $r1,53,$r1store $r1,count...

46

PENTIUM500000050000015000002

neuer Wert: 99Hauptspeicher

CPU

warum Haupt ?Central Proc. Unit ?

Aktuelle Werte im Speicher und aktueller Wert des Befehlszählersdefinieren Zustand der Berechnung.


Traditioneller AlgorithmusbegriffAlgorithmus (algorithm) benannt nach AlKhwarizmi

(arab. Mathematiker, 9.Jhd.)… abstrahiert von Rechnerhardware und konkreter

Programmiersprache… ist imperativ (!)Ein Algorithmus ist ein schrittweises Verfahren zur Lösung einer Klasse gleichartiger Problemen mit den Eigenschaften:

1. Jeder Einzelschritt ist für die ausführenden Instanzeindeutig verständlich und ausführbar

2. Das Verfahren ist endlich beschreibbar [3. Der nächste auszuführende Schritt ist eindeutig bestimmt][4. Das Verfahren terminiert]


• Termination? y=0;x=3;while (x>1) {y=y*x}

• Eindeutiger nächster Befehl? y=11;x=3;m=0;while (y>=x) {y=y-x; m=m+1;}

Reihenfolge beliebig!


Klassen von Algorithmen

Sequentiell (sequential )Eigenschaft 3. gilt – nächster Befehl eindeutig bestimmt

Nichtsequentiell (concurrent)Ausführungsreihenfolge bleibt teilweise offen

DeterministischAusführungsreihenfolge und Effekte für jeden Schritt eindeutig festgelegt (⇒ sequentiell)Nichtdeterministisch / stochastisch sonst


Nichtdeterministisch / nichtdeterminiert

Gegeben Menge von 3 Klassen von Punkten .Algorithmus zur Klassifikation:

klassifiziere (punkt p) {Punktmenge M =

bestimmeNächsteNachbarn(p);Wenn |M| = 1 :

klasse(p) = Klasse des PunktesSonst:

wähle beliebigen aus M und gibp dessen Klasse

Nichtdeterministischer Algorithmus, hier Ergebnis nicht determiniert.

Dagegen determiniert: Ergebnis ist bei gleichen Anfangsbedingun-gen eindeutig – auch wenn "gewürfelt" wird.


1.2 Programmiersprachen - Übersicht• Programmierung in Maschinen- bzw. Assemblersprache

Nachteil: geringes Abstraktionsniveau, maschinenabhängig

abs $t0, $t0 # Argum. in abs $t1, $t1 # $t0, $t1beq $t0, $t1, ex

rp:sub $t0, $t0, $t1 # $t0 <- $t0-$t1

bgt $t0, $t1, rpbgtz $t0, swneg $t0, $t0

sw:move $t2, $t0 # $t2<-$t0 move $t0, $t1 move $t1, $t2 bne $t1, $t0, rp

ex:move $a0, $t0 # Ausgabe li $v0, 1 # $t0syscall

Was berechnet f ??

• Entwicklung „problemorientierter“ Sprachen: Abstraktion von der Maschine, Sprach-elemente für typische „höhere“ Operationen und Datentypen:

Zahlen, Zeichen, Vektoren …;Wiederholungsanweisung,…;

• für wissenschaftlich-technische Aufgaben• für kommerzielle Anwendungen •„für algorithmisches Problemlösen“


Höhere Programmiersprachen: die Anfänge• Formula Translator (FORTRAN)

ab 1954, John Backus (IBM) für numerisch-wiss. Anwendungen.beachte: Sprachübersetzung erforderlich!

• Common Business Oriented Language (COBOL)ab 1960, firmenunabhängige Standardisierungbesondere Berücksichtigung von Datei-Ein-/Ausgabe, hohe sprachliche Redundanz (230 reservierte Wörter!)

• Programming Language I (PL/I)Versuch der Verbindung von numerisch und kommerziell orientiertenProgrammiersprachen und ALGOL-Konzepten (IBM 1966)erste Sprache mit formaler Semantik

• Algorithmic Language (Algol)ab 1958, Blockstrukturen, Anweisungen / Ausdrücke, Typkonzeptefirmenunabhängige Entwicklung durch Hochschulen, großer Einfluß auf Programmiersprachentwicklung, geringe praktische Bedeutung

Breitbandsprache


Weitere Programmiersprachen• List Processing Language (Lisp)

Rückbesinnung auf λ-Kalkül, funktionale Programmiersprache mit großer Bedeutung in der Künstlichen Intelligenz (MIT 1960)„Programme als Daten - Daten als Programme“, higher order functions,Speicherverwaltung und -Speicherbereinigung (garbage collection)noch heute viel benutzt (Emacs!)

• C als Implementierungsprache für UNIX entwickelt (Kernighan, Ritchie, ATT Labs, 1970), ursprünglich reine Systemimple-

mentierungssprache, Bedeutung erst durch Verbreitung UNIX

• PASCALab 1970, von Nikolaus Wirth (ETH Zürich) als Schulungssprache ent-worfen, viele ALGOL-Elemente, aber viel einfacher als ALGOL 68,weiterentwickelt unter Softwaretechnikaspekten

(Modularisierung!) zu MODULA-2


Die Geschichte von C ?

…


Moderne Sprachkonzepte und Sprachen• Simula 67

(Nygaard, Dahl u.a. 1972) , erste objektorientierte Programmiersprache,baut direkt auf ALGOL 60 auf. class als neues Konstrukt, Konstruktionvon Systemen als Motivation

der Zeit weit voraus!

• Programming in Logic (PROLOG)Tendenz: Deklarative Formulierung von Algorithmen („was statt wie“)Programm: Menge von logischen Formeln.A. Colmerauer, ca. 1973Verbreitet in der KI , sonstige Bedeutung gering

• Functional Programming (FP)1978 John Backus (IBM) ,funktionales Sprachkonzept, Plädoyer gegen anweisungsorientiertes Programmieren, Grundlage für moderne funktionale Sprachen

Ironie des Schicksals:Vorgeschlagen in seinerRede anläßlich Verleihung des Turing Award für seineFORTRAN -Verdienste(...aber nicht nur die)


Heutige Sprachkonzepte und Sprachen

Einflüsse auf Programmiersprachentwicklung • UNIX - Verbreitung → C• Softwareentwicklung → Objektorientierung:

C++, Java, C#, Delphi, Eiffel (nur im akademischen Umfeld)

• Vernetzung → Plattformunabhängigkeit, verteilte Systeme→ Java

• Produktivitätsaspekte → Programmierumgebung /-spracheVisual C / Visual Basic / Java

• Spezifikation / Verifikation → funktionale SprachenHaskell, Erlang, MatLab, R

• Skriptsprachen?


1.3 Vom Algorithmus zum ausführbaren Programm

Algorithmus Programm in höherer SpracheCodierung

Programm in Maschinensprache

Übersetzung

AusführbaresProgramm Binden mit

anderen (Hilfs-)Programmen


Interpretation von Programmen

Algorithmus Programm in höherer SpracheCodierung

Interpretation

Interpretierer-Programm

Die Welt von heute: Keine klare Trennung mehr zwischen Übersetzung und Interpretation

z.B. Java…


Java: Quell-, Byte- und Maschinencode

class xyz{

....

}

Java Quellcode-übersetzer

Aufruf: javac

Bibliothek,selbst geschriebeneProgramme (~ Klassen)

Quellcodebnc .. sto..

....

Java - Bytecode

Das ist maschinenunabhängigerMaschinencode ?!

Ausgabe Java Virtuelle Maschine

Aufruf: java

interpretiert Java Bytecode

PlattformabhängigerMaschinencode:Intel, Sun Sparc, ...,

Win / Solaris / Linux,


SkriptsprachenEigenschaften

- 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, Javascript ( ≠ Java !), Tcl, Bash, C-Shell,

Basic,…, Lisp (?)


ZusammenfassungKlassen von ProgrammiersprachenFunktionale und imperative Algorithmen Werte, Variablen, Definitionen, AnweisungenBerechnungsmodelle: Rekursive Funktionen, λ-Kalkül, Registermaschine (nächste Stunde)Arten von ProgrammiersprachenAlgorithmen, Programm, AusführungÜbersetzung, InterpretationSkriptsprachen

Documents

Algorithmen und Programmieren II SoSe 2008 · Algorithmen und Programmieren II SoSe 2008 Dozent: H. Schweppe hs/ät/inf.fu-berlin.de Sprechstunde Mi. 14-15, R 169 Sekretariat 168