Algorithmen und Programmieren II Konzepte imperativer und ...¼hrung_ALP2.pdf · ALP II: Margarita Esponda, 1. Vorlesung, 12.4.2012 Inhalt 3 1. Konzepte imperativer Programmierung

ALP II: Margarita Esponda, 1. Vorlesung, 12.4.2012

SS 2012

Prof. Dr. Margarita Esponda

1

Algorithmen und Programmieren IIKonzepte imperativer und

objektorientierter Programmierung


Inhalt

Inhalt

2

1. Konzepte imperativer Programmierung (Python)

2. Formale Verfahren zur Spezifikation und Verifikation

imperativer Programme

3. Konzepte objektorientierter Programmierung (Java)

4. Programmiermethodik

5. Analyse von Laufzeit und Speicherbedarf

6. Berechenbarkeit


Inhalt

3

1. Konzepte imperativer Programmierung

✴ Syntax und operationelle Semantik imperativer Programmiersprachen

✴ Python als Beispiel

2. Formale Verfahren zur Spezifikation und Verifikation imperativer

Programme

✴ Bedingungen im Zustandsraum (assertions)

✴ Hoare-Kalkül und partielle Korrektheit von Programmen

✴ Termination von Programmen

Inhalt (1. Teil)


Inhalt

4

3. Konzepte objektorientierter Programmierung (Java)

✴ Primitive und Zusammengesetzte Datentypen,

✴ Methoden (Prozeduren und Funktionen),

Parameterübergabe, Überladung

✴ Module, Klassen, Objekte

✴ Klassenhierarchien, Vererbung, abstrakte Klassen,

Schnittstellen, Polymorphie

✴ Ausnahmebehandlung (Exceptions)

Inhalt (2. Teil)


Inhalt

5

Inhalt (1. + 2. Teil)

4. Programmiermethodik

✴ Umwandlung von Rekursion in Iteration

✴ Teile und herrsche

✴ Rücksetzverfahren (Backtracking)

✴ Dynamische Programmierung

5. Analyse von Laufzeit und Speicherbedarf ✴ O-Notation

✴ Analyse von Such- und Sortieralgorithmen

✴ Algorithmen und Datenstrukturen

6. Berechenbarkeitsbegriff✴ Universelle Registermaschinen


Lernziele

6

Programmieren im KleinenAlgorithmen entwerfen und implementieren

Grundkonzepte von imperativen Programmiersprachen im allgemeinen beherrschen Datentypen, Anweisungen, Kontrollstrukturen

Unterprogramme, Funktionen, Parameterübergabe und Zeigertypen

Korrektheit von Programmen analysieren Tests entwerfen und ausführen

Konzepte Objektorientierter Programmierung beherrschen Klassen, Objekte, Kapselung, Vererbung,

Polymorphie und Datenabstraktion

Theoretische Grundlagen kennen Registermaschinen als Berechenbarkeitsmodell

Hoare-Kalkül zur Spezifikation / Verifikation

Unsere Lernziele sind:


Literatur

7

LiteraturAlgorithmen und Datenstrukturen

"Algorithmen und Datenstrukturen - Eine Einführung mit Java". 3. Auflage

Dpunkt.Verlag, 2006.

Gunter Saake, Kai-Uwe Sattler.

Algorithmen in Java. Robert Sedgewick. Teil 1-4. 2002. 3. Auflage.

Introduction to Algorithms. Third Edition. Thomas H. Cormen, Charles E. Leiserson,

Ronald L. Rivest, Clifford Stein. 2009.

Java-Programmierung (online)

The Java Language Specification. Java SE 7 Edition. Oracle America Inc., 2012.

James Gosling et al.

C. Ullenboom: Java ist auch eine Insel, Galileo Computing, 10. Auflage. 2012.

(Online-Version)

Thinking in Java. B. Eckel. Prentice Hall 2006 (Online-Version).


Vorlesung & Übungen

Vorlesungen & Übungen

8

1. Regelmäßige und aktive Teilnahme in der Vorlesung

Fragen stellen!

2. Regelmäßige und aktive Teilnahme an den Übungen

Selbständige Lösung der Übungsblätter!

Grundlegende Regeln zum Erfolg sind:



9

Tutoren

Max Willert

Oliver Wiese

Julian Fleischer

Alexander Steen

Julius Auer

Nicolas Lehmann

?

?



Überfüllte Tutorien

10

Tag Uhrzeit

Montag 12-14

Freitag 12-14


Kriterien des Leistungsnachweises

Regelung für die Notenvergabe:

11

Regelung aus (ALP III bei Prof. Helmut Alt)

Die Prüfungsnote ergibt sich aus dem Wert

max( (z+k)/2, k, (z+n)/2, n )

Zum Bestehen der Prüfung muss dieser Wert mindestens 50 betragen.

Dabei sind:

- z - die Anzahl der erreichten Punkte in einer Mitte des Semesters stattfindenden Zwischenklausur (Stoff der ersten Semesterhälfte)

- k - die Anzahl der erreichten Punkte in einer Ende des Semesters stattfindenden Endklausur (Stoff des ganzen Semesters)

- n - die Anzahl der erreichten Punkte in einer Ende der nächsten Semesterferien stattfindenden Nachklausur (Stoff des ganzen Semesters)

- Jede Klausur hat dabei eine maximale Punktzahl von 100.



• Zusätzlich ist es den Teilnehmern möglich durch besonders

aktive mündliche Teilnahme an den Tutorien die Gesamtnote

um maximal 0,7 zu verbessern. Diese Bewertung wird von

den Tutoren individuell vorgenommen.

• Durch diese Verbesserung kann ein Bestehen der Klausur

nicht erreicht werden.

• Die beste zu erreichende Note ist 1,0.

12

Verbesserungsmöglichkeiten



Kriterien für die Bestätigung der regelmäßigen und aktiven Teilnahmen:

13

1. Eine regelmäßige Teilnahme an den Laborterminen ist unerlässlich.

2. Die Abgabe der Übungsblätter erfolgt dienstags um 8:25 Uhr. Nach diesem

Termin abgegebene Übungsblätter werden nicht berücksichtigt.

3. Jeder Student muss an mindestens n-2 Übungsterminen anwesend sein.

4. Jeder Student muss n-2 Übungsblätter bestehen. Ein Übungsblatt gilt als

bestanden, wenn man mind. 40% der zu erreichenden Punkte erreicht hat.

5. Jeder Student muss 60% der maximal erreichbaren Punktzahl aus allen

Übungsblättern erreichen.

6. Jeder Student muss mindestens zwei Mal seine Lösungen vorrechnen. Wer

jeweils vorrechnen muss, wird per Zufall am Anfang des jeweiligen Tutoriums

entschieden.

Einführung


Kann ein Student von der aktiven Teilnahmen befreit werden?

14

Filtertest

bestanden?nein passiert

nichts!Anmelden

ja

Befreiungstest

bestanden?nein passiert

nichts!

ja

Aktive Teilnahme

Einführung


Kann ein Student mit guten ALP2-Vorkenntnissen von der aktiven Teilnahme befreit werden?

15

• 1. Filtertest am Samstag den 14.04.2012 um 10:00 Uhr

• Jeder Student kann daran teilnehmen

• Eine Anmeldung ist die einzige Voraussetzung (Siehe Veranstaltungsseite)

• 2. Befreiungstest am Samstag den 21.04.2012 um 10:00 Uhr

• nur die Studenten, die den 1.Filtertest bestanden haben, dürfen mitschreiben.

• Beide Tests müssen bestanden werden, um eine Bestätigung der aktiven Teilnahmen zu

bekommen.

• Ein freiwilliges Sondertutorium wird

• für diese fortgeschrittenen Studenten eingerichtet

• Ziel ist es, trotz Vorkenntnisse Neues zu lernen und am Ball zu bleiben als

Sicherheit für ein gutes Klausurergebnis.

• offen auch für andere interessierte Studenten


Fragen

16

Fragen

Inhaltliche Fragen sind immer willkommen

– während und nach jeder Vorlesung

– in der Sprechstunde (Freitags 10-12)

Keine Emails mit organisatorischen Fragen!

ALP II: Margarita Esponda, 1. Vorlesung, 12.4.2012 17

Wie viele Programmiersprachen?

✴ Es gibt mehr als 2000 Programmiersprachen, die im kommerziellen

Bereich bekannt sind oder bekannt gewesen sind.

✴ mehr als 200 davon haben sich im Laufe der Geschichte stärker

verbreitet

✴ (einige) Firmen entwickeln eigene private Sprachen

✴ es gibt viele akademische Programmiersprachen

✴ und es kommen immer mehr Programmiersprachen hinzu

Geschichtliche Einführung



18

PROGRAM

PRINT *, "WELCOME TO FU!"

END PROGRAM

FORTRAN Cobol

00001 IDENTIFICAL DIVISION.

00002 PROGRAM-ID HELLO.

00004 ENVIROMENT DIVISION.

00005 CONFIGURATION SECTION.

00006 SOURCE-COMPUTER IBM-PC.

00008 OBJECT-COMPUTER IBM-PC.

00010 INPUT-OUTPUT SECTION.

00011 FILE-CONTROL.

00012 SELECT AUSGABE ASSIGN TO SI.

00013 DATA DIVISION.

00014 FILE-SECTION.

00015 FD AUSGABE

00016 LABEL RECORD OMITTED.

00017 01 DATA RECORD ZEILE PICTURE X(80).

00018 WORKING STORAGE SECTION.

00019 PROCEDURE DIVISION

00020 BEGIN.

00021 OPEN OUTPUT AUSGABE.

00022 MOVE "WELCOME TO FU!" TO ZEILE.

00023 CLOSE AUSGABE.

00024 STOP RUN.



19

Konzepte imperativer Programmierung

Die eigentliche Geschichte der Programmiersprachen begann mit:

• dem Konzept der von Neumann-Maschine, die 1945 die

Notwendigkeit eines gespeicherten Programms postulierte.

• und mit dem Konzept des "conditional control transfer"

• If-then-Anweisung

• looped-Anweisungen

• Subroutines (Funktionen)



20

Imperatives Programmieren

• Ältestes und populärstes Programmierparadigma

– Fortran, Cobol, Algol, C, Basic, Pascal, Modula,

Java, usw.

• Widerspiegelt die dahinter stehende Hardware-

Architektur

– von Neumann Maschine

– gespeichertes Programm + Daten

M. Esponda-Argüero

30er Jahre

21

Alonzo Church1903-1995

Stephen C. Kleene1909-1994

Lambda-Kalkül ✴universelle abstrakte Programmiersprache

✴nur die Hardware fehlte

Erste Programmiersprache

λ − Kalkül

Lisp 1958

Funktionale Programmiersprachen

Miranda HaskellFP

M. Esponda-Argüero 22

30er Jahre

Alan Turing (1912-1954)

“On computable numbers, with an

application to the Entscheidungsproblem”.

1936

Turing-Maschine

Ein Modell, um die Klasse der intuitiv berechenbaren Funktionen zu bilden.



23

Deklarative Sprachen Imperative Sprachen

ObjektorientierteProgrammiersprachen

Was? Wie?

Höhere Programmiersprachen

Funktionale Sprachen

Logische Sprachen

Prozedurale

AspektorientierteProgrammiersprachen

in ALP IIin ALP I



24

deklarativ vs. imperativ

- Sprachen basieren auf einem mathematischen Formalismus

- Wissen über ein Problem rein deklarativ darstellbar

- Intelligentes System, das Fragen an das Programm beantworten kann

- Sprachen sind von der

dahinterstehenden Hardware

geprägt

- Befehlssequenz (Zustände)

- zeitlicher Ablauf im Programm

sichtbar

kompakterrobustereinfacher

effizienter



25

Imperatives Programmieren

Grundlegende Operation: die Zuweisung

– Operation mit Nebeneffekten

Speicherinhalte werden verändert und damit der

Zustand der gesamten Maschine.

Kontrollfluss-Anweisungen

– unbedingte Sprünge:

GOTO-, break-, return-Anweisung usw.

– bedingte Sprünge:

if-then-else-Anweisung und Loop-Anweisungen (Schleifen).



26

Grundlegende Elemente von imperativen Programmen

• Definitionen von Datentypen

• Deklarationen von Variablen unter Verwendung vordefinierter

Datentypen

• Zuweisungen

• Ausdrücke

• Anweisungen für den Kontrollfluss innerhalb des Programms

• Gültigkeitsbereich von Variablen (locality of reference)

• Definition von Prozeduren und Funktionen



27

Wir werden grundlegende Konzepte der Imperativen Programmierung mit Beispielen in Python behandeln und als Vergleich manchmal C-Beispiele diskutieren.

Konzepte der Objektorientierten Programmierung werden wir anhand der Programmiersprache Java diskutieren.


Warum Python?

28

Warum Python?

• Einfache Syntax und Semantik

• Einfache Programmierumgebung

• Hybride Programmiersprache (Multi-Paradigma)

• Ermöglicht zuerst nur das rein imperative Programmieren

• Höhere Datenstrukturen sind in der Sprache integriert

• Plattformunabhängig

• In der realen Welt verwendete Sprache

• Umfangreiche Standardbibliothek


Warum Python?

“Python is an experiment in how much

freedom programmers need.

Too much freedom and nobody can

read another's code;

too little and expressiveness is

endangered.”

- Guido van Rossum

Einfache Syntax und Semantik Erfinder:Guido van Rossum

Warum Python?

M. Esponda-Argüero

Warum Python?

30


Warum C nicht?

Assemblersprachen

Hochprogrammiersprachen

C-Sprache C wurde ursprünglich für die Programmierung von

Betriebssystemen entworfen.

31

Warum C nicht?


Eigenschaften von C

Gute

Schlechte

Der Programmierer kann machen, was er will.

Der Programmierer kann machen, was er will.

Der C-Compiler geht davon aus, dass der Programmierer genau weiß, was er will, und meldet fast keine Warnungen beim Übersetzen des Programms.

Die meisten Fehler bei C-Programmen treten erst zur Laufzeit auf.

Warum C nicht?


C ist eine formatfreie Sprache!

m(f,a,s)char*s;

{char c;return f&1?a!=*s++?m(f,a,s):s[11]:f&2?a!=*s++?1+m(f,a,s):1:f&4?a--?

putchar(*s),m(f,a,s):a:f&8?*s?m(8,32,(c=m(1,*s++,"Arjan Kenter. \no$../.\""),

m(4,m(2,*s++,"POCnWAUvBVxRsoqatKJurgXYyDQbzhLwkNjdMTGeIScHFmpliZEf"),&c),s)):

65:(m(8,34,"rgeQjPruaOnDaPeWrAaPnPrCnOrPaPnPjPrCaPrPnPrPaOrvaPndeOrAnOrPnOrP\

nOaPnPjPaOrPnPrPnPrPtPnPrAaPnBrnnsrnnBaPeOrCnPrOnCaPnOaPnPjPtPnAaPnPrPnPrCaPn\

BrAnxrAnVePrCnBjPrOnvrCnxrAnxrAnsrOnvjPrOnUrOnornnsrnnorOtCnCjPrCtPnCrnnirWtP\

nCjPrCaPnOtPrCnErAnOjPrOnvtPnnrCnNrnnRePjPrPtnrUnnrntPnbtPrAaPnCrnnOrPjPrRtPn\

CaPrWtCnKtPnOtPrBnCjPronCaPrVtPnOtOnAtnrxaPnCjPrqnnaPrtaOrsaPnCtPjPratPnnaPrA\

aPnAaPtPnnaPrvaPnnjPrKtPnWaOrWtOnnaPnWaPrCaPnntOjPrrtOnWanrOtPnCaPnBtCjPrYtOn\

UaOrPnVjPrwtnnxjPrMnBjPrTnUjP"),0);}

main(){return m(0,75,"mIWltouQJGsBniKYvTxODAfbUcFzSpMwNCHEgrdLaPkyVRjXeqZh");}

smile.c „The International Obfuscated C Code Contest“

33

Warum C nicht?


Java

public class HelloWorldProgram {

}

public static void main ( String[] args ) {

}

System.out.println( "Welcome to FU!" );

34



#include <stdio.h>

int main(void){

printf( "'Welcome to FU!'\n" );

return 0;

}

C

35



Python

print ('Welcome to FU!')

Python 3.x

36


Normalisierte Ergebnisse aus der Popularität in:

- Open-Source-Projekte

- Powell`s Books

- Job-Angebot

- Popularität in der Software-Industrie

- Google Code Search

- usw.

Quelle: http://langpop.com/ (DedaSys. Open Source Consulting) 2011

In der realen Welt verwendete Sprachen

Popularität der Programmiersprachen

Quelle: TIOBE Programming Community Index for April 2011

- Android-Anwendungen- mehr als 500.000

Keine Laptops

39

NO LAPTOPS

M. Esponda-Argüero


Mitschriften

Hörsaal der Zukunft?

40


Homepage

http://www.inf.fu-berlin.de/lehre/SS12/ALP2/

Vorlesungsfolien

Literaturliste

Übungen

Zusätzliches Material

Wichtige Mittteilungen

[email protected]

41

Sprechstunde: Fr. 10:00 - 12:00 Uhr

Raum 161

Homepage


Mitschriften

Warum ist Mitschreiben wichtig?

Das Mitschreiben hat folgende Vorteile:

• Es erhöht die Aufmerksamkeit und fördert die Konzentration

• Es regt dazu an, sich aktiv zu beteiligen

• Es individualisiert den Lernstoff und bildet eine gute

Grundlage für die Klausurvorbereitung

Fragen zuerst aufzuschreiben hat viele Vorteile.

42


Attack of the Note Sheep

43


Ich freue mich auf eine gute Zusammenarbeit und auf ein erfolgreiches Lernen!

Documents

Algorithmen und Programmieren II Konzepte imperativer und ...¼hrung_ALP2.pdf · ALP II: Margarita Esponda, 1. Vorlesung, 12.4.2012 Inhalt 3 1. Konzepte imperativer Programmierung