Lösungen zu den alten Prüfungsfragen? Kläglicher Versuch...
Results 1 to 1 of 1

Thread: Lösungen zu den alten Prüfungsfragen? Kläglicher Versuch...

  1. #1
    Zentor's Avatar
    Title
    CO-Administrator
    Join Date
    Dec 2001
    Location
    Wien???
    Posts
    1,156
    Thanks
    2
    Thanked 9 Times in 6 Posts

    Lösungen zu den alten Prüfungsfragen? Kläglicher Versuch...

    Also ich wollt etwas üben und hab mir von der Algodat HP die Prüfungsangaben für die Jahresprüfung angeschaut und einige der relevanten Bsp versucht zu lösen. Ohje ganz schön schwer... Naja is wahrscheinlich alles falsch aber würd gern wissen was ihr so herausbekommt:
    Code:
    2000 06 30
    1.a)
    Sigma(g(n)) Theta(g(n)) O(g(n))
    ------------|----------|--------|
                               x                 
    ------------|----------|--------|
         x                                          
    ------------|----------|--------|
         x           x          x                                               
    ------------|----------|--------|
         x                                    
    ------------|----------|--------|
    1.b)
    Nein, da für n kleiner als 100 Sigma(n) gilt
    2.a) 
    Der Heap ist nur ein gedachter Suchbeim welcher ganz normal als Feld gespeichert ist. Ein
    Suchbaum ist eine eigene Datenstrucktur.
    2.b) ähnlich wie 2.) vom 2002 01 28
    4.)
    ----------------------------------------------------------------------------------------------------
    2000 10 09
    1.a)
    1.b) für alle n ab beliebigen n0, n0 > 0 ,c>0
         0 <= c*n <= 1/10 n log n
              c   <= 1/10   log n
         lim n-> Inf  log n = Inf  daraus folgt kein konstantes c kann gefunden werden
         Aussage falsch
    
    4.)
    ----------------------------------------------------------------------------------------------------
    2000 12 18
    
    1.a)
    wahr    falsch
    -------|--------|
               x
    -------|--------|
       x                         
    -------|--------|
               x                                           
    -------|--------|
               x             
    -------|--------|
       x                 
    -------|--------|
               x
    -------|--------|
       x                  
    -------|--------|
       x                          
    -------|--------|
       ?       ?
    -------|--------|
    
    1.b)
    Nein weil unter 1000 die Funktion O(n^2) hat und das ist nicht O (n log n) (z.B. bei -1)
    2.a)
    Merge-Sort(A,p,q)
    falls p < q dann {
      m = floor((p+q)/2);
      Merge-Sort(A,p,m);
      Merge-Sort(A,m+1,q);
      Merge(A,p,m,q);
    }
    2.b)
    21, 14, 28, 8, 17, 36, 15, 18,  5,  2
    Merge(A,1,1,2)
    14, 21, 28, 8, 17, 36, 15, 18,  5,  2  
    Merge(A,1,2,3)
    14, 21, 28, 8, 17, 36, 15, 18,  5,  2  
    Merge(A,4,4,5)
    14, 21, 28, 8, 17, 36, 15, 18,  5,  2  
    Merge(A,1,3,5)
    8, 14, 17, 21, 28, 36, 15, 18,  5,  2 
    Merge(A,6,6,7)
    8, 14, 17, 21, 28, 15, 36, 18,  5,  2 
    Merge(A,6,7,8)
    8, 14, 17, 21, 28, 15, 18, 36,  5,  2
    Merge(A,9,9,10)
    8, 14, 17, 21, 28, 15, 18, 36,  2,  5 
    Merge(A,6,8,10)
    8, 14, 17, 21, 28,  2,  5, 15, 18, 36
    Merge(A,1,5,10)
    2,  5,  8, 14, 15, 17, 18, 21, 28, 36 
    
    4.)
    ----------------------------------------------------------------------------------------------------
    2001 01 29
    1.a)
    A:T(n) = c1*(n+1)+(c2+c3)*n = Theta(n)
    B:T(n) = c1*(n+1)+c2*n+c3*n*(n+1)+c4*n*n = Theta(n^2)
    C:T(n) = c1+c2*(n+1)+c3*n+c4*n+c5*(n-1) = Theta(n)
    D:T(n) = c1+ c2*(k+1)+c3*k = Theta(1)  <---- weil hier nach Theta Notation für n gefragt wird nicht k
    E:T(n) = ???
    
    2.a)     
    stabil  nicht stabil
    -------|--------|
      x         
    -------|--------|
               x                 
    -------|--------|
               x                                            
    -------|--------|
               x              
    -------|--------|
         ?      ?                  
    -------|--------|
    
    2.b)
    314,263,329,298,193,223,253,110
    110,263,329,298,193,223,253,314
    110,193,329,298,263,223,253,314
    110,193,223,298,263,329,253,314
    110,193,223,253,263,329,298,314
    110,193,223,253,263,329,298,314
    110,193,223,253,263,298,329,314
    110,193,223,253,263,298,314,329
    Listen da hier nur die Zeiger umgeschrieben werden müssen und nicht der ganze Datensatz
    
    4.)
    ----------------------------------------------------------------------------------------------------
    2001 03 09
    
    1.a) 
    wahr    falsch
    -------|--------|
      x          
    -------|--------|
      ?(x)      ?       was heißt enthält in dem Fall ?                 
    -------|--------|
      ?(x)      ?                                              
    -------|--------|
      ?         ?              
    -------|--------|
      x                          
    -------|--------|
      ?        ?
    -------|--------|
    1.b)
    Ja weil die Obergrenze ab einem beliebigen Wert n0>0 gelten muss
    Also wenn man n0= 126 nimmt so hat die Funktion log n / 125 +5 sicher O(log n)
    2.a)
    2.b)
    Eine völlig Sortierte Folge
    2.c)
    kommt auf die Implementierung von Quicksort an
    3.)
    ----------------------------------------------------------------------------------------------------
    2001 05 18
    
    1.)
    28 n^6 - 12 n^2 + 14 n - 13 log n + 10 = Theta(n^6)
    
    für alle n ab beliebigen n0, n0 > 0 c1,c2>0
    0<= c1* n^6 <= 28 n^6 - 12 n^2  + 14n    - 13 log n + 10 <= c2* n^6 
        c1      <= 28     - 12 n^-4 + 14n^-5 - 13 log n * n^-6 + 10* n^-6 <= c2
      geht gegen   28            0       0             ?             0    
                     
           NR : log n * n^-6 L'Hospital: x^-1 * -6 * x^-5 -> 0 (für log zur Basis n)  
    
    Also geht der ganze Ausdruck gegen 28 -> z.B. c1 = 1 c2 = 100 ,n entsprechend groß wählen 
    
    2.)
    (1) falsch weil bei log n unter 10^8 hat die Funktion Sigma(n)
    (2) richtig weil O(n^2) für die Funktion sowohl unter log n = 10^8  als auch darüber gilt 
    (3) falsch weil bei log n über 10^8 hat die Funktion O(n^2)
    (4) richtig weil Sigma(n) für die Funktion sowohl unter log n = 10^8  als auch darüber gilt
    
    3.)
    
    6.)
    NeuSort(A,i,j):
    
    
    
    
    
    
    
    
    
    
    
    
    falls i < j dann {
      minpos = i;
      maxpos = j;
      für a = i...j  {
        falls A[a].key < A[minpos].key dann {
         minpos = a;
        }
        falls A[a].key > A[maxpos].key dann {
         maxpos = a;
        }
      }
      vertausche A[i] mit A[minpos];
      vertausche A[j] mit A[maxpos];
      i++;
      j--;
      Neusort(A,i,j)
    }
    
    ----------------------------------------------------------------------------------------------------
    2001 06 22 v1
    1.)
    O()     Sigma()   Theta()   
    -------|--------|--------|
      x        x        x             
    -------|--------|--------|
      x        x        x           
    -------|--------|--------|
               x                                             
    -------|--------|--------|
               x               
    -------|--------|--------|
               x                  
    -------|--------|--------|
    2.a)
    Sort1:Selection Sort
    Sort2:Insertion Sort
    2.b)
    Selection Sort ist nicht stabil weil Elemente von ganz hinten nach vorge getauchst werden können und 
    dann die Reihenfolge von 2 gleichen Elementen nicht mehr gegeben ist
    Insertion Sort ist stabil weil beim Verschieben der Elemente die Anderen nur verschoben und 
    nicht vertauscht werden, so dass die Reihenfolge von 2 gleichen Elementen erhalten bleibt
    2.c)
    ----------------------------------------------------------------------------------------------------
    2001 06 22 v2
    1.)
    A) T(n) = c1+(11+n)*c2+(10+n)*(c4 + c5) = Theta(n)
    B) T(n) = c1*(1+floor(n/1234)) +(1+floor(n/1234))+(c2+c3)=Theta(n)
    C) T(n) = c1+(1+floor(ld(k)))*c2+(floor(ld(k)))*(c3+c4) = Theta(1) 
    D)
    ----------------------------------------------------------------------------------------------------
    2001 10 12
    1.a)
    Sigma(g(n)) Theta(g(n)) O(g(n))
    ------------|----------|--------|
                                  x                 
    ------------|----------|--------|
         x             x         x                      
    ------------|----------|--------|
         x                                                                    
    ------------|----------|--------|
         ?           ?         ?                
    ------------|----------|--------|
    1.b)
    Darf man negative Zahlen in Primfaktoren zerlegen??? -1 is doch keine Primzahl ???
    Hm wenn ja dann stimmt die Aussage nicht weil ja auch die Nicht-primzahlen 
    unbegrenzt vorhanden sind wenn man sich -unendlich nähert und daher mindestens Sigma(n^2) gelten muss
    3.)
    ----------------------------------------------------------------------------------------------------
    2001 12 14
    1.a)
    1.b)
    Ja weil O(n^3) für beide Fälle gilt
    3.) ähnlich wie 2.) vom 2000 12 18
    4.)
    ----------------------------------------------------------------------------------------------------
    2002 01 28
    1.a)
    In der O Notation kann man Konstante Faktoren vernachlässigen, da ja später
    sowieso alles mit einem konstanten c multipliziert wird also ist beides auf
    f(n) = O(1) zu vereinfachen. Somit sind sie ident und die Aussage wahr.
    1.b)
    2.).... das dauert ja ewig ....
    Last edited by Zentor; 16-04-2002 at 19:29.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •