CoboCards App FAQ & Wünsche Feedback
Sprache: Deutsch Sprache
Kostenlos registrieren  Login

Hol' Dir diese Lernkarten, lerne & bestehe Prüfungen. Kostenlos! Auch auf iPhone/Android!

E-Mail eingeben: und Kartensatz kostenlos importieren.  
Und Los!
Alle Oberthemen / Informatik / Algorithmen & Datenstrukturen

ADS (25 Karten)

Sag Danke
1
Kartenlink
0
Determiniert (Ergebnis)/ Deterministisch (Ablauf)/ Terminierend
Das Ergebnis eines Algorithmus heißt determieniert, wenn es bei vorgegebenen Eingaben immer dasselbe Ergebnis liefert. Voraussetzung ist natürlich, dass die Eingangsparameter gleich sind.


Der Ablauf eines Algorithmus heißt deterministisch, wenn er eine eindeutige Vorgabe für die Folge der auszuführenden Schritte macht.



Ein Algorithmus heißt terminierend, wenn er nach endlich vielen Schritten, abbrechen würde.

=> z.B. eine Endlosschleife ist nicht terminierend, weil die nie abbricht
2
Kartenlink
0
TreeNode
public class TreeNode {
     int value;
     TreeNode right;
     TreeNode left;
     
     public TreeNode(int value, TreeNode right, TreeNode left){
           this.value = value;
           this.right = right;
           this.left = left;
     }
   
     public Class Tree {
            TreeNode root;
            
            public boolean isEmpty(){
                return root == null;
            }

            
3
Kartenlink
0
TreeNode
public Tree getLeft(){
                Tree t = new Tree();
                 t.root = root.left;
             }
      
             public void setLeft(Tree t){
                 left = t.root;
             }
   
             public void insert(int wert){
                 TreeNode parent= null;
                 TreeNode child = root;
                 if (child == null){
                    root = new TreeNode (wert, null, null);
                    return;
                 }
                 while (child != null){
                        
4
Kartenlink
0
Preorder/Postorder/Inorder
private void print_order(TreeNode root){
      if (root == null){
          return;
      }
      print_postOrder(root.left);
      print_postOrder(root.right);
      print(root);

      print(root);
      print_preOrder(root.left);
      print_preOrder(root.right);

      print_inOrder(root.left);
      print(root);
      print_inOrder(root.right);
}
5
Kartenlink
0
Binäre Suche (rekursiv)
static boolean binaer(int [] array, int unter, int oben, int key){
         if (unten > oben){
            return false;
         } else {
                  int mitte = (unten + oben)/2;
                  if(array[mitte]==key){
                      return true;
                   } else if(array[mitte] < key){
                       return binaer(array, mitte +1, oben, key)
                   } else{
                        return binaer (array, unter, mitte - 1, key)
                   }
}
                      
                     
6
Kartenlink
0
Selection Sort
public static void selectionSort(int [] array){
          for (int i = 0; i < array.length - 1; i){
                int min = i;
                for(int j = i + 1; j < array.length; j
){
                     if (array[min] > array [j]){
                         min = j;
                     }
                 if (min != i){
                     swap (array, min, i);
                 }
          }
}

- n*n
- instabil**
7
Kartenlink
0
Bubble Sort
public void bubbleSort(int [] a){
        for (int i = 0; i < a.length - 1; i){
              for (int j = 0; j < a.length - 1; j
){
                    if (a[j] > a[j + 1]){
                        swap (a, j, j +1);
                    }
               }
         }
}


boolean swapped;
do {
     swapped = false;
     for (int i = 0; i < a.length-1; i++){
           if (a [j] > a[j +1]){
               swapped = true;
           }
} while(swapped);
8
Kartenlink
0
Insertion Sort
public static void insertionSort(int [] array){
          for (int i = 1; i < array.length; i++){
                int j = i;
                int m = array [i];
                while (j > 0 && array[j - 1] > m){
                          array [j] = array[i - 1];
                          j --;
                }
                array[j] = m;
           }
}



- stabil
- n, bei kleineren Folgen sehr gut, bei fast sortiertem Array gut,
9
Kartenlink
0
Quick Sort
private void quicksort (int [] a, int links, int rechts)
    {
        int i=links;
        int j=rechts;
        int mitte =a[(links+rechts)/2];
        while (i<=j) {   
            while (a[i]< mitte) i;
            while (a[j]>mitte) j
;
            if (i<=j) {
                swap(a, i, j);
                i
;
                j ;
            }
        }
        if (links<j) quicksort(a, links, j);
        if (i<rechts) quicksort(a, i, rechts);
    }

  
10
Kartenlink
0
Binäre und lineare Suche/ Aufwand
  Linear Binär
bester Fall 1 1
schlechtester Fallnld n
Durchschnitt (erfolgreich)n/2ld n
Durchschnitt (erfolglos)nld n
11
Kartenlink
0
Sortierverfahren im Vergleich
    Aufwand im MittelStabilität
Selection Sort n*n instabil
Insertion Sort n*nstabil
Bubble Sort n*nstabil
Quick Sort n log ninstabil
Merge Sortn log nstabil
12
Kartenlink
0
Abstrakte Datentypen
- abstrahieren von Implementierung
- arbeiten nur mit einer Schnittstelle
- verborgene Implementierung
-
13
Kartenlink
0
Listen
- Jeder Knoten außer dem letzten hat hat genau einen Nachfolger.
- Merkt man sich in einem Knoten immer nur den Nachfolger, dann handelt es sich um eine Lineare Liste (linked list).
- B-Baum: Alle Blätter liegen in derselben Schicht; alle Knoten eiens Baumes der Ordnung n (mit Ausnahme der Wurzel) besitzen zwischen m/2 und m Kinder.

- AVL-Baum: Binärer Such-Baum, bei dem sich für jeden Knoten die Höhe seiner Teilbäume höchstens um 1 differiert.
              - im schlechtesten Fall = O (log n)
14
Kartenlink
0
Listen/ Implementierung
public class Liste{
   private ListElement erstes;
  
   public boolean isEmpty(){
       return erstes == null;
   }

  public int getFirst(){
       if (isEmpty()){
          throw new Exception;
       } else {
          return erstes.wert;
       }
}
  
  
15
Kartenlink
0
Listen /Implementierung
public int anzahlVorkommen(int gesucht){
       int zaehler = 0;
       Element e = erstes;
       while (e != null){
           if (e.wert == gesucht){
              zaehler ++;
           }
          e = e.naechst;
      }
      return zaehler;
}


public void addLast(int zahl){
      ListElem neu = new ListElem();
      neu.wert = zahl;
      neu.naechst = null;
      if (erstes == null){
         erstes = neu;
      } else {
         Element e = erstes;
         while (e.naechst != null){
                 e = e.naechst;
          }
          e.naechst = neu;
}    


--
16
Kartenlink
0
Listen/Implementierung
public void removeLast(){
      if (erstes == null){
         throw new Exception;
      } else if (erstes.naechst.naechst == null){
         erstes =null;
      } else {
          ListElem e = erstes;
          while (e.naechst != null){
                 e = e.naechst;
          }
          e.naechst = null;
}


public void removeFirst(){
      if (erstes == null){
          Exception;
      }else if (erstes.naechst == null){
          erstes = null;
      } else {
           erstes = erstes.naechst;
      }
}
--
17
Kartenlink
0
Stack / Implementierung
public class Stack{
     private Liste stack;
 
     public Stack(){
          stack = new Liste();
    }
   
     public int top(){
         return stack.getFirst();
    }
  
    public void push(int zahl){
        stack.addFirst(zahl);
    }

   public void pop(){
       stack.removeFirst();
   }
18
Kartenlink
0
Queue/ Implementierung
public class Queue{
      private Liste queue;
  
      public Queue(){
           queue = new Liste();
      }

     public int front(){
        return queue.getLast();
     }
    
     public void enter(int zahl){
        queue.addFirst(zahl);
    }

     public void leave(){
        queue.removeLast();
     }

    public boolean isEmpty(){
        if (queue.isEmpty()){
           return true;
       }else false;
19
Kartenlink
0
Stack / Implementierung
public class Stack{
     private Liste stack;
 
     public Stack(){
          stack = new Liste();
    }
   
     public int top(){
         return stack.getFirst();
    }
  
    public void push(int zahl){
        stack.addFirst(zahl);
    }

   public void pop(){
       stack.removeFirst();
   }
20
Kartenlink
0
Laufzeit
1. Mit einer Stoppuhr bestimmen

2. Pseudocode schreiben und Operationen zählen

3. Wie 2., nun werden aber nur die teuren Schritte gezählt (teuer: Vertauschung odr Vergleich)
21
Kartenlink
0
O-Notation
Dient zur Abschätzung der Aufwandsfunktion

Folgende Vereinfachungen sind möglich:

g = n3 + n2 g = n3
nur größten Exponent berücksichtigen

g = ldn g = log n
nur Logarithmus zur Basis 10 betrachten

g = an g = n
konstante Faktoren weglassen g

g = n + b g = n
konstante Summanden weglassen
22
Kartenlink
0
Bubble Sort VERBAL
Man wählt das linkeste Element und dieses wird mit seinem rechten Nachbarn verglichen. Falls die Reihenfolge nicht stimmt, vertauscht man die beiden Elemente miteinander. Fallt die Reihenfolge stimmt, geht man zum nächsten Element, mit dem zuletzt verglichen wurde. Dieses Element wird mit seinem rechten Nachbarn verglichen.

So geht man bis zum vorletzten Elemen in dem Array vor. Und dann bekommen wir die sortierte Folge.
23
Kartenlink
0
Insertion Sort VERBAL
Man nimmt ein Element aus dem Originalstapel und fügt es in dem Zielstapel hinzu. Unser Zielstapel hat jetzt die Länge 1. Dann nimmt man ein weiteres Element aus dem Originalstapel und fügt es an der richtigen Stelle in den Zielstapel ein.
Muss ein Element an einer Stelle im Zielstapel „dazwischen“ geschoben werden, dann schiebe die rechts davon liegenden Elemente jeweils um eine Position nach rechts.
Falls der Originalstapel nicht leer ist, mach weiter so. Ansonsten haben wir den ursprünglichen Stapel sortiert.
24
Kartenlink
0
Selection Sort VERBAL

Es gibt 2 Arrays oder Zahlenfolgen: die unsortierte Folge und eine weitere, in der dann die sortierten Zahlen gespeichert werden sollen, die am Anfang leer ist.
Man sucht sich dann das kleinste Element in der unsortierten Folge und danach wird dieses Element am Anfang in die sortierte Folge angefügt. Man macht das solange, bis es keine Elemente mehr in der unsortierten Folge gibt.
25
Kartenlink
0
Quick Sort VERBAL
Am Beginn hat man ein unsortiertes Array, gegeben über zwei Indices: Beginn und Ende. Falls das Array die Länge 1 (beginn ==ende) hat, ist es bereits sortiert. Ansonsten muss man ein Pivot-Element auswählen. Man kann dieses frei auswählen(ganz links, ganz rechts, mitte). Nachdem man z.B. das rechteste Element als Pivot-Element ausgewählt hat, muss man das ganze Array in Teilen zerteilen, so dass die Elemente in dem Teilarray von Beginn bis Mitte(Pivot) -1 kleiner als das Pivot-Element sind und die Elemente von Mitte + 1 bis Ende größer oder gleich als dem Pivot-Element sind

Das gleiche Verfahren wird dann auf die beiden Teilarray angewendet.
Kartensatzinfo:
Autor: hristiana86
Oberthema: Informatik
Thema: Algorithmen & Datenstrukturen
Schule / Uni: HS
Ort: Mannheim
Veröffentlicht: 14.06.2010
 
Schlagwörter Karten:
Alle Karten (25)
keine Schlagwörter
Missbrauch melden

Abbrechen
E-Mail

Passwort

Login    

Passwort vergessen?
Deutsch  English