00-4

Technische Informatik
Sommersemester 2026
[Name]
Übungsblatt 0
23.04.2026

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

Erledigt, Gruppe 11.

a) Beweis: Für alle Mengen von Größe , gibt es ein minimales Element

Zu beweisende Aussage: : Jede nichtleere Menge mit unter einer partiellen Ordnung enthält ein minimales Element.

Basisfall (): Ist , dann enthält genau ein Element . Dieses Element ist trivialerweise minimal, da es mit sich selbst vergleichbar ist: . Also gilt .

Induktionsvoraussetzung (IV): Für eine beliebige aber feste natürliche Zahl gelte die Aussage : Jede nichtleere Menge mit unter einer partiellen Ordnung enthält ein minimales Element.

Induktionsschritt (von zu ): Sei eine beliebige Menge mit .

Wähle ein beliebiges Element und setze . Dann gilt .

Nach der Induktionsvoraussetzung (IV) enthält ein minimales Element . Es gibt zwei Fälle:

Fall 1: und sind vergleichbar:

Fall 2: und sind nicht vergleichbar: Das Element ist minimal in , da es für alle minimal ist, und mit nicht vergleichbar ist.

In allen Fällen besitzt ein minimales Element. Also gilt .

Schlussfolgerung: Nach dem Prinzip der vollständigen Induktion gilt für alle . ∎

b) Beispiel einer partiellen Ordnung

Ein klassisches Beispiel für eine partielle Ordnung ist die Teilbarkeitsrelation auf den natürlichen Zahlen:

mit wenn teilt (geschrieben als ).

Einige Beispiele:

Minimalelemente dieser Menge: 1 (da für alle )

Dies ist eine partielle Ordnung, da nicht alle Paare vergleichbar sind. Zum Beispiel sind 4 und 6 nicht vergleichbar.

c) Beweis für totale Ordnung und Vergleich

Zu beweisende Aussage für totale Ordnung: In einer totalen Ordnung gibt es für jede nichtleere endliche Menge ein minimales Element.

Definition totale Ordnung: Eine totale Ordnung ist eine partielle Ordnung , bei der zusätzlich gilt:

Das heißt, je zwei Elemente sind vergleichbar.

Beweis durch vollständige Induktion:

Basisfall (): Wie bei 4a): Ist , dann enthält genau ein Element . Dieses Element ist logischerweise minimal, da es mit sich selbst vergleichbar ist: . Also gilt .

Induktionsvoraussetzung: Jede Menge mit hat ein minimales Element.

Induktionsschritt (von zu ): Sei mit . Wähle beliebig und .

Nach IV hat ein minimales Element .

Da die Ordnung total ist, sind und vergleichbar:

Also hat ein Minimum.

Unterschiede zum Beweis in 4a):

Besonderheit der partiellen Ordnung (4a):

Besonderheit der totalen Ordnung (4c):

Der wesentliche Unterschied: In 4c) können wir immer zwischen und vergleichen (garantiert durch Totalität), während wir in 4a) den Fall berücksichtigen müssen, dass sie nicht vergleichbar sind (was für die Minimalität trotzdem ausreicht).

a) Dichte in Transistoren pro mm²

Berechnungen:

b) Größe eines einzelnen Transistors im M1 Ultra

Die durchschnittliche Fläche pro Transistor:

Umrechnung in Nanometer: , also

Unter Annahme eines quadratischen Transistors:

Also ist ein Transistor im M1 Ultra ca. 7368 nm² groß bzw. hat eine Seitenlänge von nm.

c)

Es ist schwierig zu entscheiden, da wir nur so wenige Daten haben. Die 86 nm Größe unterscheidet sich deutlich von den beworbenen 5 nm, aber der Chip enthält verschiedene Komponenten (CPU, GPU, Cache, RAM, etc.) mit unterschiedlichen Transistordichten. Die "5nm"-Bezeichnung bezieht sich wahrscheinlich auf die Prozesstechnologie, nicht auf eine durchschnittliche Transistorgröße.