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