Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » Lösungsvorschlag   (Übersicht)

Dies ist eine alte Version des Dokuments!


Lösungsvorschlag

Aufgabe 1.1: Einfachauswahl-Fragen

a) 4 b) 1 c) 2 d) 1 e) 3 f) 3 g) 1 h) 2 i) 3 j) 4 k) 4

Aufgabe 1.2: Mehrfachauswahl-Fragen

a) 1,4,6,8 b) 1,2,5,6,7

Aufgabe 2: pinboard

 
    #include <dirent.h>
    #include <errno.h>
    #include <signal.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <unistd.h>
    #include <netinet/in.h>
    #include <sys/socket.h>
    #include <sys/stat.h>
    #include <sys/types.h>
    #include <sys/wait.h>
 
    // Konstanten, Hilfsfunktionen
    #define LISTEN_PORT 1952
    #define MAX_CLIENTS 32
    #define MAX_LINE_LEN 1024
    #define MESSAGE_DIR "/Users/killerchicken/klausurdinge"
    static void die(const char message[])
    {
        perror(message); exit(EXIT_FAILURE);
    }
 
    // Funktionsdeklarationen, globale Variablen usw.
 
    static void serve(int clientSock);
    static int show(FILE *tx);
    static int pin(FILE *rx, const char msgTitle[]);
    static void handler(int signal);
    static volatile int processCounter;
    static sigset_t mask, old;
 
    // Funktion main()
 
    int main(int argc, char* argv[]) {
        struct sigaction sa = {
            .sa_flags = SA_RESTART|SA_NOCLDSTOP;
            .sa_handler = handler;
        };
 
        sigemptyset(&sa.sa_mask))
 
 
        (sigaction(SIGCHLD, &sa, NULL)
 
 
 
        sigemptyset(&mask);
        sigemptyset(&old);
        sigaddset(&mask, SIGCHLD);
 
 
 
 
 
    // Socket erstellen und auf Verbindungsannahme vorbereiten
 
        int sock = socket(AF_INET6, SOCK_STREAM, 0);
        if (sock == -1) {
            die("socket");
        }
        struct sockaddr_in6 sin6 = {
            .sin6_family = AF_INET6;
            .sin6_port = htons(LISTEN_PORT);
            .sin6_other = in6addr_any;
        };
 
        if (-1 == bind(sock, (struct sockaddr*)&sin6, sizeof(sin6))) {
            die("bind");
        }
        if (-1 == listen(sock,SOMAXCONN)) {
            die("listen");
        }
 
 
    // Verbindungen annehmen und Kindprozesse starten
 
 
        while (1) {
            int client_sock = accept(sock, NULL, NULL);
            if (-1 == client_sock) {
                die("accept");
            }
 
            sigprocmask(SIG_BLOCK, &block, &old);
            while (processCounter != 32) {
                sigsuspend(&old);
            }
 
            pid_t pid = fork();
            if (pid == -1) {
                die("fork");
            } else if (!pid) {
                sigprocmask(SIG_SETMASK, &old, NULL);
                serve(client_sock);
            }
            processCounter++;
            sigprocmask(SIG_SETMASK, &old, NULL);
            close(client_sock);
        }
        return 0;
    }
    // Ende Funktion main
    // Signalbehandlung für SIGCHLD
 
    static void handler(int signal) {
        int old_errno;
        while(waitpid(-1, NULL, WNOHANG) < 0) {
            processCounter--;
        }
        errno = old_errno;
    }
    // Ende Signalbehandlung
    // Funktion serve()
 
    static void serve(int client_sock) {
        FILE* client = fdopen(client_sock, "r");
        if (!client) {
            perror("fdopen");
            close(client);
            return;
        }
        char befehl[MAX_LINE_LEN + 1];
        if (!fgets(befehl, sizeof(befehl), client)) {
            //perror("fgets");
            close(client);
            return;
        }
        if (ferror(client)) {
            perror("client");
            close(client);
            return;
        }
 
        if (strcmp(befehl, "show") == NULL) {
            show(client);
            fputs(client_sock, "OK");
            fclose(client);
        }
        if (strncmp(befehl, "pin", 3) == NULL) {
            befehl[3] == '\0';
            const char* filename = befehl + 4;
            pin(client, filename);
            fputs(client_sock, "OK");
            fclose(client);
        }
        fputs(client_sock, "Failed!");
        fclose(client);
        return;
    }
    // Ende Funktion serve()
 
    // Funktion show()
    static int show(FILE* tx) {
        DIR* d = opendir(MESSAGE_DIR);
        if (!d) {
            perror("opendir");
            return -1;
        }
        struct dirent* e;
        while(errno = 0, (e = readdir(d)) != NULL) {
            if (e->d_name[0] == '.') {
                continue;
            }
            if (strcmp(e->d_name, ".") == 0) {
                continue;
            }
            char path[strlen(MESSAGE_DIR) + strlen(e->d_name) + 2];
            sprintf(path, "%s/%s", MESSAGE_DIR, e->d_name);
            struct stat s;
            if (-1 == lstat(path, &s)) {
                perror("lstat");
                continue;
            }
            if (S_ISREG(s.st_mode)) {
                errno = 0;
                fputs("== ", tx);
                fputs(e->d_name, tx);
                fputs(" ==\n", tx);
                if (errno != 0) {
                    perror("fputs");
                    continue;
                }
                FILE* c = fopen(path, "r+");
                if (c == NULL) {
                    perror("fopen");
                    continue;
                }
                int ch;
                while ((ch = fgetc(c)) != EOF) {
                    if (fputc(ch, tx) == EOF) {
                        perror("fputc");
                        continue;
                    }
                }
                if (fputc('\n', tx)) {
                    perror("fputc");
                    continue;
                }
                fclose(c);
            }
        }
        if (errno != 0) {
            perror("readdir");
            closedir(d);
            return -1;
        }
        closedir(d);
        return 0;
    }
 
    // Ende Funktion show()
    static int pin(FILE* rx,char* buf){
    char s[MAX_LINE_LENGTH];
    strcpy(s,buf+4);
    if(fgets(buf,MAX_LINE_LENGTH-1,rx)==NULL){
        if(!feof(rx)) return -1;
    }
    if(buf[0]=='.') return -1;
    if(strchr(buf,(int)'/')!=NULL) return -1;
    //createfile and write
    FILE* f;
    if((f=fopen(buf,"w"))==NULL)return -1;
    fprintf(f,buf);
    fflush(f);
    fclose(f);
    return 0;
}
    // Funktion pin()

b)

  const float &Image::operator() (unsigned int i, unsigned int j) const {
    return data[i*width+j];
  }

c)

  Image Filter::derivateX(const Image &input) {
    Image output(input.height, input.width-2);
    for(int y=0;y<input.height;y++) {
      for(int x=1;x<input.width-1;x++) {
        output(y,x-1)=0.5*(input(y,x+1) - input(y,x-1));
      }
    }
    return output;
  }

d)

  Image Filter::laplace(const Image &input) {
    Image output(input.height-2,input.width-2);
    float laplaceFilter[3][3]={{0,1,0},
                                      {1,-4,1},
                                      {0,1,0}};
 
    for(int y=1;y<input.height-1;y++) {
      for(int x=1;x<input.width-1;x++) {
        float newValue=0;
        for(int i=0;i<3;i++) {
          for(int j=0;j<3;j++) {
            newValue+=laplaceFilter[i][j]*input(y-1+i,x-1+j);
          }
        }
        output(y-1,x-1)=newValue;
      }
    }
    return output;
  }

e)

  Image Filter::mean3(const Image &input) {
    Image output(input.height-2,input.width-2);
    Image tmp(input.height,input.width-2);
    float filterX[3]={1/3,1/3,1/3};
    float filterY[3]={1/3,1/3,1/3};
 
    for(int y=0;y<input.height;y++) {
      for(int x=1;x<input.width-1;x++) {
        float newValue=0;
        for(int i=0;i<3;i++) {
          newValue+=filterX[i]*input(y.x-1+i);
        }
        tmp(y,x-1)=newValue;
      }
    }
 
    for(int y=1;y<tmp.height-1;y++) {
      for(int x=0;x<tmp.width;x++) {
        float newValue=0;
        for(int i=0;i<3;i++) {
          newValue+=filterY[i]*tmp(y-1+i.x);
        }
        output(y-1,x)=newValue;
      }
    }
    return output;
  }

Aufgabe 6 (Iterative Loesungsverfahren)

a)

 x1 = [1, 2, 5/2, 2, 1]^T
  

b)

x1 = [1, 2, 3, 3, 2]^T

c)

 Schwaches Zeilen-SummenKriterium (somit schwach diagonaldominant) + unzerlegbare Matrix => Konvergiert
 

Aufgabe 7 (Programmierung: Nichtlineare Optimierung)

a)

  vec2 Optimizer::gradientDescent(const Function &f, const vec2 &x0, int maxIter) {
    vec2 currX=x0;
    for(int i=0;i<maxIter;i++) {
      if(f.gradF(currX).length() < 0.001) {
        break; // Genauigkeit erreicht
      }
      currX = currX + stepLength(f,currX,f.gradF(currX))*f.gradF(currX);
    }
    return currX;
}

b)

  vec2 Optimizer::newton(const Function &f, const vec2 &x0, int maxIter) {
    vec2 currX=x0;
    for(int i=0;i<maxIter;i++) {
      if(f.gradF(currX).length() < 0.001) {
        break; // Genauigkeit erreicht
      }
      currX = currX - f.hessian(currX).inverse()*f.gradF(currX);
    }
    return currX;
  }

c) Falls die Hesse-Matrix nicht positiv definit ist, kann sie im jeweiligen Iterationsdurchlauf durch die EInheitsmatrix ersetzt werden. In diesem Falle geht das Newton-Verfahren in das Gradientenabstiegsverfahren ueber.

Gradientenabstiegsverfahren

Aufgabe 8 (Bezier-Kurven)

a)

Siehe Script

b)

  [-2 0] [2 4] [6 4] [6 0]
     [0 2] [4 4] [6 2]
       [2 3] [5 3]
         [3½ 3]
=> c0..c3=[-2 0] [0 2] [2 3] [3½ 3]
 d0..d3=[3½ 3] [5 3] [6 2] [6 0]

Aufgabe 9 (Faltung)

a)

[ r ] Distributivitaet\\
[ r ] Kommutativitaet\\
[ f ] Denn: Neutrales Element der Faltung zu einer Funktion f ist nicht die Funktion f selbst - neutrales element zur faltung wäre übrigens die dirac funktion\\
[ r ] Assoziativitaet

b) Angabe der Lösung zerlegt in Strecken, wobei P1 (x,y) immer den Startpunkt meint und P2 (x,y) den Endpunkt einer Strecke.
P1 = (0,0) und P2 = (1,0) würde also die Strecke auf der x-Achse meinen von x = 0 bis x = 1 (hoffe das ist verständlich, weil ASCII Bild hier rein is doof)

Lösung:
Strecke0: P1 = (-unendlich, 0) bis P2 = (-1/2, 0)
Strecke1: P1 = (-1/2, 0) bis P2 = (0, 1/2)
Strecke2: P1 = (0, 1/2) bis P2 = (1, -1/2)
Strecke3: P1 = (1, -1/2) bis P2 = (3/2, 0)
Strecke4: P1 = (3/2, 0) bis P2 = (unendlich, 0)

c)
Erklaert an einem Beispiel: http://nt.eit.uni-kl.de/fileadmin/lehre/guet/uebung/faltung.pdf

  1. (keine Überlappung) t < -1: h(x)*h(x)= 0
  2. (Eintrittsphase) -1 ⇐ t <1: h(x)*h(x) = Integral form -2 to t-1 of 1/2 dx = t/2+0.5
  3. (Vollständige Überlappung) 1 ⇐ t < 3: h(x)*h(x) = Integral form t-3 to t-1 of 1/2 dx = 1
  4. (Austrittsphase) 3 ⇐ t < 5: h(x)*h(x) = Integral form t-3 to 2 of 1/2 dx = -t/2 + 5/2
  5. (keine Überlappung) 5 ⇐t: h(x)*h(x) = 0

Aufgabe 10 ( )

1a)

Baryzentrische Koordinaten: (1/4, 1/2, 1/4)

1b)

sigma < 0, rho < 0 --> spitze  Flaeche rechts ueber Punkt T
tau = 1 --> Gerade durch den Punkt T, sodass die Gerade parallel zur Strecke [RS] liegt

1c)

  a:b = beta/alpha
  c:d = (beta+gamma)/alpha
  e:f = gamma/alpha

2)

P: fP = 3.5 
Mittelpunkt: fM = 1/4*(fA+fB+fC+fD) = 7/2