Einführung in Die Informatik

ISBN-13: 9783519022466 / Niemiecki / Miękka / 1990 / 548 str.

G. Nther Hotz; Gunther Hotz

Opis

in die Informatik Von Prof. Dr. rer. nat. Gunter Hotz UniversiHit Saarbriicken 83 B. G. Teubner Stuttgart 1990 Prof. Dr. rer. nat. Gunter Hotz Studium der Mathematik mit Nebenfach Physik an den Universitaten Frankfurt und Gottingen. Diplom und Promotion in Mathematik in Got tingen. Drei Jahre Entwicklungsingenieur in der Firma Telefunken. Seit 1962 in Saarbriicken, zunachst als Habilitand der Fritz-Thyssen-Stiftung; Habilitation in Angewandter Mathematik mit einer Arbeit aus dem Gebiet der Informatik. Seit 1969 Professor, zunachst in Angewandter Mathema tik, spater in Informatik, an der Universitat des Saarlandes. CIP.Titelaufnahme der Deutschen Bibliothek Hotz, Giinter: EinfOhrung in die Informatik I von Gunter Hotz. Stuttgart: Teubner, 1990 (Leitfaden und Monographien der Informatik) ISBN-13: 978-3-519-02246-6 e-ISBN-13: 978-3-322-80096-1 DOT: 10.1007/978-3-322-80096-1 Das Werk einschlieBlich aller seiner Teile ist urheberrechtlich geschOtzt. Jede Verwertung aul3erhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlages unzulassig und strafbar. Das gilt besonders fOr Vervielfaltigungen, Ubersetzungen, Mikroverfilmungen und die Ein speicherung und Verarbeitung in elektronischen Systemen."

Spis treści

1 Grundbegriffe.- 1.1 Notationen.- 1.2 Halbgruppen und Monoide.- 1.3 Homomorphismen und Erzeugendensysteme.- 1.4 Quotienten von Monoiden.- 1.5 Einfache Programme.- 1.6 Aufgaben.- 2 Mathematische Modelle.- 2.1 Definition einer mathematischen Maschine.- 2.1.1 Eine erste Gliederung der Maschine.- 2.1.2 Beschreibung des Programm- und Rechenspeichers.- 2.1.2.1 Der Programmspeicher.- 2.1.2.2 Der Rechenspeicher.- 2.1.3 Beschreibung des Schaltwerkes.- 2.1.3.1 Einige Operationen und ihre Wirkungen.- 2.1.3.2 Bedeutung der Schalter ?1und ?2.- 2.1.4 Ausbau des Befehlsvorrats, Indexregister, Adressenrechnung, Programmbeispiele.- 2.1.4.1 Das Hornerschema als Programmbeispiel.- 2.1.4.2 Adressenrechnung und Adressenmodifikation.- 2.1.5 Ein Sortierprogramm.- 2.2 Die formale Definition der Maschine.- 2.2.1 Abstrakte Maschinen und Berechnungen.- 2.2.2 Simulationen.- 2.2.3 Beispiele von Simulationen und Weiterentwicklung des Begriffes.- 2.2.4 Partielle und relationelle Simulationen.- 2.2.5 Spezielle Simulationen und Abschlußeigenschaften.- 2.2.6 Verschiebbarkeit von Programmen im Programmspeicher.- 2.3 Unterprogrammtechnik.- 2.3.1 Anforderungen an eine Unterprogrammtechnik.- 2.3.1.1 Realisierungsidee.- 2.3.2 Erweiterung der Maschinenkonfiguration.- 2.3.3 Dycksprachen und Klammerausdrücke.- 2.3.3.1 Analyse von Klammerausdrücken.- 2.3.3.2 Listen und Programme.- 2.3.4 Der Kellerautomat oder Push-Down-Automat.- 2.3.5 Syntaktisch korrekte Programme.- 2.3.5.1 Syntaxregeln.- 2.3.5.2 Automatische Überprüfung der Kriterien.- 2.3.5.3 Abfolge der Befehle.- 2.3.6 Organisation der Maschine.- 2.3.6.1 Definition der erweiterten Konfiguration.- 2.3.6.2 Die Syntaxanalyse.- 2.3.7 Seitenorientierte Verwaltung des Rechenspeichers.- 2.3.8 Ein Beispiel.- 2.3.8.1 Aufgabenstellung.- 2.3.8.2 Beschreibung des Programmes u zur Berechnung von ?(w) für w ? ? - Z+.- 2.3.9 Dynamische Verwaltung des Rechenspeichers.- 2.4 Aufgaben.- 3 Schaltkreise und Schaltwerke.- 3.1 Einleitung.- 3.2 Die boolesche Algebra der Schaltfunktionen.- 3.2.1 Definition der Schaltfunktionen und ein Beispiel.- 3.2.2 Die Boolesche Algebra der Schaltfunktionen.- 3.2.3 Boolesche Ausdrücke und Schaltkreise.- 3.2.3.1 Bemerkungen zum Bausteinsystemen.- 3.2.4 Berechnungsnetze und Laufzeiten.- 3.2.4.1 Berechnungsdauer in einem Berechnungsgraphen.- 3.2.5 Minimalpolynome.- 3.2.6 Schaltfunktionen, n-dimensionaler Würfel, Diagramme.- 3.2.7 Boolesche Netze.- 3.2.7.1 Simultane Berechnung zweier Übertragsfunktionen.- 3.2.7.2 Eine Bemerkung zur Berechnung unterer Schranken für die Kosten von Realisierungen.- 3.3 Sequentielle Schaltkreise.- 3.3.1 Das D-Flipflop.- 3.3.1.1 Ein Zähler modulo 10.- 3.3.2 Das (R,S)-Flipflop.- 3.3.3 Ausnutzung der funktionalen Eigenschaften des (R,S)- Flipflops.- 3.3.3.1 Ein Multiplizierer modulo 7.- 3.3.4 Auflösung boolescher Gleichungssysteme.- 3.3.5 Endliche Automaten und sequentielle Schaltkreise.- 3.3.5.1 Der Zustandsgraph eines endlichen Automaten ..- 3.3.6 Reguläre Mengen.- 3.3.6.1 Abschlußeigenschaften der regulären Mengen.- 3.3.6.2 Ein Erzeugendensystem der Kleene-Algebra.- 3.3.6.3 Eine Realisierung endlicher Akzeptoren durch Schaltwerke.- 3.3.7 Produkte endlicher Automaten.- 3.3.8 Lineare Schaltwerke.- 3.3.9 Alternative Beschreibung von Schaltwerken.- 3.4 Mikroprogrammierung.- 3.4.1 Vorläufiges über Programmiersprachen.- 3.4.2 Die Datenstrukturen der Mikroprogramme.- 3.4.3 Die Elementaroperationen der Mikroprogrammierung.- 3.4.4 Die Struktur der Mikroprogramme.- 3.4.4.1 Mikroprogramm für die Addition nach der Schulmethode.- 3.4.5 Die Syntax der Mikroprogramme.- 3.4.6 Die Semantik der Mikroprogramme.- 3.4.7 Realisierung der Mikroprogramme durch Schaltwerke.- 3.4.8 Ein Mikroprogramm für die Multiplikation.- 3.4.9 Das Speicherwerk.- 3.4.10 Mikroprogrammwerk.- 3.4.11 Schlußbemerkungen.- 3.5 Aufgaben.- 4 Programmiersprachen.- 4.1 Grundlegende Konzepte.- 4.1.1 Einleitung.- 4.1.2 Programmbeispiele und Anweisungen.- 4.1.3 Der Datentyp Real.- 4.1.4 Der Datentyp String.- 4.1.5 Der Datentyp List.- 4.1.6 Der Datentyp Sentence.- 4.1.7 Die Datentypen Boolean und Set.- 4.2 Unstrukturierte Programme.- 4.2.1 Wertzuweisungen, Variablen, Konstanten und Typen.- 4.2.1.1 Einfache Zuweisungen und einfache Prädikate.- 4.2.2 Ausdrücke.- 4.2.2.1 Arithmetische Ausdrücke.- 4.2.2.2 Arithmetische Prädikate.- 4.2.2.3 Allgemeinere Interpretationen.- 4.2.2.4 Allgemeine Ausdrücke.- 4.2.2.5 Wertzuweisung.- 4.2.3 Einfache Programme.- 4.2.3.1 Endgültige Definition der “einfachen Programme”.- 4.2.4 Elimination von Kontrollanweisungen.- 4.2.5 Elimination von Ausdrücken.- 4.3 Prozeduren.- 4.3.1 Einleitung.- 4.3.2 Die Syntax von Prozeduren und Programmen.- 4.3.2.1 Prozeduren.- 4.3.2.2 Die Syntax der Programme von PSp.- 4.3.3 Die Semantik der Programme aus PSp.- 4.3.3.1 Aufspannende Bäume und Wege in Graphen.- 4.3.3.2 Definition der Semantik der Programme.- 4.3.3.3 Prozeduren als Prozedurparameter.- 4.4 Datenstrukturen.- 4.4.1 Felder oder Arrays.- 4.4.1.1 Darstellung von Matrizen als lineare Arrays.- 4.4.2 Verbunde oder Records.- 4.4.2.1 Definition des Verbundes.- 4.4.2.2 Konstruktion des zu dem Verbund gehörigen Graphen.- 4.4.2.3 Definition der Variablen des Verbundes.- 4.4.2.4 Definition der Operationen für Verbund variablen.- 4.4.3 Der Datentyp flexibles Array.- 4.4.4 Das Modulkonzept.- 4.4.4.1 Der Modul List.- 4.5 Reduktionen.- 4.5.1 Elimination von Prozeduren.- 4.5.1.1 Die formale Konstruktion.- 4.6 Reguläre Datentypen und Wörterbücher.- 4.6.1 Hierarchische Verfeinerung regulärer Datentypen.- 4.7 Unvollständigkeit von Programmiersprachen.- 4.7.1 Die Antinomie des Barbiers.- 4.7.2 Die Nichtabzählbarkeit der unendlichen Dualbrüche.- 4.7.3 Die Unvollständigkeit der Programmiersprachen.- 4.8 Aufgaben.- Literatur.- Ergänzende und weiterführende Literatur.- Liste der Tabellen.- Liste der Abbildungen.- Verzeichnis der Maschinenbefehle.- Verzeichnis der Programme.- Symbolverzeichnis.