- Vorstellung der Fachschaft
- Vorstellung der Dozenten: Klaus Lagally, Walter Reuß, Eberhard Teufel
- Vorstellung des Mentorenprogramms
- Einführung: Organisatorisches;
- Ziel der Vorlesung: breiter Überblick, Einstieg in Vertiefung
- Informatik als Wissenschaft: Gliederung
- Theoretische Informatik
- Praktische Informatik
- Technische Informatik
- Angewandte Informatik
- methodische Bemerkungen
- weshalb Theorie? den Dingen auf den Grund gehen: "Durchblick"
- was ist Abstraktion? Unwesentliches weglassen
- was ist eine Definition: Sprachregelung mit Gültigkeitsbereich
- kurzer Überblick über Programmiersprachen
- Objektbasierung: Objekte und Klassen
- Beispiel: unser Drucker
- Ausblick auf Objektorientierung: Vererbung
- Beispiel: Drucker als Gerät
- Objekt Ausgabefläche,
potentiell unendlich
- Attribute: aktueller Inhalt, Schreibposition
- Methoden: Writeln, WriteString(s: String)
- Zugriff über Bibliotheksmodul InOut
- erstes Programmbeispiel in MODULA: "Hello, World"
- etwas naive Mengenlehre
- endliche Mengen, Grundoperationen
- unendliche Mengen: Beispiel natürliche Zahlen
- Mengenalgebra als Rechenstruktur
- Alphabete und Bezeichner; Griechisches Alphabet
- Zahlenmengen als Klassen
- Grundtypen CARDINAL, INTEGER, BOOLEAN
- Grundtypen REAL, CHAR
- Rechenausdrücke: wie gewohnt, aber:
- nur runde Klammern
- Zahlen und Bezeichner als Operanden, daher: Multiplikation explizit
- auch logische Ausdrücke
- wohlgeformte Ausdrücke; Kalküle
- Codierungen: BCD, EBCDIC, ASCII, ISO 8859, UNICODE, UTF/8
- Zeichenketten in Modula 2
- Eingabe in Modula: Read, ReadInt, ReadCard
- Speicher für Eingabewerte: (statische, einfache) Variablen
- Programmieren als systematisches Problemlösen
- Beschreibungsebenen, hierarchische Zerlegung
- Imperative (prozedurale) Programmierung:
Aktionen
- Strukturierte Programmierung, Struktogramme
- Kontrollstrukturen: Sequenzen, Alternativen, Schleifen
- Grundbestandteile: leere Aktion, Zuweisung, Aufruf Prozedur
- Black Box: Kontrakt
- Beispiel: Faktorzerlegung
- Problemlösestrategien,
divide et impera
- Modularisierung: Definitionsmodul, Implementierungsmodul
- Rekursion
- Beispiel: Faktorzerlegung, rekursiv
- Typ-Umwandlungen in Modula 2
- Beispiel: HEX-Ausgabe (rekursiv)
- Funktionen
- Funktionen allgemein
- Lambda-Notation
- höhere Funktionen
- Funktionsprozeduren
- Nachtrag: höhere Funktionen
- Kartesisches Produkt: assoziativ
- algebraische Strukturen
- Zeichenketten, Wörter: Halbgruppe, Monoid
- Homomorphismus; Beispiele
- Codierungen: umkehrbar?
- Nachtrag: Beispiele zu Halbgruppen
- Prozeduren
- Prozeduraufruf: Argumente
- Prozedurvereinbarung: Parameter
- Block: Gültigkeitsbereich; Schachtelung
- lokale Objekte: Konstanten, Typen, Variablen, Prozeduren, Funktionen
- Beispiel für Funktionsprozedur: HexDigit
- Skalare Typen
- Variablen
- Variablenbegriff in verschiedenen Wissensgebieten
- Variablen als Behälter für Werte
- Speicherobjekte: Attribute und Zugriffsmethoden
- Speicher: Zellen; Hausnummern; Adressen
- Lebensdauer: persistent, statisch, automatisch, dynamisch
- Alias-Phänomene
- Blöcke
- Block als Gültigkeitsbereich: Schachtelung
- Aktivierungsobjekt: Inkarnation, Umgebung
- Umgebungsbindung bei Prozeduren; Hülle
- Strukturierte Typen
- Tabellen als strukturierte Objekte
- Reihungen: Arrays; Indizierung
- Beispiel: Verkehrsampel
- Strukturierte Typen
- Mehrdimensionale Reihungen, Matrizen
- Verbunde: Records; Selektion
- Beispiel: Datumsangaben
- Sequenzen; Formale Sprachen
- Alphabet A: endliche Menge von Symbolen
- Wortmenge A*: freies Monoid: Menge aller Wörter
- Formale Sprache: eine Teilmenge L von A*, meist unendlich!
- Probleme bei Formalen Sprachen
- jedes L ist abzählbar, die Menge aller L nicht!
- gib endliche Beschreibung für L
- finde Aufzählung aller Elemente von L
- entscheide: ist w aus A* in L?
- Grammatiken
- Chomsky-Grammatiken: G = (T, N, P, S)
- Terminalsymbole, Nichtterminalsymbole, Regeln, Startsymbol
- Ableitungsschritt, Ableitung; Satzform, Satz
- Erzeugte Sprache L(G) zu G; Beispiel
- Sprachklassen 0, 1, 2, 3
- Entscheidbarkeit; Aufwand
- endliche Automaten
- Beispiel: Zigarettenautomat
- Übergangsdiagramm und Übergangstafel
- akzeptierte und erzeugte Sprache
- Akzeptor und Transduktor
- endliche Automaten
- Grammatik zur Automatentafel: Äquivalenz
- dual zum Übergangsdiagramm: spezielles Syntaxdiagramm
- Gleichwertigkeit mit Klasse 3
- reguläre Ausdrücke
- Effizienz und Aufwand; Bemerkungen zur Komplexität
- Nichtdeterminismus: untere Komplexitätsschranken
- allgemeine Syntaxdiagramme
- Terminalknoten und Nichtterminalknoten
- rekursiver Aufruf von Diagrammen
- Abarbeitung: Formularmaschine, Stapelprinzip
- Kellerautomat
- Gleichwertigkeit mit Klasse 2
- Implementierung endlicher Automaten
- deterministische und nichtdeterministische Automaten
- Reguläre Ausdrücke
- Notation von kontextfreien Grammatiken
- Sprachebenen: Metasprache
- BNF: Backus-Naur-Form
- EBNF: erweiterte BNF
- Erzeugungs-Maschine für Klasse 0 ?
- Aufbau eines Programmoduls
- Import von Schnittstellen
- Konstantenvereinbarung
- Mengentypen
- Variablenvereinbarung
- Inhalt und Referenz, Speicherobjekte
- Pointertypen, Pointervariablen
- Dereferenzierung, dangling pointer, NIL
- Meldungen bei Pointerfehlern
- dynamische Datenstrukturen, Geflechte
- Abstrakte Datentypen, algebraische Strukturen
- algebraische Spezifikation; Funktionale Programmierung
- Datentyp lineare Liste
- Beispiel: natürliche Zahlen
- prozedurale Implementierung: verkettete Listen
- Abstrakte Datentypen in Modula 2: opake Typen
- Freigabe von Listenobjekten
- Traversierung von Listen; Schleppzeigertechnik
- Probleme bei Zuweisung: Alias; tiefe Kopie
- Wertvergleich von Listen
- Aufwand und Effizienz:
-Notation
- Wiederholung:
- Pointer, linear verkettete Listen
- Effiziente Operationen auf Listen
- Einfügen und Löschen am Listenanfang
- im Inneren: Einfügen und Löschen: Problematik
- Effiziente Operationen auf Listen
- Einfügen und Löschen hinter Einstieg
- Einfügen vor Einstieg
- Löschen am Einstieg
- eigene Freilistenverwaltung
- Abstrakter Datentyp Stack
- funktionale Definition
- Realisierung als Liste
- Abstrakter Datentyp Queue
- funktionale Definition
- Realisierung im Array
- Abstrakter Datentyp Queue
- Realisierung im Array: leere Schlange
- Realisierung als Liste mit Beschreibungsblock
- Realisierung als Ringliste
- Abstrakter Datentyp Doppelschlange
- Doppelt verkettete Listen
- Bäume und Wälder
- Binärbäume
- Wald und äquivalenter Binärbaum
- Durchwanderung; Prozedurtypen
- Vereinigungstypen: Verbunde mit Varianten
- Rekursive Listen
- Kartesische und Polarkoordinaten
- Varianten ohne Schalterfeld
- Methodenfelder im Verbund
- allgemeine Dateien in UNIX
- Suchbäume
- Einfügen und Suchen
- Suchaufwand; Entartungsfälle
- 2-3-Bäume; AVL-Bäume
- Suchverfahren allgemein
- Rechtsrekursion und Iteration
- ungerichtete und gerichtete Graphen
- Listen von Knoten und Kanten
- Inzidenzmatrix
- Knoten und Liste der Nachfolger
- Zusammenhangskomponente
- binäre Relationen und gerichtete Graphen
- Inzidenzmatrix
- spezielle Eigenschaften
- Äquivalenzrelation, Klassenzerlegung
- Ordnungsrelation, Halbordnung, Totalordnung
- Relationenalgebra
- binäre Relationen und gerichtete Graphen
- transitive Relationen
- transitive Hülle: Verfahren von Warshall
- Durchwanderung ungerichteter Graphen: Färbung
- Tiefensuche: Labyrinth
- spannender Baum: Gerüst
- Speicherbereinigung: Garbage Collection
- Breitensuche: Platinenverdrahtung
- Verfahren von Lee; Manhattan-Metrik
- Graphen: Bemerkungen und Sonderfälle
- dünnbesetzte Inzidenzmatrix
- vollständiger Binärbaum: Ablage im Array
- Techniken zur Effizienzverbesserung
- lineare, quadratische, ganzzahlige Programmierung (Optimierung)
- Äquivalenzrelationen als Wald
- Pfadkompression
- Techniken zur Effizienzverbesserung
- Wiederholung:
- Modularisierung
- abstrakte Datentypen: funktionale Spezifikation