 |
Algorithmen & Datenstrukturen
|
|
Algorithmen & Datenstrukturen
|
| 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. |
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.
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" .
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.
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 Lohnstreifen 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.
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.
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.
| Mehr Informationen zur Hardware von Rechnern bietet das Skript Datenverarbeitungssysteme. |
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.
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 ,so ist das Betriebssystem die komfortable standardisierte Umgebung für die Anwenderprogramme. 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. Ä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, auseinendersetzten.
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.
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.
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.
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. |
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
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.
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:
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.
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:
Tatsächlich lautet die korrekte Handlungsanweisung, nach der wir alle in der Praxis vorgehen:
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.
Hilfsobjekte:
Herd, Kochgeschirr
Anweisungen:
Weitere Punkte, die auch oft als Eigenschaften von Algorithmen gefordert werden, sich aber aus den obigen Eigenschaften ergeben, sind:
Neben diesen Eigenschaften gibt es noch weitere Eigenschaften von Algorithmen, die sich auf die Art und Weise der Ausführung des Algorithmus beziehen. Hier sind zu nennen:
Zusammenfassen lassen sich alle diese Eigenschaften in einer kurzen aber präzisen Definition des Begriffs Algorithmus.
|
Algorithmus Eine Bearbeitungsvorschrift heißt Algorithmus, wenn sie folgende Eigenschaften erfüllt:
|
Da man nicht alle Bearbeitungsvorschriften durch eindeutige Folgen von Anweisungen als Algorithmus darstellen kann, wurde im Laufe der Zeit der Begriff ausgedehnt. Man unterscheidet heute zwischen deterministischen und nicht-deterministischen Algorithmen. Enthält ein Algorithmus elementare Anweisungen, deren Ergebnis durch einen Zufallsmechanismus beeinflußt wird, so heißt dieser Algorithmus nicht-deterministisch. Liefert er bei der gleichen Eingabe immer die gleiche Ausgabe, so heißt er deterministisch.
Spielen wir nun noch ein Beispiel für eine Verfahrensbeschreibung durch. Beschreibung des Verfahrens "S":
(S1) Wenn keine Striche mehr in der Eingabe vorhanden sind, so
höre auf.
(S2) Nimm einen Strich aus der Eingabe weg. Wenn bereits vier
Striche ungebündelt in der Ausgabe liegen, lege einen Querstrich
über sie; andernfalls füge einen Strich in der Ausgabe hinzu.
Dann gehe nach (S1).
Bei dieser Art der Darstellung eines Verfahrens gilt die Regel: Wenn man alle Handlungen eines Schritts durchgeführt hat und nicht ausdrücklich durch "höre auf" oder "gehe nach" etwas anderes gesagt bekommt, so geht man zum nächsten Schritt.
Sie haben zwar jetzt die Beschreibung eines Verfahrens erhalten, seinen Nutzen erkennen Sie aber erst, wenn Sie wissen, was in der EINGABE vorhanden ist und wie die AUSGABE aussieht. Denken Sie nochmal an den Informationsfluß. Das Kennzeichen der Datenverarbeitung wird Ihnen immer wieder begegnen: EINGABE - VERARBEITUNG - AUSGABE. Die Eingabe des Verfahrens "S" besteht aus einer Anzahl von Strichen, die irgendwie angeordnet sind, z. B. wie hier:
Führen Sie jetzt das Verfahren "S" durch. In (S2) ist eine Bedingung; wir müssen diese prüfen und, wenn sie erfüllt ist, die dahinterstehende Anweisung ausführen. Als Ausgabe erhält man was hier dargestellt ist.
Gewünscht war natürlich das linke Beispiel. Also hat unsere Verfahrensbeschreibung noch etliche Schwachstellen. Sie müßte präzisiert werden, etwa durch: "Füge einen Strich von 8 mm Höhe parallel zu den anderen Strichen und parallel zur langen Kante des Papiers im Abstand von 0,5 mm von dem vorhergehenden auf derselben Grundlinie wie die anderen an. Man könnte der Beschreibung auch noch einen vernünftigen Namen geben: "Verfahren zur Bündelung von Strichen in Fünfergruppen".
Damit ein Verfahren einem Computer mittels einer Programmiersprache erklärt werden kann, muß es den folgenden Bedingungen genügen:
Der Begriff Algorithmus ist ein zentraler Begriff der Informatik. Er baut immer auf einer Menge von Grundoperationen auf.
Die Schwierigkeiten, die dabei entstehen, sind der Grund, weshalb man dem Computer nur eine ganz bestimmte Sorte von Sprachen, sogenannte normierte Sprachen, anbieten darf. Die Programmiersprachen sind normierte Sprachen, die der Beschreibung von Verarbeitungsvorschriften, Datenstrukturen sowie Ein- und Ausgabe dienen.
Programmieren bedeutet also, einen Computer dazu zu bringen, Algorithmen auszuführen. Dafür müssen wir den Algorithmus so formulieren, daß der Computer ihn versteht - in einer Programmiersprache. Mit dem, was wir bisher wissen, können wir definieren, was man unter einem Programm versteht:
| Ein Programm ist die Formulierung eines Algorithmus in einer Programmiersprache. |
Programme sind also Algorithmen, die in einer besonderen Sprache formuliert sind. Den Begriff "Programmieren" können wir somit wie folgt definieren:
| Unter "Programmieren- versteht man das Aufschreiben eines Algorithmus in einer Programmiersprache. |
Wenn Sie eine höhere Programmiersprache beherrschen wollen, müssen Sie zuerst einmal ihr Vokabular und ihre Grammtik lernen. Zum Verständnis der Programmiersprache müssen Sie zusätzlich auch deren Konzepte erlernen, um die Sie sich bei natürlichen Sprachen nicht kümmern müssen. Bei imperativen Programmiersprachen wie Java sind dies z.B. Variablen, Anweisungen, Prozeduren. Alleine durch das Auswendiglernen von Vokabeln und Grammatikregeln schaffen Sie es jedoch nicht, mit der Programmiersprache umgehen zu können. Sie müssen die Sprache auch konsequent einsetzen und durch ständiges üben Erfahrungen sammeln. Deshalb ist die Bearbeitung der übungsaufgaben in diesem Kurs verpflichtend.
Das Erlernen einer Programmiersprache ist nicht schwierig, da das Vokabular und die Grammatik nicht besonders umfangreich sind. Was sehr viel schwieriger ist, ist das Programmieren lernen, d.h. das Erlernen des Programmentwicklungsprozesses:
Der Ausdruck "Programmieren" bezeichnet also im engen Sinn lediglich das Erstellen eines Programms. Oft bezeichnet man jedoch mit "Programmieren" alle Tätigkeiten eines Programmierers, die von der Problemstellung zur fertigen Lösung führen. Das Problemlösen mit Hilfe eines Computers umfaßt folgende Stufen:
Ein Programm ist also eine eindeutige, logische Folge von (genormten) bekannten Bearbeitungsschritten endlicher Länge. Beim Computer richten sich diese Befehle an das Steuerwerk. Die Zahl der verschiedenen Befehle ist bei den Computern aus verständlichen Gründen beschränkt. Als Beispiel soll ein Algorithmus aus der Mathematik betrachtet werden: Die näherungsweise Berechnung des Kreisumfangs.
Algorithmus "Kreisumfang":
(K1) Nimm den Radius aus der Eingabe.
(K2) Multipliziere den Radius mit 2,0 und nenne das Ergebnis
'Durchmesser'.
(K3) Multipliziere den Durchmesser mit 3,1415926 und bringe das
Ergebnis in die Ausgabe.
Dieser Algorithmus liefert beispielsweise zur Eingabe 7,0 die Ausgabe 43,982296. Wenn der Computer das Multiplizieren nicht beherrscht, dann müßte man ihm noch einen Algorithmus, ein Verfahren, für deren Durchführung geben.
Algorithmus "Multiplikation":
(M1) Schreibe die beiden Zahlen aus der Eingabe nebeneinander.
(M2) Nimm die erste Ziffer der zweiten Zahl.
(M3) Schreibe die erste Zahl sooft untereinander, wie die Ziffer
der zweiten Zahl angibt, und zwar so, daß die letzte Ziffer
unter der betrachteten Ziffer der zweiten Zahl steht. Für den
Fall, daß besagte Ziffer 0 ist, schreibe 0.
(M4) Falls noch Ziffern in der zweiten Zahl vorhanden sind, nimm
die nächste Ziffer und gehe nach (M3).
(M5) Addiere alle mit (M3) erzeugten Zahlen.
(M6) Zähle bei dem Ergebnis soviele Stellen von rechts ab, wie
beide Eingabewerte zusammen an Stellen hinter dem Komma besitzen.
Setze hier das Komma im Ergebnis.
(M7) Bringe dies Endergebnis in die Ausgabe.
Beispiel für die Eingaben 3,14 und 14,0:
3,14 x 14,0
-----------
314
314
314
314
314
0
----------
43,960
Die Ausgabe ist 43,960. Dieser Algorithmus für die Multiplikation kann dann überall dort verwendet werden, wo "multipliziere" steht. Aus dieser Tatsache lassen sich zwei Erkenntnisse gewinnen:
Versuchen Sie doch einmal, den Algorithmus "Kreisumfang" so umzuformen, daß er überall dort, wo multipliziert wird, der Algorithmus "Multiplikation" als "Unteralgorithmus" aufgerufen wird. Auf dieser Idee beruht die Theorie der Softwareentwicklung. Komplizierte und komplexe Strukturen und Tätigkeiten werden durch bekannte Strukturen und einfachere Unteralgorithmen realisiert. Sie werden auch sehen, daß auch Programme auf entsprechend konstruierte "Unterprogramme" zurückgreifen können. Und es sei hier schon angemerkt, daß diese Möglichkeit die wichtigste und mächtigste Eigenschaft der Programmiersprachen ist. Die oben erwähnten komplizierten Strukturen sind genau jene, die der menschlichen Denkweise entsprechen. Zum Beispiel die Struktur:
"Wenn die Bedingung erfüllt ist, dann tue dies; sonst tue jenes."
Daß dabei eine ganze Reihe von Handlungen nacheinander
erforderlich ist, wird dem Menschen gar nicht bewußt. Zuerst
muß die Bedingung ausgewertet werden. Dazu müssen alle
Informationen beschafft werden, die zu dieser Auswertung nötig
sind. Danach müssen sie verarbeitet werden, bis festgestellt
ist, ob die Bedingung erfüllt ist. Erst jetzt können die
entsprechenden Tätigkeiten ausgeführt werden, was unter
Umständen wieder recht kompliziert werden kann.
Die höheren Programmiersprachen bieten also schon als
Grundoperationen recht komplizierte Dinge an. Ebenso werden
komplizierte Denkstrukturen angeboten, die, wie gesagt, dem
menschlichen Denken sehr verwandt sind.
Sie sind normierte Sprachen, die der Beschreibung von Algorithmen
dienen. Genaueres über solche "algorithmische
Sprachen" sollen Sie im folgenden Abschnitt erfahren. Durch
die Anpassung an die menschliche Denkweise wird bei den
Programmiersprachen das Schreiben von Algorithmen erleichtert;
andererseits läßt sich aus einem Programm eine Beschreibung in
natürlicher Sprache zurückgewinnen.
Die fest vorgeschriebenen Teile der Programmiersprachen orientieren sich meist am Englischen. So wird aus der Struktur
"Wenn ... dann ... sonst ..."
in der Programmiersprache C zu
"if (..) { ... } else { ... }
Allerdings wurden bei der Konstruktion der höheren
Programmiersprachen die Ausdrucksmöglichkeiten so ausgewählt,
daß Doppeldeutigkeiten unmöglich sind. Dazu wird die Form der
Ausdrucksmöglichkeiten vorgeschrieben und ihre Bedeutung
eindeutig und genau erklärt.
Der entscheidende Punkt bei den höheren Programmiersprachen ist
aber folgender. Dadurch, daß die Form der Programme, die in
höheren Programmiersprachen geschrieben sind, bestimmten, festen
Regeln genügt, können diese Regeln automatisch, also auch von
einem Computer (mit einem entsprechenden Programm) analysiert
werden. Da zu jeder erkannten Form die zugehörige Bedeutung
genau festgelegt ist, kann das Programm automatisch (d. h. wieder
von Computer) auf eine andere Form mit der gleichen Bedeutung,
jedoch mit einfacheren Grundoperationen und Grundstrukturen
umgewandelt werden.
Die Umwandlung kann so erfolgen, daß sich die Form völlig, die
Bedeutung aber überhaupt nicht ändert. Wenn nun diese neue Form
in einer, von dem Computer ausführbaren Sprache
(Maschinensprache) besteht, so wurde eine höhere
Programmiersprache (die der Mensch versteht) in die
Maschinensprache (die der Rechner versteht) übersetzt.
Die einfachste Programmiersprache besteht aus einem Satz von Befehlen. Dies sind die eingebauten Kommandos, sie sind in ihrer Wirkung vergleichbar mit dem, was Sie mit den Tasten Ihres Taschenrechners auslösen. Mit diesen Befehlen lassen sich u.a. arithmetische Operationen ausführen und Werte für die Dauer der Rechnung speichern. Auch gibt es Befehle, mit denen man Werte vergleicht und damit entscheidet, was als Nächstes gemacht wird. Ein Teil der Befehle wird benötigt, wenn man Daten im Speicher ablegen oder von dort zurückholen will. Besondere Befehle befassen sich damit, in einem Programm Sprünge auszuführen, d.h. Programmteile, die im Moment nicht ausgeführt werden sollen, zu überspringen, oder auch um an eine bereits ausgeführte Stelle im Programm zurückzuspringen und sie so zu wiederholen.
Wenn man die Befehle durchnumeriert, erhält man eine
Maschinensprache; das ist der einfachste Programmiercode. in
diesem Code kann die Nummer eines Befehls als sein Name verwendet
werden. Ein Maschinensprachenprogramm ist nichts weiter als eine
lange Folge von solchen Codewörtern.
In einer Maschinensprache zu programmieren, ist nicht schwer,
aber unglaublich mühsam. Zum Glück hatte einer der frühen
Programmierer eine brillante Idee, wie man sich die Arbeit
erleichtern kann. Wenn man ein Maschinenprogramm schreibt, das
kurze Buchstabenfolgen erkennen und in zugehörige
Maschinenbefehle übersetzen kann, dann braucht der Programmierer
nicht die Codierung der Befehle in der Maschinensprache zu
lernen. Stattdessen kann er jeden Maschinenbefehl als
"Klartext-Kürzel" (engl. mnemonic) hinschreiben. Die
entsprechenden Übersetzungsprogramme, man nennt sie Assembler,
wurden bald für alle Computer entwickelt.
Das Programmieren in einer Assemblersprache ist etwas weniger
mühsam. Ein Programm ist eine Folge von Kommandos, die jeweils
aus zwei bis vier Buchstaben bestehen und denen Adressen von
Speicherplätzen angefügt werden. Zum Beispiel bedeutet das
Kommando
ADD R2, R6
Addiere den Inhalt des Speicherplatzes R2 zum Inhalt von R6 und speichere die Summe in R6. In welche Befehle dieses Kommando übersetzt wird, können Sie sich verdeutlichen, wenn Sie die Operation an einem Taschenrechner (der einen Speicher hat) mit einer Tastenfolge ausführen.
Noch bis zum Ende der fünfziger Jahre bestand das Programmieren tatsächlich aus der minutiösen Übersetzung von Befehlen in binär, oktal oder sexadezimal dargestellte Zahlen und deren Aneinanderreihung zu einem sinnvollen Programm. Man bezeichnet diese Tätigkeit mit Codieren. Die Unzulänglichkeiten dieses Verfahrens traten aber mit dem Schneller- und Größerwerden der Computer mehr und mehr hervor:
Diese Unzulänglichkeiten führten unter Anderem zur Entwicklung sogenannter "höherer Programmiersprachen", die zum Einen nach den Gewohnheiten und Fähigkeiten des Menschen im Ausdruck seiner Gedanken ausgerichtet sind und oftmals in ihrer Art und im Umfang am Anwendungsgebiet ausgerichtet sind (und nicht an der unterlegten Hardware).
Mit den Kommandowörtern der Assemblersprache war ein erster Schritt getan, die Programme für den Menschen verständlich zu schreiben. Man wählte Bezeichnungen, die wie ADD auf die Operation hinwiesen. Doch warum sollte man sich auf Wörter mit drei Buchstaben beschränken? Es wäre noch leichter, Programme zu schreiben, wenn man näher an der Umgangssprache formulieren könnte. Nun wiederholte sich der gleiche Schritt, der von Maschinensprachen zu Assemblersprachen geführt hatte. Man entwickelte (kompliziertere) Übersetzungsprogramme, sie heißen Interpreter und Compiler. Diese neuen Programme übersetzten zunehmend komplexe Buchstabenfolgen in eine Form, die der Computer verstehen kann. Damit konnten die Programme in einer Sprache geschrieben werden, die aus Wörtern der Umgangssprache bestand.
Meist tun diese Programme noch mehr, als nur zu übersetzen: Es meldet dem Programmierer auch Stellen in seinem Programm, die nicht den Konventionen der Sprache genügen - Programmierfehler also. Ein Maschinenprogramm läßt sich nur noch unter den größten Schwierigkeiten verstehen. Ein Beispiel soll das verdeutlichen:
a) In natürlicher Sprache: Schreibe das Wort "PASCAL"
b) In der höheren Sprache C: printf ("PASCAL");
c) In der Maschinensprache des programmierbaren Taschenrechners TI-59:
69 00 03 03 01 03 03 06 01 05 01 03 69 01
02 07 00 00 00 00 00 00 00 00 69 02 69 05
Wie Sie sehen, bieten die höheren Programmiersprachen ganz entscheidende Vorteile. Wir habe also kennengelernt:
Die Programmiersprachen sind in erster Linie dazu da die Lösung einer Aufgabe in computergerechter Form zu formulieren. Die Lösung einer hier betrachteten Aufgabe soll also durch einen Algorithmus dargestellt in einer Programmiersprache beschrieben sein. Wie muß eine solche Programmiersprache (Algorithmische Sprache) nun aufgebaut sein damit sie geeignet ist beliebige Algorithmen darzustellen?
Fangen wir gleich mit dem Problem der Normierung an. In jeder
beliebigen Sprache, sei es die deutsche, englische, italienische,
griechische oder japanische Sprache, wird ein Text als Folge von
Zeichen niedergeschrieben. Die Menge dieser Zeichen ist bei den
verschiedenen Sprachen nicht immer die gleiche, es gibt auch
nicht immer gleich viel Zeichen. Aber für jede Sprache existiert
eine endliche Menge von Zeichen, die zur Niederschrift eines
Textes verwendet werden dürfen.
Wenn man diese Menge von Zeichen in einer festgelegten
Reihenfolge ordnen kann, spricht man von einem Alphabet. Es ist
aber noch nicht möglich, einenText zu schreiben, wenn man nur
das Alphabet kennt. Wenn Sie zum Beispiel unser Alphabet
betrachten, dann ergibt:
"qwesdfcvxwcbvhgnrzrrdegfbcvdgftejsmbljouri" noch
keinen Text.
Was man benötigt, sind Elemente der Sprache, gebildet aus den
Zeichen des Alphabets. Gebilde, die durch aneinanderreihen von
Zeichen eines Alphabets nach irgendwelchen Regeln entstehen,
heißen Worte. Worte sind also Zeichenreihen. Ein Wort unterliegt
gewissen Bildungsregeln. "3az45" ist kein Wort der
deutschen Sprache, da es gegen die Regeln der deutschen
Wortbildung verstößt. Das einzelne Wort lebt wiederum von der
Kombination mit anderen Worten. Eine Kombination von Worten
heißt Satz.
Zeichen + Regeln --> Wort
Wort + Regeln --> Satz
Aus einer festgelegten Menge von Zeichen werden nach bestimmten Regeln Worte gebildet, die selbst wieder nach festen Regeln zu Sätzen vereinigt werden. Ein Text besteht dann aus einer Folge von Sätzen. Dieser formale Aufbau einer Sprache heißt Grammatik oder Syntax der Sprache. Die Syntax beschreibt im wesentlichen die Regeln, die Sie beachten müssen, damit die Form des Textes richtig ist.
Die Syntax ist auch bei Worten wie BARTSCHE, DRAUDELN,
GRUBBEND oder ZERWANKELMÜTIGKEIT und Sätzen folgender Art
völlig in Ordnung: DER COMPUTER BETRITT DEN RASEN. DER HIMMEL
WEIGERT SICH, GEMÄß VERORDNUNG 25A DEN DUSCHVORHANG ZU WABELN.
ES IST PHANTASTISCH, WIE UNMÖGLICH ES IST, DAß EINE MENGE VON
WÖRTERN KEINEN SINN ERGIBT. Aber diese Worte und Sätze, die von
der Syntax her richtig (also syntaktisch korrekt) sind, ergeben
keinen Sinn, keinen Inhalt, sie bedeuten nichts. Der Sinngehalt
eines Satzes oder Wortes muß also ebenfalls festgelegt werden.
Das bedeutet, wenn Sie ein Wort schreiben, müssen Sie die
Bedeutung des Wortes kennen. Wer MAUS schreibt und dabei an einen
großen, grauen Dickhäuter denkt, verstößt gegen jene Regeln
der Sprache, die für den Sinngehalt wesentlich sind, die Regeln
der Semantik. Mit der Erkenntnis, daß die Syntax einer
Sprache ohne eine ausreichende Definition der Semantik nicht für
die Normierung der Sprache ausreicht, ist die erste der beiden
anfangs gestellten Fragen beantwortet. Es stellt sich jetzt die
Frage, was in einer normierten Sprache alles vorhanden sein muß,
um Algorithmen zu beschreiben.
Also benötigt eine algorithmische Sprache Möglichkeiten zur
Beschreibung der Eingabe- und Ausgabedaten und zur Beschreibung
der Verarbeitungstätigkeit. Die Beschreibung der Daten muß die
Art der Daten, (z.B.: Zahlen, Striche, Texte, usw.) sowie die
Anzahl der Daten enthalten. Die Beschreibung der Tätigkeiten
soll der menschlichen Denkweise möglichst gut angepaßt sein,
muß aber trotzdem normiert sein. Dazu ein Beispiel:
Eine Normierung tut not, denn alle diese Sätze haben dieselbe Bedeutung. Also entwerfen wir die Syntaxregel:
WENN <Bedingung> DANN <Erfüllt-Aktion> SONST <Nicht-erfüllt-Aktion>
Dann lautet das Beispiel:
WENN es regnet DANN ich nehme Schirm mit SONST ich lasse Schirm zu Hause;
Es gibt nur eine Möglichkeit, das ganze noch anders darzustellen, und zwar:
WENN es regnet nicht DANN ich lasse Schirm zu Hause SONST ich nehme Schirm mit;
Aufgrund der Normierung der algorithmischen Sprache bleibt von den vielen Ausdrucksvariationen der natürlichen Sprache nur noch eine einzige Version übrig. Abkürzungen und Umstellungen sind nicht mehr zulässig. Die Sätze müssen immer in der vorgeschriebenen Reihenfolge aufgeschrieben und die Wörter immer ausgeschrieben werden. Wie in der natürlichen Sprache gibt es auch in einer algorithmischen Sprache zahlreiche festgelegte Worte, die sich nicht auf Gegenstände oder Tätigkeiten beziehen, sondern der Verbindung der Worte zu Sätzen dienen. Im Deutschen sind dies zum Beispiel die Präpositionen oder die Konjunktionen; im letzten Beispiel waren es die Worte WENN, DANN und SONST. Diese Worte dienten der Verbindung der Sätze: es regnet ich nehme Schirm mit ich lasse Schirm zu Hause Die drei "Schlüsselworte" verbinden die genannten Sätze in festgelegter Weise; man nennt sie daher auch Wortsymbole. Die im Beispiel gewählte Syntax:
WENN <Bedingung> DANN <Erfüllt-Aktion> SONST <Nicht-erfüllt-Aktion>
wurde so gewählt, daß auf Grund der Kenntnis der deutschen Sprache der Sinn des "Gebildes" ungefähr klar wird. Bedingung steht für einen Satz, der nach anderen Regeln gebildet werden muß, wie die Sätze hinter den Worten DANN und SONST und der, wie es von einer Bedingung erwartet wird, entweder erfüllt oder nicht erfüllt sein muß. Ist die Bedingung erfüllt, wird die Tätigkeit: <Erfüllt-Aktion> ausgeführt, im anderen Fall wird die mit <Nicht-Erfüllt-Aktion> bezeichnete Aktion ausgeführt. Somit hätten wir die Syntax und die Semantik unseres Beispiels definiert. Natürlich muß auch die Reihenfolge der Bearbeitung festgelegt werden: Prüfe zuerst die Bedingung und führe dann die entsprechende Tätigkeit aus. Die Wortsymbole sind also festgelegte Worte mit fest definierter Bedeutung. Sie werden in den algorithmischen Sprachen meist durch Symbolzeichen wie "+" für die Addition oder "/" für die Division ergänzt. Auch die Bedeutung dieser Zeichen ist festgelegt und nicht zu ändern. Die Menge aller Wort- und Zeichensymbole bildet zusammen mit der Beschreibung von Syntax und Semantik die Definition einer algorithmischen Sprache. Die Symbole dürfen auch in keiner anderen Bedeutung verwendet werden als in der festgelegten. Die Zahl der Symbole sollte so klein wie möglich, aber trotzdem so universell wie möglich sein. Die Vorteile von wenigen, der menschlichen Denkweise angepaßten Symbolen und Zeichen liegt auf der Hand:
Mit den Symbolen alleine kommt die algorithmische Sprache aber
immer noch nicht aus, sie möchten ja den Sätzen einen Inhalt
geben und den Dingen die Sie behandeln und den Tätigkeiten einen
Namen geben. Erinnern Sie sich noch an das Verfahren
"S". "S" war dabei ein völlig willkürlich
gewählter Name für das Verfahren. Anschließend wurde für das
gleiche Verfahren ein anderer, ebenfalls willkürlicher, aber
einleuchtenderer Name gewählt: "Verfahren zur Bündelung
von Strichen in Fünfergruppen". So wie dort die Namen der
Verfahren frei gewählt wurden, können auch die Namen für
Dinge, Daten, Personen, Verfahren und Tätigkeiten in einer
algorithmischen Sprache frei gewählt werden. Damit Sie sich bei
den frei gewählten Bezeichnungen später auch auskennen, sei
Ihnen hier erklärt, was mit einer solchen Bezeichnung eigentlich
benannt wird:
Der Gegenstand der Benamselung wird zuerst durch seinen Namen und
seine Art bekanntgemacht (z. B.: Zahl, Tätigkeit, Person, Menge,
Buchstabe, Operation, Unteralgorithmus, usw.). Ferner wird er
charakterisiert durch die Tätigkeiten, die auf ihn angewendet
werden. Steht zum Beispiel irgendwo "X/12" und jemand
fragt: "Was ist X?", können Sie nur antworten:
"Es handelt sich um irgendetwas, das durch 12 geteilt
wird". So eine Antwort ist aber recht unbefriedigend. Als
Lehre sollten Sie daraus ziehen, alle Dinge sinnvoll bezeichnen
und zusätzliche Erklärungen und Kommentare für den Leser
hinzufügen. Beispiel:
| Schlechter Stil: | Y = X/12 |
| Guter Stil: | EIERKARTONZAHL = EIERZAHL/12 |
Das Beispiel enthält die frei gewählten Bezeichnungen: X, Y, EIERKARTONZAHL, EIERZAHL. Es fehlt nur noch die Einordnung der Zahl 12. Es handelt sich hierbei um eine allgemein übliche und allseits bekannte Bezeichnung. Sie wird daher auch in algorithmischen Sprachen als allgemein üblich betrachtet und Standardbezeichnung genannt. Die Ausdrucksmöglichkeiten einer algorithmischen Sprache werden also durch Wortsymbole, Symbolzeichen, Standardbezeichnungen und frei wählbare Bezeichnungen im Rahmen einer (computerübersetzbaren) Syntax festgelegt. Die Semantik der Symbole und Standardbezeichnungen ist vordefiniert und wird vom "Compiler" schrittweise in eine Maschinensprache übersetzt, während die Semantik der frei wählbaren Bezeichnungen von der durch die Syntax festgelegten Deklarationen (Bekanntmachungen) festgelegt wird.
Ideal ist es, wenn eine solche, syntaktisch festgelegte Form mit ihrer Semantik dem Menschen, der die Verarbeitungsvorschrift verfaßt, leicht verständlich und zugänglich ist. Die erzeugten Verarbeitungsvorschriften müssen lesbar und der menschlichen Denk- und Ausdrucksweise angepaßt sein und trotzdem normiert und computerübersetzbar. Seit Mitte der sechziger Jahre werden Programmiersprachen (= algorithmische Sprachen) entwickelt.
FORTRAN (FORmula TRANSlator) ist eine der ersten und am weitesten verbreiteten Sprachen. Sie ist hauptsächlich für wissenschaftlich-technische Anwendungen bestimmt.
ALGOL (ALGOrithmic Language) ist für die Bearbeitung mathematischer Probleme und für wissenschaftliche Anwendungen besonders geeignet. Die Sprache wurde ständig weiter ausgebaut und verbessert (ALOGOL 60, ALGOL 68).
COBOL (COmmon Business Oriented Language) wurde entwickelt als Standardsprache für kommerzielle Berechnungen. Manche Anweisungen beziehen sich unmittelbar auf Lohnabrechnung oder Rechnungswesen.
BASIC (Beginners All-purpose Symbolic lnstruction Code) ist eine einfache Sprache, die benutzt wird, um in Computer-Programmierung einzuführen. Sie ist einfach zu erlernen, geht aber nicht sehr weit. Ihre Schwächen sind Grund dafür, daß sie kaum noch im Unterricht eingesetzt wird.
LISP (LIST Processing language) wird weithin benutzt in Programmen, mit denen Zeichen von mathematischen Symbolen bis hin zu den Zeichen der Umgangssprache zu verarbeiten sind. Eine Hauptanwendung liegt im Bereich der Untersuchungen zur künstlichen Intelligenz.
Pascal (benannt nach dem Mathematiker und Philosophen Blaise Pascal) wurde für den Einsatz im Informatikunterricht entwickelt. Diese Sprache gehört zur Algol-Familie und eignet sich besonders für wissenschaftliche Probleme. Da Pascal als Lehr-Programmiersprache gedacht war, soll die Entwicklung dieser Sprache etwas genauer dargestellt werden. Niklaus Wirth verfolgte dabei u.a. die folgenden Ziele:
In diesem Sinne ist Pascal so etwas wie eine
alIgemeinverständliche Sprache für das Programmieren geworden.
Sie läßt sich leicht erlernen und bildet eine gute Grundlage
für die Aneignung anderer Sprachen. Man kann sagen: Wer Pascal
beherrscht, lernt BASIC an einem Nachmittag. Und für FORTRAN
braucht er nicht mehr als ein bis zwei Wochen.
Einer der Vorzüge von Pascal gegenüber den früher entwickelten
Sprachen besteht darin, daß man die Programme fast mit den
gleichen Formulierungen wie die Lösung des Problems schreiben
kann. Die reservierten Wörter, sie bilden das Gerüst von
Pascal, sind der englischen Umgangssprache entnommen. Wer
Englisch kann, liest ein geschickt gemachtes Pascal-Programm wie
eine umgangssprachliche Beschreibung des Weges, der das gestellte
Problem löst. Und wenn man ein Problem aufbereitet, gelangt man
sehr schnell von der umgangssprachlichen Formulierung zum
Pascal-Programm.
C Die Entwicklung der Programmiersprache C ist eng mit
der des Betriebssystems UNIX verknüpft. Nachdem die erste
UNIX-Version noch in Assembler erstellt worden war (1969),
entwickelte Ken Thomson 1970 die Sprache B zur Irnplementierung
eines UNIX-Systems für eine PDP-7-Maschine. Aus der mit zu
vielen Schwächen behafteten Sprache B entwickelte Dennis Ritchie
1972 C. Seit 1973 ist das Betriebssystem UNIX fast vollständig
in C geschrieben. Zunächst gab es keinen offiziellen
Sprachstandard. Statt dessen erreichte die Sprachdarstellung in
einem Lehrbuch - deutsch: Kemighan, Ritchie; Programmieren in C,
Hanser Verlag 1983 - den Status eines Quasi-Standards
(Kernighan-Ritchie-Standard). Kleinere Erweiterungen und
Verbesserungen führten zum ANSI-Standard. Die Sprache C++ wurde
Anfangs der 80er Jahre von Bjarne Stroustrup an den Bell
Laboratories entwickelt. Es handelt sich dabei um einen Zusatz
für C.
C ist eine Sprache der 3. Generation (strukturierte Sprache) und
gehört neben FORTRAN und Pascal zu den wichtigsten Höheren
Programmiersprachen im Ingenieurbereich. Die wesentlichen
Merkmale der Sprache sind:
Was oben als Vorteil erscheint, erweist sich als Nachteil bezüglich der Erlernbarkeit als "Erstsprache". Die "kappen Befehle" könnte man etwas böswillig auch als kryptisch bezeichnen und das "klare Sprachkonzept" verlangt vom Programmierer Grundkenntnisse über Aufbau und Arbeitsweise von Computern, deutlich mehr als Pascal und FORTRAN. Allerdings steigen diese Grundkenntnisse bei der jungen Generation von Jahrgang zu Jahrgang. Fast jeder (interessierte) kann mit einem PC umgehen. Viele haben bereits gelernt, kleinere Probleme in Basic oder Pascal zu lösen. Und so kann man es heute wagen, ernsthaft mit C zu starten. Die Mühe lohnt sich!
Mittlerweile gibt es neben den vorgenannten aufschreibungsorientierten Programmiersprachen auch graphische Programmiersprachen. Populäre Firmenübergreifende Standards sind mir unbekannt. Idee ist es mittles graphischer Verknüpfung von Piktogrammen, die stellvertretend jeweils unterschiedliche Grundfunktionen darstellen, ein Programm änlich einer Zeichnung zu entwerfen. LabView ist ein solches Produkt mit einer solchen Programmierumgebung. LabView wird in der Meßtechnik häufig eingesetzt. Virtuelle Meßgeräte (Softwarefunktionen), wie Voltmeter, Ampermeter, Spektrumsanalysator etc werden als Piktogramme dargestellt und der Meßaufbau, die Verkabelung, durch graphische Linien, die die Geräte an den unterschiedlichen Buchsen verbinden. Meßvorgänge werden per Knopfdruck in der Graphik ausgelöst, und die Ergebnisse graphisch dargestellt. Vorteil dieser Art der Programmierung ist, daß sich der Anwender voll auf seine 'Welt' konzentrieren kann, ohne eine Programmiersprache lernen zu müssen. Ob sich diese Art der Programmierung auch in anderen Bereichen durchsetzt bleibt abzuwarten.
Bemerken Sie den Fehler, der auftreten würde, wenn der Computer diese Anweisungsfolge pedantisch ausführt (und das tut er tatsächlich!)? Beide Variablen, die für den Zähler und die für den Nenner, hätten zum Schluß den gleichen Wert, den des ursprünglichen Nenners. Das liegt daran, daß man den Wert des ursprünglichen Zählers nicht zwischengespeichert hat. Ein Algorithmus für den Computer muß das ausdrücklich vorsehen:
Lösung 1:
Prüfe, ob X den Wert 2 besitzt.
Falls ja, setze X auf 1.
Setze X auf 2.
Lösung 2:
Prüfe, ob X den Wert 2 besitzt.
Falls ja, setze X auf 1.
Sonst setze X auf 2.
Lösung 3:
Setze X auf das Ergebnis der Rechnung 3 - X.
Welche Lösung ist richtig? Erstaunlicherweise keine! Bei der ersten Lösung hat X nach Ablauf immer den Wert 2. Die beiden anderen Lösungen scheinen beide richtig, wobei die dritte zwar elegant erscheint, aber für den Leser des Algorithmus schwerer verständlich ist. Sie sind aber deshalb falsch, weil nicht überprüft wird, ob X einen der beiden zulässigen Werte (1,2) besitzt. Richtig wäre also:
Lösung 2:
Prüfe, ob X den Wert 1 oder den Wert 2 besitzt.
Falls nein, melde den Fehler und beende die Arbeit.
Prüfe, ob X den Wert 2 besitzt.
Falls ja, setze X auf 1.
Sonst setze X auf 2.
Diese Beispiele sollen Sie nicht in Panik versetzen. Sie brauchen nicht an Ihren Fähigkeiten, Algorithmen für den Computer zu entwerfen, zu verzweifeln. Diese Fähigkeiten sind keineswegs unveränderlich, sie lassen sich sehr wohl entwickeln und trainieren.
Es darf die systematische Arbeitsweise (Arbeitsdiziplin) nicht vergessen werden: Lernen und Verbessern erfordert einen Rückkopplungsprozeß. Allgemein: Dazu definiert sich der Ingenieur ein quantitativ erfaßbares Ziel und versucht es zu erreichen. Dabei ist es wichtig ein objektives Maß (Metrik) dafür zu haben wie nahe er dem Ziel ist. Aus der Abweichung ergibt sich Steuerungsbedarf im Bestreben dem Ziel näher zu kommen. Dieser interative Prozeß der Zielanäherung kann nur verbessert (Optimierung) und an Andere weitergegeben (Erfahrungsaustausch) werden, wenn er dokumentiert und objektiv nachvollziehbar (entspricht in der Mathematik: 'nachrechenbar' ) ist. Für die Softwareentwicklung bedeutet dies: Alle Arbeitsschritte, Metriken und Denkprozesse müssen nachvollziehbar (schriftlich) dokumentiert sein, inklusive der getroffenen technischen Entscheidungen. Nur so kann man selbst und alle zusammen an Können gewinnen.
Die Problemlösung läft also meist nach folgendem Schema ab:
Das wichtigste ist beinahe vergessen worden: Die Kundenanforderungen! Es
ist erstaunlich wie viel Software am eigentlichen Nutzer vorbei entwickelt
wird, nur weil der Entwickler denkt er weiß, was der Kunde braucht, und
sich nicht erkundigt, was der Kunde wirklich will. Oftmals verliert während
des Entwurfs der Entwickler den Kunden aus den Augen und er baut technikverliebt
nicht gewollte Komplexität ins Programm ein, die meistens viel Zeit beim
Testen kostet. Eine erste Faustformel könnte lauten:
| KISS (Keep it simple and smart!) und nicht Quick-And-Dirty! |
 Zum Inhaltsverzeichnis |
 Zum nächsten Abschnitt |