Exam

Institut für Informatik
Prof. Dr. Armin Biere
Dr. Mathias Fleury
Freiburg, 26. Februar 2025

Klausur — Technische Informatik

Bitte prüfen Sie, ob Sie alle Aufgabenblätter erhalten haben und tragen Sie auf allen verwendeten Blättern (auch den zusätzlich ausgeteilten) Ihren Namen und Ihre Matrikelnummer ein. Blätter ohne diese Information werden nicht berücksichtigt.

Das Erreichen von 48 Punkten ist hinreichend zum Bestehen der Klausur.

PRÜFUNGSUNFÄHIGKEIT

Durch den Antritt dieser Prüfung erklären Sie sich für prüfungsfähig. Sollten Sie sich während der Prüfung nicht prüfungsfähig fühlen, können Sie aus gesundheitlichen Gründen auch während der Prüfung von dieser zurücktreten. Bitte informieren Sie in diesem Fall das Aufsichtspersonal, verlassen die Prüfung und gehen unverzüglich zum Arzt. Gemäß den Prüfungsordnungen sind Sie verpflichtet, die für den Rücktritt oder das Versäumnis geltend gemachten Gründe unverzüglich (innerhalb von 3 Tagen) dem Prüfungsamt durch ein Attest mit der Angabe der Symptome schriftlich anzuzeigen und glaubhaft zu machen. Weitere Informationen: https://www.tf.uni-freiburg.de/de/studium-lehre/a-bis-z-studium/ruecktritt-von-pruefungen

TÄUSCHUNG/STÖRUNG

Sofern Sie versuchen, während der Prüfung das Ergebnis ihrer Prüfungsleistung durch Täuschung (Abschreiben von Kommilitonen …) oder Benutzung nicht zugelassener Hilfsmittel (Skript, Mobiltelefon, Spickzettel …) zu beeinflussen, wird die betreffende Prüfungsleistung mit „nicht ausreichend" (5,0) und dem Vermerk Täuschung bewertet. Als Versuch gilt bei schriftlichen Prüfungen und Studienleistungen bereits der Besitz nicht zugelassener Hilfsmittel während und nach der Ausgabe der Prüfungsaufgaben. Sollten Sie den ordnungsgemäßen Ablauf der Prüfung stören, werden Sie vom Prüfer/Aufsichtsführenden von der Fortsetzung der Prüfung ausgeschlossen. Die Prüfung wird mit „nicht ausreichend" (5,0) mit dem Vermerk Störung bewertet.
Weitere Informationen: https://www.tf.uni-freiburg.de/de/studium-lehre/a-bis-z-studium/taeuschung-plagiat-stoerung-bei-einer-pruefung

Die Funktion sei durch ihre ON-Menge gegeben:

Sie können die Kurzform 011- für nutzen.

Bestimmen Sie anhand eines KV-Diagrammes die Primimplikantenmenge von . Füllen Sie dazu zunächst das folgende Diagramm aus:

Geben Sie nun das reduzierte Polynom aller Primimplikanten:

Hinweis: Es wird nach einem KV-Diagramm verlangt! Wenn Sie statt dessen Quine-McCluskey verwenden gibt es keine Punkte!

Ein Mitstudent hat mit dem quienny Programm drei Primimplikanten gefunden aber zwei vergessen abzuschreiben:

Welche zwei Primimplikanten fehlen?

Füllen Sie die Primimplikantentafel aus.

Was sind die wesentlichen Primimplikanten aus dieser Tafel? (Hinweis: 2 Primimplikanten)

Füllen Sie die Primimplikantentafel nach Entfernen der wesentlichen Primimplikanten.

Falls die Tafel leer ist, schreiben Sie einfach "Leer" und begründen Sie kurz. Sonst, was sind die wesentlichen Primimplikanten aus dieser Tafel?

Was ist also das minimale Polynom?

Vervollständigen Sie anhand der Befehlstabelle auf der nächsten Seite folgendes Programm (eine Zahl für jedes _):

Load Befehle —

Für LOADIN1, LOADIN2: , falls .

Store Befehle — MOVE: ,

Compute Befehle —

Jump Befehle —

Kodierung der Register: PC 00 / IN1 01 / IN2 10 / ACC 11

Tabelle 1: Befehlstabelle der ReTI

Betrachten Sie folgende Behauptung:

Beweisen Sie durch Widerspruch, dass dies falsch ist, in dem:

Gegeben sei eine Funktionstabelle für eine Boolesche Funktion. Erklären Sie in ca. 3 Sätzen, wie man daraus ein PLA bestimmt. Wie kann der kleinste PLA ermittelt werden? Bis zu wie vielen Variablen funktioniert solch eine Minimierung?

Intel nutzte für einen Dividierer ein PLA und hatte dabei aber einige Einträge vergessen. Nach Korrektur (und dem Ersetzen von vielen Pentium Prozessoren) war der PLA kleiner. Warum?

Ist ein kleinerer PLA schneller oder langsamer? Warum? Was bedeutet ein kleinerer PLA für die Implementierung der ReTI in Hardware?

Sie wollen eine Chipfirma gründen und haben dafür eine Idee aus der Quantum-Computing Ecke, nämlich Gatter zu nutzen, die reversibel sind. Reversibel bedeutet, dass keine Information verloren geht. Insbesondere bleibt die Anzahl an Einsen '1' exakt gleich in der Ausgabe wie in der Eingabe.

Sie wollen dafür sogenannte "Fredkin-Gatter" nutzen mit 3 Eingaben, einem Kontrollsignal , zwei Inputs und und drei Ausgaben. Das Kontrollsignal wird einfach durchgeleitet. Wenn das Kontrollsignal an ist, d.h. auf '1' gesetzt, dann werden und vertauscht, sonst identisch weitergegeben, d.h. erste (zweite) Ausgabe ist gleich erstem (zweitem) Eingang.

Logisch sind also Fredkin-Gatter definiert durch die drei Ausgaben ( und und ) wie folgt:

Ein Motivation für reversible Berechnung ist das Landauer-Prinzip: Beim Löschen eines Bits an Information wird Energie freigesetzt (). Geben Sie eine Beispielfunktion in Form eines PLAs und eine Eingabe an, bei der Information gelöscht wird.

Eine zweite wichtige Eigenschaft von reversiblen Gattern ist, dass die Anzahl an '1' und '0' im Input und Output gleich bleiben. Geben Sie ein Beispiel eines (nicht-reversiblen) Gatters an, mit der gleichen Anzahl in Inputs und Outputs, zusammen mit einer Eingabe, bei der die Anzahl sich ändert. Woher stammt die Energie in herkömmlichen Gates?

Führen Sie nun die binären Booleschen Funktionen in der untenstehenden Tabelle in geeigneter Weise auf das Fredkin-Gatter, True ('1') oder False ('0') zurück. Im Gegensatz zur ITE-Übung auf Blatt 11 dürfen Sie hier geschachtelte Ausdrücke verwenden, wie .

Geben Sie Informationen und Kommentare an, so dass Ihre Lösung nachvollziehbar wird! Zur Verbesserung der Lesbarkeit dürfen Sie Funktionen benutzen, die Sie zuvor definiert haben. Vergewissern Sie sich aber, keine zyklischen Definitionsketten zu erzeugen!

Hinweis: Schauen Sie zuerst was passiert wenn Sie auf '0' oder '1' setzen.

Die Zehner-Komplement-Darstellung für Zahlen in Basis 10 ohne Nachkommastellen sei analog zur Vorlesung wie folgt definiert (mit ):

Beweisen Sie per Induktion im Detail, dass:

Beweisen Sie anhand obiger Definition der Zehnerkomplement-Darstellung, dass:

Die Addition von ganzen Zehnerkomplementzahlen kann gemäß folgender Formel auf die Subtraktion zurückgeführt werden:

(Diese Frage hat keinen Zusammenhang mit den Fragen a und b.)

Vervollständigen Sie durch Ausfüllen der leeren Felder folgenden Beweis, der zeigen soll, dass bit-weises AND von und (in C wäre das x & (x̃ + 1)) geschrieben als die Anzahl an Einsen in der Zahl [ermittelt].

Hinweis: Rechnen Sie zur Probe mit .

Betrachten Sie den Mealy-Automaten , der durch folgende Zustands- und Ausgangstafel definiert ist:

Dabei ist der aktuelle Zustand und der Folgezustand. Der Startzustand des Mealy-Automaten sei .

Konstruieren Sie ausgehend von diesem Mealy-Automaten ein möglichst kleines Schaltwerk mit dem gleichen sequentiellen Verhalten. Gehen Sie dazu wie folgt vor:

Zeichnen Sie für den oben definierten Mealy-Automaten das entsprechende Zustandsdiagramm.

In der Vorlesung haben wir folgende hinreichende Bedingung gesehen für äquivalente Zustände: Wenn zwei Zustände bei der gleichen Eingabe immer die gleiche Ausgabe liefern und denselben Folgezustand annehmen, dann sind die Zustände äquivalent.

Erklären Sie warum es hier keine Zustände gibt, die diese Bedingung erfüllen würden.

Minimieren Sie den Automaten auf 3 Zustände. Die Zustände , und können gelöscht werden. Zeichnen Sie dazu das Zustandsdiagramm nach der Minimierung.

Wählen Sie nun eine Zustandskodierung für die Zustände im reduzierten Zustandsdiagramm und geben Sie die neue Zustands- und Ausgangstafel an. Verwenden Sie in der Zustands- und Ausgangstafel Ihre Zustandskodierung.