Informatik 2

Inhaltsverzeichnis

Vorbemerkung.- 5. Blockstruktur und dynamische Speicherverteilung.- 5.1 Blöcke und Speicherverteilung.- 5.1.1 Blockstruktur.- 5.1.2 Pulsierende Speicherverteilung.- 5.1.3 Wortorganisierte Speicher.- 5.1.4 Relative Adressierung.- 5.1.5 Felder mit dynamisch errechneten Indexgrenzen.- 5.1.6 Abschließende Bemerkungen.- 5.2 Prozeduren und Blockstruktur.- 5.2.1 Einbeziehung von Prozeduren in die Blockstruktur.- 5.2.2 Ergänzung des Blockstrukturbaums durch Aufrufpfeile.- 5.2.3 Dynamischer Blockstrukturbaum.- 5.2.4 Statische und dynamische Verweisketten.- 5.2.5 Dynamische Speicherverteilung im Falle des Vorkommens von Prozeduren.- 6. Hintergrundspeicher und Verkehr mit der Außenwelt, Datenstrukturen, Speicherorganisation.- 6.1 Technische Charakteristika von Hintergrundspeichern und E/A-Geräten.- 6.1.1 Speicher mit direktem Zugriff.- 6.1.2 Speicher mit indirektem Zugriff.- 6.1.3 Transport-und Übertragungseinheiten.- 6.2 Funktionelle Beschreibung von Hintergrundspeichern und E/A-Geräten.- 6.2.1 Lochkarten und Lochkartenstöße, Lochstreifen/Nicht wiederverwendbare Medien.- 6.2.2 Magnetbandspeicher mit Blöcken wechselnden Umfangs / Wiederverwendbare Medien mit sequentiellem Zugriff auf Blöcke wechselnden Umfangs.- 6.2.3 Magnetband-und Scheibenspeicher mit fester Blockeinteilung / Wiederverwendbare Medien mit sequentiellem Zugriff auf fest eingeteilte Blöcke, organisierte Speicher.- 6.2.4 Magnetplattenspeicher/Wiederverwendbare Medien mit rotierendem Zugriff.- 6.3 Einführung neuer Rechenstrukturen.- 6.3.1 Teilstrukturen.- 6.3.2 Operative Anreicherung.- 6.3.3 Paar-und Tupelbildung.- 6.3.4 Variantenbildung.- 6.3.5 Rekursive Definition von Rechenstrukturen: Rekursive Datenstrukturen.- 6.3.5.1 Stapel.- 6.3.5.2 Beblätterte Binärbäume.- 6.3.5.3 Bezeichnete Binärbäume.- 6.3.5.4 Allgemeine beblätterte Bäume.- 6.3.5.5 Algorithmen auf rekursiven Datenstrukturen.- 6.3.6 Terme und Diagramme.- 6.3.6.1 Aufbau und Auswertung von Termen.- 6.3.6.2 Kantorovic-Bäume und Gabelbilder.- 6.3.6.3 Terme und Schachteldiagramme.- 6.3.6.4 Benutzung des Assoziativgesetzes.- 6.4 Datenorganisation: Listen und Zeiger.- 6.4.1 Listen.- 6.4.1.1 Referenzen.- 6.4.1.2 Unendliche Listen.- 6.4.2 Organisierte Speicher.- 6.4.2.1 Errechnete Variablenbezeichnungen.- 6.4.2.2 Der Übergang von zusammengesetzten Objekten zu organisierten Speichern.- 6.4.2.3 Gleichbesetzungs-Tabu, Seiteneffekte.- 6.4.3 Zeiger.- 6.4.3.1 Zeigergeflechte.- 6.4.3.2 Deklaration einer Zeigersorte.- 6.4.3.3 Schaffung von Variablen und Zeigern.- 6.4.3.4 Gleichheit von Zeigern.- 6.4.4 Geflechtbildende Variabelensätze.- 6.5 Zeiger-Implementierungen organisierter Speicher.- 6.5.1 Implementierung von Stapeln.- 6.5.1.1 Stapel als Einweg-Listen.- 6.5.1.2 Verkettung zweier Einweg-Listen.- 6.5.1.3 Prozeduren des Moduls KELLER.- 6.5.2 Implementierung von Sequenzen.- 6.5.2.1 Sequenzen als lineare Zweiweg-Listen.- 6.5.2.2 Kopieren von linearen Zweiweg-Listen.- 6.5.2.3 Prozeduren mit Sequenz-Variablen.- 6.5.3 Implementierung von beblätterten Bäumen.- 6.5.3.1 Beblätterte Binärbäume als Listen mit Varianten Zeigern.- 6.5.3.2 Allgemeine beblätterte Bäume als Listen mit Varianten Zeigern.- 6.6 Implementierung organisierter Speicher mittels linearer Speicher.- 6.6.1 Gestreute Speicherung.- 6.6.2 Sequentielle Speicherung.- 7. Formale Sprachen.- 7.1 Relationen und formale Systeme.- 7.1.1 Dyadische Relationen und gerichtete Graphen.- 7.1.1.1 Mengeneigenschaft der Relationen.- 7.1.1.2 Das Produkt zweier Relationen.- 7.1.1.3 Die konverse Relation.- 7.1.1.4 Maximale und größte, minimale und kleinste Elemente.- 7.1.1.5 Reflexivität.- 7.1.1.6 Transitivität.- 7.1.1.7 Hüllen.- 7.1.1.8 Äquivalenzklassen.- 7.1.2 Noethersche und konfluente Relationen.- 7.1.2.1 Wege.- 7.1.2.2 Noethersche Relationen und Graphen.- 7.1.2.3 Hüllen einer Noetherschen Relation.- 7.1.2.4 Irreduzible Elemente, terminierende Wege.- 7.1.2.5 Der nichtdeterministische Ersetzungsalgorithmus.- 7.1.2.6 Konfluente Relationen, eindeutige Normalformen.- 7.1.2.7 Church-Rosser-Eigenschaft.- 7.1.3 Formale Sprachen-allgemeine Begriffe.- 7.2 Formale Sprachen über Zeichenfolgen.- 7.2.1 Kompatible Ersetzungssysteme.- 7.2.2 Semi-Thue-Systeme.- 7.2.3 Semi-Thue-Algorithmen.- 7.2.4 Chomsky-Sprachen und-Grammatiken.- 7.2.4.1 Kontext-sensitive Chomsky-Grammatiken.- 7.2.4.2 Kontextfreie Chomsky-Grammatiken.- 7.2.4.3 Reguläre Grammatiken.- 7.2.4.4 Endliche Grammatiken.- 7.2.5 Backus-Notation und erweiterte Backus-Notation.- 7.2.5.1 Varianten.- 7.2.5.2 Syntax-Diagramme.- 7.2.5.3 Replikationsstern.- 7.2.5.4 Verallgemeinerte Syntax-Diagramme.- 7.2.5.5 Adjunktion und Elimination von Hilfszeichen.- 7.2.6 Reguläre Ausdrücke.- 7.2.7 Substitution von Grammatiken.- 7.3 Strukturgraph und Strukturbaum eines Ersetzungswegs.- 7.3.1 Bipartite Graphen.- 7.3.2 Strukturgraphen und Strukturbäume.- 7.3.3 Konstruktion des Strukturgraphen.- 7.3.4 Eindeutigkeit.- 7.3.5 Ein Eindeutigkeitskriterium.- 7.3.6 Die Strukturgrammatik einer Grammatik.- 7.4 Das Zerteilungsproblem.- 7.4.1 Sackgassen.- 7.4.1.1 Abschneiden von Sackgassen.- 7.4.1.2 Kontext-sensitive Grammatiken mit konfluenter Ersetzungsrelation.- 7.4.1.3 Sackgassen in regulären Grammatiken.- 7.4.2 Sequentielle Zerteilungsverfahren für reguläre Grammatiken.- 7.4.2.1 Zustands-Übergänge.- 7.4.2.2 Der Äquivalenzsatz von KupLEENE.- 7.4.2.3 Endliche Automaten.- 7.4.3 Sequentielle Zerteilungsverfahren für kontextfreie Grammatiken.- 7.4.3.1 Kellerzustands-Übergänge.- 7.4.3.2 Keller-Automaten.- 7.4.3.3 LR(k)-Grammatiken.- 7.4.4 Sequentielle zielbezogene Zerteilungsverfahren.- 7.4.4.1 Konverse Zustandsübergänge.- 7.4.4.2 LL(k)-Grammatiken.- 7.4.5 Verfahren des rekursiven Abstiegs.- 7.5 Berechenbarkeit und Entscheidbarkeit.- 8. Syntaktische und semantische Definition algorithmischer Sprachen.- 8.1 Syntax algorithmischer Sprachen.- 8.1.1 Syntaktische Beschreibung zusammengesetzter Objekte.- 8.1.2 Syntaktische Beschreibung von Kantorovic-Bäumen.- 8.2 Operative Semantik.- 8.2.1 Aufbau und Berechnung von Formeln.- 8.2.2 Partielle Definiertheit.- 8.2.3 Nicht-strikte Operationen.- 8.2.4 Nichtdeterminismus.- 8.2.5 Semantik der Parameterübergabe bei Rechenvorschriften.- 8.2.6 Operative Semantik der Rekursion.- 8.2.7 Reduktionsmaschinen.- 8.3 Zustandssemantik.- 8.3.1 Zustandskalkül nach MCCARTHY.- 8.3.2 Zusicherungskalkül nach FLOYD, HOARE UNDDIJKSTRA.- 8.3.2.1 Das Zuweisungsaxiom.- 8.3.2.2 Das Zusammensetzungsaxiom.- 8.3.2.3 Die Fallunterscheidungs-Axiome.- 8.3.2.4 Das Wiederholungs-Axiom.- 8.3.2.5 Allgemeine Regeln.- 8.3.2.6 Verifikation von Programmen.- 8.3.2.7 Sprünge und Schleifeninvarianten.- 8.4 Mathematische Semantik.- 8.4.1 Fixpunkttheorie.- 8.4.1.1 Fixpunkttheorie der Rekursion.- 8.4.1.2 Fixpunkttheorie im wp-Kalkül.- 8.4.1.3 Rekursive Definition der Semantik einer algorithmischen Sprache.- 8.4.2 Abstrakte (Daten-)Typen.- 8.4.2.1 Der Signaturgraph.- 8.4.2.2 Die Termalgebra eines abstrakten Typs.- 8.4.2.3 Rechenstrukturen als endlich erzeugte Modelle eines abstrakten Typs.- 8.4.2.4 Beispiele polymorpher Typen.- 8.4.3 Abstrakte Typen und die Charakterisierung primitiver Rechenstrukturen.- 8.4.4 Abstrakte Typen und die Charakterisierung der Syntax und Semantik von Programmiersprachen.- Ergônzende Literatur.- Namen- und Sachverzeichnis.