Begleitmaterial zum PRAKTIKUM EINFÜHRUNG IN DIE INFORMATIK

Transcrição

Begleitmaterial zum
PRAKTIKUM
EINFÜHRUNG IN DIE INFORMATIK
Fachhochschule Fulda
Fachbereich Elektrotechnik und Informationstechnik
Prof. Dr. Timm Grams
Datei: InfPrakt_c.doc
9. September 2002
(Erstausgabe der Pascal-Version: 8.9.94; erste C-Version: 25.11.99)
2
PRAKTIKUM EINFÜHRUNG IN DIE INFORMATIK
Gliederung
Vereinbarung zum Leistungsnachweis.................................................................................................................... 2
Teil I ............................................................................................................................................................................... 3
Handhabung des Computers.................................................................................................................................. 3
0 Zur Vorbereitung: Einführung in die Hardware des PC-Labors.................................................................... 3
1 EBNF und einfache Betriebssystembefehle (MS-DOS) ............................................................................... 3
2 Der MS-DOS-Editor......................................................................................................................................... 5
3 Computerarithmetik. Tabellenkalkulation mit Excel .................................................................................. 5
4 Einführung in SPICE: Logiksimulation........................................................................................................... 6
5 Simulation eines Schaltnetzes: Addierer ........................................................................................................ 8
6 Simulation eines Schaltwerkes: Speicher....................................................................................................... 8
7 Synthese eines Automaten: Gray-Code-Zähler.............................................................................................. 8
8 Assembler-Programmierung............................................................................................................................ 8
Ausdrücke.................................................................................................................................................................. 9
9 Syntaxbäume...................................................................................................................................................... 9
10 Logische Spielräume ...................................................................................................................................... 9
11 Logikrätsel ...................................................................................................................................................... 9
Teil II............................................................................................................................................................................ 11
Einfache Datentypen und While-Programme .................................................................................................... 11
12 Einfache C-Programme................................................................................................................................ 11
13 Algorithmen: Umcodierung zwischen Zahlensystemen u. a. .................................................................... 12
14 Invariante: Polynomauswertung................................................................................................................... 12
15 Betrag komplexer Zahlen............................................................................................................................. 13
16 Fixpunkt- und Nullstellenberechnung ......................................................................................................... 13
17 Elementare Sortierverfahren ....................................................................................................................... 13
Datentypen und Funktionen................................................................................................................................. 14
18 Scheinwiderstand eines Serienschwingkreises .......................................................................................... 14
19 Statistik über wundersame Zahlen............................................................................................................... 14
20 Lineare Liste ................................................................................................................................................. 14
21 Satzzerlegung ................................................................................................................................................ 16
Studie: Shannon-Codierung ................................................................................................................................ 17
Testate zum Praktikum Einführung in die Informatik (ET) .............................................................................. 18
Anhang: Aus den Klausuren................................................................................................................................. 19
Kopf des Aufgabenblattes einer Klausur.......................................................................................................... 19
Klausuraufgaben mit Musterlösung.................................................................................................................. 19
Ausgewählte Klausuraufgaben........................................................................................................................... 21
Aufgaben der Klausur vom 08.07.02................................................................................................................ 25
Vereinbarung zum Leistungsnachweis
Der Leistungsnachweis für die Lehrveranstaltung „Einführung in die Informatik“ wird in einer
Klausur erbracht. Klausurdauer: 90 Minuten. Erreichbare Punkte: 90. Im Praktikum können für
die Praktikumsversuche vorab bis zu 15 Punkte erworben werden. Diese Punkte werden auf
dem Testatzettel bescheinigt und in der Klausur angerechnet. Die Testate gelten für die Klausur,
die sich der Lehrveranstaltung unmittelbar anschließt, und gegebenenfalls für die Wiederholungsklausur.
3
Teil I
Handhabung des Computers
0 Zur Vorbereitung: Einführung in die Hardware des PC-Labors
Der Aufbau eines Personal Computers: Tastatur, Bildschirm, Zentraleinheit. Prozessor. Hauptspeicher. BIOS (Basic Input Output System). Externe Datenspeicherung: Laufwerke und Laufwerksbezeichnungen. Laufwerke für Festplatte und Disketten. Diskettenformate. Das Hochschulnetz. Weitere Peripheriegeräte.
1 EBNF und einfache Betriebssystembefehle (MS-DOS)
Die Dateneingabe geschieht in sprachlicher Form. Bereits die Kommunikation mit dem Betriebssystem erfordert ein Mimium an sprachlichen Vereinbarungen. Die Syntax (auch: Grammatik) einer Sprache legt fest, was unter einem wohlgeformten Ausdruck oder Satz zu verstehen
ist. Zur Syntaxdarstellung dient die erweiterte Backus-Naur-Form (EBNF) in Anlehnung an den
Pascal-Standard DIN 66 256. In der Metasprache EBNF werden die Symbole in folgenden Bedeutungen verwendet:
"="
steht für "ist definiert als"
"|"
für "alternativ"
"[x]"
für "kein oder ein Auftreten von x"
"{x}"
für "kein, ein- oder mehrfaches Auftreten von x"
"{x}n"
für "0- bis maximal n-faches Auftreten von x"
Die Festlegung der Syntax geschieht durch eine Reihe von Produktionsregeln der Gestalt
Nichtterminales Symbol = Rechte Seite der Produktionsregel
Nichtterminale Symbole werden kursiv geschrieben, terminale Symbole nichtkursiv und fett.
Jedes nichtterminale Symbol kommt in wenigstens einer Produktionsregel auf der linken Seite
vor. Die Produktionsregeln definieren die möglichen Ersetzungen eines nichtterminalen Symbols durch andere (nichtterminale oder terminale) Symbole. Es gibt ein Startsymbol und alle gemäß der Syntaxdefinition - wohlgeformten Sätze lassen sich aus diesem Startsymbol durch
sukzessive Ersetzungen herleiten.
Wichtige und häufig benötigte Betriebssystembefehle von MS-DOS (1991) leiten sich aus dem
Startsymbol Kommando gemäß Tabelle 1.1 her. Konstruieren Sie die Kommandos mittels
EBNF durch schrittweises Ersetzen der Nichtterminalsymbole.
Aufgabe 1: Schalten Sie den Computer ein. Nach Erscheinen der Eingabeaufforderung eröffnen Sie eine Sitzung (Session) mit dem Befehle LOGIN ALL. Beenden Sie die Sitzung mit dem
Befehl LOGOUT. Verlassen Sie den Arbeitsplatz nie ohne diesen letzten Schritt!
Aufgabe 2: Formatieren Sie die eigene Diskette und tragen Sie eine Datenträgerbezeichnung
ein. Für die Formatierung gibt es das DOS-Kommando
format [Laufwerk:]
ACHTUNG: Der Formatierungsbefehl zerstört sämtliche Dateien auf dem Datenträger. Grundsätzlich sollten Sie vorher überprüfen, ob bzw. was auf dem Datenträger steht.
4
Aufgabe 3: Legen Sie die folgenden Unterverzeichnisse an:
+-¦
¦
+-+-+--
LVA
+-- INFORM
+-- MATHE
XYZ
PRIVAT
VOLATILE
- Sehen Sie sich (auf Bildschirm) die Inhalte der Verzeichnisse an.
- Sehen Sie sich den Verzeichnisbaum an.
- Löschen Sie das Verzeichnis XYZ und sehen Sie sich den Verzeichnisbaum an
Tabelle 1.1 Syntax häufiger MS-DOS-Kommandos
Kommando = Verzeichniskommando|Dateikommando
Verzeichniskommando = Verzeichnis_auflisten|Verzeichnis_anlegen|
Verzeichnis_löschen|Verzeichnis_wechseln|
Verzeichnisbaum_ausgeben|Laufwerk_wechseln
Verzeichnis_auflisten = dir [Verzeichnis] [[\]Dateiname] [/w]
Verzeichnis_anlegen = md Verzeichnis
Verzeichnis_löschen = rd Verzeichnis
Verzeichnis_wechseln = cd Verzeichnis
Verzeichnisbaum_ausgeben = tree Verzeichnis
Laufwerk_wechseln = Laufwerk:
Dateikommando = Dateiinhalt_anzeigen|Datei_löschen|
Datei_kopieren|Umbenennen
Dateiinhalt_anzeigen = type Datei
Datei_löschen = del Datei
Datei_kopieren = copy Quelle [Ziel]
Umbenennen = ren Datei Dateiname
Quelle = Datei
Ziel = Datei
Datei = [Verzeichnis \] Dateiname
Verzeichnis = [Laufwerk:]Pfad
Laufwerk = Buchstabe
Pfad = \
Pfad = [.|..|Verzeichnisname]{\Verzeichnisname}
Verzeichnisname = {Zeichen}7Zeichen
Dateiname = {Zeichen}7Zeichen[.{Zeichen}3]
Zeichen = Buchstabe|Ziffer|Sonderzeichen|Platzhalter
Buchstabe = A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|
V|W|X|Y|Z
Ziffer = 0|1|2|3|4|5|6|7|8|9
Sonderzeichen = _|^|$|~|!|#|%|&|-|{|}|(|)|@|'|`
Platzhalter = *|?
Hilfe: Kommandoname /?
5
2 Der MS-DOS-Editor
Das primäre Werkzeug des Programmierers (Software-Konstrukteurs) ist der Editor. In diesem
Praktikum wird der Umgang mit einem einfachen Editor geübt. Dabei werden die Tastatur und
die spezielle Zeichencodierung der PCs erkundet.
Aufgabe 1: Rufen Sie den MS-DOS-Editor mit dem DOS-Befehl edit auf und studieren Sie das
Hilfe-System. Sehen Sie sich die wichtigsten Editorbefehle an.
Aufgabe 2: Schreiben Sie den Kopf des Textes: Name, Ort, Datum, Titel
Aufgabe 3: Erzeugen Sie die folgende Textzeile:
@âéà|~^'`
Einige der Zeichen werden mit der Kompositionsmethode erzeugt: Zur Erzeugung des Zeichens
é beispielsweise ist erst der Akut und dann das e einzugeben.
Aufgabe 4: Erzeugen Sie mithilfe der numerischen Tastatur bei gleichzeitigem Drücken der
<Alt>-Taste Zeichen des 7-Bit-Codes (Dezimalcodierung vom 0 bis 127). Erzeugen Sie Zeichen aus der erweiterten Codetabelle (Dezimalcodierung von 128 bis 255).
Aufgabe 5: Bewegen Sie den Cursor im Text. Kopieren, verschieben und löschen Sie Textteile.
Aufgabe 6: Speichern Sie die erzeugte Datei unter dem Namen pctext1 in dem Verzeichnis
a:\LVA\MATHE ab. Verlassen Sie den Editor.
Aufgabe 7: Sehen Sie sich die Inhalte der Verzeichnisse Ihrer Diskette an. Kopieren Sie die
Datei pctext1 vom Verzeichnis a:\LVA\MATHE in das Verzeichnis a:\LVA\INFORM. Sehen Sie
sich die Verzeichnisse an. Löschen Sie die Datei a:\LVA\MATHE\pctext1. Sehen Sie sich die
Verzeichnisse an.
Aufgabe 8: Gehen Sie erneut in den Editor, laden Sie die Datei pctext1 und bearbeiten Sie sie
erneut. Verlassen Sie den Editor, nachdem Sie gespeichert haben. Sehen Sie sich nun ihre Verzeichnisse an.
Aufgabe 9: Geben Sie die Datei pctext1 direkt mit dem Betriebssystemkommando auf Bildschirm aus.
3 Computerarithmetik. Tabellenkalkulation mit Excel
Aufgabe 1: Machen Sie sich mit der Tabellenkalkulation vertraut. Studieren Sie die Lektion
"Simulation mit Tabellenkalkulation" im Hypertext "Umweltsimulation mit Tabellenkalkulation"
http://www.fh-fulda.de/~grams/oekosim.htm
Erstellen Sie parallel dazu ein eigenes Arbeitsblatt zur Lösung der Kaninchenaufgabe von Fibonacci.
Aufgabe 2: Ermitteln Sie in einem Arbeitsblatt den relativen Rundungsfehler ε den die Gleitpunktarithmetik des Tabellenkalkulationsprogramms macht. Hinweis: Suchen Sie nach einer
möglichst kleinen Zahl ε, für die die Gleitpunktdarstellung von 1 + ε gerade noch ungleich 1 ist.
Beginnen Sie mit ε = 1 und halbieren Sie den Wert sukzessive. Führen Sie diese Rechnung in
einer Spalte des Arbeitsblattes durch. Legen Sie daneben eine Spalte an, die anzeigt, ob die
Differenz zum vorherigen Wert ungleich oder gleich null ist. Stellen Sie das Zahlenformat so
ein, dass Sie wenigstens die signifikanten Nachpunktstellen sehen können.
6
Aufgabe 3: Erstellen Sie ein Arbeitsblatt zur Bestimmung der Quadratwurzel des Eingabewerts
a. Die Quadratwurzel ist Fixpunkt der Funktion
f(x) = (x + a/x)/2
(Newtonsche Methode). Die Voraussetzungen dafür, dass die Rekursionsformel xk+1:= f(xk)
eine konvergente Folge x0, x1, x2, ... liefert, sind gegeben. Die Berechnung der Werte geschieht
in einer Spalte des Arbeitsblattes. Legen Sie für die Konstante a ein eigenes Feld an, so dass
sie den Wert variieren können, ohne die Formel immer wieder kopieren zu müssen. Bilden Sie
in einer Spalte außerdem die Differenzen aufeinanderfolgender Werte.
Wählen Sie den Anfangswert x0 = 1. Achten Sie auf hohe Genauigkeit. Testen Sie den Algorithmus mit folgenden Werten für a: 2.25, 4, 106, 0.1, 1, 0, 1034, 10-34, 0.999999999999,
10100, 10-100. Wichtige Regel für's Testen: Erst das erwartete Testergebnis festlegen, dann
Testdaten eingeben, dann Ergebnis prüfen!
Aufgabe 4: Führen Sie die Berechnung von √2 mit der Methode aus Aufgabe 3 "von Hand"
durch. Legen Sie eine 7-Bit-Gleitpunktdarstellung in Anlehnung an die IEEE Definitionen
zugrunde. Nehmen Sie 1 Bit für das Vorzeichen und je drei Bits für Exponenten und Mantisse.
Aufgabe 5: Berechnen Sie mittels Tabellenkalkulation näherungsweise die Summe der Reihe
1/n - 1/(n+1) + 1/(n+2) -1/(n+3) ± ... Diese Reihe konvergiert bekanntlich. Beantworten Sie die
Frage: Bis zum wievielten Reihenglied muss die Summe für ein halbwegs aussagekräftiges Ergebnis reichen? Genügt die Vorgabe einer absoluten Genauigkeit? Beispielsweise: Das Ergebnis darf von Schritt zu Schritt um höchstens den Wert 0.01 variieren. Oder muss man zur Vorgabe einer relativen Genauigkeit übergehen. Begründen Sie ihre Antwort. Hinweis: Führen Sie in
einer Spalte den relativen Zuwachs je Reihenglied mit und in einer anderen den absoluten. Variieren Sie n um mehrere Größenordnungen (n=1, 10, 100, 1000, ...). Welche Information liefert
der relative Zuwachs - was sagt ihnen der absolute Zuwachs?
4 Einführung in SPICE: Logiksimulation
Aufgabe: Machen Sie erste Bekanntschaft mit dem Programm SPICE, genauer: PSpice für Windows (Design Center). Nutzen Sie das Hilfesystem. Bereiten Sie Logiksimulation vor. Suchen
Sie die Kennzeichnungen der wichtigsten Gattertypen. Stellen Sie diese auf dem Bildschirm
dar. Experimentieren Sie mit Signalgeneratoren. Geben Sie die Ausgangsverläufe auf Bildschirm aus. Erläutern Sie die notwendigen Handlungen für
• Schaltungseingabe
• Definition der Eingangssignale
• Ausgabe der Zeitverläufe der Ein- und Ausgangsgrößen.
Tips für das Arbeiten mit dem Design Center
Das Erstellen von Schaltplänen geschieht mit dem Programm Schematics. Von dort aus werden
auch die Simulation und die Ausgabe per Menü gestartet (Menüpunkt: Analysis).
Das Auswählen und Plazieren von Bausteinen sowie das Verdrahten geschieht hauptsächlich
über den Menüpunkt Draw. Bei diesen Aktionen kann man sich weitgehend der Führung durch
die Benutzeroberfläche anvertrauen. Falls Sie doch einmal ratlos sind: Hilfesystem befragen
(Taste <F1> oder Menüpunkt Help).
7
Grundregeln für die Benutzung der Maus:
Klick links
Doppelklick links
Doppelklick links auf einem Objekt
<Shift> + Doppelklick links
Klick rechts
Doppelklick rechts
Auswahl des angeklickten Punktes
Beenden eines Modus
Editieren des Objekts
Erweiterte Auswahl
Abbrechen eines Modus
Wiederholen einer Aktion
Plazierung: Das Muster eines ausgewählten Bauelements ist bis zum Abbrechen des Plazierungsvorgangs (Klick rechts) mit dem Mauszeiger verbunden. Durch Klick links werden Exemplare dieses Bauelements erzeugt und plaziert.
Verschieben: Klick links, festhalten, Verschieben, loslassen.
Drehen eines Bauelements: Auswählen (Klick links), <Strg>+R.
Spiegeln: <Strg>+F.
Editieren/Ändern: Doppelklick links auf Bauelement
Verschieben und Editieren/Ändern von Bauteilwerten: siehe oben.
Das Editieren geschieht im Statusdialogfenster eines Bauteils. Mit "*" gekennzeichnete Einträge
sind unveränderlich.
Verbinden: Auswahl des Menüpunkts Draw Wire. Je ein Klick links auf den zu verbindenden
Bauteilleitungen. Abbrechen: Klick rechts. Nächste Verbindung: Doppelklick rechts.
Knotennamen festlegen: Doppelklick links auf Leitung.
Generieren (mehrfacher) digitaler Signale mit dem Stimulusgenerator STIM4:
- Auswählen und Plazieren wie oben
- Anschließen eines Busses (Menüpunkt: Draw Bus)
- Festlegung des Busnamens: analog zur Festlegung eines Knotennamens. Namenskonvention:
Bezeichner[0:3]. Die Zahlen 0, 1, 2 und 3 beziehen sich auf die Pins des Stimulusgenerators.
- Herausziehen einer Einzelleitung: Verbinden einer Leitung mit dem Bus. Zuordnung eines
Knotennamens: Bezeichner0, Bezeichner1, Bezeichner2 oder Bezeichner3.
- Editieren des Signalgenerators. Die Kommandos (Command1, Command2, Command3 usw.)
legen den Signalverlauf fest. Beispielsweise definieren die Kommandos
COMMAND1=
COMMAND2=
COMMAND3=
COMMAND4=
COMMAND5=
COMMAND6=
COMMAND7=
COMMAND8=
COMMAND9=
COMMAND10=
COMMAND11=
COMMAND12=
COMMAND13=
COMMAND14=
COMMAND15=
COMMAND16=
+0c
+1c
+1c
+1c
+1c
+1c
+1c
+1c
+1c
+1c
+1c
+1c
+1c
+1c
+1c
+1c
die folgenden vier Signale
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
8
Pin0
Pin1
Pin2
Pin3
+-------------------------------------------------------+
+-----------+
+-------------------------------+
+-----------+
+-----+
+-----+
+-----+
+-------------------+
+-----+
+-----+
+-----+
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +-------------+ +--+ +--+ +--+ +--+ +--+ +--+ +--+
Die Schrittweite c = 1 µs wird festgelegt durch
TIMESTEP= 1us
Markieren von Ausgangsgrößen: Menüpunkt Markers
5 Simulation eines Schaltnetzes: Addierer
Aufgabe: Führen Sie mit SPICE die Simulation eines Volladdierers durch. Benutzen Sie nur
elementare Gatterbausteine.
Einige Bausteiene der 74er Familie:
7400:
7402:
7404:
7408:
7432:
NAND
NOR
NOT (Inverter)
AND
OR
6 Simulation eines Schaltwerkes: Speicher
Aufgabe: Führen Sie mit SPICE die Simulation eines D-Flip-Flops durch. Benutzen Sie nur
elementare Gatterbausteine.
7 Synthese eines Automaten: Gray-Code-Zähler
Aufgabe: Führen Sie mit SPICE die Simulation des umschaltbaren Gray-Code-Zählers durch.
Benutzen Sie Flip-Flop-Bausteine aus der Bausteinbibliothek. Experimentieren Sie auch mit
taktpegelgesteuterten Flip-Flops.
Der TTL-Baustein 7474 ist ein taktflankengesteuertes D-Flip-Flop mit Preset und Clear:
Preset Clear
¦
¦
+----------------+
D ----¦
+---- Q
¦
¦
C ----¦>
+---- ¬Q
+----------------+
Die Wirkung der Eingänge Preset und Clear:
Preset ¦ Clear ¦ Wirkung
-------+-------+-------------------------0
¦
1
¦ Q=1
1
¦
0
¦ Q=0
0
¦
0
¦ instabil
1
¦
1
¦ normale Funktion des D-FF
8 Assembler-Programmierung
Neben den bereits bekannten (Pseudo-)Assembler-Befehlen stehen noch die folgenden Einadreß-Befehle zur Verfügung: JUMPLESS und SUB. Ihre Wirkung:
JUMPLESS a: Falls AC<0 setze PC:= a
SUB a: AC:= AC-(a)
9
//(a) bezeichnet den Inhalt der
//Speicherzelle mit der Adresse a
Aufgabe: Schreiben Sie ein (Pseudo-)Assembler-Programm, das den Divisionsrest bestimmt,
wenn man die größere der beiden Zahlen x und y durch die kleinere dividiert. Gleichheit ist
zulässig und soll sinngemäß behandelt werden.
Ausdrücke
9 Syntaxbäume
Aufgabe: Zeichnen Sie die Syntaxbäume der folgenden Kurzformausdrücke:
(A=A¬B)≤A+B
(A+B)(A≤C)≤(B+C)
(A=B)(C=¬D)
A=(B=(C=¬(B=C)))
(AB+AC+BC)(A≤¬B)(B≤¬C)(C≤A)
10 Logische Spielräume
Machen Sie sich mit dem Programm LogScope vertraut.
Aufgabe: Ermitteln Sie die Erfüllungsmengen der Ausdrücke
(A=A¬B)≤A+B
(A+B)(A≤C)≤(B+C)
(A=B)(C=¬D)
A=(B=(C=¬(B=C)))
(AB+AC+BC)(A≤¬B)(B≤¬C)(C≤A)
zunächst "von Hand" und überprüfen Sie das Ergebnis schließlich mit dem Program LogScope.
11 Logikrätsel
Das erste und das dritte der folgenden Logik-Puzzles sind der Sammlung von Smullyan entnommen; das zweite habe ich für meinen Probevortrag an der FH Fulda im Jahre 1982 entwickelt;
das vierte ist aus dem ZEITmagazin. Lösen Sie die Aufgaben nach folgendem Schema:
1. Codierung: Stellen Sie die elemtaren Aussagen zusammen und führen Sie für jede elementare Aussagen eine Variable ein.
2. Aufstellung der Prämissen: Bilden Sie für die im Rätsel vorkommenden Teilaussagen wahre
(!) Kurzformausdrücke.
3. Konjunktion der Prämissen: Die Konjunktion der Prämissen ist eine Darstellung des Sachverhalts in Form eines Ausdrucks, der wahr sein muß.
4. Bestimmung des logischen Spielraums: Die Erfüllungsmenge enthält alle möglichen Situationen, die mit den Aussagen verträglich sind.
Alternativ zum vierten Schritt kann man auch den folgenden Schritt durchführen:
5. Äquivalenztransformation: Führen Sie schrittweise den Ausdruck in eine DNF über und
minimieren Sie diese. Das Ergebnis läßt sich dann meist sofort ablesen.
10
Lösen Sie die Aufgaben sowohl durch Bestimmung des logischen Spielraums als auch durch
Äquivalenztransformationen. Überprüfen Sie Ihre Ergebnisse mit den Programmen LogScope
und LogTrans.
Aufgabe 1: Die Insel der Lügner. Auf dieser Insel leben zwei seltsame Typen von Bewohnern:
die einen sagen am Tag die Wahrheit und lügen nachts, die anderen lügen tagsüber und sagen in
der Nacht die Wahrheit. Ein Gast trifft die Inselbewohner Bob und Sam. Bob erklärt: "Mindestens einer von uns lügt nachts". Sam ergänzt: "Bob lügt am Tag". Ist es Tag oder Nacht? Zu
welcher Gruppe gehört Bob, zu welcher Sam?
Aufgabe 2: Die Insel mit einem unzuverlässigen Lügner. Auf dieser Insel sagen fast alle stets
die Wahrheit. Nur einer von ihnen lügt manchmal. Drei Inselbewohner, Albert, Bertram und
Conrad, treffen sich. Albert sagt: "Bertram lügt manchmal." Bertram sagt: "Conrad lügt manchmal" und Conrad sagt "Albert lügt nie." Wer lügt?
Anmerkung: Dieses Rätsel hat einen praktischen Hintergrund: Man stelle sich Computer anstelle der Personen vor. Diese Computer A, B und C seien zu einem Netz zusammengeschaltet, so
daß Computer A den Computer B, B den Computer C und C den Computer A überwachen kann.
Die Computer bilden also eine Art "Diagnosering". Die Rätselaufgabe entspricht offensichtlich
der Aufgabe, aufgrund eines bestimmten Diagnoseergebnisses einen fehlerhaften Computer zu
lokalisieren. Die Theorie der Diagnostizierbarkeit liefert Antworten auf solche Fragen. Sie ist
die Basis der softwareimplementierten Fehlertoleranz von Computersystemen.
Aufgabe 3: Die Insel der Fragensteller. Auf dieser leben Bewohner, deren Fragen man nur mit
Ja oder Nein beantworten kann. Es ist noch ärger: Es gibt zwei Gruppen von Bewohnern. Die
Fragen der einen Gruppe, nennen wir sie "Ja-Typen", sind korrekt mit ja zu beantworten und die
Fragen der "Nein-Typen" mit nein. Alice, Betty und Cynthia sind Bewohner dieser Insel. Alice
fragt Betty: "Gehörst du zu der Kategorie von Leuten, die Cynthia fragen können, ob sie dem
Typ angehört, der dich fragen kann, ob ihr zwei verschiedenen Typen zuzurechnen seid?" Aus
dieser Frage läßt sich zumindest für eine der Damen der Typ erschließen. Welche ist es und zu
welchem Typ gehört sie?
Aufgabe 4: Soeben hat der Postbote ein Paket gebracht. Absender ist ein "Kampfbund zur Ausrottung der Dummheit". Ich habe ausgepackt und darin einen Kasten gefunden, auf dem diese
Nachricht klebt:
"Mit dem Öffnen des Paktes haben Sie eine Zeitbombe aktiviert. Sie explodiert in zwanzig Minuten, es sei denn, Sie bringen die vier an dem Kasten befindlichen, numerierten Schalter in die
richtigen Stellungen (nach oben beziehungsweise nach unten). Dies sollte Ihnen gelingen, wenn
Sie diese Warnung beachten: Bei jeder der folgenden Schalterstellungen wird es knallen:
a) alle Schalter oben;
b) 2 und 4 in der gleichen Stellung und 1 unten;
c) 4 oben, 1 und 3 unten;
d) 1 und 3 in der gleichen Stellung und 4 unten;
e) 1 oben, 2 und 4 unten
f) 3 unten und falls 1 unten, dann auch 4 unten;
g) 3 oben, 1 unten und falls 2 oben, dann 4 unten."
Gottlob fand ich die einzig richtige Schalterstellungen rechtzeitig. Welche?
11
Teil II
Einfache Datentypen und While-Programme
12 Einfache C-Programme
Einige der folgenden Aufgaben gehen von vorgegebenen Programmtexten aus. In diesen Fällen
machen Sie vor dem Programmlauf eine Prognose des zu erwartenden Ergebnisses (schriftlich!). Prüfen Sie Abweichungen zwischen Prognose und tatsächlichem Ergebnis ganz genau.
Aufgabe 1 (am Computer): Führen Sie folgende Aktionen auf der DOS-Ebene durch. Machen
Sie einen eigenen Ordner (Verzeichnis) für die Programmierstudie Ein-Aus auf (siehe Skriptum zur Lehrveranstaltung). Schreiben Sie das Beispielprogramm mit dem Texteditor und speichern Sie die Datei unter dem Namen Ein-Aus.C in diesem Verzeichnis ab. Übesetzen Sie das
Programm durch Compileraufruf für das Programm: bcc32 Ein-Aus.C. Sehen Sie im Dateiordner (Verzeichnis) nach, welche Datei jetzt neu entstanden ist (Ein-Aus.exe). Starten Sie
dieses Programm durch den Aufruf Ein-Aus. Führen Sie die folgenden Änderungen im Beispielprogramm durch, übersetzen und starten Sie das Programm nach jeder der Änderungen;
beobachten Sie, was passiert.
1. Kommentieren Sie die Leseanweisung aus, also: Ersetzen Sie scanf("%d", &inch);
durch /*scanf("%d", &inch);*/. Dadurch wird der Text für das aktuelle Programm wirkungslos, bleibt ihnen aber zur späteren Reaktivierung erhalten,.
2. Streichen Sie die Inatialisierung der Variablen inch, also ersetzen Sie int inch = 0;
durch int inch;
3. Ersetzen Sie die automatische Variable inch durch eine statische Variable gleichen Namens. Tun Sie das auf zwei verschiedene Weisen. Lassen Sie nach wie vor die Initialisierung weg. (Gehen Sie auf Entdeckungsreise durch das Skriptum zur Lehrveranstaltung oder
sehen Sie im Buch von Kernighan und Ritchie nach.)
4. Machen Sie die Änderungen rückgängig.
5. Ändern Sie die Formatierung der Zahlenausgabe. Lassen Sie jedesmal das Programm auch
mit negativen Eingabewerten für inch laufen.
Aufgabe 2: Zeichnen Sie den Syntaxbaum des ersten Ausdrucks und machen Sie sich - durch
Skizze des Syntaxbaums - die Bedeutung zweiten Ausdrucks klar.
1) *--j=0
2) fabs(x)<fabs(y)? fabs(y)*sqrt(1+(x/y)*(x/y)): x==0? 0:
fabs(x)*sqrt(1+(y/x)*(y/x));
Aufgabe 3: Schreiben Sie ein Programm, das die Größen der fundamentalen Typen und der Zeigertypen ausgibt. Verwenden Sie dazu den Operator sizeof.
Aufgabe 4: Schreiben Sie ein Programm shift, das (0000100000100000)2 und die daraus
durch Verschiebung um eine, vier bzw. fünf Stelle nach links entstehende Dualzahl als Dezimalzahlen ausgibt. Es sind nur Ein- und Ausgabeanweisungen zulässig. Da die Rechnerein- und ausgabe keine Dualzahlen kennt, müssen Sie die Zahlen für die Ein-/Ausgabe "von Hand" wandeln.
Aufgabe 5: Zeigen Sie mit einem kleinen Program, dass Dereferenzierungs- und Adressoperator
invers zueinander sind.
12
Aufgabe 6: Probieren Sie Programme der Lektion "3.2 Lexikalische Elemente und einfache Datentypen" mit dem Computer aus. Explorieren Sie die Programmiersprache C und den
Compiler, indem Sie die Programme variieren.
13 Algorithmen: Umcodierung zwischen Zahlensystemen u. a.
Aufgabe 1: Schreiben Sie ein Programm, das die nichtnegative Zahl z und die natürliche Zahl b
einliest und die Darstellung von z im Stellenwertsystem zur Basis b ausgibt. Die zu verwendenden Ziffern in aufsteigender Folge sind 0, 1, 2, ..., 9, A, B, C, ... Die Ziffern des gebräuchlichen
Stellenwertsystems zur Basis 16 gehen also von 0 bis F.
Aufgabe 2: Die Programmsequenzen
p = a, q = b;
while (*p != 0) {*q = *p; p = p+1; q = q+1;}
*q = 0;
und
p = a, q = b;
while (*q++ = *p++);
sind funktionsgleich hinsichtlich der Variablen a und b. Aber was ist mit den Zeigern p und q?
Beantworten Sie diese Frage und Begründen Sie Ihre Antwort.
Aufgabe 2: Schreiben Sie ein Programm, das sämtliche Zeichen der Codetabelle zusammen mit
ihrer Ordnungsnummer ausgibt. Deklarieren Sie die Laufvariable als char. Hinweis: Es ist etwas knifflig. Aber mit einer Do-While-Schleife geht es.
Aufgabe 3 (freigestellt): Ergänzen Sie das Programm shift so, dass die Bitfolge als String
eingegeben werden kann und die Wandlung in eine Dezimalzahl durch das Programm selbst
durchgeführt wird. Die Anzahl der Schiebepositionen sei variabel. Sie wird als ganze Zahl
eingegeben. Ist sie positiv, wird nach links, ist sie negativ, wird nach rechts geschoben.
14 Invariante: Polynomauswertung
Aufgabe 1: Schreiben Sie ein Programm, das für ein vorgebbares Polynom eine Wertetabelle
ausgibt. Eingabe: Grad und Koeffizienten des Polynoms, Unter- und Obergrenze des Definitionsbereichs, Schrittweite (Abstand der Werte der unabhängigen Variablen). Verwenden Sie
den Algorithmus aus Lektion 3.5.
Aufgabe 2: Führen Sie den in der Übung der Lektion 3.5 geforderten Beweis durch. Das geschieht in drei Schritten:
1. Nachweis (Beweis), daß die Initialisierung die Invariante wahr macht
2. Nachweis (Beweis), daß die Schleifenanweisung die Invariante erhält
3. Nachweis (Beweis), daß die negierte Schleifenbedingung zusammen mit der Invarianten das
Resultat impliziert
Die Invariante des Algorithmus:
r = Σ 0≤i≤n-j cj+ixi = cj + cj+1x1 + cj+2x2 + ... + cn-1xn-j-1 + cnxn-j
Tip: Nehmen Sie ein einfaches allgemein geschriebenes Polynom, z. B. c0 + c1 x + c2 x2 + c3 x3,
und gehen Sie dafür den Algorithmus Schritt für Schritt durch. Machen Sie sich so die Bedeutung der Invarianten klar. Finden Sie heraus, wie das hier angewandte Verfahren in der Mathematik genannt wird.
13
15 Betrag komplexer Zahlen
Aufgabe 1: Schreiben Sie ein Programm, das die Zahlen x und y einliest. Diese Zahlen werden
als Real- bzw. Imaginärteil der komplexen Zahl z = x + jy interpretiert. Das Programm soll den
Betrag dieser Zahl ausgeben.
Aufgabe 2: Beurteilen Sie Ihr Programm unter dem Aspekt der Bereichsüberschreitung. Was
läßt sich verbessern? Überarbeiten Sie das Programm gegebenenfalls. Nutzen Sie die Formel
x 2 + y 2 = | x | 1+ ( y / x) 2 , falls |x|>|y|, und entsprechende Formeln für die anderen Fälle.
16 Fixpunkt- und Nullstellenberechnung
Aufgabe 1: Schreiben Sie ein Programm zur Berechnung derjenigen Nullstelle der Funktion f(x)
= x-(1-x)4, die im Intervall [0, 1] liegt. Benutzen Sie den Zwischenwertsatz der Analysis. Geben Sie einen möglichst genauen Näherungswert für die Nullstelle aus. Hinweis: Prüfen Sie die
Voraussetzung des Zwischenwertsatzes (Invariante). Halbieren Sie nun das Intervall und wählen Sie dasjenige aus, das die Invariante erfüllt. Wiederholen Sie diesen Schritt so lange, bis
das Intervall klein genug ist. Achten Sie bei der Festlegung einer Schranke für die Kleinheit
darauf, dass der Näherungswert für die Nullstelle einen möglichst kleinen relativen Fehler hat.
Hinweis: Sei f eine beliebige stetige Funktion. Vorgegeben seien die Werte a und b und es gelte
f(a) ≤ 0 < f(b). Der Zwischenwertsatz der Analysis besagt, daß unter dieser Voraussetzung die
Funktion f im Intervall [a, b) eine Nullstelle hat. Machen Sie sukzessive das Intervall [a, b)
immer kleiner unter Beibehaltung der Voraussetzungen des Zwischenwertsatzes (Invariante).
Halbieren Sie zu diesem Zweck das Intervall und wählen Sie das Teilintervall, für das die Invariante gilt.
Aufgabe 2 (freigestellt): Gegeben sei die Funktion g
g(x) = cos(x)/x - sin(x)/x2 + 2/π - (2/π)2
Weisen Sie nach, daß diese Funktion im Intervall [0, π/2] eine Nullstelle besitzt und ermitteln
Sie einen möglichst genauen Näherungswert dafür.
Die Aufgabe 2 fällt im Rahmen einer allgemeineren Aufgabenstellung an: Gesucht ist die
gleichmäßige Approximation einer Geraden an die Funktion sin(x)/x im Intervall [0, π/2]. Gesucht ist also ein Polynom a0 + a1x, so daß der maximale Absolutwert der Differenz f(x) =
sin(x)/x - (a0 + a1 x) minimal wird. Nach dem Tschebyscheffschen Satz (Alternantensatz) gibt
es dann eine Zahl δ, so daß f(0) = δ, f(x) = -δ für ein x mit 0 < x < π/2 und f'(x) = 0 und f(π/2) =
δ. Die Funktion g aus Aufgabe 3 ist genau die Funktion f', und |δ| ist die maximale Abweichung.
Zusatzaufgabe: Ermitteln Sie die Koeffizienten a0 und a1 und geben Sie in einem Programm
die Wertetabellen für sin(x) und a0x + a1x2 aus. Offensichtlich ist das Polynom zweiten Grades
(Parabel) für 0≤x≤π/2 eine recht gute Näherung für den Sinus. Der Fehler ist begrenzt durch δx,
wobei δ < 5%.
17 Elementare Sortierverfahren
Aufgabe: Schreiben Sie Programm, das einen Textstring einliest und diesen dann sortiert wieder ausgibt. Auf die Eingabe "8. November 1994" hin soll der Bildschirm beispielsweise folgendes Ergebnis zeigen
Eingabe: 8. November 1994
14
Ausgabe:
.14899Nbeemorv
Datentypen und Funktionen
18 Scheinwiderstand eines Serienschwingkreises
Aufgabe 1: Gegeben sei ein Serienschwingkreis mit dem Widerstand R = 10 Ω, der Induktivität
L = 1 mH und der Kapazität C = 100 nF. Schreiben Sie ein Programm, das den Betrag des Widerstands in Abhängigkeit von der Frequenz f ermittelt. Speichern Sie das Ergebnis in eine
Textdatei und stellen Sie es mit einem Tabellenkalkulationsprogramm graphisch dar.
Hinweis: Um eine geeignete Festlegung des darzustellenden Frequenzbereichs und der Schrittweite treffen zu können, ist vorab die Resonanzfrequenz des Schwingkreises zu ermitteln.
Aufgabe 2: Führen Sie den Datentyp complex ein und schreiben Sie die Funktionen entsprechend um. Definieren Sie die Betragsfunktions float betrag(complex z).
Aufgabe 3: Lagern Sie den Datentyp complex und die Funktion betrag aus dem Hauptprogramm
aus und definieren Sie ein Modul Complex.h + Complex.c dafür. Gestalten Sie das Hauptprogramm entsprechend um, so dass es dieses Modul benutzt und funktionsgleich zum ursprünglichen Programm ist.
19 Statistik über wundersame Zahlen
Aufgabe 1: Eine Zahl nennen wir wundersam, wenn sich bei folgender Rechnung schließlich
eine Eins ergibt (Hofstadter, 1988, S. 430): Wenn die Zahl ungerade ist, verdreifachen wir sie
und addieren eins. Wenn sie gerade ist, halbieren wir sie. Wir wiederholen den Prozess, solange sich Zahlen ungleich eins ergeben. Schreiben Sie ein While-Programm, das nach Eingabe
einer ganzen Zahl ermittelt, ob es sich um eine wundersame Zahl handelt und das alle Zwischenergebnisse ausgibt. Was passiert, wenn eine Zahl nicht wundersam ist?
Aufgabe 2: Für sämtliche Zahlen von 1 bis 50 000 soll die Anzahl der Berechnungsschritte, die
bei der Bestimmung der Wundersamkeit (Aufgabe 2.6.1) anfallen, in einem Histogramm ausgegeben werden. Es ist also ein Feld h, das als float h[max] deklariert ist, anzulegen, dessen
Komponenten h[i] schließlich die Häufigkeiten enthalten, mit denen die Berechnungslängen i
auftreten. Dieses Histogramm ist mit einem Tabellenkalkulationsprogramm grafisch darzustellen.
Aufgabe 3 (freigestellt): Schreiben Funktionen zum Sichern und Lesen von Textdateien mit angefügter Checksum1. Die Lesefunktion soll eine Überprüfung der Checksum durchführen und
das Ergebnis mitteilen.
20 Lineare Liste
Aufgabe 1: Schreiben Sie ein C-Programm CompList.C, das einen Datentyp complex für komplexe Zahlen mit den Feldern x und y enthält, die miteinander zu einer linearen Liste verknüpft
werden können. Die Deklaration von complex sieht so aus:
struct complex {float x, y; struct complex *next;};
1
Es handelt sich um ein einfaches Verfahren zur Fehlererkennung. Die Checksum ist die numerische Summe
über die Ordinalzahlen aller Zeichen der Datei.
15
Schreiben Sie eine Funktion betrag, die als Eingabeparameter eine komplexe Zahl entgegennimmt und als Ergebniswert den Betrag liefert. Schreiben Sie ein Hauptprogramm, das folgendes leistet: Es nimmt von der Tastatur eine Folge komplexer Zahlen entgegen. Vor jeder Eingabe steht eine Abfrage, ob mit der Eingabe fortgefahren werden soll. Die Punktfolge ist in einer
linearen Liste abzulegen. Nach Beendigung der Eingabe soll die Folge der Punkte zusammen
mit ihren Beträgen auf dem Bildschirm erscheinen. Das folgende Hauptprogramm ist also um
geeignete Funktionen zu ergänzen:
main() {
/*Initialisierung und Titel*/
struct complex *p=0, *h;
unsigned char c='j';
printf("Demo: Lineare Liste komplexer Zahlen");
/*Eingabe*/
while(c=='j'){
h=in(p); p=h;
printf("? Weiter mit \"j\": ");
scanf("%1s", &c);
}
printf("c= %c", c);
/*Verarbeitung: entfällt*/
/*Ausgabe*/
printf("Ausgabe\n");
h=p;
while(h){out(h); h=h->next;}
return 0;
}
Der Funktionsaufruf in(p) soll folgendes leisten: Es wird ein neues Objekt vom Typ complex
erzeugt, die x- und die y-Komponente der Zahl werden abgefragt und sind vom Anwender einzugeben. Außerdem wird dieses Objekt mit dem Objekt p verkettet, so dass next auf p zeigt.
Der Rückgabewert der Funktion ist ein Zeiger auf das neu erzeugt Objekt. Die Funktion out hat
nur zur Aufgabe, eine komplexe Zahl zusammen mit ihrem Betrag auf den Bildschirm zu bringen.
Aufgabe 2: Das obige main-Programm ist etwas "geschwätzig", feiner gesagt: weitschweifig.
Für die beabsichtigte Funktion ist die Variable h überflüssig. Streichen Sie h und führen Sie die
sich daraus ergebenden Änderungen durch. Was ist zu tun, wenn Sie die lineare Liste vor Verlassen des Programms aus dem Heap entfernen (löschen) wollen?
Aufgabe 3 (freigestellt): Ergänzen Sie das Modul Complex.h + Complex.c um eine Funktion
sort für das topologische Sortieren2. Zu diesem Zweck ist für die Elemente eine partielle Ordnung3 mittels des Kriteriums less (für <) definiert. Es soll less(a, b) genau dann ungleich null
sein, wenn a südwestlich von b liegt, also genau dann, wenn a.x<b.x und a.y<b.y gilt. (Zeigen
2
Topologisch sortiert ist eine Folge von Elementen, zwischen denen eine partielle Ordnung < besteht, genau
dann, wenn aus a<b folgt, dass in der Folge a vor b steht.
3
Partiell heißt eine Ordnung dann, wenn zwischen je zwei Elementen a und b nicht notwendigerweise a<b, b<a
oder a=b besteht. Das heißt: Es kann voneinander verschiedene Elemente geben, die nicht in der Ordnungsbeziehung zueinander stehen. Wenn die Ordnungsbeziehung besteht, dann gelten jedenfalls die Gesetze der Transitivität (wenn a<b und b<c, dann a<c) und Asymmetrie (wenn a<b, dann nicht b<a). Siehe dazu auch Wirth, N.:
Algorithmen und Datenstrukturen. Teubner, Stuttgart 1975
16
Sie, dass dadurch tatsächlich eine partielle Ordnung definiert wird.) Die Funktion less wird in
der Header-Datei deklariert
extern int less(struct complex*, struct complex*);
aber dem Anwender des Moduls zur letzendlichen Definition überlassen. Schreiben Sie ein
Anwendermodul, mit dem Sie diese Funktion testen können. Das Programm soll eine Folge von
komplexen Zahlen entgegennehmen und dann topologisch sortiert wieder ausgeben.
Hinweis: Die Funktion für das Sortieren könnte beispielsweise so aussehen:
struct complex* sort(struct complex* p){
if(p){
struct complex *q=p->next; p->next=0;
while(q){
struct complex *h=q; q=q->next;
if (less(h, p)) {h->next=p; p=h;} else {
struct complex *cur=p;
while (cur->next&&!less(h, cur->next)) cur=cur->next;
h->next=cur->next;
cur->next=h;
}/*EndIf*/
}/*EndWhile*/
}else /*NULL*/;
return p;
}
Aufgabe 4 (freigestellt): Schreiben Sie ein Programm zur Verwaltung einer Telefondatei. Funktionen: Einfügen neuer Einträge. Suchen, Anzeigen und Entfernen von Einträgen. Hinweis: Wählen Sie den Listenkopf vom ListenTyp. Auf diese Weise kann man sich ein paar Fallunterscheidungen sparen. Die Variable Liste zeigt auf den Anfang einer linearen Liste, deren Elemente
reelle Zahlen beinhalten. Die Liste sei zu Beginn leer (Liste = NIL).
Aufgabe 4.1: Definieren Sie die Datentypen und die Variablen ihres Programms. Schreiben Sie
den Block der Funktion mit Kopf "void Einfuegen(x: float)". Diese Funktion soll ein
neues Element mit dem Feld x an den Anfang der Liste einfügen.
Aufgabe 4.2: Schreiben Sie den Block zur Funktion Loeschen(). Diese Prozedur soll das letzte
Element der linearen Liste löschen.
Aufgabe 4.3: Schreiben Sie die Funktion Anzeigen(). Diese Prozedur soll alle reelle Zahlen
der Liste auf dem Bildschirm fortlaufend auflisten.
Aufgabe 4.4: Schreiben Sie das Hauptprogramm, das die Liste initialisiert (leere Liste) und
danach über folgendes Menü die weitere Bearbeitung der Liste steuert:
<E>infügen <L>öschen <A>nzeigen <Q>uitt
Mit dem Befehl Quitt wird das Programm verlassen.
21 Satzzerlegung
Aufgabe 1: Ein Baum sei durch folgende Syntax definiert:
Baum = Blatt | "(" Baum {Baum} ")"
Blatt = A | B | C | ... | X | Y | Z
Stellen Sie fest, bei welchen der folgenden die Textzeilen es sich um die Beschreibung von
Bäumen handelt. Markieren Sie diese und zeichnen Sie die Syntaxbäume dazu.
((A(BC))((DE)F))
A(B(CD))
17
(A(B()))
(A(B(CD(EF)G)))
(A(B(C(D(E(FG))))))
Aufgabe 2: Schreiben Sie ein C-Programm, das einen Textstring einliest und feststellt, ob es
sich um einen Baum gemäß Aufgabe 1 handelt.
Studie: Shannon-Codierung
Der Shannon-Code für gedächtnislose Quellen (Grams, T.: Codierungsverfahren. BI-Hochschultaschenbuch Band 625, Mannheim 1986) besitzt die Eigenschaft H ≤ m < 1+H. In Worten:
Die mittlere Codewortlänge ist nach unten durch die Entropie begrenzt, und sie übersteigt die
Entropie um weniger als eins. Auch die Codierungen nach Fano und die nach Huffman liefern
Codes mit dieser Eigenschaft. Aber für die Shannon-Codes ist sie besonders leicht nachzuweisen.
Aufgabe: Es ist ein Programm zu entwickeln, das eine Zeichenstatitistik von der Tastatur entgegennimmt und das die Codetabelle des Shannon-Codes liefert.
Konstruktionsvorschrift: Die ursprünglichen Zeichen des Codes seien nach fallenden Wahrscheinlichkeiten geordnet: p1 ≥ p2 ≥ p3 ≥ ... ≥ pn. Mit Pk bezeichnen wir die akkumulierten
Wahrscheinlichkeiten bis zum Zeichen k-1: P0=0, Pk+1 = Pk + pk .
Das Codezeichen des k-ten ursprünglichen Zeichens erhält man folgendermaßen: Sei m die
kleinste Zahl, für die 1 ≤ pk ⋅2m gilt. Ferner sei Z = b1/21 + b2/22 + ... + bm/2m die Dualzahlentwicklung der Zahl Pk bis zur Stelle m nach dem Dezimalpunkt. Dann ist das Codezeichen des kten ursprünglichen Zeichens gleich b1b2 ... bm.
Programmierung:
1. Festlegung der Datenstruktur: Tabelle mit Spalten für Zeichen, Wahrscheinlichkeiten und
akkumulierte Wahrscheinlichkeiten.
2. Funktion für das Sortieren der Tabelle nach fallenden Wahrscheinlichkeiten
3. Funktion für die Ausgabe der Codezeichen
4. Hauptprogramm
- Initialisierung der Tabelle. Überschrift.
- Eingabe der Zeichen und deren Wahrscheinlichkeiten
- Verarbeitung: Akkumulation
- Ausgabe der Codetabelle
Fachhochschule Fulda, Fachbereich Elektrotechnik
Freitag, 28. Februar 2003
Testate zum Praktikum Einführung in die Informatik (ET)
Die Testate können in der Klausur des und - gegebenenfalls - in der Wiederholungsklausur im darauffolgenden
Wintersemester angerechnet werden. (Maßgebend ist das Datum auf dieser Seite rechts oben.)
Name: ________________________
Matrikel-Nummer:________________
Thema
Punkte
1 EBNF und einfache Betriebssystembefehle
2 Der MS-DOS-Editor
3 Computerarithmethik. Tabellenkalkulation mit Excel
1
4
5
6
7
1
Einführung in SPICE: Logiksimulation
Simulation eines Schaltnetzes: Addierer
Simulation eines Schaltwerkes: Speicher
Synthese eines Automaten: Gray-Code-Zähler
8 Assembler-Programmierung
1
9 Syntaxbäume
1
10 Logische Spielräume
1
11 Logikrätsel
2
12 Einfache C-Programme
1
13 Umcodierung zwischen Zahlensystemen
1
14 Invariante: Polynomauswertung
1
15 Betrag komplexer Zahlen
1
16 Fixpunkt- und Nullstellenberechnung
17 Elementare Sortierverfahren
1
18 Scheinwiderstand eines Serienschwingkreises
1
19 Statistik über wundersame Zahlen
20 Lineare Liste
21 Satzzerlegung
2
Testat
KLAUSURTEXTE UND MUSTERLÖSUNGEN
19
Anhang: Aus den Klausuren
Kopf des Aufgabenblattes einer Klausur
FH Fulda, FB Elektrotechnik
Klausur: Einführung in die Informatik
08.07.2002 , 800 Uhr
Name:
Matrikelnummer:
Zugelassene Hilfsmittel: alle schriftlichen Unterlagen
Bearbeitungsdauer: 90 Minuten; maximal erreichbare Punktzahl: 90
Schreiben Sie auf alle Blätter die Blattnummer und Ihren Namen
Bitte legen Sie Ihren Personalausweis und Ihre Testate bereit
Einsichtstermin: Sprechstunde in der 2. LVA-Woche des folgenden Semesters.
Klausuraufgaben mit Musterlösung
Aufgabe 1 (10 P): Geben Sie den logischen Spielraum (die Erfüllungsmenge) des Kurzformausddrucks A=A+B an.
Musterlösung: Die Wertetabelle
A
B
A+B
A=A+B
0
0
0
1
0
1
1
0
1
0
1
1
1
1
1
1
liefert die Erfüllungsmenge {(A, B)| A=A+B} = {(0, 0), (1, 0), (1, 1)}.
Aufgabe 2 (15): Der König stellt den Gefangenen auf die Probe: In jedem der beiden Räume,
deren Türschilder unten zu sehen sind, befindet sich entweder eine Dame oder ein Tiger. Der
König, der ja immer die Wahrheit sagt, meint noch: „Die Schilder sind entweder beide falsch
oder beide richtig“. Welche Tür sollte der Gefangene öffnen? Begründen Sie die Antwort formal: Codierung der elementaren Aussagen, Aufstellung und Konjunktion der Prämissen, Äquivalenztransformation in eine minimierte disjunktive Normalform, Interpretation des Ergebnisses.
I
Zumindest in einem
der Räume
ist eine Dame
II
Im anderen Raum befindet
sich ein Tiger
Musterlösung: A steht für „In Raum I befindet sich eine Dame“ und B für „In Raum II befindet
sich eine Dame“. ¬A bedeutet demnach, dass in Raum I ein Tiger ist. Die Aussage des Königs
führt zur Prämisse A+B= ¬A. Daraus folgt (A+B)¬A+¬A¬BA und schließlich das Ergebnis
¬AB; also: in Raum I ist ein Tiger und in Raum II eine Dame.
20
Aufgabe 3 (10 Punkte): Welche Tür sollte der Gefangene öffenen, wenn die Türschilder - bei
ansonsten unveränderter Aufgabenstellung - folgendermaßen aussehen?
I
II
Entweder ist ein Tiger
in diesem Raum oder
eine Dame im anderen
Im anderen Raum ist
eine Dame
Musterlösung: Hier lautet die Prämisse ¬A+B=A. Die Äquivalenztransformationen führen hier
über (¬A+B)A+A¬BA zum Resultat AB. In jedem der Räume befindet sich eine Dame.
Aufgabe 4 (15 Punkte): Das folgende Programmfragment soll auf der Variablen y den Fixpunkt der Funktion f bestimmen. Was ist falsch daran? Korrigieren Sie den Text.
y_old:= 1; y:= f(y_old);
WHILE y<>y_old DO BEGIN
y_old:= y; y:= f(y)
END;
Musterlösung: Die Abbruchbedingung ist falsch: Real-Zahlen dürfen hier - wegen des Rundungsfehlers - nicht auf (Un-)Gleichheit geprüft werden. Der Programmtext "y<>y_old" ist zu
ersetzen durch die Prüfung auf relative Genauigkeit: "abs(y-y_old)>Eps*abs(y_old)". Hierin ist
Eps als Konstante mit einem kleinen Wert, zB. "Eps=1E-10", definiert.
Aufgabe 5 (10 Punkte): Geben Sie die Erweiterte Backus-Naur-Form (EBNF) der Wagenaufstellung eines ICE an. Terminalsymbole seien: Triebkopf1, Triebkopf2, WagenErsterKlasse, WagenZweiterKlasse und Speisewagen. Die Anzahl der Wagen
erster und zweiter Klasse seien - abgesehen davon, dass es jeweils wenigstens einen Wagen
jeder Klasse gibt - beliebig. Startsymbol sei ICE.
Musterlösung: Eine Möglichkeit ist
ICE = Triebkopf1 ErsteKlasse Speisewagen ZweiteKlasse Triebkopf2
ErsteKlasse = WagenErsterKlasse { WagenErsterKlasse }
ZweiteKlasse = WagenZweiterKlasse { WagenZweiterKlasse }
Aufgabe 6 (30 Punkte): Wiedergegeben ist die rekursive Prozedur WriteCode aus dem
Programm Huffman.
void WriteCode(Node *x){
if(x->next!=NULL) {
WriteCode(x->next);
printf("%1d", x->sign);
}
}
/*rekursive Funktion*/
Schreiben Sie eine nichtrekursive Variante dieser Prozedur. Benutzen Sie zur Zwischenspeicherung der Zeichen ein Array.
Musterlösung: Die nichtrekursive Variante könnte beispielsweise so aussehen:
void WriteCode(Node *x) {
int i=0, c[100];
while (x->next!=NULL) {
c[i++]= x^.sign; x= x->next;
}
while (i>0) printf("%d", c[--i]));
}
21
Ausgewählte Klausuraufgaben
1. Aufgabe (20 P): Ein RS-Flip-Flop sei mit einem Vorschaltnetz gemäß folgendem Blockschaltbild und Funktionstabelle versehen:
J K Q ¦ S R
--------+-----0 0 0 ¦ 0 0
0 0 1 ¦ 0 0
0 1 0 ¦ 0 0
0 1 1 ¦ 0 1
1 0 0 ¦ 1 0
1 0 1 ¦ 0 0
1 1 0 ¦ 1 0
1 1 1 ¦ 0 1
+---------------------------+
¦ +--------+
+------+ ¦
+--¦
¦ S ¦
¦ ¦
J -----¦ Vor+-----¦ RS- +----- Q
¦ schalt-¦
¦ Flip-¦
K -----¦ netz
+-----¦ Flop +----- ¬Q
+--¦
¦ R ¦
¦ ¦
¦ +--------+
+------+ ¦
+---------------------------+
- Bilden Sie die Schaltfunktion des Vorschaltnetzes
- Zeichnen Sie das Schaltbild des Vorschaltnetzes
- Beschreiben Sie möglichst knapp die Funktion der Gesamtschaltung (ein sogenanntes JKFlip-Flop)
2. Aufgabe (20 Punkte): Auf der Insel der Ritter und Schurken behauptet ein Einwohner über
seinen Bruder, der ebenfalls auf der Insel lebt: "Wenn mein Bruder ein Ritter ist, dann bin ich
ein Schurke". Wer ist was?
- Codieren Sie die elementaren Aussagen
- Formulieren Sie die Prämisse
- Leiten Sie mittels Äquivalenztransformation die Antwort auf die Frage her
3. Aufgabe (15 Punkte): Schreiben Sie den Block der Funktionsdeklaration mit dem Kopf
FUNCTION Min(VAR a, b, c: INTEGER): INTEGER;
Ergebniswert soll das Minimum der Zahlen a, b und c sein.
4. Aufgabe (20 P): Folgende Syntaxdefinition ist gegeben:
Wald = Baum {Baum}
Baum = Blatt | "(" Wald ")"
Blatt = A | B | C | ... | X |
Y | Z
Zeichnen sie die Syntaxbäume und tragen Sie in die
nebenstehende Tabelle ein, ob es sich bei der jeweiligen Zeichenfolge um einen Wald, einen Baum, ein
Blatt oder nichts von alldem handelt. Mehrfachnennungen sind - falls zutreffend - einzutragen.
Zeichen- Wald
folge
()
A
ABCD
(AB(CD))
A(B(CD))
5. Aufgabe (15 Punkte): Folgende Prämissen mögen gelten
- Wenn es regnet, wird die Straße nass
- Wenn der Nachbar den Rasen sprengt, wird die Straße nass
- Wenn es regnet, findet das Fußballspiel nicht statt
- Die Straße ist nass
- Das Fußballspiel findet statt
Was schließen Sie daraus?
- Codieren Sie die elementaren Aussagen
Baum
Blatt
22
- Formulieren Sie die Prämissen
- Bilden Sie die Konjunktion der Prämissen
- Leiten Sie mittels Äquivalenztransformationen die Antwort auf die Frage her
6. Aufgabe (20 P): Albert und Bertram der folgenden Unteraufgaben sind Bewohner der Insel
mit einem unzuverlässigen Lügner. Zur Aufgabenlösung gehen Sie so vor: Codieren, Prämissen
aufstellen, konjugieren, äquivalent transformieren, DNF interpretieren, feststellen, wer manchmal lügt.
6.1 Albert behauptet: Bertram lügt nie. Bertram behauptet: Albert lügt nie. Was lässt sich daraus schließen?
6.2 Albert behauptet: Bertram lügt manchmal. Bertram behauptet: Albert lügt manchmal. Was
lässt sich daraus schließen?
6.3 Albert behauptet: Bertram lügt manchmal. Bertram behauptet: Albert lügt nie. Was lässt
sich daraus schließen?
6.4 Albert behauptet: "Bertram behauptet, ich würde manchmal lügen". Was lässt sich daraus
schließen?
7. Aufgabe (15 P): Beweisen Sie, dass die Anweisungsfolge
k:= 0;
i:= 1;
while k<n do begin
k:= k+1;
i:= i*j
end
auf der Variablen i den Wert jn abliefert, dass also schließlich i=j n gilt. (Zeigen Sie zunächst,
dass i=j k eine Schleifeninvariante ist und vervollständigen Sie dann den Beweis.)
8. Aufgabe (10 Punkte): Geben Sie den logischen Spielraum (die Erfüllungsmenge) des Kurzformausddrucks A=(A≤B) an. (Herleitung in nachvollziebaren Schritten oder mittels Tabelle!)
9. Aufgabe (15 P): Entwickeln Sie ein Schaltnetz mit drei Eingangsgrößen und einer Ausgangsgröße. Die erste Ausgangsgröße soll genau dann den Wert 1 annehmen, wenn eine oder zwei
Eingangsrößen gleich 1 sind.
• Stellen Sie die Wertetabelle auf.
• Geben Sie die Schaltfunktionen in möglichst einfacher Form an.
• Zeichnen Sie das Schaltnetz.
10. Aufgabe (15 P): Gegeben sei die folgende Grammatik in EBNF
aFolge = "a" aFolge | "a" bFolge
bFolge = "b" bFolge | "b" aFolge | "c"
Welche der folgenden Folgen sind aFolgen, welche bFolgen, welche weder das eine noch das
andere:
a)
b)
c)
d)
e)
aaaaac
abababac
c
bbcc
abbbac
Geben Sie die Schaltfunktion in möglichst einfacher Form an. Zeichnen Sie das Schaltnetz und
formulieren Sie einen Pascal-Text mit derselben Funktion.
23
11. Aufgabe (20 Punkte): Schreiben Sie ein C-Programm mit folgender Funktion: Das Programm nimmt eine Folge von reellen Zahlen von der Tastatur entgegen, solange der Anwender
eine entsprechende Anfrage mit der Eingabe "j " beantwortet. Sobald der Anwender die Anfrage abweichend beantwortet (beispielsweise mit "n") wird die Eingabe beendet und das Programm gibt den Mittelwert, den Maximalwert und den Minimalwert der eingegebenen Zahlenfolge aus. Deklarieren Sie nur die nötigsten Variablen.
12. Aufgabe (10 Punkte): Geben Sie den logischen Spielraum (die Erfüllungsmenge) des
Kurzformausdrucks ¬A=(A≤¬B) an. (Herleitung in nachvollziebaren Schritten oder mittels
Tabelle!)
13. Aufgabe (20 P): Gegeben sind ein paar Aussagen. Finden Sie heraus, ob ich die Verabredung einhalten kann.
1. Wenn der Bus zu spät kommt und mein Fahrrad nicht verfügbar ist, werde ich meine Verabredung verpassen.
2. Wenn mein Fahrrad kaputt ist oder wenn es gestohlen wurde, steht es nicht zur Vefügung.
3. Wenn mein Bruder gestern mit dem Fahrrad gefahren ist, dann ist es kaputt.
4. Mein Bruder ist mit meinem Fahrrad gefahren.
5. Ich sehe mein Fahrrad.
6. Der Bus ist noch nicht da. Er kommt sicherlich zu spät.
Gehen sie in folgenden Schritten vor: Codierung, Aufstellung der Prämissen in Kurzformdarstellung, Konjunktion der Prämissen, Transformation, Interpretation des Ergebnisses.
14. Aufgabe (20 P): Zeichnen Sie den komprimierten Syntaxbaum (Knoten für Variablen und
Verknüpfungen, keine Durchreichefunktionen) des folgenden Kurzformausdrucks:
(A+B)(A≤C) ≤B+C
Geben Sie die Postorder-Darstellung des Ausdrucks an.
15. Aufgabe (20 P): Stellen Sie die Zahl 2.7 im Dualsystem dar. Gesucht ist die Festpunktzahl
zur Basis 2 mit 3 Stellen hinter dem Dezimalpunkt.
16. Aufgabe (10 P): Was bedeutet "relative Genauigkeit" in der Gleitpunktrechnung. Wann und
warum drückt man Bedingungen mit Hilfe der relativen Genauigkeit aus?
17. Aufgabe (25 Punkte): Schreiben Sie ein C-Programm, das Ihnen das kleine Einmaleins in
Tabellenform ausgibt. Die linke obere Ecke soll so aussehen:
*|
1
2
3
------------------1|
1
2
3
2|
2
4
6
18. Aufgabe (10 Punkte): Geben Sie für den arithmetischen Ausdruck a*((b+c)-d) die Postorderdarstellung an. Die Operatoren werden als zweistellig vorausgesetzt, so dass die Knotengrade nicht mit angegeben werde müssen.
19. Aufgabe (15 P): Eine Nachrichtenquelle erzeugt die Zeichen a, b, c, d und e mit den Wahrscheinlichkeiten 60 %, 10 %, 10 % , 10 % und 10 %. Konstruieren Sie den Codierbaum eines
Huffman-Codes und geben Sie die Codierungsvorschrift in Tabellenform an.
20. Aufgabe (20 P): Beschreiben Sie, was das folgende C-Programm tut. Kommentieren Sie es
Zeile für Zeile und fassen Sie die Bedeutung (Semantik) des Programms in einem Satz zusammen. (Sie können das auf dem Aufgabenblatt tun.)
24
complex {float x, y; complex *next;};
void main(){
complex *p=0, *h;
unsigned char c='j';
printf("\nEingabe\n");
while (c=='j') {
h=(complex*)malloc(sizeof(complex));
printf("? x y= ");
scanf("%f %f", &h->x, &h->y);
h->next=p;
p=h;
printf("? Weiter: \"j\": ");
scanf("%1s", &c);
}
printf("\nAusgabe:");
printf("\n
x
y");
while(p){
printf("\n%5.1f
%5.1f", p->x, p->y);
p=p->next;
}
}
21. Aufgabe (25 Punkte): Schreiben Sie ein C-Programm, das als Eingabe zwei Gleitpunktzahlen a und b entgegennimmt und diese als Seitenlängen eines Rechtecks interpretiert. Ausgeben soll das Programm
1. Fläche,
2. Umfang und
3. die Länge der Diagonalen
des Rechtecks.
Das Programm muss vollständig sein, also auch die Include-Anweisungen umfassen. Achten Sie
auf gute Textgestaltung des Programms selbst und auf gute Gestaltung der Bildschirm-Ausgabe.
22. Aufgabe (25 Punkte): Welchen Wert ergibt das folgende Programmfragment für die Variable r? Verwenden Sie die Tabelle für die Variablen und geben Sie deren Werte vor Eintritt in
die Schleife (i ist da noch undefiniert) und nach jedem Schleifendurchlauf an.
#define n 3
unsigned t[n] = {1, 10, 100};
double p=2, q=1, r=0;
char d = 0, i, j=2;
for(i=1; i<=n; i++) r+=(d?1:i)*(q*=p)*t[(i+j)%n];
i
q
r
Nebenrechnungen
?
1
2
3
23. Aufgabe (25 Punkte): Stellen Sie die Funktion des folgenden C-Programmes fest. Was
passiert, wenn Sie für z die Zahl 15 und für b die Zahl 3 eingeben? Gehen Sie das Programm
25
Schritt für Schritt durch und notieren Sie die jeweiligen Werte der Variablen. Was erscheint
schließlich auf dem Bildschirm?
int z, b;
void F(int z) {
if (b<=z) F(z/b);
printf("%d", z%b);
}
main() {
printf("\n? z = "); scanf("%d", &z);
printf("? b = "); scanf("%d", &b);
printf("! ");
F(z);
}
Aufgaben der Klausur vom 08.07.02
Aufgabe 1 (15 Punkte): Zeichnen Sie das Schaltbild eines Schaltnetzes, das
genau dann am Ausgang eine 1 zeigt, wenn wenigstens zwei der drei Eingangsgrößen gleich 1 sind. Verwenden dürfen Sie nur die Grundgatter AND, OR und
NOT. Führen Sie die beiden Schritte Spezifizierung und Entwurf aus.
Aufgabe 2 (15 P): Eine Nachrichtenquelle erzeugt die Zeichen a, b, c, d, e und f. Alle haben
dieselbe Wahrscheinlichkeit. Konstruieren Sie den Codierbaum eines Huffman-Codes und geben Sie die Codierungsvorschrift in Tabellenform an.
Aufgabe 3 (15 P): Beschreiben Sie mittels EBNF den Aufbau (Grammatik, Syntax) eines einfachen arithmetischen Ausdrucks, in dem nur die vier Grundrechenarten vorkommen. Die
Grammatik soll zum Ausdruck bringen, dass „Punktrechnung vor Strichrechnung“ geht und sie
soll das Rechnen mit Klammern beinhalten. Als Terminalsymbole sind „V“ und „Z“ für Variablen und Zahlen zugelassen. Sie brauchen die Grammatik der Variablen und Zahlen also nicht
weiter auszuführen. Außerdem gibt es die Terminalsymbole „+“, „-“, „*“ und „/“ für Addition,
Subtraktion, Multiplikaton und Division.
Aufgabe 4 (15 Punkte): Auf der Insel mit einem unzuverlässigen Lügner äußert sich der Inselbewohner Albert über die Mitbewohner Bertram und Conrad: „Bertram lügt nie. Conrad
aber lügt manchmal". Und Conrad sagt über die beiden anderen, dass diese niemals lügen. Wer
lügt? Wer sagt stets die Wahrheit? Führen Sie folgende Schritte aus: Codierung der elementaren
Aussagen, Formulieren Sie die Prämissen, Konjunktion der Prämissen, Äquivalenztransformationen, Beantwortung der Fragen („Decodierung des formalen Ergebnisses“).
Erläutern Sie kurz, was Logikaufgaben in einer Lehrveranstaltung „Einführung in die Informatik“ zu suchen haben.
Aufgabe 5 (15 P): Schreiben Sie auf, was der Bildschirm zeigt, wenn das folgende Programm
gelaufen ist.
void main(){
printf("\n1.0/2==0: %d", 1.0/2==0);
printf("\n1.0/2==0.5: %d", 1.0/2==0.5);
printf("\n1/2==0: %d", 1/2==0);
printf("\n1/2==0.5: %d", 1/2==0.5);
}
Aufgabe 6 (15 Punkte): Schreiben Sie ein C-Programm, das einen String s entgegennimmt und
dann ausgibt, wie oft die Buchstabenkombination „ei“ in diesem String vorkommt.
26

Begleitmaterial zum PRAKTIKUM EINFÜHRUNG IN DIE INFORMATIK

Transcrição

Documentos relacionados

Urlaubsguru Praktikant (m/w)

Kreisverwaltung Eifelkreis Bitburg-Prüm

Kommandozeilenspicker, Linux Cheat Sheet

Bespielen von Datenträgern für MP3

9. BürgerEnergie-Treff 12. September 2013 Jena, Ricarda

Annette - Kolb

Verzeichnis Leistungen anderer Unternehmer

Lebenslauf Pascal Fischer

Angabe von Herrn Hermann Ölberg, h.oelberg@tsn

Aufgabe 2 - Verwendung von Zählern