Algorithmen & Datenstrukturen
Programmieren 1


von Prof. Jürgen Plate

1 Daten und Algorithmen

1.1 Grundbegriffe: Nachricht und Information

Fragen:Was ist "Information"?
 Was sind "Nachrichten"?
 Wie wird Information weitergegeben?
 Wie wird Information dargestellt?

Neben der Energie (und der Materie) ist Information eine zweite Basisgröße von universeller Bedeutung. Ihre Eigenständigkeit wurde erst spät erkannt, da ihre Weitergabe immer an energetische oder materielle Träger gebunden ist. An Informationen gelangt man über Nachrichten. Die Definition von Information in der Informatik deckt sich nicht ganz mit dem umgangssprachlichen Gebrauch.

Anders formuliert:

Nachrichten und Informationen sind nicht identisch, insbesondere kann die gleiche Nachricht (mit gleicher Information) auf verschiedene Empfänger unterschiedliche Wirkung haben. Es gibt aber auch Nachrichten, die subjektiv keine Information enthalten.

Bei a) gibt es nur zwei Möglichkeiten (kleiner/größer 25 Grad), bei b) sind theoretisch beliebig viele Möglichkeiten gegeben. Also ist bei b) die Information größer. Daraus folgt, daß Information mit der Zahl der Möglichkeiten zu tun hat.

Der Informationsgehalt einer Nachricht ist also feststellbar und wird durch die Anzahl der (rechts-links) Entscheidungen bestimmt und wird in "bit" gemessen. 1 bit entspricht dabei einer Entscheidung:
Einfacher Weg: Information 1 bit
Komplizierter Weg: 2 Weggabelungen --> 4 Möglichkeiten, 2 bit
3 Weggabelungen --> 8 Möglichkeiten, 3 bit
4 Weggabelungen --> 16 Möglichkeiten, 4 bit
usw.
1 bit ist die Datenmenge, die mit der Antwort auf eine Ja-Nein-Frage übertragen wird.
Mit einem Binärzeichen wird nur dann 1 bit übertragen, wenn die beiden Zeichen des Zeichenvorrats gleichwahrscheinlich sind. In allen anderen Fällen wird weniger als 1 bit übertragen.

Das Shannonsche Informationsmaß H, oder kurz die Datenmenge, ist definiert als:
Dabei gilt:
N = Gesamtzahl der verwendeten Zeichen
pi = Wahrscheinlichkeit für das Auftreten des Zeichens i
ld = Logarithmus zur Basis 2

Sind alle Symbole gleichwahrscheinlich, vereinfacht sich die Formel zu: H = ld(N) bit

Anmerkung:
ld = logarithmus dualis: y = 2n --> n = ld(y)
Umrechnung: ld z = lg(z)/lg(2) = ln(z)/ln(2) (Basis beliebig)

Beträgt die Zeichenzahl N = 2n, so werden n bit übertragen. Man könnte dies als n aufeinanderfolgende Antworten auf jeweils eine Ja-Nein-Frage auffassen.

Jedes Astende (Blatt) entspricht dann einem Zeichen, also ergeben sich 23 = 8 Zeichen, die hiermit übertragen werden können.

Darstellung von Information

Nach der abstrakten Information nun zu konkreten Darstellung der Information, der Nachricht. Dazu einige Definitionen:

Nachricht:
Zusammenstellung von Symbolen (Zeichen) zur Informationsübermittlung.

Symbol:
Element eines Symbol- oder Zeichenvorrates. Dieser Vorrat ist eine festgelegte endliche Menge von verschiedenen Symbolen (= Elemente der Menge). Der Unterschied zwischen Symbol und Zeichen ist recht subtil. Ein Symbol ist ein Zeichen mit bestimmter Bedeutung.

Alphabet:
Ein geordneter Vorrat von Symbolen.

Wort:
Folge von "zusammengehörigen" Zeichen, die in einem bestimmten Zusammenhang als Einheit betrachtet werden.

Beispiel:
Alphabet: A,B,C,D,E,F,...,X,Y,Z
Wort: DONALD
Nachricht: DONALD SUCHT DAISY

Nachrichten können durch Signale physikalisch dargestellt werden, z. B. Schallwellen, elektromagnetische Wellen, Ströme, Spannungen, Licht, etc. Dabei wird zwischen digitalen und analogen Signalen unterschieden.

Analoge (wertkontinuierliche) Signale:

Digitale (wertdiskrete) Signale:
Hier gibt es nur eine endliche Zahl von möglichen Zuständen einer physikalischen Größe (im einfachsten Fall zwei), z. B. Ziffernanzeige eine Meßinstruments, Folge von Ziffern. Da die meisten physikalischen Größen analog sind, wird oft eine Quantelung vorgenommen, z. B. eine Spannung zwischen 6,5 V und 7,5 V auf 7 V gequantelt.

Daher unterscheidet man zwischen Analogtechnik und Digitaltechnik. In den normalerweise verwendeten Digitalrechnern wird eine Digitaltechnik mit nur zwei möglichen Werten eingesetzt. Diese beiden Signale (meist durch "0" und "1" dargestellt) müssen in irgend einer Form aus dem Signal erkennbar sein. Je nach verwendeter phsikalischer Größe ergeben sich oft mehrere eindeutige Möglichkeiten für die "0" oder "1" .

Informatik

Vereinfacht ausgedrückt kann man sagen: Die Informatik ist die Lehre von der Information.

Es stecken aber zahlreiche Gesichts- und Ansatzpunkte dahinter. Eine Information oder ein Datum ist etwas das uns eine Mitteilung macht. Diese können wir aufnehmen oder auch (als unwichtig) ignorieren. Oft sind die Datenmengen so immens, dass wir sie nur aufnehmen können, wenn sie entsprechend aufgearbeitet, z. B. reduziert sind. Daten sollen bei Bedarf abrufbar gespeichert sein und an beliebige Stellen transportiert werden können. Wir bedienen uns für diese Aufgaben oft der Hilfe von Maschinen und Computern. Diese müssen in der Lage sein, unsere Wünsche der Datenaufbereitung zu erfüllen. Das bedeutet aber, dass wir die Fähigkeit haben müssen, Ihnen unsere Wünsche (Anweisungen) auch mitzuteilen. Es muss eine Art Sprache zwischen Mensch und Maschine bestehen, die beide verstehen. Solche Anweisungen können nicht nur zur Verarbeitung von Daten dienen, sondern auch für zahlreiche Tätigkeiten auch im Sinne von Automaten und Robotern.

In diesen Bereichen Forschung zu betreiben und neue (bessere) Möglichkeiten zu finden ist die Aufgabe der Informatik. Sie hat daher einerseits mit Theorien zu tun wie das Verwalten von Daten und Entwickeln von Datenstrukturen, der Entwicklung von Sprachen und Abläufen (Algorithmen) für den Betrieb von virtuellen, simulierten und realen Maschinen und sich überhaupt mit der Lösung und Lösbarkeit gestellter Probleme zu befassen. Dies geht hin bis zu abstrakten Theorien. Andererseits hat die Informatik auch mit der Entwicklung praktischer Geräte, Maschinen, Prozessoren usw. zu tun und Kommunikationsmöglichkeiten (Schnittstellen) zu entwickeln. Hier grenzt sie an den Bereich der Elektrotechnik (Datentechnik), die letztendlich die gewünschten Schaltungsvarianten entwickeln und bereitstellen muss. Auch bestehen hier Verbindungen zum Maschinenbauer, der die Modelle von maschinellen Automaten und Robotern entwickelt, während der Informatiker die Steuerungsaufgaben (Programmierung) übernimmt.

Zu Beginn wollen wir uns vor allem mit einem praktischen Aspekt der Informatik auseinandersetzen. Sie lernen kennen, wie man Abläufe darstellen und werden auch eine Programmiersprache also ein Kommunikationsmittel kennenlernen. Hierzu gehört auch das Erfassen und Darstellen von Daten und zugehöriger Datenstrukturen und programmtechnischer Ablaufstrukturen.

1.2 Der Computer und seine Fähigkeiten

Es mag Sie erstaunen, daß im gesamten Skriptum kaum je von Computern gesprochen wird, obwohl es doch um das Programmieren von Computern geht. In der Regel braucht ein Programmierer heute kaum noch etwas darüber zu wissen, was im Detail im Computer vor sich geht. Eine modellhafte Vorstellung genügt zunächst.

Auch der normale Autofahrer braucht keine technischen Einzelheiten des Motors zu kennen. Doch sollte man einige grundlegende Dinge verstanden haben, wenn man mit dem Auto bzw. dem Computer sicher umgehen will.

In diesem Abschnitt werden einige Anwendungsfälle aufgezählt, die Arbeitsweise von Mensch und Computer verglichen und die Frage gestellt, wie der Computer zu seinen Fähigkeiten kommt.

Nehmen Sie als Beispiel moderne Kaufhauskassen. Sie schreiben jeden Betrag, mit Erklärung versehen, auf den Kassenbon. Das kann natürlich jede alte Registrierkasse auch. Was ist also Besonderes an den modernen Kassen? Die neuen Kassen können einem Computer mitteilen, wieviel von jedem Artikel im Lauf des Tages verkauft wurde. Wenn man dem Computer vorher mitgeteilt hatte, wieviele Pakete Waschmittel im Regal standen, kann der Rechner am Abend nicht nur die Kassenabrechnung erledigen, sondern auch ausdrucken, ob das Regal aus dem Lager nachgefüllt werden muß. Das konnten die alten Kassen natürlich nicht. Zudem können diese Kassenterminals noch viel mehr, nämlich Tippfehler korrigieren (wenn z. B. Preis und Artikelnummer nicht zusammenpassen), Sonderangebote berücksichtigen (auch wenn der alte Preis noch auf der Ware steht), Preisfragen beantworten und Absatzstatistiken erstellen.

Kasse und Computer übernehmen also etliche Aufgaben, die vorher die Angestellten des Kaufhauses erledigen mußten. Eine weitere Computeranwendung war die Vorbereitung des Flugs und die Steuerung der Raumschiffe, die Menschen vor nunmehr 30 Jahren zum Mond und wieder heil zurück zur Erde brachten. Und die damaligen Computer waren verglichen mit heutigen Maschinen äußerst primitiv.

Am nächsten Beispiel, der Lohnabrechnung, werden Sie sehen, worin der Unterschied liegt zwischen dem, was ein Mensch tut, und dem, was der Computer tut. Schauen Sie sich zuerst die Arbeit eines Lohnbuchhalters an. Er stellt zuerst anhand der Stundenabrechnungen und Stempelkarten fest, wieviele Stunden der Arbeitnehmer gearbeitet hat. Die Stunden werden addiert um die Gesamtarbeitszeit zu erhalten. Diese Zeit wird mit dem Stundenlohn multipliziert, und dann werden Steuern und Sozialabgaben abgezogen. Dabei muß der Buchhalter einige Fakten aus der Personalkartei heraussuchen - Kinderzahl, Familienstand, Steuerklasse, Versicherungsnummer etc. Ist die Berechnung beendet, werden Lohnabrechnung und Überweisungsformulare ausgefüllt und an die richtigen Stellen weitergeleitet.

Der Buchhalter erhält also gewisse Informationen, nämlich Arbeitszeit, Steuerklasse, Stundenlohn usw.; er verarbeitet dann diese Informationen nach einem bestimmten Schema und gibt schließlich neue Informationen, z. B. den Betrag des Nettolohns an andere weiter. Der Informationsfluß läßt sich also folgendermaßen skizzieren:

Eingabe - Verarbeitung - Ausgabe

Genauso arbeitet auch der Computer; er erhält aus einer Eingabestation die Daten über die Anwesenheitszeiten des Arbeitnehmers. Bereits das Addieren der einzelnen Zeiten wird "vom Programm" übernommen, das dazu ebenfalls eingegeben werden mußte. Die eigentliche Verarbeitung erfolgt in der Zentraleinheit des Computers. Sie besteht im wesentlichen aus drei Teilen, dem Arbeitsspeicher (dem Gedächtnis des Buchhalters entsprechend), das Rechenwerk und das Steuerwerk (am besten, wenn auch stark vereinfacht, den Koordinierungsfähigkeiten des Buchhalters vergleichbar). Die Personalkartei wird nicht im Arbeitsspeicher untergebracht, da dieser dafür zu klein ist (der Buchhalter kann ja auch nicht alle Kontonummern im Kopf behalten). Für die Personalkartei stehen externe Speicher zur Verfügung, meist Magnetplatten. Wenn das Rechenwerk mit seiner Arbeit fertig ist, wird das Ergebnis dann vom Drucker gleich an die richtigen Stellen in die entsprechenden Formulare eingetragen.

Im letzten Absatz wurden einige Begriffe erwähnt, so z. B. Eingabestation, Zentraleinheit, Arbeitsspeicher, Steuerwerk. Die Erklärungen dieser Begriffe sollen Sie nun erhalten.

Computer-Systeme

Computer sind Systeme, die aus Hardware und Software bestehen. Jede der beiden Komponenten ist ohne die andere nichts wert. Die von Ihnen geschriebenen Programme nehmen, damit sie ablaufen, sowohl die Hardware als auch die Software des Computers in Anspruch. Die Hardwarekomponenten umfassen alle "anfaßbaren" Komponenten. Dazu zählt der Computer selbst und alle Geräte, die daran angeschlossen sind: Bildschirm, Drucker, Diskettenlaufwerk usw. Die Software ist "nicht anfaßbar". Sie benötigt zum Transport, zur Speicherung und zum Funktionieren immer irgendwelche Hardware. Software läßt sich grob in das sog. Betriebsystem und die sog. Anwendersoftware unterteilen.

Trotz allem kann man die Software nicht von der Hardware trennen, da selbst die kleinsten Aufgaben beide in Anspruch nehmen. Man braucht Hardware, um Daten eingeben zu können, aber zugleich auch die Software, die den Datenaustausch zwischen Terminal und Computer steuert. Man braucht Hardware, um Daten ausdrucken zu können, aber auch die Software, die ein Zeichen nach dem anderen vom Computer zum Drucker überträgt. Man braucht Hardware, um mit Zahlen rechnen zu können, aber auch die Software, die Zahlen für die Berechnung aufbereitet. Die beiden Komponenten eines Computersystems sind nicht voneinander zu trennen, trotzdem sollen sie nun nacheinander betrachtet werden.

Hardware

In der zuerst von John v. Neumann 1947 angegebenen Modellvorstellung eines Rechners besteht dieser aus vier Funktionseinheiten:

Recheneinheit und Steuereinheit werden oft als Zentraleinheit oder Central Processing Unit (CPU) zusammengefasst. Die CPU ist das "Herz" eines Computers. Sie bearbeitet Programme, führt Rechnungen aus und steuert die Vorgänge in den anderen Teilen.
Der Speicher nimmt alle Daten auf, die der Computer braucht. Das geht von Daten, die der nächste Programmschritt in einer Mikrosekunde benötigt, bis hin zu ganz selten gebrauchten Daten.
Schließlich stellen die E/A-Geräte die Verbindung her zwischen dem Computer und seinem Anwender.

Zentraleinheit

Die CPU besteht aus mehreren Teilen, die eng zusammenarbeiten: Recheneinheit und Steuereinheit. Sie enthält mehrere Register für die Aufnahme der Daten, die bei der Ausführung eines Programms verfügbar sein müssen. So nimmt z.B. das Befehlsregister den jeweils auszuführenden Befehl auf. Ein Register kann man sich als schnellen (Zwischen-) Speicher für ein einzelnes Datenwort vorstellen. Nur der anstehende Befehl steht im Befehlsregister, daher gibt es - von der Ausführung her gesehen - keinen Unterschied zwischen langen und kurzen Programmen oder zwischen schwierigen und einfachen. Die Befehle enthalten die Informationen über die Speicherplätze der benötigten Daten; bei der Ausführung des Befehls werden die Daten bereitgestellt und nach der Bearbeitung wieder abgelegt.

Recheneinheit

Die ALU (Arithmetic and Logic Unit) der Recheneinheit führt alle Berechnungen aus und trifft logische Entscheidungen. Ihre Hauptaufgabe ist es, Vergleiche zwischen Werten vorzunehmen und damit Bedingungen zu überprüfen. Die Rechenfähigkeit beschränkt sich auf die Addition, doch lassen sich daraus alle anderen arithmetischen Operationen aufbauen. Die komplizierten Rechnungen, die der Computer in kurzer Zeit ausführen kann, setzen sich aus einer Vielzahl kleinster Schritte in der ALU zusammen.

Steuereinheit

Die Register der Steuereinheit und die Recheneinheit arbeiten Hand in Hand, die Register der Steuereinheit liefern die Signale zur Steuerung der gewünschten ALU-Funktion. Die Verbindung zwischen ihnen (und von ihnen zu den übrigen Einheiten) wird durch die Steuereinheit hergestellt. Man kann die Steuereinheit als Schaltzentrale des Computers ansehen, die alle Datenströme lenkt.

Speicher

Der Speicher nimmt alle Daten auf, dazu gehören die Programme ebenso wie die von ihnen zu verarbeitenden Werte. Bei der Verarbeitung werden Zwischenergebnisse im Speicher abgelegt und schließlich die Endergebnisse. Man unterscheidet beim Speicher zwischen dem Hauptspeicher (oder Arbeitsspeicher) und dem externen Speicher. Der Hauptspeicher ist fest im Computer eingebaut, man kann ihn meist durch zusätzliche Speicherkarten erweitern. Im Hauptspeicher befindet sich das Programm, das Sie schreiben oder verändern wollen oder das der Computer bearbeiten soll. Auch die Daten, die beim Ablauf des Programms benötigt werden, werden dort abgelegt. Auf den Hauptspeicher kann die CPU direkt zugreifen, sie kann von dort neue Programmbefehle holen und kann Daten laden oder abspeichern.

Externe Speicher (Massenspeicher)

Im externen Speicher werden die Programme und Werte aufbewahrt, die man zur Zeit nicht benötigt. Als Datenträger werden Festplatten und Disketten (Floppy- Disks) verwendet. Die Diskette wird ins Diskettenlaufwerk eingelegt und kann dann mit Daten "beschrieben" werden. Für das Abspeichern von Programmen vom Hauptspeicher auf die Festplatte oder Diskette gibt es besondere Kommando des Betriebssystems, ebenso für das Laden von einem Massenspeicher in den Hauptspeicher.

Ein-/Ausgabe-Geräte

Die Eingabe- und Ausgabegeräte stellen die Verbindung her zwischen einem Computer und seinem Benutzer, aber auch zwischen einem Computer und anderen Geräten oder anderen Computern. Ohne Geräte zur Ein- und Ausgabe könnte man keine Programme eingeben und keine Daten an ein laufendes Programm liefern, man erhielte keine errechneten Ergebnisse. Ein Ausgabegerät wie der Drucker läßt sich einsetzen, um die Ergebnisse der Programmbearbeitung zu erhalten oder um die Werte auszugeben, die in einem Speicher abgelegt sind. Ein Eingabegerät wird komplementär eingesetzt, mit ihm versorgt man die CPU oder den Hauptspeicher durch die CPU mit neuen Daten.

Vernetzung

Zu den E/A-Geräten gehören auch die Netzwerk-Verbindungen, mit denen sich mehrere Computer zu einem Verbund zusammenschließen lassen. Sie erlauben einen sehr schnellen Datenaustausch zwischen verschiedenen Computersystemen. Ein Vorteil solcher Vernetzung liegt darin, daß mehrere Systeme gemeinsam auf periphere Geräte wie Drucker oder Festplatte zugreifen können. Damit erweitern sich die Fähigkeiten der einzelnen Maschinen ohne entsprechende zusätzliche Kosten.

Sichtweisen eines Rechners

Der Benutzer eines Rechners sieht von der Maschine je nach seinem Status einen mehr oder weniger eingeschränkten Teil.

Mehr Informationen zur Hardware von Rechnern bietet das Skript Datenverarbeitungssysteme.

Software

Damit kennen Sie nun in etwa den Hardwareaufbau eines Computers. Es stellt sich jetzt die Frage nach seinen Einsatzgebieten und nach der Herkunft seiner Fähigkeiten. Seine Universalität erklärt sich aus den sehr elementaren Maschinenbefehlen, der Rechnerarchitektur und der Tatsache, daß der Computer, bevor er überhaupt etwas tun kann, erst in einem Programm (Software) erklärt bekommen muß, was er zu tun hat. Es gibt eine riesige Vielfalt an Programmen, geschrieben für die unterschiedlichsten Aufgaben, die aber auf ein und derselben unveränderten Hardware lauffähig sind.

Die Software eines Computersystems kann grob in zwei Teile gegliedert werden: die Anwendersoftware und das Betriebssystem. Ein Anwenderprogramm ist für die Lösung einer ganz bestimmten Aufgabe geschrieben worden, der Anwender setzt es dann (und nur dann) ein, wenn er eine solche Aufgabe lösen will.

Anwenderprogramme

Wenn man allgemein von Software spricht, meint man meist Anwenderprogramme, also Programme, die eine spezielle Aufgabe lösen. Einige typische Anwenderprogramme sind

Wenn Sie in eine Computerzeitschrift schauen, finden Sie viele weitere Beispiele für Anwenderprogramme. Und auch die Programme dieses Skriptums sind zu den Anwenderprogrammen zu zählen, jedes wird für die Lösung eines bestimmten Problems geschrieben.

Betriebssystem

Dagegen ist das Betriebssystem eine anwendungsneutrale Software. Was die Infrastruktur einer Stadt mit Ihren Straßen, Buslinien, Trambahnen, Telefonnetz, Fernverkehrsanbindung für den Einzelnen und die Geschäftswelt ist, stellt das Betriebssystem als komfortable standardisierte Umgebung für die Anwenderprogramme dar. Möchte man in der Stadt von einem Ort zum anderen Waren transportieren, so benutzt man mit dem Auto die bestehenden Straßen und baut keine neuen. Änlich ist es mit den Anwendungsprogrammen. Sie sind für eine spezielle Aufgabe geschaffen worden. Der Ersteller möchte sich aber nicht unbedingt mit der Infrastruktur, der Hardware, auseinandersetzten.

Das Betriebssystem wird ständig benötigt, um die Vorgänge in der Hardware zu steuern und um die Wechselwirkung zwischen dem Computer und seiner Anwendungsprogramme zu koordinieren.

Die "nackte" Hardware eines Computers hat nicht die Fähigkeiten, ein Anwenderprogramm zu bearbeiten. Auch wenn die CPU die Vorgänge in der Hardware auf einer niedrigen Ebene koordinieren kann, es muß eine Verbindung zwischen dem Anwenderprogramm und der jeweiligen Hardware hergestellt werden. Die Bearbeitung des Programms erfordert den Einsatz verschiedener Eingabe- und Ausgabegeräte. Es ist zunächst extern gespeichert und muß in den Hauptspeicher geladen werden. Diese und viele weitere Abläufe werden vorn Betriebssystem gesteuert. Es ist ein sehr umfangreiches Programm, das die Vorgänge in der Hardware steuert und koordiniert. Der Benutzer braucht sich nicht selbst darum zu kümmern, wie die einzelnen Schritte bei der Bearbeitung seines Programms intern ablaufen.

Wenn ein Computer nur ein einziges Programm zu bearbeiten hätte wie z.B. der Mikroprozessor in einer Waschmaschine, dann bräuchte er kein Betriebssystem. Die Aufgabe eines Betriebssystems ist es, eine Umgebung zu schaffen, in welcher verschiedene Anwenderprogramme ablaufen können. Es bietet verschiedene Möglichkeiten an, den Computer einzusetzen. Da das Betriebssystem unerläßlich ist, wird es vom Hersteller mitgeliefert und läßt sich kaum verändern.

Aufgaben des Betriebssystems

Von den vielen Aufgaben des Betriebssystems sollten Sie einige kennen. Zum Betriebssystem gehört z. B. ein Programm, das den Zugriff auf externe Speicher steuert und die gespeicherten Dateien verwaltet. Bei größeren Systemen und Netzwerken kontrolliert das Betriebssystem z.B. den Zugang zum Computer mit der Eingabe eines Paßwortes und organisiert die gleichzeitige Arbeit, mehrerer Benutzer. Das Betriebssystem ist verantwortlich für das Speichern und Laden von Programmen und für die Zuteilung der benötigten Hilfsmittel. Aus der Sicht des Programmierers ist besonders wichtig, daß vom Betriebssystem her die Programmierumgebung geschaffen wird. Es liefert die Umgebung, in der Sie Programme schreiben können, und es steuert den Ablauf Ihrer Programme. Sie brauchen sich nicht um die Einzelheiten zu kümmern, das Betriebssystem nimmt Ihnen (fast) alles ab. Die Entwicklung immer leistungsfähigerer Betriebssysteme hat es ermöglicht, die Programmier-Arbeit immer komfortabler zu machen.

Mehr Infos zur Arbeitsweise von Betriebssystemen bietet das Skript Betriebssysteme.

Fazit

Der Computer kann eine einmal programmierte Aufgabe beliebig oft ausführen. Er ist also für Routineaufgaben, aber auch für die Verarbeitung so riesiger Datenmengen geeignet, die der Mensch nicht mehr bewältigen könnte. Wenn es also darauf ankommt, ein Rechenergebnis unmittelbar nach Eintreffen der Daten zu erhalten, wird man einen Computer bemühen - oder, wenn Sie wissen wollen, ob die Zahl 94084005495481 eine Primzahl ist. Um dies nachzuprüfen, bräuchte man sehr lange; vom Computer erfährt man schon nach Sekunden, daß es sich um keine Primzahl, sondern um das Quadrat der Primzahl 9699691 handelt. Die Datenverarbeitung umfaßt also:

- Daten-Empfang ----------------------------------- lesen, eingeben
- Daten-Speicherung ------------------------------- speichern
                                         /--------- umformen
                      /-- nach der Form +
                     /                   \--------- rechnen
- Daten-Bearbeitung +
                     \
                      \-- nach dem Inhalt --------- ordnen
                          (sortieren, vergleichen, 
                           selektieren, mischen)
- Daten-Ausgabe ----------------------------------- schreiben, ausgeben
- Daten-Übertragung ------------------------------- transportieren

1.3 Softwareerstellung (Programmierung)

Kennen Sie die Geschichte des Herrn X., der sich in eine astronomische Vorlesung verirrt hatte. Obwohl die dargestellten Gedankengänge fremd und neu für ihn waren, meinte er doch verstehen zu können, wie die Astronomen ihre Teleskope einsetzten, um die Entfernung der Gestirne von der Erde zu ermitteln. Es erschien ihm auch verständlich, daß sie die relative Positionen der Sterne und ihre Bewegungen voraussagen konnten. Was er aber gar nicht begreifen konnte: Wie zum Teufel konnten die Astronomen die Namen der Sterne und der Sternbilder herausbekommen?

Manche Leute haben das gleiche Problem bei den Programmiersprachen: Sie halten eine Sprache für ein kompliziertes mathematisches Begriffssystem, das von den ersten Informatikern mit viel Glück entdeckt worden ist. Es handelt sich aber nicht um einen Code, den es zu knacken galt, sondern um eine künstliche Sprache, die von Menschen aus ersten bescheidenen Anfängen heraus immer weiter entwickelt und verbessert worden ist.

Was sind Algorithmen?

Sie haben mit Sicherheit im Augenblick, in dem Sie diese Zeilen lesen, eine ganze Reihe von Problemen. Diese können Sie in verschiedene Kategorien einteilen, z. B. Sie können sie aber auch unter einem Aspekt sehen, der uns ganz besonders interessiert, nämlich mit Computern lösbare bzw. nicht lösbare Probleme. Hier interessieren wir uns für die erste der beiden Gruppen. Eine klare Trennungslinie zwischen beiden läßt sich im allgemeinen nicht ziehen, denn Probleme, die gestern noch als unlösbar galten, werden morgen von Computern vielleicht gelöst. Es gilt aber ein Grundsatz:

Jedes Problem, dessen Lösung durch einen Algorithmus beschrieben werden kann, ist im Prinzip durch einen Computer lösbar.

Aus dieser Aussage können Sie zwei Schlüsse ziehen:

  1. Ein Computer ist ein Werkzeug, welches Ihnen bei der Lösung gewisser Probleme hilft.
  2. Ein Algorithmus ist eine Art Anleitung oder Vorschrift, wie man zu einem Problem eine Lösung findet.
Das Wort "Algorithmus" wird im allgemeinen Sprachgebrauch kaum verwendet und ist Ihnen daher vermutlich auch nicht geläufig. Es geht zurück auf den arabischen Autor Al-Khowarizmi (ca. 825 n. Chr.), der ein Lehrbuch über Mathematik geschrieben hat. In der Informatik versteht man darunter eine Lösungsvorschrift. Wir wollen den Begriff "Algorithmus" folgendermaßen definieren:

Ein Algorithmus ist eine eindeutige Beschreibung eines endlichen Verfahrens zur Lösung einer bestimmten Klasse von Problemen.

Zu viel auf einmal? Wir werden im nächsten Abschnitt auf die einzelnen Eigenschaften eines Algorithmus noch genauer eingehen. Zunächst wollen wir den Begriff des Algorithmus jedoch mit "Leben" füllen, damit Sie ganz konkrete Vorstellungen damit verbinden können.

Alltagsalgorithmen

Die Alltagswelt, die Sie umgibt, ist voller Algorithmen - Sie haben es bisher nur nicht gewußt. Wenn Sie z. B. eine Coladose öffnen wollen, führen Sie mit dem Objekt "Coladose" eine Folge koordinierter Bewegungsabläufe aus, die schließlich die gewünschte Lösung produzieren. Die Lösungsvorschrift hierzu haben Sie sich durch Lernen und Üben erworben und in Ihrem Gehirn abgespeichert. Sie tragen also den Algorithmus "Coladose öffnen" zusammen mit unzähligen anderen Algorithmen in Ihrem Kopf herum. Eine ganze Reihe von Alltagsalgorithmen ist schriftlich formuliert, z.B. Bedinungsanleitungen oder Kochrezepte, aber auch Wegbeschreibungen in einem Wanderführer oder Gesetze. Andere Algorithmen sind in Form eines Bildes formuliert, z.B. die Aufbauanleitung für eine Lampe oder die Anleitung zum Falten eines Papierfliegers:


Die Algorithmen haben alle einige Gemeinsamkeiten. Sie bestehen aus kurzen und knappen Formulierungen, welche dem "Ausführenden" gewisse Anweisungen geben, die zur Lösung seines Problems führen. Je komplizierter ein Problem ist, umso mehr Anweisungen wird man in der Regel benötigen. Da als Adressat dieser Anweisungen ein mit Vernunft begabter Mensch vorausgesetzt wird, ist es hinreichend, wenn man die Anweisungen in einem kurzen deutschen Satz formuliert. Verständnisschwierigkeiten bei deren Interpretation treten im allgemeinen nicht auf. Der Mensch verfügt auch über ein gewisses Repertoire an Hilfsmaßnahmen, wenn unvorhergesehene Störungen auftreten. Dazu ein Beispiel:

Jeder von uns kann in einer Telefonzelle erfolgreich telefonieren. Nehmen wir an, wir hätten einen Gast von einem fernen Planeten, der perfekt deutsch spricht und liest, der aber noch niemals eine Telefonzelle benutzt hat (vermutlich, weil seinesgleichen per Telepathie kommuniziert). Er soll nun von uns auf einem Blatt Papier eine exakte Handlungsanweisung für die Benutzung dieser Telefonzelle erhalten, damit er uns nach dem Shopping anrufen kann. Es wird sich also um ein Ortsgespräch handeln, und wir unterstellen, daß unser Gast einige Groschen in der Tasche hat und unsere Telefonnummer kennt. Außerdem setzen wir einige Randbedingungen als bekannt voraus, obwohl gerade diese in der Praxis oft zu großen Realisierungsproblemen führen, hier z. B. die Frage: "Was ist der Hörer und wie dann wir herum wird er gehalten?".

Von Personen, die sich bisher mit der algorithmischen Lösung solcher Alltagsprobleme nicht beschäftigt haben, wird meist folgende Handlungsanweisung genannt:

  1. Nimm Hörer ab;
  2. Wirf 20 Cent ein;
  3. Wähle ...
Bereits zwischen der ersten und zweiten Anweisung wurde übersehen, daß niemand von uns eine Münze einwirft, wenn er in dem zum Ohr geführten Hörer keinen Dauerton hört. Und schließlich würden wir nicht wählen, wenn eine der eingeworfenen Münzen durchgefallen wäre. Auch der jetzt naheliegende Schritt, daß man diese Münze dem Rückgabefach entnimmt und es mit ihr nochmals probiert, muß nach wenigen gleichartigen Versuchen ersetzt werden durch das Austauschen der offensichtlich ungeeigneten Münze. Denn ein derart "falsch" programmierter Computer würde die gleiche durchgefallene Münze immer wieder erneut einwerfen, da er entgegen dem Menschen diese Handlungsweise niemals als unsinnig erkennen würde.

Tatsächlich lautet die korrekte Handlungsanweisung, nach der wir alle in der Praxis vorgehen:

  1. Nimm Hörer ab;
  2. Falls Dauerton vorhanden, dann wirf 20 Cent ein, sonst hänge Hörer ein und verlasse Telefonzelle;
  3. Falls eine Münze durchfällt, dann prüfe, ob diese Münze schon einmal durchgefallen ist. Falls ja, tausche sie aus, sonst werfe sie erneut ein;
  4. Wähle ...
Die Lesbarkeit dieser Handlungsanweisung läßt sich durch eine geeignete graphische Strukturierung verbessern:
  1. Nimm Hörer ab;
  2. Falls Dauerton vorhanden,
  3. Falls ein Cent durchfällt,
  4. ...
Es ist offensichtlich, daß bei alltäglichen Handlungen, also auch bei berufsbezogenen Abläufen, ein großer Unterschied zwischen "tun können" und "exakt beschreiben können" besteht. Soll der Algorithmus jedoch von einer Maschine (einem Computer) ausgeführt werden, dann müssen diese Anweisungen viel präziser formuliert und alle möglichen Sonderfälle berücksichtigt werden. Auch wenn man selbst nicht programmiert, so ist diese Art zu denken eine wichtige Grundlage für eine sinnvolle Anwendung von Computern.

Eine weitere Gemeinsamkeit der aufgeführten Alltagsalgorithmen besteht darin, daß sie Anweisungen zur Manipulation von Objekten geben. Der Algorithmus oben beschreibt beispielsweise, wie die Objekte Hörer, Münze, Tastenfeld usw. zu manipulieren sind. Besonders deutlich tritt diese Eigenschaft bei Kochrezepten zum Vorschein. Als Beispiel betrachten wir die Zubereitung einer Gulaschsuppe.

Algorithmus "Gulaschsuppe zubereiten"

Zu manipulierende Objekte:
350 g Rindfleisch, 3 Zwiebeln, 50 g Schweineschmalz, 15 g Mehl, 1 kleine Dose Tomatenmark, 3/4 1 Wasser, Salz, Paprika, Majoran.

Hilfsobjekte:
Herd, Kochgeschirr

Anweisungen:

  1. Fleisch und Zwiebeln würfeln
  2. in Schmalz andünsten
  3. mit Mehl bestäuben und kurz anrösten
  4. Tomatenmark zugeben
  5. mit Wasser auffüllen
  6. garen
  7. mit Salz, Paprika und Majoran abschmecken.
An diesem Beispiel wird deutlich, daß ein Algorithmus aus zwei Teilen besteht:

Eigenschaften von Algorithmen

In der Definition des Begriffs "Algorithmus" im vorausgegangenen Abschnitt kommen einige Adjektive vor, welche die Eigenschaften von Algorithmen beschreiben. Wir wollen Sie der Reihe nach betrachten.