Social Media Teil 2
Computerprogramm
aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Computerprogramm)
Ein Computerprogramm oder kurz Programm ist eine Folge von den Regeln der jeweiligen Programmiersprache genügenden Anweisungen, die auf einem Computer ausgeführt werden können, um damit eine bestimmte Funktionalität zur Verfügung zu stellen. [1]
Überblick
Ein Computerprogramm liegt zumeist auf einem Datenträger als ausführbare Programmdatei im sogenannten Maschinencode vor und wird zur Ausführung in den Arbeitsspeicher des Rechners geladen. Das Programm wird als Abfolge von Maschinen-, d.h. Prozessorbefehlen von dem/den Prozessoren des Computers verarbeitet und damit ausgeführt.
Eine Programmdatei, die aus Maschinencode besteht, enthält Befehle aus dem Sprachschatz des Prozessors, d. h. Befehle, die für den Prozessor „verständlich“ und damit ausführbar sind. Die Erstellung eines solchen Programms bezeichnet man allgemein als Programmierung oder auch als Implementierung. In den Anfängen der Programmierung wurde – bis zur Entwicklung von Programmiersprachen – ausschließlich in Maschinencode programmiert. Der Programm- bzw. Quelltext, den der Programmierer in einer Programmiersprache abgefasst hat, besteht aus einer Abfolge von (zumeist der englischen Sprache entnommenen) Befehlen, die für den Programmierer (i. A.) verständlicher sind als der Maschinencode (z. B.: ADD, SUB, AND, OR etc). Später ergänzten die höheren Programmiersprachen Schleifen, Abstraktion und modularen Aufbau.
Sowohl der Quelltext als auch der von einem Computer ausführbare Maschinencode werden als Programm bezeichnet. Meist ist eine Quelltextdatei durch eine Dateiendung gekennzeichnet, die auf die verwendete Hochsprache hinweist (programm.c: ein in C formuliertes Programm). Sie kann im Allgemeinen mit einem einfachen Texteditor bearbeitet werden. Eine Datei, die dagegen Maschinencode enthält, besitzt keine oder eine betriebssystemspezifische Endung, die lediglich auf ihre Ausführbarkeit hinweist (programm.exe bei MS-DOS und Windows; programm bei unixoiden Systemen). Sie kann oft als Kommando in einem Terminal (Eingabeaufforderung) aufgerufen werden.
Damit ein in einer Hochsprache geschriebenes Programm auf einem Prozessor ausgeführt werden kann, muss es in Maschinencode übersetzt werden. Ein Befehl einer höheren Programmiersprache wird im Allgemeinen in mehrere Maschinenbefehle übersetzt. Den Übersetzungsvorgang nennt man Compilierung. Um aus dem Quelltext den Maschinencode zu generieren, wird ein Assembler, Compiler oder Interpreter benötigt. Dieser übersetzt die Befehle der Programmiersprache, die für menschliche Benutzer verständlich und bearbeitbar sein sollen, in die semantisch entsprechenden Befehle der Maschinensprache des verwendeten Computers.
Die Anweisungen, die (als Teil von Programmen) einen konkreten Lösungsweg repräsentieren, werden als Algorithmus bezeichnet; Beispiel: Berechnen der Mehrwertsteuer.
Im Sprachgebrauch wird Computerprogramm meist zu Programm verkürzt oder der Begriff Software verwendet. Allerdings ist Computerprogramm kein Synonym zu Software, da mit Software die komplette, für den Benutzer fertige Anwendung gemeint ist. Diese umfasst zusätzliche Ressourcen wie Betriebssystem, Datenbanken, Grafik- und Audiodateien, Schriftarten oder Hilfetexte.
Ein größeres Computerprogramm besteht meist aus mehreren Modulen – die entweder zum Programm selbst ‘gehören’ oder die als ‘Bausteine’ aus bereits bestehenden Programmbibliotheken bei der Ausführung des Programms benutzt werden.
Die Entwicklung von Computerprogrammen ist das Gebiet der Softwaretechnik. Je nach Komplexität der zu entwickelnden Computerprogramme werden dazu verschiedene Vorgehensmodelle verwendet.
Geschichte
Das erste Computerprogramm von Ada Lovelace
Als weltweit erstes Computerprogramm gilt eine Vorschrift für die Berechnung von Bernoulli-Zahlen, die Ada Lovelace in den Jahren 1842/1843 für die mechanische Analytical Engine von Charles Babbage erstellte. Das Programm konnte seinerzeit nur von Hand ausgeführt werden, da es im 19. Jahrhundert noch keine funktionsfähige Maschine gab, die dazu in der Lage war.
Erste Programme auf Lochstreifen
In den Jahren 1936 bis 1941 entwarf Konrad Zuse die Rechner Z1 und Z3, die lange Befehlsfolgen auf einem Lochstreifen verarbeiteten, die ersten Computerprogramme, die auf realen Maschinen ausgeführt werden konnten. Die Rechner beherrschten die vier Grundrechenarten und Quadratwurzelberechnungen auf binären Gleitkommazahlen, der Lochstreifen enthielt jeweils eine Rechenoperation und eine Speicheradresse.
Auf Zuse geht auch die erste höhere Programmiersprache Plankalkül, zurück. Damit lassen sich Probleme maschinenunabhängig formulieren und später in eine maschinenlesbare Form überführen.
Programme im Arbeitsspeicher
Der EDVAC-Rechner, der auf einem Entwurf von John von Neumann aus dem Jahre 1945 basiert, hatte einen Quecksilber-Verzögerungsspeicher für 1024 Fest- oder Gleitkommazahlen mit jeweils 44 Bit. Jede Speicherzelle konnte statt einer Zahl auch einen Befehl aufnehmen. Bei diesem Rechnerkonzept war es möglich, die Befehle eines Computerprogramms vor der Ausführung zuerst in den Arbeitsspeicher zu übertragen. Das ist heute noch üblich. EDVAC wurde jedoch erst im Jahr 1951 teilweise fertiggestellt. Der Demonstrationsrechner Manchester SSE und der auf dem EDVAC aufbauende EDSAC-Rechner hatten schon vorher Programme aus dem Arbeitsspeicher ausgeführt.
Höhere Programmiersprachen und Compiler
Ende der 1950er Jahre wurden Computer so leistungsfähig, dass spezielle Programme, Compiler genannt, Quelltexte in höheren Programmiersprachen automatisch in Maschinenbefehle, also ausführbare Programme, übersetzen konnten. Ausführbare Programme können dann, wie beim EDVAC, in den Speicher geladen und abgearbeitet werden.
Mit Fortran, COBOL, ALGOL und LISP entstanden in den späten 1950er Jahren die ersten standardisierten höheren Programmiersprachen. Programme in diesen Sprachen laufen durch einen entsprechenden Compiler übersetzt auf unterschiedlichen Rechnern. Sie können teilweise auch noch auf modernen Computern eingesetzt werden.
Vom Algorithmus zum Programm
Berechnung des größten gemeinsamen Teilers
Es soll ein Programm zur Bestimmung des größten gemeinsamen Teilers (ggT) zweier Zahlen erstellt werden. Zunächst muss ein geeigneter Algorithmus gefunden werden.
Der euklidische Algorithmus, der bereits um 300 v. Chr. beschrieben wurde, ermittelt den größten gemeinsamen Teiler (ggT) zweier natürlicher Zahlen A und B:
- Sei A die größere der beiden Zahlen A und B (gegebenenfalls vertauschen).
- Setze A = A – B.
- Wenn A und B ungleich sind, dann mit Schritt 1 fortfahren, wenn sie gleich sind, dann den Algorithmus beenden: Diese Zahl ist der größte gemeinsame Teiler.
Verwendung einer Programmiersprache
Sobald eine formale Beschreibung eines Algorithmus, also eine genau definierte Verarbeitungsvorschrift, vorliegt, kann der Algorithmus umgesetzt (implementiert) werden. Dazu wird eine geeignete Programmiersprache ausgewählt.
Zur Umsetzung wird heute meist eine höhere Programmiersprache verwendet, die von einem Computer eventuell nicht direkt ausgeführt werden kann, sondern zuerst compiliert oder interpretiert werden muss. In Sprachen wie Pascal dienen Variablen, Ausdrücke, Vergleiche, Zuweisungen und Kontrollstrukturen zur Umsetzung des ggT-Algorithmus:
(* Schritt3: *)
WHILE A <> B DO (* Solange A ungleich B *)
BEGIN
(* Schritt1: *)
IF B > A THEN (* Falls B größer als A *)
BEGIN
H = A; A = B; B = H; (* A und B vertauschen *)
END;
(* Schritt2: *)
A = A-B; (* A durch A-B ersetzen *)
END;
Berücksichtigung aller Sonderfälle
Bei der Umsetzung wird mit der Prüfung von Schritt 3 begonnen. Der ursprüngliche Algorithmus berücksichtigt nicht den Fall, dass A und B bereits zu Beginn gleich sein können. Wäre die Aufgabe, den größten Teiler von 103 und 103 zu finden, würde ein Mensch sofort das Ergebnis 103 nennen, er würde den Algorithmus gar nicht bemühen. Der originale Algorithmus würde aber null ergeben. Die Umsetzung auf einem Rechner muss auch alle Sonderfälle berücksichtigen. Durch das Vorziehen von Schritt 3 wird der Sonderfall hier korrekt behandelt.
Elementare Schritte
Pascal und andere Programmiersprachen besitzen keine Operation zum Vertauschen von Zahlen. Das muss daher in elementarere Schritte umgesetzt werden. Eine zusätzliche Variable H, eine sogenannte Hilfsvariable, erlaubt die Vertauschung mit Hilfe von drei Zuweisungen:
H := A; (* Wert von A in der Hilfsvariablen H retten *)
A := B; (* A mit dem Wert von B überschreiben *)
B := H; (* B mit dem Wert von H (=A) überschreiben *)
Das ist auch ein kleiner Algorithmus.
Ein vollständiges Programm
Damit daraus ein korrektes Programm wird, muss der Algorithmus noch um Ein- bzw. Ausgabeanweisungen, oft jedoch auch um Variablen und eine Programmstruktur ergänzt werden. Diese sind nicht Teil des eigentlichen Algorithmus:
PROGRAM Ggt(Input,Output); (* Programmkopf *)
VAR A,B,H: Integer; (* Variablendefinition *)
BEGIN
ReadLn(A,B); (* Eingabe von A und B *)
WHILE A <> B DO (* Euklidischer Algorithmus *)
BEGIN
IF B > A THEN
BEGIN
H := A; A := B; B := H;
END;
A := A-B;
END;
WriteLn(A) (* Ausgabe von A *)
END. (* Programmende *)
Übersetzung und Ausführung
Erst dieses Programm kann mit einem Texteditor in eine Datei geschrieben werden, die dann übersetzt und ausgeführt werden kann. Dazu ist ein Compiler erforderlich, der den Code in der Programmiersprache in Maschinensprache übersetzt und das Ergebnis in eine ausführbare Datei schreibt. Diese kann dann über ein Betriebssystem gestartet werden. Das Programm muss dabei nur einmal übersetzt werden. Es kann danach beliebig oft gestartet werden.
Einige Programmiersprachen verwenden keinen Compiler, sondern einen Interpreter, der Programme erst zur Laufzeit in Maschinensprache übersetzt.
Eine weitere Möglichkeit besteht in der Verwendung von Zwischencode (Bytecode), der vom Compiler an Stelle des Maschinencodes generiert wird. Ein Beispiel dafür ist Java: Der Java-Compiler erzeugt Bytecode, welcher dann auf der sogenannten virtuellen Maschine ausgeführt wird. Die virtuelle Maschine interpretiert oder übersetzt dann den Bytecode für das darunterliegende Betriebssystem.
Mittels spezieller Programme, sogenannter Decompiler, ist es in begrenztem Maße möglich, aus dem Maschinencode wieder einen in Hochsprache lesbaren Quelltext zu erzeugen.
Informatik
aus Wikipedia, der freien Enzyklopädie
Informatik ist die Wissenschaft von der systematischen Verarbeitung von Informationen, insbesondere der automatischen Verarbeitung mit Hilfe von Rechenanlagen. Historisch hat sich die Informatik einerseits aus der Mathematik entwickelt, andererseits durch die Entwicklung von Rechenanlagen aus der Elektrotechnik und der Nachrichtentechnik.
Geschichte und Entwicklung
Ursprung der Informatik als Wissenschaft
Die Wurzeln der Informatik liegen in der Mathematik, der Physik und der Elektrotechnik (hier vor allem der Nachrichtentechnik).
Bereits Leibniz hatte sich mit binären Zahlendarstellungen beschäftigt. Gemeinsam mit der Booleschen Algebra, die zuerst 1847 von George Boole ausgearbeitet wurde, bilden sie die wichtigsten mathematischen Grundlagen späterer Rechensysteme. 1937 veröffentlicht Alan Turing seine Arbeit On Computable Numbers with an application to the Entscheidungsproblem, in welcher die nach ihm benannte Turingmaschine vorgestellt wird, ein mathematisches Maschinenmodell, das bis heute für die Theoretische Informatik von größter Bedeutung ist. Dem Begriff der Berechenbarkeit liegen bis heute universelle Modelle wie die Turing- oder Registermaschine zu Grunde, und auch die Komplexitätstheorie, die sich ab den 1960er Jahren zu entwickeln begann, greift bis in die Gegenwart auf Varianten dieser Modelle zurück.
Entwicklung der Informatik als Wissenschaft
Nach einem internationalen Kolloquium in Dresden am 26. Februar 1968 setzte sich „Informatik“ als Bezeichnung für die Wissenschaft nach französischem und russischem Vorbild auch im deutschen Sprachraum durch. Die Bezeichnung „Computerwissenschaften“ ist weniger gebräuchlich. Im Wintersemester 1969/70 begann die Universität Karlsruhe als erste deutsche Hochschule mit der Ausbildung von Diplom-Informatikern. Wenige Jahre darauf gründeten sich die ersten Fakultäten für Informatik, nachdem bereits seit 1962 an der Purdue University ein Department of Computer Science bestand.
Informatikbewegungen
Die Gesellschaft für Informatik (GI) wurde 1969 gegründet und ist die größte Fachvertretung im deutschsprachigen Raum. International bedeutend sind vor allem die beiden großen amerikanischen Vereinigungen Association for Computing Machinery (ACM) seit 1947 und das Institute of Electrical and Electronics Engineers (IEEE) seit 1963. In Deutschland genießt vor allem der Chaos Computer Club (Gründung 1981) hohe Bekanntheit.
Rechenmaschinen – Vorläufer des Computers
Als erste Vorläufer der Informatik jenseits der Mathematik, also als Vorläufer der angewandten Informatik, können die Bestrebungen angesehen werden, zwei Arten von Maschinen zu entwickeln: Solche, mit deren Hilfe mathematische Berechnungen ausgeführt oder vereinfacht werden können („Rechenmaschinen“), und solche, mit denen logische Schlüsse gezogen und Argumente überprüft werden können („Logische Maschinen“). Als einfache Rechengeräte leisten Abakus und später der Rechenschieber unschätzbare Dienste. 1641 konstruiert Blaise Pascal eine mechanische Rechenmaschine, die Additionen inklusive Überträgen durchführen kann. Nur wenig später stellt Gottfried Wilhelm Leibniz eine Rechenmaschine vor, die alle vier Grundrechenarten beherrscht. Diese Maschinen basieren auf ineinandergreifenden Zahnrädern. Einen Schritt in Richtung größerer Flexibilität geht ab 1838 Charles Babbage, der eine Steuerung der Rechenoperationen mittels Lochkarten anstrebt. Erst Herman Hollerith ist aufgrund der technischen Fortschritte ab 1886 in der Lage, diese Idee gewinnbringend umzusetzen. Seine auf Lochkarten basierenden Zählmaschinen kommen unter anderem bei der Auswertung einer Volkszählung in den USA zum Einsatz.
Die Geschichte der logischen Maschinen wird oft bis ins 13. Jahrhundert zurückverfolgt und auf Ramon Llull zurückgeführt. Auch wenn seine rechenscheibenähnlichen Konstruktionen, bei denen mehrere gegeneinander drehbare Scheiben unterschiedliche Begriffskombinationen darstellen konnten, mechanisch noch nicht sehr komplex waren, war er wohl derjenige, der die Idee einer logischen Maschine bekannt gemacht hat. Von diesem sehr frühen Vorläufer abgesehen verläuft die Geschichte logischer Maschinen eher sogar zeitversetzt zu jener der Rechenmaschinen: Auf 1777 datiert ein rechenschieberähnliches Gerät des dritten Earl Stanhope, dem zugeschrieben wird, die Gültigkeit von Syllogismen (im aristotelischen Sinn) zu prüfen. Eine richtige „Maschine“ ist erstmals in der Gestalt des „Logischen Pianos“ von Jevons für das späte 19. Jahrhundert überliefert. Nur wenig später wird die Mechanik durch elektromechanische und elektrische Schaltungen abgelöst. Ihren Höhepunkt erleben die logischen Maschinen in den 1940er und 1950er Jahren, zum Beispiel mit den Maschinen des englischen Herstellers Ferranti. Mit der Entwicklung universeller digitaler Computer nimmt – im Gegensatz zu den Rechenmaschinen – die Geschichte selbstständiger logischen Maschinen ein jähes Ende, indem die von ihnen bearbeiteten und gelösten Aufgaben zunehmend in Software auf genau jenen Computern realisiert werden, zu deren hardwaremäßigen Vorläufern sie zu zählen sind.
Entwicklung moderner Rechenmaschinen
Siehe hierzu auch den Abschnitt: Der Siegeszug des elektronischen Digitalrechners im Artikel Computer!
Eine der ersten größeren Rechenmaschinen ist die von Konrad Zuse erstellte, noch immer rein mechanisch arbeitende Z1 von 1937. Vier Jahre später realisiert Zuse seine Idee mittels elektrischer Relais: Die Z3 von 1941 verfügt als erster Computer bereits über eine Trennung von Befehls– und Datenspeicher und ein Ein-/Ausgabepult. Etwas später werden in England die Bemühungen zum Bau von Rechenmaschinen zum Knacken von deutschen Geheimbotschaften unter maßgeblicher Leitung von Alan Turing mit großem Erfolg vorangetrieben. Parallel entwickelte Howard Aiken mit Mark I (1944) den ersten Computer der USA, wo die weitere Entwicklung maßgeblich vorangetrieben wurde. Einer der Hauptakteure ist hier John von Neumann, nach dem die bis heute bedeutende Von-Neumann-Architektur benannt ist. 1946 erfolgt die Entwicklung des Röhrenrechners ENIAC, 1949 wird der EDSAC gebaut. Ab 1948 steigt IBM in die Entwicklung von Computern ein und steigt innerhalb von zehn Jahren zum Marktführer auf. Mit der Entwicklung der Transistortechnik und der Mikroprozessortechnik werden Computer von dieser Zeit an immer leistungsfähiger und preisgünstiger. Im Jahre 1982 öffnet die Firma Commodore schließlich mit dem C64 den Massenmarkt speziell für Heimanwender aber auch weit darüber hinaus.
Maschinensprachen
1956 beschreibt Noam Chomsky eine Hierarchie formaler Grammatiken, mit denen formale Sprachen und jeweils spezielle Maschinenmodelle korrespondieren. Diese Formalisierungen erlangen für die Entwicklung höherer Programmiersprachen große Bedeutung. Wichtige Meilensteine sind die Entwicklung von Fortran (erste höhere Programmiersprache, 1957), LISP (funktional, 1959), COBOL (Programmiersprache für kaufmännische Anwendungen, 1959), ALGOL (strukturiert/imperativ; 1960/1968), Smalltalk (objektorientiert, 1971), Prolog (logisch, 1972) und SQL (Relationale Datenbanken, 1976). Einige dieser Sprachen stehen für typische Programmierparadigmen ihrer jeweiligen Zeit. Weitere über lange Zeit in der Praxis eingesetzte Programmiersprachen sind BASIC (seit 1960), C (seit 1970), Pascal (seit 1971), C++ (objektorientiert, generisch, um 1990), Java (objektorientiert, seit 1995) und C# (objektorientiert, um 2000). Sprachen und Paradigmenwechsel wurden von der Informatik-Forschung intensiv begleitet oder vorangetrieben.
Indessen schreibt nahezu jeder wichtige Teilbereich der Informatik seine eigene Geschichte, die im Einzelnen zu verfolgen den Rahmen dieses Abschnitts sprengen würde. Wie in anderen Wissenschaften auch, schreitet die Informatik mit zunehmender Nähe zur Gegenwart in Richtung einer immer größeren Spezialisierung fort.
Disziplinen der Informatik
Die Teildisziplinen in der Informatik
Die Informatik unterteilt sich in die Teilgebiete der Theoretischen Informatik, der Praktischen Informatik und der Technischen Informatik.
Die Anwendungen der Informatik in den verschiedenen Bereichen des täglichen Lebens sowie in anderen Fachgebieten, wie beispielsweise der Wirtschaftsinformatik, Geoinformatik, Medizininformatik, werden unter dem Begriff der Angewandten Informatik geführt. Auch die Auswirkungen auf die Gesellschaft werden interdisziplinär untersucht.
Die theoretische Informatik bildet die theoretische Grundlage für die anderen Teilgebiete. Sie liefert fundamentale Erkenntnisse für die Entscheidbarkeit von Problemen, für die Einordnung ihrer Komplexität und für die Modellierung von Automaten und Formalen Sprachen.
Auf diese Erkenntnisse stützen sich Disziplinen der Praktischen und der Technischen Informatik. Sie beschäftigen sich mit zentralen Problemen der Informationsverarbeitung und suchen anwendbare Lösungen.
Die Resultate finden schließlich Verwendung in der Angewandten Informatik. Diesem Bereich sind Hardware- und Software-Realisierungen zuzurechnen und damit ein Großteil des kommerziellen IT-Marktes. In den interdisziplinären Fächern wird darüber hinaus untersucht, wie die Informationstechnik Probleme in anderen Wissenschaftsgebieten lösen kann. Als Beispiel mag hier die Entwicklung von Geodatenbanken für die Geographie dienen, aber auch die Wirtschafts- oder Bioinformatik.
Theoretische Informatik
Die Theoretische Informatik beschäftigt sich mit der Theorie formaler Sprachen bzw. Automatentheorie, Berechenbarkeits- und Komplexitätstheorie, Graphentheorie, Kryptologie, Logik (u. a. Aussagenlogik und Prädikatenlogik), formaler Semantik und bietet Grundlagen für den Bau von Compilern von Programmiersprachen und die mathematische Formalisierung von Problemstellungen.
Automaten sind in der Informatik „gedachte Maschinen“, die sich nach bestimmten Regeln verhalten. Ein endlicher Automat hat eine endliche Menge von inneren Zuständen. Er liest ein „Eingabewort“ zeichenweise ein und führt bei jedem Zeichen einen Zustandsübergang durch. Zusätzlich kann er bei jedem Zustandsübergang ein „Ausgabesymbol“ ausgeben. Nach Ende der Eingabe kann der Automat das Eingabewort akzeptieren oder ablehnen.
Formale Sprachen eignen sich unter anderem zur Beschreibung von Programmiersprachen. Formale Sprachen lassen sich aber auch durch Automatenmodelle beschreiben, da die Menge aller von einem Automaten akzeptierten Wörter als formale Sprache betrachtet werden kann.
Kompliziertere Modelle, verfügen über einen Speicher, zum Beispiel Kellerautomaten oder die Turingmaschine, welche gemäß der Church-Turing-These alle durch Menschen berechenbaren Funktionen nachbilden kann.
Berechenbarkeitstheorie
Im Rahmen der Berechenbarkeitstheorie untersucht die theoretische Informatik, welche Probleme mit welchen Maschinen lösbar sind. Ein Rechnermodell oder eine Programmiersprache heißt turing-vollständig, wenn damit eine universelle Turingmaschine simuliert werden kann. Alle heute eingesetzten Computer und die meisten Programmiersprachen sind turing-vollständig, das heißt man kann damit dieselben Aufgaben lösen. Auch alternative Berechnungsmodelle wie der Lambda-Kalkül, WHILE-Programme, μ-rekursive Funktionen oder Registermaschinen stellten sich als turing-vollständig heraus. Aus diesen Erkenntnissen entwickelte sich die Church-Turing-These, die zwar formal nicht beweisbar ist, jedoch allgemein akzeptiert wird.
Den Begriff der Entscheidbarkeit kann man veranschaulichen als die Frage, ob ein bestimmtes Problem algorithmisch lösbar ist. Ein entscheidbares Problem ist zum Beispiel die Eigenschaft eines Texts, ein syntaktisch korrektes Programm zu sein. Ein nicht-entscheidbares Problem ist zum Beispiel die Frage, ob ein gegebenes Programm mit gegebenen Eingabeparametern jemals zu einem Ergebnis kommt, was als Halteproblem bezeichnet wird.
Komplexitätstheorie
Die Komplexitätstheorie befasst sich mit dem Ressourcenbedarf von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen, sowie der Güte der sie lösenden Algorithmen. Insbesondere werden die Ressourcen „Laufzeit“ und „Speicherplatz“ untersucht und ihr Bedarf wird üblicherweise in der Landau-Notation dargestellt. In erster Linie werden die Laufzeit und der Speicherplatzbedarf in Abhängigkeit von der Länge der Eingabe notiert. Algorithmen, die sich höchstens durch einen konstanten Faktor in ihrer Laufzeit bzw. ihrem Speicherbedarf unterscheiden, werden durch die Landau-Notation der gleichen Klasse, d.h. einer Menge von Problemen mit äquivalenter vom Algorithmus für die Lösung benötigter Laufzeit, zugeordnet.
Ein Algorithmus, dessen Laufzeit von der Eingabelänge unabhängig ist, arbeitet „in konstanter Zeit“, man schreibt . Beispielsweise wird das Programm „gib das erste Element einer Liste zurück“ in konstanter Zeit arbeiten. Das Programm „prüfe, ob ein bestimmtes Element in einer unsortierten Liste der Länge n enthalten ist“ braucht „lineare Zeit“, also , denn die Eingabeliste muss schlimmstenfalls genau einmal komplett gelesen werden.
Die Komplexitätstheorie liefert bisher fast nur obere Schranken für den Ressourcenbedarf von Problemen, denn Methoden für exakte untere Schranken sind kaum entwickelt und nur von wenigen Problemen bekannt (so zum Beispiel für die Aufgabe, eine Liste von Werten mit Hilfe einer gegebenen Ordnungsrelation durch Vergleiche zu sortieren, die untere Schranke Ω(nlog(n))). Dennoch gibt es Methoden besonders schwierige Probleme als solche zu klassifizieren, wobei die Theorie der NP-Vollständigkeit eine zentrale Rolle spielt. Demnach ist ein Problem besonders schwierig, wenn man durch dessen Lösung auch automatisch die meisten anderen natürlichen Probleme lösen kann, ohne dafür wesentlich mehr Ressourcen zu verwenden.
Die größte offene Frage in der Komplexitätstheorie ist die Frage, ob P gleich NP ist. Das Problem ist eines der Millennium-Probleme, die vom Clay Mathematics Institute mit einer Million US Dollar ausgeschrieben sind. Wenn P nicht gleich NP ist, können NP-vollständige Probleme nicht effizient gelöst werden können. Ein NP-vollständiges Problem ist zum Beispiel das Finden von Beweisen.
Praktische Informatik
Die Praktische Informatik beschäftigt sich mit der Lösung von konkreten Problemen deren Umsetzung (Implementierung) in Form von Computerprogrammen. Sie liefert auch die grundlegenden Konzepte zur Lösung von Standardaufgaben, wie die Speicherung und Verwaltung der Informationen mittels Datenstrukturen. Einen wichtigen Stellenwert haben dabei die Algorithmen, die Musterlösungen für häufige oder schwierige Aufgaben bereitstellen. Beispiele dafür sind die Sortieralgorithmen und die schnelle Fourier-Transformation.
Eines der zentralen Themen der praktischen Informatik ist die Softwaretechnik. Sie beschäftigt sich mit der systematischen Erstellung von Software. Es werden auch Konzepte und Lösungsvorschläge für große Softwareprojekte entwickelt, die einen wiederholbaren Prozess von der Idee bis zur fertigen Software erlauben sollen.
Die Praktische Informatik stellt auch die Werkzeuge zur Softwareentwicklung bereit. So werden Compiler für die Programmiersprachen wie Visual Basic, Java, Delphi oder C++ entwickelt. Compiler sind selbst Computerprogramme, die eine Computersprache in eine andere übersetzen. Sie erlauben es also einem Programmierer in einer für Menschen leichter verständlichen Sprache zu arbeiten. Ein Compiler übersetzt das Programm später in Maschinencode, der sehr „natürlichen“ Sprache des Computers.
Nur durch die Grundlage der formaler Sprachen wurde die effiziente Entwicklung von Compilern möglich. Übersetzer werden auch an vielen anderen Stellen in der Informatik verwendet. Zum Beispiel beim Übersetzen von HTML-Code in ein gut lesbares Dokument.
Ein Beispiel für den Einsatz von Datenstrukturen ist der B-Baum, der in Datenbanken und Dateisystemen das schnelle Suchen in großen Datenbeständen erlaubt.
Technische Informatik
Die Technische Informatik befasst sich mit den hardwareseitigen Grundlagen der Informatik wie etwa der Mikroprozessortechnik, Rechnerarchitekturen und verteilten Systemen. Damit stellt sie ein Bindeglied zur Elektrotechnik dar.
Die Rechnerarchitektur ist die Wissenschaft, die Konzepte für den Bau von Computern erforscht. Hier wird das Zusammenspiel von Mikroprozessor, Arbeitsspeicher sowie Controller und Peripherie definiert und verbessert. Das Forschungsgebiet orientiert sich dabei sowohl an den Anforderungen der Software als auch an den Möglichkeiten, die sich über die Weiterentwicklung von Integrierten Schaltkreisen ergeben.
Ein weiteres wichtiges Gebiet ist die Rechnerkommunikation. Diese ermöglicht den elektronischen Datenaustausch zwischen Computern und stellt damit die technische Grundlage des Internets dar. Neben der Entwicklung von Routern, Switches oder einer Firewall, gehört auch die Entwicklung der Softwarekomponenten, die zum Betrieb dieser Geräte nötig ist, zur Rechnerkommunikation. Insbesondere gehört die Definition und Standardisierung der Netzwerkprotokolle, wie TCP, HTTP oder SOAP zur Rechnerkommunikation. Die Protokolle sind dabei die Sprachen, in denen Computer miteinander „reden“.
Während die Rechnerkommunikation die Kommunikation auf Protokollebene regelt, stellt die Wissenschaft der Verteilten Systeme, den Zusammenschluss von Computern im Großen dar. Hier regeln Prozesse die Zusammenarbeit von einzelnen Systemen in einem Verbund (Cluster). Schlagworte in diesem Zusammenhang sind beispielsweise Grid-Computing und Middleware.
Informatik in interdisziplinären Wissenschaften
Rund um die Informatik haben sich einige interdisziplinäre Forschungsansätze, teilweise zu eigenen Wissenschaften, entwickelt:
Ingenieurinformatik, Maschinenbauinformatik
Die Ingenieurinformatik, englisch auch als Computational Engineering Science bezeichnet, ist eine interdisziplinäre Lehre an der Schnittstelle zwischen den Ingenieurwissenschaften, der Mathematik und der Informatik an den Fachbereichen Elektrotechnik, Maschinenbau, Verfahrenstechnik, Systemtechnik.
Die Maschinenbauinformatik beinhaltet im Kern die virtuelle Produktentwicklung (Produktionsinformatik) mittels Computervisualistik, sowie die Automatisierungstechnik.
Wirtschaftsinformatik, Informationsmanagement
Die Wirtschaftsinformatik (englisch (business) information systems, auch management information systems) ist eine „Schnittstellen-Disziplin“ zwischen der Informatik und den Wirtschaftswissenschaften, besonders der Betriebswirtschaftslehre. Sie hat sich durch ihre Schnittstellen zu einer eigenständigen Wissenschaft entwickelt. Ein Schwerpunkt der Wirtschaftsinformatik liegt auf der Abbildung von Geschäftsprozessen und der Buchhaltung in relationalen Datenbanksystemen und Enterprise-Resource-Planning-Systemen. Das Information Engineering der Informationssysteme und das Informationsmanagement spielen im Rahmen der Wirtschaftsinformatik eine gewichtige Rolle.
Medieninformatik
Die Medieninformatik hat die Schnittstelle zwischen Mensch und Maschine als Schwerpunkt und befasst sich mit der Verbindung von Informatik, Psychologie, Arbeitswissenschaft, Medientechnik, Mediengestaltung und Didaktik.
Computerlinguistik
In der Computerlinguistik wird untersucht, wie natürliche Sprache mit dem Computer verarbeitet werden kann. Sie ist ein Teilbereich der Künstlichen Intelligenz, aber auch gleichzeitig Schnittstelle zwischen Angewandter Linguistik und Angewandter Informatik. Verwandt dazu ist auch der Begriff der Kognitionswissenschaft, die einen eigenen interdisziplinären Wissenschaftszweig darstellt, der u. a. Linguistik, Informatik, Philosophie, Psychologie und Neurologie verbindet. Anwendungsgebiete der Computerlinguistik sind die Spracherkennung und -synthese, automatische Übersetzung in andere Sprachen und Informationsextraktion aus Texten.
Umweltinformatik, Geoinformatik
Die Umweltinformatik beschäftigt sich interdisziplinär mit der Analyse und Bewertung von Umweltsachverhalten mit Mitteln der Informatik. Schwerpunkte sind die Verwendung von Simulationsprogrammen, Geographische Informationssysteme (GIS) und Datenbanksysteme.
Die Geoinformatik (englisch geoinformatics) ist die Lehre des Wesen und der Funktion der Geoinformation und ihrer Bereitstellung in Form von Geodaten und mit den darauf aufbauenden Anwendungen auseinander. Sie bildet die wissenschaftliche Grundlage für Geoinformationssysteme (GIS). Allen Anwendungen der Geoinformatik gemeinsam ist der Raumbezug und fallweise dessen Abbildung in kartesische räumliche oder planare Darstellungen.
Bioinformatik, Biodiversitätsinformatik
Die Bioinformatik (englisch bioinformatics, auch computational biology) befasst sich mit den informatischen Grundlagen und Anwendungen der Speicherung, Organisation und Analyse von biologischen Daten. Die ersten reinen Bioinformatikanwendungen wurden für die DNA-Sequenzanalyse entwickelt. Dabei geht es primär um das schnelle Auffinden von Mustern in langen DNA-Sequenzen und die Lösung des Problems, wie man zwei oder mehr ähnliche Sequenzen so übereinander legt und gegeneinander ausrichtet, dass man eine möglichst optimale Übereinstimmung erzielt (sequence alignment). Mit der Aufklärung und weitreichenden Funktionsanalyse verschiedener vollständiger Genome (z. B. des Fadenwurms Caenorhabditis elegans) verlagert sich der Schwerpunkt bioinformatischer Arbeit auf Fragestellungen der Proteomik, wie z. B. dem Problem der Proteinfaltung und Strukturvorhersage, also der Frage nach der Sekundär- oder Tertiärstruktur bei gegebener Aminosäuresequenz. Die Biodiversitätsinformatik umfasst die Speicherung und Verarbeitung von Informationen zur biologischen Vielfalt. Während die Bioinformatik sich mit Nucleinsäuren und Proteinen beschäftigt, sind die Objekte der Biodiversitätsinformatik Taxa, biologische Sammlungsbelege und Beobachtungsdaten.
Chemoinformatik
Die Chemoinformatik (engl. chemoinformatics, cheminformatics oder chemiinformatics) bezeichnet einen Wissenschaftszweig, der das Gebiet der Chemie mit Methoden der Informatik verbindet und umgekehrt. Sie beschäftigt sich mit der Suche im chemischen Raum welcher aus virtuellen (in silico) oder realen Molekülen besteht. Die Größe des chemischen Raumes wird auf etwa 1062 Moleküle geschätzt und ist weit größer als die Menge der bisher real synthetisierten Moleküle. Somit lassen sich unter Umständen Millionen von Molekülen mit Hilfe solcher Computer-Methoden in silico testen, ohne diese explizit mittels Methoden der Kombinatorischen Chemie oder Synthese im Labor erzeugen zu müssen.
Andere Informatikdisziplinen
Weitere Schnittstellen der Informatik zu anderen Disziplinen gibt es in der Informationswirtschaft, Medizinischen Informatik, Pflegeinformatik und der Rechtsinformatik, Informationsmanagement (Verwaltungsinformatik, Betriebsinformatik), Architekturinformatik (Bauinformatik) sowie der Agrarinformatik, Sozialinformatik, Archäoinformatik, Sportinformatik, sowie neue interdisziplinäre Richtungen wie beispielsweise das Neuromorphic Engineering. Die Zusammenarbeit mit der Mathematik oder der Elektrotechnik wird aufgrund der Verwandtschaft nicht als interdisziplinär bezeichnet.
Release 2011.07.31
