|
Informatik I Zusammenfassung 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) |
