Einführung Informatik/Algorithmen und Datenstrukturen

Prof. Dr. Reiner Dumke

WS 00/01

Sören Balko, Ilona Blümel, Dr. Martina Engelke, Markus Feldbach, Niels Grabe, Dr. Reinhard Köppe, Uwe Scholz, Nadine Schulz, Dr. Fritz Zbrog

9. Übungsblatt

Aufgabe 34

Die Algorithmen A1 bis A5 haben die folgende Komplexität (= Anzahl elementarer Rechenschritte) in Abhängigkeit von der Problemgröße n:

A1: t1(n) = ld n (ld n = log2 n)          A2: t2(n) = n ld n

A3: t3(n) = n2                                    A4: t4(n) = n3

A5: t5(n) = 2n

a) Der Zeitbedarf für einen elementaren Rechenschritt sei 10-3 sec (= 1 Millisekunde). Erstellen Sie mit einem JAVA-Programm eine Tabelle mit den tatsächlichen Rechenzeiten in geeigneten Maßeinheiten der Algorithmen A1 bis A5 für n = 2k, k = 0,1,..,10.

b) Wie verändert sich der tatsächliche Zeitbedarf, wenn (z. B. durch effiziente Hardware) der Zeitaufwand für einen elementaren Rechenschritt auf 10-9 sec (= 1 Nanosekunde) verkürzt werden kann?

Aufgabe 35

Modifizieren Sie die Klasse Kreisdiagramm aus der Vorlesung, indem Sie die Neu-Immatrikulationen an der FIN 1999 geeignet darstellen.

Diplom-Informatiker:

100

Diplom-Wirtschaftsinformatiker:

100

Diplom-Computervisualisten:

155

Diplom-Informatiker Zusatzstudium:

19

Diplom-Informatiker Fernstudium:

47

Berufsbegleitend:

32

Aufgabe 36

Implementieren Sie folgende Verfahren zur Berechnung der ganzzahligen Potenzfunktion in JAVA:

Beide Methoden realisieren eine Reduktion auf die Berechnung der Potenzfunktion mit dem Exponenten n/2. Formal bedeutet dies:

a)

         a                            für n = 1
a n = a n/2 * a n/2 * a        für ungerades n > 1
         a n/2 * a n/2                 für gerades n

b)

         a                            für n = 1
a n = (a2) n/2 * a        für ungerades n > 1
         (a 2) n/2                 für gerades n

Was können Sie über die Komplexität beider Algorithmen aussagen?

Aufgabe 37

Bestimmen Sie die Zeitkomplexität des ungünstigsten Falles in Abhängigkeit von der Feldgröße n für den folgenden Algorithmus:

static void bubblesort(int[] feld){
     boolean swapped = false; // Vertauschung
     int max = feld.length - 1; // obere Feldgrenze
     do {
         swapped = false;
         for (int i = 0; i < max; i++) {
         if (feld[i] > feld[i + 1]) {
             // Elemente vertauschen
         int tmp = feld[i];
         feld[i] = feld[i + 1];
         feld[i + 1] = tmp;
         swapped = true;
        }
    }
     max--;
     } while (swapped); // solange Vertauschung auftritt
}

Hinweis: Jede arithmetische Operation (auch ein Vergleich), Indexberechnung und Zuweisung wird dabei mit 1 bewertet.

Aufgabe 38

Welche Komplexität in O-Notation haben folgende drei Anweisungsfolgen?

a)
for(i=1; i<n; i*=2);		 b)
for(i=1; i<n; i++);
for(i=n; i>0; i--);		 c)
for(i=1; i<n; i++)
for(j=1; j<n*n; j++);