Informatik

Die Informatik ist die Wissenschaft der systematischen Verarbeitung von Information. Sie, auch als "computer science" bezeichnet, beschäftigt sich mit deren automatischer Verarbeitung mit Hilfe von Computern, synonym auch Digitalrechner oder elektronische Datenverarbeitungsanlage. Dabei stehen die Struktur und das Zusammenwirken von Prozessen, Daten und Sprachen im Mittelpunkt des Interesses. Nach den jeweiligen Schwerpunkten unterscheiden sich technische, theoretische, praktische und angewandte Informatik. Der technischen Informatik sind die Untersuchungen und Entwicklungen des funktionellen Aufbaus von Computern und deren zugehörigen Geräten eigen, sowie Rechnerarchitekturen, die "Hardware" also, und der Entwurf logischer Schaltungen.

Das Rechnen betreibt die Menschheit vermutlich schon seit der Urzeit, eine mechanische Unterstützung dieser intellektuellen Leistung bot bereits im Altertum und Mittelalter der Abakus, ein Brett mit verschiebbaren Kugeln für die vier Grundrechenarten. 1623 konstruierte Wilhelm Schickard(1592-1635) eine Maschine zur Addition, Subtraktion, Multiplikation und Division für Kepler, die unbeachtet blieb, und achtzehn Jahre später stellte Blaise Pascal(1623-1662) eine Maschine zur Addition sechsstelliger Zahlen vor. Eine Rechenmaschine mit Staffelwalzen, die die binäre Darstellung von Zahlen benutzte, baute 1674 Gottfried Wilhelm Leibniz(1646-1716), die ab 1818 in die serienmäßige Herstellung ging. Charles Babbage(1792-1871) plante 1838 seinen "Analytical Engine", der mit einem Zahlenspeicher, einem Rechenwerk, einer Steuereinheit und einem Programmspeicher ausgestattet, über Lochkarten die programmgesteuerte Reihenfolge von Rechenoperationen verarbeiten sollte. Die unzulängliche feinmechanische Technik seiner Zeit verhinderte allerdings die volle Funktionsfähigkeit dieser modern anmutenden Idee. Die erste funktionstaugliche, programmgesteuerte Rechenmaschine war die elektro-mechanische Anlage Z3 von Konrad Zuse(1910-1995), die 1941 fertiggestellt wurde und deren Programmierung über Lochstreifen erfolgte. Ihr folgte 1946 der ENIAC (electronic numerical integrator and automatic calculator) von J. P. Eckert und J. W. Mauchly als erste vollelektronische Anlage und 1949 der EDSAC (electronic delay storage automatic calculator) von M. V. Wilke als erster universeller Digitalrechner, der ein Programm speichern konnte. Seit den fünfziger Jahren wird die Entwicklung der Datenverarbeitungsanlagen in Generationen gezählt, die durch die verwendete Schaltkreistechnologie charakterisiert sind. Der Fortschritt ging hierbei von der Benutzung von Elektronenröhren, die etwa tausend Additionen pro Sekunde bewältigten, über Halbleiterschaltkreise, Transistoren und Dioden zu höchstintegrierten Schaltkreisen, die etwa zehn Millionen Additionen pro Sekunde berechnen. Die Architektur all dieser Rechenanlagen geht auf das Konzept eines universellen Computers von John von Neumann(1903-1957) und anderer Wissenschaftler am Institute of Advanced Study at Princton zurück, das in den Jahren 1946 bis 1952 entwickelt wurde. Es sieht eine Einteilung in die fünf Einheiten Steuerwerk, Rechenwerk, Speicher, Eingabe- und Ausgabewerk vor. Die notwendigen Bearbeitungsvorschriften, das Programm, wird von außen eingeben und befindet sich zusammen mit seinen Daten im selben Speicher. Dieser Speicher wird in gleichgroße Zellen eingeteilt, wo die Befehle aufeinanderfolgend abgelegt werden. Das Ansprechen der entsprechenden Speicherzellen erfolgt durch eine Adressierung im Steuerwerk. Das Konzept kennt neben arithmetischen und logischen Anweisungen auch Transport- und Sprungbefehle. Die Kodierung von Programmen erfolgt, wie schon bei Leibniz, binär

Seit ungefähr 1960 in den USA und 1970 in Deutschland wird Informatik als theoretisch fundierte Grundlagenwissenschaft betrieben und gilt nicht mehr als Ansammlung entliehener Regeln und Methoden anderer Wissenschaften. Der Gegenstand dieser Ingenieurwissenschaft ist Information, anstelle von Materie und Energie, die durch Kommunikation ausgetauscht wird. Bei der Betrachtung des Begriffs Information wird die Nähe zu dem von Wissen deutlich erkennbar. Die Informatik geht von einer Darstellung durch Signale, Zeichen, Nachrichten oder Sprache aus. Bei der Verarbeitung von Information spielen Eingabe, Ausgabe, Übermittlung, Speicherung, Klassifizierung, Umwandlung und Kombination eine Rolle. Information besitzt Eigenschaften wie Orts- und Zeitunabhängigkeit, es gibt keine Originale, sondern lediglich Kopien von Gegenständen der Wirklichkeit. Information ist komprimierbar, aus Bruchstücken rekonstruierbar und in der Lage sich selbst zu verarbeiten. Als Bestandteile einer Information gelten Syntax, Semantik und Pragmatik. Die Syntax ergibt sich aus Signalen, Daten oder Nachrichten, die Semantik aus der Interpretation durch Menschen, Algorithmen oder Datenbanken. Die Pragmatik, der Zweck oder die ableitbaren Handlungen, bleiben in dieser Sichtweise in der Regel verborgen. Mit diesem umfangreichen Begriff von Information findet die Informatik Eingang in andere Wissenschaften, wo sie als Anwendung der technischen, theoretischen und praktischen Kerninformatik angewandte Informatik genannt wird. Sie behandelt Gebiete wie die Kommunikation von Menschen mit Maschinen, die gesellschaftliche Akzeptanz der elektronischen Datenverarbeitung und die Ergonomie von Computern am Arbeitsplatz oder in der privaten Anwendung. Aus der Spezialisierung auf bestimmte Wissenschaften entstanden beispielsweise Wirtschafts,- Rechts- und Medizininformatik. Jede Wissenschaft profiliert sich durch eigene Methoden, in diesem Sinn ist die Informatik die Methodologie des Gegenstandsbereichs Information.

Grundsätzliche, prinzipielle Methoden, die über Einzelwissenschaften hinausgehen, bezeichnen Philosophien, die Aufstellung von Lebens- und Arbeitsregeln, oder Paradigmen, typische Beispiele für Vorgehensweisen innerhalb einer wissenschaftlichen Periode. Bis etwa 1970 wurde die Informatik als "Kunst" betrieben, was bei der Erstellung umfangreicher Systeme zu den Problemen der Softwarekrise führte, anschließend und bis in die 90¹er Jahre herrscht die Philosophie der strukturellen Zerlegung vor. Sie konkretisiert sich in der Analyse an der wiederholten Zerlegung in Komponenten, im Entwurf an einer hierarchischen Modularisierung, in der Implementierung an der Aufteilung des Ablaufs in Einzelschritte und in der Zerlegung der Entwicklung von Informatiksystemen in die vorgenannten Phasen. Dieser Prozeß endet auf einem atomaren Niveau, wo keine weitere sinnvolle Aufgliederung mehr möglich ist. Aus der Mathematik ist dieses Vorgehen als Orthogonalisierung bekannt, unter der die Angabe einer endlichen Anzahl beliebig kombinierbarer Basiselemente ohne einschränkende Bedingungen verstanden wird. Neben der "Strukturalisierung" existieren noch die Kategorien der "Algorithmisierung", die der theoretischen Informatik zugeordnet werden kann, und die einer tendenziellen "Versprachlichung" von Sachverhalten, mehr der praktischen Informatik zuzurechnen. Der Begriff Algorithmus gilt als zentral für die gesamte Informatik und leitet sich vom Namen des persisch-arabischen Mathematikers Ibn Musa Al-Chwarismi ab, der im 9. Jh. n. Chr. ein Buch über die "Regeln der Wiedereinsetzung und Reduktion" schrieb. Allgemein ist ein Algorithmus eine Beschreibung einer Anweisungsmenge, die einer Person oder Maschine zur Ausführung übergeben werden kann, oder genauer: ein formal beschreibbares, mechanisch oder elektronisch nachvollziehbares Verfahren zur Lösung einer Klasse von Problemen. Die präzisen Definitionen, die in Mathematik und Informatik gebräuchlich sind, führen über die Churchsche These zu den Begriffen einer virtuellen Maschine und denen der Berechen- bzw. Entscheidbarkeit. Nach Goldschlager und Lister "“... wurden die folgenden zwei Aussagen weitverbreitete Annahmen: (1) Alle vernünftigen Definitionen von "Algorithmus", soweit sie bekannt sind, sind gleichwertig und gleichbedeutend. (2) Jede vernünftige Definition von "Algorithmus", die jemals irgendwer aufgestellt hat, ist gleichwertig und gleichbedeutend zu denen, die wir kennen. Diese Annahmen sind als Church-Turing-These (Wort im Original kursiv, A.d.V) (oder manchmal Church's These) bekanntgeworden ..." ([GOL] S. 81)

Dem "Duden “Informatik" kann folgendes entnommen werden: "(...) formulierte A. Church im Jahre 1936 die folgende nach ihm benannte These: Jede im intuitiven Sinne berechenbare Funktion ist Turing-berechenbar(Satz im Original kursiv, A.d.V.)" ([LEK] S. 129).

Dorffner führt diese These, in Zusammenhang mit der von-Neumann-Architektur, als "Theorem" ([DOR] S. 7) an: "Church-Turing-These: (Wort im Original fett, A.d.V) Jede berechenbare Funktion kann von einer Turing-Maschine berechnet werden, somit auch von jeder Maschine, die einer Turingmaschine äquivalent ist. Ein von Neumann Computer, mit theoretisch beliebig viel Speicherraum, ist einer Turingmaschine äquivalent.(Sätze im Original kursiv, A.d.V.)" (ebenda). Aus den Zitaten wird ersichtlich, daß sich ein Algorithmus formal äquivalent durch eine Maschine, eine berechenbare Funktion oder eine Folge von ausführbaren, intuitiv verständlichen Anweisungen beschreiben läßt. Voraussetzungen sind eine wohl-definierte Spezifikation des zu lösenden Problems, insbesondere die Angabe der Umstände, unter denen es als gelöst gilt, und ein Prozessor, der die Bearbeitung leistet.

Eine Maschine, die sich zur Beschreibung eines Algorithmus konstruieren läßt, hat A. M. Turing(1912-1954) vorgestellt. Sie besteht aus einem unbegrenzten, in einzelne Felder unterteilten Band, das jeweils um ein Feld nach rechts oder links verschoben werden kann. Die Felder enthalten Zeichen oder sind leer. Ein Schreib- Lesekopf, der sich immer über genau einem Feld befindet, liest entweder ein Zeichen oder beschreibt das Band mit einem Symbol aus einem bekannten Alphabet. Eine Steuereinheit, die sich in einem bestimmten Zustand befindet, interpretiert das gelesene Zeichen, führt eine Schreib- oder Bewegungsaktion durch und geht in den nächsten Zustand über. Die Verarbeitung eines Algorithmus geschieht, indem einige Felder des Bandes mit Zeichen beschrieben werden, die Steuereinheit in einen Anfangszustand über einem Feld versetzt wird und die Maschine dann in Schritten die Aktionen, die die Zeichen beschreiben, ausführt. Die Beschreibung auf dem Band heißt Programm.

In der Mathematik ist die Darstellung eines Algorithmus als Funktion gebräuchlich. Eine Funktion ist eine eindeutige Zuordnung der Elemente einer Menge E zu den Elementen einer Menge A, wobei jedem Element aus E höchstens ein Element aus A, verschiedenen Elementen aus E aber dasselbe aus A zugeordnet werden darf. Gibt es in der Definitionsmenge, oder dem Urbildbereich, E zu jedem Element ein Element aus der Wertemenge, oder dem Bildbereich, A, heißt diese Abbildung totale Funktion, ansonsten partielle Funktion, bei der diese Zuordnung "nicht definiert" ist. Die Elemente der Mengen können wiederum Funktionen sein. Wenn eine Funktion in ein Programm überführt wird, was durch eine Abbildung der Funktion auf eine Turingmaschine stets möglich ist, berechnet die Maschine die Funktion und der Bildbereich entspricht der Ausgabe, also den Zeichen auf dem Band nach der Bearbeitung. Anstatt eine solche Maschine tatsächlich zu bauen, genügt es eine virtuelle, gedanklich konstruierte Maschine mit ihrem Anweisungsvorrat und Speicher anzunehmen. Ein Programm besteht dann aus einer Folge von Anweisungen, möglichen Auswahlen und Wiederholungen. Neben diesen Kontrollstrukturen, die ausreichen einen Algorithmus zu beschreiben, werden zur Vereinfachung Programme, die mehrfach Anwendung finden, in Module zusammengefaßt. Diese Prozeduren oder Unterprogramme können dann als Anweisungen in anderen Programmen oder in der Prozedur selbst, als sogenannte Rekursion, benutzt werden. Programme werden in einer künstlichen Sprache ausgedrückt, die nach festen Regeln der Syntax und Grammatik Worte und Sätze, oder Zeichen und Worte, bildet. Deren Semantik, und damit die Bedeutung der Ausdrücke, müssen wohl-definiert sein. Mathematische Kalküle, die eine Formalisierung der Logik darstellen, gehören ebenfalls zu den künstlichen Sprachen, die, wenn sie sich auf einer Maschine ausführen lassen, Programmiersprachen heißen. Ein Algorithmus definiert somit die Abstraktion eines in einer Programmiersprache beschriebenen Programms, einer Funktion oder einer Turingmaschine, da diese austauschbare Konkretisierungen verkörpern. Die heutzutage verfügbaren Rechenanlagen entsprechen ebenfalls, wegen ihrer von Neumann Architektur, die sich auf eine Turingmaschine reduzieren läßt, einer Algorithmisierung von Problemstellungen. Im Umkehrschluß bedeutet die dargestellte Äquivalenz, daß alles, was mit einem Computer berechenbar ist, einen Algorithmus definiert. Eine weitere Eigenschaft von wesentlicher praktischer Bedeutung ist die Feststellung der erfolgreichen Problemlösung durch einen Algorithmus. Turing verlangt für seine Maschine, daß diese nach endlich vielen Schritten anhält, d.h in einen Zustand übergeht, der die weitere Verarbeitung unterbricht. Ein Algorithmus soll terminieren. Eine Turingmaschine läßt sich durch einen Text eindeutig beschreiben, der die Übergangsfunktion der Zustände hintereinander angibt, und durch eine Turingmaschine simulieren. Es könnte also eine Algorithmus konstruiert werden, der bei Eingabe des Textes einer Turingmaschine feststellt, ob diese nach endlich vielen Schritten anhält, und die Entscheidung ausgibt. Desweiteren ließe sich eine Maschine bauen, die eine Ausgabe aufgrund der Entscheidung, daß die Textmaschine nicht stoppt, produziert und anhält oder, im Fall, die Textmaschine hält an, endlos weiterarbeitet. Unter Verwendung des Textes der letzten Maschine als Eingabe ihrerselbst, ergibt sich, daß sie nur dann anhält, wenn sie nicht anhält. Dieser Widerspruch beweist, daß es eine Maschine, die feststellt, ob jede Turingmaschine anhält oder nicht, nicht geben kann. Somit ist dieses sogenannte Halteproblem algorithmisch nicht lösbar, weil es keinen Algorithmus gibt, der entscheidet, ob alle Algorithmen terminieren.

In der Algorithmustheorie gibt es weitere Fragestellungen, die ebenfalls nicht entscheidbar sind, wie das Äquivalenzproblem, bei dem entschieden werden soll, ob zwei Programme die gleiche Aufgabe erfüllen, oder das Totalitätsproblem, das die Frage nach einer Funktion stellt, die berechnet, ob eine Funktion total ist. Die Beweise für die Nicht-Berechenbarkeit oder die Nicht-Entscheidbarkeit solcher Probleme lassen sich auf den Beweis des Halteproblems zurückführen. Lassen sich Probleme algorithmisieren, etwa durch die Klasse der µ-rekursiven Funktionen, die als berechenbar gilt, interessiert sich die Komplexitätstheorie der angewandten Informatik für die Auswirkungen, die eine Implementierung auf einem Computer hat. Die Komplexität eines Algorithmus ist ein Maß für den Bedarf an Betriebsmitteln, vorallem an Zeit und Speicher. Die Laufzeit eines Algorithmus wird angegeben, indem die zur Bearbeitung erforderlichen Schritte proportional zur Zahl n der Eingaben ermittelt wird. Aus Gründen der oft schwierigen Durchführbarkeit der exakten Berechnung werden das asymptotische Verhalten, die höchste vorkommende Potenz in einem Polynom, betrachtet und konstante Faktoren in der sogenannten Ordnung weggelassen. Ist n die Basis zu einem Exponenten, gehört sie zur Klasse P oder NP der berechenbaren Probleme, wenn n Exponent zur Basis 2 ist, zu denen exponentiell wachsender Ordnung, die, außer bei sehr kleinen Eingabemengen, als undurchführbar gelten. Die Probleme der Klasse P erfordern einen polynomialen Zeitaufwand und gelten bei praktisch auftretenden Eingabemengen als durchführbar. Die lineare Ordnung O(n) ist die Mindestlaufzeit auf sequentiellen Rechnern. Die Unterscheidung in P und NP Probleme betrifft den Determinismus von Algorithmen. In deterministischen Algorithmen ist in jeder Programmsituation der Folgeschritt eindeutig bestimmt, nicht-deterministische erlauben eine Auswahl aus mehreren Alternativen. Nicht-deterministisch polynomiale Probleme lassen sich unter Umständen in Linearzeit lösen und haben die Eigenschaft, daß für Fragestellungen, zu denen kein durchführbarer Algorithmus bekannt ist, eine gefundenen Lösung in polynomialer Laufzeit verifiziert werden kann.

Mit P bzw. NP werden häufig die entscheidbaren Mengen von Sprachen bezeichnet, die ein Algorithmus akzeptiert. Eine Menge M heißt entscheidbar, wenn für jedes Element in M entschieden werden kann, ob es in einer Teilmenge N von M liegt oder nicht. Die Menge M entsteht aus dem kartesischen Produkt über einem Alphabet A. Der Zeichenvorrat A ist eine geordnete, nichtleere Menge von Zeichen. Die Teilmengen von M, zu denen auch die leere Menge gehört, sind dessen Wörter und stellen Relationen zwischen den Zeichen des Alphabets her. Diese geordneten Tupel können auf zweistellige Relationen reduziert werden, kommen dann auf der linken Seite der Paare der Relationenmenge Zeichen des Alphabets höchstens einmal vor, spricht man von einer Funktion. Grammatiken, wie sie auf Chomsky(*1936) zurückgehend genannt werden, legen die Regeln zur Ableitung neuer Wörter einer formalen Sprache fest. Das Alphabet wird in eine Menge Terminalzeichen und eine Menge Superzeichen oder Axiome aufgeteilt, die disjunkt sein müssen. Das Produktionsystem der Sprache oder Menge benötigt ein vorgegebenes Terminal, das Startterminal, und Ableitungsregeln, die angeben, wie Superzeichen durch Terminale oder Superzeichen ersetzt werden. Finden die benachbarten Zeichen bei der Ersetzung der Axiome keine Beachtung, handelt es sich um eine kontextfreie, ansonsten um eine kontextsensitive Grammatik. Zur Interpretation einer formalen Sprache, deren Grammatik zum einen die Syntax bestimmt, bedarf es einer Metasprache, die zum anderen die Semantik der Aussageformen festlegt. Aussageformen unterscheiden sich von Aussagen dadurch, daß ihnen innerhalb der Sprache keine Wahrheit, sondern ein Wahrheitswert zugeordnet wird, dessen Wahrheit bzw. Existenz erst in der Metasprache ausgedrückt werden kann. Für logische Kalküle, die eine kontextfreie Grammatik haben, konnte Gödel die Widerspruchsfreiheit und Vollständigkeit zeigen, während für die mächtigeren mathematischen Kalküle auf die Vollständigkeit zugunsten der Widerspruchsfreiheit verzichtet werden muß. Dies liegt an einem nötigen Metakalkül zur Festlegung der Semantik, der nicht die Ableitung aller wahren Aussagen ermöglicht, und das System somit unvollständig bleibt. Gödel konnte ebenfalls beweisen, daß es einen “"Meta...Metakalkül", der vollständig ist, nicht geben kann, da es keine Menge aller Mengen gibt. Die Mathematik und Physik muß sich daher mit Kalkülen begnügen, die mächtig und ausdrucksstark genug sind, Aussagen machen zu können. Das führt mit unter zu Sprachen, bei denen nicht einmal die Widerspruchsfreiheit bewiesen werden kann. Die Entscheidbarkeit einer Sprache oder Menge M, die neben Vollständigkeit und Widerspruchsfreiheit charakteristisch ist, bezieht sich dabei auf die Frage, ob ein beliebiges Wort oder Element relativ zu M zu einer bestimmten Teilmenge N gehört oder nicht. Es bedarf dazu einer Funktion, die dies bestimmt, indem sie entweder die Zugehörigkeit zu N oder zu der Differenzmenge von M und N nachweist. Diese Funktion heißt charakteristisch für M und muß berechenbar sein, d.h. es muß einen Algorithmus geben, der terminiert. Die Sprachen der kontextfreien Grammatiken sind nicht entscheidbar, der Beweis kann über das Halteproblem geleistet werden, wohingegen die der kontextsensitive Grammatiken, zu denen Programmiersprachen zählen, entscheidbar sind. Programmiersprachen werden durch Superzeichen und Terminalsymbole auf abstraktem Niveau beschrieben. Dazu gehören Kontrollstrukturen, wie Sequenz, Selektion und Iteration und Datenstrukturen, die die Identifikation der symbolischen Daten durch Benennen oder Zeigen erlauben. Aus den Kalkülen der Logik entstanden zwei Formen an deklarativen, also das zu verarbeitende "Was", statt des “"Wie" bestimmende Programmiersprachen: einerseits die logische Programmierung, die auf dem Prädikatenkalkül basiert, und andererseits die funktionale, die auf dem von Church entwickelten Lambda-Kalkül fußt. Neben diesen beiden, die Rekursion verwenden, um die Iteration zu ersetzen, existieren die imperativen Sprachen, auf die zur Programmierung auch die deklarativen zurückgr

Modell & Metapher