= Datum der Prüfung
22.07.15

= Benötigte Lernzeit als Empfehlung
1 Woche, wenn man die Übungsblätter lösen konnte und die VL regelmäßig besucht hat

= Verwendete Materialien (Bücher, Skripte etc...)
Übungsaufgaben und Vorlesungsfolien

= Prüfungsfragen

----------------------------------------------------------------------------

AUFGABE 1

Die Zahl 50,3125 (Basis Zehn) in Binärdarstellung (als Festkommazahl
und unter Verwendung des Zweierkomplements) ist 0110 0100 1010.

a) Wie viele Nachkommastellen hat dieses Festkommaformat?
b) Stellen sie die Zahl 9,5 in diesem Format da.
c) Stellen sie die Zahl -29,875 in diesem Format da.
d) Stellen sie die Zahl 50,3125 als IEEE 754 mit einfacher Genauigkeit dar.

----------------------------------------------------------------------------

AUFGABE 2

Im Folgenden sollen sie einen Mux-4 entwerfen, der mit einer Steuerleitung
S(1:0) von vier eingehenden Signalen x(0), x(1), x(2), x(3) eines auswählt.

S = 00  ->  q = x(0)
S = 01  ->  q = x(1)
S = 10  ->  q = x(2)
S = 11  ->  q = x(3)

Dieses Problem soll auf ein kleineres reduziert werden, deshalb soll zunächst
ein Mux-2 entwurfen werden.

Der Mux zwei erhält ein Signal S als Eingabe und wählt zwischen zwei Symbolen
x(0) und x(1) aus.

S = 0  ->  q = x(0)
S = 1  ->  q = x(1)

a) Füllen sie die Tabelle für den Mux-2 aus:

S x0 x1  | q
---------|---
0  0  0  |
0  0  1  |
0  1  0  |
0  1  1  |
1  0  0  |
1  0  1  |
1  1  0  |
1  1  1  |

b) Geben sie eine minimale Schaltfunktion für den Mux-2 an.

c) Entwerfen sie einen Mux-2 (Gatter) und denken sie sich ein Symbol für ihren
Mux-2 aus.

d) Entwerfen sie nun mit Hilfe ihrer Mux-2 Symbole einen Mux-4.

----------------------------------------------------------------------------

AUFGABE 3

Gegeben war ein Schaltwerk (eine Art Shifter).

a) In wenigen Worten: Was tut die Schaltung?

b) Unten sehen sie einen Signalverlauf für die Eingänge A, C und E. Ergänzen sie
die beiden Ausgangssignale X und Y.

c) Wie könnte man die obige Schaltung auch realisieren, wenn keine Flip-Flops mit
Enable zur Verfügung stehen?

----------------------------------------------------------------------------

AUFGABE 4

Gegeben war unsere ALU mit der Funktion

q = ( (s3ab v s2a-b v s1-ab v s0-a-b) <-> (BA v C-1) )

und dem Steuervektor (s3, s2, s1, s0).

Zeigen sie:

Wenn BA = 0 und S = 0110 dann führt die ALU eine Subtraktion aus, also

Q = A - B - 1 + C-1.

Dazu dürfen sie benutzen, dass diese Gleichung auch der folgenden entspricht:

q = (a <-> b <-> c)

----------------------------------------------------------------------------

AUFGABE 5

Ein Computer hat die Folgende Speicherhierarchie:

Cache: 1 Takt, 0.97 Hitrate
RAM: 30 Takte, 0.91 Hitrate
HS: 2 000 000 Takte

Wie viele Takte braucht ein Speicherzugriff durchschnittlich?

----------------------------------------------------------------------------

AUFGABE 6

mov eax, [ebx+8]
add eax, 1
add ebx, 8
mov [ebx], eax

Wie könnte man diese Befehlsfolge alternativ realisieren, wenn registerindizierte
Adressierung nicht zur Verfügung steht. Verwenden sie nicht mehr Befehle als vier.

----------------------------------------------------------------------------

AUFGABE 7

Gegen war unsere Prozessorarchitektur.

a) Schreiben Sie ein Mikroprogramm, was den nächsten Befehl holt und dekodiert.

b) Gegeben ein kurzes Mikroprogramm. Finden Sie heraus, auf welche Art Operand 1
und Operand 2 adressiert werden.

----------------------------------------------------------------------------

AUFGABE 8

Gegeben ein Write-Back Cache, der 4-Wege-Setassoziativ ist und als Ersetzungs-
strategie LRU benutzt.

Der Cache ist 8 Blöcke groß.
Jeder Block ist 4 Byte groß.
Der Hauptspeicher ist 256 Byte (oder so) groß.
(Byteweise adressiert)

a) Wie viele Sets hat der Cache.

b) Welche Bits werden für Steuerinformationen gebraucht?

c) Wie lang ist das Tag.

Die Hauptspeicherbytes haben die Adressen 0, 1, 2, ...
Die Blöcke werden nummeriert 0, 1, 2, ...

d) Gegeben eine Tabelle:

Byte (dezimale Adresse) | Block
--------------------------------
0                       |
--------------------------------
9                       |
--------------------------------
32                      |
--------------------------------
...                     |


In welchem Block (dezimal) liegen die Adressen?

e) Unten zu sehen war der Cache (Tabellarisch). Kennzeichnen sie, welche Cachelines
zu welchem Set gehören und schreiben sie auf, wie der Cache nach den oben genannten
Zugriffen auf den Hauptspeicher aussieht.

Cacheline   Set   Tag (binär)   Block-Nummer (dezimal)

----------------------------------------------------------------------------

AUFGABE 9

Standart Aufgabe zu virtuellen Speicher und Pages.

----------------------------------------------------------------------------

= Note (Optional)
1.3

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Mehr Wissen als Lernen, aber eigentlich gut zu schaffen.
Viele Aufgaben waren angelehnt an die auf den Übungsblättern,
mit der ALU und dem Steuerwerk sollte man sich auch beschäftigt haben :)

hugo.png
Fachschaft Informatik
Humboldt-Universität zu Berlin

    Prüfungsprotokolle
    Lesen
    Erstellen

Navigation

    Hauptseite
    Die Fachschaft
    Erstsemester
    Service
    Kontakt
    Links

Vorhandene Protokolle
Protokolle (5 gefunden)
Nr. 	Prüfer 	Fach
608 	Leser Prof. 	Algorithmen und Datenstrukturen

Protokoll

Datum der Prüfung:
16.7.2013
Benötigte Lernzeit als Empfehlung:
2 Wochen
Aufgaben:
Das Gedächnisprotokoll der Klausur mit allen Aufgaben und dazugehörigen Puntzahlen liegt als .pdf vor. Ich habe keine Möglichkeit gefunden, diese auf eine Fachschaftsseite hochzuladen, deshalb liegt sie vorrübergehend in der Dropbox:

https://www.dropbox.com/s/888q80fnhalseir/Klausurprotokoll.pdf

Falls der Link nicht mehr funktioniert, oder jemand eine bessere Idee als Dropbox hat bitte eine kurze Email an jonas.marasus@cms.hu-berlin.de schicken, dann lade ich die datei anderswo hoch.

Nr. 	Prüfer 	Fach
689 	Reinhardt, Klaus Prof. Dr. 	Algorithmen und Datenstrukturen

Protokoll

= Datum der Prüfung
25.9.14

= Prüfungsfragen

O-Notation
a) Funktionen ordnen (mit Beweis) n^4/(sqrt(n)*log n); 4^(log n) * log n; n^3 -10n^2 +200
b) (ohne Begründung) je eine Funktion angeben, die
- \in o(n^3) und \in klein-Omega(log n^3) ist
- nicht \in Omega(n log n) und nicht \in O(log n) ist
- \in o(n^4) und \in Theta(n^2-\sqrt(n) +10) ist
c) Zeigen oder widerlegen: f \in Theta (g) und g \in o(h) => f \in O(h)

Sortieren
a) Idee von Countingsort erklären
b) entscheiden und begründen, ob b1) Mergesort und b2) Quicksort Vorsortierung ausnutzen
c) Gegeben sei eine Folge a_1,..,a_n. Dabei wird (a_i, a_j) mit i<j, aber a_i>a_j als sog. falsches Paar definiert. Es sollte ein Algorithmus entworfen werden, der in O(n) alle falschen Paare beseitigt, sofern nur O(n) falsche Paare vorliegen (mit Laufzeitbeweis)

BB[alpha]-Bäume
a) in gegebenem BB[alpha]-Baum für alle Knoten die Balancen angeben
b) Sei alpha zwischen 0 und 1/2 gegeben. Was muss binärer Suchbaum erfüllen, um BB[alpha]-Baum zu sein?
c) für 3 verschiedene alpha-Werte entscheiden, ob der Baum aus a) legitimer BB[alpha]-Baum ist

B-Bäume
a) ein Element in einen gegebenen B-Baum einfügen
b) ein Element aus einem gegebenen B-Baum löschen
c) Wann/warum sind B-Bäume AVL- und BB[alpha] vorzuziehen?

Hashing
a) mit linearem Sondieren
b) mit double Hashing
keine weiterführenden Fragen

Schreibtischtest zu Prim, auch ohne weiterführende Fragen

Heaps und Bäume
a) aus gegebener Zahlenfolge nach Algorithmus aus der VL einen maxHeap aufbauen
b) Hier war die Inorder- und die Preorder-Traversierung eines binären Baumes (kein Suchbaum) gegeben und man sollte daraus den Baum auslesen (Pseudocode zu Inorder- und Preorder-Traversierung war mit angegeben)
c) zwei verschiedene Bäume mit derselben Preorder-Traversierung angeben
d) Beweisen oder widerlegen: Wenn Preorder-Traversierung eines binären Suchbaumes vorliegt, lässt sich daraus eindeutig der Baum bestimmen.

Beweisaufgabe zu Bäumen und einem gegebenen Pseudocode-Algorithmus - hatte leider keine Zeit, mich hiermit zu beschäftigen

Graphalgorithmen
Hier war (verbalisiert) ein All-pairs-shortest-path-Algorithmus gegeben, der u. a. Bellman-Ford und Dijkstra als Teilschritte benutzte
a) Schreibtischtest zu gegebenem Graph
b) Laufzeiten der Teilschritte und Gesamtlaufzeit angeben
c) und d) kleinere Beweise zu Zwischenergebnissen des Algorithmus
e) mit Hilfe der Erkenntnisse aus c) und d) Korrektheit des Gesamtalgorithmus zeigen

= Note (Optional)
2.x

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Die Küraufgaben waren zeitlich kaum zu schaffen (letzlich wurden dann aber auch 10 Punkte aus der Wertung rausgenommen). 


Nr. 	Prüfer 	Fach
690 	Reinhardt, Klaus Prof. Dr. 	Algorithmen und Datenstrukturen

Protokoll

= Datum der Prüfung
25.9.14

= Prüfungsfragen

O-Notation
a) Funktionen ordnen (mit Beweis) n^4/(sqrt(n)*log n); 4^(log n) * log n; n^3 -10n^2 +200
b) (ohne Begründung) je eine Funktion angeben, die
- \in o(n^3) und \in klein-Omega(log n^3) ist
- nicht \in Omega(n log n) und nicht \in O(log n) ist
- \in o(n^4) und \in Theta(n^2-\sqrt(n) +10) ist
c) Zeigen oder widerlegen: f \in Theta (g) und g \in o(h) => f \in O(h)

Sortieren
a) Idee von Countingsort erklären
b) entscheiden und begründen, ob b1) Mergesort und b2) Quicksort Vorsortierung ausnutzen
c) Gegeben sei eine Folge a_1,..,a_n. Dabei wird (a_i, a_j) mit i<j, aber a_i>a_j als sog. falsches Paar definiert. Es sollte ein Algorithmus entworfen werden, der in O(n) alle falschen Paare beseitigt, sofern nur O(n) falsche Paare vorliegen (mit Laufzeitbeweis)

BB[alpha]-Bäume
a) in gegebenem BB[alpha]-Baum für alle Knoten die Balancen angeben
b) Sei alpha zwischen 0 und 1/2 gegeben. Was muss binärer Suchbaum erfüllen, um BB[alpha]-Baum zu sein?
c) für 3 verschiedene alpha-Werte entscheiden, ob der Baum aus a) legitimer BB[alpha]-Baum ist

B-Bäume
a) ein Element in einen gegebenen B-Baum einfügen
b) ein Element aus einem gegebenen B-Baum löschen
c) Wann/warum sind B-Bäume AVL- und BB[alpha] vorzuziehen?

Hashing
a) mit linearem Sondieren
b) mit double Hashing
keine weiterführenden Fragen

Schreibtischtest zu Prim, auch ohne weiterführende Fragen

Heaps und Bäume
a) aus gegebener Zahlenfolge nach Algorithmus aus der VL einen maxHeap aufbauen
b) Hier war die Inorder- und die Preorder-Traversierung eines binären Baumes (kein Suchbaum) gegeben und man sollte daraus den Baum auslesen (Pseudocode zu Inorder- und Preorder-Traversierung war mit angegeben)
c) zwei verschiedene Bäume mit derselben Preorder-Traversierung angeben
d) Beweisen oder widerlegen: Wenn Preorder-Traversierung eines binären Suchbaumes vorliegt, lässt sich daraus eindeutig der Baum bestimmen.

Beweisaufgabe zu Bäumen und einem gegebenen Pseudocode-Algorithmus - hatte leider keine Zeit, mich hiermit zu beschäftigen

Graphalgorithmen
Hier war (verbalisiert) ein All-pairs-shortest-path-Algorithmus gegeben, der u. a. Bellman-Ford und Dijkstra als Teilschritte benutzte
a) Schreibtischtest zu gegebenem Graph
b) Laufzeiten der Teilschritte und Gesamtlaufzeit angeben
c) und d) kleinere Beweise zu Zwischenergebnissen des Algorithmus
e) mit Hilfe der Erkenntnisse aus c) und d) Korrektheit des Gesamtalgorithmus zeigen

= Note (Optional)
2.x

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Die Küraufgaben waren zeitlich kaum zu schaffen (letzlich wurden dann aber auch 10 Punkte aus der Wertung rausgenommen). 

Nr. 	Prüfer 	Fach
733 	Leser Prof. 	Algorithmen und Datenstrukturen

Protokoll

= Datum der Prüfung
10.9.15
= Benötigte Lernzeit als Empfehlung
4 Wochen
= Verwendete Materialien (Bücher, Skripte etc...)
Folien aus Vorlesung, Übung, Tutorium; Internet; Ottmann/Widmayer
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
dritter Prüfungsversuch -> starke Nervosität
Leser beginnt mit etwas Smalltalk (Wie läuft das Studium? Warum 2 mal durchgefallen), Beisitzer waren A. Nonym und ein Protokollant, Stift und Papier wird gestellt
Beisitzer sagen nichts
= Prüfungsfragen
Quick Sort --- wie funktioniert es genau? Komplexität von Worst/Average/Best-Case herleiten - kein genauer Beweis aber gut argumentieren können
Merge Sort --- wie funktioniert es genau? Komplexität von Worst/Average/Best-Case herleiten - kein genauer Beweis aber gut argumentieren können
Suchbäume --- Definition, Wie groß?, Kosten von Einfügen/Löschen, wie funktioniert das Löschen
Starke/schwache Zusammenhangskomponenten --- Was ist das? Wie berechnet man das? Kosaraju-Algorithmus ausführen
= Note (Optional)
bestanden ;)
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Die behandelten Themen werden sehr detailliert behandelt, Leser hilft bei Unsicherheiten weiter, Prüfung ist eher schlecht gelaufen

Nr. 	Prüfer 	Fach
734 	A. Nonym,Susanne 	Algorithmen und Datenstrukturen

Protokoll

= Datum der Prüfung
22.07.15

= Benötigte Lernzeit als Empfehlung
1 Woche, wenn man die Übungsblätter lösen konnte und die VL regelmäßig besucht hat

= Verwendete Materialien (Bücher, Skripte etc...)
Übungsaufgaben und Vorlesungsfolien

= Prüfungsfragen

----------------------------------------------------------------------------

AUFGABE 1

Die Zahl 50,3125 (Basis Zehn) in Binärdarstellung (als Festkommazahl
und unter Verwendung des Zweierkomplements) ist 0110 0100 1010.

a) Wie viele Nachkommastellen hat dieses Festkommaformat?
b) Stellen sie die Zahl 9,5 in diesem Format da.
c) Stellen sie die Zahl -29,875 in diesem Format da.
d) Stellen sie die Zahl 50,3125 als IEEE 754 mit einfacher Genauigkeit dar.

----------------------------------------------------------------------------

AUFGABE 2

Im Folgenden sollen sie einen Mux-4 entwerfen, der mit einer Steuerleitung
S(1:0) von vier eingehenden Signalen x(0), x(1), x(2), x(3) eines auswählt.

S = 00  ->  q = x(0)
S = 01  ->  q = x(1)
S = 10  ->  q = x(2)
S = 11  ->  q = x(3)

Dieses Problem soll auf ein kleineres reduziert werden, deshalb soll zunächst
ein Mux-2 entwurfen werden.

Der Mux zwei erhält ein Signal S als Eingabe und wählt zwischen zwei Symbolen
x(0) und x(1) aus.

S = 0  ->  q = x(0)
S = 1  ->  q = x(1)

a) Füllen sie die Tabelle für den Mux-2 aus:

S x0 x1  | q
---------|---
0  0  0  |
0  0  1  |
0  1  0  |
0  1  1  |
1  0  0  |
1  0  1  |
1  1  0  |
1  1  1  |

b) Geben sie eine minimale Schaltfunktion für den Mux-2 an.

c) Entwerfen sie einen Mux-2 (Gatter) und denken sie sich ein Symbol für ihren
Mux-2 aus.

d) Entwerfen sie nun mit Hilfe ihrer Mux-2 Symbole einen Mux-4.

----------------------------------------------------------------------------

AUFGABE 3

Gegeben war ein Schaltwerk (eine Art Shifter).

a) In wenigen Worten: Was tut die Schaltung?

b) Unten sehen sie einen Signalverlauf für die Eingänge A, C und E. Ergänzen sie
die beiden Ausgangssignale X und Y.

c) Wie könnte man die obige Schaltung auch realisieren, wenn keine Flip-Flops mit
Enable zur Verfügung stehen?

----------------------------------------------------------------------------

AUFGABE 4

Gegeben war unsere ALU mit der Funktion

q = ( (s3ab v s2a-b v s1-ab v s0-a-b) <-> (BA v C-1) )

und dem Steuervektor (s3, s2, s1, s0).

Zeigen sie:

Wenn BA = 0 und S = 0110 dann führt die ALU eine Subtraktion aus, also

Q = A - B - 1 + C-1.

Dazu dürfen sie benutzen, dass diese Gleichung auch der folgenden entspricht:

q = (a <-> b <-> c)

----------------------------------------------------------------------------

AUFGABE 5

Ein Computer hat die Folgende Speicherhierarchie:

Cache: 1 Takt, 0.97 Hitrate
RAM: 30 Takte, 0.91 Hitrate
HS: 2 000 000 Takte

Wie viele Takte braucht ein Speicherzugriff durchschnittlich?

----------------------------------------------------------------------------

AUFGABE 6

mov eax, [ebx+8]
add eax, 1
add ebx, 8
mov [ebx], eax

Wie könnte man diese Befehlsfolge alternativ realisieren, wenn registerindizierte
Adressierung nicht zur Verfügung steht. Verwenden sie nicht mehr Befehle als vier.

----------------------------------------------------------------------------

AUFGABE 7

Gegen war unsere Prozessorarchitektur.

a) Schreiben Sie ein Mikroprogramm, was den nächsten Befehl holt und dekodiert.

b) Gegeben ein kurzes Mikroprogramm. Finden Sie heraus, auf welche Art Operand 1
und Operand 2 adressiert werden.

----------------------------------------------------------------------------

AUFGABE 8

Gegeben ein Write-Back Cache, der 4-Wege-Setassoziativ ist und als Ersetzungs-
strategie LRU benutzt.

Der Cache ist 8 Blöcke groß.
Jeder Block ist 4 Byte groß.
Der Hauptspeicher ist 256 Byte (oder so) groß.
(Byteweise adressiert)

a) Wie viele Sets hat der Cache.

b) Welche Bits werden für Steuerinformationen gebraucht?

c) Wie lang ist das Tag.

Die Hauptspeicherbytes haben die Adressen 0, 1, 2, ...
Die Blöcke werden nummeriert 0, 1, 2, ...

d) Gegeben eine Tabelle:

Byte (dezimale Adresse) | Block
--------------------------------
0                       |
--------------------------------
9                       |
--------------------------------
32                      |
--------------------------------
...                     |


In welchem Block (dezimal) liegen die Adressen?

e) Unten zu sehen war der Cache (Tabellarisch). Kennzeichnen sie, welche Cachelines
zu welchem Set gehören und schreiben sie auf, wie der Cache nach den oben genannten
Zugriffen auf den Hauptspeicher aussieht.

Cacheline   Set   Tag (binär)   Block-Nummer (dezimal)

----------------------------------------------------------------------------

AUFGABE 9

Standart Aufgabe zu virtuellen Speicher und Pages.

----------------------------------------------------------------------------

= Note (Optional)
1.3

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Mehr Wissen als Lernen, aber eigentlich gut zu schaffen.
Viele Aufgaben waren angelehnt an die auf den Übungsblättern,
mit der ALU und dem Steuerwerk sollte man sich auch beschäftigt haben :)

    Datenschutz Über Fachschaft Informatik Impressum