Allgemeine Informatik WS 2000/01
Prof. Dr. H. Neumann $\bullet$ Dr. K. Murmann $\bullet$ S. Geschwentner $\bullet$ Dr. F. Schwenker

Übungsblatt für die vorlesungsfreie Zeit im WS 00/01



1. Aufgabe: Implementation endlicher Automaten
Implementieren Sie den endlichen Automaten aus Aufgabe 29 in Modula-2. Für Eingaben über dem Alphabet $\{a,b\}$ soll die Folge der Zustände ausgegeben werden. Bei ungültigen Eingaben soll das Programm mit einer entsprechenden Meldung abbrechen. Falls der Automat die Eingabe akzeptiert, d.h. mit abgearbeiteter Eingabe im Endzustand bleibt, soll die Meldung Eingabe akzeptiert! erfolgen.



2. Aufgabe: 2D Zeichenfelder
Implementieren Sie einen Filter, der jede Eingabezeile in Felder unterteilt und diese in umgekehrter Reihenfolge wieder ausgibt. Dabei erfolgt die Unterteilung einer Zeile in Felder durch einen Feldtrenner, der als Konstante im Programm definiert wird. Ein Feld besteht also aus allen Zeichen ungleich Feldtrenner und Zeilenende. Implementationshinweis: Ein zweidimensionales ARRAY soll benutzt werden. Beispiel:

Eingabesatz:    heute:kommt der:Nikolaus

Trenner = ' '   Feld1 =	"heute:kommt",   Feld2 = "der:Nikolaus"
                Ausgabe: "der:Nikolaus heute:kommt"

Trenner = ':'   Feld1 = "heute",         Feld2 = "kommt der",   Feld3 = "Nikolaus"
                Ausgabe: "Nikolaus:kommt der:heute"
Die maximale Feldanzahl pro Zeile, sowie die maximale Feldlänge sollen ebenfalls als Konstante definiert werden. Das Programm soll erkennen, wenn die oberen Grenzen überschritten werden und eine entsprechende Fehlermeldung ausgeben. Eine Fehlermeldung soll also ausgegeben werden, wenn eine zu lange Zeile oder ein zu langes Feld in der Eingabe auftaucht. In einem solchen Fall soll das Programm beendet werden.

Testen Sie Ihr Programm mit geeigneten Text-Dateien!



3. Aufgabe: Zeichenfelder
In der vorherigen Aufgabe haben Sie bereits eine Zeile in Felder zerlegt und diese wiederum in einem Feld abgelegt. Dazu haben Sie ein zweidimensionales ARRAY benutzt. Der Nachteil dieser Methode ist, daß relativ viel Platz verschenkt wird, da kleine Felder genauso viel Platz benötigen wie große.

Eine weitere Möglichkeit besteht darin, die Worte hintereinander in ein großes Zeichenfeld zu schreiben (wieder unter Verwendung des Null-Bytes 0C):

  
  0   1   2   3   4   5   6   ....           11 12  ....
----------------------------------------------------------------------------
  W   o   r   t   1  0C   W   o   r   t   2  0C  W   o   r   t   3  0C  ....

Bei dieser Methode ist die Verwendung eines Indexfeldes sinnvoll, in dem die Wortanfänge abgelegt werden.

  0   1	  2    ...
---------------------
  0   6  12    ...

Schreiben Sie ein Modula-2-Programm, das jeweils eine Zeile seiner Eingabe liest, die Zeile in Worte unterteilt und die Worte in die oben beschriebene Struktur ablegt. Am Ende einer Zeile sollen die Worte ausgegeben und anschließend die nächste Zeile abgearbeitet werden.

Ein Wort ist dabei eine Folge von Buchstaben und Ziffern. Sonstige Zeichen (Satzzeichen, usw.) sollen ignoriert werden.

Die maximal erlaubte Anzahl von Wörtern innerhalb einer Zeile, sowie die maximale Anzahl von Zeichen innerhalb einer Zeile sollen wieder durch Konstante definiert werden, damit das Programm leicht an andere Anforderungen angepaßt werden kann.



4. Aufgabe:
Ein Kettenbruch der Tiefe $n$ mit Koeffizienten $a_0,\ldots,a_n \in {\rm I\! N}$ ist eine rationale Zahl $x$ nach der folgenden Bauart (hier speziell Tiefe $5$):

\begin{displaymath}
x = a_0+\frac{1}{\displaystyle a_1 +
\frac{1}{\displaystyl...
... +
\frac{1}{\displaystyle a_4 +
\frac{1}{a_5}
}
}
}
}
\end{displaymath}

Zur Abkürzung schreibt man $x_n=[a_0,a_1,\ldots,a_n]$. Schreiben Sie ein Modula-2 Programm zur Berechnung von Kettenbrüchen mit beliebiger Tiefe $n$ mit den Koeffizienten $a_k =1$ für $k\ge 0$. Das Programm soll als Eingabe eine CARDINAL Zahl $n$ einlesen und den Kettenbruch $x=[1,1,\ldots,1]$ ($x$ mit $n$ Einsen) als Ergebnis ausdrucken.



5. Aufgabe: Prozeduren
Schreiben Sie eine Modula-2-Funktionsprozedur, die das bestimmte Integral $\int_a^b f(x) dx$ einer stetigen reellwertigen Funktion $f(x)$ durch numerische Integration näherungsweise berechnet und diese Näherung als Ergebnis zurückliefert. Verwenden Sie für die numerische Integration die Trapezregel:

\begin{displaymath}
\int_a^b f(x) \approx h \left( \frac{f(a)}{2} + f(a+h) + f(a+2h) + \cdots +f(b-2h) + f(b-h) + \frac{f(b)}{2} \right)
\end{displaymath}

mit $h = (b-a)/n, n \in {\rm I\! N}$.

Der Prozedur sollen als Parameter eine beliebige reellwertige Funktion $f(x)$, die Integrationsgrenzen $a$ und $b$ sowie die Zahl $n$ (Schrittweite $h=(b-a)/n)$ übergeben werden.

Schreiben Sie ein Modula-2 Programm zum Testen der Prozedur und berechnen Sie die folgenden Integrale:

\begin{displaymath}
\int_0^\pi \sin x \,dx,
\int_\pi^{2\pi} \cos x \,dx,
\int_0^2 x^2 \,dx,
\int_1^5 1/x \, dx,
\int_0^1 e^x \,dx,
\end{displaymath}

Wird die Approximation mit wachsendem $n$ immer besser?



6. Aufgabe: Prozeduren
Für die numerische Integration von reellwertigen Funktionen sind, neben der Trapezregel, viele andere Verfahren bekannt. Ein davon ist die Simpsonregel:

\begin{displaymath}
\int_a^b f(x) \approx \frac{h}{3} \left( f(a) + 4f(a+h) + 2f(a+2h) + 4f(a+3h) + \cdots + 2f(b-2h) + 4f(b-h) + f(b) \right)
\end{displaymath}

mit $h = (b-a)/n, n \in {\rm I\! N}$ gerade!

Erweitern Sie die Modula-2-Prozedur aus Aufgabe 6 derart, daß neben der zu integrierenden Funktion auch die Integrationsregel als Parameter übergeben wird.

Berechnen Sie die Integrale aus Aufgabe 6 nun mit der Simpsonregel.





Stefan Geschwentner 2001-04-26