URL:         /axel/informatik2_ss01_blatt1.html
Dieses  Übungsblatt ist in Zweiergruppen zu bearbeiten. Auf dem Blatt  bitte Übungsgruppentag angeben. Um den Übungsschein zu erhalten muß man 50% der  (Theorie)Punkte erreichen und zweimal erfolgreich eine Aufgabe vorrechnen.  Auch bei den Programieraufgaben müssen 50% erreicht werden.

Aufgabe 1 - binäres Suchen - (4 Punkte)

In der Vorlesung wurde  skizziert , dass der Aufwand beim binären Suchen in einem sortierten Feld  der Länge n  O(log n) ist.
Geben Sie hierfür einen  vollständigenBeweis.
 
 

Aufgabe 2 - priority queue - (4+2 Punkte)
Beim Heapsort  wird in der ersten Phase innerhalb eines Feldes ein sog. Haufen angelegt.  Erläutern Sie, wie  eine Variation dieser Idee verwendet werden kann, um  folgende  Aufgabe eines Betriebssystems zu   lösen:
In einem Betriebsystem (z.B. Linux)  kann es maximal  P  Prozesse  ( das sind zu erledigende  Aufgaben) P1,..,PP  geben. Diese Prozesse sind von unterrschiedlicher Priorität (Wichtigkeit)  W1,....,WP.  Die Prozesse  könnten eigentlich gleichzeitig  laufen, aber auf dem Rechner,  der leider nur eine  CPU hat, kann immer nur ein Prozess laufen.
Wie kann mit  einer Variation des Haufens erreicht werden, dass immer der Prozess mit der höchsten Priorität als nächster gestartet wird. Skizzieren Sie, was  bei folgenden  Aktionen passiert:

-  Erzeugen eines neuen Prozess  mit Priorität  W
-  Suche nach dem  wichtigsten Prozess , der neu gestartet werden soll.

Zeigen Sie, dass der  Aufwand   jeweils O(log p)  ist.

Aufgabe 3 - Programmieraufgabe (5 Punkte, Abgabe per email bis 10.5.01 10.00 Uhr)

diese Programmieraufgabe ist alleine zu bearbeiten.

Erweitern Sie  folgendes C Programm  mit einer  Implementierung des  bubblesort. Dazu soll die Routine
my_bubblesort_xxxxxx() ersetzt werden. Der Name soll statt der xxxxxx Ihre Matrikelnummer enthalten.
Die Zahlen sollen aufsteigend sortiert werden.
 

#include <stdlib.h>
int feld[] = {3,4,6,3,8,9,3,4,6,8};

main()
{
     int i;

     my_bubblesort_000000(feld, sizeof(feld)/sizeof(int) );
     for (i=0; i<sizeof(feld)/sizeof(int); i++)
             printf("%d ",feld[i]);
     printf("\n");
}
 
 

my_bubblesort_000000(int *feld, int feld_laenge)
/* hier muss eingefügt werden */
{
}