Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » Lösungsvorschlag (Übersicht)
Dies ist eine alte Version des Dokuments!
Inhaltsverzeichnis
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
- (keine Überlappung) t < -1: h(x)*h(x)= 0
- (Eintrittsphase) -1 ⇐ t <1: h(x)*h(x) = Integral form -2 to t-1 of 1/2 dx = t/2+0.5
- (Vollständige Überlappung) 1 ⇐ t < 3: h(x)*h(x) = Integral form t-3 to t-1 of 1/2 dx = 1
- (Austrittsphase) 3 ⇐ t < 5: h(x)*h(x) = Integral form t-3 to 2 of 1/2 dx = -t/2 + 5/2
- (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