Blatt01

Page 1

Professur für Rechnerarchitektur
Prof. Dr. Armin Biere
Dr. Mathias Fleury
Freiburg, 24. April 2026
Technische Informatik

Übungsblatt 1

Aufgabe 1 (KI/Pflicht Punkte)

Bitte ankreuzen welches von beiden Punkte passt:

□ Ich habe die Aufgaben selbst versucht zu lösen und möchte ein Korrektur

  • a) mir ist bewusst, dass signifikante Bearbeitung reicht zum Bestehen des Blatts
  • b) mir ist bewusst, dass ich vielleicht trotzdem Vorrechnung muss (ohne meine Notizen!)

□ Ich habe irgendwann die KI gefragt und einfach abgeschrieben. In diesem Fall:

  • a) muss ich alle Aufgaben abgeben, das reicht zum Bestehen dieses Blatts
  • b) mir ist bewusst, dass ich keine Korrektur bekommen werde
  • c) mir ist bewusst, dass ich vielleicht trotzdem Vorrechnung muss (ohne meine Notizen!)

Die Bewertung passiert nur wenn die Aufgabe beantwortet wurde.

Vorgeschlagenes Lesethema der Woche: Was passiert wenn Hardware nicht korrekt ist, aber nur manchmal? https://tech.ahrefs.com/skylake-bug-a-detective-story-ab1ad2beddcd

Aufgabe 2 (1 + 3 + 7 Punkte)

a)

Das Prinzip der Dualität für boolesche Algebren besagt:

Gilt eine aus den Gesetzen der booleschen Algebra abgeleitete Gleichung , so gilt auch die zu duale Gleichung, die aus durch gleichzeitiges Vertauschen von und , sowie und hervorgeht.

Warum gilt dieses Prinzip? Begründen Sie das Prinzip zunächst für den Fall, dass die Gleichung weder noch enthält. Wieso lässt sich das Prinzip auch auf den Fall erweitern, dass bzw. enthält?

Page 2

b)

Auf sei eine boolesche Algebra mit den booleschen Operatoren , und definiert. Die Symbole und bezeichnen hierbei die üblichen Operatoren auf ganzen Zahlen ():

Zeigen Sie formal, dass die folgenden in der Vorlesung vorgestellten Axiome einer booleschen Algebra erfüllt:

i) Absorption

ii) Komplementregel

Benutzen Sie dabei ausschließlich die obigen Operatordefinitionen und Rechenregeln aus , gehen Sie formal vor und nicht über Tabellen wie in der Vorlesung.

Hinweise:

  • Führen Sie (für jedes Axiom eine) Fallunterscheidung durch.
  • Das Prinzip der Dualität darf für Aufgabenteil b) nicht verwendet werden.

Aufgabe 3 (3 + 3 Punkte)

In der Informatik verwendet man zur Beschreibung des "asymptotischen Wachstumsverhaltens" von Funktionen über (den nicht-negativen reellen Zahlen) die sogenannte O-Notation. Die O-Notation wird verwendet, um die Größe von parametrisierten Objekten, die Laufzeit von Algorithmen (Anzahl von Rechenschritten in Abhängigkeit von der Eingabelänge) usw. asymptotisch, d.h. bis auf eine multiplikative Konstante , abzuschätzen. Hierbei interessiert man sich nur für die "großen Werte" aus der Definitionsmenge von , d.h. für gewisse Konstanten interessiert man sich nicht für das Verhalten auf Anfangsbereichen der Definitionsmenge .

Die O-Notation ist exakt wie folgt definiert:

Seien . Man schreibt

wenn es ein und ein gibt, so dass für alle gilt.

Beispiel:

Beweis: Setze , .

ü

Page 3

Anmerkung: Die Notation ist weit verbreitet, aber eigentlich falsch, da eine Menge ist. So folgt aus und keinesfalls !

Geben Sie mit Begründung/Berechnung an, für welche der folgenden Paare von Funktionen , welche der Eigenschaften und/oder gelten.

a)

b)

Hinweis: Für diese Aufgabe dürfen Sie Folgendes (unbewiesen) verwenden:

Aufgabe 4 (3 + 1 Punkte)

In der Vorlesung wurden Bäume als Graphen definiert, wo der Ausgangsgrad kleiner als 2 sein muss. Es gibt jedoch eine alternative rekursive Definition. Ein Binärbaum ist dann:

  • entweder ein Blatt (Basisfall),
  • oder ein Knoten mit einem oder zwei Kindern (rekursiver Fall).

a)

Beweisen Sie durch Induktion über die Baumstruktur, dass ein Binärbaum höchstens Knoten besitzen kann, wobei die Höhe – also die maximale Länge von der Wurzel bis zu einem Blatt – bezeichnet.

b)

Wenn Sie den Beweis mit der Definition aus der Vorlesung führen, worüber müssten Sie dann induzieren?

Abgabe: 1. Mai 2026, 1600 über Ilias