Slide 1

Slide 2

Algorithmen, Programme, Sprachen

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Programm-  &  Sprachelemente

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Gestaltung von Programmen (Grundsätzliches)
Grundsätzliches
Quelltext eines Programms (= Nachricht)
Þ Arbeitsergebnis, Doku, Unterlage 
(
® Wartung, Programmerweiterung ...)
Grundregeln zu Programmaufbau und -gestaltung
jedes Programm besteht aus (mehreren) Modulen
jeder Modul ist ein eigenes Dokument
Quelltext ist zeilenweise organisiert, mit je 1 Anweisung oder Vereinbarung pro Zeile
Verwendung von Leerzeilen (Absetzen von Blöcken)
Einrücken von Anweisungen
sinnvolle Verwendung von Kommentaren (*  ... *)

Gestaltung von Programmen (Grundsätzliches)
Kommentare
Syntax: beliebiger, in (*  ...  *) eingeschlossener Text
sinnvoll einsetzen:
Modulanfang: Kurzbeschreibung der Aufgabe
Beschreibung der Ein- und Ausgabegrößen
Erläuterung des logischen Programmablaufs
(grob strukturierter Algorithmus, Invarianten)
Erklärung von Variablen, Typen, .... (falls nötig)
Kennzeichnung von END
nicht sinnvoll: Unter-, aber auch Überkommentierung

Slide 48

Übersetzung von Programmen („Compilation“)

Übersetzung und Ausführung von Programmen
Übersetzung
m2c <Name>.m2
Aufruf des Modula-2 Compilers (Programmstart)
input = <Name>.m2; output = a.out (ausführbares Programm)
m2c  -o  <Name>  <Name>.m2
-o ist Compileroption
das ausführbare Programm heisst statt a.out jetzt <Name>
Ausführung
Start mittels ...$ a.out
bzw. Start mittels ...$ <Name>

Einfache Datentypen

Eigenschaften eines „Typs“
Grundsätzliches
Der (Daten-)Typ kennzeichnet die aktuelle Wertemenge eines Objekts (Konstante, Variable, Ausdruck, Funktion, ...)
Typ-Zuweisung durch Vereinbarung (= Deklaration)
Eigenschaften
Der Datentyp bestimmt die Wertemenge,
zu der eine Konstante gehört.
deren Werte durch eine Variable oder einen Ausdruck angenommen werden können.
deren Werte durch einen Operator oder eine Funktion berechnet werden können.
Der Datentyp ist anhand seiner Notation oder Vereinbarung erkennbar.
Jeder Operator bzw. jede Funktion
erwartet Argumente eines bestimmten Typs
liefert Resultate eines bestimmten Typs

Slide 52

Slide 53

Einfache Standardtypen
Cardinal
Wertemenge: nicht-negative ganze Zahlen
       {0,1, ... ,MaxCard}; MaxCard = 232 - 1
Deklaration: 
VAR c,anzahl,monat,hausnummer: CARDINAL;
Ein-/Ausgabe:
FROM InOut IMPORT ReadCard(var),Write(var,breite);
Operationen:
Addition +
Subtraktion –
Multiplikation *
ganzzahlige Division mit Rest DIV, MOD
Vergleiche =,<>,>=,>,<=,<

"Integer"
Integer
Wertemenge: vorzeichenbehaftete ganze Zahlen
       {-2N-1, ... ,2N-1-1}; N = 32
Deklaration: 
           VAR  k, wert,index,faktor: INTEGER;
Ein-/Ausgabe:
           FROM InOut IMPORT ReadInt(var),WriteInt(var,breite);
Operationen:
Addition +
Subtraktion –
Multiplikation *
ganzzahlige Division mit Rest DIV, MOD
Vergleiche =,<>,>=,>,<=,<
Vorzeichenumkehrung –
Konvertierung « Cardinal
VAR   i,int : INTEGER;
      c,card : CARDINAL;
i:= INTEGER(card);
c:= CARDINAL(int)

"Definition von DIV und MOD"
Definition von DIV und MOD
(x,y) ® (q,r)  mit  x,y,q,r Î N (oder Z)
wobei x DIV y
® q („Quotient“)
x MOD y
® r („Rest“)
x DIV y = floor(x/y) =: q
wobei q > 0, if sgn(x)=sgn(y)
q = 0, if abs(x)<abs(y)
q < 0, if sgn(x)
¹sgn(y)
x MOD y =: r
wobei r = x - (x DIV y)
·y,  if  r ³ 0
r = x - (x DIV y)·y + y,  if  r < 0
„DIV-MOD“ - Identität
(x DIV y)
·y + (x MOD y) = x

"Boolean"
Boolean
Wertemenge: Wahrheitswerte {FALSE,TRUE}, auch {0,1}
Deklaration: 
           VAR  present,billig,laut,gefunden : BOOLEAN;
Ein-/Ausgabe:
           keine!
Operatoren:
Negation, Verneinung NOT ~
Konjunktion, logisches UND AND &
Disjunktion, logisches ODER OR
Vergleichsoperationen
Gleichheit =
Ungleichheit <> #
Mengenzugehörigkeit? IN
Operatoren sind zweistellig
Beispiel: (x<y) AND (y<z)
falsch: x<y<z

"Boolean (cont‘d)"
Boolean (cont‘d)
Verwendung
Ausdruck einer erfüllten oder nicht erfüllten Eigenschaft
Variablen vom Typ BOOLEAN sollten Eigenschaftsworte sein
Boolean in Bedingungen: 
           IF billig THEN ... ELSE ...
anstatt: IF billig = TRUE THEN ... ELSE ...

           IF NOT billig THEN ... ELSE ...
anstatt: IF billig = FALSE THEN ... ELSE ...

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

"Character"
Character
standardisierter Zeichensatz
Festlegung einer rechnerinternen Darstellung von Zeichen (Bitmuster)
Festlegung einer Ordnung über der Zeichenmenge
Beispiel: ASCII (American Standard Code for Information Interchange)
M ist größer als !, denn (M « 33D « 21H), (! « 77D « 4DH)
Deklaration: 
           VAR  ch1,ch2,ch3 : CHAR;
Zuweisung:
           ch1 := "a";
ch2 := 'b';
ch3 := 65C; (65C ist ASCII-Oktal-Code für 5 (
« 53D « 35H))
Ein-/Ausgabe:
           FROM InOut IMPORT Read,Write;
Operationen: Vergleiche auf Basis der ASCII-Ordnung
ORD(ch) liefert den ASCII-Wert (Ordnungsnr.) des Characters ch
CHR(z) liefert den Character zum ASCII-Wert z (0 £ z < 128)
es gilt: CHR(ORD(ch)) = ch und ORD(CHR(z)) = z

"Real"
Real
Wertemenge: darstellbare reelle Zahlen (beschr. Stellenzahl)
Deklaration:
           CONST  pi = 3.1415;
           VAR  coeff,std,temp: REAL;
Ein-/Ausgabe:
FROM RealInOut IMPORT   ReadReal(var),
WriteReal(var,minstellen);
Operationen:
Addition +
Subtraktion –
Multiplikation *
Division /
Vergleichsoperatoren =,<>,>=,>,<=,<
alle Op. auf REAL-Werten sind Approximationen (Genauigkeit von Maschine/Implementierung))
Konvertierung
FLOAT: CARDINAL / INTEGER  ®   REAL
TRUNC: REAL  ®  CARDINAL / INTEGER

Operationsprinzipien - Anweisungen

Allgemeines
Ein Programm manipuliert Daten
Operationen ® Datenmanipulation (d.h. Zustandsänderung)
Aktionen (® Zustandsänderung) werden in Anweisungen (statements) beschrieben

Slide 67

Zuweisung und Ausdrücke
Zuweisung („assignment“) :=
Syntax

Zuweisung und Ausdrücke
Ausdruck („expression“)
Auswerteregeln: links ® rechts, algebraische Regeln

Zuweisung und Ausdrücke
Ausdruck („expression“) (cont‘d)
Beispiele:
3.0 * 8.0 / 4.0 * 5.0  Û   ((3.0 * 8.0) / 4.0) * 5.0
2 * 3 - 4 * 5 Û (2 * 3) - (4 * 5)  =  -14
80 / 5 / 3 Û (80 / 5) / 3  = 5.333
SQRT(SQR(3) + 11*5)  =  8.000
4  =  0 ®  = FALSE
Syntax einfacher Ausdrücke

Zuweisung und Ausdrücke
Ausdruck („expression“) (cont‘d)
Rangfolge von Operatoren
logische Negation NOT(~)
Multiplikationsoperatoren *, /, DIV, MOD, AND(&)
Additionsoperatoren +, – , OR
Relationaloperatoren =, <>, >=, >, <=, <, IN

Leere Anweisungen und Anweisungsfolgen
Leere Anweisung („empty statement“)
Anweisung ohne Wirkung für Programmstellen, an denen syntaktisch eine Anweisung vorkommen muss, jedoch keine Aktion stattfinden soll
Anweisungsfolgen
Aneinanderreihung von Anweisungen
Klammerung
explizit: BEGIN ... END bei Moduln, Prozeduren
implizit: Auswahl, Wiederholung, ...

Verzweigungen - Fallunterscheidungen
IF - Anweisung
Struktur: Einfachauswahl
IF   logische Bedingung  THEN  ...  ELSE  ...  END
falls  logische Bedingung = true ® Abarbeitung der THEN-Anweisungsfolge ...
falls  logische Bedingung = false ® Abarbeitung der ELSE-Anweisungsfolge ...
Struktur: Mehrfachauswahl
IF   ...  THEN  ... 
ELSIF ...  THEN  ...
    
M
ELSE  ...  END
Syntax

Verzweigungen - Fallunterscheidungen
CASE - Anweisung
n unabhängige Ausgangssituationen (cases); jede ist mit einer Aktion verbunden
Struktur
CASE  Ausdruck zur Fallunterscheidung  OF
K  :  ... ¬ Fall 1
K  :  ... ¬ Fall 2

 
M

ELSE  ...
¬ Fall n oder der „Rest“
END
Syntax

Slide 75

Slide 76

Slide 77

Slide 78

Wiederholungsanweisungen
WHILE ... DO ...... END
vorangestellte Bedingung (kopfgesteuerte Schleife)
solange Bedingung gilt, führe Anweisungsfolge aus
REPEAT ...... UNTIL ...
nachgestellte Bedingung (fußgesteuerte Schleife)
führe Anweisungsfolge aus, bis (Abbruch-)Bedingung erfüllt ist
FOR ... TO ... [BY ...] DO ...... END
feste Zählschleife (kopfgesteuerte Schleife)
führe Anweisungsfolge aus, solange der Index sequentiell verändert wird.
LOOP ...... END
einfache Schleife (loop)
führe Anweisungsfolge aus, solange bis Schleife per EXIT verlassen wird

Wiederholungsanweisungen
fußgesteuerte Schleifen
die zu wiederholenden Anweisungen werden zunächst ausgeführt.
Danach wird die Schleifenbedingung geprüft
ist die Schleifenbedingung erfüllt, so wird an den Anfang des Anweisungsblocks gesprungen
kopfgesteuerte Schleifen
bevor die zu wiederholenden Anweisungen ausgeführt werden, wird erst einmal die Schleifenbedingung geprüft.
ist die Schleifenbedingung nicht mehr erfüllt, so wird an das Ende des Anweisungsblocks gesprungen
sicherer als fußgesteuerte Schleifen

Wiederholungsanweisungen

Wiederholungsanweisungen
WHILE-Schleife
Struktur:
WHILE Bedingung DO
M (*Anweisungsfolge*)
END
Syntax:

Wiederholungsanweisungen
REPEAT-Schleife
Struktur:
REPEAT
M (*Anweisungsfolge*)
UNTIL Bedingung
Syntax:

Wiederholungsanweisungen
FOR-Schleife
Struktur:
FOR index:=ausdruck1 TO ausdruck2 BY KonstAusdruck DO
M (*Anweisungsfolge*)
END
Syntax:

Wiederholungsanweisungen
FOR-Schleife (cont‘d)
Hinweise:
Die Anweisungsfolge wird mit fest vorgegebener Wertefolge durchlaufen
index = Zählvariable (Laufvariable); Ausdruck1 = Startwert von index
Ausdruck2 = Endwert der Iteration
KonstAusdruck = Schrittweite der Laufvariable (= 1 falls nichts angegeben)
Ausdruck1, Ausdruck2, KonstAusdruck dürfen in der Anweisungsfolge nicht verändert werden (ggf. WHILE bzw. REPEAT verwenden)
index ist nach Abarbeitung der FOR-Anweisung undefiniert!

Slide 86

Wiederholungsanweisungen
Loop-Anweisung
Struktur:
LOOP
M (*Anweisungsfolge mit EXIT(s)*)
END (*LOOP*)
Syntax:

Slide 88

Slide 89

Konvertierung: REPEAT « WHILE
... im Prinzip durch Negierung der Schleifenbedingung
beachte bei logisch (mit und / oder) zusammengesetzten Bedingungen die de Morgan‘schen Regeln!
Beispiel:
Bedingung: q OR (i = n)
negierte Bedingung: (NOT q) AND (NOT(i=n))
              also: (NOT q) AND (i<>n)
Beispiel: WHILE ® REPEAT (nicht zu empfehlen)
WHILE bedingung DO anweisung END
 
konvertiert in:
IF bedingung THEN
REPEAT anweisung UNTIL NOT bedingung
END

Konvertierung: REPEAT « WHILE
Beispiel: REPEAT ® WHILE
mit Code-Verdopplung

REPEAT anweisung UNTIL abbruchbedingung
 
konvertiert in:
 
anweisung;
WHILE NOT abbruchbedingung DO anweisung END
mit Schaltervariable schalter

REPEAT anweisung UNTIL abbruchbedingung
 
konvertiert in:

schalter := TRUE;
WHILE schalter DO
anweisung;
schalter = NOT abbruchbedingung
END

Programmbeispiele
größter gemeinsamer Teiler (ggT)
Der ggT(a,b) zweier ganzer Zahlen a und b ist die größte ganze Zahl, durch die sowohl a als auch b teilbar ist.
Beispiel: ggT(16,36) = 4
Anwendung: optimales Kürzen
Es gilt:
ggT(a,a) = a falls b = a
ggT(a,b) = ggT(a-b,b) falls b < a
ggT(a,b) = ggT(a,b-a) falls b > a
® iteratives Programm zur Berechnung des ggT
effektiver: Euklid‘scher Algorithmus für a ³ b:
ggT(a,b) = b falls a MOD b = 0
ggT(a,b) = ggT(b, a MOD b) sonst

Slide 93

Slide 94

Slide 95

Typ-Definition
Einordnung
bisher: „nur“ vordefinierte Datentypen (Standardrepertoire der Sprache)
jetzt: Datentypen selbst definieren
Aufzählungs- und Unterbereichstypen ® Mittel zur Strukturierung
kompliziertere Strukturen ® Mittel zur Abstraktion (später)
Syntax

Aufzählungs- und Unterbereichstypen
Allgemein:  Ordinal-Datentypen (geordnet)
bisher: vordefinierte Datentypen mit interner Ordnung
jetzt: explizite Definition von Wertemengen durch
Aufzählung (Reihenfolge = Ordnung)
Selektion von Teilmengen (Unterbereiche)
Aufzählungstyp (“enumeration”)
eine geordnete Menge von Werten wird spezifiziert durch Aufzählung (konstanter Identifikatoren)
Beispiele:
mit Variablendeklaration

VAR
 Tag : (Montag, Dienstag, Mittwoch, Donnerstag,
   Freitag, Samstag, Sonntag);

 Farbe : (Weiss, Rot, Blau, Gelb, Gruen, Schwarz);

Aufzählungs- und Unterbereichstypen
Aufzählungstyp (“enumeration”) (cont‘d)
Beispiele:
mit Typdefinition

TYPE
  Wochentag = (Montag, Dienstag, Mittwoch, Donnerstag,   Freitag, Samstag, Sonntag);
  FarbPalette = (Weiss, Rot, Blau, Gelb, Gruen, Schwarz);

VAR
  Tag : Wochentag;
  Farbe : FarbPalette;
wäre BOOLEAN nicht schon Standard

TYPE
  BOOLEAN = (FALSE, TRUE)

Aufzählungs- und Unterbereichstypen
Aufzählungstyp (“enumeration”) (cont‘d)
Bemerkungen:
Elemente müssen eindeutig definiert sein, dürfen also nicht in 2 Typen vorkommen
Bezeichner dürfen nur in einer festgelegten Bedeutung vorkommen
Beispiele:  Karte : (7, 8, 9, Bube, Dame, König, 10, As)
         Tag   : (MO, DI, MI, DO, FR, SA, SO)
aber erlaubt: 
         Tag   : (Mo, Di, Mi, Do, Fr, Sa, So)
die Elemente einer Aufzählung erhalten analog ihrer Position in der Aufzählung eine Ordnungszahl zugeordnet
Operationen und Aktionen
Wertzuweisung wie gewohnt: Tag := Dienstag; Farbe := Blau;
durch die Def. der Ordnung sind Vergleiche möglich {=,<>,<,<=,>,>=}
Funktionen
Minimum, Maximum: MIN(T ) = a0 , MAX(T) = an ¬ Typ T = (a0,a1,...,an)
Ordnungszahl- und Wertfunktion: ORD(...), VAL(...)
mit: ORD(x) = VAL(CARDINAL,x)
Nachfolger und Vorgänger: INC(...), DEC(...)

Aufzählungs- und Unterbereichstypen
Aufzählungstyp (“enumeration”) (cont‘d)
Bsp: MIN, MAX, ORD, INC, DEC bei einem Aufzählungstyp

Aufzählungs- und Unterbereichstypen
Unterbereichstyp (“subrange”)
Festlegung eines Unterbereichs des Definitionsbereichs eines ...
vordefinierten Typs
eigens definierten (Ordinal-)Typs
der Grundtyp ist der “Träger (host type)”
Syntax

Aufzählungs- und Unterbereichstypen
Unterbereichstyp (“subrange”) (cont‘d)
Beispiele:
Typdefinition

TYPE
  Buchstabe = [“a” .. “z”];
  Ziffer = [0 .. 9];          (*Grundtyp CARDINAL*)
  ZahlInt = INTEGER[1 .. 10];
  Wochentag = (Mo, Di, Mi, Do, Fr, Sa, So);
  VL_Tag = [Mo .. Fr];
  BYTE = [0 .. 255];
Variablendefinition

VAR
  CAPITAL : [“A” .. “Z”];
  OktZiffer : Ziffer[0 .. 7];

Aufzählungs- und Unterbereichstypen
Unterbereichstyp (“subrange”) (cont‘d)
Hinweise:
Verwendung eines AufzTypName (hier INTEGER, Ziffer) zur Verdeutlichung des Grundtyps (Bsp.: CARDINAL vs. INTEGER)
der Trägerdatentyp bestimmt die Menge der erlaubten Operationen
bei Operationen auf Unterbereichstypen dürfen die Ergebnisse den Wertebereich nicht verlassen
Unterbereiche auf REAL nicht erlaubt

Slide 104

Aufzählungs- und Unterbereichstypen
Kompatibilität (auch für strukturierte Daten)
Typkompatibilität
strenge Regeln bzgl. der verträglichkeit von verschiedenen Typen in Ausdrücen und Zuweisungen!
2 Typen sind identisch, wenn sie in einerTypdefinition gleichgesetzt werden
2 Typen haben den gleichen Grundtyp, wenn sie Unterbereiche des gleichen Typs sind.
Ausdruckskompatibilität
Alle Operanden in einem Ausdruck haben den gleichen Typ oder den gleichen Grundtyp
Zuweisungskompatibilität
Variable W sei vom Typ V, Ausdruck A von Typ E;
Zuweisung W := A ist möglich, falls (Auswahl):
V und E sind gleich oder haben gleichen Grundtyp
V hat Grundtyp CARDINAL,E hat Grundtyp INTEGER oder umgekehrt
V hat Grundtyp CHAR und E ist einelem. oder leere Stringkonstante
V ist vom Typ ADDRESS,E ist vom Typ POINTER oder umgekehrt

Datenstrukturen
Einordnung
bisher: „nur“ einfache Objekte eines Typs ® unstrukturierte Typen
jetzt:
strukturierte Objekte (statisch) ® Komponenten
dynamische Objekte ® Zeiger, Dateien

Slide 107

Datenstrukturen

ARRAYs (Felder)

ARRAYs (Felder)

ARRAYs (Felder)

ARRAYs (Felder)

ARRAYs (Felder)

ARRAYs (Felder)

ARRAYs (Felder)

RECORDs ((Daten-)Verbunde)
in anderen Sprachen: „structure“

RECORDs ((Daten-)Verbunde)

RECORDs ((Daten-)Verbunde)

RECORDs ((Daten-)Verbunde)

RECORDs

RECORDs

RECORDs