Algorithmen, Programme, Sprachen
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 | |||
Ü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 |
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 | |||
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 | ||
(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 | |||
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) | |||
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 ... |
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 | |||
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 | ||
Zuweisung („assignment“) := | ||
Syntax |
Ausdruck („expression“) | ||
Auswerteregeln: links ® rechts, algebraische Regeln |
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 | |||
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 |
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 | ||
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 | ||
WHILE-Schleife | ||
Struktur: WHILE Bedingung DO M (*Anweisungsfolge*) END |
||
Syntax: | ||
REPEAT-Schleife | ||
Struktur: REPEAT M (*Anweisungsfolge*) UNTIL Bedingung |
||
Syntax: | ||
FOR-Schleife | ||
Struktur: FOR index:=ausdruck1 TO ausdruck2 BY KonstAusdruck DO M (*Anweisungsfolge*) END |
||
Syntax: | ||
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! | |||
Loop-Anweisung | ||
Struktur: LOOP M (*Anweisungsfolge mit EXIT(s)*) END (*LOOP*) |
||
Syntax: | ||
... 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 |
|||
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 |
||
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 |
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 |
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 |
Einordnung | |||
bisher: „nur“ einfache Objekte eines Typs ® unstrukturierte Typen | |||
jetzt: | |||
strukturierte Objekte (statisch) ® Komponenten | |||
dynamische Objekte ® Zeiger, Dateien | |||