Praktikum Algorithmische Anwendungen

Wintersemester 2003/04

Praktikum 1

 

Gruppe AI A1
M. Serhat Çinar 11030409 ai440
Michael Boiman 11027800 ai320
Mustafa Ekit 11027589 ai336

 

Index

  • Aufgabe 1: Insertion Sort mit Merge Sort kombiniert
  • Aufgabe 2: Evaluation von Polynomen
  • Aufgabe 3: Inversionen
  •  


    Aufgabe 1: Insertion Sort mit Merge Sort kombiniert     top

    A) Zeige, dass n/k Teillisten jeweils der Länge k durch InsertSort im Worst Case in Ø(nk) Zeit sortiert werden können.

    Im Worst Case: Zum sortieren benötigt InsertionSort (k-1)*k / 2 Vergleiche, denn beim ersten Durchlauf muss das erste Element mit allen anderen n-1 elementen Verglichen werden. Das 2. Element muß mit den restlichen n-2 Elementen verglichen werden. Dies führt zur Folge n-1, n-2, n-3, ..., 1. Nach der Summenformel von Gauss gilt Sum(i) mit i=1...k = k*(k+1) / 2. Setzt man hier statt k k-1 ein, erhält man die besagten (k-1)*k/2 Vergleiche. Dies wiederum entspricht einer Laufzeit von O(k2).
    Diese Laufzeit liegt n/k mal vor, daher gilt für alle n/k Teilfolgen die Laufzeit O(n/k * k2) = O(nk).

    B) Ziege, dass die Teillisten in Ø(n log(n/k)) Worst Case Zeit gemischt werden können.

    Die Idee der Merge-Sort besteht ja darin, die Sequenz zu halbieren und diese beiden Hälften jeden für sich zu sortieren. Anschliessend werden die beiden geordneten Teile zusammen gemischet.
    Wenn aber die Liste vorher mit InsertSort sortiert wird, braucht sie nicht mehr per MergeSort sortiert werden.
    Deshalb werden die Teillisten in O ( n * log (n/k) ) und nicht in O ( n * log (n) ) Zeit gemischt.

    C) Gegen ist ein modifizierter Algorithmus, der in Ø(nk + n log(n/k)) Worst-Case-Zeit läuft. Welches ist der größte Asymptotische (Ø-Notation) Wert für k als Funktion von n, für den der modifizierte Algorithmus dieselbe asymptotische Laufzeit hat wie der Standard-MergeSort-Algorithmus?

    Wählt man k = log n (durch Ausprobieren!) so ergibt sich für die Laufzeit: Ø(n log n + n log (n/log n)). Dies liegt gerade noch in Ø(n log n). Wählt man einen höheren Wert für k, so liegt die Laufzeit schon in Ø(n2).

    D) Wie würde man k in der Praxis wählen?

    Wegen 1C) k <= Floor (log n)


    Aufgabe 2: Evaluation von Polynomen     top

    Ein Polynom P(x) = Sum(akxk) mit k=0...n ist nach Faktorisierung a0+x*(a1+ x*(a2+...+x*(an-1+x*an)...)). Die Evaluation durch das Horner-Schema kann mit folgendem Algorithmus gemacht werden:

    y = 0
    i = n
    while i >= 0
      do y = a[i] + x*y
      i = i-1
    

    A) Welche asymptotische Laufzeit hat der Algorithmus für die Horner-Regel?

    Die Laufzeit beträgt O(n), da eine einfache Schleife über i=0...n evaluiert wird.

    B) Schreiben Sie einen Algorithmus, der das Polynom auf primitive Art und Weise evaluiert. Welche Laufzeit hat dieser Algorithmus? Wie arbeitet er im Vergleich zur Horner-Regel?

    for i = 0 to n
       pow = 1;
       for p = 1 to n-1
         pow = pow * x
       y = a[i] * pow
    

    Die asymptotische Laufzeit beträgt O(n2), da zwei ineinander verschachtelte Schleifen ausgeführt werden.
    Im Gegensatz zum Horner-Schema werden redundanterweise Zwischenergebnisse für die Potenzen von x nicht zwischengespeichert, bzw. genutzt.

    C) Prüfe folgende Schleifeninvariante der While-Schleife:
    Am Anfang jeder Iteration gilt: y = Sum(ak+i+1*xk) mit k=0...n-(i+1).
    i y = ai+x*y i Invariante (Sum)
    n an + x*0 = an n-1 a0+n*x0=an
    n-1 an + x*an-1 n-2 a0+n*x0+a1*(n+1)*x1=an-1
    . . . .
    . . . .
    0 . -1 .
    Die Schleifeninvariante der while-Schleife muss einmal durchgelaufen werden, damit sie stimmt!

     


    Aufgabe 3: Inversionen     top

    Sei A[1...n] ein Array mit n verschiedenen Zahlen. Wenn i<j und A[i] > A[j], dann heißt das Paar (i,j) eine Inversion von A.

    A) Wie lauten die 5 Inversionen der Folge <2,3,8,6,1>?

    (2,1), (3,1), (6,1), (8,1), (8,6)

    B) Welches Array mit Elementen aus der Menge {1, 2, ..., n} hat die meisten Inversionen? Wie viele Inversionen sind es?

    Das von großen auf kleine Werte sortierte Array [n, n-1, ..., 1] hat die meisten Inversionen, nämlich (n-1)*n/2 verschiedene Inversionen. (n, n-1), (n, n-2), ..., (n, 1), (n-1, n-2), (n-1, n-3), ..., (3, 2), (3, 1), (2, 1).

    C) Welche Beziehung besteht zwischen der Laufzeit von InsertionSort und der Anzahl der Inversionen des Eingabefeldes? Begründung!

    Die Inversionen beschreiben genau die Paare, die im Verlaufe des Sortierens vertauscht werden müssen. Dem entsprechend müssen genausoviele Vertauschungen wie Inversionen vorgenommen werden. Die Laufzeit von InsertionSort ist damit äquivalent zur Anzahl der Inversionen.

    D) Geben Sie einen Algorithmus an, welcher die Anzahl der Inversionen in einer beliebigen Permutation von n Elementen in Ø(n log n) Worst-Case-Zeit bestimmt. Hinweis: Modifiziere MergeSort.

    import java.util.Random;
    
    
    /**
     * MergeInversions.java
     * 
     * Created on 21.10.2003
     * @author M. Serhat Cinar; Michael Boiman, Mustafa Ekit 
    based on code from http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/merge/merge.htm * @version 23.10.2003 */ public class MergeInversions { private int[] a, b; // temporäres Array b private int inversions = 0; public void sort(int[] a0){ a=a0; int n=a.length; b=new int[n]; mergesort(0, n-1); } private void mergesort(int lo, int hi){ int inversions = 0; if (lo<hi){ int m=(lo+hi)/2; mergesort(lo, m); mergesort(m+1, hi); merge(lo, hi); } } private void merge(int lo, int hi){ int i, j, k, m, n=hi-lo+1; k=0; m=(lo+hi)/2; // untere Hälfte in Array b kopieren for (i=lo; i<=m; i++) b[k++]=a[i]; // obere Hälfte in umgekehrter Reihenfolge in Array b kopieren for (j=hi; j>=m+1; j--) b[k++]=a[j]; i=0; j=n-1; k=lo; // jeweils das nächstgrößte Element zurückkopieren, // bis i und j sich überkreuzen while (i<=j) if (b[i]<=b[j]) a[k++]=b[i++]; else{ a[k++]=b[j--]; inversions++; } } public int getInversions(){ return inversions;} public static void main(String[] args){ int size = 20; // Default if (args.length == 1) size = Integer.parseInt(args[0]); // Folge erzeugen int i; int A[] = new int[size]; // Falls ein Parameter angegeben wurde Zufallszahlen erzeugen if (args.length == 1){ // Zufallszahlengenerator Random rnd = new Random(System.currentTimeMillis()); // Zahlen zufällig generieren for (i=0; i<size; i++) A[i] = rnd.nextInt(); } // Sonst Reverse Folge else for (i=0; i<size; i++) A[i] = size-i; System.out.println("Folge:"); // Folge ausgeben for (i=0; i<size; i++) System.out.println("A["+i+"] = "+A[i]); // Inversionen Anzahl berechnen & sortieren MergeInversions merger = new MergeInversions(); merger.sort(A); int inversions = merger.getInversions(); System.out.println("Anzahl Inversionen :"+inversions); System.out.println("Maximale Anzahl Inversionen bei "+ A.length+" Elementen :"+ Math.round((float)(A.length*(A.length-1)*0.5))); } }