Ergänzende Übungsaufgaben
Teil I (Programmierung)
 |
Aufgabe 1
|
 |
Lernen Sie die Java-Programmierumgebung kennen, indem Sie das Programm "
JavaSpass" aus Buch eingeben,
übersetzen und ausführen lassen.
|
|
Aufgabe 2
|
|
Geben Sie eine Definition des Begriffs "Algorithmus". Was sind die vier grundlegenden Eigenschaften?
|
|
Aufgabe 3
|
|
a)
Schreiben Sie einen Algorithmus
Max(a0,a1,....,an),
der den größten Wert der Zahlenmenge
{ a0,a1,....,an } findet.
b)
Schreiben Sie ein Java-Programm
ProgramMaxSuche analog
zum Programm
ProgrammMinSuche aus dem Buch. Verwenden Sie zum
Testen auch einmal eine andere Zahlenmenge.
|
|
Aufgabe 4
|
|
a)
Schreiben Sie einen Algorithmus
fuenfteilbar(a0,a1,....,an) in Pseudocode,
der "
true" zurückliefert, wenn die Zahlenmenge
{ a0,a1,....,an } eine Zahl enthält,
die durch 5 teilbar ist, und sonst "
false" zurückgibt. Die Teilbarkeit kann mit "modulo" getestet werden: a modulo b
liefert den Rest bei der ganzzahligen Teilung von a durch b.
b)
Schreiben Sie eine Java-Funktion
static boolean fuenfteilbar(int[] a), die dies leistet.
Java repräsentiert modulo durch %, d.h. a % b steht für a mod b.
c)
Schreiben Sie ein Testprogramm, dessen Hauptprogramm ein Array deklariert und initialisiert,
dann die Methode
fuenfteilbar aufruft und das Ergebnis des Aufrufs auf dem Bildschirm ausgibt.
|
|
Aufgabe 5
|
|
a)
Schreiben Sie einen Algorithmus
invers(int[ ] a) in Pseudocode, der die Reihenfolge der Werte im
Array a umdreht. Z.B. soll für den Fall, dass a[0]=4, a[1]=7 und a[2]=9 ist, a[0]=9, a[1]=7 und a[2]=4 herauskommen.
Der Algorithmus soll mit einer einzigen zusätzlich definierten ganzzahligen Variablen merker auskommen.
b)
Implementieren Sie den gefundenen Algorithmus als Java-Funktion
static void invers(int a).
Diese Funktion soll zunächst das Original-Array und dann das inverse Array auf dem Bildschirm
ausgeben (
System.out.println).
c)
Schreiben Sie ein Testprogramm, dessen Hauptprogramm ein Array deklariert und initialisiert
und dann die Methode
invers aufruft.
|
|
Aufgabe 6
|
|
a)
Schreiben Sie einen Algorithmus
mehrfach(a0,a1,....,an) in Pseudocode,
der in einer Menge
{ a0,a1,....,an } von n+1 Zahlen herausfindet, ob zwei
Zahlen den gleichen Wert haben. Der Algorithmus soll "
true" zurückgeben, wenn
dies der Fall ist, sonst "
false".
b)
Schreiben Sie eine Java-Funktion
static boolean mehrfach(int[ ] a), die dies leistet.
c)
Schreiben Sie ein Testprogramm, dessen Hauptprogramm ein Array deklariert und initialisiert,
dann die Methode
mehrfach aufruft und das Ergebnis des Aufrufs ausdruckt.
d)
Schätzen Sie den maximalen Zeitaufwand Ihres Algorithmus in Abhängigkeit von n ab.
|
|
Aufgabe 7
|
|
Die Primzahlen in einem Intervall I(n)={2, ..., n} ganzer Zahlen lassen sich dadurch berechnen,
dass zunächst alle Zahlen aus I(n) entfernt werden, die durch 2 teilbar sind und größer als 2 sind.
Aus der Menge der verbleibenden Zahlen werden dann alle diejenigen Zahlen entfernt, die durch 3
teilbar sind und größer als 3 sind, usw., bis n/2 erreicht ist.
a)
Schreiben Sie einen Algorithmus in Pseudocode, der dies leistet.
b)
Schätzen Sie den maximalen Zeitaufwand Ihres Algorithmus in Abhängigkeit von n ab.
|
|
Aufgabe 8
|
|
a)
Die Summe der ganzen Zahlen zwischen 1 und n soll berechnet werden. Schreiben Sie einen Algorithmus
summeBis(n) in Pseudocode, der dies leistet.
b)
Die Summe s
n der ganzen Zahlen zwischen 1 und n kann rekursiv wie folgt definiert werden:
s
1 :=1, s
n := s
n-1+n für n>1.
Schreiben Sie einen Algorithmus
rekSummmeBis(n) in Pseudocode, der die Berechnung auf diese Weise
ausführt.
c)
Schreiben Sie Java-Funktionen
static int summeBis(int n) und
static int rekSummeBis(int n), die diese
Algorithmen implementieren.
d)
Schreiben Sie ein Testprogramm, das beide Funktionen mit dem gleichen Wert aufruft und jeweils das Ergebnis
auf dem Bildschirm ausgibt.
|
|
Aufgabe 9
|
|
Der größte gemeinsame Teiler zweier positiver ganzer Zahlen a, b lässt sich mit folgendem rekursiv
definierten Verfahren berechnen:
ggt(a,1) =1,
ggt(1,b)=1,
ggt(a,a)=a,
ggt(a,b)= ggt(a-b,b) für a>b>1,
ggt(a,b)=ggg(a,b-a) für b>a>1.
Schreiben Sie eine Java-Funktion
static int ggt(int a, int b), die den größten gemeinsamen Teiler so
berechnet. Schreiben Sie ein Testprogramm, das diese Funktion mit aktuellen Parametern aufruft und die
Parameter sowie das Ergebnis auf dem Bildschirm ausgibt.
Teil II (Algorithmen Datenstrukturen)
|
|
Aufgabe 1
|
|
a)
Welche der folgenden Angaben ist richtig:
(1) 4n
2 +5n -1 = O(n2) (2) 4n
2 +5n -1 = O(n)
(3) 4n2 +5n -1 = O(n3)
b)
Geben Sie eine möglichst kleine Ordnung an, die das asymptotische Wachstum der folgenden
Funktionen beschreibt:
(1) f(n) = 5n+17 (2) g(n) = 3 + 5 n log n
(3) h(n) = 2 n
3-19n
2+17n-2
c)
Führen Sie das Verfahren der binären Suche für die Menge S={47, 21, 27, 6, 18, 28} und die
Suchwerte 27 und 17 durch. Geben Sie dabei die Intervalle an, die nacheinander durchlaufen werden.
|
|
Aufgabe 2
|
|
Gegeben sei der folgende binäre Suchbaum
a)
Ist der Baum ausgeglichen im Sinne der Definition des Buches?
b)
Geben Sie die Knoten an, die bei der Suche nach 15, 45 und 20 durchlaufen werden.
|
|
Aufgabe 3
|
|
Gegeben ist die Zahlenmenge S={87, 23, 27, 16, 18, 28}.
a)
Zeichen Sie einen ausgeglichenen binären Suchbaum für S.
b)
Zeichnen Sie die Belegung der Hash-Datenstruktur für S, die ein Hash-Array mit n=11 Elemente
hat und deren Hash-Funktion durch i(s)=s mod (n-1) definiert ist.
c)
Geben Sie ein n an, so dass für die oben gegebene Menge S keine Kollision in der Hash-Datenstruktur
auftritt, d.h. eine Zelle des Hash-Arrays nur auf höchstens einen Eintrag verweist.
|
|
Aufgabe 4
|
|
Beweisen Sie durch vollständige Induktion, dass die Summe s(n) der Dreierpotenzen der
ganzen Zahlen von 1 bis n gleich (n(n+1)/2)
2 ist.
|
|
Aufgabe 5
|
|
Beweisen Sie durch vollständige Induktion, dass die Anzahl k(h) an Knoten,
die ein binärer Baum der Höhe h haben kann, höchstens 2
h-1 ist, d.h. k(h)<= 2
h-1.
|
|
Aufgabe 6
|
|
Angenommen, es ist von einem Algorithmus bekannt, dass sein maximaler Zeitaufwand T(n)
folgender Beziehung genügt:
T(n) = T(n-1)+O(1) für n>1.
Geben Sie eine möglichst kleine gültige Wachstumsordnung (O-Notation) für T(n) an.
Beweisen Sie, dass T(n) diese Beziehung erfüllt.
Teil III (Vom Programm zum Rechner)
|
|
Aufgabe 1
|
|
Was sind die Basiskomponenten eines Rechners in der von-Neumann-Architektur?
|
|
Aufgabe 2
|
|
Beschreiben Sie den Ablauf der Befehlsausführung bei einem von-Neumann-Rechner.
|
|
Aufgabe 3
|
|
Die Funktionstabelle der Booleschen Funktion xor (entweder oder) sieht so aus:
| a |
b |
xor(a,b) |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 0 |
0 |
1 |
| 1 |
1 |
0 |
a)
Geben Sie eine Boolesche Formel mit and, or und not-Operationen für xor an.
b)
Zeichnen Sie einen Schaltkreis, der die Boolesche Formel realisiert.
|
|
Aufgabe 4
|
|
Stellen Sie die Funktionstabelle der Booleschen Funktion
auf.
|
|
Aufgabe 5
|
|
Was macht ein Compiler, was ein Interpreter?
|
|
Aufgabe 6
|
|
a)
Von welchem Typ ist die Grammatik
G=(T,N,P,S) mit T={a,b}, N={S}, P={S->ab, S->aSb}?
b)
Geben Sie die Sprache L(G) an, die von G erzeugt wird.
|
|
Aufgabe 7
|
|
Geben Sie eine reguläre Grammatik G an, deren Alphabet T nur das Zeichen c enthält und
deren Sprache L(G) alle Worte umfasst, in der das Zeichen c mit gerader Anzahl auftritt?
Falls Sie keine reguläre Grammatik finden, genügt auch eine kontextfreie.
