Prof. Dr. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 16.11.2005
Norbert Heidenbluth Blatt 5






Allgemeine Informatik I für Mathematiker/Wirtschaftsmathematiker
(WS 2005/2006)


Abgabetermin: 23. November 2005

In der Informatik kommt man immer wieder mit unterschiedlichen Zahlensystemen in Berührung, insbesondere mit dem Dual-, dem Oktal und dem Hexadezimalsystem. Das Konvertieren vom einen System in die anderen (auch in das uns vertraute Dezimalsystem) üben wir in der ersten Aufgabe.

Die zweite Aufgabe macht uns ein wenig mit formalen Grammatiken vertraut, auf der jede (Programmier)sprache aufgebaut ist. Sie ist theoretisch gehalten und statt mit dem Rechner diesmal mit ``Papier und Bleistift'' zu lösen. Aber wie sagte einst Immanuel Kant (1724-1804): ``Es gibt nichts Praktischeres als eine gute Theorie.''

Die dritte und letzte Aufgabe beschäftigt sich dann noch mit unterschiedlichen Möglichkeiten, Prozesse zu beenden.

Aufgabe 9: Nachsitzen für Pisa, die erste (2 Punkte)

Die jüngste Pisa-Studie hat es zu Tage gebracht: wir beherrschen immer weniger die Mathematik!

Na gut, $4+5$ geht gerade noch so, aber was ist zum Beispiel $4A+5B$? Und wußten Sie schon, daß $4656_{8}+8B9_{16}=4711_{10}$ sind? Wie? Nicht? Dann haben Sie also auch zu dem Pisa-Ergebnis beigetragen?

Okay, wenn das so ist, dann wärmen wir uns für dieses Übungsblatt gleich mit einer kleinen Rechenaufgabe auf: Sie lautet:

``Vervollständigen Sie die folgende Tabelle!''

	Dezimal	Dual	Oktal	Hexadezimal
			144
		1100101111
				7b
	2005
$\sum$	3043

Aufgabe 10: Nachsitzen für Pisa, die zweite (4 Punkte)

Erwähnte ich eben die neueste Pisa-Studie? Was diese ebenfalls zu Tage gebracht hat, ist: wir tun immer weniger das deutsche Grammatik beherrschen!

``Gut,'' werden Sie sagen, ``deshalb studiere ich ja auch etwas Naturwissenschaftliches und nicht Germanistik¹''. Das Dumme dabei ist nur, daß auch in der Informatik - und jede Naturwissenschaft macht heutzutage von der Informatik Gebrauch - mit Grammatiken gearbeit wird.

Wie gut, daß es da dieses Übungsblatt gibt, denn wir geben Ihnen nun die folgende Grammatik:

• $V_T = \{\mbox{\lq\lq 0''}, \mbox{\lq\lq 1''}, \mbox{\lq\lq ,''}, \mbox{\lq\lq (''}, \mbox{\lq\lq )''}\}$
• $V_N = \{\langle \mbox{List} \rangle, \langle \mbox{Elements} \rangle, \langle \mbox{Parenthesis} \rangle, \langle \mbox{Element} \rangle\}$
• Produktionsregeln P:
  $$\begin{eqnarray*} \langle \mbox{List} \rangle & \longrightarrow & \epsilon ... ... \mbox{Element} \rangle \langle \mbox{Parenthesis} \rangle \\ \end{eqnarray*}$$
  
  
  
  
  

• Startsymbol $S = \langle \mbox{List} \rangle$

Nach dem kurzen Studium dieser Grammatik sind Sie bestimmt sofort in der Lage, die folgenden kleinen Aufgaben zu lösen:

• Bei welchen der folgenden Sequenzen von Symbolen aus $V_T$ handelt es sich um Sätze der Grammatik?
  1. ``0''
  2. ``0,''
  3. ``0,1''
  4. ``(0)''
  5. ``()0()''
  6. ``(0)(1)''
  7. ``(0)0(1)''
  8. ``(0),1,(1)''
  9. ``(1)1(0),1''
  10. ``(1),1(0)1''
  11. ``(0)(0)0(0)0(0)''
  12. ``(0)(0)1(1)(1)''
  13. ``1,,1''
  14. ``01''

• Geben Sie in den Fällen, bei denen es sich um Sätze der Grammatik handelt, die formalen Ableitungsregeln an.

• Denken Sie sich einen Satz dieser Grammatik aus, der mit zwei unmittelbar aufeinanderfolgenden Klammern beginnt und geben Sie dessen formale Ableitungsregel an.

Aufgabe 11: Das Kill(er)-Kommando (4 Punkte)

``Luigi, schaff' ihn weg! Nimm' seine Füße und steck sie in eine Schale mit Beton! Und dann versenke ihn - in der Donau!''

So oder so ähnlich klingt die Ausführung eines Killer-Kommandos der Mafia. Die Ausführung des kill-Kommandos verstößt hingegen nicht gegen das Strafgesetzbuch. Und deshalb arbeiten wir in dieser Aufgabe mal damit.

• Laden Sie sich für diese Aufgabe zunächst das Programm ``eternity'' von unserem FTP-Server herunter.
• Wenn Sie es auf einem unserer Rechner ausführen möchten, benötigen Sie das Programm eternitySolaris. Für den Linux-Rechner benötigt man stattdessen jedoch eternityLinux².
• Kontrollieren Sie mit ls -l, ob es ausführbar ist. Wenn nicht, geben Sie chmod +x eternitySolaris (bzw. chmod +x eternityLinux) ein.

Teil a: Killen via Tastatur

• Starten Sie das Programm im Vordergrund.
• Brechen Sie es nun mit einem ``geeigneten Tastenkommando'' ab.

Teil b: Wir spielen mit Signalen

• Starten Sie das Programm erneut im Vordergrund und spielen Sie die Teilaufgabe a) erneut durch, wobei Sie diesmal die Signale nicht via Tastatur-Kürzeln sondern via kill senden.
  Wichtig: Hier soll nicht das Signal ``-9'' (sigkill) verwendet werden!

Teil c: 3 auf einen Streich

• Öffnen Sie nun (auf stets demselben Rechner) vier Shells und starten Sie in dreien von ihnen das sensationelle Programm ``eternity'' (jeweils im Vordergrund).
• Bauen Sie sich auf der verbliebenen Shell aus den folgenden Zutaten (noch anzureichern durch sinnvolle Optionen) eine (mehrfache) Pipe, die die Prozeß-IDs aller drei Programmausführungen ermittelt und diese durch Senden des Signals ``sigkill'' (-9) augenblicklich und automatisch (d.h. ohne Eingriffe ihrerseits) beendet.
• Ach ja, die Zutaten$\ldots$
  • kill
  • grep
  • ``Backticks''
  • cut
  • ps
  Tip: Die angegebene Reihenfolge der Kommandos ist nicht diejenige, in der die Kommandos verwendet werden sollen. Außerdem muß eines der Kommandos gleich doppelt verwendet werden!

Genereller Hinweis:

Die ersten beiden Aufgaben dieses Blattes sind ausnahmsweise mal schriftlich zu bearbeiten. Zwar genügt auch hier eine Lösung pro Gruppe, aber während des Tutorium muß jeder in der Lage sein, die Lösungswege bei diesen Aufgaben zu erklären.

Viel Spaß!

Fußnoten

... Germanistik¹

Dabei fällt uns doch sofort ein Zitat von Harald Schmidt ein: ``Taxifahrer sind die Karrieretypen unter den Germanisten!''

...ftp://ftp.mathematik.uni-ulm.de/pub/vorlesungen/ws05/ai1/uebungen/blatt5/bsp/eternityLinux²

Wer die Aufgabe partout auf irgendetwas anderem (außer Windows) lösen möchte, kann von mir auch gerne den streng geheimen Quellcode bekommen und es selber übersetzen (es ist ein C-Programm).