- Ziel der Vorlesung: breiter Überblick
- Informatik als Wissenschaft: Gliederung
- Überblick über Programmiersprachen
- Beispiel für Objekte und Klassen :
- Ausgabefläche, potentiell unendlich (aus Bibliothek )
- Attribut : Schreibposition
- Methoden : Writeln, WriteString(s: String)
- Zugriff über Bibliotheksmodul InOut
- Ausblick auf OOP: Vererbung
- Hausaufgabe: Kapitel "Rechner" selbst durchlesen
- Algorithmus: informell
- erstes Programmbeispiel in MODULA: "Hello, World"
- Information und Nachricht ; Interpretation
- äquivalente Repräsentationen; Codierungen
- Sprache : Syntax und Semantik
- Pragmatik : soziale Übereinkunft
- Abstraktion : Unwesentliches weglassen
- ein wenig naive Mengenlehre
- endliche Mengen, Grundoperationen
- unendliche Mengen: Beispiel natürliche Zahlen
- kartesisches Produkt: assoziativ
- Rechenstruktur = "Algebra"
- Einschub: was ist eine Definition :
- Sprachregelung mit Gültigkeitsbereich
- (dummes) Beispiel: "Quabbel"
- Halbgruppe, Monoid
- Zeichenvorrat = Alphabet (synonym, hier ohne Anordnung)
- Wörter , Wortmengen, freies Monoid , leeres Wort
- formale Sprache = Wörtermenge (abzählbar)
- Problem: endliche Beschreibung für unendliche Menge gesucht
- Aufzählbarkeit, Entscheidbarkeit
- Chomsky-Grammatiken , Sprachklassen
- Klassen 2 und 3: deute NT als Wortmenge
- Chomsky-Grammatiken als Erzeugungsverfahren, Ableitung
- Determinismus, Nichtdeterminismus
- Entscheidungsverfahren: rate und verifiziere Ableitung
- Funktion als statische Zuordnung zwischen Mengen
- Definitionsbereich, Wertevorrat
- totale und partielle Funktionen
- Mengen von Funktionen: M --> N
-
- formale Parameter, Bindung , lokale Umbenennung
- weitere Bindungsbeispiele:
- Funktionen höherer Ordnung: Ableitung, Stammfunktion
- Funktionen mehrerer Veränderlicher
- Beispiel Landkarte
- Beispiel Höhenprofil: "Currying"
- Funktionen auf Zeichenketten: Länge ist Homomorphismus
- endlicher Automat am Beispiel Zigarettenautomat
- Übergangsdiagramm und Übergangstafel
- Ausgabe: hier nur kursorisch
- Sprache der zulässigen Eingaben : regulär
- Grammatik aus Tafel ablesbar und umgekehrt (Beispiel)
- Übergangsdiagramm , akzeptierte Wörter
- duale Darstellung: vergiß Zustände, markiere Pfeile
- Syntaxdiagramm , beschreibt Wortmenge; vorerst nichtrekursiv
- rekursives Einsetzen: --> Chomsky 2
- Abarbeitung: Stapel von Kopien --> Stack-Prinzip
- Kellerautomat
- Turing-Maschine : einfach und allgemein; ineffizient
- Marsfahrzeug "Pathfinder" als Modell für Turingmaschine
- formale Definition der TM
- Algorithmus , Definition
- Algorithmus realisieren durch geeignete Maschine
- Beispiel: Subtraktion in Strichdarstellung
- Übergangsfunktion : hier als Matrix geschrieben (Currying)
- weitere Beispiele
- Universalität (behauptet), Church -sche These
- es gibt nicht berechenbare Funktionen!
- Halteproblem, Äquivalenzproblem: allgemein unentscheidbar!
- Übersetzen von Programmiersprachen:
bedeutungsgleich !
- Analysephase : lexikalisch, syntaktisch, semantisch
- Einstieg in MODULA 2: lexikalische Ebene
- Scanner: reguläre Ausdrücke , Syntaxdiagramme, endl. Automat
- MODULA: Bezeichner, Zahlen, Zeichenketten
- geschachtelte Kommentare: endlicher Automat genügt nicht!
- Kellerautomat ; hier: Zähler reicht aus
- Programmieren = Problemlösen
- Problem erkennen, analysieren
- Lösungsweg suchen, formulieren, realisieren
- Lösung berechnen
- Problemlöse-Strategien
- einfache, kleine Probleme: direkt lösen
- strukturierte Probleme: zerlegen, Lösungen zusammensetzen
- Rekursion : Teilproblem ist Instanz der gleichen Problemklasse,
- aber in wohldefiniertem Sinne kleiner : Terminierung ist klar!
- Problemlöse-Strategien
- einfache, kleine Probleme: direkt lösen
- strukturierte Probleme: zerlegen, Lösungen zusammensetzen
- Frage: Testaufwand versus Programmlänge? bestenfalls linear
- Regel: keine zu frühe Festlegung von Einzelheiten!
- Strukturierung sequentieller Programme
- Struktogramme, einfache Ablaufstrukturen
- Sequenz, Alternative, Mehrfachauswahl, Iteration
- Vorschlag für bessere Notation (privat)
- benötigt werden: Ausdrücke und Bedingungen
- MODULA: oberste Ebene
- "module", "import", "block"
- Kontextbedingungen
- einfaches Beispiel für komplettes Programm (2.1 aus L & A)
- Datentyp : Menge von Werten mit definierten Operationen
- andere Sprechweise: Klasse :
- Objekte (Instanzen) mit Attributen und Methoden
- MODULA: Datentyp INTEGER mit definierten Operationen
- MODULA: Datentyp BOOLEAN mit definierten Operationen
- maschineninterne Datentypen: BIT, WORD
- technische Grundoperationen
- Festpunktarithmetik: ohne Vorzeichen
- Übertrag bei ADD, doppelt langes Resultat bei MUL
- Festpunkt-Division: 2 Resultate, DIV und MOD in MODULA
- MODULA: Datentyp CARDINAL
- negative Festpunktzahlen: Einerkomplement und Zweierkomplement
- Ausblick auf Langzahl-Arithmetik
- MODULA: benannte Konstanten, Gültigkeitsbereich!
- MODULA: arithmetische Ausdrücke
- MODULA: Fallunterscheidung mit "case"
- MODULA: Relationen
- MODULA: Fallunterscheidung mit "if", "then", "else", "elsif"
- Struktogramme
- Funktionen :
statischer Zusammenhang vs. Algorithmus
- berechenbar : Algorithmus existiert (muß nicht sein!)
- MODULA: Syntax Funktionsdeklaration
- MODULA: Syntax Funktionsaufruf
- Beispiel: Stellenwertdarstellung natürlicher Zahlen
- Zifferndarstellung zur Basis 16: HexDigit(n: cardinal): char
- Vorbedingung : 0 <= n < 16
- Nachbedingung : RESULT in {'0'..'9', 'A'..'F'}
- definieren die Korrektheit ; nicht notwendig abgeprüft!
- Kontrakt zwischen Anbieter und Aufrufer
- Beispiel: bestimme die notwendige Stellenzahl
- rekursiver Ansatz: Teilproblem ist kleiner!
- Überlegung zur Korrektheit:
- benutze den Satz: "jede nichtleere Menge natürlicher Zahlen hat ein kleinstes Element"
- zeige, daß kein "kleinster Verbrecher" existiert, sonst gäbe es einen noch echt kleineren
- das ist ein versteckter Induktionsbeweis !
- das Beweisschema gilt für alle rekursiven Programme!
- man muß nur jeweils eine geeignete Problemgröße definieren
- Beispiel: Ausgabe einer Hexzahl in ein Feld gegebener Breite,
führende Blanks
- 2 rekursive Aufrufe; nur einer mit Zählschleife (ad hoc)
- Einpacken in Bibliotheksmodul: Schnittstellenbeschreibung
- Implementierung kommt erst später.
- Modul-Mechanismus in MODULA: (mit Versions-Überprüfung)
- "definition module", "implementation module",
- Hauptprogramm zur Hex-Umrechnung
- Variablen für Eingabewerte; ReadCard(x)
- statische Variablen im Hauptprogramm
- lokale Variablen in Prozedur
- Wertzuweisung
- Inkarnationen , Laufzeitorganisation, Aktivierungsblöcke
- Gültigkeitsbereich und Lebensdauer
- Referenzparameter
- Beispiel: ggt(p, q) rekursiv
- suche kleinste Linearkombination
- Terminierung?
- Regel: bei rekursiven Prozeduren niemals den Aufrufbaum betrachten, sondern inneres Exemplar als black box !
- Problemgröße jeweils geeignet definieren (natürliche Zahl!)
- hier Problemgröße: max(p, q)
- End-Rekursion entfernen (nicht Prüfungsstoff! )
- Idee: Aktivierungsblock wiederverwenden
- Wertparameter als lokale Hilfsgrößen
- loop- Konstrukt, exit
- einige Mechanismen zur Erzeugung neuer Typen:
- Aufzählungen
- Boolean als Aufzählungstyp
- Unterbereiche
- skalare Typen allgemein
- Schleife über skalaren Typ
- Mengentypen
- Beispiel: Türme von Hanoi
- Modellierung durch rekursive Datenstruktur
- Modellierung durch Attributierte Grammatik
- Algorithmus analog zur Datenstruktur
- Beispiel für Aufzählung und Bereichstyp
- Gültigkeitsbereiche
- Mechanismen zur Notation von Syntaxregeln: bisher bekannt:
- Chomsky-Grammatiken
- Syntaxdiagramme (einfach und auch rekursiv)
- zusätzlich:
- BNF (ALGOL 60)
- EBNF : Beziehung zu Syntaxdiagrammen; reguläre Ausdrücke
- Aufwandsabschätzung für Türme von Hanoi
- Exkurs über Differenzengleichungen
- O(f(n)) -Notation (informell)
- Beispiel: Fibonacci-Zahlen
- rekursiver Ansatz:
- Aufwand: exponentiell; abschätzen
- (exakte Lösung unübersichtlich)
- Beispiel: Fibonacci-Zahlen (später in vielen Versionen!)
- Fibonacci : Definitionsmodul , exportiert MaxArg = 24
- Zusicherungen in der Schnittstelle
- Arten von Moduln (oder Kapseln ):
- Funktionsmodul (keine internen Objekte außer Konstanten)
- Datenmodul: abstraktes Objekt (interner Status)
- Typenmodul: Menge von abstrakten Objekten gleichen Typs
- Implementierungsmodul , rekursiv
- bessere Lösung: dynamic programming (Terminus erklären)
- Prinzip: berechne alle benötigten Teilprobleme in einer geeigneten Reihenfolge, jedes nur einmal;
- hier gibt es für die zulässigen Eingabewerte nur endlich viele jemals benötigte Teilprobleme: vorweg berechnen und merken
- MODULA: "while"-Schleife
- Fibonacci : berechne Werte von unten nach oben, mit Umspeichern
- MODULA: weitere Schleifenkonstrukte: "repeat", "loop", "exit"
- Struktogrammdarstellung
- ablegen in Tabelle : Array-Konzept
- Regel: Grenzen bei Indizierung immer prüfen, falls man die Einhaltung nicht statisch zeigen kann!
- MODULA: "array"-Syntax
- Beispiele für Array: Verkehrsampel, Dreiervektoren
- Fibonacci : Ablage der Werte in Tabelle,
vorbesetzen bei der
Initialisierung des Moduls;
bei Funktionsaufruf nachsehen: O(1)
- Fibonacci : berechne Werte von unten nach oben, mit Hilfsfeld
- Frage: woher kommt der Effizienzgewinn der iterativen Lösung?
Die Erklärung im Buch (Verwendung von Variablen)
stimmt nicht!
- Idee: benachbarte Werte zusammenfassen
- Konzept: abstrakter Datentyp :
- Menge von Werten
- Satz von Operationen
- Regeln über das Verhalten
- Realisierung braucht nicht bekannt zu sein!
- Beispiel: ADT Zahlenpaar ;
Operationen: Comb, First, Second
- Term-Algebra ist treues Modell
- Fibonacci : Annahme: Wert vom Typ Paar kann Funktionsresultat sein (stimmt leider nicht in MODULA!)
- Rekursionsgleichung für benachbarte Paare ist einstufig
- rekursive Lösung hat linearen Aufwand!
- Problem: Typ Paar soll Ergebnistyp sein; geht hier nicht
- Problem: Typ Paar soll Ergebnistyp sein; geht hier nicht
- Ausweg in MODULA: Resultate als var-Parameter ;
Hilfsvariablen nötig, Eleganz der funktionalen
Schreibweise geht verloren
- intern wird das ohnehin so gemacht, aber dafür sind eigentlich Compiler da!
- es ist immer noch derselbe Algorithmus, daher der lineare Aufwand!
- mehrdimensionale Arrays
- Matrix als Array von Zeilen;
- Notation für Mehrfach-Indizierung
- Prozedurtypen in MODULA
- Beispiel: numerische Integration, Rechteckregel, Trapezregel
- Komplexe Datentypen in MODULA:
- Sets , BITSET, INCL, EXCL
- Arrays (schon teilweise besprochen)
- Verwendung von Zeichenreihenkonstanten
- offene Array-Parameter
- Komplexe Datentypen in MODULA:
- Records , Selektoren
- "with"-Statement
- Varianten
- Gültigkeitsbereiche bei Records
- Datentypen, Verbunde für Datum und Personendaten
- Vergleichsoperationen für Datum und Namen
- Resultattyp: VglTyp = (kl, gl, gr)
- lexikographischer Vergleich von Strings
- Dynamische Speicherverwaltung
- Zeigertypen frei eingeführt
- Halde : ALLOCATE, DEALLOCATE, NEW, DISPOSE
- Hinweis: Zeiger sind keine festen Adressen ! Arithmetik unzulässig, nur Zuweisung, Vergleich und Dereferenzierung sind definiert
- Begriff Garbage-Collection (keine Algorithmen)
- ADT Liste
- funktionale Spezifikation
- Term-Algebra als Modell
- Definitionsmodul
- opaker Typ ; motiviert mit festem Platzbedarf
- Listen-Realisierung als Geflecht , rekursiv
- Listen-Realisierung als Geflecht , rekursiv
- kopierende Realisierung, flache und tiefe Kopie
- iterative Realisierung, Schleppzeigertechnik
- Kopieren mit Reißverschlußtechnik
- Grundoperationen mit linearen Listen
- welche Operationen mit verketteten Listen gehen mit O(1) ?
- eigene Freilistenverwaltung
- Standard-Typschema Stack (generisch!)
- funktionale Spezifikation
- Term-Algebra als Modell
- Realisierung als verkettete Liste , funktional
- dasselbe prozedural mit Durchgangsparameter
- Standard-Typschema Schlange (generisch!)
- funktionale Spezifikation
- Term-Algebra als Modell
- Realisierung als Geflecht, prozedural
- verkette Realisierung mit Kopfblock
- verkette Realisierung als Ringliste
- Sonderfall leere Schlange
- Sonderfall einelementige Schlange
- Schlange endlicher Maximallänge
- Realisierung als Ringliste im Array
- mod versus explizite Ende-Abfrage
- Standard-Typschema Binärbaum (generisch!)
- funktionale Spezifikation
- Term-Algebra als Modell
- Realisierung als Geflecht
- Durchwanderung : prefix, infix, postfix
- Beispiele: Strukturbaum einer Formel
- prefix gibt Funktions-Termdarstellung
- infix gibt Infix-Notation
- postfix gibt Operationenfolge für UPN-Rechner
- Darstellung allgemeiner Bäume und Wälder
- äquivalenter Binärbaum , Durchwanderungen analog
- Standard-Typschema Suchbaum (generisch!)
- Infix-Durchwanderung gibt sortierte Folge
- Entartungsfall : Balancierung nötig; keine Algorithmen
- Realisierung als Geflecht
- Eintragen , rekursiv
- Suchen , rekursiv
- Suchen in allgemeinen Datenstrukturen
(Zustandsmodell)
- rekursiver Ansatz
- iterativer Ansatz
- Binäres Suchen im Suchbaum
- Binäres Suchen in Tabelle
- Aushängen aus einem Suchbaum
- Grundidee der Streuspeicherverfahren (Hashing)
- Gerichtete Graphen ; Darstellungen:
- Liste von Knoten und Kanten
- Adjazenzmatrix
- Liste der Vorgänger bzw. Nachfolger je Knoten
- binäre Relationen als gerichtete Graphen
- ungerichtete Graphen als Sonderfall
- Labyrinth-Algorithmus (als Anekdote)