Posts Tagged ‘Programmierung’
Zweites BS1 Praktikum

Hier nun die Lösungen zu den Aufgaben 2-4 aus dem zweiten BS1 Praktikum!
In Aufgabe 2 sollte man die Anzahl der Parameter in der Argumentenliste und die Argumentenliste, die bei dem Programmaufruf angegeben wird, mittels des Programms ausgeben. Die Ausgabe erfolgt, wie gefordert, dabei über die Pointerschreibweise. Werden keine Parameter angegeben, so wird eine Fehlermeldung ausgegeben und ein Fehlercode an die Shell zurück gegeben.

#include<stdio.h>
#include<stdlib.h>

int main(int argc, char *argv[]) {
    int    i = 0;
    if (argc==1){
        printf(“ERROR: Kein Parameter!\n”);
        return 1;
    }
    else {
        printf(“Anzahl der Kommandozeilenparameter: %d \n”, argc);
        printf(“Die Eingabeparameter sind:\n”);
        while(*argv != 0) {
            printf(“argv[%d] = %s \n”, i++, *argv++);
        }
    }
    return 0;
}

Die Aufgabenstellung Nummer drei lässt sich schnell und unkompliziert zusammenfassen. Gefordert war die Ausgabe der Umgebungsvariablen, das Setzen einer Umgebungsvariable und das Suchen nach Umgebungsvariablen, ob diese vorhanden sind!

#include<stdio.h>
#include<stdlib.h>

void main(int argc, char* argv[], char* envp[]) {
    printf(“Liste der Umgebungsvariablen:\n”);
    while(*envp != 0) {
        printf(“%s \n”, *envp++);
    }

    setenv (“HUGO”, “Hugo”, 1);

    char search[50];
    printf(“Geben Sie die zusuchende Umgebungsvariable an:\n”);
    scanf(“%s”, &search);
    if(getenv(search)){
        printf(“%s = %s\n”, search, getenv(search));
    }
    else{
        printf(“Die gesuchte Umgebungsvariable existiert nicht!\n”);
    }
}

Das Programm für Ausgabe 4 ersetzt einen vorhandenen Prozess durch einen anderen mittels einem Befehl aus der exec-Familie. Der fork()-Aufruf durfte laut Aufgabenstellung nicht verwendet werden.

#include <stdio.h>
#include <unistd.h>

int main() {
    printf(“Eigene Prozess-ID: %i\n\n”, getpid());
    execlp(“ps”, “ps-Test”, 0);
    printf(“Ein Problem ist während dem Ersetzen des Prozesses aufgetreten!”);
return -1;
}

Erstes DB2 und BS1 Praktikum

Die ersten Praktikaabnahmen in den Fächern DB2 und BS1 liegen erfolgreich hinter mir. Die Aufgaben der Praktika und die entsprechenden Lösungen präsentiere ich euch in diesem Artikel.

Das erste Datenbank 2 Praktikum beinhaltete insgesamt 6 Aufgaben, die jeweils wieder Teilaufgaben enthielten. Die erste Aufgabe in diesem Zusammenhang bezog sich noch auf den Themeninhalt der im letzten Semester statt gefundenen Vorlesung Datenbanken 1.

  • 1. Transaktionen
    1. Einfügen von zwei Datensätzen mittels SQL-DML-Befehlen in zwei Tabellen.
    2. Verändern von gespeicherten Daten, so dass ein Integritätsfehler für den Primärschlüssel auftritt.
    3. Prüfzeitpunkt eines anderen Primärschlüssels auf INITIALLY DEFERRED ändern.
    4. Mittels SQL-DML-Befehlen Testdaten erstellen und sich jeweils nach der Aktion die Tabellen ausgeben lassen.
    5. Datensätze in der Reihenfolge Subtyp dann Supertyp hinzufügen / Datensätze in der Reihenfolge Supertyp dann Subtyp löschen.

Die Zusammenhänge und die jeweiligen Reaktionen/Aktionen des Systems/der Befehle müssen dabei erklärt werden können

  • 2. PL/SQL-Funktion: Datumsfunktion
    1. Das aktuelle Tagesdatum soll entweder in deutscher oder amerikanischer Schreibweise ausgegeben werden. Das Kennzeichen wird dabei an die Funktion beim Aufruf übergeben.
  • 3. PL/SQL-Prozedur im Theater: Namen trennen
    1. Ein an die Prozedur übergebener Name soll getrennt nach Vorname, 2. Vorname und Nachname zurückgegeben werden. (Der Name besteht wenigstens aus zwei Teilen und maximal aus drei Teilen.)
  • 4. PL/SQL-Prozedur im Theater: Dichter ohne Inszenierung
    1. Es sollen dabei folgende Daten aus der Datenbank ermittelt werden:
      1. Dichter und zugehörigen Dramen, für die es keine Inszenierung gibt.
      2. Dichter für die kein Drama in der Datenbank hinterlegt ist.
    2. Die Sortierung soll aufsteigend nach dem Namen der Dichter und der Titel erfolgen.
  • 5. PL/SQL-Prozedur im Theater: Dichter mit den meisten Inszenierungen
    1. Die Dichter mit den meisten Inszenierungen in dem angegebenen Suchintervall (z.B. 2008-2009) sollen ausgegeben werden. Fehlt die erste Jahreszahl, so wird automatisch die kleinste Jahreszahl einer Inszenierung gesetzt. Genau umgekehrt verhält es sich für die letzte Jahreszahl.
  • 6. PL/SQL-Prozedur im Theater: Package-Prozeduren
    1. Es soll ein Package aus den Aufgaben 3, 4 und 5 erstellt werden.
    2. Aufgabe 3 soll eine private Prozedur im Package sein.
    3. Aufgabe 4 soll so angepasst werden, dass die private Prozedur zur Namensausgabe der Dichter verwendet wird.

Praktikum_1_DB_2

Das Praktikum in Betriebssysteme und verteilte Systeme 1 bestand im Gegensatz zum Datenbank 2 Praktikum nur aus 4 Aufgaben. Zu der ersten Aufgabe existieren einige Lösungen im Internet, so dass ich auf diese schriftliche Ausarbeitung nicht weiter eingehen werde. Sondern mich direkt den Aufgaben 2, 3 und 4 widme.

Aufgabe 2:
Hier sollte ein Shell-Script und ein C-Programm implementiert werden. Das C-Programm soll dabei nach einer bestimmten Anzahl Sekunden folgenden Text ausgeben: “./p1 nach der 1. Schlafzeit” und nochmals “./p1 nach der 2. Schlafzeit”. Dabei werden der Name des C-Programms (p1) und die Anzahl der Sekunden über das Shell-Script eingelesen und dann an das Programm übergeben. Mittels symbolischen Link soll der zweite Aufrufname p2 erzeugt werden. Beide Programmaufrufe sollen durch die Shell in den Hintergrund geschickt und zusätzlich  eine ausführliche Prozessliste ausgegeben werden.

C-Programm: p1

#include<stdio.h>
#include<stdlib.h>

void main(int argc, char* argv[]) {
    int x = 0,
         i = 1;
    if (argc==1)
        printf(“ERROR: Kein Paramter!\n”);
    else {
        x = atoi(argv[1]);
        while(i<3) {
            sleep(x);
            printf(“%s nach der %d. Schlafzeit. \n”, argv[0], i++);
        }
    }
}

Der symbolische Link wird mittels ln –s ./p1 ./p2 auf der Konsole erzeugt.

Shell-Script:

#! /usr/bin/sh
echo “Programm?”
read progr
echo “Zeit?”
read zeit
./$progr $zeit &
jobs -l
ps -ef | grep $USER

Aufgabe 3:
Bei Aufgabe 3 sollte ein Shell-Script implementiert werden, welches Dateien aus einem Verzeichnis löscht. Die zu löschenden Dateien werden als Parameter an das Script übergeben. Das Script fragt bei jeder Datei, ob diese gelöscht werden soll oder nicht. Eine entsprechende Rückmeldung sowie Fehlermeldungen, wenn die Datei nicht exitiert, müssen auch implementiert werden. Die Verarbeitung der Parameterliste soll dabei nicht unterbrochen werden.

#! /usr/bin/sh
for i in $*
do if test -r $i
    then echo “Delete $i? (y/n)”
    read a
    if [$a == y]
        then rm $i
        echo –Datei $i wurde geloescht.–
    else echo –Datei $i nicht geloescht.–
    fi
else echo –Datei $i nicht gefunden.–
fi
done
echo DONE.

Aufgabe 4:
Hier erfolgt die Ausgabe der 10 häufigsten Vornamen der Benutzer auf dem Rechner advbs08.

#! /usr/bin/sh
ypcat passwd |
cut -d : -f 5 |
cut -d ‘ ‘ -f 1 |
sort |
uniq -c |
sort |
grep -v Samba |
grep -v Dr. |
sort -r |
head

 

Die Praktika wurden zusammen von meinen Kommilitionen und mir bearbeitet.
Aufgabe 8 – Algorithmik Praktikum

In diesem Teil des Praktikums war es Aufgabe das Dreieckszahlen-Hashing mit der Sondierungsfolge 0, 1, 3, 6, 10,… zu implementieren. Dazu sollte das Programm eine Ausgabe mit dem momentanen Füllgrad und der Anzahl an Clustern enthalten, sowie einen Performancetest.

Die Ausgabe auf der Konsole sieht mit dem fertigem Programm folgendermaßen aus:

Hier der Programmcode dazu:

import java.util.Random;

public class Three_hashing{
 
 public static int hash(int zahl, int groesse){
  int temp;
  temp = zahl%groesse;
  return temp;
 }
 
 public static int hash2(int zahl, int cnt, int groesse){
  int temp;
  temp = (int) ((zahl+0.5*cnt+0.5*(cnt*cnt))%groesse);
  return temp;
 }
 
 public static void hashInsert(int groesse, int array[], int arrayZuf[], int fillState, int fillStatePrev){
  Random r = new Random();
  int z=groesse*4;
  
  for(int i=fillStatePrev; i<fillState; i++){
   int zahl=0;
   boolean tempend = true;
   
   //Generierung von Zufallszahlen und Überprüfung, dass keine doppelt vorkommt
   while(tempend){
    zahl = r.nextInt(z);
    if(zahl!=0 ){
     for(int x=0; x<arrayZuf.length; x++){
      if(arrayZuf[x]!=zahl){
       arrayZuf[x]=zahl;
       tempend=false;
       x=arrayZuf.length;
      }
     }
    }
   }
   
   //Berechnung der Speicherstelle im Array => Hashing
   boolean end = true;
   int cnt=0;
   int hashKey = hash(zahl, groesse);
   
   if(array[hashKey]==0){
    array[hashKey]=zahl;
   }
   else{
    while(end){
     cnt++;
     int hashKey2=hash2(hashKey, cnt, groesse);
     if(array[hashKey2]==0){
      array[hashKey2]=zahl;
      end = false;
     }
    }
   }
  }
 }
 
 public static int hashSearch(int groesse, int array[], int fillState){
  Random r = new Random();
  int zaehler=0;
  int temparray[] = new int[fillState];
  int z=groesse*4;
  
  for(int i=0; i<fillState; i++){
   int zahl=0;
   boolean tempend = true;
   
   //Generierung von Zufallszahlen und Überprüfung, dass keine doppelt vorkommt
   while(tempend){
    zahl = r.nextInt(z);
    if(zahl!=0 ){
     for(int x=0; x<temparray.length; x++){
      if(temparray[x]!=zahl){
       temparray[x]=zahl;
       tempend=false;
      }
     }
    }
   }
   
   //Berechnung der Speicherstelle im Array => Hashing
   boolean end = true;
   int cnt=0;
   int cnt2=0;
   int hashKey = hash(zahl, groesse);
   
   if(array[hashKey]==0 || array[hashKey]==zahl){
    zaehler++;
   }
   else{
    while(end){
     if(cnt2>groesse){
      end = false;
     }
     cnt++;
     int hashKey2=hash2(hashKey, cnt, groesse);
     if(array[hashKey2]==0 || array[hashKey2]==zahl){
      zaehler++;
      end = false;
     }
     else{
      zaehler++;
     }
     cnt2++;
    }
   }   
  }
  return zaehler;
 }
 
 public static void main(String[] args){
  double groesse=128;
  int counter=10;
  int counterC=0;
  double Cn=0;
  double Cn1=0;
  double a=0;
  int Hash_array[] = new int[(int) groesse];
  int Zuf_array[] = new int[(int) groesse];
  int fillStatePrevTemp=0;
  
  while(counter<=99){
   int counter2=0;
   
   int fillStateTemp=(int) Math.round((groesse/100)*counter);
   hashInsert((int) groesse, Hash_array, Zuf_array, fillStateTemp, fillStatePrevTemp);
   fillStatePrevTemp=fillStateTemp;
   
   //Performancetest
   counterC=hashSearch((int) groesse, Hash_array, 64);
   counterC=(counterC/64);
   
   //Anzeige Konsole
   System.out.print(counter+”% “);
   
   //Anzeige von befüllten Arrayfeldern!
   for(int j=0; j<Hash_array.length; j++){
    if(Hash_array[j]!=0){
     System.out.print(“|”);
    }
    else{
     System.out.print(” “);
    }
   }
   
   //Zählen der vorhandenen Cluster
   int j=0;
   while(j<Hash_array.length){
    if(Hash_array[j]!=0){
     while(j<Hash_array.length && Hash_array[j]!=0){
      j++;
     }
     counter2++;
    }
    else{
     while(j<Hash_array.length && Hash_array[j]==0){
      j++;
     }
    }
   }
   
   if(Hash_array[0]!=0 && Hash_array[(int) (groesse-1)]!=0){
    counter2- -;
   }
   
   //Cn und Cn’ Berechnung
   a=counter/100.00;
   Cn=1+Math.log(1/(1-a))-(a/2);
   Cn1=(1/(1-a))-a+Math.log(1/(1-a));
   
   System.out.print(” “+counter2);
   System.out.print(” — C=”+counterC);
   System.out.print(” Cn: “+Cn);
   System.out.print(” Cn’: “+Cn1);
   System.out.println(” “);
   if(counter!=90){
    counter=counter+10;
   }
   else{
    counter=counter+9;
   }
  } 
 }
}

4. DB Praktikum und 2. ALG Praktikum

Hier zwei Lösungen für das vierte Datenbank Praktikum und das zweite Algorithmik Praktikum.

Das vierte Datenbank Praktikum handelte über die Erstellung einer Datenbank heraus aus einem ERM-Diagramm. Mittels dem Modellierungstool ERwin wurde der dazu nötige SQL-Code erstellt. Desweiteren wurden weitere SQL-Skripte für die restlichen Aufgabenteile erstellt. Dort sollten dann Benutzerrechte gesetzt , Constraints hinzugefügt und als Test in jede Tabelle mindestens eine Zeile eingefügt werden.

Create: CREATE

Constraints: ALTER

Insert: INSERT

Im zweiten Algorithmik Praktikum wurden AVL-Bäume behandelt. Aufgabe war es ein einfaches Konsolen-Interface zu programmieren, welches die entsprechenden Operationen für AVL-Bäume anspricht. Die Operationen mussten selbstverständlich auch programmiert werden.

AVLNode.java:

public class AVLNode{
 protected AVLNode left;
 protected AVLNode right;
 protected int balance;
 public int value;
 
 //Konstruktoren
 
 public AVLNode(int value){
  this(value, null, null);
 }
 
 public AVLNode(int value, AVLNode left, AVLNode right){
  this.value=value;
  this.left=left;
  this.right=right;
  balance=0;
 }
 
 /**
  * Liefert die Höhe eines Teilbaumes
  * @return Gibt die Höhe eines Teilbaumes zurück
  */
 
 public int hoehe(){
  int l=0;
  int r=0;
  
  if(left!=null) l=left.hoehe();
  if(right!=null) r=right.hoehe();
  return Math.max(l, r)+1;
 }
}

 AVLTree.java:

public class AVLTree{
 
 private AVLNode root;
 
 /**
  * Konstruktor
  */
 
 public AVLTree(){
  root = null;
 }
 
 /**
  * Aufruf um einen Knoten hinzu zu fügen
  * @param value hinzu zu fügender Knoten
  */
 
 public void insert(int value){
  root = insert(value, root);
 }
 
 /**
  * Aufruf um einen Knoten zu löschen
  * @param value zu löschender Knoten
  */
 
 public void remove(int value){
  if(isEmpty()){
   System.out.println(“Leerer Baum”);
  }
  else{
   root = remove(value, root);
  }
 }
 
 /**
  * Löscht den kompletten Baum
  */
 
 public void delete(){
  root = null;
 }
 
 /**
  * Prüft ob der Baum leer ist
  * @return true oder false
  */
 
 public boolean isEmpty(){
  return root==null;
 }
 
 /**
  * Aufruf der versetzten Ausgabe
  */
 
 public void ausgBinaerBaum(){
  if(isEmpty()){
   System.out.println(“Leerer Baum”);
  }
  else{
   ausgBinaerBaum(root,0);
  }
 }
//——————————————————————
 /**
  * Gibt den Baum ab dem angegebenen Knoten versetzt aus
  */
 
 public void ausgBinaerBaum(AVLNode node, int step){
  if(node != null){
   ausgBinaerBaum(node.right, step + 1);
   for (int i=0; i < step; i++){
    System.out.print(“-”);
   }
   System.out.println(node.value+”  (“+node.balance+”)”);
   ausgBinaerBaum(node.left, step + 1);
  }
 }
 
 /**
  * Berechnet die Balance des jeweiligen Knotens
  */
 
 private static int bal(AVLNode p){
  AVLNode r=p.right;
  AVLNode l=p.left;
  int bal=0;
  
  if(r!=null && l!=null){
   bal=r.hoehe()-l.hoehe();
  }
  else if(r!=null && l==null){
   bal=r.hoehe();
  }
  else if(r==null && l!=null){
   bal=0-l.hoehe();
  }
  return bal;
 }
 
 /**
  * Fügt einen Knoten in den angegebenen Teilbaum ein
  */
 
 private AVLNode insert(int value, AVLNode node){
  if(node == null){
   node = new AVLNode(value, null, null);
  }
  else if (value < node.value){
   node.left = insert(value, node.left);
   node=upin(node);
  }
  else if(value > node.value){
   node.right = insert(value, node.right);
   node=upin(node);
  }
  else{
    System.out.println(“Der Knoten ist schon vorhanden!”);
  }
  return node;
 }
 
 private AVLNode upin(AVLNode node){
  node.balance=bal(node);
  if(node.balance==-2){
   if(node.left.balance!=1){
    node = rotationRight(node);
   }
   else{
    node = doublerotationLeftRight(node);
   }
  }
  else if(node.balance==2){
   if(node.right.balance!=-1){
    node = rotationLeft(node);
   }
   else{
    node = doublerotationRightLeft(node);
   }
  }
  return node;
 }
 
 //Rechtsrotation
 
 private static AVLNode rotationRight(AVLNode node){
  AVLNode temp = node.left;
   node.left = temp.right;  
   temp.right = node;
   
   node.balance = bal(node);
   temp.balance = bal(node);
   
  return temp;
 }
 
 //doppelt: Links-Rechts-Rotation
 
 private static AVLNode doublerotationLeftRight(AVLNode node){
  node.left = rotationLeft(node.left);
  return rotationRight(node);
 }
 
 //Linksrotation
 
 private static AVLNode rotationLeft(AVLNode node){
  AVLNode temp = node.right;
   node.right = temp.left;
   temp.left = node;
   
   node.balance = bal(node);
   temp.balance = bal(node);
   
  return temp;
 }
 
 //doppelt: Rechts-Links-Rotation
 
 private static AVLNode doublerotationRightLeft(AVLNode node){
  node.right = rotationRight(node.right);
  return rotationLeft(node);
 }
 
 /**
  * Entfernt einen Knoten aus dem angegebenen Teilbaum
  */
 
 private AVLNode remove(int value, AVLNode node){
  if(node == null){
    System.out.println(“Wert nicht vorhanden”);
  }
  else if (value == node.value){
   if(node.left == null){
    return node.right;
   }
   else if(node.right == null){
    return node.left;
   }
   else{
    if(node==root){
     node=rootRemove(node);
     return node;
    }
    else{
     AVLNode temp=Successor(node);
     remove(temp.value, node);
     node.value=temp.value;
     return node;
    }
   }
  }
  else if (value < node.value){
   node.left = remove(value, node.left);
   node=upout(node);
  }
  else if(value > node.value){
   node.right = remove(value, node.right);
   node=upout(node);
  }
  return node;
 }
 
 private AVLNode rootRemove(AVLNode node){
  AVLNode prev=null;
  AVLNode temp=node.right;
  while(temp.left != null){
   prev=temp;
   temp=temp.left;
  }
  if(prev!=null){
   prev.left=temp.right;
   temp.right=node.right;
   prev.balance=bal(prev);
  }
  temp.left=node.left;
  node=temp;
  if(node.right!=null){
   node.right=upout(node.right);
  }
  node=upout(node);
  return node;
 }

 private AVLNode upout(AVLNode node){
  node.balance=bal(node);
  if(node.balance==2){
    if(node.right.balance!=-1){
     node = rotationLeft(node);
    }
    else{
     node = doublerotationRightLeft(node);
    }
  }
  else if(node.balance==-2){
   if(node.left.balance!=1){
    node = rotationRight(node);
   }
   else{
    node = doublerotationLeftRight(node);
   }
  }
  node.balance=bal(node);
  return node;
 }
 
 private AVLNode Successor(AVLNode node){
  AVLNode temp=node.right;
  while(temp.left != null){
   temp=temp.left;
  }
  return temp;
 }
 
 private AVLNode Predecessor(AVLNode node){
  AVLNode temp=node.left;
  while(temp.right != null){
   temp=temp.right;
  }
  return temp;
 }
 
 public boolean IsSuccessor(int node, int node2){
  AVLNode temp=IsMember(node2);
  AVLNode temp2=Successor(temp);
  if(temp2.value==node){
   return true;
  }
  return false;
 }
 
 public boolean IsPredecessor(int node, int node2){
  AVLNode temp=IsMember(node2);
  AVLNode temp2=Predecessor(temp);
  if(temp2.value==node){
   return true;
  }
  return false;
 }
 
 public AVLNode IsMember(int value){
  AVLNode node = root;
  while(node != null){
   if(value == node.value){
    return node;
   }
   else if(value<node.value){
    node = node.left;
   }
   else{
    node = node.right;
   }
  }
  return null;
 }
}

Main.java:

import java.util.Scanner;

public class Main{
 public static void main(String[] args){
 
  boolean fertig = true;
  Scanner scan = new Scanner(System.in);
  AVLTree Baum = new AVLTree();
  
  while(fertig){
   System.out.println(“———————————————————”);
   System.out.println(“1   -  Knoten hinzufuegen || 2   -  Knoten löschen”);
   System.out.println(“3   -  AVL-Baum löschen   || 4   -  Suchen”);
   System.out.println(“5   -  IsPredecessor      || 6   – IsSuccessor”);
   System.out.println(“9   -  Beenden”);
   System.out.println(“———————————————————”);
   if(!Baum.isEmpty()){
    System.out.println(“****************************************”);
    Baum.ausgBinaerBaum();
    System.out.println(“****************************************”);
   }
   //Auswahl einlesen
   int Zahl = scan.nextInt();
  
   //Menüoptionen
   switch(Zahl){
    case 1:
     int wert = scan.nextInt();
     Baum.insert(wert);
     break;
    case 2:
     int wert2 = scan.nextInt();
     Baum.remove(wert2);
     break;
    case 3:
     Baum.delete();
     break;
    case 4:
     int wert3 = scan.nextInt();
     AVLNode temp=Baum.IsMember(wert3);
     if(temp!=null&&temp.value==wert3){
      System.out.println(wert3+” ist vorhanden!”);
     }
     else{
      System.out.println(wert3+” ist nicht vorhanden!”);
     }
     break;
    case 5:
     if(!Baum.isEmpty()){
      System.out.println(“Geben Sie den Vorgängerknoten an den Sie vergleichen wollen:”);
      int wert4 = scan.nextInt();
      System.out.println(“Geben Sie Knoten an dessen Vorgänger mit ihrem angegebenen Vorgänger verglichen werden soll:”);
      int wert5 = scan.nextInt();
      if(Baum.IsPredecessor(wert4, wert5)==true){
       System.out.println(wert4+” ist der Vorgänger von “+wert5+”!”);
      }
      else{
       System.out.println(wert4+” ist nicht der Vorgänger von “+wert5+”!”);
      }
     }
     else{
      System.out.println(“Leerer Baum”);
     }
     break;
    case 6:
     if(!Baum.isEmpty()){
      System.out.println(“Geben Sie den Nachfolgerknoten an den Sie vergleichen wollen:”);
      int wert6 = scan.nextInt();
      System.out.println(“Geben Sie Knoten an dessen Nachfolger mit ihrem angegebenen Nachfolger verglichen werden soll:”);
      int wert7 = scan.nextInt();
      if(Baum.IsSuccessor(wert6, wert7)==true){
       System.out.println(wert6+” ist der Nachfolger von “+wert7+”!”);
      }
      else{
       System.out.println(wert6+” ist nicht der Nachfolger von “+wert7+”!”);
      }
     }
     else{
      System.out.println(“Leerer Baum”);
     }
     break;
    case 9:
     fertig = false;
   }
  }
 }
}

Windows Server 2008 R2 über Dreamspark verfügbar

Wie ich heute gesehen habe, ist der Windows Server 2008 R2 Standard Edition über Dreamspark verfügbar! Die Freischaltung erfolgt schnell und einfach mittels seiner eigenen Hochschulmailadresse. Weitere interessante Produkte die über Dreamspark verfügbar sind:

  • SQL Server 2008 Developer
  • Robotics Developer Studio 2008 R2
  • XNA Game Studio 3.1
  • Expression Studio 3
  • Visual Studio 2008 Professional
  • Windows Server 2008 Standard
  • Windows Server 2003

-> www.dreamspark.com

6. AP 2 Praktikum

Die Aufgabenblätter sind hier zu finden: http://www.gm.fh-koeln.de/~ehses/ap/index.html

Aufgabe 1:

Node.java:

package search.util;

public class Node {
 public Object value;
 public Node next;

 Node (Object value, Node next) {
 this.value = value;
 this.next = next;
 } 
}

ConcatenateList.java:

package search.util;

import java.util.Comparator;
public class ConcatenateList {
 private Node first = null;

 public boolean isEmpty() {
  return first == null;
 }
  
 public Object removeFirst() {
  Object retValue = first.value;
  first = first.next;
  
  return retValue;
 }
 
 public void addLast(Object o) {
  Node newNode = new Node(o, null);
  
  if (first == null) {
   first = newNode;
  }
  else {
   Node temp = first;
   while (temp.next != null) {
    temp = temp.next;   
     
   temp.next = newNode;
  }
 }
 
 public void clear() {
  first = null;
 }

 public void add(Object o, Comparator cmp) {
  if ( isEmpty() ) {
   first = new Node(o, null);
  }
  else {

   Node temp = first;  
   Node temp_prev = null; 

   while ( temp != null && cmp.compare(o, temp.value) > 0 ) {
    temp_prev = temp;
    temp = temp.next;
   }
   
   if (temp == null) {
    temp_prev.next = new Node (o, null);
   }
   else if (temp == first){

     first = new Node (o, temp);
   }
   else{
    temp_prev.next = new Node (o, temp);
   }
  }
 }

 public Object removeLast() {

  Node temp = first;  
  Node temp_prev = null; 
  
  while (temp.next != null) {
   temp_prev = temp;
   temp = temp.next;
  }
  
  if (temp == first) {
   first = null;
   return temp.value;
  }
  else {
   temp_prev.next = null;
   return temp.value;
  }
 }
}

FIFOQueue.java:

package search.util;

import java.util.NoSuchElementException;

public final class FIFOQueue implements IQueue {

 private ConcatenateList snake = new ConcatenateList();
 
 public void clear() {
  snake.clear();  
 }

 
 public Object get() {
  if (this.isEmpty()) throw new NoSuchElementException(“Queue is empty”);
  return snake.removeFirst();
 }

 
 public boolean isEmpty() {
  return snake.isEmpty();
 }

 
 public void put(Object p) {
  snake.addLast(p);
 }
 
}

LIFOQueue.java:

package search.util;

import java.util.NoSuchElementException;

public final class LIFOQueue implements IQueue {

 private ConcatenateList stack = new ConcatenateList();
 
 public void clear() {
  stack.clear();  
 }

 
 public Object get() {
  if (this.isEmpty()) throw new NoSuchElementException(“Queue is empty”);
        return stack.removeLast();
 }

 
 public boolean isEmpty() {
  return stack.isEmpty();
 }

 
 public void put(Object p) {
  stack.addLast(p);
 }
 
}

PriorityQueue.java:

package search.util;

import java.util.Comparator;
import java.util.NoSuchElementException;

public final class PriorityQueue implements IQueue {

 private ConcatenateList prio = new ConcatenateList();
 
 private Comparator cmp;
 
 public PriorityQueue(Comparator cmp) {
  this.cmp = cmp;
 }

 public void clear() {
  prio.clear();  
 }

 
 public Object get() {
  if (this.isEmpty()) throw new NoSuchElementException(“Queue is empty”);
        return prio.removeFirst();
 }

 
 public boolean isEmpty() {
  return prio.isEmpty();
 }

 
 public void put(Object p) {
  prio.add(p, this.cmp);
 }
}

Aufgabe 3:

numberOfNodes():

public static int numberOfNodes(ITreeNode root) {
     if(root==null){
      return 0;
     } 
     else{
    
            int countNodes = 1;
            for (Iterator iter = root.getChildren().iterator(); iter.hasNext();) {
                ITreeNode child = (ITreeNode) iter.next();
                countNodes += numberOfNodes(child);
            }
            return countNodes;
     }
}

Aufgabe 4:

getPathToGoal():

public static List getPathToGoal(ITreeNode root, Object goalNode) {
        List pathList = null;
     
     if (root == null) {
      return pathList;
     }
     
     if (goalNode.equals(root.getValue())) {
      pathList = new ArrayList();
      pathList.add(goalNode.toString());
      return pathList;
     }
     
        for (Iterator iter = root.getChildren().iterator(); iter.hasNext();) {
            ITreeNode child = (ITreeNode) iter.next();           
            pathList = getPathToGoal(child, goalNode);         
            if (pathList != null) {
             pathList.add(0, root.getValue().toString());
             return pathList;
            }
        }
     
     return pathList;
}

Shannon-Fano in Maple

Hier folgt nun meine Implementierung des Shannon-Fano Algorithmus für Maple, die wir bezüglich unseres Mathematik-Praktikums “Tag7″ programmieren sollten!

Aufgabe 1 (Shannon-Fano)
Implementieren Sie einen Algorithmus zur Shannon-Fano Kodierung und berechnen Sie eine Kodierung für das Beispiel 21.1.

Beispiel 21.1: [[a,41],[b,33],[c,23],[d,25],[e,100]]

Prozedur:

restart:
with(GraphTheory):
with(Logic):
with(networks):

##Aus dem Mapleskript zum Sortieren von Listen!
comp2 :=proc(a::list,b::list)
if a[2] < b[2] then true else false fi;
end:

##Der Graph muss vor der Prozedur initialisiert werden!
global G2:
G2:=Digraph():

########################################################################

##Prozedur Shannon-Fano!
ShaFa:=proc(L::listlist)
global prev, ECKE, KANTE, G2;
local i,j,k,l,v,S,Sl,Sr,hauf1,hauf2,hauf3,hauf4,hauf5;

##Sortierung der Liste!
S := sort( L , comp2);

##Lokale Variablen initialisieren!
hauf1:=0;
hauf2:=0;
hauf3:=0;
hauf4:=0;
hauf5:=0;
Sl:={};
Sr:={};
ECKE:={};
KANTE:={};

##Gesamthäufigkeit von S!
i:=1;
while(i<=nops(S)) do
 hauf1:=hauf1+S[i][2];
 i:=i+1;
od:

##Festlegen einer Grenze für die Häufigkeit, damit Sl und Sr ungefähr die gleiche Häufigkeit haben!
hauf3:=((hauf1/2))+(S[nops(S)][2]/nops(S));

##Algorithmus der S in Sl und Sr überführt!
j:=1;
while(j<=nops(S)) do
 hauf2:=hauf2+S[j][2];
 if(hauf2<=hauf3) then
  Sl:=[op(Sl),S[j]];
 fi;
 if(hauf2>hauf3)then
  Sr:=[op(Sr),S[j]];
 fi;
 j:=j+1;
od:
##Kontrolle ob auch alles funktioniert!
print(S);
print(“linkerTeilbaum:”, Sl);
print(“rechterTeilbaum:”, Sr);

##Gesamthäufigkeit von Sl! Wird beim Erstellen der Ecken und Kanten gebraucht!
k:=1;
while(k<=nops(Sl)) do
 hauf4:=hauf4+Sl[k][2];
 k:=k+1;
od:

##Gesamthäufigkeit von Sr! Wird beim Erstellen der Ecken und Kanten gebraucht!
l:=1;
while(l<=nops(Sr)) do
 hauf5:=hauf5+Sr[l][2];
 l:=l+1;
od:

##Welche Ecken sind in G2 vorhanden!
v:=Vertices(G2);

##Wenn nicht in G2, dann initialisiere die Wurzel!
if not member(hauf1, v) then
 ECKE:=[op(ECKE),hauf1];
fi;

##rechter Teilbaum: Fügt entweder eine endgültige Ecke oder eine weitere Ecke hinzu, an der weitere Ecken folgen können!
if(nops(Sr)=1) then
 ECKE:=[op(ECKE),Sr[1][1]];
 KANTE:=[op(KANTE),[hauf1,Sr[1][1]]];
else
 ECKE:=[op(ECKE), hauf5];
 KANTE:=[op(KANTE),[hauf1,hauf5]];
fi;

##linker Teilbaum: Fügt entweder eine endgültige Ecke oder eine weitere Ecke hinzu, an der weitere Ecken folgen können!
if(nops(Sl)=1) then
 ECKE:=[op(ECKE),Sl[1][1]];
 KANTE:=[op(KANTE),[hauf1,Sl[1][1]]];
else
 ECKE:=[op(ECKE),hauf4];
 KANTE:=[op(KANTE),[hauf1,hauf4]];
fi;

##Kontrolle ob auch alles funktioniert!
print(“Ecken:”,ECKE);
print(“Kanten:”,KANTE);

##Die Ecken und Kanten werden dem Graphen G2 hinzugefügt!
G2:=AddVertex(G2,ECKE);
G2:=AddArc(G2, KANTE);

##rekursiver Aufruf bis Sl und Sr =1 sind!
if(nops(Sr)>1) then ShaFa(Sr); fi;
if(nops(Sl)>1) then ShaFa(Sl); fi;

##Rückgabe des Graphen G2 zum Zeichnen!
return G2;

end:

########################################################################

Aufruf:

S:=ShaFa([[a,41],[b,33],[c,23],[d,25],[e,100]]);

Graphzeichnen:

DrawGraph(S);