Einführung in die praktische Informatik Skript PDF

lOMoARcPSD|34983113 Einführung in die praktische Informatik Einführung in die Praktische Informatik (Ruprecht-Karls-Universität Heidelberg) Scanne, um auf Studocu zu öffnen Studocu wird von keiner Universität gesponsert oder unterstützt. Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Einführung in die Praktische Informatik Peter Bastian Interdisziplinäres Zentrum für Wissenschaftliches Rechnen, Universität Heidelberg Im Neuenheimer Feld 368, 69120 Heidelberg, [email protected] basierend auf der überarbeiteten und erweiterten Version von: Nicolas Neuß Universität Erlangen-Nürnberg, Department Mathematik, Lehrstuhl Angewandte Mathematik 3, Haberstr. 2, 91058 Erlangen, [email protected] Version 2.0 Erstellt: 24. Juli 2014 URL für die Vorlesung (enthält die Beispielprogramme): http://conan.iwr.uni-heidelberg.de/teaching/info1_ws2014/ Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Inhaltsverzeichnis 1 Grundbegriffe 7 1.1 Formale Systeme: MIU............................. 7 1.2 Turingmaschine................................. 10 1.3 Problem, Algorithmus, Programm....................... 14 1.4 Berechenbarkeit und Turing-Äquivalenz.................... 15 1.5 Reale Computer................................. 16 1.6 Programmiersprachen.............................. 19 1.7 Komplexität von Programmen......................... 19 2 Funktionale Programmierung 21 2.1 Auswertung von Ausdrücken.......................... 21 2.2 Funktionen................................... 23 2.3 Selektion..................................... 24 2.4 Syntaxbeschreibung mit Backus-Naur Form................. 25 2.5 Das Substitutionsmodell............................ 28 2.6 Linear-rekursive Prozesse............................ 29 2.7 Linear-iterative Prozesse............................ 30 2.8 Baumrekursion................................. 31 2.9 Größenordnung................................. 35 2.10 Wechselgeld................................... 37 2.11 Der größte gemeinsame Teiler......................... 39 2.12 Zahlendarstellung im Rechner......................... 41 2.13 Darstellung reeller Zahlen........................... 42 2.14 Wurzelberechnung mit dem Newtonverfahren................. 44 2.15 Fortgeschrittene funktionale Programmierung................ 46 3 Prozedurale Programmierung 48 3.1 Lokale Variablen und die Zuweisung...................... 48 3.2 Syntax von Variablendefinition und Zuweisung................ 50 3.3 Anweisungsfolgen (Sequenz).......................... 51 3.4 Bedingte Anweisung (Selektion)........................ 53 3.5 While-Schleife.................................. 53 3.6 For-Schleife................................... 54 3.7 Goto....................................... 56 3.8 Formale Programmverifikation......................... 57 3.9 Prozeduren und Funktionen.......................... 60 4 Benutzerdefinierte Datentypen 61 4.1 Aufzählungstyp................................. 61 4.2 Felder...................................... 62 4.3 Zeichen und Zeichenketten........................... 64 4.4 Typedef..................................... 66 4.5 Das Acht-Damen-Problem........................... 67 4.6 Zusammengesetzte Datentypen........................ 69 3 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 5 Globale Variablen und das Umgebungsmodell 74 5.1 Globale Variablen................................ 74 5.2 Das Umgebungsmodell............................. 75 5.3 Stapel...................................... 77 5.4 Monte-Carlo Methode zur Bestimmung von π................ 80 6 Zeiger und dynamische Datenstrukturen 82 6.1 Zeiger...................................... 82 6.2 Zeiger im Umgebungsmodell.......................... 84 6.3 Call by reference................................ 85 6.4 Zeiger und Felder................................ 87 6.5 Zeiger auf zusammengesetzte Datentypen................... 87 6.6 Problematik von Zeigern............................ 88 6.7 Dynamische Speicherverwaltung........................ 89 6.8 Die einfach verkettete Liste.......................... 90 6.9 Endliche Menge................................. 95 7 Klassen 97 7.1 Motivation.................................... 97 7.2 Klassendefinition................................ 98 7.3 Objektdefinition................................. 99 7.4 Kapselung.................................... 99 7.5 Konstruktoren und Destruktoren....................... 100 7.6 Implementierung der Klassenmethoden.................... 101 7.7 Klassen im Umgebungsmodell......................... 103 7.8 Beispiel: Monte-Carlo objektorientiert..................... 103 7.9 Initialisierung von Unterobjekten....................... 106 7.10 Selbstreferenz.................................. 107 7.11 Überladen von Funktionen und Methoden.................. 107 7.12 Objektorientierte und funktionale Programmierung............. 109 7.13 Operatoren................................... 110 7.14 Anwendung: rationale Zahlen objektorientiert................ 111 7.15 Beispiel: Turingmaschine............................ 113 7.16 Abstrakter Datentyp.............................. 119 8 Klassen und dynamische Speicherverwaltung 121 8.1 Klassendefinition................................ 121 8.2 Konstruktor................................... 122 8.3 Indizierter Zugriff................................ 123 8.4 Copy–Konstruktor............................... 124 8.5 Zuweisungsoperator............................... 125 8.6 Hauptprogramm................................ 126 8.7 Default-Methoden................................ 127 8.8 C++ Ein- und Ausgabe............................ 127 9 Vererbung 131 9.1 Motivation: Polynome............................. 131 9.2 Implementation................................. 132 4 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 9.3 Öffentliche Vererbung.............................. 132 9.4 Beispiel zu public/private und öffentlicher Vererbung............ 133 9.5 Ist-ein-Beziehung................................ 134 9.6 Konstruktoren, Destruktor und Zuweisungsoperatoren............ 135 9.7 Auswertung................................... 135 9.8 Weitere Methoden............................... 135 9.9 Gleichheit.................................... 136 9.10 Benutzung von Polynomial.......................... 137 9.11 Diskussion.................................... 138 9.12 Private Vererbung................................ 139 9.13 Methodenauswahl und virtuelle Funktionen.................. 140 10 Abstrakte Klassen 142 10.1 Motivation.................................... 142 10.2 Schnittstellenbasisklassen............................ 143 10.3 Beispiel: geometrische Formen......................... 144 10.4 Beispiel: Funktoren............................... 146 10.5 Beispiel: Exotische Felder........................... 147 10.6 Zusammenfassung................................ 153 11 Generische Programmierung 153 11.1 Funktionsschablonen.............................. 153 11.2 Klassenschablonen............................... 155 11.3 Effizienz generischer Programmierung..................... 162 11.4 Zusammenfassung................................ 170 12 Containerklassen 170 12.1 Motivation.................................... 170 12.2 Listenschablone................................. 171 12.3 Iteratoren.................................... 173 12.4 Doppelt verkettete Liste............................ 175 12.5 Feld....................................... 181 12.6 Stack....................................... 184 12.7 Queue...................................... 185 12.8 DeQueue..................................... 187 12.9 Prioritätswarteschlangen............................ 187 12.10Set........................................ 189 12.11Map....................................... 191 12.12Anwendung: Huffman-Kode.......................... 192 13 Effiziente Algorithmen und Datenstrukturen 197 13.1 Heap....................................... 197 13.2 Sortierverfahren mit quadratischer Komplexität............... 202 13.3 Sortierverfahren optimaler Ordnung...................... 204 13.4 Suchen...................................... 210 14 Beispiel: Logiksimulator 221 14.1 Simulation komplexer Systeme......................... 221 5 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 14.2 Grundbausteine digitaler Schaltungen..................... 222 14.3 Reale Gatter................................... 223 14.4 Schaltnetze................................... 224 14.5 Schaltwerke................................... 225 14.6 Der Simulator.................................. 226 15 Verschiedenes 243 15.1 Rechtliches................................... 243 15.2 Software-Technik (Software-Engineering)................... 244 15.3 Wie werde ich ein guter Programmierer?................... 246 Literatur 247 6 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 1 Grundbegriffe 1.1 Formale Systeme: MIU Im folgenden betrachten wir Zeichenketten über einem Alphabet. Ein Alphabet A ist eine endliche, nichtleere Menge (manchmal verlangt man zusätzlich, dass die Menge geordnet ist). Die Elemente von A nennen wir Zeichen (oder Symbole). Eine endliche Folge nicht notwendigerweise verschiedener Zeichen aus A nennt man ein Wort. Das leere Wort ǫ besteht aus keinem einzigen Zeichen. Es ist ein Symbol für Nichts“. ” Die Menge aller möglichen Wörter inklusive dem leeren Wort wird als freies Monoid A∗ bezeichnet. Beispiel: {0, 1}∗ = {ǫ, 0, 1, 00, 01, 10, 11, 000,...} Formale Systeme dienen der Beschreibung interessanter Teilmengen von A∗. Definition: Ein formales System ist ein System von Wörtern und Regeln. Die Regeln sind Vorschriften für die Umwandlung eines Wortes in ein anderes. Mathematisch: F = (A, B, X , R), wobei A das Alphabet, B ⊆ A∗ die Menge der wohlgebildeten Worte, X ⊂ B die Menge der Axiome und R die Menge der Produktionsregeln sind. Ausgehend von X werden durch Anwendung von Regeln aus X alle wohlgeformten Wörter B erzeugt. Formale Systeme entstanden Anfang des 20. Jahrhunderts im Rahmen der Formalisierung der Mathematik. Ziel war es ein System zu schaffen mit dem alle mathematischen Sätze (wahre Aussagen über einen mathematischen Sachverhalt, möglicherweise in Teilgebieten der Mathematik) aus einem kleinen Satz von Axiomen mittels Regeln hergeleitet werden können (Hilbertprogramm1 ). Wir betrachten hier formale System nur im Sinne formaler Sprachen“, die später noch ” ausführlicher behandelt werden. Beispiel: MIU-System (aus [Hofstadter2 , 2007]) Das MIU-System handelt von Wörtern, die nur aus den drei Buchstaben M, I, und U bestehen. AMIU = {M, I, U}. XMIU = {MI}. 1 David Hilbert, dt. Mathematiker, 1862-1943. 2 Douglas R. Hofstadter, US-amerk. Physiker, Informatiker und Kognitionswissenschaftler, geb. 1945. 7 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 RMIU enthält die Regeln: 1. MxI → MxIU. Hierbei ist x ∈ A∗MIU irgendein Wort oder ǫ. Beispiel: MI → MIU. Man sagt MIU wird aus MI abgeleitet. 2. Mx → Mxx. Beispiele: MI → MII, MIUUI → MIUUIIUUI. 3. xIIIy → xUy (x, y ∈ A∗MIU ). Beispiele: MIII → MU, UIIIIM → UUIM, UIIIIM → UIUM. 4. xUUy → xy. Beispiele: UUU → U, MUUUIII → MUIII. BMIU sind dann alle Worte die ausgehend von den Elementen von X mithilfe der Regeln aus R erzeugt werden können, also B = {MI, MIU, MIUUI,...}. Beobachtung: BMIU enthält offenbar unendlich viele Worte. Problem: (MU-Rätsel) Ist MU ein Wort des MIU-Systems? Oder mathematisch: MU ∈ BMIU ? Systematische Erzeugung aller Worte des MIU-Systems Dies führt auf folgende Baumstruktur: MI 1 2 MIU MII 1 2 2 MIUIU MIIU MIIII 2 2 3 1 2 3 MIUIUIUIU MIIUIIU MIIIIU MIIIIIIII MUI MIU 2 2.... Beschreibung: Ganz oben steht das Anfangswort MI. Auf MI sind nur die Regeln 1 und 2 anwendbar. Die damit erzeugten Wörter stehen in der zweiten Zeile. Ein Pfeil bedeutet, dass ein Wort aus dem anderen ableitbar ist. Die Zahl an dem Pfeil ist die Nummer der angewendeten Regel. In der dritten Zeile stehen alle Wörter, die durch Anwendung von zwei Regeln erzeugt werden können, usw. 8 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Bemerkung: Wenn man den Baum in dieser Reihenfolge durchgeht (Breitendurchlauf), so erzeugt man nach und nach alle Wörter des MIU-Systems. Folgerung: Falls MU ∈ BMIU , wird dieses Verfahren in endlicher Zeit die Antwort liefern. Wenn dagegen MU 6∈ BMIU , so werden wir es mit obigem Verfahren nie erfahren! Sprechweise: Man sagt: Die Menge BMIU ist rekursiv aufzählbar. Frage: Wie löst man nun das MU-Rätsel? Lösung des MU-Rätsels Zur Lösung muss man Eigenschaften der Wörter in BMIU analysieren. Beobachtung: Alle Ketten haben immer M vorne. Auch gibt es nur dieses eine M, das man genausogut hätte weglassen können. Hofstadter wollte aber das Wort MU herausbe- kommen, das in Zen-Koans eine Rolle spielt: Ein Mönch fragte einst Meister Chao-chou: Hat ein Hund wirklich Buddha-Wesen oder nicht?“ ” Chao-chou sagte: Mu.“ ” Beobachtung: Die Zahl der I in einzelnen Worten ist niemals ein Vielfaches von 3, also auch nicht 0. Beweis: Ersieht man leicht aus den Regeln, sei anzahli(n) die Anzahl der I nach Anwen- dung von n Regeln, n ∈ N0. Dann gilt:    1 n = 0, Axiom,  anzahli(n − 1) n > 0, Regel 1, 4, anzahli(n) =   anzahli(n − 1) · 2 n > 0, Regel 2,  anzahli(n − 1) − 3 n > 0, Regel 3 Ist anzahli(n − 1) mod 3 6= 0, so gilt dies auch nach Anwendung einer beliebigen Regel. Von Graphen und Bäumen Der Baum ist eine sehr wichtige Struktur in der Informatik und ein Spezialfall eines Graphen. Definition: Ein Graph G = (V, E) besteht aus einer nichtleeren Menge V , der sogenannten Menge der Knoten, sowie der Menge der Kanten E ⊆ V × V. V × V = {(v, w) : v, w ∈ V } bezeichnet das kartesische Produkt. Teilmengen von V × V bezeichnet man auch als Relationen. 9 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Beispiel: Gleichheit als Relation. Sei V eine Menge (dies impliziert, dass alle Elemente verschieden sind). Setze E= = {(v, w) ∈ V × V : v = w}. Dann gilt v = w ⇔ (v, w) ∈ E=. Wichtige Spezialfälle von Graphen sind: Ungerichter Graph: (v, w) ∈ E ⇒ (w, v) ∈ E. Sonst heisst der Graph gerichtet. Verbundener Graph: Ein ungerichteter Graph heisst verbunden, falls jeder Knoten mit jedem anderen Knoten über eine Folge von Kanten erreichbar ist. Bei einem gerichteten Graphen ergänze erst alle Kanten der Gegenrichtung und wende dann die Definition an. Zyklischer Graph: Es gibt, ausgehend von einem Knoten, eine Folge von Kanten mit der man wieder beim Ausgangsknoten landet. Definition: Wir definieren die Menge der Bäume rekursiv über die Anzahl der Knoten als Teilmenge aller möglicher Graphen. ( {v} , ∅ ) ist ein Baum. Sei B = (V, E) ein Baum, so ist B ′ = (V ′ , E ′ ) ebenfalls ein Baum, wenn V ′ = V ∪ {v}, E ′ = E ∪ {(w, v) : w ∈ V }. Man hängt also einen neuen Knoten an genau einen Knoten des existierenden Bau- mes an. v heisst Kind und w wollen wir geschlechtsneutral als Elter von v bezeichnen. Bemerkung: Auch andere Definitionen sind möglich, etwa als zyklenfreier, verbundener Graph. Bezeichnung: Jeder Baum besitzt genau einen Knoten, der keine eingehenden Kanten hat. Dieser heisst Wurzel. Knoten ohne ausgehende Kanten heissen Blätter, alle anderen Knoten heissen innere Knoten Ein Baum bei dem jeder innere Knoten höchstens zwei Kinder hat heisst Binärbaum. Beobachtung: Ein Baum ist verbunden. Es gibt genau einen Weg von der Wurzel zu jedem Blatt. 1.2 Turingmaschine Als weiteres Beispiel für ein Regelsystem“ betrachten wir die Turingmaschine (TM). ” Diese wurde 1936 von Alan Turing3 zum theoretischen Studium der Berechenbarkeit ein- geführt. 3 Alan Turing, brit. Mathematiker, 1912-1954. 10 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Wissen: Der sogenannte Turing-Preis (Turing Award) ist so etwas wie der Nobelpreis ” der Informatik“. Eine TM besteht aus einem festen Teil ( Hardware“) und einem variablen Teil ( Softwa- ” ” re“). TM bezeichnet somit nicht eine Maschine, die genau eine Sache tut, sondern ist ein allgemeines Konzept, welches eine ganze Menge von verschiedenen Maschinen definiert. Alle Maschinen sind aber nach einem festen Schema aufgebaut. Die Hardware besteht aus einem einseitig unendlich großen Band welches aus einzelnen Feldern besteht, einem Schreib-/Lesekopf und der Steuerung. Jedes Feld des Bandes trägt ein Zeichen aus einem frei wählbaren (aber für eine Maschine festen) Bandalphabet (Men- ge von Zeichen). Der Schreib-/Lesekopf ist auf ein Feld positioniert, welches dann gelesen oder geschrieben werden kann. Die Steuerung enthält den variablen Teil der Maschine und wird nun beschrieben. Diese Beschreibung suggeriert, dass eine TM als eine Art primitiver Computer verstanden werden kann. Dies war aber nicht die Absicht von Alan Turing. Er verstand diese als Gedankenmodell um die Berechenbarkeit von Funktionen zu studieren. a a a a an 1 2 3 4 Band bestehend aus Feldern Schreib/ Lesekopf Steuerung (Programm) Die Steuerung, der variable Teil der Maschine, befindet sich in einem von endlich vielen Zuständen und arbeitet wie folgt: 1. Am Anfang befindet sich die Maschine im sog. Startzustand, das Band ist mit einer Eingabe belegt und die Position des Schreib-/Lesekopfes ist festgelegt. 2. Lese das Zeichen unter dem Lesekopf vom Band. 3. Abhängig vom gelesenen Zeichen und dem aktuellen Zustand der Steuerung führe alle folgende Aktionen aus: Schreibe ein Zeichen auf das Band, bewege den Schreib-/Lesekopf um ein Feld nach links oder rechts, überführe die Steuerung in einen neuen Zustand. 4. Wiederhole diese Schritte solange bis ein spezieller Endzustand erreicht wird. 11 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Die auszuführenden Aktionen kann man in einer Übergangstabelle notieren. Diese Tabelle nennt man auch Programm. Beispiel: Zustand Eingabe Operation Folgezustand 1 0 0,links 2 2 1 1,rechts 1 Jede Zeile der Tabelle beschreibt die auszuführenden Aktionen für eine Eingabe/Zustand- Kombination. Links vom Doppelbalken stehen Eingabe und Zustand, rechts davon Aus- gabe, Bewegungsrichtung und Folgezustand. Beispiel: Löschen einer Einserkette. Das Bandalphabet enthalte nur die Zeichen 0 und 1. Zu Beginn der Bearbeitung habe das Band folgende Gestalt: 1 1... 1 0... n >= 1 Einsen Der Kopf steht zu Beginn auf der Eins ganz links. Folgendes Programm mit zwei Zuständen löscht die Einserkette und stoppt: Zustand Eingabe Operation Folgezustand Bemerkung 1 1 0,rechts 1 Anfangszustand 0 0,rechts 2 2 Endzustand Beispiel: Raten Sie was folgendes Programm macht: Zustand Eingabe Operation Folgezustand Bemerkung 1 1 0,rechts 2 Anfangszustand 0 0,rechts 4 2 1 1,rechts 2 0 1,links 3 3 1 1,links 3 0 0,rechts 2 4 Endzustand TM-Programme lassen sich übersichtlicher als Übergangsgraph darstellen. Jeder Knoten ist ein Zustand. Jeder Pfeil entspricht einer Zeile der Tabelle. Hier das Programm des vorigen Beispiels als Graph: 12 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 0 | 0,rechts 1* 4 1 | 0,rechts 1 | 1,rechts 1 | 1, links 0 | 1, links 2 3 0 | 0, rechts Beispiel: Verdoppeln einer Einserkette. Eingabe: n Einsen wie in Beispiel 1. Am Ende der Berechnung sollen ganz links 2n Einsen stehen, sonst nur Nullen. Wie löst man das mit einer TM? Hier eine Idee: Eingabe 1 1... 1 0 Markiere erste... X 1 1 Y 0 und zweite Kette Kopiere 1... 1 X 1... 1 Y 1... 1 0... schon noch zweite Kette kopiert wird kopieren kopiert Das komplette Programm ist schon ganz schön kompliziert und sieht so aus: 13 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 1* 1 | X, rechts 1 | 1, rechts 2 0 | Y, links 8 Y | Y, links 3 X | 1, rechts Y | 1, rechts 1 | 1, links 1 | 1, links 7 4 1 | X, rechts 0 | 1, links 1 | 1, rechts 1 | 1, rechts 6 5 Y | Y, rechts Bemerkung: Wir erkennen die drei wesentlichen Komponenten von Berechnungsprozes- sen: Grundoperationen Selektion Wiederholung 1.3 Problem, Algorithmus, Programm Definition: Ein Problem ist eine zu lösende Aufgabe. Wir sind daran interessiert Ver- fahren zu finden, die Aufgaben in einer Klasse von Problemen zu lösen. Das konkrete zu lösende Problem wird mittels Eingabeparameter ausgewählt. Beispiel: Finde die kleinste von n ≥ 1 Zahlen x1 ,... , xn , xi ∈ N. Definition: Ein Algorithmus beschreibt wie ein Problem einer Problemklasse mittels einer Abfolge bekannter Einzelschritte gelöst werden kann. Beispiele aus dem Alltag, wie Kochrezepte oder Aufbauanleitungen für Abholmöbel erinnern an Algorithmen sind aber oft nicht allgemein und unpräzise. Beispiel: Das Minimum von n Zahlen könnte man so finden: Setze min = x1. Falls n = 1 ist man fertig. Ansonsten teste der Reihe nach für i = 2, 3,... , n ob xi < min. Falls ja, setze min = xi. 14 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Ein Algorithmus muss gewisse Eigenschaften erfüllen: Ein Algorithmus beschreibt ein generelles Verfahren zur Lösung einer Schar von Problemen. Trotzdem soll die Beschreibung des Algorithmus endlich sein. Nicht erlaubt ist also z. B. eine unendlich lange Liste von Fallunterscheidungen. Ein Algorithmus besteht aus einzelnen Elementaroperationen, deren Ausführung bekannt und endlich ist. Als Elementaroperationen sind also keine Orakel“ erlaubt. ” Bemerkung: Spezielle Algorithmen sind: Terminierende Algorithmen: Der Algorithmus stoppt für jede zulässige Eingabe nach endlicher Zeit. Deterministische Algorithmen: In jedem Schritt ist bekannt, welcher Schritt als nächstes ausgeführt wird. Determinierte Algorithmen: Algorithmus liefert bei gleicher Eingabe stets das gleiche Ergebnis. Ein terminierender, deterministischer Algorithmus ist immer determiniert. Terminierende, nichtdeterministische Algorithmen können determiniert sein oder nicht. Definition: Ein Programm ist eine Formalisierung eines Algorithmus. Ein Programm kann auf einer Maschine (z. B. TM) ausgeführt werden. Beispiel: Das Minimum von n Zahlen kann mit einer TM berechnet werden. Die Zahlen werden dazu in geeigneter Form kodiert (z. B. als Einserketten) auf das Eingabeband geschrieben. Wir haben also das Schema: Problem =⇒ Algorithmus =⇒ Programm. Die Informatik beschäftigt sich damit algorithmische Problemlösungen systematisch zu finden: Zunächst muss das Problem analysiert und möglichst präzise formuliert werden. Dieser Schritt wird auch als Modellierung bezeichnet. Im folgenden entwirft man einen effizienten Algorithmus zur Lösung des Problems. Dieser Schritt ist von zentralem Interesse für die Informatik. Schließlich muss der Algorithmus als Computerprogramm formuliert werden, wel- ches auf einer konkreten Maschine ausgeführt werden kann. 1.4 Berechenbarkeit und Turing-Äquivalenz Es sei A das Bandalphabet einer TM. Wir können uns die Berechnung einer konkreten TM (d.h. gegebenes Programm) auch als Abbildung vorstellen: f : A ∗ → A∗. Hält die TM für einen Eingabewert nicht an, so sei der Wert von f undefiniert. Dies motiviert folgende allgemeine 15 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Definition: Eine Funktion f : E → A heisst berechenbar, wenn es einen Algorithmus gibt, der für jede Eingabe e ∈ E, für die f (e) definiert ist, terminiert und das Ergebnis f (e) ∈ A liefert. Welche Funktionen sind in diesem Sinne berechenbar? Auf einem PC mit unendlich viel Speicher könnte man mit Leichtigkeit eine TM simulie- ren. Das bedeutet, dass man zu jeder TM ein äquivalentes PC-Programm erzeugen kann, welches das Verhalten der TM Schritt für Schritt nachvollzieht. Ein PC (mit unendlich viel Speicher) kann daher alles berechnen, was eine TM berechnen kann. Interessanter ist aber, dass man zeigen kann, dass die TM trotz ihrer Einfachheit alle Berechnungen durchführen kann, zu denen der PC in der Lage ist. Zu einem PC mit gegebenem Programm kann man also eine TM angeben, die die Berechnung des PCs nachvollzieht! Computer und TM können dieselbe Klasse von Problemen berechnen! Bemerkung: Im Laufe von Jahrzehnten hat man viele (theoretische und praktische) Berechnungsmodelle erfunden. Die TM ist nur eines davon. Jedes Mal hat sich herausge- stellt: Hat eine Maschine gewisse Mindesteigenschaften, so kann sie genausoviel wie eine TM berechnen. Dies nennt man Turing-Äquivalenz. Die Church’sche4 These lautet daher: Alles was man für intuitiv berechenbar hält kann man mit einer TM ausrech- nen. Dabei heißt intuitiv berechenbar, dass man einen Algorithmus dafür angeben kann. Mehr dazu in Theoretische Informatik. Folgerung: Berechenbare Probleme kann man mit fast jeder Computersprache lösen. Unterschiede bestehen aber in der Länge und Eleganz der dafür nötigen Programme. (Auch die Effizienz ihrer Ausführung kann sehr unterschiedlich sein, allerdings hängt dieser Punkt sehr von der Compilerimplementation ab.) Bemerkung: Es gibt auch nicht berechenbare Probleme! So kann man z.B. keine TM angeben, die für jede gegebene TM entscheidet, ob diese den Endzustand erreicht oder nicht (Halteproblem). Dieses Problem ist aber noch partiell-berechenbar, d.h. für jede terminierende TM erfährt man dies nach endlicher Zeit, für jede nicht-terminierende TM erfährt man aber kein Ergebnis. 1.5 Reale Computer Algorithmen waren schon vor der Entwicklung unserer heutigen Computer bekannt, aller- dings haperte es mit der Ausführung. Zunächst arbeiteten Menschen als Computer“! ” 5 Lewis Fry Richardson schlägt in seinem Buch Weather Prediction by Arithmetical Finite Differences vor das Wetter für den nächsten Tag mit 64000 (!) menschlichen Computern auszurechnen. Der Vorschlag wird als unpraktikabel verworfen. 4 Alonzo Curch, US-amerikanischer Mathematiker, Logiker und Philosoph, 1903-1995 5 Lewis Fry Richardson, brit. Meteorologe, 1881 - 1953. 16 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 In Los Alamos werden Lochkartenmaschinen und menschliche Rechner für Berech- nungen eingesetzt. Richard Feynman6 organisierte sogar einen Wettbewerb zwischen beiden. Der Startpunkt der Entwicklung realer Computer stimmt (zufällig?) relativ genau mit der Entwicklung theoretischer Berechenbarkeitskonzepte durch Church und Turing überein. Dabei verstehen wir Computer bzw. (Universal-)Rechner als Maschinen zur Ausführung beliebiger Algorithmen in obigem Sinne (d.h. sie können nicht nur“ rechnen im Sinne ” arithmetischer Operationen). Einige der wichtigsten frühen Rechenmaschinen waren: Zuse Z3, Mai 1941, mechanisch, turing-vollständig (aber nicht als solcher konstru- iert) Atanasoff-Berry-Computer, Sommer 1941, elektronisch (Röhren), nicht turing-mächtig, gebaut zur Lösung linearer Gleichungssysteme (29 × 29) Colossus, 1943, elektronisch, nicht turing-mächtig, Kryptographie Mark 1, 1944, mechanisch, turing-vollständig, Ballisitik ENIAC, 1946, elektronisch, turing-vollständig, Ballistik EDVAC, 1949, elektronisch, turing-vollständig, Ballistik, erste Von-Neumann-Architektur“ ” Praktische Computer basieren meist auf dem von John von Neumann 1945 im Rahmen der EDVAC-Entwicklung eingeführten Konzept. Es ist umstritten welche der Ideen tatsächlich genau von ihm sind. Geschichte: John von Neumann7 war einer der bedeutendsten Mathematiker. Von ihm stammt die Spieltheorie, die mathematische Begründung der Quantenmechanik, sowie wichtige Beiträge zu Informatik und Numerik. Der Speicher M besteht aus endlich vielen Feldern, von denen jedes eine Zahl aufneh- men kann. Im Unterschied zur TM kann auf jedes Feld ohne vorherige Positionierung zugegriffen werden (wahlfreier Zugriff, random access). Zum Zugriff auf den Speicher wird ein Index, auch Adresse genannt, verwendet, d.h. wir können den Speicher als Abbildung M :A→D auffassen. Für die Adressen gilt A = [0, N − 1] ⊂ N0 wobei aufgrund der binären Organisation N = 2n gilt. n ist die Anzahl der erforderlichen Adressleitungen. Für D gilt D = [0, 2m − 1] mit der Wortbreite m, die meistens ein Vielfaches von 8 ist. m ist die Anzahl der erforderlichen Datenleitungen. Die Gesamtkapazität des Speichers ist demnach m · 2n Bit. Jedes Bit kann zwei Werte annehmen, 0 oder 1. In der Praxis wird die Größe des Speichers in Byte angegeben, 6 Richard P. Feynman, US-amerik. Physiker, Nobelpreis 1965, 1918-1988. 7 János Neumann Margittai, Mathematiker österreichisch-ungarischer Herkunft, 1903 - 1957. 17 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Instruktions− Register einheit steuert IU Rechenwerk Befehlszähler ALU Prozessor (CPU) Daten, Adressen Befehle, Adressen Speicher M Abbildung 1: Grobe Struktur der von-Neumann-Architektur. wobei ein Byte aus 8 Bit besteht. Damit enthält ein Speicher mit n Adressleitungen bei Wortbreite m genau (m/8) · 2n Byte. Gebräuchlich sind auch noch die Abkürzungen 1 Kilobyte= 210 Byte = 1024 Byte, 1 Megabyte= 220 Byte, 1 Gigabyte = 230 Byte. Der Speicher enthält sowohl Daten (das Band in der TM) als auch Programm (die Ta- belle in der TM). Den einzelnen Zeilen der Programmtabelle der TM entsprechen beim von Neumannschen Rechner die Befehle. Die Vereinigung von Daten und Programm im Speicher (stored program computer) war der wesentliche Unterschied zu den früheren Ansätzen. Befehle werden von der Instruktionseinheit (instruction unit, IU) gelesen und dekodiert. Die Instruktionseinheit steuert das Rechenwerk, welches noch zusätzliche Daten aus dem Speicher liest bzw. Ergebnisse zurückschreibt. Die Maschine arbeitet zyklisch die folgenden Aktionen ab: Befehl holen Befehl dekodieren Befehl ausführen Dies nennt man Befehlszyklus. Viel mehr über Rechnerhardware erfährt man in der Vor- lesung Technische Informatik“. ” Bemerkung: Hier wurde insbesondere die Interaktion von Rechnern mit der Umwelt, die sog. Ein- und Ausgabe, in der Betrachtung vernachlässigt. Moderne Rechner haben insbesondere die Fähigkeit, auf äußere Einwirkungen hin (etwa Tastendruck) den Pro- grammfluss zu unterbrechen und an anderer Stelle (Turingmaschine: in anderem Zustand) wieder aufzunehmen. Von Neumann hat die Ein-/Ausgabe im Design des EDVAC schon ausführlich beschrieben. 18 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Bemerkung: Heutige Rechner beinhalten insbesondere viele Möglichkeiten der paralle- len Verarbeitung bis hin zur kompletten Vervielfachung von Instruktionseinheit, Rechen- werk und Speicher (Multicorerechner). 1.6 Programmiersprachen Die Befehle, die der Prozessor ausführt, nennt man Maschinenbefehle oder auch Maschi- nensprache. Sie ist relativ umständlich, und es ist sehr mühsam größere Programme darin zu schreiben. Andererseits können ausgefeilte Programme sehr kompakt sein und sehr effizient ausgeführt werden. Beispiel: Ein Schachprogramm auf einem 6502-Prozessor findet man unter http://www.6502.org/source/games/uchess/uchess.pdf Es benötigt weniger als 1KB an Speicher! Die weitaus meisten Programme werden heute in sogenannten höheren Programmier- sprachen erstellt. Sinn einer solchen Sprache ist, dass der Programmierer Programme möglichst schnell (in Sinne benötigter Programmiererzeit) und korrekt (Programm löst Problem korrekt) erstellen kann. Wir lernen in dieser Vorlesung die Sprache C++. C++ ist eine Weiterentwicklung der Sprache C, die Ende der 1960er Jahre entwickelt wurde. Programme in einer Hochsprache lassen sich automatisch in Programme der Maschinen- sprache übersetzen. Ein Programm, das dies tut, nennt man Übersetzer oder Compiler. Ein Vorteil dieses Vorgehens ist auch, dass Programme der Hochsprache in verschiedene Maschinensprachen (Portabilität) übersetzt und andererseits verschiedene Hochsprachen auch in ein und dieselbe Maschinensprache übersetzt werden können (Flexibilität). Abbildung 2 zeigt die notwendigen Schritte bei der Programmerstellung im Überblick. Frage: Warum gibt es verschiedene Programmiersprachen? Antwort: Wie bei der Umgangssprache: teils sind Unterschiede historisch gewachsen, teils sind die Sprachen wie Fachsprachen auf verschiedene Problemstellungen hin opti- miert. 1.7 Komplexität von Programmen Die Leistungsfähigkeit von Computern wächst schnell. Wissen: (Moore’sches8 Gesetz“) ” Die Anzahl der Transistoren pro Flächeneinheit auf einem Halbleiterchip verdoppelt sich etwa alle 18-24 Monate. 8 Gordon E. Moore, US-amerk. Unternehmer (Mitbegründer der F. Intel), geb. 1929. 19 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Problem Editor Idee C++ Programm (auf Papier) Programm- text in Arbeit Algorithmus Datei geht nicht Compiler 01001 01100 Prozessor Maschinen- geht ! programm Abbildung 2: Workflow bei der Programmerstellung. Beispiel: Entwicklung von Taktgeschwindigkeit, Speichergröße und Größe des Linux- Kernel. Zeit Proz Takt RAM Disk Linux Kernel (.tar.gz) 1982 Z80 6 64KB 800KB 6KB (CPM) 1988 80286 10 1MB 20MB 20KB (DOS) 1992 80486 25 20MB 160MB 140KB (0.95) 1995 PII 100 128MB 2GB 2.4MB (1.3.0) 1999 PII 400 512MB 10GB 13.2MB (2.3.0) 2001 PIII 850 512MB 32GB 23.2MB (2.4.0) 2004 P4 (Prescott) 3.8 GHz 2048 GB 250 GB 36 MB (2.4.26) 2010 i7 (Westmere) 3.5 GHz 8196 MB 1024 GB 84 MB (2.6.37.7) Bis 2001 exponentielles Wachstum. Prozessortaktfrequenz stagniert seit 2004. Wachstum des Linux-Kernel ist auch abgeflacht. Problem: Die benötigte Zeit zum Erstellen großer Programme skaliert mehr als linear, d. h. zum Erstellen eines doppelt so großen Programmes braucht man mehr als doppelt so lange. Abhilfe: Verbesserte Programmiertechnik, Sprachen und Softwareentwurfsprozesse. Einen wesentlichen Beitrag leistet hier die objektorientierte Programmierung, die wir in dieser Vorlesung am Beispiel von C++ erlernen werden. 20 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 2 Funktionale Programmierung 2.1 Auswertung von Ausdrücken Arithmetische Ausdrücke Beispiel: Auswertung von: 5 + 3 oder ((3 + (5 ∗ 8)) − (16 ∗ (7 + 9))). Programm: #i n c l u d e ” f c p p. hh” int main ( ) { return p r i n t ( (3+(5∗8) ) −(16∗(7+9) ) ) ; } Übersetzen (in Unix-Shell): > g++ -o erstes erstes.cc Ausführung: >./erstes -213 Bemerkung: Ohne -o erstes“ wäre der Name a.out“ verwendet worden. ” ” Das Programm berechnet den Wert des Ausdrucks und druckt ihn auf der Konsole aus. Wie wertet der Rechner so einen Ausdruck aus? Die Auswertung eines zusammengesetzten Ausdruckes lässt sich auf die Auswertung der vier elementaren Rechenoperationen +, −, ∗ und / zurückführen. Dazu fassen wir die Grundoperationen als zweistellige Funktionen auf: +, −, ∗, / : Z × Z → Z. Jeden Ausdruck können wir dann äquivalent umformen: ((3 + (5 ∗ 8)) − (16 ∗ (7 + 9))) ≡ −(+(3, ∗(5, 8)), ∗(16, +(7, 9))). 21 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Definition: Die linke Schreibweise nennt man Infix-Schreibweise (infix notation), die rechte Präfix-Schreibweise (prefix notation). Bemerkung: Die Infix-Schreibweise ist für arithmetische Ausdrücke bei Hinzunahme von Präzedenzregeln wie Punkt vor Strich“ und dem Ausnutzen des Assoziativgesetzes kürzer ” (da Klammern wegelassen werden können) und leichter lesbar als die Präfix-Schreibweise. Bemerkung: Es gibt auch eine Postfix-Schreibweise, welche zum Beispiel in HP-Taschen- rechnern, dem Emacs-Programm Calc“ oder der Computersprache Forth verwendet wird. ” Die vier Grundoperationen +, −, ∗, / betrachten wir als atomar. Im Rechner gibt es ent- sprechende Baugruppen, die diese atomaren Operationen realisieren. Der Compiler übersetzt den Ausdruck aus der Infix-Schreibweise in die äquivalente Präfix- schreibweise. Die Auswertung des Ausdrucks, d.h. die Berechnung der Funktionen, erfolgt dann von innen nach aussen: -(+(3,*(5,8)),*(16,+(7,9))) = -(+(3, 40 ),*(16,+(7,9))) = -( 43 ,*(16,+(7,9))) = -( 43 ,*(16, 16 )) = -( 43 , 256 ) = -213 Bemerkung: Dies ist nicht die einzig mögliche Reihenfolge der Auswertung der Teilope- rationen, alle Reihenfolgen führen jedoch zum gleichen Ergebnis! Bemerkung: C++ kennt die Punkt-vor-Strich-Regel und das Assoziativgesetz. Überflüssige Klammern können also weggelassen werden. Ausdrücke als Bäume Jeder arithmetische Ausdruck kann als binärer Baum dargestellt werden. Die Auswertung des Ausdruckes erfolgt dann von den Blättern zur Wurzel. In dieser Darstellung erkennt man welche Ausführungsreihenfolgen möglich sind bzw. welche Teilausdrück gleichzeitig ausgewertet werden können (Datenflussgraph). − + ∗ 3 ∗ 16 + 5 8 9 7 22 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 2.2 Funktionen Zu den schon eingebauten Funktionen wie +, −, ∗, / kann man noch weitere benutzerde- finierte Funktionen hinzuzufügen. Beispiel: int quadrat ( int x ) { return x∗x ; } Die erste Zeile (Funktionskopf) vereinbart, dass die neue Funktion namens quadrat als Argument eine Zahl mit Namen x vom Typ int als Eingabe bekommt und einen Wert vom Typ int als Ergebnis liefert. Der anschließende Funktionsrumpf (body) zwischen geschweiften Klammern sagt, was die Funktion tut. Wir werden uns zunächst auf einen sehr kleinen Teil des Sprachumfangs von C/C++ beschränken. Dort besteht der Funktionsrumpf nur aus dem Wort return gefolgt von einem Ausdruck gefolgt von einem Semikolon. Bemerkung: C++ ist eine streng typgebundene Programmiersprache (strongly typed ), d. h. jedem Bezeichner (z. B. x oder quadrat) ist ein Typ zugeordnet. Diese Typzuordnung kann nicht geändert werden (statische Typbindung, static typing). Bemerkung: Der Typ int entspricht dabei (kleinen) ganzen Zahlen. Andere Typen sind float, double, char, bool. Später werden wir sehen, dass man auch neue Typen hinzufügen kann. Programm: (Verwendung) #i n c l u d e ” f c p p. hh” int quadrat ( int x ) { return x∗x ; } int main ( ) { return p r i n t ( quadrat ( 3 )+quadrat (4+4) ) ; } Bemerkung: Damit können wir die Bedeutung aller Elemente des Programmes verste- hen. Neue Funktionen kann man (in C) nur in Präfix-Schreibweise verwenden. main ist eine Funktion ohne Argumente und mit Rückgabetyp int. 23 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 #include ”fcpp.hh” ist ein sogenannter Include-Befehl. Er sorgt dafür, dass die in der Datei fcpp.hh enthaltenen Erweiterungen von C++, etwa zusätzliche Funktio- nen, verwendet werden können. fcpp.hh ist nicht Teil des C++ Systems, sondern wird von uns für die Vorlesung zur Verfügung gestellt (erhältlich auf der Webseite). Achtung: Die Datei muss sich im selben Verzeichnis befinden wie das zu übersetzende Programm damit der Compiler diese finden kann. print ist eine Funktion mit Rückgabewert 0 (unabhängig vom Argument), welche den Wert des Arguments auf der Konsole ausdruckt (Seiteneffekt). Die Definition dieser Funktion ist in der Datei fcpp.hh enthalten. Die Programmausführung beginnt immer mit der Funktion main (sozusagen das Startsymbol). 2.3 Selektion Fehlt noch: Steuerung des Programmverlaufs in Abhängigkeit von Daten. Beispiel: Betragsfunktion −x x < 0 |x| = x x≥0 Um dies ausdrücken zu können, führen wir eine spezielle dreistellige Funktion cond ein: Programm: (Absolutwert) #i n c l u d e ” f c p p. hh” int a b s o l u t ( int x ) { return cond ( x oder < Ausdruck > oder < Zahl >, sind Symbole für noch zu bildende Zeichenketten. Regeln beschreiben, wie diese Symbole durch weitere Symbole und/oder terminale Zeichen ersetzt werden können. Da diese Symbole immer ersetzt werden, nennt man sie nichtterminale Symbole. < ǫ > bezeichnet das leere Zeichen“. ” Die normal gesetzten Zeichen(ketten) ::= | { } }+ [ ] sind Teil der Regelbeschreibung und tauchen nie in abgeleiteten Zeichenketten auf. (Es sei denn sie sind unterstrichen und somit terminale Zeichen). (Alternativ findet man auch die Konvention terminale Symbole in Anführungszeichen zu setzen und die spitzen Klammern bei nichtterminalen wegzulassen). Jede Regel hat ein Symbol auf der linken Seite gefolgt von ::=“. Die rechte Seite be- ” schreibt, durch was das Symbol der linken Seite ersetzt werden kann. Beispiel: < A > ::= a < A > b < A > ::= < ǫ > Ausgehend vom Symbol < A > kann man somit folgende Zeichenketten erzeugen: < A > → a< A >b → aa< A >bb →... → a... a< A >b... b → a... ab... b | {z } | {z } | {z }| {z } n mal n mal n mal n mal Bemerkung: Offensichtlich kann es für ein Symbol mehrere Ersetzungsregeln geben. Wie im MIU-System ergeben sich die wohlgeformten Zeichenketten durch alle möglichen Regelanwendungen. 9 John Backus, 1924-2007, US-amerik. Informatiker. 10 Peter Naur, geb. 1928, dänischer Informatiker. 25 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Kurzschreibweisen Oder: Das Zeichen | “ ( oder“) erlaubt die Zusammenfassung mehrerer Regeln in einer Zeile. ” ” Beispiel: < A > ::= a < A > b | < ǫ > Option: < A > ::= [ ] ist identisch zu < A > ::= | < ǫ > Wiederholung mit n ≥ 0: < A > ::= { } ist identisch mit < A > ::= < A > | < ǫ > Wiederholung mit n ≥ 1: < A > ::= { }+ ist identisch zu < A > ::= < A > | Syntaxbeschreibung für FC++ Die bisher behandelte Teilmenge von C++ nennen wir FC++ ( funktionales C++“ und ” wollen die Syntax in EBNF beschreiben. Syntax: (Zahl) < Zahl > ::= [ + | - ] { < Ziffer > }+ Syntax: (Ausdruck) < Ausdruck > ::= < Zahl > | [ - ] < Bezeichner > | ( < Ausdruck > < Operator > < Ausdruck > ) | < Bezeichner > ( [ < Ausdruck > { , < Ausdruck > } ] ) | < Cond > < Bezeichner > ::= < Buchstabe > { < Buchstabe oder Zahl > } < Operator > ::= +|-|*|/ Weggelassen: Regeln für < Buchstabe > und < Buchstabe oder Zahl >. Diese einfache Definition für Ausdrücke enthält weder Punkt-vor-Strich noch das Weglas- sen von Klammern aufgrund des Assoziativgesetzes! Hier die Syntax einer Funktionsdefinition in EBNF: Syntax: (Funktionsdefinition) < Funktion > ::= < Typ > < Name > ( < formale Parameter > ) { < Funktionsrumpf > } < Typ > ::= < Bezeichner > < Name > ::= < Bezeichner > < formale Parameter > ::= [ < Typ > < Name > { , < Typ > < Name > } ] Die Argumente einer Funktion in der Funktionsdefinition heissen formale Parameter. Sie bestehen aus einer kommaseparierten Liste von Paaren aus Typ und Name. Damit kann man also n-stellige Funktionen mit n ≥ 0 erzeugen. 26 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Regel für den Funktionsrumpf: < Funktionsrumpf > ::= return < Ausdruck > ; Hier ist noch die Syntax für die Selektion: Syntax: (Cond) < Cond > ::= cond ( < BoolAusdr > , < Ausdruck > , < Ausdruck > ) < BoolAusdr > ::= true | false | ( < Ausdruck > < VglOp > < Ausdruck >) | ( < BoolAusdr > < LogOp > < BoolAusdr > ) | ! ( < BoolAusdr > ) < VglOp > ::= == | != | < | > | = < LogOp > ::= && | || Bemerkung: Beachte dass der Test auf Gleichheit als == geschrieben wird! Syntax: (FC++ Programm) ::= { } { < Funktion > }+ ::= #include “ < DateiName > “ Bemerkung: (Leerzeichen) C++ Programme erlauben das Einfügen von Leerzeichen, Zeilenvorschüben und Tabulatoren ( whitespace“) um Programme für den Menschen les- ” barer zu gestalten. Hierbei gilt folgendes zu beachten: Bezeichner, Zahlen, Schlüsselwörter und Operatorzeichen dürfen keinen Whitespace enthalten: – zaehler statt zae hler, – 893371 statt 89 3371, – return statt re tur n, – && statt & &. Folgen zwei Bezeichner, Zahlen oder Schlüsselwörter nacheinander so muss ein Whi- tespace (also mindestens ein Leerzeichen) dazwischen stehen: – int f(int x) statt intf(intx), – return x; statt returnx;. Die obige Syntaxbeschreibung mit EBNF ist nicht mächtig genug, um fehlerfrei übersetzbare C++ Programme zu charakterisieren. So enthält die Syntaxbeschreibung üblicherweise nicht solche Regeln wie: Kein Funktionsname darf doppelt vorkommen. Genau eine Funktion muss main heissen. Namen müssen an der Stelle bekannt sein wo sie vorkommen. Bemerkung: Mit Hilfe von EBNF lassen sich sogenannte kontextfreie Sprachen definie- ren. Entscheidend ist, dass in EBNF-Regeln links immer nur genau ein nichtterminales Symbol steht. Zu jeder kontextfreien Sprache kann man ein Programm (genauer: einen Kellerautomaten) angeben, das für jedes vorgelegte Wort in endlicher Zeit entscheidet, ob 27 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 es in der Sprache ist oder nicht. Man sagt: kontextfreie Sprachen sind entscheidbar. Die Regel Kein Funktionsname darf doppelt vorkommen“ lässt sich mit einer kontextfreien ” Sprache nicht formulieren und wird deshalb extra gestellt. Kommentare Mit Hilfe von Kommentaren kann man in einem Programmtext Hinweise an einen mensch- lichen Leser einbauen. Hier bietet C++ zwei Möglichkeiten an: // nach // wird der Rest der Zeile ignoriert 2.5 Das Substitutionsmodell Selbst wenn ein Programm vom Übersetzer fehlerfrei übersetzt wird, muss es noch lange nicht korrekt funktionieren. Was das Programm tut bezeichnet man als Semantik (Be- deutungslehre). Das in diesem Abschnitt vorgestellte Substitutionsmodell kann die Wir- kungsweise funktionaler Programme beschreiben. Definition: (Substitutionsmodell) Die Auswertung von Ausdrücken geschieht wie folgt: 1. < Zahl > wird als die Zahl selbst ausgewertet. 2. < Name > ( < a1 >, < a2 >,... , < an > ) wird für Elementarfunktionen folgender- maßen ausgewertet: a) Werte die Argumente aus. Diese sind wieder Ausdrücke. Unsere Definition ist also rekursiv! b) Werte die Elementarfunktion < Name > auf den so berechneten Werten aus. 3. < Name > ( < a1 >, < a2 >,... , < an > ) wird für benutzerdefinierte Funktionen folgendermaßen ausgewertet: a) Werte die Argumente aus. b) Werte den Rumpf der Funktion < Name > aus, wobei jedes Vorkommen eines formalen Parameters durch den entsprechenden Wert des Arguments ersetzt wird. 4. cond ( < a1 >, < a2 >, < a3 > ) wird ausgewertet gemäß: a) Werte < a1 > aus. b) Ist der erhaltene Wert true, so erhält man den Wert des cond-Ausdrucks durch Auswertung von < a2 >, ansonsten von < a3 >. Wichtig: nur eines der beiden Argumente < a2 > oder < a3 > wird ausgewertet. Bemerkung: Die Namen der formalen Parameter sind egal, sie entsprechen sogenannten gebundenen Variablen in logischen Ausdrücken. Beispiel: 28 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 quadrat(3) = *(3,3) = 9 quadrat(quadrat((2+3)+7)) = quadrat(quadrat(+(+(2,3),7))) = quadrat(quadrat(+( 5 ,7))) = quadrat(quadrat( 12 )) = quadrat( *(12,12) ) = quadrat( 144 ) = *(144,144) = 20736 quadrat(quadrat(+(+(2,3),7))) *(144,144) 20736 3 (c) 3 (a) 3 (b) 3 (c) quadrat(+(+(2,3),7)) *(12,12) 144 3 (b) 3 (a) 3 (c) +(+(2,3),7) +(5,7) 12 2 (a) 3 (b) 3 (b) 2 (a) 7 1 7 +(2,3) 5 2 2.6 Linear-rekursive Prozesse Beispiel: (Fakultätsfunktion) Sei n ∈ N. Dann gilt n Y n! = i, i=1 = 1 · 2 · 3 · · · · · n. Oder rekursiv: ( 1 n = 1, n! = n(n − 1)! n > 1. Programm: (Rekursive Berechnung der Fakultät) #i n c l u d e ” f c p p. hh” int f a k u l t a e t ( int n ) { return cond ( nende , produkt , f a k I t e r ( produkt ∗ z a e h l e r , z a e h l e r +1, ende ) ) ; } int f a k u l t a e t ( int n ) { return f a k I t e r ( 1 , 1 , n ) ; } int main ( ) { return p r i n t ( f a k u l t a e t ( 5 ) ) ; } 30 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Die Analyse mit Hilfe des Substitutionsprinzips liefert: fakultaet(5) = fakIter(1,1,5) = fakIter(1,2,5) = fakIter(2,3,5) = fakIter(6,4,5) = fakIter(24,5,5) = fakIter(120,6,5) = 120 Sprechweise: Dies nennt man einen linear iterativen Prozess. Der Zustand des Program- mes lässt sich durch eine feste Zahl von Zustandsgrößen beschreiben (hier die Werte von zaehler und produkt). Es gibt eine Regel wie man von einem Zustand zum nächsten kommt, und es gibt den Endzustand. Bemerkung: Von einem Zustand kann man ohne Kenntnis der Vorgeschichte aus weiterrechnen. Die Zahl der durchlaufenen Zustände ist proportional zu n. Die Informationsmenge zur Darstellung des Zustandes ist konstant. Bei geeigneter Implementierung ist der Speicherplatzbedarf konstant. Beim Lisp-Dialekt Scheme wird diese Optimierung von am Ende aufgerufenen Funk- tionen (tail-call position) im Sprachstandard verlangt. Bei anderen Sprachen (auch C++) ist diese Optimierung oft durch Compilereinstel- lungen erreichbar (nicht automatisch, weil das Debuggen erschwert wird). Beide Arten von Prozessen werden durch rekursive Funktionen beschrieben! 2.8 Baumrekursion Beispiel: (Fibonacci-Zahlen)   0 n=0 fib(n) = 1 n=1.  fib(n − 1) + fib(n − 2) n > 1 Die Folge der Fibonacci Zahlen modelliert (unter anderem) das Wachstum einer Kanin- chenpopulation unter vereinfachten Annahmen. Sie ist benannt nach Leonardo di Pisa.11 Programm: (Fibonacci rekursiv) #i n c l u d e ” f c p p. hh” int f i b ( int n ) 11 Leonardo di Pisa (auch Fibonacci), etwa 1180 - 1241, ital. Rechenmeister in Pisa. 31 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 { return cond ( n==0, 0 , cond ( n==1, 1 , f i b ( n−1)+f i b ( n−2) ) ) ; } int main ( int argc , char ∗∗ argv ) { return p r i n t ( f i b ( r e a d a r g i n t ( argc , argv , 1 ) ) ) ; } Auswertung von fib(5) nach dem Substitutionsmodell: fib(5) = +(fib(4),fib(3)) = +(+(fib(3),fib(2)),+(fib(2),fib(1))) = +(+(+(fib(2),fib(1)),+(fib(1),fib(0))),+(+(fib(1),fib(0)),fib(1))) = +(+(+(+(fib(1),fib(0)),fib(1)),+(fib(1),fib(0))),+(+(fib(1),fib(0)),fib(1))) = +(+(+(+( 1 , 0 ), 1 ),+( 1 , 0 )),+(+( 1 , 0 ), 1 )) = +(+(+( 1 , 1 ), 1 ),+( 1 , 1 )) = +(+( 2 , 1 ), 2 ) = +( 3 , 2 ) = 5 Graphische Darstellung des Aufrufbaumes 5 4 3 3 2 2 1 2 1 1 0 1 0 1 0 fib(5) baut auf fib(4) und fib(3), fib(4) baut auf fib(3) und fib(2), usw. Bezeichnung: Der Rekursionsprozess bei der Fibonaccifunktion heißt daher baumre- kursiv. Frage: Wie schnell wächst die Anzahl der Operationen bei der rekursiven Auswertung der Fibonaccifunktion? Wie schnell wächst die Fibonaccifunktion selbst? 32 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Antwort: (Wachstum von fib). Fn := fib(n) erfüllt die lineare 3-Term-Rekursion Fn = Fn−1 + Fn−2 Die Lösungen dieser Gleichung sind von der Form aλn1 + bλ√n2 , wobei λ1/2 die Lösungen der quadratischen Gleichung λ2 = λ + 1 sind, also λ1/2 = 1±2 5. Die Konstanten a und b werden durch die Anfangsbedingungen F0 = 0, F1 = 1 festgelegt und damit ergibt sich √ !n √ !n √ !n 1 1+ 5 1 1− 5 1 1+ 5 Fn = √ −√ ≈√ 5 2 5 2 5 2 |{z} | {z } a b für große n, da |λ2 | < 1. Bemerkung: λ1 ≈ 1.61803 ist der goldene Schnitt. Antwort: (Aufwand zur rekursiven Berechnung von fib(n)) Der Gesamtaufwand An zur Auswertung von fib (n) ist größer gleich einer Konstante c1 multipliziert mit der Zahl Bn der Blätter im Berechnungsbaum: An ≥ c1 Bn. Die Zahl der Blätter Bn erfüllt die Rekursion: B0 = 1 , B1 = 1 , Bn = Bn−1 + Bn−2 , n>1 woraus man λ1 Bn = fib(n + 1) ≥ √ λn1 − ǫ1 5 ersieht. Die Ungleichung gilt für n ≥ N1 (ǫ1 ). Der Gesamtaufwand An zur Auswertung von fib (n) ist kleiner gleich einer Kon- stante c2 multipliziert mit der Anzahl Gn der Knoten im Baum: An ≤ c 2 G n. Diese erfüllt: G0 = 1 , G1 = 1 , Gn = Gn−1 + Gn−2 + 1 , n > 1. Durch die Transformation Gn = G′n − 1 ist dies äquivalent zu G′0 = 2 , G′1 = 2 , G′n = G′n−1 + G′n−2 , n > 1. Mit den Methoden von oben erhält man 1 1 1 Gn = 1 + √ λ1 + 1 − √ λ2 ≤ 1 + √ λn1 + ǫ2 ′ n n 5 5 5 für n ≥ N2 (ǫ2 ). 33 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Damit erhalten wir also zusammengefasst: λ1 n 1 c1 √ λ1 − c1 ǫ1 ≤ An ≤ c2 1 + √ λn1 + c2 ǫ2 5 5 für n ≥ max(N1 (ǫ1 ), N2 (ǫ2 )). Bemerkung: Der Rechenaufwand wächst somit exponentiell. Der Speicherbedarf wächst hingegen nur linear in n. Auch die Fibonaccizahlen kann man iterativ berechnen indem man die aktuelle Summe mitführt: Programm: (Fibonacci iterativ) #i n c l u d e ” f c p p. hh” int f i b I t e r ( int l e t z t e , int v o r l e t z t e , int z a e h l e r ) { return cond ( z a e h l e r ==0, vorletzte , f i b I t e r ( v o r l e t z t e+l e t z t e , l e t z t e , z a e h l e r −1) ) ; } int f i b ( int n ) { return f i b I t e r ( 1 , 0 , n ) ; } int main ( int argc , char ∗∗ argv ) { return p r i n t ( f i b ( r e a d a r g i n t ( argc , argv , 1 ) ) ) ; } Hier liefert das Substitutionsmodell: fib(2) = fibIter(1,0,2) = cond( 2==0, 0, fibiter(1,1,1)) = fibiter(1,1,1) = cond( 1==0, 1, fibiter(2,1,0)) = fibIter(2,1,0) = cond( 0==0, 1, fibiter(3,2,-1)) = 2 Bemerkung: Man braucht hier offenbar drei Zustandsvariablen. Der Rechenaufwand des linear iterativen Prozesses ist proportional zu n, also viel kleiner als der baumrekursive. 34 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 2.9 Größenordnung Es gibt eine formale Ausdrucksweise für Komplexitätsaussagen wie der Aufwand zur ” Berechnung von fib(n) wächst exponentiell“. Sei n ein Parameter der Berechnung, z. B. Anzahl gültiger Stellen bei der Berechnung der Quadratwurzel Dimension der Matrix in einem Programm für lineare Algebra Größe der Eingabe in Bits Mit R(n) bezeichnen wir den Bedarf an Resourcen für die Berechnung, z. B. Rechenzeit Anzahl auszuführender Operationen Speicherbedarf Definition: R(n) = Ω(f (n)), falls es von n unabhängige Konstanten c1 , n1 gibt mit R(n) ≥ c1 f (n) ∀n ≥ n1. R(n) = O(f (n)), falls es von n unabhängige Konstanten c2 , n2 gibt mit R(n) ≤ c2 f (n) ∀n ≥ n2. R(n) = Θ(f (n)), falls R(n) = Ω(f (n)) ∧ R(n) = O(f (n)). Beispiel: R(n) bezeichne den Rechenaufwand der rekursiven Fibonacci-Berechnung: R(n) = Ω(n) , R(n) = O(2n ) , R(n) = Θ(λn1 ) Bezeichnung: R(n) = Θ(1) konstante Komplexität R(n) = Θ(log n) logarithmische Komplexität R(n) = Θ(n) lineare Komplexität R(n) = Θ(n log n) fast optimale Komplexität R(n) = Θ(n2 ) quadratische Komplexität R(n) = Θ(np ) polynomiale Komplexität R(n) = Θ(an ) exponentielle Komplexität 35 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Beispiel 1: Telefonbuch Wir betrachten den Aufwand für das Finden eines Namens in einem Telefonbuch der Seitenzahl n. Algorithmus: (A1) Blättere das Buch von Anfang bis Ende durch. Satz: Sei C1 > 0 die (maximale) Zeit, die das Durchsuchen einer Seite benötigt. Der maximale Zeitaufwand A1 = A1 (n) für Algorithmus A1 ist dann abschätzbar durch A1 (n) = C1 n Algorithmus: (A2) Rekursives Halbieren. 1. Setze [a1 = 1, b1 = n], i = 1; 2. Ist ai = bi durchsuche Seite ai ; Fertig; 3. Setze m = (ai + bi )/2 (ganzzahlige Division); 4. Falls Name vor Seite m setze [ai+1 = ai , bi+1 = m], i = i + 1, gehe zu 2.; 5. Falls Name nach Seite m setze [ai+1 = m, bi+1 = bi ], i = i + 1, gehe zu 2.; 6. Durchsuche Seite m; Fertig; Satz: Sei C1 > 0 die (maximale) Zeit, die das Durchsuchen einer Seite benötigt, und C2 > 0 die (maximale) Zeit für die Schritte 3-5. Der maximale Zeitaufwand A2 = A2 (n) für Algorithmus A2 ist dann abschätzbar durch A2 (n) = C1 + C2 log2 n Man ist vor allem an der Lösung großer Probleme interessiert. Daher interessiert der Aufwand A(n) für große n. Satz: Für große Telefonbücher ist Algorithmus 2 besser“, d.h. der maximale Zeitaufwand ” ist kleiner. Beweis: A1 (n) C1 n n = = C2 → +∞ A2 (n) C1 + C2 log2 n 1 + C1 log2 n Beobachtung: Die genauen Werte von C1 , C2 sind für diese Aussage unwichtig. Für spezielle Eingaben (z.B. Andreas Aalbert) kann auch Algorithmus 1 besser sein. 36 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Definition: Man sagt A(n) = O(f (n)), wenn es C > 0 und N > 0 gibt mit A(n) ≤ Cf (n) , ∀n ≥ N Bemerkung: Um Algorithmus 2 ist für große Telefonbücher besser“ zu schließen, reichen ” die Informationen A1 (n) = O(n) und A2 (n) = O(log n) aus. Man beachte auch, dass wegen log2 n = log n log 2 gilt O(log2 n) = O(log n). 2.10 Wechselgeld Aufgabe: Ein gegebener Geldbetrag ist unter Verwendung von Münzen zu 1, 2, 5, 10, 20 und 50 Cent zu wechseln. Wieviele verschiedene Möglichkeiten gibt es dazu? Beachte: Die Reihenfolge in der wir die Münzen verwenden ist egal. Idee: Es sei der Betrag a mit n verschiedenen Münzarten zu wechseln. Eine der n Münzarten habe den Nennwert d. Dann gilt: Entweder wir verwenden eine Münze mit Wert d, dann bleibt der Rest a − d mit n Münzarten zu wechseln. Wir verwenden die Münze mit Wert d überhaupt nicht, dann müssen wir den Betrag a mit den verbleibenden n − 1 Münzarten wechseln. Folgerung: Ist A(a, n) die Anzahl der Möglichkeiten den Betrag a mit n Münzarten zu wechseln, und hat Münzart n den Wert d, so gilt A(a, n) = A(a − d, n) + A(a, n − 1) Dies ist ein Beispiel für eine Rekursion in zwei Argumenten. Bemerkung: Es gilt auch: A(0, n) = 1 für alle n ≥ 0. Wenn der Betrag a den Wert 0 erreicht hat haben wir den ursprünglichen Betrag gewechselt. (A(0, 0) kann nicht vorkommen). A(a, n) = 0 falls a > 0 and n = 0. Der Betrag kann nicht gewechselt werden. A(a, n) = 0 falls a < 0. Der Betrag kann nicht gewechselt werden. Das Wechseln von 5 Cent in 1 und 2 Centstücke zeigt Abbildung 3. Bemerkung: Dies ist wieder ein baumrekursiver Prozess. Programm: (Wechselgeld zählen) #i n c l u d e ” f c p p. hh” // u e b e r s e t z e Muenzart i n Muenzwert int nennwert ( int nr ) { 37 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 5,2 2 | 3,2 5,1 1 | 4,1 2 2 | 1,2 2 | 3,1 1 1 | 3,1 2 2 | 1,1 2 1 | 2,1 1 1 1 | 2,1 221 2 1 1 | 1,1 1 1 1 1 | 1,1 2111 11111 Abbildung 3: Aufrufbaum im Wechselgeld Beispiel. return cond ( nr==1, 1 , cond ( nr==2, 2 , cond ( nr==3, 5 , cond ( nr==4, 1 0 , cond ( nr==5, 2 0 , cond ( nr==6, 5 0 , 0 ) ) ) ) ) ) ; } int wg ( int b e t r a g , int muenzarten ) { return cond ( b e t r a g ==0, 1 , cond ( b e t r a g 0, so ist ggT(a, b) = a. a 2. Aus s = q sb + r s ∈ N ersieht man ggT(a, b) = ggT(b, r). Somit haben wir folgende Rekursion bewiesen: a falls b = 0 ggT(a, b) = ggT(b, a mod b) sonst Programm: (Größter gemeinsamer Teiler) #i n c l u d e ” f c p p. hh” int ggT ( int a , int b ) { return cond ( b==0 , a , ggT ( b , a%b ) ) ; } 12 Euklid von Alexandria, ca. 360 - 280 v. Chr., bedeutender griechischer Mathematiker. 39 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 int main ( int argc , char ∗∗ argv ) { return p r i n t ( ggT ( r e a d a r g i n t ( argc , argv , 1 ) , r e a d a r g i n t ( argc , argv , 2 ) ) ) ; } Hier die Berechnung von ggt(91,287) ggT(91,287) # 91=0*287+91 = ggT(287,91) # 287=3*91+14 = ggT(91,14) # 91=6*14+7 = ggT(14,7) # 14=2*7+0 = ggT(7,0) = 7 Terminiert das Verfahren immer? Wie schnell terminiert es? Bemerkung: Im ersten Schritt ist 91 = 0 · 287 + 91, also werden die Argumente gerade vertauscht. Der Berechnungsprozess ist iterativ, da nur ein fester Satz von Zuständen mitgeführt werden muss. Satz: Der Aufwand von ggT(a,b) ist O(log n), wobei n = min(a, b). Beweis: Ausgehend von der Eingabe a0 = a, b0 = b, a, b ∈ N0 , a + b > 0, erzeugt der Euklidsche Algorithmus eine Folge von Paaren (ai , bi ), i ∈ N0. Dabei gilt nach Konstruktion ai+1 = bi , bi+1 = ai mod bi. Wir beweisen nun einige Eigenschaften dieser Folge. 1. Es gilt bi < ai für alle i ≥ 1. Wir zeigen dies in zwei Schritten. α. Sei bereits bi < ai , dann gilt ai = q i b i + r i mit 0 ≤ ri < bi. Da ai+1 = bi und bi+1 = ri gilt offensichtlich bi+1 = ri < bi = ai+1. β. Ist b0 < a0 dann gilt wegen α. auch b1 < a1. Bleiben also die Fälle b0 = a0 und b0 > a0 : b0 = a0 ⇒ a0 = 1 · b0 + 0 ⇒ b1 = 0 < b0 = a1. b0 > a0 ⇒ a0 = 0 · b0 + a0 ⇒ b1 = a0 < b0 = a1. 40 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 2. Nun können wir bereits zeigen, dass der Algorithmus terminieren muss. Wegen 1. gilt bi+1 < ai+1 = bi < ai , für i ≥ 1, mithin ist also die Folge der bi streng monoton fallend. Wegen bi ∈ N0 impliziert bi+1 < bi dass bi+1 ≤ bi − 1. Andererseits ist bi ≥ 0 für alle i ≥ 0 da b0 ≥ 0 und bi+1 = ai mod bi. Somit muss irgendwann bi = 0 gelten und der Algorithmus terminiert. 3. Sei bi < ai. Dann gilt bi+2 < ai+2 < ai /2. Dies ist also eine Behauptung über die Konvergenzgeschwindigkeit. Wir unterscheiden zwei Fälle. I. Sei bi ≤ ai /2. Dann gilt ai = qi · bi + ri mit 0 ≤ ri < bi ≤ ai /2, also bi+1 = ri < bi = ai+1 ≤ ai /2. Im nächsten Schritt gilt dann ai+1 = qi+1 · bi+1 + ri+1 mit bi+2 = ri+1 < bi+1 = ai+2 < bi ≤ ai /2. Somit gilt bi+2 < ai+2 < ai /2. II. Sei bi > ai /2. Dann gilt ai = 1 · bi + (ai − bi ), also qi = 1, ri = ai − bi. Damit gilt bi+1 = ri = ai − bi < ai /2 und ai+1 = bi > ai /2 (nach Vor.). Im nächsten Schritt gilt nun wieder ai+1 = qi+1 · bi+1 + ri+1 mit bi+2 = ri+1 < bi+1 = ai+2 < ai /2, also ebenfalls bi+2 < ai+2 < ai /2. Damit ist gezeigt, dass ai und bi nach zwei Schritten noch höchstens halb so groß sind. Da ai , bi ∈ N0 sind höchstens 2 log2 (min(a0 , b0 )) Halbierungen möglich bis bi den Wert 0 erreicht. 2.12 Zahlendarstellung im Rechner In der Mathematik gibt es verschiedene Zahlenmengen: N ⊆ Z ⊆ Q ⊆ R ⊆ C. Diese Mengen enthalten alle unendlich viele Elemente, im Computer entsprechen die di- versen Datentypen jedoch nur endlichen Mengen. Um Zahlen aus N darzustellen, benutzt man ein Stellenwertsystem zu einer Basis β ≥ 2 und Ziffern ai ∈ {0,... , β − 1} Dann bedeutet n−1 X (an−1 an−2... a1 a0 )β ≡ ai β i i=0 Dabei ist n die Wortlänge. Es sind somit die folgenden Zahlen aus N0 darstellbar: 0, 1,... , β n − 1 Am häufigsten wird β = 2, das Binärsystem, verwendet. Zur Darstellung vorzeichenbehafteter Zahlen gibt es verschiedene Möglichkeiten. 41 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 1. Zusätzliches Bit für das Vorzeichen. 2. Zweierkomplement (β = 2) Beispiel: (Zweierkomplement) Für n = 3 setze 0 = 000 -1 = 111 1 = 001 -2 = 110 2 = 010 -3 = 101 3 = 011 -4 = 100 Solange der Zahlenbereich nicht verlassen wird, klappt die normale Arithmetik ohne Be- achtung des Vorzeichens: 3 → 011 -1 → 111 2 → 010 Gebräuchliche Zahlenbereiche in C++ β = 2 und n = 8, 16, 32: char -128... 127 unsigned char 0... 255 short -32768... 32767 unsigned short 0... 65535 int -2147483648... 2147483647 unsigned int 0... 4294967295 2.13 Darstellung reeller Zahlen Neben den Zahlen aus N und Z sind in vielen Anwendungen auch reelle Zahlen R von Interesse. Wie werden diese im Computer realisiert? Festkommazahlen Eine erste Idee ist die Festkommazahl. Hier interpretiert man eine gewisse Zahl von Stellen als nach dem Komma, d. h. n−1 X (an−1 an−2... aq.aq−1... a0 )β ≡ ai β i−q i=0 Beispiel: Bei β = 2, q = 3 hat man drei Nachkommastellen, kann also in Schritten von 1/8 auflösen. Bemerkung: 42 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Jede Festkommazahl ist rational, somit können irrationale Zahlen nicht exakt dar- gestellt werden. Selbst einfache rationale Zahlen können je nach Basis nicht exakt dargestellt werden. So kann 0.1 = 1/10 mit einer Festkommazahl zur Basis β = 2 für kein n exakt dargestellt werden. Das Ergebnis elementarer Rechenoperationen +, −, ∗, / muss nicht mehr darstellbar sein. Festkommazahlen werden nur in Spezialfällen verwendet, etwa um mit Geldbeträgen zu rechnen. In vielen anderen Fällen ist die im nächsten Abschnitt dargestellte Fließkommaarithmetik brauchbarer. Fließkommaarithmetik Vor allem in den Naturwissenschaften wird die Fließkommaarithmetik (Gleitkommaarith- metik) angewendet. Eine Zahl wird dabei repräsentiert als ± a0 + a1 β −1 +... + an−1 β −(n−1) × β e Die Ziffern ai bilden die Mantisse und e ist der Exponent (eine ganze Zahl gegebener Länge). Wieder wird β = 2 am häufigsten verwendet. Das Vorzeichen ist ein zusätzliches Bit. Typische Wortlängen float: 23 Bit Mantisse, 8 Bit Exponent, 1 Bit Vorzeichen ent- sprechen log 2 23 · log10 2 = 23 · ≈ 23 · 0.3 ≈ 7 log 10 dezimalen Nachkommastellen in der Mantisse. double: 52 Bit Mantisse, 11 Bit Exponent, 1 Bit Vorzeichen entsprechen 52 · 0.3 ≈ 16 dezimalen Nachkommastellen in der Mantisse. Referenz: Genaueres findet man im IEEE-Standard 754 (floating point numbers). Fehler in der Fließkommaarithmetik Darstellungsfehler β = 10, n = 3: Die reelle Zahl 3.14159 wird auf 3.14 × 100 gerundet. Der Fehler beträgt maximal 0.005, man sagt 0.5ulp, ulp heißt units last place. Bemerkung: Wenn solche fehlerbehafteten Daten als Anfangswerte für Berechnungen verwendet werden, können die Anfangsfehler erheblich vergrößert werden. Durch Rundung können weitere Fehler hinzukommen. Vor allem bei der Subtraktion kann es zum Problem der Auslöschung kommen, wenn beinahe gleichgroße Zahlen voneinander abgezogen werden. 43 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Beispiel: Berechne b2 − 4ac in β = 10, n = 3 für b = 3.34, a = 1.22, c = 2.28. Eine exakte Rechnung liefert 3.34 · 3.34 − 4 · 1.22 · 2.28 = 11.1556 − 11.1264 = 0.0292 Mit Rundung der Zwischenergebnisse ergibt sich dagegen... 11.2 − 11.1 = 0.1 0.0708 Der absolute Fehler ist somit 0.1 − 0.0292 = 0.0708. Damit ist der relative Fehler 0.0292 = 240%! Nicht einmal eine Stelle des Ergebnisses 1.00 · 10−1 ist korrekt! Typkonversion Im Ausdruck 5/3 ist /“ die ganzzahlige Division ohne Rest, in 5.0/3.0 wird eine Fließ- ” kommadivision durchgeführt. Will man eine gewisse Operation erzwingen, kann man eine explizite Typkonversion ein- bauen: ((double) x)/3 Fließkommadivision ((int) y)/((int) 3) Ganzzahldivision 2.14 Wurzelberechnung mit dem Newtonverfahren Problem: f : R → R sei eine glatte“ Funktion, a ∈ R. Wir wollen die Gleichung ” f (x) = a lösen. Beispiel: f (x) = x2 Berechnung von Quadratwurzeln. √ Mathematik: a ist die positive Lösung von x2 = a. √ Informatik: Will Algorithmus zur Berechnung des Zahlenwerts von a. Ziel: Konstruiere ein Iterationsverfahren mit folgender Eigenschaft: zu einem Startwert x0 ≈ x finde x1 , x2 ,..., welche die Lösung x immer besser approximieren. Definition: (Taylorreihe) h2 ′′ ′ f (xn + h) = f (xn ) + hf (xn ) + f (xn ) +... 2 Wir vernachlässigen nun den O(h2 )-Term (|f ′′ (x)| ≤ C, kleines h) und verlangen f (xn + ! h) = a. Dies führt zu a − f (xn ) h= f ′ (xn ) 44 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 und somit zur Iterationsvorschrift a − f (xn ) xn+1 = xn +. f ′ (xn ) Beispiel: Für die Quadratwurzel erhalten wir mit f (x) = x2 und f ′ (x) = 2x die Vor- schrift 1 a xn+1 = xn +. 2 xn Abbruchkriterium: |f (xn ) − a| < ε für eine vorgegebene (kleine) Zahl ε. Programm: (Quadratwurzelberechnung) #i n c l u d e ” f c p p. hh” bool g u t g e n u g ( double xn , double a ) { return f a b s ( xn∗xn−a ) (6 7 8) 46 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Die Übertragung der inkrementierer-Definition in C++ wäre etwas wie: FUNKTION inkrementierer (int n) { int lokale_funktion (int x) { return x+n; } return lokale_funktion; } Leider ist dieses Konstrukt nicht erlaubt. Bemerkung: Das Schlüsselwort lambda deutet auf den von Alonzo Church in den 1930ern ent- wickelten Lambda-Kalkül hin, in dem etwa die Identität als (λx.x) geschrieben wird. Der Lambda-Kalkül ist eine äußerst kleine, mathematisch sehr elegante Pro- grammiersprache, von der man Turing-Äquivalenz zeigen kann. Scheme, Haskell, etc basieren auf diesem Kalkül. Die Behandlung von Funktionen als Objekte erster Klasse impliziert eine aufwendi- gere Art der Speicherverwaltung, die mit einem gewissen Effizienzverlust einhergeht. Aus diesem Grund wird diese Technik zum Beispiel in C++ nicht erlaubt. Auch FC++ wäre Turing-äquivalent, wenn man beliebig lange int-Zahlen hätte. Der Lambda-Kalkül kommt sogar ohne Zahlen aus. Warum funktionale Programmierung? Mathematisch am besten verstanden ⇒ relativ oft sind Korrektheitsbeweise von funktionalen Programmen möglich Wenn man zusätzlich Syntaxtransformationen erlaubt, lassen sich viele bekannte Merkmale von Programmiersprachen (z.B. lokale Variablen, Schleifen, Objekte) sehr einfach erhalten Aber: Funktionales Programmieren ist nicht für alle Situationen die beste Wahl! Zum Beispiel legt die Interaktion mit der Außenwelt oder ihre effiziente Nachbildung oft an- dere Paradigmen nahe. Funktionale Sprachen haben deshalb auch oft nicht-funktionale Sprachelemente. Zusammenfassung Die funktionale Programmierung kommt mit wenigen Konzepten aus C++ aus: Definition von Funktionen, Auswertung von Ausdrücken und cond-Funktion. Bestimme Probleme lassen sich mit rekursiv formulierten Algorithmen (und nur mit diesen) sehr elegant lösen. 47 Heruntergeladen durch Mariam Assi ([email protected]) lOMoARcPSD|34983113 Allerdings können ungeschickte rekursive Formulierungen auch zu sehr langen Lauf- zeiten führen. Mittels geeigneter Formulierung und Ausnutzung der Endrekursion kann dies umgangen werden 3 Prozedurale Programmierung 3.1 Lokale Variablen und die Zuweisung Erinnerung: Bis jetzt haben wir Namen nur als Funktionssymbole und im Zusammen- hang mit formalen Parametern einer Funktion kennengelernt. Innerhalb des Funktionsrumpfes steht der Name des formalen Parameters für einen Wert (der zum Zeitpunkt der Funktionsdefinition unbekannt ist). Konstanten In C++ kann man konstante Werte wie folgt mit Namen versehen: float umfang (float r) { const double pi = 3.14159265; return 2*r*pi; } int hochacht (int x) { const int x2 = x*x; // jetzt gibt es ein x2 const int x4 = x2*x2; // nun ein x4 return x4*x4; } Bemerkung: Einer solchen Konstanten kann nur einmal ein Wert zugeordnet werden. Die Auswertung solcher Funktionsrümpfe erfordert eine Erweiterung des Substitu- tionsmodells: – Ersetze formale Parameter durch

Einführung in die praktische Informatik Skript PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue