Gratis Newsletter !
Der Schultreff-Newsletter informiert Dich stets über neue Arbeiten und mehr rund um Schultreff.
Du kannst Dich jederzeit wieder abmelden.
|
|
Informatik I Zusammenfassung
von Sascha Klüppelholz
WS 98/99 - Universität Bonn
Prof. Strelen
Referenzen : 1. Klaeren : Herbert Klaeren - "Vom Problem zum Programm"
ISBN 3-519-12242-1
2. Broy : Manfred Broy - "Informatik - Eine grundlegende Einführung"
ISBN 3-540-63234-4
3. Vorlesungsmitschriften WS 98/99 - 12.10.98 bis 12.2.99
Inhalt : 1. Algorithmen
2. Spezifikationen
3. Pseudocode
4. Korrektheit
5. Rechenaufwand
6. Entwicklungsmethoden
7. Programmiersprachen
8. MINI-PASCAL
9. Semantik von Programmiersprachen
10. (Binär)(e)(Such)Bäume
11. Information/ Repräsentation
12. Boolsche Terme
13. Sortieralgorithmen
14. Textersetzungsalgorithmen
15. Rechenstrukturen
16. Signaturen
Anhang :
- Bemerkungen
- Begriffe
Algorithmen (Klaeren Seite 17 und Broy Seite 31) :
1. schematisches (Lösungs)Verfahren in endlichem Text beschrieben
2. besteht aus einzelnen Anweisungen (Finitheit)
3. in einer eindeutigen Reihenfolge (Determiniertheit)
4. gewisse Parameter/ Eingabewerte
5. nach endlich vielen Rechenschritten terminiert (Terminiertheit)
6. liefert ein eindeutiges Ergebnis
7. Menge von Regeln eines Verfahrens, um Eingabegrößen bestimmte Ausgabewerte zuzuordnen
8. jeder einzelne Schritt muß ausführbar sein (Effektivität)
9. Beispiele finden sich auch im täglichen Leben (Gebrauchsanweisungen)
10. im Allgemeinen dient ein Alg. zur Lösung einer Klasse von Problemen
11. Ein Alg. beschreibt also eine Informationsrepräsentationsumformung
12. sequentiell : wenn alle Schritte hintereinander ausgeführt werden
13. parallel : wenn gewisse Schritte nebeneinander ablaufen
14. Rekursion als wichtiges Hilfsmittel. Wiederholungen mit
vereinfachten Parametern
Betrachtung der verschiedenen Aspekte eines Alg. :
- Aufgabenstellung (funktional)
- Art und Weise (operational) :
a) elementare Verarbeitungsschritte (Wertzuweisungen, Vergleiche)
b) Kontrollfluß (Beschreibung der Auswahl)
c) Daten und Parameter
Also gibt es immer unterschiedliche Möglichkeiten zur Lösung eines Problems.
Unterscheidung Algorithmus und Programm (Klaeren Seite 21) :
Unterscheidung lohnt sich nicht. Programme sind spezielle Erscheinungsformen von Alg. =
Alg. als Oberbegriff für Programm. Ein Programm ist eine Beschreibung
eines Alg. in einer formalen Sprache - der Programmiersprache. Pseudocode
als halbformale, programmiersprachenähnliche Notation für Algorithmen.
Spezifikationen (Klaeren Seite 21) :
1. Präzise umgangssprachliche Beschreibung des Problems
2. {P} Prämisse oder Vorbedingung
3. A für Anweisung
4. {Q} für Konsequenz
5. jedes Programm beginnt mit {P} und endet mit {Q}
6. jede Anweisung bekommt zum Beweis der Korrektheit eine Vor- und eine Nachbedingung
7. Spezifikationsregel : Spezifikation beschreibt mögliche Eingaben (Definitionsbereich)
und die Menge der möglichen Ausgaben (Wertebereich) und den funktionalen Zusammenhang
zwischen diesen
8. In einer Spezifikation sollten auch schon die Variablenbezeichner des entstehenden
Programms explizit benannt sein.
9. zur Spezifikation gehören :
Deklarationsteil : Konstanten : falls notwendig. Bezeichner angeben !
Typen : problemspezifische Datentypen wie Bezeichner für Trägermengen
bestehend aus Typenbezeichnern und Funktionsbezeichner
Funktionen : Funktionsbezeichner müssen genannt werden
Prädikate : vereinbart Prädikatsbezeichner zu Funktionen die
einen Wahrheitswert zurückgeben
Eingabe : Variablenbezeichner für Eingabeparameter denen Bereiche/ Typen zugeordnet
werden
Vorbedingung : Menge von Prädikaten, welche die Eingabe erfüllen
Verfahren : informelle Beschreibung des Alg. (in Pseudocode)
Ausgabe : Variablenbezeichner für die Ausgabeparameter mit zugehörigen Typen
Nachbedingung : Menge von Prädikaten, die der Aufgabenstellung entsprechen sollen
10. Spezifikationen als Schnittstelle zwischen Auftraggeber und Programmierer
11. Spezifikationen sind ein wesentlicher Teil der Problemlösung
Pseudocode (Klaeren) :
- endliche Folge von Anweisungen
- eine Anweisung ist ein einfacher Befehlssatz in natürlicher Sprache
- Anweisungen : Wertzuweisungen, (While)Schleifen, bedingte Anweisungen
- Gliederung durch Einrücken und Absätze empfohlen
Korrektheit von Programmen (Klaeren Seite 51) :
- Testen ist kein Beweis (Regel vom Testen : Durch Testen kann nur die Anwesenheit von
Fehlern bewiesen werden - nicht aber die Abwesenheit) Es sollten mehrere Regelfälle
und möglichst alle Sonderfälle getestet werden.
- Ein Alg. heißt korrekt, wenn er unter gegebener Vorbedingung und einem terminierenden
Verfahren, die gegebene Nachbedingung erfüllt. D.h. wenn jede Eingabe unter {P}
nach dem Verfahren {Q} erfüllt.
- zum Beweis eines Alg. ist vor jeder Anweisung eine Vorbedingung und nach jeder Anweisung
eine Nachbedingung einzufügen, so daß das erste {P} am Ende des Alg. in {Q} übergeht.
- Ein Anweisungsblock terminiert, wenn es eine obere bzw. untere Schranke gibt und
sind der entsprechende Wert bei jedem Schleifendurchlauf verkleinert bzw. vergrößert.
- (endliche) Wertzuweisungen terminieren immer (Annahme)
- {P}A{Q} liefert true für : nicht P, P und A terminiert nicht, und P A Q
- Hoare-Kalkühl (ohne Rekursion, exit, endif besagt :
1. Einfügen von {P} und {Q} für jede Anweisung und zeige partielle Korrektheit
aller Anweisungen.
2. Beweise Korrektheit des gesamten Verfahrens aus der partiellen Korrektheit
3. Verifikationsregeln (Prämisse und Konsequenz) :
- Zuweisungsaxiom : {P(t)}x:=t{P(x)}
wenn Vorbedingung für t gilt und x:=t zugewiesen wird gilt P nach A auch für x
- Sequenzregel : {P}A1{Q} + {Q}A2{R} = {P}A1A2{R}
die Nachbed. von A1 entspricht der Vorbedingung von A2 = Wegfall der mittleren Bed.
- Alternativregeln : {P+pi}A1{Q} + {P+not pi}{Q} = {P}if pi then A1 endif{Q}
{P+pi}A1{Q} + {P+not pi}A2{Q} = {P}if pi then A1 else A2 endif{Q}
- Interationsregel : {P+pi}A{P} = while pi do A endwhile{P+not pi}
- Konsequenzregeln : R=P + {P}A{Q} = {R}A{Q} (stärkere Vorbedingung)
{P}A{Q} + Q=R = {P}A{R} (schwächere Nachbedingung)
4. Korrektheit von Schleifen muß induktiv bewiesen werden. (Gilt für 1. Durchlauf, für n+1
und für das Ende der Schleife)
Rechenaufwand (Klaeren Seite 60) :
- terminiert der Alg. ?
- Effektivität zählt (prinzipiell machbar)
- Effizienz (wirtschaftlich sinnvoll)
- terminiert der Alg. in einer sinnvollen Zeit (Aufwandsabschätzung)
- Einheit für Rechenaufwand : Anzahl der Anweisungen (Vergleiche, Wertzuweisungen)
- Bei Rekursion ebenfalls Rechenschritte zählen
- verschiedene Fälle behandeln : Sonderfälle, minimaler Aufwand, maximaler Aufwand
- durchschnittlicher Aufwand ist meistens schwer abzuschätzen
- O-Notation :
- Einbahngleichung
- Angabe über Obergrenze
Entwicklungsmethoden (Klaeren Seite 34 und Broy Seite 85) :
Es gibt ein paar Eigenschaften, die bei der Entwicklung von
Programmen beachtet werden sollten (Software Engineering) :
- Korrektheit (siehe oben)
- Lesbarkeit (Absätze, einrücken etc.)
- Änderbarkeit (Kommentare, eindeutige Bezeichner)
- Wiederverwendbarkeit (möglichst breite Anwendungsbereich)
- Effizienz
- Speicheraufwand
- Rechenaufwand
- Rechenzeit
Wichtige Schritte bei der Entwicklung von komplexen Programmen :
Es gehört zu den Aufgaben des Informatikers sich frühzeitig
auch Gedanken über die wirtschaftliche Konsequenzen und den Sinn
zu machen. Daher ist es unbedingt erforderlich sich vor dem Beginn
des eigentlichen Programmierens strukturierte und detaillierte
Gedanken zu machen :
- Spezifikation
a) Systemanalyse (Strukturen, Zusammenhänge erfassen)
b) Anforderungsdefinition (Festlegung der Problemstellung)
c) Nebenbedingungen finden - falls vorhanden
- Vorgehensweise festlegen, Machbarkeit, Arbeitsplan)
- Strukturierung/ Aufspaltung in Teilaufgaben
a) Rechenstrukturen festlegen
b) Funktionalität der Programmeinheiten genau festlegen
c) Wahl der Datenstruktur und Alg.
- Dokumentation der Programmteile
a) evtl. grafisch
b) Wirkung beschreiben
c) Verwendungsformen der Parameter
d) Dokumentation der globalen Variablen
Entwicklungsansätze :
1. Top-Down-Methode :
- schrittweise Verfeinerung (Unterteilung in Teilprobleme/ Divite & Conquer)
- von der Quellmaschine zur Zielmaschine (siehe abstrakte Maschinen)
- Regel von der minimalen Festlegung : Es soll mit demjenigen Unterproblem begonnen werden,
dessen Lösung am wenigsten von den anderen abhängt und deswegen dessen Lösung am
wenigsten festlegt.
2. Bottom-Up-Methode :
- von der Zielmaschine zur Quellmaschine (siehe abstrakte Maschinen)
Programmiersprachen (Klaeren Seite 94 und Broy Seite 90) :
Applikative/ Funktionale Programmiersprachen :
Funktionsanwendungen sind das dominierende Mittel. Diese Programmier-
sprachen bestehen in der Regel aus einer gewissen Anzahl von
Funktionen und einem Ausdruck der mittels dieser erzeugt werden soll.
Man unterscheidet primitive Terme und Ausdrücke. Primitive Terme
sind sofort berechenbar, während Ausdrücke Funktionsbezeichner enthalten.
Zuweisungsorientierte Programmiersprachen :
äquivalent zu applikativen Programmiersprachen, aber verwendet
repetitive Rekursion. Namensgebung durch die Nähe zur Neumann-Maschienen-
Struktur (linear angeordneter Speicher für Daten und Programme)
- Programmiersprachen sind formale Sprachen, da Syntaxregeln streng eingehalten werden müssen
im Gegensatz zur Umgangssprache
- wichtig neben der Syntax ist die Semantik/ Bedeutung (oft verschiede Syntax für gleiche Sem.)
- abstrakte Syntax versucht lediglich das wesentliche zu erfassen
- Syntaktische Beschreibungsmittel :
- Chomsky-Grammatiken - Unterscheidung zwischen :
1. kontextsensitiven Sprachen (Typ 1)
2. kontextfreie Sprachen (Typ 2) <= BNF
3. reguläre Sprachen (Typ 3) mit regulärer Grammatik
- BNF (Backus-Normalform) - eine kontextfreie Definition einer (Programmier)Sprache
Es müssen kontextsensitive Nebenbedingungen eingeführt werden
Wichtig ist die Unterscheidung zwischen "Objektsprache" (zu definierende Sprache)
und der "Metasprache" (zur Definition benutzte Sprache). Dazu gehören Objektzeichen
/ Terminalsymbol und Metazeichen/ Nonterminalsymbole - diese dürfen nur in
einer Sprache auftauchen. Kontextfreie Grammatik wie die BNF bestehen aus :
N : Alphabet der Nonterminalsymbole
Summenzeichen : Alphabet der Terminalsymbole (keine Schnittmenge mit N)
P : Menge von Produktionen oder Regeln
S : S aus N ist Startsymbol
Definitionszeichen : "::=="
Alternativzeichen : "|"
Nonterminalklammern : "[]" - Lie-Klammern(linke Seite)
- EBNF (extended BNF)
Definitionszeichen : "="
Alternativzeichen : "|"
Nonterminalzeichen : Anführungszeichen
Wiederholungsklammern : "{}"
Optionsklammern : "[]"
Gruppenklammern : "()"
Punk : . ,
- Syntaxdiagramme
- lassen sich leicht aus EBNF erstellen
- Terminalsymbole : Runde Kästchen z.B. "true"
- Nonterminalsymbole : eckige Kästchen "Bezeichner"
- Linien und Pfeile zur Verbindung der Kästchen
Linien können Kästchen verbinden oder um sie herum führen
- Jedes Kästchen besitzt genau zwei Verbindungen (im Regelfall gegenüber)
- Es gibt genau eine Linie am Anfang (Eingang)
- Es gibt genau eine Linie die aus dem Diagramm herausführt (Ausgang)
- Linien dürfen sich nicht kreuzen
- Jedes Syntaxdiagramm hat einen eindeutigen Namen
Identifikatoren/ Bezeichner bestehen aus einem Buchstaben und
einer evtl. lehren Zeichenkette aus Buchstaben und Zahlen.
Zuweisungen/ Wertzuweisungen : x:=term Die leere Anweisung wird
mit nop (no operation) abgekürzt. Die Anweisung, die einen Term in
einen nicht definierten Wert verwandelt heißt abort. Zusammensetzungen
ist eine besondere Form der Zuweisung (Komposition)
Bedingte Anweisungen : IF [Boolscher Term] THEN Expr1 ELSE Expr2 ENDIF/ FI
Diese Anweisungen können auch in einander verschachtelt werden.
Wiederholte Anweisungen (Schleifen) :
WHILE [Boolscher Term] DO Expr ENDWHILE/ OD
REPEAT Expr UNTIL [Boolscher Term]
FOR Bezeichner = Anfang TO Ende DO Expr OD
While und For Schleifen sind Pre-check-Loops (erst Bedingung prüfen und
dann ausführen, während die Repeat Schleife ein Post-check-Loop ist
hier wird erst die Anweisung ausgeführt, bevor überprüft wird, ob diese
erneut auszuführen ist.
Prozeduren : PROC Name (Parameter mit zugehöriger Sorte)
Prozeduren sind Abbildungen gewisser Parameter in einen Wertebereich.
"Call-by-Value" : Parameterübergabe, bei der nichts an den übergebenen
Parametern verändert wird. Die Proc. verändert nur
nur eine Kopie der Parameter.
"Call-by-Referenz" : Parameterübergabe, bei der die übergebenen
Werte referenziert verändert werden.
Auch hier wird eine Kopie angelegt, die aber
im Gegensatz und Call-by-Value direkt mit den
übergebenen Parametern referenziert ist.
Funktionen : FCT Name(Parameter mit zugehöriger Sorte) Sorte von Name
Funktionen sind Prozeduren, denen dessen Name ein Rückgabewert
zugeordnet werden kann.
Zu MINI-PASCAL (Klaeren Seite 111) :
- echte Teilmenge von PASCAL
- Komponenten : - "programm" gefolgt von einem Ident(ifier)
+ block bestehend aus
[ConstDecl] [VarDecl] {ProcDecl}
"begin" statement {statement} "end."
- ConstDecl bestehend aus
"const" Ident "=" Nummer (nicht weiter beschrieben)
{"const" Ident "=" Nummer} ";"
- VarDecl bestehend aus
"var" Ident {,Ident} ": Integer (nur Int in Mini)
- ProcDecl bestehend aus
"procedure " Ident ";" block ";"
- statement bestehend aus
[VarIdent ":=" expression | ProcIdent |
"begin" statement {statement} "end;" |
"if" condition "then" statement ";" |
"while" condition "do" statement ";" ]
- condition bestehend aus
expression
("=" | "<>" | "<" | "" | "<=" | "=")
expression
- expression bestehend aus
["+" | "-"] term {("+" | "-" term)}
- term bestehend aus
factor {("*" | "div") factor}
- factor bestehend aus
ConstIdent | VarIdent | Nummer | "(" expression ")"
- ConstIdent, ProcIdent, VarIdent bestehend aus
Ident
- Schlüsselwörter (program, if, then, do, while, end, const etc.)
dürfen nicht als Ident benutzt werden.
- in Mini Pascal gibt es nur parameterlose Prozeduren
= nur globale Variablen
- Semikolon als Trennzeichen
- leere Anweisungen werden akzeptiert = überflüssige Semikolons
werden dadurch ignoriert. Das kann auch zu Problemen führen
wie z.B. bei while sonstwas do;
- Variablen können überlagert werden
Somit hat jede Variable ihren eigenen Sichtbereich, Lebensdauer
= Speicherplatz wird frei, sobald eine Variable nicht mehr gebraucht
wird. Bei rekursiven Aufrufen, werden natürlich dem entsprechend
viele Kopien angelegt wie die Anzahl der Aufrufe
Semantik von Programmiersprachen am Beispiel MINI-PASCAL
(Klaeren Seite 118 und Broy Seite 85) :
Unterscheidung in Funktionale Semantik (man beschreibt die Funktion
des Programmes durch Festlegung von Ein- und Ausgabeverhalten)
und der Operationalen Semantik bei der die einzelnen Rechenschritte
beschrieben werden.
- Adr : Adressen aus den natürlichen Zahlen
- Int : Menge der ganzen Zahlen
- Bool : Wahrheitswerte : {W,F}
- Int : Namen/ Bezeichner
- VEnv : partielle Abbildung [Ide = Adr] Variablenabbildung
- Store : partielle Abbildung [Adr = Int] Speicherzustände
- CEnv : partielle Abbildung [Ide = Int] Constantenumgebung
- Stat : partielle Abbildung [CEnv X VEnv X PEnv X Store = Store]
- PEnv : partielle Abbildungen [Ide = [Store = Store]]
Semantische Funktionen sind der folgenden Gestalt : F[a]b
F ist der Name der Funktion, a ein Programmstück und b weitere Argumente.
Üblicherweise klammerlose Präfixschreibweise z.B. : block für F(block)
Dazugehörige Funktionen :
- C : ConstDecl X CEnv = CEnv
- V : VarDecl X VEnv = VEnv
- P : Prog X CEnv X VEnv X PEnv = PEnv
- E : Expression X CEnv X VEnv X Store = Int
- R : Condition X CEnv X VEnv X Store = Bool
- S : Statement = Stat
- B : Block = Stat
- PRO : Program = [Int^n =Int]
Bäume, Binärbäume, Suchbäume, binäre Suchbäume (Klaeren Seite 197) :
- Baumstrukturen sind Darstellungsformen von abstrakten Datentypen
oder Termen
- KNOTEN : Eine Komponente eines Baumes
- GEORDNETER BAUM : wenn die direkten Nachfolger eines Knotens in
einer bestimmten Reihenfolge stehen
- BINÄRBAUM : Maximale Anzahl der Nachfolger (Söhne) ist 2
- BLÄTTER : Knoten ohne Nachfolger
- INNERE KNOTEN : Knoten, die keine Blätter sind
- SOHN : Nachfolger
- VATER : Vorgänger
- BRUDER : haben den gleichen Vater
- GRAD : maximale Anzahl der Nachfolger
- RECHENBAUM : Darstellung von arithmetischen und logischen Termen
- ENTARTETER BAUM : z.B. Kamm oder verkettete Liste
- Darstellungsformen : Graph, Klammerstruktur, Kreisdiagramm und
Einrückstruktur
Information/ Repräsentation (Broy Anfang) :
Informationen können durch unterschiedliche Repräsentationen dargestellt
werden. (0.9999 = 1 = I =...). Aufgabe der Informatik ist es geeignete
Repräsentationen für Informationen zu finden und somit auf ein
geeignetes Level für Problemlösungen mit Hilfe von Maschinen zu
ermöglichen.
Boolsche Terme (Broy Seite 9) :
Zusammenhang zwischen Ausdrücken, die entweder wahr oder falsch ergeben.
wahr, true, L, 1 ...
falsch, false, O, 0 ...
- true und false werden als Konstante bezeichnet
- Abhängigkeit vom Bezugssystem (reale Welt oder Modell)
- Identifikatoren sind Platzhalter für Aussagen (freie Bezeichner)
- elementare Aussage : keine Identifikatoren
= wahr oder falsch im Bezugssystem
einfachste elementare Aussagen sind true und false
die Verknüpfung elementarer Aussagen ist wieder elementar
- atomare Aussage : nicht zusammengesetzt
- Jede Verknüpfung elementarer oder atomarer Aussagen sind
genau wie die Aussagen selbst Boolsche Terme
Boolsche logische Operatoren in der Prioritäten-Reihenfolge :
1. nicht (einstelliger Operator : Negation - not)
2. und (zweistellig : Konjunktion - and)
3. oder (zweistellig : Disjunktion - or)
(in der Regel nicht exklusives sondern alternatives oder)
4. = implizert (zweistellig : Implikation - impl)
5. <= äquivalent (zweistellig : Äquivalenz - equiv)
Diese Prioritäten machen das Setzten von Klammern erforderlich
bzw. überflüssig. Semantisch äquivalente Terme können nach den
folgenden Regeln ersetzt werden :
Involutionsgesetz : nicht nicht x = x
Kommutativgesetz : x und y = y und x
x oder y = y oder x
oziativgesetz : (x und y) und z = x und (y und z)
(x oder y) oder z = x oder (y oder z)
Idempotenzgesetz : x und x = x
x oder x = x
Absorptionsgesetz : x und (x oder y) = x
x oder (x und y) = x
Distributivgesetz : x und (y oder z) = (x und y) oder (x und z)
x oder (y und z) = (x oder y) und (x oder z)
de Morgan : nicht (x und y) = nicht x oder nicht y
nicht (x oder y) = nicht x und nicht y
Neutralitätsgesetz : x oder (y und nicht y) = x
x und (y oder nicht y) = x
Die Gesetze der Boolschen Algebra sind verträglich mit der Interpretation.
Abbildungen zwischen Wahrheitswerten lassen sich leicht in einer
Wertetafel darstellen. Identifikatoren sind abhängig von einer
Belegung b: ID=Bool, so ist Ib(true)=true (unabhängig von der
Belegung) und Ib(nicht t) = not(Ib(t)) für x aus ID (abhängig).
Weiterhin gelten die folgenden Äquivalenzrelationen
für t, t1, t2 aus der Menge der Boolschen Terme (das Gleichheitszeichen
steht für semantisch äquivalent ) :
- Reflexivität : t = t
- Symetrie : t1 = t2 = t2 = t1
- Transitivität : t1 = t2 und t2 = t3 = t1 = t3
Ein wichtiges Hilfsmittel ist die Substitution von Boolschen Termen.
Sie stellt eine Abbildung zwischen Boolschen Termen dar. Hier findet auch
die Boolsche Algebra eine Anwendung.
t1[t2/x] bedeutet : ersetze im Term t1 alle x durch t2
t[t1/x1, t2/x2,..., tn/xn] dem entsprechend Ersetzungen in t
- gibt es in t1 kein x, so bleibt t1 invariant
- ist t1=x so ist t1[t2/x] = x[t2/x] = t2
Sortieralgorithmen (Broy Seite 33) Beispiel Kartenspiel :
1. Vorsortieren und Zusammenmischen
(1) ist x leer oder einelementig so ist x der sortierte Stapel - exit
(2) Aufspalten in zwei Stapel und Sortieren durch Mischen
danach die beiden sortierten Stapel durch Mischen
2. Einsortieren
(1) ist x leer so ist y der sortierte Hilfsstapel - exit
(2) wähle eine Karte aus x und sortiere sie in y ein. Danach
den Alg. mit dem um eins verkleinerten Stapel erneut aufrufen.
3. Auswählen
(1) ist x leer so ist y der sortierte Hilfsstapel - exit
(2) größte Karte aus x an y anhängen und Alg. erneut aufrufen.
4. Vertauschen
(1) Enthält x zwei Karten in der falschen Reihenfolge vertausche
sie und starte den Alg. erneut
(2) Gibt kein solches Paar : exit
Textersetzungsalgorithmen (Broy Seite 34) :
Ersetzungssystem auf Zeichenreihen zur Substitution von Teilworten
Wird ein Term s in den term t durch die Vorschrift v=w überführt,
so gilt s[t/s, v/w]
- terminal : falls die Textersetzungsregel nach endlich vielen
Ersetzungen nicht mehr anzuwenden ist
- Berechnungssequenz : gibt die einzelnen Schritte der Ersetzung an
es entsteht eine Folge von Termen :
t1=t2=...=tn
t1 heißt Eingabe, t2 heißt Resultat
- terminierend : wenn tn terminal, heißt die Berechnung terminierend
mit dem Resultat tn
- deterministisch wird ein Textersetzungsalg. erst dann, wenn man
durch die Reihenfolge des Aufschreibens Prioritäten für die
Ersetzungen festlegt. Nach A.A. Makrov sind die folgenden Regeln
einzuhalten, damit ein Alg. deterministisch ist :
- bei mehreren anwendbaren Regeln, nimm die oberste
- bei mehreren möglichen Stellen, nimm die am weitesten links
Textersetzungsalgorithmen lassen sich für Ersetzungen nach der
Boolschen Algebra einsetzen.
Rechenstrukturen (Broy Seite 45) :
Rechenstrukturen entspricht eine Algebra in der Mathematik und werden
mit einem großen A abgekürzt.
bestehen aus : - Familie von Daten/ Trägermengen/ Sorten (s aus S)
- Familie von Abbildungen/ Funktionssymbole (f aus F)
Ausprägungen/ Erscheinungsformen sind z.B. Taschenrechner, Rechenanlagen
Es muß das spezielle Element "Bottom" eingeführt werden für das n.d.
Ergebnis einer Funktion. Eine Abbildung wird strikt genannt, wenn gilt :
Sobald ein Argument der Funktion Bottom ist, so ist auch das Resultat Bottom
Beispiele für Rechenstrukturen sind :
- BOOL : S={bool}
F={true, false, nicht, oder, und}
- NAT : S={bool, nat}
F={true, false..., zero, succ, pred, add, mult, sub, div, <=, =?}
- SEQ : S={bool, nat, m, seq m}
F={..., ..., empty, make, conc, first, rest, last, lrest}
seq m ist eine polymorphe Sorte; es ist möglich...
seq bool, seq nat, seq seq nat... zu bilden.
- CALC : S={Taste, Zustand}
Taste ={0,.., 9, +, *, =}
Zustand = {(s, p, d)} + Fehler
s aus W={0, ... 10^10-1}
p aus {+,*,=}
d aus W={0, ... 10^10-1}
F={ein, tip,0,1...,9,+,*,=}
Bemerkung : =? ist eine strikte Abbildung zugeordnet, nicht wie bei =
d.h. sobald bei x =? y x oder y = Bottom sind ist
x =? y = Bottom.
Signaturen und Interpretationen (Broy Seite 51) :
Erfassen lediglich die Funktionssymbole einer Rechenstruktur und nicht
ihren genau Bedeutung. Eine Signatur wird mit dem Summenzeichen und besteht
aus einem 2-Tupel (S,F). S ist die Menge der Sorten und F die Menge
der Funktionssymbole. Jedes f aus F hat eine eigene Funktionalität fct,
die Aussagen über die Art der Abbildung liefert. So ist fct(true) aus bool
eine 0-stelligige Abbildung von bool. Außerdem ist
fct(und) =(bool)(bool) bool , da es sich um eine Abbildung von
bool X bool nach bool handelt. Diese Funktionalitäten ergeben eine Signatur,
die sich leicht in einem Signaturdiagramm darstellen lassen Beispiel S.52 :
- Die Trägermengen S werden hierbei jeweils in eine Elipse geschrieben
- Gibt es Beziehungen zwischen diesen, so werden sie mit entsprechender
Anzahl der Eingaben bzw. Ausgaben miteinander verbunden.
Am Schnittpunkt der Linien befindet sich ein Knoten, neben den
die entsprechenden Funktionssymbole eingetragen werden
- Bezieht sich die Funktion nur auf eine Sorte, so führen n (entsprechend
der Anzahl der Eingaben) Kanten aus dem Sortenknoten heraus,
treffen sich in einem Punkt, neben dem die entsprechenden Funktionalitäten
stehen und es führt eine Kante in den entsprechenden Ausgabesorten-
knoten zurück.
- Manche Funktionen benötigen keine Eingabe, bei diesen führt jeweils
nur eine Kante in die dazugehörige Sorte.
0-stellige Funktionen wie z.B. succ werden als Grundterme bezeichnet.
Signaturdiagramme sind keineswegs eindeutig, sondern sie können für
verschieden Signaturen identisch aussehen.
Interpretationen I haben folgende Gestalt : I^A[Grundterm]
Hier wird durch eine Interpretation auf einer Trägermenge ein
entsprechender Grundterm ausgewertet. So ist :
I^NAT(pred(zero)) = Bottom ABER I^INT(pred(zero)) = -1
Grundterme lassen sich leicht in einer Baumstruktur darstellen.
Dieser Baum wird dass als Formular bezeichnet, da man in einem
leeren Formular lediglich die entsprechenden Werte eintragen muß,
und durch die gegebene Baumstruktur leicht das Ergebnis errechnen kann.
Formulare werden im Zusammenhang zur Interpretation benutzt.
Will man die Interpretation eines Termes von einer Belegung und
einer Trägermenge angeben, so schreibt man : I^A unten B (t)
Natürlich kann man auch Formulare von der Belegung abhängig erzeugen,
indem man die Felder mit freien Identifikatoren leer läßt.
Diese Formulare heißen dann Berechnungsschema, da lediglich die
Methode abhängig von einer Konkreten Belegung grafisch dargestellt ist.
Formulare und Rechenschemata können auch gegen die Baumstruktur
verstoßen. So kann ein Knoten zwei Väter haben. Diese bezeichnen wir
mit "Hasse-Diagramm"
Begriffe :
1. Datentyp : Trägermenge + Funktionen/ Operationen auf dieser.
Im Def-Bereich und im Wertebereich treten die Elemente der Trägermenge auf.
D=[M, f1,f2,...,fn]
2. Trägermenge : z.B. INT X INT X BOOL oder INT^2 X BOOL
3. Funktionen/ Operationen : +,-,*,/ usw.
4. Darstellungsformen : - (Polnische Notation)
- geklammerte Präfixnotation F(x,y) (Mathe)
- klammerfreie Präfixnotation F x y (bei +,*, und,..)
- Infixnotation x F y
- geklammerte Postfixnotation (x y) F
- klammerfreie Postfixnotation x y F (z.B. x!)
- Mixfix (z.B. x x<y<z)
- Bäume (siehe Bäume)
- (Signatur)Diagramme
- Formulare (Bäume für Grundterme)
verschiedene Darstellungsformen machen das Setzen von Klammern
erforderlich bzw. überflüssig. Das gilt natürlich auch für
die Einführung von Prioritätsregeln (Punkt vor Strich).
5. Terminieren : Abbruchkriterium ist immer erfüllt
= Programm/ Alg. terminiert
6. Compiler : Übersetzungsprogramm, das ein Programm einer bestimmten
Programmiersprache in Maschinensprache übersetzt.
7. Interpreter : Interpretationsprogramn, das ein Programm einer
bestimmten Programmiersprache unmittelbar ausführt
8. Rekursion : a) linear : in jedem Fall der Fallunterscheidung wird
die Funktion/ Prozedur jeweils höchstens einmal
aufgerufen.
b) repetitive : falls in jedem Zweig der Fallunterscheidung
die Rekursion als letzte Anweisung auftaucht
c) kaskadenartig : falls in mindestens einem Zweig der
der Fallunterscheidung mindestens zwei
rekursive Aufrufe erfolgen. P(x-1)*P(x+1)
d) vernestet : falls weitere Aufrufe im Rumpf auftreten
|