TU Wien:Grundzüge der Informatik VU (Blieberger)/Prüfung 2011-01-25

Aus dem Gedächtnis, Punkteangaben sind unsicher:

1. (15P) Zwei Bitfolgen $a[i]$ und $b[i]$ ($i=1..n$) sind gegeben. Die Operation X ist NAND für ungerades $i$, OR für gerades $i$. Geben Sie einen Mealy-Automaten an, der diese Operation für beliebig lange Bitfolgen implementiert.
2. (10P) Ein Eintrag in einem unsortierten Datenfeld mit M Elementen wird gesucht. Wieviele Schritte benötigt
   • der Grover-Algorithmus
   • ein herkömmlicher Algorithmus im Worst Case?
3. (10P) Data Encryption Standard.
   • Welches Konzept wird zur Verschiebung verwendet?
   • Welches Konzept wird zur Ersetzung verwendet?
   • Wie groß sind die Blöcke, in die Daten aufgeteilt werden?
   • Skizzieren Sie die Funktionsweise des DES-Algorithmus!
4. (12P) Sind die folgenden Aussagen in der Pseudoarithmetik der Numerik wahr oder falsch? (Antwort richtig=3P falsch=-1P keine=0P)
   • $a+(b*(c*d))=a+((b*c)*d)$
   • $(a*b)+(c*d)=(b*a)+(c*d)$
   • $a*(b+c)=a*b+a*c$
   • $a+(b+c)=(a+b)+c$
5. (12P) 9 Datenbits sollen mit Hamming-Code übertragen werden.
   • Geben Sie die Formeln zur Berechnung der Prüfbits an!
   • Wie hoch ist die Redundanz?
6. (15P) Beweisen Sie mittels vollständiger Induktion, dass in einem ungerichteten Graphen die doppelte Anzahl der Kanten immer gleich der Summe der Knotengrade ist.
7. (16P) Ist die NAND-Operation eine universelle Operation der boole'schen Algebra mit zwei Eingangsvariablen? Beweisen Sie!