Angewandte Informatik

Herzlich willkommen bei meinen "tollen" Notitzen zu meinem Studium.

Das ding hier wird mit mdbook generiert, dazu nutze ich mdbook-katex als Preprozessor um KaTeX Kram zu rendern und mdbook-mermaid um Mermaid-Diagramme anzuzeigen.

Zusammengebaut wird das dann mit nix-shell in einer Gitlab-Pipeline.

Viel Spaß!

Copyright Tobias Rempe. Alle Rechte vorbehalten.
Achja, und die jeweilligen Profs, wenn ich einzelne Folien, Abbildungen oder Zitate einbinde :).

Impressum: zyonic.de/impressum
Urheberrechtsansprüche bitte an tobias.rempe(at)rub.de.

Informatik 2

Prof. Dr. Maike Buchin
SS2024

01 Informatik Br(Z)wei: Grundlagen II

Wir schauen uns in diesem Modul Algorithmen und Datenstrukturen an, damit wir schön sachen modellieren können
Heute geht es um Laufzeit und Korrektheit
Wir reden über "tolle" Laufzeiten
Das ist wie immer super toll

Laufzeiten

Wenn wir die Laufzeit von etwas ermitteln wollen, dann machen wir das immer in einigen Schritten.
- Wir schauen uns erstmal die Anzahl an elementaren Operationen an
  - Wat dat? Variablenzuweisungen, $a + b$ , conditionals
- dann versuchen wir zu ermitteln ob die Laufzeit sich einer änderung der Eingabegröße verändert
- Wir finden solche sachen am besten mit der Asymptotischen Notation heraus
- Wie Sieht das dann aus?:
- time(I) = \text{# Rechenschnritte eines Algorithmus auf einer Eingabe } I
- Analyse im Schlechtesten Fall:
  $T (n) = max {t im e (I) ∣ s i ze (I) = n}$
- Alternativ:
  - Analyse im besten Fall:
    $T (n) = min {t im e (I) ∣ s i ze (I) = n}$
  - Analyse im mittleren Fall:
    $T (n) = \frac{1}{∣ { I ∣ s i ze ( I ) = n } ∣} {I ∣ s i ze (I) = n} \sum t im e (I)$
- All das gilt nur, solange die Menge (dat in den Mengenklammern) endlich ist
- Im allgemeinen betrachten wir die Warscheinlichkeitsverteilung über den Eingaben
Am ende des tages wollen wir sehr schöne dinge modellieren, mithilfe von diesen sehr schönen Laufzeiten:

Begriff	Erklärung
Invariante	Eigenschaften die vor jedem Durchlauf gelten
Initialisierung	Eigenschaften die vor dem Ersten durchlauf gelten müssen. Danach können sie weiterhin gelten, müssen dies aber nicht zwingend
Aufrechterhaltung	Wenn etwas vor einem Durchlauf gilt, dann gilt das auch danach, Die Aufrechterhaltung kümmert sich darum, dass der Loop weiter loopen kann
Terminierung	Die Terminierung beschreibt die Bedingung die erfüllt werden muss, damit die Expression Terminiert werden kann. Diese folgt i.d.R. aus der Invarianten der letzten, vorhergehenden Iteration

Info 2 version 3

Was auch immer Buchin sagt

Binäre Suche

Naja wir suchen mit dem "Teile und Herrsche" Konzpet
- Wir teilen das Array was wir duchsuchen wollen auf und durchsuchen die teile weiter rekursiv
- :)
  semmup
Jetzt analysieren wir den kram
Algorithmenanalyse
- Wir können die Laufzeit vin rekursiven Algos als "Rekurrenz" formulieren
- Wir stellen unsere Rekurrenz auf, da müssen wir auch berücksichtigen wie die Rekursivität der Funktion funktioniert
- Im Fall der Binären suche können wir T(n) \leq T(\lceiln/2\rceil) + O(1) sagen, denn jeder weitere Rekursive Aufruf hat die Hälfte der Daten von dem Aufruf davor
- Das Mastertheorem ist ein "Kochrezept" von rekurrenzen

Analyse im Mittleren Fall

Wir wollen schauen was "durchschnittlich" passiert
Wir interessieren uns in der regel für den "Worst Case", weil dann kann ja alles andere nur noch besser werden

Amortisierte Analyse

Jede Operation hat "kosten"
Diese kosten drücken aus, wie lange etwas zum laufen braucht
Die konkrete Frage ist dann: Was sind die Kosten für $m$ Operationen

Beispiel

Wir implementeren einen Zähler

Wir wissen, dass eine inkrementierung $O (1)$ Kostet

Wenn wir uns den Zähler anschauen merken wir, dass alle Zustände gleich warscheinlich sind, da der Zähler ja alle zustände durchläuft wenn er von 0000 bis 1111 zählt

Randomisierten Algorithmen

Es gibt zwei arten
- Las Vegas: Die Laufzeit hängt vom zufall ab, das Ergebnis nicht
Minte-Carlo-Algorithmen
- Das Ergebnis hängt vom Zufall ab, die Laufzeit nicht

Graphen

Mit graphen kann man die Beziehungen zwischen Objekten darstellen
Graphen werden in vielen Konzepten benutzt, und bilden somit eine Grundlage für diesen Kram

Wasn das?

Ein Graph ist immer eine Menge $G = (V, E)$ Mit knoten V (Verticy) und Kanten E (Edge)
Ein Baum ist dann ein ungerichteter Graph, in dem es Zwischen zwei beliebigen Knoten jeweils genau einen weg gibt
- Das bedeutet, dass es von jedem knoten zu jedem anderen knoten einen weg gibt, und somit jeder Knoten von jedem anderen Knoten erreichbar ist, wenn man jeden weg nutzen kann
- Es gibt da mehrere Arten von Knoten
  - Wurzel: Da wo alles losgeht
  - Innere Knoten sind die, die weitere Kinder haben
  - Blätter sind die, die keine Kinder haben

Polynominielle und Non-Polynomielle Laufzeit

Ein Algorithmus mit polynomieller Laufzeit (oder auch $P$ Laufzeit) heißt effizient;
Zeume sagt hi
- Es gibt keine Effizienten Algorithmen für manche Probleme

Schminfo II: Arrays und Listen

WAsn los?

Wir brauchen datenstrukturen mit denen wir gut und günstig Daten organisieren können
Die Antiken kulturen haben laut Buchin auch schon arrays und Listen genutzt, zwar auf steintafeln oder so, aber ich weiss nicht: der compiler war bestimmt interessant

Spezifikation

Wir wollen Objekte in einer Numerierten Liste abspeichern
- Da soll man wieder daten rein und raus lesen können
- Das soll alles möglichst effizient laufen
Unterschiede:
- statisch vs. dynamisch
- beschränkt vs. unbeschränkt

LiNkeD LiSt!!!!!

Die haben so knoten
die knoten sind anneinander gehangne
in diesen Knoten sind zwei simple sachen gespeichert
- Inhalt
- Der Pointer zum nachfolgeknoten
  - Wenns keinen nachfolger gibt, dann pointen wir ins narnia, auch bekannt als "nullpointerexception thown in 0x993a492f938d74e892"
Es gibt mehrere "Simple" Implementationen von den dingern
- Man kann praktisch einen ewigen Loop mahen, indem man den ersten Knoten mit einem "Dummy-Knoten" ersetzt
- Wenn man dann einfach etwas hinzufügt und in den nullpointer runnen würde, landet man einfach wieder beim Dummy-Knoten! BOAH WIE BRILLIANT ICH KANN DAS FAST ALLES NICHT MEHR GLAUBEN ICH BIN JA SO ERSTAUNT
- Der Vorteil daran ist, dass man das Relativ einfach modifizieren kann usw.
Um sachen aus der Liste zu löschen muss man einfach nur die pointer neu setzen, was halt schön einfach ist, weils einfach Variablen von konstanter größe sind, deswegen läuft der kram auch in konstanter Zeit
Leider kann man in einer verketteten Liste leider nicht direkt auf Element 9203748243 zugreifen, sondern man muss sich halt ein wenig "durchhangeln"

Operationen

Wir wollen dass man kram
einfügne
löschen
und suchen kann
und das man nen paar safety checks wie größe und und "isEmpty" abfragen kann.
Die kosten sollen so laufen
- Einfügen soll $O (1)$ kosten
- Suchen dann halt $O (n)$ wobei $n = l e n g h t$

Arrays

Naja diese komische Tabelle die man halt so hat
Normalerweise fangen die dinger einfach mit 0 an
- ausser man heisst Lua, oder buchin, some of the time
- In der vorlesung fangen wir einfach da an was gerade passt, also 0 oder 1, das ist aber hart doof weil das massiv unübersichtlich ist und alles nur für verwirrung sorgt
In beschränkten arrays hängen die Kosten davon ab, ob der kram sortiert ist oder nicht
wenn das unsortiert ist, ist das Price-to-Performance Ratio meisstens schlechter
Häufig sind unbeschränkte arrays wünschenswert, aber die gibt es nicht, wenn man nciht gerade eine komische dynamische programmiersprache ist oder natürlich T-Script ist.
Man kann unbeschränkte Arrays mit beschränkten arrays "emulieren", indem man den kram halt immer in größere oder kleinere arrays überschreibt usw.
Das ist lustig, weil man dann sehr viel code extra schreiben muss dafür, aber das ist dann halt lustig
- Die kosten dafür sind aber nen bissl doof, denn wenn man
  - Verdoppelt: $O (n \cdot n)$
  - Halbiert: $O (n \cdot n)$

Operationen

Arrays können ja klassisch
- Einfügen
- Löschen
- Lookup by Index
- Größe und isEmpty usw. abfragn
Das jostet:
- Aufruf mit Index $O (1)$
- Einfügen auch $O (1)$ wenns unsortiert ist, in sortierten arrays dann $O (n)$ weil man ja dann die restlichen tiele immer wieder neu sortieren muss bzw. dann halt passend einfügen muss

Amortisierte Analyse

wenn man das "Halbieren und verdoppeln" betrachtet, sieht man dass das sehr teuer ist.
wenn wir aber nicht so viele Jetons ausgben wollen, kann man sich bewusst machen, dass das ja nicht so soft passiert, weil das ja am ende einfach immernoch relativ selten passiert

Wir nutzen jeztt dann hier unter umständen die "Bankkontomethode"

We enter: Jetons
Die idee sieht so aus
- Wir haben ein Bankkonto
- auf dieses Bankkonto zahlen wir mit manchen operationen jetons ein
- andere operationen können dann jetons abheben um schlimme sachen zu bezahlen: wie z.b. Bogo-Sort

Beispiel

Wir schauen uns da mal anhand von dem tollen k-bit binärzähler an
Was wir jetzt machen:
- Wir legen uns neben jede eins einen jeton
  - Das ist okay, weil wir ja immer nur eine eins pro operation schreiben
  - Das ist gut, weil wir diese "angesparten" Jetons dann nutzen können, um die wieder zu nullen zu machen, wenn wir das dann irgendwann unweigerlich machen wollen
Wir müssen jetzt duese Invariante dann so zeigen
- Jeder bit der auf 1 steht ist ein Jeton Guthaben
- jeden bit den wir von 0 auf 1 flippen kostet diesen Jeton Guthaben
- So können wir nie weniger als 0 einsen haben, was toll ist
- wenn wir also eine 0 zu einer 1 machen, "belohnen" wir das mit Jetons
Wir haben bei jeder operation kosten, aber nur das was wirklich "schlimm" ist berechnen wir irgendwie

Zurück zu den arrays

Wir fragen uns wieder, was $m$ Operationen kosten
Das wollen wir uns wieder krass überlegen, und das machen wir dann am besten mit der "tollen" bankkontomethode, damit wir weiterhin alles mit unserer lieblingswärung: Jetons tracken können, denn das macht das ja alles so viel einfacher und spaßiger
wenn wir hier die bankkonto methode nutzen, dann sind die operationen das hier:
- Einfügen ist +2 Jetons
- Löschen ist -1 Jeton
- Kopieren pro eintrag dann auch -1 Jeton
So sichern wir, dass wir immer genug jetons zum Kopieren haben

Stack, Queue und Deque

Wir haben nen stapel, das halt so LIFO
Dann gibts ne Queue, die macht das FIFO
Und dann gibts Deque, oder wie Bauchin sagt: Dequeue, da kann man auf beiden seiten was einfügen und ausbauen

Info Schmei 2: Sortieren

Wir wollen öfter mal kram sortieren
wenn wir kram sortieren müssen wir das mit irgendeiner tollen struktor / einem Algorigthmus machen

Wasn sortieren eigentlich

Wir haben eine beliebig große Menge an Einträgen von beliebiger größe
Wenn wir diese Mege von, sagen wir mal, Zahlen sortieren wollen müssen wir erst etablieren
Was die erwünschte reihenfolge ist
Mit dieser reihenfolge haben wir dann unser ziel zu dem wir sortieren wollen.
Dieser Eintrag (bzw. die Zahl) kann auch Index sein, mit dem man Kram sortieren kann, anstelle davon einfach alleine zu stehen
[We <3 Seni]
Anhand dieser Indizes kann man dann auch sortieren und oder suchen (haha was nen wunder)

Was gibts denn für Sortierverfahren

Selection Sort
- Wir suchen uns den kleinsten Eintrag der Eingabefolge und verschieben den in die Ausgabefolge
- Und das wiederholen wir bis die Eingabefolge leer ist
- Laufzeit:
Insertion Sort
- schieben den ersten wert der Eingabefolge an die irchtige stelle in der Ausgabe (vor / nach einem bestimmten wert)
- Wiederholen bis die Eingabefolge leer ist
- Laufzeit: Anzahl der Vergleiche $\geq$
- Invariante: die Ausgabefolge enthält vor dem $i$ -ten Durchlauf die $i - 1$ ersten Elemente der Eingabe sortiert.
Mergesort
- Teile und herrsche algorithmus
- Wir teilen unsere eigabe in zwei gleich große teile
- Wir sortieren so lange rekursiv, bis wir nicht mehr sortieren / teilen können
- dann fügen wir am ende die dinger sortiert wieder zusammen
  - Das machen wir am Effizientesten wenn wir
  - in dem wir immer den kleinsten der folge nehmen und anfügen
- Laufzeit:
Quicksort
- Wir suchen uns ein beliebiges Pivot-Element (PIVOOOOOOO)
- Dann vergleichen wir jedes element damit, und sortieren kleinere nach links, größere nach rechts.
- Das machen wir dann rekursiv soooooo oft, bis alles implizit sortiert ist.
- Das cool, weil man kann quicksort gut threaden und damit schneller machen

Wie messen wir Algorithmen

Untere Schranke

Algorithmen liefern obere Schranken
Denn wir können relativ einfach, das worst case etablieren
Z.b. Sortieren von $n$ Objektne passiert in $O (n l o g n)$
Die frage ist: Kann man denn überhaupt besser as in $O (n)$ Zeit agieren
- nein, wenn der Algorithmus auf vergleichen aufbaut
- ja, wenn der das nicht tut
Da stellt sich die Frage, wasn dasn eig?
Naja ein vergleichsbasierter Algorithmus darf nur vergleichen, verschieben, und kopieren.
- Das was dabei rauskommt können wir auch "sortierte Permutation" der Eingabe nennen
- Deterministische Vergleichsbarsierte Algorithmen kann man als binary search-trees darstellen
- Wir haben halt den baum, und da entscheiden wir mit rechts oder links, ob das was wir suchen kleiner oder größer als der Derzeitige Knoten ist.
- Wenn wir das alles dann durchmodellerien, haben wir dann einfach "tolle" schlüssel in den blättern
- Wir können so dann aber auch etablieren, dass jeder vergleichsbasierte Sortieralgorithmus im schlechtesten fall $n l o g n - O (n)$ Vergleiche.
- Satz 5.6. Die erwartete Anzahl $C (n)$ von Vergleichen die Quiclsort auf Eingaben mit $n$ einträgen ausführt, erfüllt $C (n) = O (n l o g n)$

06 Schminfo II Vorlesung 7

Wir sortieren sortierten kram und sortieren weiter mit sortiertem kram

Berechnen der Unteren schranke

Gibt es Algos die schnell sind und vllt nicht vergleichsbasiert sind?
Halt dinge die einfach die Struktur der Eingabe Nutzen anstelle sich durchzukämpfen

Wat gibts denn da für algos?

KSort

Wir haben schlüssel, und die sind kleine natürliche Zahlen
Wir nutzen ein Arra von anfangs leeren Behältern
Wenn wir etwas eingeben sortieren wir das dann direkt in den Behälter mit dem passenden Index ein
Am ende hängen wir alle behälter (buckets) direkt aneinander
Dann haben wir den kram erstmal so definiert, und soweit sortiert, dass die richtig "geordnet" sind
Laufzeit:

Radixsort

Wir nehmen KSort als Baustein um größere Schlüssel zu sortieren.
Annahme: Schlüssel haben bis zu $d$ Ziffern,
Ansatz: Wir wenden dann KSort auf alle $d$ Ziffern an.
Sprich, wir sortieren erst nach zahlen der 1. stelle, dann der 2. stelle etc.
§%37%§

LSD-Edition Radix Sort (LSD-RadixSort)

Wir nehmen einfach Radix-Sort, und sortieren von hinten, also letzte stelle der zahl, dann vorletzte etc.
Korrektheit folgt aus KSort
§%21%§

MSD-Radix-Sort

Wir machen das anhand der größten Ziffer, und dann sortieren wir inenrhalb der behälter mit einem genaueren, langsamen algo
Das kann aber dazu führen, dass unser kram am ende langsam(er) wird, und das dann deswegen irgendwie problematisch wird

08 Info 2 Toll yeah BAIHdahsudhuiashfuiasdf

Prioritätswarteschlange

Wir machen kram und wenn wir sachen prioritätsmässig sammeln wollen
Wir machen kram mit prioritätswarteschlangen
- Dat sind warteschlangen, mit priorität
Die dinger haben einige krasse funktionen
- build in O(n)
- insert, deleteMin in O(log n), im best case O(1)
- heapSort zur sortierung in O(n log n)
Addressierbare Binärheaps sind auch krass

Sortierte Folgen

Wir haben eine menge von Objekten mit schlüsseln
Diese dinge kommen aus einem geordneten universum
Wir wollen den kram sortiert machen
Wir wollen eine Datenstruktur die das macht
Naja sortieren kann man dann halt tun
- Wir können nach dem kleinsten schlüssel == gesuchtem key suchen
- wir können sachen inserten
- Wir können sachen löschen

Binary Search Tree

Naja das ist nen Baum
Mit dem kann man Suchen
- links kleiner gleich, rechts größer als der derzeitige
Der baum Pointed auf eine doubly linked list
Es gibt verschiedene arten von Bäumen
- (a, b)-Bäume
  - Kranke tolle grade
- Rot-Schwarz-Bäume
  - Baumrotationen
- AVL-Bäume
  - Baumrotationen
wenn wir einen krassen baum haben der a, b ist, kann man sagen, dass ein baum eine gewisse höhe hat (a) und gewisse anzahl von knoten (b)
lol schau in vl10

10

11 Infobratik 2: Hashing

Motivation

Wir sollen wie immer komisch motiviert werden
Ich weiss nicht zu was das führen soll
Scheinbar gibt es das Szenario öfter, dass wir daten anhand von einem numerischen Schlüssel abspeichern und dann suchen
Beispielsweise
- Die doofen Studis mit ner Matrikelnummer
- Menschen mit IDs
- Bürger einer Stadt mit Ausweisnummer (hold up, da sind Buchstaben drin)
Leider ist unsere Schlüsselmenge gerade ein bissl zu groß
- Wir können die also dann auch verringern

Danzer sagt, dass das Intuitiv ist:

Wir nehmen eine kleinere schlüsselmenge und bilden die ab und versuchen gleichzeitig Kollisionen zu vermeiden.
Beispiel: Die unibib will aus dem Archiv bestellte Bücher in Regalfächern nach der Matrikelnummer bereitstellen.

Hashtabellen

Operationen sind breus
Hashtabellen implementieren halt das Dictionary (jedenfalls nennt glasi das so)
Mir wird zugeflüstert, dass man das auf Deutsch auch "assoziatives Array" nennt, noch nie gehört ehrlich gesagt
Die dinger haben ein paar (mehr oder weniger) sinnvolle operationen
- aufbauen
- einfügen
- löschen
- suchen
Zum vergleich:
- Queues erlauben nur insert und deleteMin (also älteste element löschen)
- Sortierte Folgen erlauben locate, insert und delete
Wir brauchen also $O (n)$ Platzbedarf und verarbeiten alles idealerweise in $O (1)$ Zeit.
Wir betrachten die Menge $S$ von Eintragen mit Schlüsseln $k ey (e) \in Key$
- Am ende nutzen wir eine Hashfunktion
  - Wenn wir was reinwerfen kriegen wir den hash (also ne Zahl in diesem fall) raus
- Und die hashtabelle (dat einfach nen Array)
Leider können in diesem Approach immernoch Elemente / indizes Kollidieren, was es zu vermeiden gilt
Daher müssen wir uns dafür eine Alternative Ausdenken
Hier können wir ein "Tolles" beispiel sehen, wie man hashtabellen anwenden kann
leichzeitig können wir aber auch sehen, wie "einfach" kollisionen passieren können
Dementsprechend suchen wir jetzt ein paar wege mit denen man Kollissionen vermeiden / umgehen kann
Dafür gibt es verschiedene Lösungsansätze
- Hashing mit Verketting
- Hashing mit offener Addressierung (in der VL stehen hier noch die englischen namen, aber ich glaube ihr seit schlau genug, dass ihr das auch so kapiert weil naja, englisch ist irgenwie nen requirement)
Gleichzeitig müssen wir uns überlegen welche Hashfunktion am besten passt
- Passt für unsere Anwendung besser eine einfache, aber individuelle
- oder eine (warscheinlich kompliziertere) universelle Hashfunktion

Hashing mit Verkettung

Wenn wir bei jedem Index, also jeder Zelle in der Hashtabelle eine Verkettete Liste speichern, können wir mehrere sachen auf einmal speichern, die den selben Hashwert haben
Jedes element $e$ wird dann dementsprechend in der Liste in $t [h (e)]$ gespeichert.
Das ding hat dann logischer weise auch wieder einige operationen
- Find
- remove
- insert
- build
Alle "access" funktionen durchsuchen die Folge
Da stellt sich die Frage, ob es Hashfunktionen geben kann, die eine Kleine bzw. kurze Liste garantieren
- Leider gibt es das nicht, da wir nicht garantieren können, dass der "letzte" schlüssel gegrabbled wird
Wie(so) ist Hashibg dabb immernoch effizient?
Dafür haben wir verschieden Ansätze
- Durchschnittsanalyse
- Randomisierung
- Perfektes Hashing für statische Schlüsselmenge

Durchschnittsanalyse

Wir folgern, dass wir linearen Platzbedarf und konstante erwartete Ausführungzeiten der Operationen durch $m = Θ (n)$ erreichen.
Dabei passen wir dann die Tabellengröße an, so wie wir das schon bei unbeschränkten arrays gesehen haben

Universelle Hashfunktionen

Die sollen so viele verschiede Themenbereiche wie möglich abdecken, und das am besten auch noch möglichst effizient machen.
Für Mehr infos einfach VL 12 Folien 43-60 anstarren :)

Hashing II

Hashing mit liearem Sondieren

Wir nutzen einfach die hashfunktion als "sortierverfahren"
Wenn eine Zelle schon voll ist, dann schauen wir, ob wir in die zelle danach rutschen können
So entstehen dann blöcke, und dann können wir da "einfacher" finden
Wenn wir dann etwas aus der Map löschen wollen, und dann am ende irgendwas fehlt, können wir diese "blöcke" wieder zusammenschieben und damit dann lücken füllen

Vergleich

Naja wenn wir das dann vergleichen, haben wir ein paar "lustige" erkentnisse
Hashing mit verkettung braucht einen Extra zeiger, aber wir wissen, dass jeder index auch wirklich auf seinen Wert zeigt
Beim linearen Sondieren, ist das leider nicht so, allerdings brauchen wir keine zusätzlichen speichersegmente und nutzen den gegebenen Speicherplatz effizienter.
Dazu kommt dann aber leider nochm, dass wir durch die "enge" packung eine höhere Suchdauer haben
Wenn wir aber das "beste" in einer bestimmten Situation brauchen, müssen wir uns eine "Perfekte Hashfunktion" basteln

Perfektes Hashing

Wenn wir unsere bisherigen verfahren anschauen, garantieren die alle "nur" erwartete Laufzeiten in $O (1)$ . Leider reicht das aber nicht immer aus
Hier kommen perfekte hashfunktionen ins spiel.
Eine Hashfunktion nennen wir "perfekt", wenn sie so effizient wie möglich ohne kollissionen auf unserem gegebenen Dataset funktioniert.
Wenn eine Hashfunktion keine Kollissionen hat, nennen wir das auch injektiv
Formell sieht das dann so aus:

Verfahren

Wir wollen Beispielsweise eine Hashfunktion mit quadratischem Platz haben

$I n f or ma t ik II$ Übung 07

Wenn wir etwas mit verkettung hashen wollen, müssen wir kram dann auch irgendwie sortieren, aber das machen wir einfach nicht, denn wir fügen einfach immer ganz am ende an :)
Denen ist aufgefallen, dass der Pseudocode aus der Vorlesung fürs Hashen mit verschieben, bzw lücken füllen (dat mit den blöcken) warscheinlich falsch ist (yay)
- In Vorlesung 13, Folie 3-12ff. muss es in Zeile 27
- $i f (h (f) \leq i < j \lor j < k \leq h (f))$

Aufgabe 1: Hashing mit Verkettung

a)

Hashfunktion: $h_{a} \in H^{SP}$ mit $h_{a} (x) = a \cdot x m o d m$
$a = (2, 7)$ und $m = 11$
Einzufügen:

$e_{1} = (2, 3)$
$e_{2} = (1, 2)$
$e_{3} = (3, 0)$
$e_{4} = (2, 1)$
$e_{5} = (0, 2)$
$e_{6} = (3, 3)$
$e_{7} = (4, 4)$

Mit Hashfunktion: $h_{a} ((x_{1}, x_{2})) = (27 x_{1} x_{2}) m o d 11$

Iteration:

$h_{a} ((2, 3)) = 3$

Iteration:

$h_{a} ((1, 2)) = 5$

Iteration:

$h_{a} ((3, 0)) = 6$

Iteration:

$h_{a} ((2, 1)) = 0$

Iteration:

$h_{a} ((0, 2)) = 3$

Iteration:

$h_{a} ((3, 3)) = 5$

Iteration:

$h_{a} ((4, 4)) = 3$

Tabelle:

Key	Value
0	$e_{4}$
1
2
3	$e_{1} \to e_{5} \to e_{7}$
4
5	$e_{2} \to e_{6}$
6	$e_{3}$
7

b)

$h_{0} (x) = (x + 5) m o d 3 = (x + 2) m o d 3$
$h_{0} (x) = (x + 7) m o d 3 = (x + 1) m o d 3$
$h_{0} (x) = (x + 9) m o d 3 = x m o d 3$

Für alle zwei unterschiedlichen schlüssel (in der schlüsselmenge der natürlichen Zahlen) darf es höchstens eine Hashfunktion geben bei der beide eingegebenen Zahlen den selben Hashwert haben, damit das dann 1 Universell ist $\forall x \neq = y \in N : ∣ {h \in H ∣ h (x) = h (y)} ∣ \leq \frac{c \cdot ∣ H ∣}{m}$

=> $H$ ist nicht $1$ -universell für $Key = N$

Aufgabe 2: Hashing mit linearem Sondieren

Mit Hashfunktion: $h (x) = x m o d 11$

a)

Schlüssel $14, 42, 19, 3, 17, 20, 6, 31, 25, 28$ mit obiger Hashfunktion in eine leere Hashtabelle einfügen

Key	Value
1
2
3
4
5
6
7
8
9
10
11
12

$I n ser t (14)$

Key	Value
1
2
3	14
4
5
6
7
8
9
10
11
12

$I n ser t (42)$

Key	Value
1
2
3	14
4
5
6
7
8
9	42
10
11
12

$I n ser t (19)$

Key	Value
1
2
3	14
4
5
6
7
8	19
9	42
10
11
12

$I n ser t (3)$

Key	Value
1
2
3	14
4	3 $↑$
5
6
7
8	19
9	42
10
11
12

$I n ser t (17)$

Key	Value
1
2
3	14
4	3 $↑$
5
6	17
7
8	19
9	42
10
11
12

$I n ser t (20)$

Key	Value
1
2
3	14
4	3 $↑$
5
6	17
7
8	19
9	42
10	20 $↑$
11
12

$I n ser t (6)$

Key	Value
1
2
3	14
4	3 $↑$
5
6	17
7	6 $↑$
8	19
9	42
10	20 $↑$
11
12

$I n ser t (31)$

Key	Value
1
2
3	14
4	3 $↑ 3$
5
6	17
7	6 $↑ 6$
8	19
9	42
10	20 $↑ 9$
11	31 $↑ 9$
12

$I n ser t (25)$

Key	Value
1
2
3	14
4	3 $↑ 3$
5	25 $↑ 3$
6	17
7	6 $↑ 6$
8	19
9	42
10	20 $↑ 9$
11	31 $↑ 9$
12

$I n ser t (28)$

Key	Value
1
2
3	14
4	3 $↑ 3$
5	25 $↑ 3$
6	17
7	6 $↑ 6$
8	19
9	42
10	20 $↑ 9$
11	31 $↑ 9$
12	28 $↑ 6$

Insgesamt: (Lösung)

Key	Value	(Hashwert)
0	31	9
1	28	6
2
3	14	3
4	3	3
5	25	3
6	17	6
7	6	6
8	19	8
9	42	9
10	20	9

(Der Hashwert, wird normalerweise nicht gespeichert)
Wir wrappen around, damit wir nicht nen ewigen "overflowpool" bauen, und um effizienter zu sein
Die Länge der Hashtabelle ist $m$ , also die Maximale anzahl an Indizes (jedenfalls beim linearen sondieren)

b)

Mit markieren als gelöscht:

Key	Value
0	31
1	28
2
3	14
4	3
5	25
6	del
7	6
8	19
9	42
10	20

Nachdem wir gelöscht haben, mmüssen wir einmal komplett über das ding iterieren und schauen, ob eine Zahl gut in das jetzt leere feld passt, spricht hochrücken will
Das machen wir so lange, bis es keinen "besseren Fit" mehr gibt.

Mit verschieben:

Key	Value
0	31
1	28
2
3	14
4	3
5	25
6	6
7
8	19
9	42
10	20

Jetzt schauen wir in der Leeren Zeile und applien wieder das oben erwähnte

Key	Value
0	31
1
2
3	14
4	3
5	25
6	6
7	28
8	19
9	42
10	20

Graphdarstellung

Graphdurchläufe

Übung 08

flowchart TD
    1 --> 2
    1 --> 3
    3 --> 1
    3 --> 2
    3 --> 4
    4 --> 2

Starke Zusammenenshangkomponenten

Kürzester Weg

Übung 09

Aufgabe 1

a) DFS-Verfahren

1 (Baumkante)
3
5 (Baumkante)
4 (weil das die niedriegste nächste Zahl ist)
2
8 (Hier ist der Pfad zuende, dementsprechend bekommt die 8 die Fin-Num 1)
2 (Wir gehen wieder zurück, und dann bekommt die 2 die Fin-Num 2)
7 (Baumkante, weil wir sie vorher nicht besucht hatten)
8 (Crosskante (weil die 8 schon besucht wurde, und wir so die etablierte Reihenfolge brechen))
7 (Fin-Num 3)
4 (Towardkante, Fin-Num 4)
5 (Wir gehen weiter zurück)
7 (Crosskante)
5 (Fin-Num 5)
3 (Direkt fertig, da keine "unbenutzten" wege existieren, Fin-Num 6)
1
5 (Crosskante)
1 (Fin-Num 8)
Jetzt sind wir mit dem ersten teilbaum fertig und fangen beim 2. an (also 6)
6
7 (crosskante, weil wir die 7 ja schon kennen)
6 (Fin-Num 8)
9 (Crosskante, Fin-Num 9)
Topologische Sortierung: 9, 6, 1, 3, 5, 4, 7, 2, 8

b) BFS-Verfahren

flowchart TD 
1 --> 3 
1 --> 5 
3 --> |Cross| 5 
5 --> 4 
5 --> 7
4 --> |Cross| 7
7 --> |Cross| 8
4 --> 2 
4 --> 8 
2 --> |Cross| 8
6 --> |Cross| 7
9 --> |Cross| 6

Aufgabe 2

component:

1	2	3	4	5	6	7	8	9	10
1	1	3	4	1	6	10	6	6	10

Wenn so eine Aufgabe in der Klausur kommt, alles beschreiben was man tut, denn sonst ist es sehr schwer bzw. praktisch unmöglich Teilpunkte zu geben
Beispielsweise sowas wie:

DFS besucht 1, 5, 2 und identifiziert {1, 5, 2} als Komponente. 1 wird als repräsentant ausgewählt
DFS besucht 3, 4, 6, 8, 9, 10, 7 in dieser reihenfolge
1. 6 wird durch kante (9, 6) als Repräsenentat indetifiziert
2. 10 wird durch kante (7, 10) als Repräsenentat indetifiziert
3. 7, 10 wird kollabiert
4. 6, 8, 9 wird kollabiert
5. 4 wird kollabiert
6. 3 wird kollabiert

Übung 10

Aufgbabe 1)

Djikstras Algo lolsies

Durchlauf	A	B	C	D	E	F	Q
$0$	$0/ A$	$\infty/ ⊥$	$\infty/ ⊥$	$\infty/ ⊥$	$\infty/ ⊥$	$\infty/ ⊥$	$< (A, 0) >$
$1$	$0/ A$	$1/ A$	$4/ A$	$\infty/ ⊥$	$\infty/ ⊥$	$\infty/ ⊥$	$< (B, 1), (C, 4) >$
$2$	$0/ A$	$1/ A$	$4/ A$	$\infty/ ⊥$	$\infty/ ⊥$	$\infty/ ⊥$	$< (C, 3), (D, 5) >$
$3$	$0/ A$	$1/ A$	$3/ B$	$5/ B$	$\infty/ ⊥$	$4/ C$	$< (F, 4), (D, 5) >$
$4$	$0/ A$	$1/ A$	$3/ B$	$5/ B$	$7/ F$	$4/ C$	$< (D, 5), (E, 7) >$
$5$	$0/ A$	$1/ A$	$3/ B$	$5/ B$	$6/ D$	$4/ C$	$< (E, 6) >$
$6$	$0/ A$	$1/ A$	$3/ B$	$5/ B$	$6/ D$	$4/ C$	$<>$

Durchlauf	A	B	C	D	E	F	Q
$0$	$\infty/ ⊥$	$\infty/ ⊥$	$\infty/ ⊥$	$0/ D$	$\infty/ ⊥$	$\infty/ ⊥$	$B [0] :< D >\leftarrow min$
$1$	$\infty/ ⊥$	$4/ D$	$4/ D$	$0/ D$	$1/ D$	$\infty/ ⊥$	$B [1] :< E >\leftarrow min B [4] :< B, C >$
$2$	$\infty/ ⊥$	$1/ E$	$4/ D$	$0/ D$	$1/ D$	$5/ F$	$B [0] :< F > B [1] :< B >\leftarrow min B [4] :< C >$
$3$	$\infty/ ⊥$	$1/ E$	$3/ B$	$0/ D$	$1/ D$	$5/ F$	$B [0] :< F > B [3] :< C >\leftarrow min$
$4$	$\infty/ ⊥$	$1/ E$	$3/ B$	$0/ D$	$1/ D$	$4/ C$	$B [4] :< F >\leftarrow min$
$5$	$7/ F$	$1/ E$	$3/ B$	$0/ D$	$1/ D$	$4/ C$	$B [2] :< A >\leftarrow min$
$6$	$7/ F$	$1/ E$	$3/ B$	$0/ D$	$1/ D$	$4/ C$

Wir bleiben so lange in einem behälter bis der leer ist
Wenn der leer ist gehen cyklisch weiter, bis der leer ist

Übung 11

Aufgabe 1: Algorithmus von Kruskal

Nach kruskal sortieren wir nach den Kantengewichten (die Zahlen da an der seite lol)
Die aufgabe definiert, dass wir das Aufsteigend machen sollen
Die sind in dieser Reihenfolge:
- $(1, 3), (2, 5), (7, 8), (1, 4), (3, 4), (4, 7), (5, 8), (6, 7), (1, 2), (3, 5), (5, 6), (4, 6)$
- erst 1,3, da die näher an 1 dran ist
- wir sortieren immer nach Gewicht, und dann eben der Lexegographischen Reihenfolge
Am Anfang haben wir keine Kanten in unserem Baum und für jeden Knoten seine eigene Zusammenhangskomponente
Das heiß́t, unser baum sieht "mengentechnisch" so aus:
- ${1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}$
Wir führen jetzt den Algo von Kruskal aus, so auch in der Klausur notieren:
Wir fügen also zuerst die Kante zwischen 1 und 3 an und überprüfen, ob diese eine unendliche schleife generiert (einen Kreis verursacht)
- Tut sie nicht, deswegen fügen wir das dann in unsere Zusammenhangskomponente ein
- $Zusammenhangskomponente = {1, 3}, {2}, {4}, {5}, {6}, {7}, {8}$
- $T = {(1, 3)}$
Einfügen $(2, 5)$
- $Zusammenhangskomponente = {1, 3}, {2, 5}, {4}, {6}, {7}, {8}$
- $T = {(1, 3), (2, 5)}$
Einfügen $(7, 8)$
- $Zusammenhangskomponente = {1, 3}, {2, 5}, {4}, {6}, {7, 8}$
- $T = {(1, 3), (2, 5), (7, 8)}$
Einfügen $(1, 4)$
- $Zusammenhangskomponente = {1, 3, 4}, {2, 5}, {6}, {7, 8}$
- $T = {(1, 3), (2, 5), (7, 8), (1, 4)}$
Einfügen $(3, 4)$
- würde einen Kreis verursachen, nehmen wir daher nicht auf
Einfügen $(4, 7)$
- $Zusammenhangskomponente = {1, 3, 4, 7, 8}, {2, 5}, {6},$
- $T = {(1, 3), (2, 5), (7, 8), (1, 4), (4, 7)}$
Einfügen $(5, 8)$
- $Zusammenhangskomponente = {1, 3, 4, 7, 8, 2, 5}, {6},$
- $T = {(1, 3), (2, 5), (7, 8), (1, 4), (4, 7), (5, 8)}$
Einfügen $(6, 7)$
- $Zusammenhangskomponente = {1, 3, 4, 7, 8, 2, 5, 6},$
- $T = {(1, 3), (2, 5), (7, 8), (1, 4), (4, 7), (5, 8), (6, 7)}$
Alle folgenden Kanten würden (mind.) einen Kreis verursachen und werden daher nicht aufgenommen
Das finale $T$ ist dann:
- $T = {(1, 3), (2, 5), (7, 8), (1, 4), (4, 7), (5, 8), (6, 7)}$
- Mit kosten 11, nachdem man das gewicht der Kanten summiert hat

Aufgabe 2: Minimaler Spannwald

Option A)
- wir fügen einfach einen neuen knoten an mit den höchsten kosten an jeder kante
- dann ist das halt das teuerste auf jedem weg, deswegen lohnt sich das dann nich
Option B)
- Wir fügen einfach überall wo der Graph nicht zusammenhängt, eine Kante mit relativ hohen Kosten ein $(ma x_{k os t e n} + 1)$ , damit sich das wie oben wieder nicht lohnt
- Führe Jarnik-Prim auf diesem "zusammengebauten" Graphen aus
- Entferne anschliessend die "klebekanten" und spuck das dann aus

Korrektheit:

Wir zeigen: Der Spannbaum den Janik-Prim auf dem modifizieren Graphen bestimmt, besteht aus
- einem Spannbaum für jede Zusammenhangskomponente von $G$ und
- Kanten auf Ê, die zwei Zusammenhangskomponenten verbinden (je höchstens eine pro Paar von Zusammenhangskomponente)

Begründung:

Keine Kanten aus Ê werden Innerhalb einer Zusammenhangskomponente verwendet: gilt wegen kreiseigenschaften und Korrektheit Janik-Prim
Zwischen zwei Zusammenhangskomponenten wird höchstens eine Kante aus Ê (E-Dach) verwendet

max Kantengewicht $O (∣ V ∣ + ∣ E ∣)$ (Adj, listen)
Absteigend bei Kante aus $\hat{E} : O (∣ V ∣ + ∣ E ∣) \to$ Graph mit $∣ V ∣ K n o t e n$
Janik-Prim $O (∣ V ∣ l o g ∣ V ∣ + ∣ E ∣ + ∣ V ∣ - 1) \leq ∣ E ∣ + ∣ V ∣ - 1$ Kanten
$O (∣ V ∣ l o g ∣ V ∣ + ∣ E ∣)$
Entfernen den Kanten aus $\hat{E} / E : O (∣ V ∣ + ∣ E ∣)$

Übung 12

Aufgabe 1: Suchbäume

Die Logarithmische Tiefe wird sicher gestellt, indem alle Blätter auf der gleichen Höhe gespeichert werden.
Hierbei gibt es die Beschränkeung, dass (fast) alle inneren Knoten zwischen $a$ und $b$ Kinder haben (Menge).
Dadurch stellen wir sicher, dass Operationen effizient laufen und es generell "nur" eine geringe Tiefe gibt.
- Sicherstellen der Invariante beim
  - Einfügen durch Spalt-Operationen
  - Löschen durch Balancieren oder Verschmelzen

d) Beweis:

Induktionsannahme: $n = 1$ Suchbaum besteht nur aus Wurzel
- Wurzel ist ein Blatt
- Baum hat $0 = (1 - 1)$ innere Knoten
Induktionsvorraussetzung: Sei $n \in N_{i} \forall1 \leq n \leq n$ gekte, dass ein binärer Suchbaum mit $n^{'}$ Blättern genau $n^{'} - 1$ innere Knoten hat.
Induktionsschritt: $n \to n + 1$ . Sei $T$ binärer Suchbaum mit $n + 1$ Blättern $n + 1 \geq 2$ , d.h. Wurzel ist innerer Knoten und hat genau 2 Kinder, die Wurzeln von Teilbäumen $T_{1}, T_{2}$ sind. Wir können $T_{1}, T_{2}$ als binäre Suchbäume mit $n_{1} \leq n, n_{2} \leq n$ Blättern auffassen
$1 \leq n_{1} \leq n => T_{1}$ hat $n_{1} - 1$ innere Knoten
$1 \leq n_{2} \leq n => T : 2$ hat $n_{2} - 1$
$#$ innere Knoten von $T = n_{1} - 1 + n_{2} - 1 + 1$
- $T_{1} \to n_{1}$
- $T_{2} \to n_{2}$
- Wurzel $\to 1$
$= n_{1} + n_{2} - 1 = (n + 1) - 1 = n$

Vollständig

Fehlt
Dine
?
?
?
Fehlt
Done
Fehlt
?
Fehlt
Fehlt
Done
Unvollständig

Logik in der Informatik

Prof. Dr. Thomas Zeume
SS 2024

A1: Syntax und Semantik der Aussagenlogik

Wir wollen erstmal schauen was wir überhaupt mit formaler Logik anstellen können
denn warum sollten wir uns die extra arbeit machen, das alles zu formalisieren, wenns uns doch dann am ende nichts bringt oder?
wenn wir unsere sachen logisch formalisieren, dann können wir sicher sein, dass das tatsächlich stimmt, was wir da erzählen, also
- das wahre Aussagen belegbar auch wahr sind, und wir das nicht einfach so definieren
wir fangen an, indem wir unsere (schlüssigen) überlegungen notieren, und daraus folgerungen ziehen
wir schauen daher, wie wir unseren kram vernünftig und fehlerfrei modellieren
Das machen wir so
- Wir repräsentieren unsere Aussagen mit Buchstaben
- $A$ steht z.b. für Anna isst Äpfel
- Mit diesen repräsentationen können wir dann "schöne" formeln basteln mit deren Hilfe wir unsere Aussagen dann modellieren können
Nachdem wir unsere Formeln aufgestellt haben können wir diese dann auch auswerten, nachdem wir den einzelnen Variablen (repräsentationen) Wahrheitswerte zugewiesen haben

Semantik und Syntax

Wir haben wie oben schon beschrieben verschiedene variablen mit verschiedenen bezeichnungen wie $A$ , $B$ , $C$ oder ähnlichem
Die dinger können wir dann zusammengroupen und daraus "tolle" Formeln bauen
Die haben folge Darstellungsweisen
- $(\neg φ)$ (Negation)
- $(φ_{1} \land φ_{2})$ (Konjunktion)
- $(φ_{1} \lor φ_{2})$ (Disjunktion)
Mit dieser Struktur können wir vieles in sog. Aussagenlogischen Formeln modellieren
Wenn wir dann unsere Aussagenlogische Formel moddliert haben wollen wir warscheinlch ihre wahrheit belegen (schauen, dass das tatsächlich stimmt, was wir da gebastelt haben)
Das machen wir oft einfahc mit der sog. "Wahrheitsbelegung"
Semantisch können wir das "einfach" so definieren:
- Naja ich werd das jetzt nicht weiter aufschlüsseln weil das so ist wie bei logikgattern

Woche 02

Wir schauen uns halt mal an was die Aussagenlogik ist
Damit können wir kram aussagen, und damit halt dinge feststellen
Je nachdem wie wir was darstellen kann man das dann als Formel "einfach" lesen
Wie wir wissen, hat jede Aussage eine Variable zugewisen, die aussagt was dat ist
Mit diesen variablen können wir dann, wie wir wissen ja eine formel basteln

Äquivalenz

Manchmal wollen wir herausfinden, ob zwei Formeln äquivalent zueinander sind
das machen wir idealerweise indem wir die beiden erstmal miteinander vergleichen
Damit zwei formel äuivalent sind, müssen wir schauen, dass beide unter allen aussagen auch dasselbe ausspucken
genau aussagen können wir das mit solchen Formeln:

Wahrheitstabellen

Die kennen wir schon aus Hömmi 1
Mit denen krann man praktisch jede kombination von Aussagenlogischen Vaiablen in ihre einzelteile zersägen und dann einzelnd ein teil at a time durchschauen
In denen können wir z.b. auch einfach sachen substituieren, wenn wir wissen, wie dieser teil reagiert

Woche 03: Anwendung: Formale Verifikation

Wenn wir eine gemeinsame Ressource nutzen wollen machen wir das oft mit einem System von höflichkeit
Sowas kann man allerdings nur sehr schlecht formalisieren
Das ist problematisch, weil dann können wir uns praktisch garnicht sicher sein, ob das was wir machen / das was wir betrachten, tatsächlich das tut was es tun soll
Wenn wir uns das mal fundamental anschauen, sehen wir, dass eine Ressource automatisch abhängig ist, wenn wir sie teilen
Genauer gesagt ist ein System Abhängig, indem sich mehrere Prozesse untereinander beeinflussen können
Das können sachen sein die ein gemeinsames Ziel verfolgen oder auch dinge sein die was komplett unterschiedliches machen
klassisch können wir das in einem System beobachten indem es Mutual exclusion gibt
- sprich asynchrone Programme oder ähnliches

Dijkstras Protokoll

Um damit vernünftig durchzustarten hat unser beliebter Dijkstra schonmal ein Protokoll gemacht
in diesem Protokoll stellt er einen weg dar, mit dem man sowas vernünftig handlen kann
Zunächst unterteilen wir unser Programm in einen Kritischen und einen Unkritischen bereich
Hier ist der unterschied, dass der Kritische bereich die Ressource darstellt, die geteilt ist
- Also hier können wir probleme bekommen, denn die ressource kann logischerweise nur von einem Thread / einem Prozess gleichzeitig genutzt werden
Wir schnappen uns also ein "Signal" bzw. einen Indikator, mit dem wir aussagen können, ob eine Ressource derzeit available oder nicht ist
Wenn also eine ressource auf den kritischen bereich zugreifen will, schauen wir zuerst nach, ob der bereich betretbar ist
Wenn das geht, setzen wir die ressource auf "unavailable" und gehen dann rein
Nachdem wir mit dem kram fertig sind, können wir das dann einfach wieder zurückstellen
So können wir sichergehen, dass nicht zwei ressourcen gleichzeitig versuchen auf die selbe Ressource zuzugreifen
Und ausserhalb von unserem kritischen bereich, können wir alles einfach so machen wie wir wollen

Einführung ins Model Checking

Beim model-Checking verwenden wir (wie so häufig) einen Algorithmus um zuzuschauen, dass alles so passiert wie wirs haben wollen

Wir modellieren unser Programm in einem Transitionssystem, damit wir den fluss von Daten / Informationen schön und sinnvoll darstellen können
Spezifizieren der einzelnen Eigenschaften durch formeln
- Wir schreiben also eine Formel, für jede auftretende eingenschaft, damit wir uns absolut sicher sein können, dass wir tatsächlich das ausdrücken was wir auch sagen wollen
Dann testen wir, ob das Transitionssystem auch unseren Formeln "Standhält"
Wenn das nicht der fall sein sollte, konstruieren wir ein Gegenbeispiel

betrachten können wir das ganze durch typische Logiken
- $L T L$ Linear temporal logic
- $CT L$ Computational tree logic
Das modelchecking und seine respektiven logiken verwenden wir in Programmen, Protokollen und vielem mehr

Wie kommen wir denn jetzt dahin

Naja, wenn wir uns jetzt den Ablauf oben anschauen, sehen wir, dass wir ja irgendwie unsere Strukturen bauen müssen
Wir bauen uns also unser Transitionssystem: eine Kripke-Struktur mit verschiedenen Startwelten
Die startwelten haben einen Pfeil (wie bei den Automaten in Info 3)
In der "normalen" Literatur haben die Kanten meisstens beschriftungen, das machen wir hier einfach nicht
Aber wie machen wir denn jetzt aus unserem Theoretischen Entwurf eine Kripestruktur?
- Wir schauen uns alle möglichen "states" an
- Diese können wir dann modellieren und mit Transitionen miteinander verbinden
- Sprich: es kann nur ein Valider State in einen anderen validen State wechseln
- Damit können wir das "relativ" leicht darstellen und ein wunderschönes Diagramm erstellen

Eigenschaften Spezifizieren

ja wir haben also jetzt unsere "tolle" Kripestruktur
Wir überlegen uns jetzt erstmal "sinnvolle" Eigenschaften
1. Fangen wir mit Korrektheit an, was sind dinge, die immer gelten müssen?
1. "Fairness" wie können wir sicherstellen, dass alle teile unseres Systems gleichmäßig gut die geteilte ressource nutzen könnnen?

Abwicklung

Aus jeder Welt unserer Kripestruktur können wir eine Abwicklung konstruiheren
Diese ist analog mit unseren Transitionssystemen
eine Abwicklung ist am ende nichts weiter, als der "Weg" ausgehend von einer Kripestruktur

CTL

Wenn wir uns CTL anschauen, sehen wir, dass es sehr sinnvolle Operatoren gibt

Syntax und Semantik

Wenn wir Formeln wie $φ$ oder $ψ$ haben können wir auch
- $\neg φ, φ \land ψ$ und $φ \lor ψ$
- $EXφ, EFφ, EGφ$ und $E (φ U ψ)$
- $A Xφ, A Fφ, A Gφ$ und $A (φ U ψ)$ haben
Kurz gesagt, können wir die beliebig aneinanderhängen und stacken
Die vorhergehenden Ausdrücke "begrenzen" sozusagen die folgenden
Denn am ende bezieht sich das alles auf einen Weg

Auswertung

Zur auswertung haben wir ja meisstens noch ein Transitionssystem zur hand
Hiermit können wir dann unsere Formeln auswerten, und schauen was passiert und aufschreiben wofür was genau gilt

Konstruktion

Verifikation

Zu "guter" letzt wollen wir den kram ja auch noch irgendwie verifizieren, also schauen, dass das wirklich sinn macht, was wir da gebastelt haben
So nutzen wir den kram den wir uns ausgesucht haben dann auch wirklich
Wir werfen noch einen Blick auf das tolle diagramm von vorher

Beispiel:

Woche 04

Woche 05

Woche 07

Übung 04: Modallogik

Wir schauen uns das als Welten an
Wir schauen uns dementsprechend auch die Verbindungen zu und zwischen Welten an
Propositionen / Variablen in Welten

Wasn der Unterschied zur Aussagenlogik?

In der Aussagenlogik haben wir uns immer nur eine welt angeschaut
Jetzt können wir mehrere Welten beobachten
In der aussagenlogik konnten wir vieles "schön" darstellen
$□ ϕ$ Bedeutet, dass eine Aussage in allen erreichbaren Welten gilt
$◊ ϕ$ Bedeutet, dass es eine erreichbare Welt gibt, in der $ϕ$ gilt
$\neg □ A \equiv ◊ \neg A$

Beispiele

Wir betrachten zwei Formeln ( $f$ = falsch, $w$ = wahr)
- $□ A f w$
- $◊ A f f$
- $\neg □ A \equiv ◊ \neg A$
Lustig ist zu beachten, dass $□ ϕ$ auch gelten kann, wenn es keine erreichbaren Welten gibt

Aufgaben

Aufgabe 1)

Wenn man nicht am Hauptbahnhof ist und keine Eintrittskarten für das Stadion kaufen kann, dann ist die Uni nicht ohne umzusteigen erreichbar

$H \to □ S$
$U \leftrightarrow (S \lor ◊ S \lor ◊◊ \lor ◊◊◊ S)$
$□ (\neg U \land \neg S) \to \neg ◊ H$

Aufgabe 2)

	$S_{1}$	$S_{2}$	$S_{3}$	$S_{4}$	$S_{5}$	$S_{6}$	$S_{7}$	$S_{8}$
$a$	true	false	true	true	true	false	true	true

Aufgaben vom Heimblatt

Aufgabe 3)

B2: Erfüllbarkeit in der Modallogik

Wir wollen uns heute anschauen, wie wir festlegen können, dass etwas entscheidbar ist
Wir sehen, dass das nicht besonders übersichtlich ist
Das ist nicht soooo toll
Wir schauen uns diesen "tollen" graphen an:
Damit die Formel erfüllbar ist, muss einer der beiden Formeln wahr sein

Tableaukalkül

Ein Aussagenlogisches Tableau ist son toller "Baum" dessen knoten so Aussagenlogische Formeln sind
Ein Tableau für eine AL-Formel $ϕ$ in Negationsnormalform.
- Ohne vorkommen von wahr & falsch kann sie so konstruiert werden:
Wat bedeutet das denn?
- Ein saturiertes Tableau ist eins, wo alle Knoten die kein Literal sind markiert sind
- [...]
Wir können das so erreichen, wenn wir die Literale sinnvoll belegen
(Sinnvoll, ist oben gezeichnet)
Insgesamt ist das einfach: Wir schauen uns unsere Formel an, und machen "einfach" Fallunterscheidunng

Korrektheit

Das ganze wird hier einfach groß beschrieben
Wie machen wir das jetzt?
- Wir schauen uns jetzt an, ob unser Algo irgendwann mal terminiert
  - Wenn er das nicht machen würde, wäre das deutlich schlecht
- Dann schauen wir, ob das ding jetzt Korrekt ist, und ob das überhaupt das tut, was wir wollen
- Zuletzt schauen wir, ob das was da rauskommt denn überhaupt vollständig ist

B3: Anwendung Formale Verifikation

watn das?
Wir versuchen ein (komplexes) stück hardware und oder software zu "beweisen"
Also nicht schauen, dass es da ist, sondern beweisen, dass es das tut, wozu wir es definiert haben
Idealerweise macht man das eben nicht von hand, sondern eben mit einem Compuper
Wir wollen letztendlich dann alles irgendwie formell definieren und eben auch verifizieren
Wir schauen uns zunächst ein "tolles" szenario an
Das können wir am besten mit diesem bild veranschaulichen:
Wenn wir uns das anschauen, sehen wir, dass wir (hallup time) ein abhängiges System haben, indem sich mehrere Prozesse gegenseitig beeinflussen
- Diese zwei prozesse können am ende alles sein, ob jetzt programme, Autos o.ä.
- Die können auch nen gemeinsames Ziel verfolgen oder auch eben nicht
Das beste beispiel dabei sind praktisch "Beispiele"
- Denn jedes beispiel ist ein System dessen Prozesse ein "gemeinsames" Ziel erreichen (nämlich das zeigen, wozu wir ein beispiel machen)
- Denn unterm strich greifen sie auf gemeinsame ressourcen zu
Ein problem was wir dabei erkennen ist, dass vieles nur eine sache gleichzeitig machen kann
- Dementsprechend kann dann immer nur ein Prozess drauf zugreifen
- Das nennen wir dann "Mutual Exclusion" auch bekannt als der legendäre Mutex
Wir schauen uns jetzt ein Szenario an:
- Von zwei Prozessen kann maximal ein Prozess auf eine Gemeinsame Ressource zugreifen
- Es gibt einen Kritischen und einen Unkritischen bereich.
- Der geteilte bereich, ist dann eben der "kritische" bereich, weil dieser "weitergegeben" werden muss
- Wir wollen also garantieren, dass nicht beide Prozesse gleichzeitig in eben diesem Kritischen bereich sind
Das lösen wir am besten eben mit Semaphoren-
- Wat dat?
  - Ein Semaphor "bewacht" eine gemeinsame Ressource, und entscheidet bzw. Signalisiert, ob diese gerade nutzbar ist
  - Ein Prozess kann sich eine Ressource vom Semaphor "reservieren" lassen, und solange diese Ressource reserviert ist, kann kein anderer Prozess auf eben diese Ressource zugreifen
  - Der Semaphor behält hier den überblick
- Die, und all ihre operationen, sollen Atomar ausführen
- Sprich: Das muss für alle immer gleich aussehen, und alles muss in einer festen reihenfolge passieren.
- In der realen welt stelt das Betriebssysten eben das sicher
  - Wie geht das? Man lernt das in Betriebssysteme an
Wir schauen uns eben das in "Dijkstras Protokoll" an.
- Initial ist unser Prozess (den wir uns anschauen) im Unkritischen bereich
- Der Prozess entscheidet jetzt, dass er die geteilte ressource braucht
- Jetzt schaut er, ob sie frei ist, und wartet wenn sie nicht frei ist
- Wenn die ressource dann frei ist, signalisiert der Prozess dem Semaphor, dass er die Ressource nutzen will und dieser Reserviert diese dann für unseren prozess
- Dann ist der Prozess im sog. Kritischen Bereich, und hat alleinigen zugriff auf die ressource
- wenn der Prozess dann fertig mit der Ressource ist, gibt der semaphor die ressource wieder frei, und der Prozess ist wieder im unkritischen bereich
- Genauer gesagt, kann es auch passieren, dass ein OS wärend die Prozesse laufen sie zwangsweise abwechseln lässt, aber das ist hier gerade nicht weiter relevant
Wir können so auch sehen, dass Dijkstras Protokoll nicht fair ist, dementsprechend schauen wir uns noch zwei andere Protokolle an:

Einführung ins Model Checking

Wir können letztendlich alles verifizieren
Das machen wir aber alles mit einem bestimmten schema, das ist dann eben das hier:
Wir wollen uns jetzt Transitionssysteme anschauen, sprich wie man von einem Protokoll zur Logik kommt

Vom Protokoll zum Transitionssystem

Naja, das transitionssystem ist eine Kripke-Strkruktur mit Startwelten
Das erste was wir also machen müssen, ist uns zu überlegen wie man von unserm Protokoll zum Transitionssystem kommen
- Das Protokoll ist eben unser sachverhalt, sprich ein Schaltkreis, Programm o.ä. Irgendwas, was definiert werden kann
Wir schauen uns erstmal an was für zustände es gibt.
- Nen zustand ist z.b. was für gegebenheiten gerade innerhalb des Progreamms herrschen
Wenn wir alle zustände haben, bauen wir eben ein Transittionssystem
- Wir überlegen uns also, wie man von einem Zustand in den nächsten wechseln kann
- Das machen wir dann eben mit "tollen" Pfeilen
- Das sieht dann am ende so aus: (irgendwie ein bisschen wie ein Pentagramm)
Jetzt können wir auf "einen blick" sehen, was wie erreichbar ist

Spezifikation von Eigenschaften

Wir schauen uns jetzt eine Spezifikationssprache an
Die sprache heisst CTL
Die protokolle die wir uns anschauen müssen ja eine gewisse anzahl an "vorraussetzungen" erfüllen
Eine davon ist auf jeden fall die Korrektheit, denn das ding muss ja auch funktionieren.
- $ϕ_{1} = A G (\neg c_{1} \lor \neg c_{2})$
- Das liest man dann so:
  - $A$ = Für alle Berechnungpfade
  - $G$ = Global, also überall in unserer welt
Eine zweite Eigenschaft ist Fairness
- Das bedeutet, dass jeder Prozess gleich behandelt wird, also jeder zugreifen darf (wenn wir das beispiel von oben weiter nutzen)
- $A G (ω_{1} \to A F c_{1})$
  - Das liest man:
    - Für alle möglichen berechnungspfade muss gelten, dass wenn jemand wartet
    - irgendwann $c_{1}$ gelten muss
Das alles sind +CTL* Formeln, das steht für "Computation Tree Logic"
Die dinger können wir auch als "Berechnungsbaum" anschauen, und so werten wir das dann am ende aus
- Das ist gleich, wie die abwicklung einer Startwelt, also wie wir durch diese welt (und ihre folgewelten) laufen können
Die welten verhalten sich nach dem oben definierten schema, und dann können wir eben durch diese welt mithilfe des Berechnungsbaum laufen

Zutaten von CTL

CTL hat gewisse Operatoren
- $EX, EF, EG, E U$
- $A X, A F, A G, A U$
dabei stehen die buchstaben (logischerweise) für tolle dinge
- $E$ : "Es gibt einen Pfad..."
- $A$ : "Für alle Pfade..."
Der Zeweite Teil beschreibt dann den quantifizierten Pfad:
- $Xϕ$ : In der nächsten Welt gilt $ϕ$
- $Fϕ$ : In einer zukünftigen Welt gilt $ϕ$
- $Gϕ$ : In allen zukünftigen Welten gilt $ϕ$
- $δ U ϕ$ : $δ$ gilt bis $ϕ$ gilt
Insgesamt ist CTL eine Verallgemeinerung der Modallogik
- $EX$ entspricht $◊$
- $A X$ entspricht $□$
Es gibt in CLT immer einen "Roten Faden", also was immer gilt usw.

Syntax und Semantik von CTL

Auswertung von CTL-Formeln

Verifikation von Eigenschaften

Wir erinnern uns nochmal an das schema:
Letztendlich ist die Große frage die wir uns stellen und die wir entscheiden wollen ist eben, ob die Aussage bzw. das vorliegende Protokoll Stimmt und unseren Vorraussetzungen entpsicht

Übung 05

Zuerst ein Rückblick

Wir wollen zunächst mal schauen, ob unsere Logiken so vertretbar und oder beweisbar sind

	Erfüllbar	nicht erfüllbar	allgemein gültig	nicht allgemein gültig
nur Aussagenlogik	(Resolution)	Resolution
	DPLL + CDLL	DPLL + CDLL
	Wahrheitstabelle	Wahrheitstabelle	Wahrheitstabelle	Wahrheitstabelle
(nur Hornformeln)	Markierungsalgorithmus	Markierungsalgorithmus
Aussagenlogik & Modallogik	Tableaukalkül	Tableaukalkül	Negierte Formel auf Unerfüllbarkeit testen	Negierte Formel auf Erfüllbarkeit testen
	Modell angeben			nicht erfüllende Interpretation angeben

Resolution
- Es gibt "nur" Exponentiell Viele Klauseln, nicht unendlich
- Dementsprechend kann man mit "brute force" theoretisch alles durchprobieren
- nur weil man das "selber nicht schafft" ist das kein beweis
Beispiel:
- $(A \lor \neg A) \lor (B \land \neg B)$
- Hier sehen wir, dass wir einen geschlossenen Pfad haben, allerdings muss die Formel deswegen nicht allgemeingültig sein
Wir hoffen, dass wir das alles können (yay)

CTL Formeln

Wo gilt welche Formel?

	A	B	D	E	F
$E (a U c)$	x	x		x
$EG a$	x			x	x
$A FEG a$	x		x	x	x
$A G a$					x
$EF A G a$	x	x	x	x	x
$FG a$	x		x	x	x
$EG A F a$	x		x	x	x
$EF a$	x	x	x	x	x
$A GEF a$					x

Sind diese Folgen Equivalent?

$A F a \lor A F b$
$A F (a \lor b)$

Modallogik und CTL

a) 1.

CTL
- $a \land ◊ f$
- $a \land EX f$
ML
- Wir können das ggf. einfach nicht auswerten, weil wir theoretisch eine unbeschränkte menge von $□$ -Operatoren brauchen können
- Dadurch ist hier die CTL deutlich ausdrucksstärker, weil $n$ Boxes
- $(f \to \neg a) \land (f \to n \cdot □ \neg a)$

CTL
- $A G (f \to A G \neg a)$
ML
- Wir können das ggf. einfach nicht auswerten, weil wir theoretisch eine unbeschränkte menge von $□$ -Operatoren brauchen können
- Dadurch ist hier die CTL deutlich ausdrucksstärker

C1: Grundlagen der Prädikatenlogik

Einleitendes Beispiel

Wir wollen scheinbar wen umbringen?
Das ist maximal doof?
Wir können diese Sachverhalte mit sog. Prädikaten ausdrücken, die sehen dann so aus:
- $D (x)$ : $x$ ist ein Bewohner von Schloss Dreadsbury
- $K (x, y)$ : $x$ hat $y$ ermordet
- $H (x, y)$ : $x$ hasst $y$
- $R (x, y)$ : $x$ ist reicher als $y$
Mithilfe dieser Prädikate können wir dann blutige sachverhalte modellieren und am ende dann zeigen, wer wann wie weswegen der Mörder mit welchem Motiv ist
Ausgeschrieben kann dann sowas hier entstehen:
Da stellt sich dann aber die frage, wie wir sowas überhaupt zusammenbauen:
- Wir brauchen dafür eine Grundmenge die Festlegt welche Werte es gibt und welche Bedeutung diese Annehmen können
- Daneben brauchen wir auch die konkreten relatinonen um darzustellen wie unsere Aussagen zueinander stehen
- Unter den dort definierten Umständen können dann Formeln gelten

Strukturen

Wenn wir daten in der Informatik anschauen dann wollen wir die in einem Format betrachten das der Computer verstehen und auch auswerten kann
Leider kann man nicht alles optimal in einem Format ausdrücken und dementsprechend brauchen wir dann mehrere Darstellungen um verschiedene Daten möglichst Effizient darstellen zu können
Diese "Formate" kennen wir auch als kodierungen, oder als Codecs
- Hier sind die bejanntensten beispiele wohl Binärdarstellungen und Hexadezimalzahlen
Ebenso können wir im Computer alles irgendwie in Datenstrukturen Darstellen oder auch gruppieren, denn diese sind
- Komfortablere Repräsentationen
- Einfache Abstraktion von (komplexen) Datenmengen
Daneben stehen die Datenbanken die eine "externe" Speicherung von mengen von daten möglich machen
Unser Ziel ist, dass wir über Daten "einfach reden" können
- Das wir unsere Daten in einem (festen) Schema spezifizieren können
- Und wir einfache "fragen" stellen können
Dazu müssen wir unsere Daten modellieren, und das machen wir mit Mathematischen objekten
Die mathematischen Objekte die wir hier nutzen nennen wir auch Strukturen und die bestehen aus
- Relationen
- Funktionen
- Konstanten

C2: Modellierung und Normalformen

Heute wollen wir schauen was wann wie erfüllbar ist
Die motivation dazu ist dieselbe wie das was wir schon bei aussagenlogik etc. gemacht haben
das ist alles das gleiche, bis auf, dass das hier jetzt nen bissl komplizierter ist

Modellierung: Formeln erstellen und verstehen

wir erinnern uns an das "tolle" schloss dreadsbury
Da (und auch nur da) konnte man mit logischen formeln einen Mord aufklären
- Das haben wir gemacht, indem wir die zwischenmenschlichen beziehungen mit prädikatenlogik formalisiert haben (was irgendwie nen sehr komisches verfahren ist)
- Wir konnten mit so ausdrücken wie $\forall x \forall y (D (x) \to \neg K (y, x))$ definieren, dass niemand der im Schloss selber wohnt ermordet würde
Diese formeln haben wir mithilfe von "aussagen" definiert die wir uns wie funktionen vorstellen können
- dementsprechend gilt sowas wie $D (x)$ in unserem fall dafür, dass $x$ im Schloss wohnt
So können wir auch komplexere sachverhalte "dynamisch" modellieren, indem wir aus diesen "simplen" Formeln komplexere zusammensetzen
wir versuchen natürlich die sachen so zu modellieren, dass sie immernoch der "natürlichen sprache" ähneln, denn am besten modelliert man "nach der umgangssprache"
Was dann noch für uns interessant ist, sind die "beschränkten quantoren"
Diese sind in der mathematik sehr beliebt, da man mit diesen einfach einen Wertbereich einschränken kann
- solche dinge sind bei uns aber leider nicht erlaubt
Wir können aber statt sowas wie $\forall x (R (x) \to ψ)$ anstelle von $\forall x \in R : ψ$ schreiben
Ebenso kann man $\exists x \in R : ψ$ durch $\exists x (R (x) \land ψ)$ ersetzen
Damit simulieren wir eben diese "Beschränkten quantoren"

Äquivalenzen

zuerst wollen wir uns aber dann mal anschauen wie wir bestimmen können, dass zwei aussagen äquivalent sind
Denn beide sind Äquivalent, wenn es eine passende Interprätation $I$ gibt für die gilt, dass $I ⊨ φ \Leftrightarrow I ⊨ ψ$
- Das schreiben wir "einfacher" so: $φ \equiv ψ$

Nachweise von Äquivalenzen

Wir können äquivalenzen immer nachweisen indem wir
- die Definition überprüfen
- das ersetzungslemma
Wasn das Ersetzungslemma?

Sei $φ_{1}$ eine prädikaten-logische Formel mit einer Teilformel $ψ_{1}$

Sei $ψ_{2}$ eine weitere Formel mit $ψ_{2} \equiv p s i_{1}$

Wenn $φ_{2}$ aus $φ_{1}$ entsteht, indem ein Vorkommen von $ψ_{1}$ durch $ψ_{2}$ ersetzt wird,
dann gilt $φ_{2} \equiv φ_{1}$

Hier gibts nen beispiel.

Nachweise von Nicht-Äquivalenz

Wenn wir die Äquivalenz definieren können, müssen wir ja auch definieren können, dass man andere sachen nicht definieren kann
Das machen wir (wie so oft) "einfach" mit nem gegenbeispiel

Normalformen

Was ist denn eine Normalform?
- eine Prädikatenlogische Formel ist in reduzierter form wenn sie nur $\exists, \lor, \neg$ verwendet, aber bene nicht $\forall$ und $\land$
- $φ$ ist in Negationsnormalform (NNF), wenn Negationen in $φ$ nur unmittelbar vor atomaren Formeln vorkommen
- $φ$ ist in prännexform wenn sie so aussieht: $Q_{1} x_{1} Q_{2} x_{2} ... Q_{k} x_{k} φ^{'}$
  - Dabei ist $Q_{i}$ entweder $\exists$ oder $\forall$
  - $x_{i}$ muss paarweise verschieden sein
  - $φ^{'}$ quantorenfrei
- Beispiel
Umwandlung in Pränexform: ein Algorithmus
Berechnung von einer Pränexform: Beispiel
Berechnung von einer Pränexform: Beispiel 2

Erfüllbarkeitstest

So wir wollen am ende ja auch testen, ob das was wir da gebastelt haben auch wirklich erfüllbar ist
Erstmal wollen wir ein paar begriffe definieren:
- Eine Interpretation $I$ von einem Modell $φ$ heisst Modell von $φ$ , wenn $I ⊨ φ$ gilt.
- Wenn $φ$ ein Model hat, ist $φ$ erfüllbar, sonst nicht
- Wenn jede passende Interpretation von $φ$ ein Modell von $φ$ ist, ist $φ$ allgemeingültig
  - Eine andere Bezeichnung für das ist die Tautologie
- $I$ ist ein Nodell einer Menge prädikatenlogischer Formeln $ϕ$ , falls $I ⊨ φ$ für alle $φ \in ϕ$ gilt.
Die Begriffe "erfüllbar" und "allgemeingültig" haben für Mengen von Formeln $ϕ$ die gleiche bedeutung
Beispiele:
- $\exists x \forall y (R (x) \lor \neg R (y))$ ist allgemeingültig
- $\forall x \exists y (\neg R (x) \land R (y))$ ist unerfüllbar
Anmerkungen:
- Der Zusammenhang zwischen unerfüllbaren und allgemeingültigen Formeln ist genauso wie in der Aussagenlogik:
  $φ$ unerfüllbar $\Leftrightarrow$ $\neg φ$ allgemeingültig
- Ist $φ$ einge geschlossene Formel mit Modell $I = (A, β)$ , so nennen wir auch $A$ ein Modell von $φ$ und schreiben $A ⊨ φ$
Fun-Fact: Der Unterschied zwischen $φ$ und $ϕ$ ist, dass das erste als "die variable" Phi definiert wird und das andere dann als "das normale" Phi

Skolemform

Wir wollen unsere bisherigen Formeln ein wenig vereinfachen, da diese ja teilweise schon sehr schnell sehr komplex werden können
- Damit wollen wir dann die Erfüllbarkeit einfacher überprüfen können
- Wir bemerken: Wenn wir die Erfüllbarkeit einer Formel $φ$ testen wollen, können wir auch "einfach" eine "simplere" Formel $ψ$ aufstellen die sich was Erfüllbarkeit angeht gleich verhält, überprüfen
  - So können wir Quantoren "sparen"
- Jetzt stellen wir uns aber die frage "Wann verhält sich denn eine Formel vor der Erfüllbarkeit gleich wie eine andere"?
  - Erstmal die komischen begriffe:
  - Wir nennen das Erfüllbarkeitsäquivalent
- Zwei formeln sind Erfüllbarkeitsäquivalent, wenn:
  - $φ$ und $ψ$ beide entweder erfüllbar oder beide nicht erfüllbar sind.
Zurück zur Überschrift
Eine prädikatenlogische Formel ist dann in Skolemform wenn sie
- in Pränexform ist
- im Quantoren-Präfix nur Allquantoren vorkommen
- im Quantoren-Präfix keine Variable mehrfach vorkommt
Allgemein gesagt sieht eine Formel in Skolemform also so aus: $\forall x_{1} ... \forall x_{n} ψ$ , wobei $ψ$ quantorenfreii ist
Ein Beispiel
Wenn wir die Skolemregel anwenden, können wir u.U. Existenzquantoren die "erfüllbarkeitsäquivalent" sind aus unserer Formel entfernen

Die Skolem-Regel

Ist $φ = \forall x_{1} \forall x_{2} ... \forall x_{k} \exists y ψ$ und kommt das Funktionssymbol $f$ in $ψ$ nicht vor, so ist die Formel $\forall x_{1} \forall x_{2} ... \forall x_{k} ψ [y / f (x_{1}, ..., x_{k})]$ erfüllbarkeitsäquivalent zu $φ$
Bemerkungen dazu:
- $ψ$ darf weitere Quantoren enthalten
- steht der $\exists$ -Quantor am Anfang $(k = 0)$ , so wird $y$ durch eine Konstante ersetzt.
  - Wir erinnern uns: Konstanten sind eigentlich $0$ -Stellige funktionen.
ToDo: 26

Übung 06

Aufgabe 1)

Relationssymbole

$N (x)$ : $x$ ist eine Nutzernummer
$P (x)$ : $x$ ist Premiumnutzer
( $R (x)$ : $x$ ist reserviert) $\leftarrow$ Das hier ist, da wir später auch eine weitere Relation R haben doppelt, und deswegen nicht mehr zwingend notwendig
$K (x, y)$ : Die Kategorie von Sitzplatz $x$ ist $y$ / $k (x)$ ist die Kategorie von Sitz $x$
$S (x)$ : $x$ ist ein Verfügbarer Sitz
$R (x, y)$ : Person $x$ reserviert Sitzplatz $y$

Konstantensymbole

$b$ : ist der Bürgermeister
$s$ : ist der Stellvertretende Bürgermeister

Grundmenge: ${N 1, N 2, N 1000, ..., N 1003, S 1, ..., S 100, K 1, K 2, K 3}$

$N = {N 1, N 2, N 1000, ..., N 1003}$ Nutzer
$P = {N 1, N 2}$
$S = {S 1, ..., S 100}$
$R = {(N 1, S 16), (N 2, S 17)}$
$k (x) = ⎩ ⎨ ⎧ K 1, S 1 \leq x \leq 20 K 2, S 21 \leq x \leq 70 K 3, S 71 \leq x \leq S 100 0 sonst x sonst x \in {S 1, ..., S 20} x \in {S 21, ..., S 70} x \in {S 71, ..., S 100}$
$b = N 1$
$S = N 2$

Der Bürgermeister und sein Stellvertreter sind Premiumnutzer:
- Relation $P (x)$ mit ${b, s}$
Sitze 16 und 17 sind reserviert
- Relation $R (x, y)$ mit $R (s, 17)$ und $R (b, 16)$

C3: Erfüllbarkeit: Grundresolution

Wir schauen uns heute Prädikatenlogisches Folgern an

Wenn wir so tagtäglich durch unser Leben laufen sind wir in einem "Wissensbasierten" system
wenn wir etwas machen, machen wir das oft auf grundlage von vorherigem wissen
z.b. packen wir einen Regenschirm aus, da wir wissen, dass wir nass werden, wenn es regnet
Sowas können wir auch in prädikatenlogischen Formeln ausdrücken
wir verwenden dafür Konstantensymbole und Relationssymboke
Die fakten die wir als "wissen" definieren setzen sich dann aus den atomaren Formeln zusamme
Wir können aber leider nicht annehmen, dass unsere Wissensbasis alle wichtigen Fakten enthält
Dementsprechend ist immer die frage, welche weiteren fakten aus den gegebenen Fakten und regeln folgen also implizit dargestellt werden
Daher stellen wir uns die frage, wie können wir sehen, dass dieser kram überhaupt erfüllbar ist?

Übung 07

Aufgabe 1: Aussagenlogische Modellierung

$D$
$(i) \land (ii) \land ... \land (\lor) \land \neg D \to^{K NF} {{P, \neg F}, {\neg P, F}, {\neg N \neg G}, {P, F, G}, {\neg P, \neg F, D}, {\neg G, D, N}, {\neg D}}$

Aufgabe 2: Modallogik

Web Engeneering

HTML

HTML steht für Hyper Text Markup Language
Das iwie sehr offensichtlich
Wenn wir ein HTML Doc anfangen, muss es mit <!DOCTYPE html> beginnen
<head> Hier werden viele wichtige Dinge aufbewahrt
z.b. auch Metadata wie <meta charset ="utf-8"> -So können wir auch einach mit dem img tag bilder einfügen etc.
- Das sieht dann so aus: <img> src="https://fsr.rub.de/thonk" alt="Nachdenken">
Wenn wir eine große, tolle Tabelle brauchen können wir tabellieren
- Wir haben tables und tabellieren tables

HTML5 seit HTML 5

Da gibt es einige neue coole Tags
Wie z.b. Header, main und Footer um sachen zu ordnen
So auch den NAV-Tag z.b.
Mit dem article können wir z.b. auch eine geschlossene Komposition anzeigen

Tools

Devtools
Editor VSCode
Blah Blah

CSS

Damit wir unseren Websitebesuchern nicht die augen wegbrennen sollten wir unsere Website ein wenig Stylen
Das machen wir mit CSS
Cascading Style Sheets oder so
Damit kann man "schönes" HTML schöner machen
Wir haben Standartmässig sachen die so aussehen:
Selector { Attribute: Value; }
So können wir mehreren elemente mehrere verschiedene Styles zuweisen
Das machen wir, wenn wir z.b. sachen aufeinander stacken wollen oder sowas
Wir können z.b. auch verschiedene eigenschaften auf einmal anpassen, wenn wir das einfach untereinander in die selbe "klammer" einfügen
Die CSS dokumente können wir auch in HTML einbinden (damit wir das dann auch nutzen können)

Einbettung in HTML

Die "erste" option ist den <link> tag zu nutzen:
- <link rel="stylesheet" href="stylesheet.css">
- SO wird das CSS aus einer anderen File importiert, mit der wir dann Global sachen stylen können
Wenn uns das nicht reicht / wir das nicht machen wollen können wir auch mit den Style tags arbeiten
- So können wir z.b. einen <h1> tag mit dem "style" argument erweitern:
- <h1 style="color:green;">Lol</h1>
- Oder wir können innerhalb zwei <style> tags auch einfach "normales" CSS schreiben
Klassenselektor und ID-Selektor
- Wir können mit dem "class" attribut oder mit dem "id" attribut dingen Identifier geben, mit denen wir dann suchen können
- Diese Selektoren fassen dann auf alles was diesen tag hat

JavaScript I

Warum?

Wenn wir sinnvollere Sachen machen wollen die nicht static sites sind, können wir das oft einfach mit JAVASCRIPT evaluieren
Das können wir wie so vieles entweder mit einem script tag direkt inline machen, oder auch aus einer anderen File importieren

Selektoren

in Javascript können wir kram auch oft einfach selektieren usw
So können wir z.b. mit dem document.querySelector("div ul"); was aus einem HTMl doc parsen und dann halt darauf funktionen anwenden
Mit javascript können wir dann z.b. auch eine liste daraus ziehen und dann da durch for-eachen
In javascript gibts immer dinge die komisch sind, aber grundlegend funktioniert das genauso wie jede andere Programmiersprache es auch tut, was ziemlich nice ist
Wichtige Funktionen siehst du hier:

var list = document.querySelector("div ul");

list.forEach(function(list) {
    let listItem = document.createElement("li");
    //do some stuff
    list.appendChild(listItem);
});

Formelsammlung

HTML

Elemente:

<!DOCTYPE html>

<table>
    <tr>
        <th>Yikes</th>
        <th>Yokes</th>
    </tr>
    <tr>
        <td>sol</td>
        <td>les</td>
    </tr>
</table>

CSS

Selektoren:

element: p {}
class: .name {}
id: #name {}
universal: *
child: >
- selektiert nur direkte kinder
sibling: ~
- Teilen die selben eltern
direct sibling: +
- Teilen die selben eltern und folgen direkt
pseudo-class: :
- sachen wie a:visited
pseudo-element: ::
- sachen wie p::first-line
$n$ th child: nth-child(x)
- wie: p:nth-child(2);
- oder: p:nth-child(An+B);
  - $A$ : Schrittweite
  - $B$ : Startwert

Box Model

Aller content steht in einer box
padding (Abstand von innen zum Rahmen)
border (Rahmendicke)
margin (Der abstand ausserhalb vom Rahmen)
das kann auch alles mit CSS angepasst werden

Specific

.applyMargin
- margin-top
- margin-bottom
- margin-right
- margin-left

Scale

height: 30px;
width: 40vh;
vh
vw
%
em (schriftgröße)

Flexbox

justify-content: abstand zwischen den Elementen, x-achse
align-items: abstand zwischen den Reihen, y-achse
flex-wrap: Ob das zeugs wrappen kann
align-items: Wie biel platz die Elemente nutzen (wie)
flex: Wie die Elemente sich bei änderung verhalten

Grid

kann flexibel und absolut bemmessen werden
px, em für absolut
% und fr (free range) für Flexibel
- fr ist oft in kombination mit padding und margin einfacher zu nutzen

Layout

grid-template-columns: Teilt den verfügbaren platz ein
gap, column-gap, row-gap: Definiert abstände
grid-auto-rows: minmax(px, auto): Definieren "ränder"
justify-content, align-items: genau wie vorher
grid-column: x: definiert spalte
grid-row: x/y: definiert (mehrere) reihen

Event Handling

Naja, events halt, die müssen gehandled werden
Die kann man mit element.AddEventListener('event', function() {}, false);ein Event registrieren
So können Events auch mit event.stopPropagation angehalten werden (also die werden dann nicht weiter verteilt)

Javascwipt UwU

Function

function lustigeFunktion() {
    for(let i = 0; i < 5, i++) {

    }
}

Objektos

var y,i;
var person = {
    name: "Bre", 
    lastName: "Brup", 
    alter: 97
}

Scam (auch bekannt als Funktionen in Variablen)

var ops = [addition, substraktion]; // Das sind Funktionen
for (var i = 0; i < ops.length; i++) {
    console.log(operationen[i](2, 2));
}

Typescwipt OwO

Überprüft Types und macht dinge mit denen (krass)

var lol: string

interface Car {
    name: string; 
    year?: number;
    lol: int;
}

function sell(obj: Car) {
    ...
}

sel({name: name: "BEHEMWEH", lol: 23});

enum Direction {
    Up, 
    Down, 
    Left, 
    Right
}

enum Direction2 {
    Up = 1; 
    Down = 2;
    Left = 3; 
    Right = 4;
} // hier kann man am ende alles einfügen

Vue

Templates

Daten speichern wir in der Vue-VM
hier können wir sachen in variablen speichern und später mit {{ variable }} wieder aufrufen
VueDirectives können das dann weiter raussortieren
- v-html
- v-bind:src
- v-on:click
- v-for
Innerhalb der "moustache" schreibweise (das mit den klammern) können wir JS ausführen
Wir können aber auch schon funktionen auf keywords mappen
- Das machen wir in der "computed" sektion der VueVM, damit der code ordentlicher bleibt
- computed: { keyword: function() { ... } }
Wir können aber auch "tolle" sachen modellieren, wie dynamische klassenzuweiseung
- <div v-bind:class="positive: isPositiv, negativ: isNegativ"></div>
  - positiv und negativ sind abhängig von den Wahrheitswerten in den Vars
  - Je nachdem, wird die klasse dann konstruhiert als positiv, positiv negativ o.ä.
Klassen können wir aber auch schon im JS teil definieren
Dann können wir das mit v-bind:class="name" wie gehabt verbinden
Wir können daten auch conditional Rendern, mit den v-if v-else und v-else-if
for-Loops: v-for="item in list" dann einfach weiter mit normalen JS in mustache
Events: v-on:Event="action in JS"
Wir können auch auf methoden verweisen, wenn welche im "methods" teil definiert sind
- methodName: function() {}

Warum n Vue

Kann besser updaten
Realtime & reactive ohne dauernd neuzuladen

Components

Mit denen kann man teile von vue immer wieder neu verwenden
Sprich basically "kleinere" versionen von Vue-VMs
Global efinieren können wir die mit Vue.component("component-name", { data: function() { ... }})
wenn wir das so machen, können wir das ding dann wie ein HTML element nutzen
Lokal, machen wir das, wenn wir die einfach in einer Vue Instanz in der components sektion hinterlegen

Props

Bei einer Statischen website:
Vue.component("component-a", { props: ["name"], template: "<h1>{{name}}</h1>"});
<component-a name="Meme"></component-a>
Props können nur ein Element gleichzeitig beherbergen! bei mehreren, muss ein div eingefügt werden

Dynamische Props

Beispiel

Vue.component("component-a", {
    props:["prop-data"],
    template: '<div class="component-a">
        <h1>{{propData.title}}</h1>
        <p>{{propData.date}}</p>
        <p>{{propData.content}}</p>
    </div>'
});

var vm = new Vue({
    el:"#app",
    data:{
        propData:{
            title: "Hello World",
            date: "06.07.2020",
            content: "Lorem Ipsum"}
}});

<div id="app">
    <component-a
    v-bind:prop-data="propData">
    </component-a>
    <component-a
    v-bind:prop-data="propData">
    </component-a>
</div>

Die dinger haben einen sog. one-way-data flow
Kinder elemente werdne nur von ihreen eltern "mit" geändert
Andersrum gibt es fehler

Emit

Wir können mit $emit (custom-) Events auslösen
Mit denen können wir so auch mit elternelementen kommunizieren
Vue-component('custom-elem', { emits: ['myEvent']})

Dynamische Komponeneten

Ähnlich wie bei conditionals kann man einen componeneten an etwas anderes aufhängen
mit v-bind:is="componente" kann man das machen
mit jeder aktualisierung wird der gesamte Komponent gewechselt

Software Engineering

WS2023/24
Prof. Thorsten Berger

Hausaufgaben

Hier könnt ihr die Code-Hausaufgaben finden!

Rechnerarchitektur | Technische Informatik 1

Prof. Dr. Philipp Niemann
WS 2022/23 & 2023/24

Rechnerarchitektur Zusammenfassung

Eine schriftliche Zusammenfassung des Faches Rechnerarchitektur aus dem Wintersemester 2022/23 von Tobias Rempe im Studiengang Angewandte Informatik (PO20) der Ruhr Universität Bochum.

Turingmaschine

Aufbau

Hat ein unendlich langes Band
Hat einen Schreib- und Lesekopf
und das Programm was das steuert
- Zustände
- So wenn A passiert dann mach B und gehe in zustand C
In der Theorie kann man damit alles Berechenbare Berechnen

The Law's

Moore's Law

Besagt dass sich die Transistordichte jedes Jahr verdoppelt
Allerdings wurden die Bestandteile dann irgendwann so klein, dass es physikalisch nicht mehr möglich war / nicht mehr sein wird alles so eng zusammen zu quetschen, weswegen morees law immer irrellevanter wird
Es wird kontinuierlich schwerer Moores law einzuhalten
- Wir sind jetzt schon im faktor 15 hinterher
Zudem kommen immer mehr herausforderungen hinzu
Absturz ist also vorprogrammiert
- Wir müssen also etwas tun!

Dennard Scaling

Besagt, dass wir trotz steigender Transistordichte einen Konstanten Energieverbrauch erwarten sollen
Da lag er aber leider falsch der Bre
Wie wir sehen haben wir die Energieeffizienz kontinuierlich gesteigert
Deswegen nur bis knapp 2000 anwendbar

Multicore und Amdahl's Law

Neue Prozessoren haben mehrere Prozessorkerne, damit arbeit paralellisiert werden kann
Allerdings ist hier der Performancegewinn begrezt, da nicht alle Programme paralellisiert werden können
Dementsprechend ist immer der Langsamste teil ausschlaggebend für die Geschwindigkeit des Programms

In Anderen Aspekten der Prozessortechnik

Wir entwickeln immer mehr Flexiblere Sachen
Wie man z.b. auch an handys sieht, die immer effizienter und schneller werden.

Rechnersichten

Höhere Sicht eines Rechners.

Wenn wir uns als Programmierer einen Rechner anschauen sehen wir einen schwarzen kasten der das macht was wir von ihm wollen
Es gibt dementsprechend verschiedene Wege Einen Rechner zu sehen, und daher auch verschieden "genaue" Sichtweisen
Am besten stellen wir das mit sog. Schichtenmodellen da.
- Diese sind der Abstraktion nach geordnet, also die "einfachste" ebene ist die ganz oben, und die technischste ganz unten

Modellierung eines RISC-Rechners

(RISC = Reduced Instruction Set Coputer)
Verschidene Ebenen und Sprachen

"Höhere" Programmiersprachen $\to$ 99% des Marktanteils
- C++, Java, Fortran, Rust
Assembler
- Symbolische Notation der bisher vorhandenen Befehle direkt an den Computer
Betriebssystemebene
- "Hintergrunddienste" wie Speicherorganisation, Dateiverwaltung etc.
Maschinensprache
- Die unterste Sprache an die wir so dran kommen
- Befehle sind folgen von 0, 1 also Stromimpulsen
Digitale Ebene
- Also die Hardware Direkt

Modellierung eines CISC-Rechners

(Complex Instruction Set Computer) $\to$ Bekanntester Vertreter x86 bzw. x86_64
Verschiedene Sprachen und Ebenen

Ein CISC Rechner bitete anstelle von "normalen" Instruktionen die in hardware Augewertet werden den sog. Mikrocode.
Mit diesem ist es möglich Komplexere Instruktionen wie mini-programme im Prozessor zu realisieren, sodass sie virtuell ohne kosten ausgeführt werden können und somit wie "in hardware laufen" ohne extra hardware zu konzipieren.
Dise Mikroprogramme sind aus direkten Instruktionen für das Steuerwerk zusammengesetzt und so vergleichbar mit einem "regulären programm", was allerdings tiefer im Prozessor aufbewahrt, und somit deutlich schneller evaluiert und ausgeführt werden kann..
Dadurch ist deutlich flexiberes Prozessorendesign möglich

Virtueller Rechner

Jede Ebene ist ein "virtueller Rechner" $M_{i}$ , zu dem eine Sprache $L_{i}$ gehört.
Programme der Sprache $L_{i}$ werden
- Übersetzt in die Sprache $L_{j} (j < i)$ übersetzt oder
- In die Sprache $L_{j} (j < i)$ Interpretiert
Die Virtuelle Maschine $M_{i}$ trollt den benutzer einfach richtig hart und tut so, als würden die Programme die er in $L_{i}$ geschrieben hat einfach direkt auf Hardware ausgeführt werden

Hirachie: Illustriert

BRE NE HIRACHIE SACHE DIE MAXIMAL DIAGRAMMATISCH IST

Übersetzung versus Interpretation

Übersetzung

Ein $L_{i}$ Compiler ist eine Software die einfach nen Programm was in der Sprache $L_{i}$ geschrieben wurde nimmt, da nen bissl drauf rum haut und dann ein equivalentes Programm ausspuckt welches in der sprache $L_{j} (j < i)$ "geschrieben" wurde ausspuckt.
Wenn $L_{j}$ dann die maschinensprache, also das Binärformat ist, sprechen wir von einem $L_{i}$ -Vollcompiler

Ausführung eines $L_{i}$ -Programms

Wir Trainsformieren das originale Programm in ein äquivalentes $L_{j}$ -Programm $(j < i)$
Dann führen wir dieses massiv krasse $L_{j}$ -Programm aus, nich?

Interpretation

Dat funktioniert nach einem Festen Schema, und das sieht so aus:

$v a r c m d := erste Instruktion des L_{i} Programms; w hi l e (L_{i} -Programm ha t Instruktionen) {c m d_{2} = co n v er t (c m d); e x ec u t e (c m d_{2}); c m d = n \overset{a}{¨} chste Instruktion aus dem L_{i} Programm;}$

Abwägung

Interpreter sind einfacher zu Implementieren als Compiler
- Deswegen auch oft einfacher auf andere Plattformen zu Übertragen
- geeignet für z.b. Prototypen von Programmiersprachen
Compilation ist leider nicht immer möglich
Compilierte (Übersetzte) Programme sind aber (fast) immer schneller als interprätierte Programme
- Es kann Codeoptimierung @ Compiletime verwendet werden
- Und Binäranweisungen werden von hardware ausgewertet und sind dadurch radikal schneller
(vollständige) Compilation ist allerdings auch nicht immer erwünscht
- Da das zu einer Systemabhängigkeit führt, und deswegen nicht einfach auf andere Systeme übertragen werden kann

Performanzmaße eines Rechners

Hierein bild mit sehr viel Performance

Rechnerorganisation: Aufbau und Funktionsweise

Kernbegriffe:

Hardware
- Ja die hardware halt, dein Handy, dein PC, dein dummes Mainboard was vor 3 jahren mal nen stromschlag bekommen hat und deswegen immer weiter failed und deine smartwatch
Software
- Das was die meissten Entwickler schreiben, also der kram der auf deinem Gerät läuft
Firmware
- Der "kleber" der die verbindung zwischen Software und Hardware herstellt, also sowat wie das BIOS.
- Meisstens in ROM (Read only Memory) gespeichert

Hardware VS Software

viel von dem was früher in Software gemacht werden musste kann heute in hardware gemacht werden
- z.b. Ganzzahlige Multiplikation, Division, Floatingpointarithmatic
Allerdings gibt es auch neue Konzepte wie das oben genannte RISC-Konzept
- Hier wird wieder mehr in Software ausgeführt
  - Damit das Instruktionsset so simpel wie möglich gehalten werden kann, um schnelle Übersetzung und Ausführung zu garantieren
- z.b. Ganzzahlige Division

Der Kram zwischen Software und Hardware

Das instruktionsset (Instruction-Set)
Dieses Set bestimmt den befehlssatz mit dem später (wie der name schon sagt) Befehle an den Computer gesendet werden können
Dieses set entscheidet was in hardware direkt gelöst werden kann, und was nur in software gebaut werden kann
Hier ist es wichtig alles genau abzuwägen, weil es zu ineffizienzen und problemen führen kann wenn wir alles in eine richtung schieben.

Exkurs: Hardware / Software Co-Design

Es gibt auch Orte an denen wir sehr spezifische goals haben und die erreichen müssen
z.b. Smart-Home geräte
Die dinger nennt man dann Embedded Devices
- Die müssen ja am ende nicht frei programmierbar sein, deswegen können wir die hardware auf genau diese eine sache die die erledigen müssen zuschneiden
  - Sowas wurde z.b. auch bei alten videospielkonsolen gemacht
Was in Software und was In hardware implementiert wird muss ein sog. "Systemarchitekt" entscheiden, der dann anforderungen Stellt.
Die genaue Implementation wird dann (halb-) automatisch durch diverse Laufzeitanalysen erprobt und Entschieden
Aber insgesamt sollte alles was in software schwer ist weil es z.b. sehr rechenintensiv ist auf Hardware ausgelagert werden

Prinzipieller Aufbau eines Rechners

Hier wieder ein Extrem krasses bild was darstellt wie krass gut nen Computer aufgebaut ist

John von Neumann (1903-1957)

(es geht weiter mit Geschichte!!1!)

Der bre hat den aufbau von Modernen Rechnern sehr stark beeinflusst, u.a. weil er einfach nen krasser Mathematiker war
Das sog. von-Neumann-Prinzip was (schocker) er erfunden hat beruht auf den folgenden 4 Punkten:

voll-elektrischer Rechner
binäre Darstellung der Daten
Benutzung einer Arithmetischen Einheit
Benutzung eines Steuerwerkes
Interner Daten- und Programmspeicher

Falls ihr in der 1. Klasse aufgepasst habt merkt ihr, dass das da 5 Punkte sind. SUPER GEMACHT! 3 Bonus Gummi-Punkte!

Der Arbeitsspeicher (Hauptspeicher)

Ja in dem ding können wir sachen speichern an denen wir gerade arbeiten (ja was nen wunder nich)
der besteht aus $n$ (also praktisch beliebig vielen) Speicherzellen
Eine Speicherzelle
- speichert immer $\underline{eine}$ Information bestehend aus $k$ Bit. $k$ wird dabei die Wortbreite des Speichers genannt.
  - $k$ kann 8, 16, 32, 64 oder noch viel mehr Bit groß sein
  - Allerdings arbeiten unsere Modernen rechner und geräte fast Exklusiv mit 64Bit Großen $k$ 's
- Hat eine Adresse mit der sie identifizierbar ist.
  - Diese liegt im bereich $[0.. n - 1]$
- Nix kann kleiner sein als Wortbreite, also ist eine speicherzelle die kleinste adressierbare einheit des speichers

Der Prozessor (+ Cache)

Dat ding besteht in seiner Einfachsten Form aus

Steuerwerk (Control Unit)
- indem das ding die richtigen Signale an die richtigen Sachen schickt bewegt sich der nächste Maschinenbefehl aus dem Hauptspeicher in eins der Arbeitsregister im Cache
- Dann sendet der noch mehr von diesen Signalen um die gelesene Maschineninstruktion auszuwerten
- Dann führt er diese Instruktion durch das senden weiterer Signale aus
Recheneinheit (Arithmethic Logic Unit - ALU, Datenpfad)
- führt die Teilschritte (Vergleiche, Move, Addition, etc.) gemäß der Signale aus.
Registerbank
- Beinhaltet die sog. Register
- Die dinger speichern daten die der Prozessor in diesem Moment benötigt
- Denn auf Register kann ohne Wartezyklus direkt vom Rechenwerk aus Zugegriffen werden

Register des Prozessors

Hier werden die sachen aufbewahrt, die schnell vom Prozessor gebraucht werden

Art der Information	Speicherort	Name	Acronym
aktuell abzuarbeitender Befehl	Befehlsregister	Instruction Register	IR
Adresse des als nächstes abzuarbeitenden Befehl	Befehlszähler	Program Counter	PC
Adresse im RAM ab der Daten gespeichert werden können	Stackpointer	Stackpointer	SP
von der ALU zu verarbeitende Daten	Arbeitsregister	General Purpose Register	GPR

Prinzipielle Arbeitsweise eines Prozessors

Fetch-Decode-Execute-Zyklus
- Fetch
  - Hol dir den nächsten Maschinensprachebefehl aus dem GPR und speicher ihm im IR a. Die benötigte Adresse steht im PC
- Decode
  - Analysiere (Decode) die daten und lade dir alle wat du gerade brauchst
- Execute
  - Führ dat wat de dir da zusammen gesucht hast aus und speicher dat erjebnis ab (im Hauptspeicher)
- REPEAT!

Assembler

Der kram ist die letzte ebene vor 1en und 0en
Befehle sind meist elemetare operation (also so simpel wie es geht)
Du hast die Register für datenmanipulation, damit du damit halt arbeiten kannst nich
Operanden werden durch verschiedene Adressierungsarten bestimmt
Wir verweisen zurück auf die Ebenenansicht
wir schauen uns die jetzt nochmal genauer an

Ebenensicht : The SQL

Höhere Programmiersprachen
- C++, Java, Fortran, Rust, Son kram
Assembler
- symbolische Notation der bisher vorhandenen Befehle
Betriebssystemebene
- zusäzliche util Dienste wie Speicherorganisation, Dateiverwaltung
Maschinensprache
- unterste frei zugängliche Sprache Befehle sind am ende Folgen über 0 und 1
Mikroprogrammebene
- Instruktionen zum setzen von Steuersignalen
- Hier werden die Instruktionen in Maschinensprache auseinander genommen und in die Steuersignale übersetzt
digitale Ebene
- die eigentliche Hardware

Assembler Höhere Programmiersprachen

Assembler	Höhere Programmiersprachen
Zusammenhang ist oft schwer erkennbar	Man kann den Code (meisstens) gut lesen und funktionen dem kontext entnehmen
Einfache Befehle	Komplexe Sprachkonstrukte
Direkter Speicherzugriff und volle Kontrolle	Konstruktion komplexer Datentypen und limitierte Kontrolle
Maschinenabhängige Programme	Programme die weitgehend unabhängig von Maschinen sind

Befehlssatz

Der Befehlssatz eines Prozessors wird beim Entwurf festgelegt

Kompromiss:
- Wünsche aus Anwendersicht
- Technische Machbarkeit
Von bedeutung sind dabei
- Bitbreite zur kodierung eines Befehls
  - Also wie viel platz ein Befehl verbrauchen soll
  - und im Umkehrschluss auch wie viele Befehle verwendet werden können
- Zusätzliche Adressierungsarten von Befehlen

Klassen von Befehlen

Da gibts janz viele, wir betrachten hierbei z.b.. sowas wie

Arithmetische Befehle (Rechnen-Dinger)
- Add, Sub, Mult, Div, Srl, ...
Datentransportbefehle (Ja dinger zum Daten transportieren halt)
- Load, Store, Move, Push, Pop, I/O, ...
Logische Befehle (Halt so dings dinger zum vergleichen)
- And, Or, Not, ...
Bitverarbeitende Befehle (So zeuchs was iwas iwo rein schreibt)
- Setzen, Rücksetzen von bits, Statusflags, ...
Sprungbefehle (So GEH ZU BEFEHL 210,7 BRE!!!!!)
Systembefehle (Ja du da fällt mir gerade kein Beispiel ein)

Exkurs: RISC-V

Wofür steht RISC-V?

Reduced
Instruction
Set
Computer
5

Wat is das überhaupt

Eine Modulare 32/64/128-Bit RISK Architektur
- Basisinstruktionen RVd $I$ ( $d = 32, 64, 128$ )
- Dazu gibt es Optionale Instruction-Set-Extentions (Befehlssatzerweiterungen) u.a:
  - RVd $M$ : Multiplikation & Division
  - RVd ${F ∣ D ∣ Q}$ : Floating-Point Arithmetic mit einfacher $(F)$ , doppelter $(D)$ und vielfacher Genauigkeit $(Q)$
- LOAD/STORE-Architektur:
  - Es kann lediglich durch LOAD- bzw. STORE-Befehle auf den RAM zugegriffen werden
  - Alle anderen Befehle müssen mit den Registern auskommen

Die verschiedenen Register

32-Bit Datentyp, hat eine kapazität von "einem Wort"
Konventionen legen fest, wie diese Register heißen und wie sie verwendet werden sollen:
- 12 Register für Variablen des Quellprogramms: $s 0, ..., s 11$
- 7 Register für temporäre Variablen: $t 0, ..., t 6$
Allerdings müssen diese Konventionen nicht zwingend beachtet werden
Derartige Konventionen sind aber notwendig, wenn mehrere, potentiell getrennte, Programmteile zusammen laufen können

Register	Name	Verwendung
$x 0$	$zero$	Konstante 0
$x 1$	$r a$	Rücksprungadresse
$x 2$	$s p$	Stackpointer
$x 3$	$g p$	Globaler Pointer
$x 4$	$tp$	Threadpointer
$x 5$ - $t 7$	$t 0$ - $t 2$	Temporäre Register
$x 8$	$s 0$ / $f p$	Registerzwischenspeicher oder Framepointer
$x 9$	$s 1$	Registerzwischenspeicher
$x 10$ - $x 11$	$a 0$ - $a 1$	Funktionsargumente und Rückgabewerte
$x 12$ - $x 17$	$a 2$ - $a 7$	Funktionsargumente
$x 18$ - $x 27$	$s 2$ - $s 11$	Registerzwischenspeicher
$x 28$ - $x 31$	$t 3$ - $t 6$	Temporäre Register

Beschränkte Anzahl von Registern
- Diese sind leider unzureichend um die Variablen von "echten" Programmen aufzunehmen
$\to$ Deswegen müssen größere, oder größere Mengen von Variablen (z.B. Arrays) im Speicher abgelegt werden.

Arithmetische Befehle

Befehle für Festkommaarithmetik (RV32 $IM$ )
- mit oder ohne Vorzeichen
Befehle für Gleitkommaarithmetik (RV32 $F$ )
- Im prozessor integriert
- Emulation durch Zerlegung in elementare Operationen
Vergleichsbefehle
Schiebe und Rotationsbefehle

Rechenbefehle

Instruktion	Operation	Resultat
ADD $R_{d es t ina t o n}$ , $R_{src 1}$ , $R_{src 2}$	Add	$R_{d es t ina t o n} := R_{src 1} + R_{src 2}$
ADDI $R_{d es t ina t o n}$ , $R_{src}$ , $I mm$	Add immediate	$R_{d es t ina t o n} := R_{src} + I mm$

Analog dazu gibt es SUB
Andere Assemblersprachen lassen auch Speicherinhalte als Operanden zu (z.b. Einige CISC Sprachen)

Vergleichsbefehle

Instruktion	Operation	Resultat
SLT $R_{d es t ina t o n}, R_{src 1}, S rc 2$	Set less than	$R_{d es t ina t o n} := {1, falls R_{src 1} < S rc 2 0, sonst$
SLTU $R_{d es t ina t o n}, R_{src 1}, S rc 2$	SLT unsigned	$R_{d es t ina t o n} := {1, falls R_{src 1} < S rc 2 0, sonst$

Schiebebefehle

Instruktion	Operation	Resultat
SLL $R_{d es t ina t o n}, R_{src 1}, S rc 2$	Shift left logical	$R_{d es t ina t o n} := R_{src 1} << S rc 2$
SRL $R_{d es t ina t o n}, R_{src 1}, S rc 2$	Shift right logical	$R_{d es t ina t o n} := S rc 1 >> S rc 2$
SRA $R_{d es t ina t o n}, R_{src 1}, S rc 2$	Shift right arithmetic	$R_{d es t ina t o n} := R_{src 1} \cdot 2^{- S rc 2}$

Notation: $S rc 2$ kann Register oder Immediate sein

Ladebefehle

Instruktion	Operation	Resultat
LUI $R_{d es t ina t i o n}, I mm$	Load upper immediate	$R_{d es t ina t o n} := I mm e d ia t e [31 : 12]$
LW $R_{d es t ina t i o n}, R_{ba se}, O ff s$	Load word	$R_{d es t ina t o n} := M e m ory [R_{ba se} + O ff s]$
LB $R_{d es t ina t i o n}, R_{ba se}, O ff s$	Load byte	$R_{d es t ina t o n} := M e m ory [R_{ba se} + O ff s]$

Speicherbefehle (Memory)

Instruktion	Operation	Resultat
SB $R_{src}, R_{ba se}, O ff s$	Store byte	$M e m [R_{ba se} + O ff s] := R_{src} [7 : 0]$
SW $R_{src}, R_{ba se}, O ff s$	Store word	$M e m [R_{ba se} + O ff s] := R_{src}$

Logische Befehle

Instruktion	Operation	Resultat
AND $R_{d es t ina t i o n}, R_{src 1}, S rc 2$	And	$R_{d es t ina t i o n} := R_{src 1} \land S rc 2$

BITWISE OR
Analog dazu OR, XOR (Exclusive Or)

Sprungbefehle

Werden verwendet um den ablauf von Programmen zu steuern
Klassifikation
- bedingte / unbedingte Sprungbefehle
  - Sprung erfolgt relativ zum Programmzähler oder absolut
- Unterprogrammaufrufe (wie Subroutines oder so)
- Rückker zum aufrufenden Programmabschnitt (wie beim ende einer Subroutine)
  - Nennt man auch "unterprogrammbeendigung"
- Unterbrechung (Interrupt)

Unbedingte Sprünge: (pc: Program Counter)

Instruktion	Operation	Resultat
JAL $R_{d es t ina t i o n}, o ff s$	Jump and Link	$R_{d es t ina t i o n} := p c + 4$ , Sprung zu $p c + o ff s$
JALR $R_{d es t}, R_{ba se}, o ff s$	JAL Register	JAL zu Adresse $R_{ba se} + o ff s$

Bedingte Sprünge

Instruktion	Operation	Resultat
BEQ $R_{src 1}, R_{src 2}, o ff s$	Branch Equal	Sprung, falls $R_{src 1} = R_{src 2}$
BNE $R_{src 1}, R_{src 2}, o ff s$	Branch not Equal	Sprung, falls $R_{src 1} \neq = R_{src 2}$
BLT $R_{src 1}, R_{src 2}, o ff s$	Branch Less Than	Sprung, falls $R_{src 1} < R_{src 2}$
BGE $R_{src 1}, R_{src 2}, o ff s$	Branch Greater Equal	Sprung, falls $R_{src 1} \geq R_{src 2}$
BLTU $R_{src 1}, R_{src 2}, o ff s$	Unsingned BLT	Sprung, falls $R_{src 1} < u (R_{src 2})$
BGEU $R_{src 1}, R_{src 2}, o ff s$	Unsingned BGE	Sprung, falls $R_{src 1} \geq u (R_{src 2})$

Systembefehle

In RISC-V

Instruktion	Operation
ECALL	Systemaufruf

Control-/Statusregister (CSR):

Instruktion	Operation
CSRR{W\|S\|R} $R_{d es t ina t i o n}, R_{src}, csr$	Lese bzw, überschreibe Control- und Statusregister

Dat gut für
- Fehlerbehandlung(Exceptions)
- das Steuern vom Prozessorverhalten

Beispiele für Systembefehle

Rechenbefehle

Bedeutung	RISC-V Instruktion
$a = a + b$	$a dd a, a, b$
$a = a - b$	$s u b a, a, b$

Längere Ausdrücke müssen vom Anwender bzw. dem Compiler in eine Reihe von einfacheren operationen aufgeteilt werden
$a = b + c + d + e ⎩ ⎨ ⎧ a dd a, b, c a dd a, a, d a dd a, a, e$
Wenn nötig kann man auch temporäre Variablen einführen
$f = (g + h) - (i + j) ⎩ ⎨ ⎧ a dd t 0, g, h a dd t 1, i, j s u b f, t 0, t 1$
Befehl $f = (g + h) - (i + j)$
Annahme: Variable $g$ befindet sich im Register $s_{1}$ , $h$ im Register $s_{2}$ , $i$ im Register $s_{3}$ und $j$ im Register $s_{4}$ . Das Ergebnis soll im Register $s_{0}$ gespeichert werden.

(# Ist hier der Kommentar-Operator)

$a dd a dd s u b t_{0}, s_{1}, s_{2} t_{1}, s_{3}, s_{4} s_{0}, t_{0}, t_{1} # # # t_{0} = g + h t_{1} = i + j f = (g + h) - (i + j)$

Logische Befehle

$s ll or an d i an d i s_{1}, s_{0}, 2 s_{1}, s_{1}, s_{0} s_{1}, s_{1}, 15 s_{2}, s_{1}, 0 # s_{1} = 0...00100100 # s_{1} = 0...0010 \underline{1} 10 \underline{1} # s_{1} = 0...00001101 # s_{1} = 0...00000000$

Sprungbefehle

C/C++ Programm:

if (i == j) {
    f = g + h;
} else {
    f = g - h;
}

RISC-V Assembler-Programm:
Annahmen: Variablen $f, g, h, i, j$ in $s_{0}, s_{1}, s_{2}, s_{3}, s_{4}$

$El se : E x i t : bn e a dd j s u b ... s_{3}, s_{4}, El se s_{0}, s_{1}, s_{2} E x i t s_{0}, s_{1}, s_{2} # # # # if (i != j) g o t o El se f = g+h g o t o E x i t f = g-h$

Hier sind $El se$ und $E x i t$ Labels (Sprungmarken) zu denen gesprungen werden kann

Anderes Beispiel:

Annahmen: Variablen $i, k$ in $s_{3}, s_{5}$ Ebenso: Basisadresse von $s a v e$ in $s_{6}$

Hier ist ein massiv weiteres Beispiel für Assembly

Datentransportbefehle

$A [12] = h + A [8]$
Annahme: $A$ ist ein Array vom Datentyp Wort. Die Variable $h$ steht im Register $s_{2}$ , die Basisadresse von $A$ steht im Register $s_{3}$

$lw a dd s w t_{0}, t_{0}, t_{0}, 32 (s_{3}) s_{2}, t_{0} 48 (s_{3}) # # # t_{0} = M e m ory [s_{3} + 32] t_{0} = h + A [8] M e m ory [s_{3} + 48]$

Datentransportbefehle

Transport von Daten zwischen Quelle und Ziel
Quelle und Ziel sind entweder im Hauptspeicher oder in den Registern
Übertragung ist auch zwischen den I/O-Schnitstellen und Registern möglich
Zudem ist Transport nicht wirklich das Richtige Wort, Weil eigentlich nicht wirklich viel von der Quelle entfernt wird

Adressierungsarten

(Keine RISC-V Befehle)

Implizite Adressierung
- Dat Ziel wird durch den Befehl bestimmt
  $L O A D A R_{src} A := R_{src}$
Unmittelbare Adressierung
- Operand wird als Wert angegeben
  $L I R_{d es t ina t i o n}, 4 R_{d es t} := 4$
absolute (direkte) Adressierung
- Operand ist Inhalt der angegeben Adresse
  $L W R_{d es t}, R_{src} R_{d es t} := M e m [R_{src}]$
indirekte Adressierung
- Operand ist Inhalt des Zeigers an der angegeben Adresse
  $L W R_{d es t}, R_{src} R_{d es t} := M e m [M e m [R_{src}]]$
indizierte Adressierung
- $L B R_{d es t}, 4 (R_{src}) := M e m [R_{src} + 4]$

Unterprogramme

(Subroutines oder so)

Prinzipieller Ablauf, wie kann man sich dat vorstellen
- Der Kontrollfluss wird an eine Subrutine abgegeben
- Diese Prozedur macht wat sie machen soll
- Und dann wird der Kontrollfluss zurück an die aufrundende Funktion geworfen
RISC-V-Unterstützung für Prozeduraufrufe
- es gibt ein spezielles Register für die Sicherung der Rücksprungadresse: $r a$
- Sprunginstruktionen
  - $ja l$ (Jump and Link)
    - Speichert die Rücksprungadresse in $r a$ und springt dann zur Adresse der Subroutine
  - $j r$ (Jump Register)
    - springt zur Adresse, die im angegebenen Register steht, d.h. $j r r a$ springt zurück zum aufrufenden Programm
- Prozeduren brauchen im Allgemeinen Argumente und leifern Resultate
  - Dafür gibt es in RISC-V folgende Konvention:
    - 8 Register für Argumente $a_{0}, ..., a_{7}$
    - 2 Register für Resultate $a_{0}, a_{1}$

Beispielprogramm: $n!$

Gegeben: Wert $n$ in Register $a_{0}$ , Rückgabe in $a_{1}$

Beispielprogramm, n! ausrechnet

Instruktionskodierung

Wir haben bisher die Instruktionen "nur" in Assemblersprache notiert, der Prozessor versteht den kram aber leider so garnich
Detwegen müssen wir iwas aus dem kram machen, was der Prozessor verstehen kann.
Was kann der verstehen? genau! binär, deswegen müssen wir dat jz binär kodieren
Das nennt man (... Trommelwirbel) Instruktionskodierung (Wasn Schocker)

add $t_{0}, s_{1}, s_{2} \to 00000001001001001000001010110011$

Bei RV32 sind alle Instruktionen 32 Bit lang!
- Da die ganzen Instruktionen allerdings verschieden viele Operanden haben, gibt es verschiedene Instruktionsformate:
  - R-Typ
  - I-Typ
  - S/B-Typ
  - U/J Typ

Instruktionsformat R-Typ

Instruktionsformat R-Typ (Register-Format) wird für Arithmetische Instruktionen verwendet

Hier ist ne Grafik die garnicht zu 100% aus den Folien geklaut ist

Instruktionsformat I-Typ

Das Immediate-Format wird verwendet für

Immediate-Versionen der arithmetischen und logischen Instruktionen
Load-Instruktionen und Systembefehle

Hier ist noch ne krasse Grafik vom Niemeier

$imm$ ist eine signed 12-bit Zahl im 2er Kimplement und kann dadurch Werte zwischen $- 2^{11}$ und $2^{11} - 1$ annehmen
Beispiel:

hier noch ein massiv besseres bld für ityp

Instruktionsformat S/B-Typ

Das Store-Format wird, wie man sich wohl schion denken kann, für Store-Befehle verwendet

Krasses bild was den aufbau für das ding da zeigt

offset ist eine signed 12Bit-Zahl auf die der Wert aus Register $r s_{2}$ addiert wird um die effektive Speicheradresse zu bekommen

mehr krasse beispiele

Beim B-Typ - also Branch-Format für bedingte Sprünge - gibt es eine andere interpretation der offset bits

Instruktionsformat U/J-Typ

Das Upper-Format wird für Spezielle Load-Befehle verwendet

Krasses beispiel für uj dings

$imm$ ist eine 32-Bit Zahl deren 20 höchstwertige Bits
$imm$ [31:12] ins Register $r d$ geladen werden

Beim J-Typ, also unbedingten Sprüngen wird die effektive Sprungadresse aus $imm$ [20:1] (interpretiert als signed 20-bit Zahl) konstruiert

Assembler Maschinenschprache

Assembler	Maschinensprache
Symbolische Bezeichnung von Befehlen, Adressen (label) und teils der operanden	Binäre Darstellung von Befehlen (Op-Code) Adressen und Operanden in einem Datenwort
Ein-/Ausgabe-Routinen eines etwaigen betriebssystems könenn verwendet werden	Bibliotheken für komplexe Befehl(sketten)
Programme müssen vor der Ausführung assembliert (also zu Maschinensprache übersetzt) werden	Programmen werden direkt ausgeführt, da wir praktisch eine "binary" von hand schreiben

Verarbeitung einer Instruktion (RISC-V)

Im Folgenden bereits um Pipelining erweitererte CPU
- Pipelining kommt später
Die verarbeitung läuft Stufenweise
- Wir holen uns den befehl
- Decoden den kram erstmal / Holen uns den Operanden
- Befehl ausführen
- Speicherzugriff (wenn wa wat schreiben oder lesen wollen)
- Ergebnis in Register schreiben
Hier ist zu beachten, dass es je nach prozessor anders aussehen kann

Aufbau eines RISC-V Prozessors

Hier eine schematic wie der RISC-V Prozessor aussieht Hier ein Weiteres Bildschin mit anderen krassen instruktionssachen

Befehlssätze und Optimierungen

Die Extreme:
CISC-Rechner und RISC-Rechner

CISC - Complex Instruction Set Computer

Großer Satz von Maschinenbefehlen
- Diese können teilweise sehr Spezifische und Komplexe operationen selbstständig ausführen
Sehr unterschiedliche Ausführungszeiten, also nicht wirklich regelmäßig
Das system wird durch ein sog. Mikroprogramm im Prozessor gesteuert, nicht durch direkte Hardware.
Zudem war der erste "moderne" Rechner (IBM 369) ein CISC-Rechner

Was spricht für CISC?

Komplexe Befehle schliessen eine Lücke zwischen den programmiersprachen und der hardware
- es gibt "direktere" übersetzungen
Komplexe Befehle verringern den Ramverbrauch, da alles praktisch "vorprogrammiert" ist und nicht erst in viele kleine operation zerbrochen werden muss
Dadurch kann es auch zu einem geschwindigkeitsboost kommen, da weniger auf den "langsamen" Speicher zugegriffen werden muss
Komplexe befehle können vom Compiler einfacher aus geschriebenem programmcode hergeleitet werden
Je mehr der Computer in hardware / intern Regeln kann, desto zuverlässiger "ist" er, denn hardware ist angeblich zuversichtlich
- Ist allerdings nicht ganz richtig, da fehler die hier auftreten, fast nicht zu beheben sind ohne neue hardware zu beschaffen

Was spricht dagegen?

Viele Programmspeicher-Zugriffe können aufgrund von Cache strategien sehr schnell und effizient ausgeführt werden
- Dementsprechend brauchen wir keine "riesiegen" mikroprogramme
Hardware ist, wie oben schon gesagt, nicht zuverlässiger als Software, zum großen teil auch wegen der fehlenden debugging-möglichkeit
Die komplexen befehle die der compiler "einfach" nutzen könnte werden von modernen Compilern kaum noch genutzt, da sie oft sehr spezifisch sind und gewisse hardware voraussetzen

Eine Statistik für CISC-Rechner (ca.1990)

Wenn wir uns CISC Rechner anschauen, denken wir an die Intels und AMDs auf dieser Welt, irgendwie klar weil sie die einzigsten firmen auf der Welt sind die die x86 Architektur verwenden dürfen, die, wie oben erläutert, die weit verbreiteteste CISC Architektur die wir haben ist.

Hier eine krasse Statistik die zeigt wie falsch die leute at itel damals lagen

Wenn wir uns obige Statistik anschauen, sehen wir, dass mehr als 90% aller Operationen die ein x86 (oder auch x86, x86_64 (auch bekannt als AMD64 weil AMD als erste Firma einen funktionierenden 64-Bit prozessor bauen konnte)) ausführt "einfache" Befehle sind, die nicht weiter heruntergebrochen werden können und deswegen auch direkt in Hardware gehandled werden könnten. Da dies bei CISC allerdings nicht passiert, wird effizienz auf dem tisch liegen gelassen, um die restlichen ~10% zu supporten.

RISC - Reduced Instruction Set Computer

Einfache Befehle
- Deswegen ein insgesamt kleinerer Befehssatz
Jeder Befehl ist in einem Verarbeitungsschrit ausführbar
- Effizienz durch berechenbarkeit
großer interner Registersatz
Leistungsfähige Speicherhirachie
Dadurch, dass das System nicht mehr durch Mikrocode Kontrolliert wird, kann ein Fest verdratetes Steuerwerk verwendet werdn
Dadurch wird das System schneller und effizienter, einfach weil Hardware in so ziemlich jedem fall schneller ist als software.

Bekannte Beispiele für RISC-Prozessoren sind

Mips R2000/3000 (1982-89)
IBM Power
IBM PowerPC
Apple M
Apple A
Apple T
Quallcomm Snapdragon

RISC VS CISC

Hier ein massiv cooles bild was die Performance und Zyklenanzahl zwischen RISC und CISC vergleicht

Man sieht hier vor allem, dass RISC was Zyklen / Operation angeht um einiges Effizienter agiert als CISC in vergleichbaren fällen.
Ein Großes Element ist natürlich auch der Unterschied zwischen Hardware und Software als ausführungsplattform, da Hardware logischerweise um einiges schneller und effizienter ist.

Hier mal ein paar konkrete beispiele:

Power PC (IBM, RISC)
- Operanden aus dem Hauptspeicher kommen nur von load-, store-, branch- oder cache-Befehlen vor
- Drei Modi der Adressberechnung:
  - Registerinhalte + Konstante
  - Summe zweier Register
  - Registerinhalt
Pentium 4 (Intel, CISC)
- Mögliche Operanden für beliebige Befehle
  - Konstante (natürlich nicht für Ergebnisse)
  - Registerinhalt
  - Speicherplatz
  - I/O Port
- Adressberechnung:
  - Speicheradresse = Segment + Offset
  - Segment steht in einem speziellen Register
  - Offset wird entsprechend der folgenden Tabelle berechnet

Designprinzipien für Rechner

Was sind die Schlüsseloperationen für das was wir bauen wollen
Wie soll der Datenpfad aussehen? (also dat rechenwerk + die Verbindungen zum RAM etc.)
Was brauchen wir für Maschinenbefehle in dieser Architektur.
- Wie können wir dafür sorgen, dass alles was wir brauchen möglichst in Hardware und ohne mikroprogramme in einem Zyklus ausführbar ist
Wie können wir den Befehlssatz erweiterbar machen, aber so, dass bei erweiterung die Maschine nicht langsamer wird

Pipelining

Wat dat überhaupt?

Wir visualisieren uns dat mal mit nem massiv coolen Beispiel:
Wir kommen nachhause und finden einfach nen riesigen haufen Wäsche die AUF EINMAL dreckig geworden ist.

Nun Reflektieren wir mal darüber, wie wir die wäsche wieder sauber bekommen. Unserer normaler Workflow ist wie folgt:

Wir nehmen die Dreckige Wäsche und stecken sie gewaltsam in die Waschmaschine die dann etwa 30 Minuten Läuft
Wir werfen die gewaschene Wäsche in den Trockner der dann ebenfalls wieder 30 Minuten läuft
Dann müssen wir die Kleidung Bügeln und falten, was wieder etwa 30 Minuten dauert
Und zuletzt müssen wir unsere nun wieder saubere Wäsche nehmen und sie in den schrank räumen.

Wir werfen einen Blick auf den unmöglich großen Berg an plötzlich dreckiger wäsche und realisieren, dass dat nich alles in unsere Waschmaschine passt. Wir müssen sogar warscheinlich insgesamt 4 Mal waschen. Das dauert, wenn wir alles hintereinander machen, ja knapp 8 Stunden. Das ist nicht so gut, und genau hier kommt pipelining ins spiel!
Denn wenn wir mehrere Verschiedene Arbeitsschrotte auf einmal bzw. gleichzeitig erledigen können reduzieren wir die zeit von etwa 8 auf 3 $\frac{1}{2}$ Stunden Reduzieren!
Wie wir das machen zeigt dieses Bild:

Hier ein bild was das oben beschriebene Phänomen beschreibt und dadurch die beschreibung beschreibender macht

Das ist ja alles Schön und gut, aber wie machen wir das Im computer?!

Damit wir Pipelining im Datenpfad anwenden können müssen wir die abarbeitung der diversen Maschinenbefehle in mehrere teilschritte (Phasen) aufteilen die idealerweise alle die gleiche dauer haben.
Bei der Aufteilung ist vor allem der bestehende Befehlssatz und die zur verfügung stehende Hardware zu beachten, da die beiden elemente genau aufeinander abgestimmt sein müssen, wenn wir ein effizientes system entwickeln wollen.
Hier ein Beispiel für die Abarbeitung in 5-Schritten:
- Befehl-Holphase, auch bekannt als Instruction-Fetch
- Dekodierungsphase, hier lesen wir die Operanden aus Registern
- Ausführung / Adressberechnung, hier führen wir den befehl aus und berechnen wo wirs hin speichern müssen
- Speicherzugriff, hier wird alles gelesen was wir vom Speicher wollten
- Abspeicherphase (result write back phase) Hier schreiben wir alles zurück in den speicher, was wir berechnet haben
Bei CISC Pipelinig ists schwierig die genaue dauer zu bestimmen, da mikroprogramme in der Dekodier und Ausführungsphase unterschiedlich lang brauchen können und die komplexität sehr unterschiedlich sein kann

Hier ein Beispiel wie man den Datenpfad aufteilen kann:

Krasse Graphik von dem Datenpfad eines RISC-V Prozessors die in 5 segmente unterteilt ist

Speedup

Annahmen:
- Abarbeitungszeit eines Befehls ohne Pipelining: $t$
- wir haben $k$ pipelinestufen mit gleicher lauftzeit der Stufen
- Laufzeit einer Stufe ist also $\frac{t}{k}$
Beschleunigung $m$ Bei ausführenden Instruktionen
- $m = 1$ Laufzeit mit pipeline = $k \cdot \frac{t}{k} = t$
- $m = 2$ Laufzeit mit Pipeline = $t + \cdot t k = (k + 1) \cdot \frac{t}{k}$
  - Beschleunigung um Faktor $2 \cdot \frac{k}{( k + 1 )}$

$m \geq 1$ Laufzeit mit Pipeline: $t + (m - 1) \cdot \frac{t}{k}$
Laufzeit ohne Pipeline: $m \cdot t$

Beschleunigung um: $\frac{m \cdot t}{t + ( m - 1 ) \cdot \frac{t}{k}} = \frac{m \cdot k}{m + k - 1} = \frac{k \cdot ( k - 1 )}{m + k - 1}$

Ergebnis:

für $m >> k$ nähert sich der Speedup also der Anzahl $k$ der Pipelinestufen

Es wurde vorausgesetzt, dass sich die Ausführung der BEfehle ohne weiteres aneinanderreihen ("verzahnen") lässt. Dies ist in der Praxis mit immer der Fall $\to$ Hazards

Hazards

Massiv krasse Gefahren würd ich mal sagen (boah krass dat hat sich ja sogar gereimt)

Hier ist ein weiteres massiv krasses game

Hier tritt ein Problem auf! Denn wenn pipelining verwendet wird kann es sein, dass der ADD Befehl in diesem Beispiel nicht auf den Wert in R1 zugreifen kann wenn man die Pipeline nicht stoppt

Dat kann man lösen indem man NOPs einfügt, also No-Operation

Ein NOP könnte erspart werden, wenn der load befehl direkt am ende der Execute-Phase das ergebnis im angegebenen Register zur verfügung stellt. Allerdings ist dafür extra Hardware von nöten

Bedingte Verzweigung: Control Hazards

Sprungbedingungen werden potentiell zu spät ausgeführt, da durch das pipeling schon die nächste Instruktion abgearbeitet wird

Mögliche Lösung: Branch Prediction

Mit branch Prediction Raten wir praktisch, was als nächstes kommt
- Natürlich raten wir nicht vollständig sondern agieren auf bisherigen erkenntnissen
Wir springen also basierend auf unserer Spekulation durch die gegend
Und falls wir uns mal vertun leeren wir die pipeline wieder auf den vorherigen stand wenn wir dann "zurücksetzen"

Zusammenfassend

Wir können unsere Schnelligkeit in den Pipelines steigern, indem wir Branch Prediction oder Forwarding und Optimierung der Instruktionen verwenden, allerdings kann das auch zu Hazards führen die unterm strich unsere Schnelligkeit verringern

Out of Order Execution

In Ohrder Execution	Out of Order Execution
Es wird sich strickt an den Programmcode gehalten und alles wird sequenziell ausgeführt	Prozessor bestimmt die ausführungsreihenfolge und optimiert "on the fly" mit möglichen Fehlern
Vorab-analyse von Datenabhängigkeiten und Datenfluss	Fortlaufende Datenabhängigkeitanalyse zur Laufzeit
Warten auf "langsamere" Befehle	Kein warten, alles was unabhängig bearbeitet werden kann wird dann einfach vorgezogen
Leistungseinbußen	Schnelligkeit erfordert zusätzliche Hardware, kann zu unvorhersebaren Risiken führen

Datenabhängigkeiten

Read-after-Write (RAW)
- bzw. True Dependence
- Instruktion $S_{j}$ liest Wert aus Register, das in $S_{i}$ beschrieben wurde $(i < j)$
Problem:
- Zugriff auf veralteten Registerwert
- -Die lö sung hier: Wir müssen mit der Ausführung Warten, bis wir den richtigen wert haben.
Write-after-Read (WAR)
- bzw. Anti-Dependence
- Instruktion $S_{j}$ schreibt Wert in Register, das in $S_{i}$ gelesen wurde $(i < j)$
Problem
- ggf. haben wir aufgrund der Veränderten Ausführungsreihenfolge den falschen Wert.
- Lösung hier: ALten wert Zwischenspeichern und das Register umbenennen (Also einfach ein anderes Verwenden)
Write-after-Write (WAW)
- bzw. Output Dependence
- Instruktion $S_{j}$ schreibt Wert in Register, das in $S_{i}$ beschrieben wurde $(i < j)$
Problem:
- Hier ist ggf auch der falsche wert aufgrund der veränderten Ausführungsreihenfolge
- Die Lösung sieht hier ähnlich aus, wir nennen die Register um bzw. verwenden andere Ressourcen

Out-Of-Order-Execution

Erlaube, dass RAW unabhängige Instruktionen langsame "überholen" können
Mehrere Funktionseinheiten verwenden um die Execute-Phase zu Pararellisieren
Scheduler ein, der Instruktionen ihrer geschwindigkeit und aktuellen Prozessorauslastung scheduled und ausführt.
- Hierfür verwendet man dann einen "Warteraum" für die nach hinten verlegten Instruktionen

Data-Driven-Execution-Graph

Hier ein krasser DDE Graph

Modifikation Registerbank

Hier ist noch eine weitere krasse registerbank

Pro Register zusätzliche Felder Busy und Producer.
Busy: Eine instruktion I in FU die gewisse instruktionen in dieses Feld schiebt
Producer: (nur relevant falls Busy-Flag gesetzt): Eindeutiger Name dieser Instruktion
Als namen werden Paare (j, k) mit folgender Bedeutung verwendet:
- Diese instruktion wurde zur Dispatchzeit in SlotJ des Warteraumes der Funktionseinheit $F U_{k}$ Allokiert
- Schreibenden Zugriff auf Register $R$ erhält bei gesetztem busy flag nur der dort eingetragene Producer. SObald dieser schreibt wird das busy flag resetted

Struktur dieser "Warteräume"

Busy: Dieser Slot ist besetzt
Opcode der auszuführenden Instruktion
Dest Das zielregister für das Ergebnis der Instruktion
Source1 werden Kopiert aus den zur Dispatchzeit vorliegenden einträgen für die Source.Register
Wenn der Wert des Register aktuell berechnet wird, ist die Waiting flag gesezt, und der Produzent des Wertes Eingetragen
Data-Driven-Execution: Nur wenn beide Waiting Flags nicht gesetzt sind, kann die Instruktion ausgeführt werden

Verteilung der Ergebnisse

FU legt Dest, Producer, Value auf Common data bus
Alle FUs hören mit, und schauen ob in einem Warteslot auf diese Producer-Daten gewartet wird
Wenn ja: Wird das waiting flack zurückgesetzt und der Wert übernommen
Registerbank lässt den schreibzugriff auf Destination nur zu, wenn keine busy flag gesetzt ist und der genannte Producer mit dem Producer aus dem Common data bus übereinstimmt

Speicheradressierung

Speicher wird mit Byteadressen adressiert
- Speicher ist praktisch ein Riesiges eindimensionales Array von Bytes
- Adresse einer Speicherzelle entspricht dem Array Index
- Logischerweise (looking at you, Lua) startet das Array bei 0, also ist dat auch die niedrigste Speicheradresse
Wie wird ein Wort (4 Byte / 32-Bit) im Speicher abgelegt?
- Das höchstwertige Byte des Wortes speichert sich an der niedrigsten Byte adresse
- Ein wort wird mit der Adresse seines höchstwertigsten Bytes adressiert (also da wo es losgeht)
- Wortadressen müssen ein vielfaches von 4 sein ("Alignment Restriction")

SRAM

Static Random Access Memory
Ja halt statischer speicher für einen bit
Gleicher aufwand für lesen und schreiben
Die information wird im status der inneren Transistoren gespeichert
Vorteile:
- ist sehr schnell
- Braucht keine regelmäßige Auffrischung
Nachteil:
- Physisch relativ groß im gegensatz zu DRAM

DRAM

Dynamic Random Access Memory
Information wird in der Ladung eines Kondensators gespeichert
Vorteile:
- Einfacher Aufbau
- Geringe Größe
Nachteile
- höhere Zugriffszeit
- kondensator verliert mit der zeit seine ladung
  - braucht daher einen periodischen refresh

Aufbau von Zellfeldern

2-Dimensionale Matrix
mehrere Speicherzellen $\to$ Speicherzeile
Mehrere Speicherzeilen $\to$ Speicherfeld/Zellenfeld
Mehrere Speicherfelder
- 1 Speicherbank
Mehrere Speicherbanken
- 1 Speicherchip

Funktionsweise des RAM

Ansprechen von Ziel chip/bank
Speichercontroller der CPU übermittelt die Adresse
- Entschlüsselung durch Zelendecoder
Aktivierung der Speicherzeile (wordline)
Spaltendecoder ermittelt die richtige Position
Bitline wird mit Datenleitung des speicherchips verbunden
- Lesen: Zustand des Kondensators wird ausgelesen
- Schreiben: Richtiger Zustand wird gesetzt
Deaktivierung der Speicherzelle

Gründe für Komlexe Speicheroganisation

Ein Zugriff auf eine Hauptspeicherzelle ist langsamer als ein Zugriff auf ein Register
- Hautpspeicherzellen sind DRAM-Zeilen (dynamische speicherzellen), wärend Register in der Regel SRAM-Zellen (statische Speicherzellen) sind
- Bei einem "simplen" registerzugriff kommt man sogar ohne Bus-operation aus!
Idee: man stellt dem prozessor einfach einige megabyte Register zur Verfügung
- Aber:
  SRAM-Zeilen sind wesentlich größer als DRAM-Zellen $(F ak t or \geq 4)$
Leider ist das derzeit noch nicht realistisch, das kann aber vielleicht in der Zukunft kommen.

Lokalitätsprinzip

Lokalitätsprinzip:
- Programme greifen sehr schnell hinterinander auf einen relativ kleinen Teil des Adressraums zu
Temporale Lokalität
- Wenn ein Zugriff auf eine Adresse erfolgt, wird auf diese Adresse mit "großer" Wahrscheinlichkeit bald wieder zugegriffen
  - z.b. beim Abarbeiten von schleifen
Räumliche Lokalität
- Wenn ein Zugriff auf eine Adresse erfolgt, werden mit "großer" Watscheinlichkeit bald Zugriffe auf in der nähe liegende Adressen erfolgen
  - z.b. Verarbeiten von Arrays, Loopen durch Listen
Aufgrund der Lokalität kann man Speichersysteme hierarchisch aufbauen
- Obere Stufe der Hierarchie: schneller und teurer Speicher (wenig)
- Untere Stufe der Hierarchie: Langsamer und billiger Speicher (aber viel davon)

Speicherorganisation Heute

Hier eine krasse Grafik die Zeigt wie Speicherorganisation heute funktioniert

Hier noch eine krasse speichertabelle die Speichertabelle anzeigt

Big Endian vs Little Endian

Boah krass eine visualisierung die erklärt was little und was Big endian ist

Caches

Cache kommt aus dem Französischen cacher (verstecken)
Er kann durch ein Anwendungsprogramm nicht explizit adressiert werden
Der kram ist "software-Transparent", d.h. der benutzer muss eig nich wissen, dass es den kram gibt

Lage des Caches

hier liegt der Cache in einer massiv krassen grafik die wieder angezeigt wird

In der Regel besitzt ein Rechner getrennte Caches für Instruktionen (Instruktionscache) und für Daten (Datencache)

Ziel des Cache Einsatzes

Wir versuchen die daten so "nah wie möglich" zu halten
- Prozessor kann dann mehr auf Caches zugreifen und verschwendet weniger zeit beim warten auf den langsamen RAM oder auf den unglaublich langsamen langzeitspeicher
Hierfür müssen wir das oben angesprochene Lokalitätsprinzip verwenden

Wie sieht das in der Praxis aus?

Wenn der CPU die daten die er sucht in dem Cache findet, dann ist er glücklich und macht einfach weiter ohne zu warten
Sei das aber nicht so schön, muss der CPU erstmal auf den Arbeitsspeicher zu und schreibt das was er gelesen hat gleichzeitig in den cache, und in die arbeitsregister der CPU

Mittlere Zugriffszeit beim Lesen

$c$ Zugriffszeit des Caches
$m$ Zugriffszeit beim Hauptspeicher
$h$ Trefferrate
$\to$ Durchschnittliche Zugriffszeit: $c + (1 - h) \cdot m$

Aufbau eines Caches

Ein Cache besteht aus zwei Speicher-EInheiten, die wortweise einander fest zugeordnet sind,

Cache als assoziativer Speicher

Im idealfall, wäre Cache immer Inhaltsorientiert, also assoziativ
Die von dem Prozessor angelegte Adresse wird parallel mit allen im Adresspeicher des Caches vorhandenen Adressen verglichen
Außerdem kann ein neues Datenteil praktisch an jeder freien Stelle des caches abegelgt werden.
Deswegen gibt es eine Aufwendige Logik für den Parallelen Vergleich
Assoziative Speicher nur für kleine Cache-größen

Was passiert mit Alten daten?

Wenn wir cachedaten nicht mehr brauchen, dann müssen wir sie wegwerfen um platz für neues zu machen.
Wenn wir noch nen register frei haben, nutzen wir immer erst das, einfach weil das uns den job einfacher macht und wir nicht 500 Sachen abfragen müssen
Wenn aber nix mehr frei ist, dann schauen wir nach einigen Kriterien
- Least Recently used (LRU) wirft das weg was am längsten nicht benutzt wurde
- Least Frequently Used (LFU) wirft dat wech, auf das am wenigsten zugegriffen wird
- First in, First out (FIFO) Wirft das über bord, wat schon am länchsten da war

Direct Mapped Cache

Die von der CPU angelegte Adresse wird in 2 Teile Gespalten
- Die $i$ niederwertigen Bits adressieren einen EIntrag im Adresspeicher
- Dieser Eintrag wird dann mit den $n - i$ höherwertigen Bits der Adresse verglichen
Speicherzellen des Hauptspeichers, deren $i$ niederwertige Stellen gleich sind, werden auf die gleiche Position im Cache abgebildet

Illustration

Hier eine krasse Skizze die Direktaddressierten Cache visualisiert

Cache Tag
- Der Index (Cacheblockadresse) kann nicht eindeutig der Speicherblockadresse zugeordnet werden
- Also ist der Inhalt des Caches an dieser position somit nicht eindeutig bestimmbar
- Deshalb verwendet man die restlichen bits der Speicherblockadresse für einen sog. "Tag"
  - Zu jedem block im Cache speichern wir auch den Tag
- Wir finden jetzt also daten, indem wir die caches nach dem Tag und dem Eintrag suchen
Valid bit
- Ja nen bit was sagt, ob der eintrag valid is
  - Am anfang (und nach jedem flushen) enthält der cache keine gültigen daten
    - Also ist das Valid bit 0
  - Wenn wir dann aber einen validen eintrag hinzufügen, wird das bit auf 1 gesetzt

Hier eine massiv coole grafik die uns zeigt, wie viel direct mapped Cache ausmachen kann

Hier sehen wir, wie viele Anfragen im cache gehittet werden können, gemessen an der cachegröße

Prinzipielle Funktionsweise: Schreibzugriff

Schreibe Datum in den Arbeitsspeicher unter Adresse $a$ :
CPU Überprüft, ob eine Kopie der Hauptspeicherzelle a im Cache abgelegt ist
Write-through verfahren
- cache miss: CPU schreibt das Datum in die Hauptspeicherzelle mit der Adresse $a$ . Der Inhalt des Cache wird nicht verändert
- cache hit: die Kopie der Haauptspeicherzelle im Cache wird aktualisiert, die Hauptspeicherzelle wird auch direkt aktualisiert
  - so kann sich der Prozessor auch direkt anderen sachen widmen, aber der speicher-controller regelt das update im ram, ohne dass der Prozessor warten muss
Write-back Verfahren
- cache miss: CPU schreibt das datum in die Hauptspeicherzelle mit Adresse $a$ , Der Inhalt des caches wird nicht verändert.
- cache hit: Die kopie der Hauptspeicherzelle im Cache wird aktualisiert und durch "dirty bit" als verändert markiert. Die hauptspeicherzelle selbst wird erst später aktualisiert, nämlich erst wenn die Kopie ausm cache geworfen wird, die CPU damit also "fertig" ist
write-allocation Verfahren
- cache miss: CPU schreibt Datum in den Cache (markiert mit "dirty bit"), aber nicht in den Hauptspeicher, da wirds dann wie oben erst aktualisiert, wenns ausm cache geworfen wird
- cache hit: Wie beim write-back verfahren

Writeback VS writeallocation

Vorteile von Write-back/Write-allocation

Schreibzugriffe auf Cache bei cache hit ohne Wartezyklus möglich (bei write-allocation sogar bei cache miss)
Belastung des Systembusses kleiner, wenn das Rückschreiben in den Hauptspeicher erst nach mehreren Schreibvorgängen erfolgen muss

Nachteile von Write-back/Write-allocation

Schwierikeiten bei der Datenkonsistenz, wenn andere Komponenten die daten brauchen die nicht auf den CPU-Cache zugreifen können

Festplatte (Hard Disk Drive)

ja dat ding hat halt mehrere Platten
Die haben jeweils ihren eigenen lese/schreibkopf
und dann funktioniert dat maßgeblich wie ne CD
Sind aufgeteilt in Sektoren von 128Byte bis 1 Kbyte
Und haben dann auch diverse Spuren & Schreibdichten

Adressierung

Heute verwenden wir das sog. Logical block addrssing, oder LBA
Hierbei sind die Sektoren fortlaufend numerriert
Und ein Festplattencontroller übersetzt in physikalische Koordinaten des Sektors

Partitionierung

Festplatten kann man aufteilen in diverse Partitionen
- Wie eine partition aufgebaut aussieht, steht im ersten Sektor im "master boot record" (MBR) oder den äußeren 32 Sektoren (GUID Partition Table, GPT) in einer sog. Partitionstabelle
MBR: 4 Master-Partitionen, je 16 Byte
- Erster und letzter Sektur in CHS-Koordinaten (je 3Byte)
- Erster Sektor in LBA und Gesamtzahl Sektoren (je 4Byte)
- allg. Informationen (Typ/Format, bootfähig; je 1 Byte)
- Maximale Partitionsgröße: Abhängig vom System
- Maximale Festplattengröße: Abhängig von Systemarchitektur
MBR: Enthält vorwiegen Bootstrap-Code zum Laden des Betriebssystems (wird von BIOS/UEFI beim Start geladen und ausgeführt)

Ausführung eines Festplattenzugriffs

Beweg die Köpfe zu dem Richtigen Zylinder
Warte bis der gesuchte Sketor zum Kopf rotiert
Übertrage den Inhalt des Sektors

Hier ein beispiel für die rechnung eines festplattenzugriffs

Alternative: Solid State Disk (SSD)

Hier werden zum speichern Halbleiterbausteine wie beim RAM verwendet
Es gibt zwei große verfahren:
- Flash-Specher:
  - Nicht flüchtig (verliert also seinen zustand nicht, wenn er keinen strom mehr bekommt)
  - sehr energieeffizient
  - Kurze Zugriffszit ~ $0, 1 m s$
- SDRAM
  - Flüchtig, deswegen nicht für langzeitspeicher geeignet
  - Allerdings als cache für die SSDs
  - Ist allerdings auch seeehr schnell
  - aber Stromineffizienter
Vorteile:
- kein verschleis weil keine mechanischen teile
- Kann besser mit äußerlichen Einwirkungen umgehen
- Ideal für Anwendungen mit niedrigem energieverbrauch
Nachteil:
- Deutlich Teurer als Festplatten
- Nicht beliebig oft wiederbeschreibbar (flash: 100.000 bis 5 Millionen Schreibyklen)
- Daher benutzen die meissten modernen SSds Reserve-Zellen und Wear-leveling-Algorithmen

Das problem mit dem Hauptspeicher

Der adressraum von heutigen Computern, ist aufgrund von 64-Bit Prozessoren sehr groß
Bei busbreite $n$ sind beispielsweise $2^{n}$ Speicherzellen adressierbar
So viel speicher hat aber niemand, weils einfach unendlich teuer wird

Daher: Festplatte als virtuellen Arbeitsspeicher verwenden

Der nutzer kriegt davon eig nix mit
Wie sieht das dann in der Praxis "unter der haube" aus?
- Multi-User: nicht jeder benutzer kriegt den kompletten hauptspeicher zugeschrieben
- Programme werden nicht für einen spezifischen rechner geschrieben, sondern sehr generalisiert
Ausweg?
- Benutze die Festplatte als erweiterten Hauptspeicher
- Hier sollen dann sachen die noch gebraucht werden, aber nicht unbedingt dringend gebraucht werden gelagert werden, sobald nicht mehr genug platz im Hauptspeicher ist

Ja aber was machen wir jetzt mit dem Adressraum?

-> Virtueller adressraum

Jeder Prozess bekommt einen virtuellen Adressraum
Diese virtuellen adressräume werden vom Betriebssystem verwaltet
- Das OS hat also eine "übersetzungstabelle", denn wenn z.b. Word denkt, dass es auf memory adresse 0x10331 zugreift, weiss das OS, dass die daten in 0xff781 liegen.
- Zudem verwaltet das Betriebssystem welche programmteile im Ram gehalten werden
- und wann welche daten in den festplatten-ram (SWAP) ausgelagert werden
In diesem zusammenhang werden konzepte wie
- Paging
- Segmentierung
angewandt

Segmentierung

Unterteilung des Virtuellen Speichers in Segmente unterschiedlicher Größen
Wenn ein programm versucht ausserhalb seiner Segmentgrenzen zu schreiben gibts den bekannten segmentation fault
und wenn nen angefordertes segment erst garnicht existiert, gibts den auch
Das betriebssyteme ist dafür verantwortlich, welche segmente im ram liegen und welche weggeworfen werden können und welche weggeworfen werden

Paging

Grundidee

Der Virtuelle Speicher wird auf dem Sekundärspeicher abgelegt
- dabei wird er in seiten fester größe unterteilt
der hauptspeicher besteht aus page-frames, die jeweils eine Seite aufnehmen können
Eine Seitentabelle (page table) gibt an, welche seitenrahmen durch welche Seiten belget sind

Hier eine Illustration wie paging funktioniert

Paging: Zugriff auf Datenseite $i$

Überprüfe ob Datenseite $i$ im Hauptspeicher liegt;
If Seitenfehler (page fault)
then Überprüfe ob ein Seitenrahmen im Hauptspeicher leer ist;
if Kein seitenrahmen leer
then Verdränge eine Seite ausm hauptspeicher und aktualisiere dann die seitentabelle
Schreibe Die datenseite $i$ in den Freien Rahmen und aktualisier die tabelle
auf $i$ im Hauptspeicher zugreifen

Wir verweisen wieder auf die Verdrängungsstrategien

Übersetzung von virtuellem Speicher auf physikalischen Speicher

macht eine MMU (memory Management Unit)
- Ist heutezutage direkt im Prozessor (früher North-Bridge)
- Cache für zuletzt benutzte Pages
  (Translation Loojkaside Buffer, TLB)
- Falls nicht in TLB aus (mehrstufiger) Seitentabelle Berechnen
  - das erfordert bis zu 5 Hauptspeicherzugriffe und ggf. Pagefaults (+ handling) falls die seitentabelle nicht vollständig im speicher ist
Caches:
- PIPT (Physicalle Indexed, Physically Tagged)
  - Einfach aber langsam wegen MMU-Aufrufen
- VIVT (virtually Indexed, Virtually Tagged)
  - sehr schnell, aber Homonyme/Synonyme
- VIPT (Virtually Indexed, Physically Tagged)
  - für schmale indices: Index der Virtuellen adresse stimmt mit phys. Adresse überein
  - in Frage kommendes Cache-Set kann parallel zum MMU Aufruf geladen werden

Speed-up vs. Security

Meltdown

CPU- Branch-Prediction Exploits
Idee:
- Greife auf Kernel-Speicher zu (ohne berechtigung)
- Das wirft logischerweise ne Exception
- Während die Exception behandelt wird, wird allerdings auf den daten die bereits geholt wurden aufgrund der Branch-prediciton spekulativ weitergerechnet
- Hat messbare effekte auf den Cache, die nicht zurückgesetzt werden
Auslesen der Informationen
- Je nach Speicherinhalt wird eine andere Seite in den Cache geladen
- anderer Prozess überprüft dann anhand von Zugriffszeiten welche Seite geladen wurde
- Dadurch kann man rückschlüsse auf den Speicherinhalt erziehlen
- Auslesegeschwindigkeit ~500 kB/s
Wat kann man dagegen machen?
- Auf der OS-Ebene schon den speicher besser isolieren und keinen zugang zum Kernel zulassen
- Mikrocode Updaten

Spectre V1

schläust sich in laufende Prozesse ein
kann dann auf den jeweiligen User-Space zugreifen

Spectre V2

Branch prediciton manipulativ trainieren (Context A)
Spekulative Code-execution ausnutzen, wie oben schon benannt (Context B)
- denn oft wird nur ein teil der virtuellen speicheradresse für den Sprungcode verwendet
- Und alle prozesse eines Kerns nutzen die selbe branch perediction engine
Gegenmaßnahmen:
- SpectreV1:
  - Bounds check Bypass
    - absichtlich ungenaue zeitmessungen
  - Spectre V2
    - Branch Target Injection
      - Maßnamen auf OS-Ebene
      - Microcode-Updates
      - weitere sicherheitsmechanismen
      - allerdings auch hier wieder merkbare Leistungseinbußen

Parallelverarbeitung

Formen der Parallelität

Bis etwa 1985 haben wir das auf bitebene gemacht, also hatten wir kombinatorische addierer und Multiplizierer die immer alles 1zu1 verglichen haben, das wurde dann irgendwann unpraktisch, weil wir ja immer größere wörter in memory haben, was zu mehr und mehr pain geführt hat
Heutezutage machen wir das Auf instruktionsebene, also werden immer mehrere instruktionen gleichzeitig ausgeführt, anstelle von einigen operationen die "gleichzeitig" im ram gespeichert und immer sequenziell aisgeführt werden
- Das kann allerdings ab > 4 Cores problematisch werden - was zu hindernissen bei effizienz und optimierungen führt
Als alternative dazu gibt es auch die paralelität auf Prozessorebene
- nur damit sind beschläunigungen um den Faktor 50 und mehr möglich (allerdings is Amdahl's Law zu beachten)

Amdahl's Law

$p$ = Relative Größe des Programmanteils, welcher leider nicht massiv hip und multithreaded werden kann
$k$ = Anzahl der massiv coolen Kerne
Ideal wäre natürlich, wenn wir dat alles gleichmäßig aufteilen könnten (logischerweise) geht nur leider iwie nicht ganz so gut auf
Beschleunigung: $\frac{t}{p \cdot t + ( 1 - p ) \cdot \frac{t}{k}} = \frac{1}{p + \frac{1 - p}{k}} < 1/ p$

Formen der Parallelverarbeitung auf prozessor-/ Rechnerebene(1)

Arrayprozessoren

Viele Prozessoren die gleich sind und eventuell lokalen speicher haben
Jeder dieser prozessoren hat seine eigene Steuereinheit
Und alle haben immer dieselbbe Instruktionsfolge
Bsps:
- Illiac IV
- CM-2

Wie machen wir dat sinnvoller? -> Wir machen die einzelnen Prozessoren in der Datenvararbeitung unabhängiger machen

Multiprozessoren:

bestehend aus mehreren (seperaten) Prozessoren und haben insgesamt einen (realtiv großen) hauptspeicher
die kommunizieren über den gemeinsamen speicher
Allerdings kann das zu performanceprobleben füren wenn viele prozessoren gleichzeitig auf den speicher zugreifen wollen

Multi-Core Prozessoren

Mehrere prozessoren auf einem chip die evtl gemeinsamen Cache und ggf. direkte Kommunikationsmöglichkeiten untereinander haben.

Koprozessoren

Sollen hauptsächlich den hauptprozessor entlasten
sind daher meisstens auf eine bestimte menge an spezialisierten Aufgaben Spezialisiert
Wie z.b. GPUs für alles das wofür man ne Grafikkarte braucht
- Die dinger haben scheinbar ne große Ähnlichkeit zu Vektorprozessoren
Und dann gibts natürlich noch die absoluten chads: die mathemathischen Koprozessoren die unanfälliger für die nervigen Floating-Point issues sind.

Multicomputer

Man kanns natürlich maximal übertreiben und mehrere computer zusammenstrappen.

Dabei haben sie kein shared memory
Die prozessoren kommunizieren über kommunikationstunnel mit gewissen protokollen (nachrichten)
Dadurch wird das potentiell sehr komplex, dafür aber "beliebig" expandierbar

Beispiele für parallele Rechnerarchitekturen:

Symmetrische multiprozessoren (SMP)

massiv bessere Grafik

Dat is leider oft busbasiert und nutzt einen gemeinsamen Speicher
Das sind halt homogene Prozessoren
Dabei wird durch lokale Caches die Speicherlatenz verringert
leider können dabei diskrepanzen zwischen dem Cache und dem gemeinsamen Speicher entstehen, die zu komplikationen führen
Damit das passiert, müssen alle caches permanent "überwacht" werden, damit alle diskrepanzen frühzeitig behoben werden können

Cache Koeärenz

z.B. MESI-Protokoll
- Modified:
  - Einzige, veränderte kopie
- Exklusive:
  - Einzige unveränderte Kopie
- Shared:
  - mehrere unveränderte kopien
- Invalid:
  - ungültige kopien

Hier ein krasseres bild über das MESI Protokoll

Systeme mit Verbindungsnetzwerg und dezentralisiertem gemeinsamen Speicher:

Einfach die beste grafik der VL

Mit dieser Technik können sehr riesige Speichermodule realisiert werden.
System mit Dezentralisiertem Speicher mit Verbindungsnetzwerk und zusätzlichem lokalen cache

Boah die ist ja fast noch besser als die letzte grafik

Dann gibt es noch die Parallelen Rechnerarchitekturen die ein Verbindungsnetz und viele "kleinere" lokale speicher verwenden.
Hier ist der Prozessoroverhead hoch, weil jedes system eigenständig ist und immer alles an die jeweils anderen weitergeben muss.

Das ist ja trotzdem mega cool

Dabei ist der direkte Zugriff auf den lokalen speicher einer anderen maschine nicht möglich. Man muss alles anfragen
Dadurch, dass mehr anfragen / antworten gebraucht werden um dasselbe zu erreichen wie bei den "simpleren" systemen wird die "normale" usage komplizierter.
dafür ist dieses System allerdings pysikalisch skalierbarer, da jede einheit alleine agiert und durch das Verbindungsnetz die Aufgaben aufgeteilt werden können

Verbindungsstrukturen

Wie schnell die maschinen untereinander kommunizieren können ist ausschlaggebend für die allgemeine Performance, da durch übermäßiges Warten prozessorzeit verloren gehen könnte
Zudem ist zu beachten, dass nicht unbedingt jedes Problem direkt für Parallelisierung geeignet ist, da manche sachen so stark aufeinander aufbauen, dass mehr zeit verschwendet würde, wenn die prozessoren aufeinander warten, als wenn es einer in einem zug "alleine" machen würde
Um die Datenverarbeitung zu maximieren muss man zwischen diversen Strukturen wählen, welche alle andere Vorteile im hinsicht zu Kosten und Leistung haben

Modellierung von Verbindungen

Die Topologie eines Parallelrechners wird durch einen abstrakten Graphen $G = (V, E)$ dargestellt mit
$V = {1, ..., n}$
- Menge der Knoten, diese repräsentieren Prozessoren oder switches
$E \subseteq {{a, b}; a, b \in V}$
- menge der Kanten. Diese Repräsentieren die Verbindungen zwischen den einzelnen Knoten (Switches und CPUs)
$D u rc hm esser (G) = ma x_{v, w \subseteq V}$ {Länge des kürzesten Pfades von v nach w}
$G r a d (G) = ma x_{v \subseteq V} ∣ {w \in V, {v, w} \in E}$
$A n z ah l d er V er bin d u n g e n (G) = ∣ E ∣$

Bsp:

MAN IST DAS NEN MEGA KRASSES BILD NEY?

Stern

Andernfalls gibt es noch den stern als Verbindungsmodell, hierbei läuft alle Kommunikation durch einen Knotenpunkt

Mench Krasse sterngrafik

Ebenso kann mann einen Bus als Stern Modellieren, allerdings ist dann hierbei zu beachten, dass der Mittlere Punkt keine Logik verarbeiten kann. Leider gibt es dabei aber wieder denselben "Flaschenhals" (Bottleneck) wie beim Stern, denn es kann nie schneller Kommuniziert werden als der Mittlere Punkt / Das Switchboard Zulässt

Ring

Dann gibt es noch das Ring-Modell, was man sich wie einen Redekreis vorstellen kann. Hierbei kursiert ein sog. "Ring-Token" was wie der mystische "Gesprächsstein" fungiert, denn ein mitglied des Ringes darf nur dann etwas senden, wenn es diesen Token hat.

Durchmesser = $⌊ n /2 ⌋$
Grad = $2$
| Verbindungen | = $n$

CDDI / FDDI-Ring

[Copper / Fiber Distributed Data Interconnect]

Characteristika:

Besteht aus den komischen Sitzkreis-Ringen die oben beschrieben wurden
Allerdings hat das ding zwei davon, die gegenläufig sind, also in die jeweils andere Richtung voneinander Laufen.
- Dadurch wird die Fehlertoleranz erhöht

BOAH KRASS EINFACH kreise

MESH ("torusähnliches Gitter")

MESH

wird z.b. bei MPPs verwendet
Durchmesser = $⌊ n^{1/2} /2 ⌋$
Grad = $4$
| Verbindungen | = $2 n$

HYPERCUBE ( $d$ -Dimensionaler Würfel)

MAN DAS IST NEN HYPENDER CUBE ODER

dieses Modell ist bei einer hohen anzahl von Prozessoren nicht verwendbar, da der grad zu schnell ansteigt.
Im Bild haben wir z.b. einen 3-Dimensionalen würfel mit 8 ecken, also Knoten. Sprich:
- $d = 3$ (Dimension)
- $n = 8$ (Nodes)
Allgemein:
Durchmesser = $l o g_{2} n$
| Verbindungen | = $(n l o g_{2} n) /2$

Cube Connected Cycle (CCC)

MAN NEN WÜRFEL DER WÜRFELIGER IST ODER WIE

Prozessoren = $n l o g_{2} n$
Durchmesser = $⌊ 5/2 l o g_{2} n ⌋ - 1$
Grad = 3
| Verbindungen | = $3/2 n l o g_{2}$

Beispiele für parallele Rechnerarchitekturen

Die "heute" gängigen Multi-Core Architekturen
- Dual Core:
  - Intel Core 2 Duo
  - AMD Athlon X2
- Quad Core:
  - AMD Phenom II X4
  - Intel Core 2 Quad
  - Intel Core i7
- Octa Cores (Und darüber hinaus):
  - AMD Ryzen 9 (bis zu 16 Kerne + 32 Threads)
  - Intel Core i9 (bis zu 18 Kernen + 36 Threads)

Beispiel AMD Phenom II X4 (2009)

Dat teil hat:
- 4 Identische Kerne
- Cache:
  - L1: 64 KB / Kern
  - L2: 512KB / Kern
  - L3: 6144KB Insgesamt
- 45 nm
- 2,8 - 3 GHz

Beispiel: Cell Chip

Cell Chip
- (IBM, Sony, Toshiba)
- 234 Millionen Transistoren
- $>$ 256 Gigaflops (Single prec.)
- CPU: 1 x 64-Bit-Power-PC
- 8 x SPE (Synergistic Processing Element)

Grafikprozessor

KRASSES BILD

die Grafikpipeline beschreibt die Schritte in denen eine 3D.Szene auf dem Bildschirm gerendert wird.
Ein Grafikprozessor setzt diese Pipeline direkt in Hardware um

Aber wie funktioniert das eigentlich?

Bildpunkte werden durch Vektoren dargestellt
Eine GPU ist dafür ausgelegt, sehr viele Bildpunkt-Operationen gleichzeitig auszuführen
Ebenso ist die GPU auf alles ausgelegt, was in der Grafikverabreitung vorkommt wie z.b.Skalarprodukt, Logarithmen etc. Hardwareseitig optimiert

Grafik-2 YEAH KRASS ODER

Die Schritte in der Grafikpipeline:

Projektion von 3D Auf 2D
- Beispiel: Zentralprojektion für einen Punkt $(x, y, z)$ und das Projektionszentrum $(0, 0, - z_{0})$ ergibt sich die Projektion durch:
- $10000100 000 z_{0}^{- 1} 0001 \cdot x y 0 z 1 = x y 0 1 + z \cdot z_{0}^{- 1}$
- $\to$ Die Operation $a^{'} = a + (b \cdot c)$ wird sehr häufig verwendet, daher wird sie durch einen Multiplikationsakkumulator (MAC) direkt in Hardware realisiert
Matrix $A \cdot V e k t or x = \sum_{j = 1}^{n} a_{1 j} x_{j} ... \sum_{j = 1}^{n} a_{mj} x_{j}$
Wir betrachten, mal wieder, eine extremst veraltete Grafikkarte als Beispiel:

AMD Radeon RX 580

GPU "Polars20"
spezielle Funktionseinheiten:
- 2304 Shading Units (Stream-Prozessoren)
- 36 Compute Units
- 144 Textureinheiten
1,257 GHz
6200 Gflops
2 x 1024KB L2-Cache

Klassifikationsmerkmale bei Parallelen Rechnerarchitekturen

Speichermodell:

Nicht verteilter Speicher, gemeinsamer Adressraum
verteilter Speicher, gemeinsamer Adressraum
verteilter Speicher, getrennte Adressräume

Homogenität der Prozessoren

homogene Parallelrechner: alle prozessoren sind gleich
heterogene Parallelrechner: Prozessoren dürfen sich hardwaremäßig unterscheiden

Hirachie zwischen den Prozessoren

symmetrische Parallelrechner: Die Prozessoren sind bzgl ihrer Rolle im gesamtsystem untereinander Austauschbar.
nichtsymmetrische Parallelrechner: es gibt masters und Slaves

Eigenständigkeit der Prozesoren:

lose gekoppelter Parallelrechner: Netzwerk von eigenständigen Rechnern
eng gekoppete Parakkekrechner: physikalisch ein Rechner

Klassifikation nach Flynn [1966]

SISD (Single Instruction stream, Single Data stream)
- Eine Instruktion betrachtet immer ein Datenteil isoliert und alleine
- So lernen wir Programmierne zu Beginn
SIMD (Single Instruction stream, Multiple Data streams)
- Eine Instruktion behandelt direkt mehrere Datenteile
- Dieses Modell findet sich in modernen GPUs wieder
- Beispielsweise loopen wir über eine Liste von elementen und rechnen alle + 1
MISD (Multpiple Instruction stream, Single Data Stream)
- Wenn mehrere Instruktionen verwendet werden um ein Datenteil zu editieren.
- z.b. wenn wir 3 verschiedene Rechenoperationen hintereinander auf ein element ausführen
MIMD (Multiple Instruction streams, Multiple Data streams)
- Basically "true" multitasking. Mehrere unabhängige Systeme interagieren mit mehreren unabhängigen Datensätzen

Codierung (Von Zeichen)

Motivation?

Ein Rechner kann traditionell leider keine
- Zeichen verarbeoten
- mit zahlen rechnen
- Bilder / Grafik darstellen
Wir können zwar theoretisch algorithmen bauen, die diese sachen implementieren, allerdings müssen wir diese algorithmen in ein vom Computer verstandenes Binärformat umwandeln (Kompillieren)

ASCII

Wir reden erstmal über Primitive Dinge: also T-Scr.. ich meine Ascii (American Standard Code for Information Interchange)

Mit Ascii kann man (sehr begrenzte) Zeichen darstellen und deswegen hat man angefangen Alternativen zu bauen
Man kann mit Ascii zudem nur lateinische Buchstaben darstellen, und auch nur die, die im englischen sehr aktiv genutz werden, da man aufgrund von bandbreitenlimitierung ein (weirdes) 7-Bit format gewählt hat.
Dann hatten wir eine radikal bessere idee als Ascii: Unicode

Unicode

Auch bekannt als UTF-8
8 weil ein zeichen bis zu 8 bit lang sein kann.
Zudem hat Unicode auch support für Ascii, indem man nur den ersten byte der sequenzfolge nutzt. Da ascii praktischerweise in einen byte passt, ist damit das gesamte Ascii spektrum auch abgebildet
Wenn ein Zeichen nicht Ascii codiert ist, dann ist es zwischen 2 und 4 Byte lang

Definition: Code

Das werdet ihr in Info3 wieder sehen :P

Sei $A = {a_{1}, a_{2}, ..., a_{k}}$ ein endliches Alphabet der größe $k$
Die Menge $c : A \to {0, 1}^{*}$ oder $c : A \to {0, 1}^{n}$ heißt Code falls $c$ injektiiv ist.
Die menge $c (A) := {w \in {0, 1}^{*} ∣ \exists a \in A : c (a) = w}$
Ein Code $c : A \to {0, 1}^{n}$ heißt Code fester Länge
Beobachtung: Für einen Code $c : A \to {0, 1}^{n}$ fester Länge gilt $n \geq ⌈ l o g_{2} k ⌉$ .

Probleme bei Binär-encoding:

Daten können in der Transmission beschädigt werden, weswegen dann Interpätationsschwierigkeiten aufkommen

Was kann alles Passieren?

Bitstellen können Geflipped werden (Der mysteriöse Bitflip)
Die distanz zwischen zwei bitfolgen könnte sich verändern, dass dazwischen mehr 0en stehen als geplant.
Ein Übertragungsfehler heisst einfach, wenn $d i s t (v, w) = 1$ gilt.
Hier ein beispiel wie die $d i s t$ funktion funktioniert:
- $d i s t (00001101, 10001100) = 2$
- $d i s t (00001101, 00001101) = 0$
Wat bei der krassen Fehlerhaft übertragung helfen könnte wäre eine FEHLERERKENNUNG (BOAH KRASS)

Fehlererkennender Code

Sei $c : A \to {0, 1}^{n}$ ein code fester Länge von $A$

Der kürzeste Abstand
- $d i s t (c) := min {d i s t (c (a_{i}), c (a_{j})); a_{i}, a_{j} \in A mit a_{i}, \neq = a_{j}}$
zwischen zwei Codewörtern wird Distanz des Codes $c$ genannt. Der code $c$ heisst $k$ -fehlererkenned, wenn mder Empfänger in jedem fall entscheiden kann, ob ein gesendetes Codewort durch flippen von $k$ Bits verfälscht wurde.

Lemma

Ein Code $c$ von fester Länge ist genau dann $k$ -fehlererkennend, wenn $d i s t (c) \geq k + 1$ gilt.

Wir erkennen Fehlerhaften code indem wir parity-checks (Paritätstests) durchführen, und prüfen, ob sich die beiden bitfolgen an einer oder mehreren Stellen unterscheiden
Man kann z.b. einen Parity-Bit (Paritätsbit) an eine bitsequenz hängen um mit dem abschliesenden bit überprüfen zu können, ob die datenübertragung erfolgreich war.

MASSIV COOLE GRAFIK

Beweis Lemma [Fehlerkorrektur]

Idee

Sei $m = d i s t (c)$ . Da $c$ $k$ -Fehlererkennend ist, muss $m \geq k + 1$ gelten.
Wir haben zwei Codewörter $c (a_{i}), c (a_{j})$ , die sich an genau $m$ Stellen unterscheiden. Die Bitfolge $b$ die man erhält, wenn $k$ dieser stellen in $c (a_{i})$ geflippt werden, underscheidet sich in $m - k$ Bit von $c (a_{j})$
Ist $m < 2 k + 1$ dann $m - k < k$ und es kann nicht mehr eindeutig bestimmt werden, zu welchem Codewort $b$ korrigiert werden muss
Ist $m \geq 2 k + 1$ , unterscheidet sich $b$ von $c (a_{j})$ an mehr als $k$ Stellen. Gleiches gilt dann auch für alle anderen Codewörter und bitfolgen die sich von $c (a_{i})$ an höchstens $k$ stellen unterscheiden. Also ist eine eindeutige Korrektur zu c(a_j) möglich

Wir könnten normale Bitsequenzen um Prüfbits erweitern
Die Prüfbits müssten dann so belegt werden, dass jedes Codewort $r$ verschiedene Parity-checks bestehen kann
Genau die bitstellen $2^{j}$ (also 1, 2, 4, 8,...) sind Prüfbits
Das prüfbit an der Stelle $2^{j}$ muss so gewählt werden, dass alle Bitdarstellungen die an der $j$ -ten Stelle eine 1 haben, den Parity-check bestehen

Hamming Code an einem Beispiel

Uncodiertes Zeichen: $0111010100001111$
$m = 16, r = 5$
Wie sieht nun der Hamming-Code dieses Zeichen aus?
Der Code wird auf 21 Bitstellen verlängert
Die zweierpotenz-Bitstellen werden als Überprüfungsbits benutzt 0 1110 _ 101 0000 _ 111 _ 1 _ _
wobei Bitstelle $2^{i}$ die Bitstellen Überprüft deren Binärdarstellungen an der $j$ -Ten Stelle eine 1 haben. Die belegung der Bitstelle 2^j ergibt sich jeweils aus der Summe der (belegungen der) überprüften Bistellen modulo 2

Hamming Code Berechnen

Wie viele bits brauchen wir für die Parity?
- Um einen Hamming code zu berechnen schauen wir uns die datenlänge von dem ding, was wir senden wollen an.
- die menge an Paritätsstellen ist immer der $l o g_{2} (x)$ wo $x = D a t e n_{l \overset{a}{¨} n g e}$ (aufgerundet)
- Das macht bei 11-bit $3.45943...$ also $4$
Stellen bestimmen
- Jetzt schauen wir uns die bit-nachricht an, und stellen an die indizes die mit dem Wert einer zweierpotenz übereinstimmen eine Leere stelle, die wir mit der Parity-Zahl füllen werden.
- Bei unserer 11-Bit langen Datei sind das die Indizes 1, 2, 4 und 8.
Parity Berechnen
- Jetzt kommen wir an den lustigen Teil des ganzen
- Wir schauen uns die binärrepresenationen der Indizes der 1en und 0en an.
- Sprich, wenn wir eine Zahl mit 15 Stellen haben (wie bei unserer ursprünglich 11-bit Langen Datei) ist das 1111, 1110, 1101 etc. you get the point.
- Wir schauen uns dann alle Zahlen an, deren Index eine 1 ganz am ende hat.
- Hier bemerken wir, dass eine unserer Parity Zahlen auch eine 1 am ende hat, nämlich die 1 (oHhHHHHh).
- Das ist absichtlich, denn wir werden diese Zahl nutzen um die Menge an 1en an den stellen die wir gerade betrachten gerade zu machen.
- wenn wir also an index 7 und 3 eine 1 stehen haben, und sonst nirgendwo schreiben wir bei index 1 eine 0 hin, da wir ja schon 2 1en haben und 2 ist gerade.
- ebenso, würden wir wenn wir bei index 9, 7 und 3 1en hätten eine 1 an den index 1 schreiben, damit wir am ende 4 1en in der Gruppe hätten. (Damit unsere Zahl wieder gerade wäre)
- Das wiederholen wir jetzt mit allen zahlen die an der 2. stelle des Index eine 1 haben usw.
- Am Ende sollten dann alle lücken gefüllt sein.

Bussysteme

Memory - I/O Busse

Wat das eig?
ein Elektronisches leitungsbündel in einem digitalen Rechner
Kommunikationsmedium auf dem daten fließen können
- Zwischen CPU und Hauptspeicher
- zwischen CPU und I/O Geräten
- zwischen Hauptspeicher und I/O-Geräten
normierte Stecker
standarisierte Interpretation der einzelnen Leitungen

Heutige Bussysteme

USB
SATA
Thunderbolt
AGP
PCI-E

Morgige?

Thunderbolt?
USB 4?

Selbstaktende Codierung

Problem:
- Nur eine Leitung bei srielle Übertragung
- fehlende Synchronisierung / kein seperates Takt signal
- Wann beginnen einzelne bits? -> Es muss ein takt aus dem datensignal ausgelesen werden können
Keine Steuersignalleitungen
- Wo sind die blockgrenzen? was sind bus befehle bzw. daten?
  - Steuersignale sind bestimmte bitfolgen
Manchester Code:
- übertrage 2 Bits pro Datenbit
- Übergang in Taktmitte codiert Informatin
  - fallende und steigende Flanke
- andere Übergänge: Takt-Rückgewinnung
$\frac{nb}{( n + 2 ) \cdot b}$ -Codes
- Z.b. bei PCI-E, SATA, USB (ab 3.0)
- codiere $n$ Datenbits in $n + 2$ Übertragungsbit (früher $n = 8$ heute: $n = 64, 128$ )
- ~4 Möglichkeiten für jede $n$ -Bitfolge erlaubt primitive Fehlerkorrektur
- einige $(n + 2)$ -Bitfolgen repräsentieren Steuersignale
  - für $n = 8$ : Zwölf besondere Bitfolgen
  - für $n = 64, 128$ : Codiert über die ersten zwei bit ("Präambel")
    - "01": Nutzerdaten
    - "10": Steuer-/Nutzerdaten
    - "00"/"11": Nicht erlaubt, Fehler!

Prinzipieller ablauf einer Kommunkation

Datentransfer vom Hauptspeicher zu einer Festplatte

Der Prozessor fragt daten an
Liest die daten vom Ram in den cache
Fragt an ob er daten schreiben kann

Datentransfer von einer Festplatte zum Hauptspeicher

Prozessor fragt daten an
Prozessor sagt der festplatte was er will
Festplatte schreibt das ind en ram

Direct memory Access

Da ja leider die datenübertragung über den Prozessor den prozessor unnötig belastet kann ein eigenständiger DMA-Controller eingeführt werden
Dieser kann dann selbstständig daten aus dem sekundären (langzeit) Speicher in den RAM schieben wenn der CPU sie verlangt
Dadurch wird der Prozessor weniger Belastet
und es gibt unterm Strich einen höheren Datendurchsatz

Optionen eines Busses

Schneller	Billiger
Seperate Adress- und Datenleitungen	Multiplexen von Adress- und Datenleitungen
Breiter	Schmaler
Mehrere Busmaster erlaubt (Erfordert Schiedsrichter)	Nur ein Busmaster
synchrone Übertragung	asynchrone Übertragung

Zu guter letzt: Vielen dank fürs Lesen! Ich hoffe ich konnte ein wenig behilflich sein. VG, Tobi :)

Database Systems

SS 2024
Prof. Dr. Velasha Moonsamy

Databasesystem 01

Watn eigentlich data
Wir haben ein Definiertes Tabellenstrukt, das unsere Datenform vorgibt
Die meissten sachen die wir tagtätlich nutzen interagieren im Hintergrund mit einer Datenbank
- Praktisch alles was im Internet erreichbar ist macht irgendwas mit einer Datenbank, wenns daten speichert
Queries müssen dementsprechend sehr schnell bzw. was instant verarbeitet werden, damit man als User kein großen Slowdown spürt

Wasn nen Databasesystem?

Naja da ist dann ne menge von daten
Hauptsächlich eine Sammlung an Tabellenstrukturen die miteinander verwandt bzw. verbunden sind
Das wird von einem Sog. Datenbankmanagementsystem geregelt
Dieses Programm kann anfragen entgegennehmen und damit mit daten interagieren und sie auch ggf. zurückgeben
Wir haben allerdings auch "Application-Programs" die Transaktionen bzw. queries eröffnen / ausführen
- Transaktionen schreiben oder schreiben und lesen daten
- Queries lesen nur daten bzw, fragen diese ab

Core design Prinzipien von Datenbanksystemen

Alle daten müssen in der Datenbank hinterlegt werden
- Diese müssen alle das richtige schema beibehalten
- ggf. Redundancy
Wir müssen Operationen darauf ausführen können
- Daten abfragen bzw. queries
- Daten Updaten bzw. storage & manipulation
Es muss Permanenter Speicher realisiert sein, damit wir auch länger was speichern können
Wir müssen die daten Katogalisieren, sprich wir müssen alles irgendwie managen und durchsuchen können

User Requirements für Datenbanksysteme

Wir wollen ja unsere Daten sinnvoll verwalten können
Dafür brauchen wir dinge, wie z.b. ein User Interface
- Die sollten je nach "kompetenz" der Nutzer verschieden viel können
- Verschiedene Nutzer brauchen auch verschiedene ansichten der Selbem daten / brauchen nicht die selben daten
So brauchen wir z.b. auch sachen wie ein Account-System das uns dabei hilft die User voneinander zu unterscheiden

Wie modellieren wir unsere Daten

Wir haben bestimmte constraints
Diese constrainst müssen so gewählt werden, dass unsere Realisierung da gut reinpasst
Diese müssen auch durch Operationen einfach und sinnvoll modifiziert bzw. bearbeitet werden können
Dann haben wir Operationen mit denen wir
- Daten modifizieren
- Daten abrufen können
Wir machen das halt via Queries, die das DBMS dann halt abarbeiten kann

Datenmodelle können wir in einige Kategorien aufteien

Konzeptuell
- Auf dieser ebene gehen wir mal grundlegend davon aus, dass der user irgendwie nicht nen tiefes verständnis für DBMS dinge hat
- Wir modellieren alles auf einer Ebene, wie wir als "menschen" Daten verstehen
- Wir nennen das auch Entity-based Data, weil sie klassisch auch auf Objekten basiert
Physikalisch
- Physikalisch betrachten wir, wie die Daten auf den Speichermedien gespeichert werden
Implementation
- Hier können wir konzeptuell sachen modellieren und in einer Ebene die zwischen die ersten beiden fällt modellieren
- Sowas wie ein Relationelles Datenbankmodell
NoSQL
- Andernfalls haben wir ja auch noch die utopische vorstellung von selbst-dokumentierenden Code
- Das ist lustig und fundamental doof und kann nich tpassieren, aber NoSQL glaubt immernoch dran

Schma vs Instanz

Schema

Ein Schema speichert daten in Tables, data types etc.
E.g. wir speichern den kram als virtuelle dinge, die man in einem Diagramm darstellen kann

Instanz

Die Instanz ist das was am ende auf dem Computer läuft
Hier werden die tatsächlichen Daten gespeichert und überwacht

Three Schema Architecture

Wir haben Internale Schema
- Beschreibt die Physikalische speicherebene
- Speichert typisch alles auch direkt im Speicher
Conceptual Schema
- Hier werden die Constraintes etc. modelliert
- Verwendet wird hier eher Konzeptuelles zeugs
External Level
- Hier werden die Nutzer views beschrieben
- Hier wird der kram verwendet, der auch im Conceptual Schema da ist
Mappings
- hier werden die schema level miteinander verbunden
- Das hier sind meisstens Interne schema

Data Indipendence

Daten sind unabhängig voneinander
Die daten werden voneinander abhängig, weil wir mappings nutzen
Allerdings können wir oft an den unteren ebenen was ändern, ohne das die oberen levels sich verändern

Database Modelling

Wenn wir daten dann modellieren können wir das auch einigermaßen aufteilen
Wir schauen das wir alles irgendwie repräsentiert bekommen, damit das alles funktional passt

Entity Relationshop Model

Das ER Modell hat ein paar grundlagen
Wir haben die Entities
- Die können alle möglichen dinge darstellen
Relationshops
- Mit diesen können wir die Verbindung zwischen zwei oder mehr Entities klar machen
- Es gibt natürlich auch noch verschiedene Relationship-Models

Cardinality

Es gibt verschiedene arten von Relationen
1:1
2:2
M:N

Total and Partial Participation in Relationships

Wir können einige arten von Relationships ausdrücken
Wie iwr gerade schon genannt haben
Aber grob zusammengefasst gibt es totale participation und partielle participation
Hier ist der name sehr aussagend denke ich

MinMax Constraints

Es gibt ausserdem auch min und maximal constraints
wie "es kann mindestens 3 und maximal 10 leute geben, die einkaufen gehen"

Weak Entity Types

Weak entities sind dinger die keinen eigenen Key haben, und deswegen yeah.

Datenwanksysteme: Logical Database Modelling

Rub motorsport ist ist wieder da
Naja kennt man, oder nich?

Logical Database

Wir haben únsere requirements
Wir wollen jetzt eine krasse Datenbank aufsetzen und dann auch noch ne krassere datenbank bauen

Types of Logical Data Model

Key-Value
- naja halt das klassische key-value ding,
- jedes ding hat nen key, und dann kann man das so anordnen , keys nicht doppelt etc.
- Keine query sprachen (lol)
Document-Oriented-Data-Model
- Key-Value paare, wenn die daten semi-strukturiert sind
- Dokumente haben verschiedene Strukturen und sind sog. schemata
- Wir spezialisieren das key-value kram auf das "nötigste" damit man schneller suchen kann
- du kannst aber auch die dokumente durchsuchen, wenn man denn weiss wonach man sucht
- Diese art von datenbanken unterstützt normalerweise auch sowas wie collections etc.
- Viele unterstützen dann auch replikation und sharding, was sinnvoll für clustering ist
Graph Data Model
- Wir modellerien Daten die zusammenhängen
- Entities werden als knoten dargestellt und die verbindungen sind dann halt die kanten
- Es gibt zwie große datenmodelle
  - Ressource Description Framework (RDF)
  - Property Graph (Graph Databases) (Naja, graphendatenbanken / request formate wie sowas wie GraphQL)

Relational Data Model

The Origin

Eine Relation ist ein Mathematisches konzept die an die "Gruppentheorie" anhängt
Das modell wurde von irgendwem bei IBM in den 70ern erfunden

Core Structures

Structure	Description
Relation Shema	Sieht so aus wie die Tabellennamen etc.
Attribute	Halt der Name der einzelnen spalten
Relation or Tuple	Ist verbunden mit einer Zeile im table \
Jede Relation repräsentiert fakten die mit einer "echten" entity oder beziehung zusammenhängen
Relation Key	Attribut oder Menge an attribute die die daten in der Zeile identifizieren
Relation State	Eine gewisse menge von Zeilen in der Tabelle

Man kann sich das alles ein bisschen so vorstellen wie ne klassische datenbank
Sprich mit tabellen, Primary keys, Foreign Keys etc.

Relation Shema

Ein relationsschema bezieht sich auf die Beschreibung der Daten gezeigt durch $R (A_{1}, A_{2}, ..., A_{n})$
Ein schema besteht aus teilen:
- Name der Relation, oder auch $R$
- Eine Menge an Attributen (oder eigenschaften) der Relation, auch $A_{n}$
Jedes Attribut $A_{i}$ hat eine Domain $D_{i}$ oder eine Liste an richtigen werten, auch als $A_{i}$ bekannt
- Der name des Attributes zeigt welche rolle es in der Domain spiel t
- Die Domain insgesamt ist eine Ansammlung an atomic (oder auch global unsichtbaren) daten
- Um die Domain anzugeben, können wir verschiedene datentypen bzw. werte nutzen
Der Grad bzw. die Arity von einem Relationsschema wird von der anzahll seiner attribute vorausgesetzt

Wie isn das aufgebaut

Naja wenn wir uns das dann anschauen könnenwir sehen, dass uns das sehr an OOM sachen erinnert
Denn wir haben auf jeden fall die Strukturen von Klassen
§%15%§

Relation State

Eine Relation $r$ von einem Relationsschema $r (R)$ ist eine Menge an $n$ -tuplen $r = (t_{1}, ..., t_{m})$
- Sprich wir können daten nur innerhalb dieeser Reichweite haben, und ausserhalb ist dann narnia
Jeder der $n$ -tupel ist eine geordnete liste von werten bei dennen halt jedes element ein teil von einer domain ist
$v_{i}$ ist immer ein "Null" wert
Forell ist eine Relation eine mathematische relation von dem grad $n$ auf den Domains, die zutreffend sind

Wie isn das aufgebaut

Eine relation kann einfach daten bzw. keys von wo anderes importieren
sprich wenn wir z.b. sagen, dass wir die relationen von studenten haben, sprich $r (St u d e n t)$
- können wir sehen was für fächer usw. er studiert, und welche daten wie zusammen hängen

Interprätation von einer Relation

Jeder Touple repräsentiert etwas in unserer "virtuellen" welt
Jeder touple kann auch als statement bzw. fakt angesehen werdne
In unserem Relationsstatus können wir nur wahre aussagen haben, weils sonst halt keinen sinn macht

Constraints

Constraints definieren "regeln" die schauen was und was nicht in einer Datenbank erlaubt sind
Constraints müssen immer valid sein, sonst passt was nicht. Man kann die sich ein wenig vorstellen wie so assert statements
Es gibt vier Typen von inherenten constraints die in jedem Relation-Model ausgedrückt werden können
- 1. Domain
- 1. Key
- 1. Entity Integrity
- 1. Referential integrity constraints

Domain Constraints

Bei jedem tuple muss ein wert von jedem attribut atomic sein und aus der domain stammen
Sprich jeder wert muss aus der domain stammen und in das passende Schema passen

Key Constraints

Das sind subsets von attributen die einzigartig einen Tuple in einem relationsstate identifizieren
Wir haben Superkeys
- Die dinger sind eine Menge an attributen die folgenden conditions folgen
  - keine zwei touple können in der selben relation die selben werte für die attribute haben
  - Formell: $\forall t_{1}, t_{2} \in r (R) s . t . t_{1} \neq = t_{2}, it holds that t_{[} S K] \neq = t_{2} [S K]$
Schlüssel von dem Constraint ist ein "minimaler" superkey
- also praktisch ein superkey, der keine attribute entfernen und immernoch die selbe "einzigartigkeit" haben kann
- §%23%§
Jeder schlüssel ist ein superkey, aber nicht andersrum
- jedes subset von attributen mit einem key ist ein superkey
- aber ein superkey kann ein key sein (wenns denn minmal ist), das nuss aber nicht zutreffen (sofern es dann halt nicht minimal ist)
Wenn eine Relation mehrere Key-Kandidaten (haha) hat, wird einer als der primary key ausgewählt
- Das attribut das als primary key ausgewählt wurde wird unterstrichen
Diese Primary keys werden auch verwendet um tuples von anderen touples zu erreichen bzw. zu referenzieren
Wir wählen immer die kompaktesten keys, damit wir schön effizienz sind

Wie kann ich mir dat denn vorstellen?

Wir schauen uns ein relationsschema an
Da haben wir zwei schlüssel
die sind beide dann zusammen der superkey von unserem wert
Da allerdings noch mehr daten in unserer zeile sind, sind die zwei keys zusammen ein superkey, aber kein aussagender schlüssel
§%25%§

Entity Integrity Constraint

Das Primary-Key attribut ine inem relationsschema kann keine null-werte in der relation haben
§%16%§

Refeerential Integrity Constraint

Ein tuple in einer relation der auf eine Andere relation zeigt und auf eine bereits vorhandenen tuple in der relation verweisen muss
Tuples in einer referenzierenden relation haben foreign keys, die die PK attribute von einem anderen tuple, also einer anderen referenzeirten relation referenzieren
- $F K (R_{1}) = P K (R_{2})$

EER to Relational Mapping

Wir wollen schauen, wie wir jetzt diese "Beziehungen" die wir uns in unserem magical dream land entity relationship model zusammengebastelt haben in einer Relationalen Datenbank zusammen passen
weil das doppel-oval ist, ist "semester" ein Element mit mehreren werten
Es gibt am ende verschiedene Grundrelationen mit denen wir sachen zusammenfügen können
- Binäre Relationen
  - Also relationen wo 2 bres involviert sind
  - Auch bekannt als ein 1:1 relationship
  - Sprich jede entity hat auch genau eine andere, verwandte entity
- Dann gibt es noch 1:N bzw. N:1 Relationships
  - Hier werden unterschiedlich viele sachen zusammengehangen, je nachdem wie das im Kontext passt
  - Wir haben z.b. 50 Papiere in einem Drucker, aber logischerweise nicht 50 Drucker mit einem Papier each, denn das wäre offensichtlich DOOF
- Neben solchen expliziten Relationen gibt es auch noch N:M Relationen
  - Hier können beliebig viele dinge mit beliebig vielen anderen dingen abhängen
  - Das ist sinnvoll, wenn z.b. große abhängigkeitsstrukturen oder fammilien oder so modelliert werden müssen, denn rein Theoretisch, kann jemand n kinder haben....

DBS III

Constraints

Die Constraints setzen uns "regeln" und definieren was wann wo erlaubt ist
Die müssen unter allen validen Bedingungen fest halten, und auch wirklich gültig sein

Functional Dependencies

Wir brauchen für dependencies, mit denen wir Daten verknüpfen und oder zusammenbauen #
Wir nutzen hier das Akronym FD
Die Funktionalen Dependencies werden von den "bedeutungen" der attribute abgeleitet und stellen dar, wie die attribute miteinander Interagieren
Wenn wir eine Datenbank bauen, müssen wir verstehen, wie FDs daten über alle möglichen Verbindungen interagieren
Nur relation-states die mit den bestimmten FDs übereinstimmen bzw. diese Respektieren werden von uns als Valide akzeptiert

Inference RUles (IRs) for FDs

Wir betrachten "F" als menge von FDs die auf dem Relationsschema R definiert sind
Normalerweise werden die FDs aufgestellt, die semantisch "offensichtlich" sind
Allerdings gibt es auch sachen die von den FDs inferred werden können
"F" enthält alle legalen relationen auf der R, dementsprechend können wir schauen, wenn irgendetwas da rein passt / da drin ist, dass es dann dazugehört
Interferiert werden die dinge mit den sog. Armstrong Axiomen (yay)

Armstrong's Axiom

Soundness, Completeness and Closure

Sound
- Naja das passiert, wenn diese Regel jede mögliche relation die im originalen set enthalten ist enthält
Completeness
- Ist Complete, wenn wir die regeln wiederholt anwenden können, sodass alle möglichen FDs von der gegebenen Menge F abgeleitet werden können
Closure
- Eine Closure auf einer Menge F ist die Komplette menge von allen Funktionalen dependencies, die von F abgeleitet werden können

Closure

FD Closure
- Wenn F eine Menge von FD s ist, ist die closure $F^{+}$ eine Menge von allen FDs die logisch von F impliziert werden
Attribute Closure
- Wenn X eine Attribumenge ist, wird die closure $X^{+}$ eine menge von allen attributen B sein, dass $X \to B$
- Alos, dass $X^{+}$ alle attribute die funktional von X impliziert / abgeleitet werden enthält

Algorithm

Wir schauen das uns jeztt mal als Beispiel an
Dieses Format sehen wir warscheinlich auch in der Klausur / in der echten welt
Wir müssen immer wieder nachfragen und checken, ob das was wir uns vorstellen, tatsächlich zutrifft
- Das machen wir so lange, bis wir irgend eine Wand erreichen / irgend ein hindernis erkennen
Wir können sowas einfach "ausrechnen", wir müssen allerdings auch schauen welche vorraussetzungen und welche "guidelines" uns übergeben wurden

Cover and Equivalence of FDs

Equivalence
- Zwei mengen von FDs E und F sind equivalent zu einander, das impliziert, dass jede Menge alle FDs von der anderen Menge ableiten kann
Cover
- Eine menge an FDs kann eine andere Menge E überlappen, wenn jede FD in der überlappten menge E von F inferred werden kann
Minimal Cover of FDs

Normalization

Es gibt verschiedene Normalformen (die kommen von codd)
Es gibt eine stärkeare ausführung der 3NF, das ist dann die Boyce-Codd normalform BCNF
Es gibt auch mehrere, allerdings betrachten wir hier nur die ersten 3

1NF

Keys
- Dürfen keine multiwertattribute haben
- Keine zusammengesetzen attributen
- Alle keyattrubute dürfen nur einen wert haben
Setzen sicherheit, integrität und simplicity vorraus, und verhindern komplexe strukturen
jede DB der 1NF limitiert sich auf simple, atomic werte, wo jedes attribut einnerhalt eines Tupels ist, wodurch die komplexität von verschachtelten relationen eliminiert wird

2NF

Eine 2NF ist eine 1NF auf der alle nicht-key elemente funktional von dem primary key abhängig sind, dementsprechend gibt es keine partiellen dependencies
2NF baut auf dem prinzip der "vollständigen abhängigkeit"
- Full Functional Dependency: Jedes Attribut Y ist vollständig funktional abhängig von einer menge von attributen namens X, wenn die abhängigkeit abbricht, wenn ein attribut von x entfernt wird.
  - Also: Y ist von allen X gemeinsam abhängig
- Partial Dependency: Passiert, wenn ein attribut Y immernoch auf einem subset von X abhängig ist, was zeigt, dass nicht alle elemente von X für diese Relation benlötigt wird
2NF ist sehr wichtig, wenn man verdopplungen verringern will, und daten nur dann ordentlich abzuspeichern, wenn sie von einem vollständigen primary key abhängig sind

3NF

Eine Relation ist in 3NF, wenn sie schon 2NF ist, und kein nichtprimäres Attribut eine transitive abhängigkeit zu dem Primarykey hat
- Eine Transitive Dependency ist eine funktionale Abhängigkeit $X \to Y$ ist genau dann transitiv, wenn es eine mittelmenge $Z$ gibt, sodass $X \to Z$ und $Z \to Y$ gilt, und Z nicht teil eines Kandidatenschlüssel ist
- Achieving 3NF enhances database design by ensuring each non-key attribute is directly related to the primary key, eliminating indirect dependencies that can cause data anomalies

Boyce-Codd Normalform (BCNF)

Die BCNF ist eine striktere version der 3NF
Eine Relaiton ist genau dann BCNF, wenn es in 1NF ist und jede nicht-triviale funktionale dependency $X \to A$ X ein superkey von $R$ ist
Anders als 3NF, erlaubt BCNF keine nicht-superkey funktionalen dependencies, wo die rechte hand primäre attribute sind. Die absence macht BCNF strikter

3NF VS BCNF

Die meissten Datenbanken die 3NF erreichen erfüllen auch BCNF.
Um sich an BCNF zu halten, müssen viele sich an BCNF halten, um redundanz und datensicherheit zu maintainen

DBS II: Relational Algebra and Calculus

Relational Algebra and Calculus

Wir haben einige tolle Operatoren
Herzlich willkommen im Shouty-Case-Land

SELECT

Wir wählen kram aus um kram zu machen
$σ$ ist das Zeichen was wir dafür verwenden
Damit machen wir dann wie sachen aussortieren
Wir können damit boolean expressions modellieren, um halt weiter einzuordnen was wir auswählen wollen
Bester punkt ist sowas wie "SELECT * FROM WHERE "
Wenn wir was auswählen kriegen wir logischerweise nur das, was unseren "bedingungen" entspricht
Wir können die Selections dann auch stacken und weiter subsetten etc.
- Wenn wir z.b. etwas aus einer riesigen tabelle grob selektieren, und auf dieser selektion dann weiter filtern
- Je nachdem wie gut wir das dann filtern, kann man dann auch mit Joins etc. arbeiten

PROJECT

Mit der PROJECT operation können wir einige attribute auswählen die wir nöher betrachten wollen
$π$ (R)
Nach dieser Operation haben wir dann nur noch die ausgewählten attribute in unserer liste, in der reihenfolge die wir definiert haben
Diese operation entfernt zudem auch noch allemöglichen duplikate, damit der kram irgendwie einigermaßen stabil läuft
Alle Attribute die wir Projecten wollen müssen auch schon in der ausgehenden Query / Tabelle vorliegen, damit wir das machen können. Also, muss die angegebene Attributsliste ein Subset der ausgehenden sein

RENAME

Wir können damit relationen umbennen (was ein wunder)
Das macht sehr viel sin, wenn wir kram mergen, joinen oder projezieren oder so

Kurzer Exkurs zur Mengentheorie

Wir kennen aus Hömmi 1 und logik die vereinigung, den Schnitt, die Differenz und das Kreuzprodukt mit denen wir kram irgendwie zusammen verbinden können
Das geht auch in den tollen datenbanken, damit wir schön und toll und effizient suchen können
Zwei Relationen sind Kompatibel, wenn sie die gleiche anzahl an attributen haben
Die Domains müssen auch type-Kompatibel sein, dementsprechend müssen sie die beiden werte verwalten können

UNION

Wenn wir etwas vereinigen wollen können machen wir das einfach
Dann werden die einfach verbunden, und "aneinandergehängt"
Ebenso werden gedoppelte tupel eliminiert
Idealerweise wird das dann so gemanaged, dass die sachen vernünftig gejoined werden, wenn der kram aufeinander passt (sprich wenn die irgendwie verbunden sind mit keys, dass die keys dann auch gelinked werden)

INTERSECTION

Wenn wir einen Tupel haben, der in beiden ist wird dieser von dieser selektion mitgenommen
Das bedeutet, dass wir alles suchen, was in A UND in B ist, aber nicht nur in einem von beidem

SET DIFFERENCE

Die SET DIFFERENCE Operation, zeigt dir alle sachen die in Relation $A - B$ sind, also alles was in A aber nicht in B ist
Damit können wir kram noch weiter einschränken und damit noch besser suchen

CARTESIAN PRODUCT

Mit dem Kartesischen Produkt, oder auch X wird verwendet um zwei tupel miteinander zu kombinieren
Das machen wir dann mit einem Tupel, der die Relationen zwischen den beiden (oder mehreren) dingern repräsentiert.
Der wird dann erschaffen, damit wir die beziehungen klar definiert haben, und das dann einfach schön zusammen passt und der zusammenhang offensichtlich erkenntlich wird

JOIN

HAHAHAH YEAH DER JOIN IST DA
Naja, wir können mit dem join $⋈$ kram joinen
Der join kombiniert ein Kartesisches produkt und select
Wir können also Tabelle A mit Tabelle B joinen, wenn die irgendwelche überlappende elemente haben, anhand von denen wir zuordnen können.

DIVISION

Wir können die division wie ein "umgedrehtes" Kartesisches Produkt verwenden.
Das macht sehr viel sinn, wenn wir den kram einfach umdrehen
Wir nehmen also alles was nur in A ist, nur halt nicht in B
AUch bekannt als der "ohne" operator in der Logik

Aggregate Funcvtions and Grouping

Manche sachen können wir nicht vernünftig ausdrücken mit den sachen die wir vorliegen haben
Wenn wir das dann machen schauen wir uns mehrere sachen zusammen an
Generell "aggregieren" wir daten, um sie halt zusammenzufassen
Am ende bekommen wir praktisch ein großes (oder zusammengefasstes) Element was dann am ende kram macht
§%38%§

Queries

Mit queries können wir ja logischerweise kram definieren und dann auch suchen
Die queries repräsentieren die ausdrücke die wir auf unseren datensatz anwenden wollen, um eben das ziel zu erreichen

Relational Calculus

Das ist eine tolle deklarative Sprache
Wir können kram machen
Wir nutzen so die relationen in der datenbank um daten zu sortieren und daraus sachen zu lesen
§%48%§
§%49%§
§%50%§
§%51%§

SQL as DQL

Watn das?

Structured Query Language als Data Query Language
Wir schauen uns heute das "normale" SQL, was alle DBMS sharen an
Leider können wir nicht alles in Tupeln modellieren
Dementsprechend schauen wir, das wir das anders (mit joins etc.) modellieren können

Queries

Mit queries können wir logischerweise Daten abfragen bzw. modifizieren
Identifizieren tun wir die wie gehabt mit column row und table
Wir müssen heutezutage nicht mehr alles in Shouty-Case machen, aber das ist gut, um zu spezifizieren was daten(typen) und oder Logikanafragen etc. sind
Logischerweise können wir alles irgendwie stacken und so sehr komplexe Queries bauen

SELECT-FROM-WHERE

Das ist die "simpelste" sache die du machen kannst
Hier fragen wir einfach daten anhand einer Condition ab, nichts wildes, sollte einfach zu verstehen sein

SELECT attribute, list FROM table WHERE condition;

Vergleich zu Relationaler Algebra

WHERE Clause

hier "passiert" die Condition
Es gibt verschiedene Conditionale Operatoren
- Vergleichsoperatoren (Sprich $>, <, \geq, \leq, =, \neq =$ )
- [not] between x and y
- [not] like patternX
- is [not] in listY
- is [not] distinct from
- is conditionZ
- is {[not] true | [not] false}

Matching Strings

Strings sind immer von '' umgeben
Ebenso sind sie case-sensitiv
Um zu suchen können wir wildcards verwenden:
- % für eine beliebige Anzahl von arbiträren Zeichen
- _ für genau ein Zeichen
Diese wildcards können mit anderen Wildcards und Zeichen kombiniert werden
Diese ggf. kombinierten Queries können dann in einer Query wie SELECT first_name, last_name FROM employee WHERE last_name LIKE %man_; verwendet werden;

Querying Multiple Tables

Wir können auch mehrere Tabellen gleichzeitig betrachten und Abfragen
Das machen wir, indem wir mehrere Tabellen zusammenjoinen
- Joins brauchen ja schon eine (oder mehrere) condition(s) um zusammengeklebt zu werden
- Relational ausgedrückt sieht das dann so aus:
  $T_{1} ⋈ < joinn condition > T_{2} := σ < join condition > (T_{1} \times T_{2})$
- In SQL sieht das dann So aus:
  SELECT first_name, last_name, address FROM employee, department WHERE department.name = 'Research' AND department.number = employee.department_number;

Renaming

Manchmal haben wir das problem, dass mehrere Attribute den gleichen Namen haben
Damit das nicht zu einem Problem wird, können wir dann Tabellen usw. umbenennen
Das machen wir mit dem as keyword
Sprich SELECT name as employee_name FROM employee WHERE name = 'Friedrich Wilhelm XXVI';

Multi-Set Operatoren

Diese Operatoren können verschiedene Formen annehmen, die wir schon aus der Mengenlehre kennen.
- So kann man z.b. die UNION nehmen, als auch INTERSECT und EXCEPT
- Wichtig ist hier, den unterschied im Kopf zu behalten, denn sonst kann es lustig werden

Joins

Mit joins kann man tabellen zusammensetzen
Das geht mithilfe von Spalten die den gleichen wert haben (sprich Foreign-Key / Primary-Key paare o.ä.)
Wir können dann so eine RIEEESIIGE Tabelle erschaffen, die dann am ende alles enthält
Falls man keine Spalte mit den selben Namen und werten hat, kann man mit dem USING operator auch einiges schaffen
Das sieht dann in etwa so aus: USING (department.number)
Alternativ gibt es auch noch den ON Operator.
- Der sieht dann so aus:
  SELECT D.number, E.ssn, E.first_name, E.last_name FROM employee AS E JOIN department AS D ON E.ssn = D.manager_ssn;
Diesen Operator kann man auch mit einer Condition verbinden, um dann beim Joinen noch auszusortieren.
Joins kann man übrigens auch auf sich selber ausführen, wobei man dann auf jeden fall die Attribute umbennen muss
Es gibt bekanntlich auch noch den outer join, aber wo ist denn da der unterschied?
- The join between two tables, which returns the values of an inner join and the unmatched rows from the left (or right) table, is called left (or right) outer join
- The join between two tables, which returns the values of an inner join and the results of a left and right outer join, is called a full outer join
Beim joinen werden leere Werte immer mit NULL aufgefüllt

Doppelte Werte Entfernen: DISTINCT

Normalerweise passiert das öfter, dass wir doppelte werte haben
Das ist manchmal nicht ganz so passend, wenn das so ist
Deswegen klnnen wir dann mit dem DISTINCT Operator identische Tuple bzw. Reihen einfach entfernen
Syntaktisch wird der Operator einfach hinter SELECT aufgerufen, also: SELECT DISTINCT FROM...

Resultate Sortieren

Es gibt auch noch den ORDER BY operator
Damit können wir sachen (wer hätte es gedacht) Sortieren
Das machen wir mit den datentypen und ner Richtung (ASC für ascending, DESC für decending)

Verschachtelte Queries

Um richtig Fucked Up Queries zum (rekursiven) Suchen zu basteln können wir mehrer SQL queries ineinander verschachteln
So können wir z.b. auf das Resultat von einer Query eine weiter ausführen (denn unterm strich ist das resultat einer query immer eine tabelle, nur manchmal ist da halt nur ein einzelner, alleiner, nutzloser und echt blöder Wert drin)
Falls das nicht das ist, was wir machen wollen, können wir einfach den COMP Operator nutzen um etwas zu VERGLEICHEN (BOAH KRANK HAHAHAHAHAHAHAHHAHAHAHAHAHHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHHAHAHAHAHAHHAHAHAHAHAHHAHAHAHAHAHAHAHHAHAHAHAHA) (ja, ich hab keine lust mehr)

EXISTS

Wir können mit EXISTS und NOT EXISTS schauen ob was da ist lol

Programming Database Applications

Naja, wir haben jetzt einiges an zeit damit verbracht zu verstehen wie "tolle" datenbanken funktionieren
aber mit diesem wissen können wir irgendwie nicht viel machen ausser daten speichern, was irgendwie nen bissl langweillig ist
Deswegen schauen wir uns jetzt mal das Programmieren mit DBsses an

Erstmal ein Beispiel

Wir wollen ein tolles neues Stripe entwickeln
Das ist ein sehhhhr naives beispiel
Wirspeichern user mit diesen Feldern
- uuid
- username
- balance
Ebenso speichern wir jeden Transfer
- uuid
- sending user
- receiving user
- transferred amount
Das speichern wir (wie man sich warscheinlich schon denken kann) in einer massiv coolen datenbank

Wie würden wir sowas umsetzen

naja bisher haben wir uns immer alles mit der CLI angeschaut, also könnten wir das hier auch machen
allerdings müssten wir hier DREI SQL queries ausführen
Das ist halt für unsere nutzer ziemlich doof, weil naja, wir können die ja nicht einfach an unsere database lassen
Wir haben generell drei grundlegende fragestellungen
- 1. Wie stellen wir sicher, dass jeder nutzer wirklich die drei queries ausführt
  - wenn nicht alle queries ausgeführt werden könnten wir einfach unendlich geld erstellen
- 1. Wie gehen wir sicher, dass nur der nutzer selber auf seine Daten zugreifen kann?
  - Jeder nutzer sollte nur auf sein Konto zugreifen können, und eben nicht auf das von anderen leuten
  - Dementsprechend müssen wir dann authentifizieren, aber wie machen wir das?
- 1. Die UX muss gut sein, denn user müssen alles irgendwie "einfach" ausführen können
  - Denn wenn alles nicht gut und sicher ausgeführt wird, funktioniert unsere app nicht
  - und wenn unsere app nicht die schönste Prinzessin im ganzen land ist, dann wird sie nicht erfolgreich

Lösungsansätze

Two-Tier Architecture with Stored Procedures

Wir implementieren die Logik mithilfe von stored procedures
- Diese werden in der Datenbank hinterlegt und sorgen dafür, dass immer alle drei sachen ausgeführt werden, auch wenn wir nur einen Aufruf haben
Wir limitieren den Beispiel zum DBMs mit dem integrierten DBMs access management
- Das können wir machen, indem wir jedem user seinen eigenen User erstellen, womit er nur auf SEINE daten zugreifen kann, und auf daten die mit ihm geteilt sind
Wir entwickeln einen Client der die Datenbank wegabstrahiert und den Useren erlaubt "einfach" die App zu nutzen, ohne das sie fähigkeiten oder wissen zu den DBMS oder auch SQL haben müssen
- Wir entwickeln einen DB driver (oder naja, nutzen einen bestehenden) der dann das CLI ersetzt.
- Dann können wir auch "einfach" eine App oder ein Webinterface oder so schreiben, was dann alles implementiert etc.

Das hört sich doch erstmal alles super toll an, oder?
- Wir haben wenige bewegliche teile
  - wir brauchen nur das DBMs und seine clienten aufrecht zu erhalten
  - der Client ist relativ leicht
- Wir haben Sicherheit indem wir die Privilegien gut rausseperieren können
  - Damit ein Angreifer etwas "sinnvolles" erreichen kann, muss er das DBMS selber angreifen
  - Das ist sichergemacht dadurch, dass wir unseren Nutzern generell nicht vertrauen
- Und wir sind gegen datenverlust gesichert
  - Denn wenn eitrwa fehlt, werden unsere daten wieder schön zurückgerollt
  - weil das eben so durch das DBMs überwacht wird
Ganz so rosig ist das dann aber doch nicht
- Für entwickler ist das ein bissl sehr nervig
  - Stored Procedured sind halt schon nen bissl massiv nervig
  - Testen wird sehr schwer, weil die stored Procedures halt nicht teil des programms selber sind, sondern irgendwie anders im DBMS liegen und so schlecht getestet werden können
- Ebenfalls wird das dadurch sehr schwer das zu debuggen
  - Denn die stored procedures nerven ein wenig und sind halt irgendwie nicht besonders "toll" und loggen auch nicht wirklich
  - Leider sind die errors die wir hierfür bekommen dementsprechend besonders kryptisch und machen generell keinen spaß zu debuggen
- Ausserdem muss die Datenbank eben an die clients exposed werden, was inhärent ein Sicherheitsrisiko ist, was dazu führt, dass wir uns direkt wieder ein weniger unsicher machen
  - Zudem entsteht dadurch eben eine vermeindlich große angriffsfläche, die halt für uns dann wieder nen bissl schlecht sind
  - wenn eine Datenbank direkt ins Internet exposed ist, macht uns das direkt angreifbar und ist generell ne ziemliche bad practise

Two-Tier Architecture with Fat Clients

Wir implementieren unsere Business Logic innerhalb des clients in der Sprache des clients
- Hier können wir dann unsere lieblingssprache nehmen und dann dementsprechend ggf. auch schöner einbinden
- Die clienten können ausserdem schneller und genauer auf daten zugreifen, weil sie durch die direkte implementation einfacher zum bearbeiten sind
jetzt können wir deutlich sicherere permissionsverteilung machen
- leider müssen die clients immernoch "direkten" zugriff haben, dennoch sollte das dann einfacher möglich sein
- wir müssen allerdings weiterhin "einfach vertrauen" denn irgendwie kommen wir da nicht herum
- Wenn leute Zugriff auf den client haben, können sie ausserdem das passwort o.ä. "einfach" direkt aus dem client auslesen, und dann halt dementsprechend auch einfach blöde dinge tun
- wenn unsere Datenbank nicht richtig gesichert ist, könnten sie zudem auch einfach die daten von anderen leuten anschauen oder traffic snoopen
- Leider funktioniert das alles nur, wenn der Client wirklich vertrauenswürdig ist
die GUI ist weiterhin einfach eine GUI, genau so wie vorher

Ist das die lösung für uns alle?
- Es ist immernoch sehr simpel
  - wir brauchen immernoch nur das RDBMS und müssen nur clienten accounts machen
- Jetzt ist die Development Experience deutlich schöner
  - die logik ist in "richtigen" programmiersprachen deutlich durchsichtiger und wir können dementsprechend echt schön alles filtern etc.
- Das debuggen ist auch einfacher, denn alles ist ja wie gesagt einfach direkt integriert
Leider immernoch nicht das Rezept für den Weltfrieden
- Wir müssen weiterhin unseren clients vertrauen, was wir irgendwie immernoch nicht machen wollen
- Da die user immernoch von ihrem gerät aus zugreifen, könnten die einfach irgendwas machen, usw.
- Daher müssen wir auch jedes mal, wenn irgendetwas an der DB geändert wird, den Client updaten, und alle bisherigen clients gehen einfach kaputt, was halt auch nen bissl blöd ist
- Ausserdem muss jetzt alles in jedem client gespeichert werden, was irgendwie nicht so geil ist
  - Vor allem wenn wir ein cross-plattform system nutzen, ist das echt irgendwie nicht besonders toll, und wir müssen dementsprechend das jedes mal irgendwie neu machen
- Wie gesagt muss die DB immernoch ans offene Internet exposed werden, was halt am ende dann doof ist

Three-Tier Architecture

Yay, wir haben noch ein weiteres tier

Wir implementieren weiterhin die Business Logic in einer "tollen Programmiersprache"
- Hier nutzen wir weiterhin die vorteile davon, alles integriert zu machen
Wir autorisieren jetzt auf einem application server
- Der Server ist von uns trusted, und kann so "mehr" machen
- Wir steuern den über HTTP an und müssen so nicht mehr die DB exposen
- Wir können deutlich feiner seperieren und mit deutlich mehr genauigkeit autorisieren
Der Client ist jetzt "simpler" und interfaced nur mit dem Server
- So müssen wir die Datenbank nicht mehr ans internet exposen, und alles wird für uns unendlich einfacher (yay)
- Bei updates an der datenstruktur etc müssen wir nicht immer den Client updaten, denn jetzt kann der Server etwas als "übersetzer" fungieren
- Der client enthält nichts mehr von der "richtigen Datenbank" und kann dementsprechend auch nicht mehr dadrauf zugreifen oder durch irgendwas dummes die Datenbank compromisen
- Gutes beispiel sind hier websiten

Jetzt ist das wohl unser Erfolgsrezept?
- Die development experience ist wie gesagt weiterhin toll
- Das debuggen ist noch einfacher, denn wir wissen direkt in welchem teil der "Kette" das alles passiert
- Wir müssen das DBMS nicht exposen
  - Der Server ist warscheinlich auch generell einfacher zu sichern, als eben das DBMS
- Änderungen in der Datenbank macht uns nicht direkt den Client kaputt, denn der Server kann hier übersetzen
- Dementsprechend müssen wir nur eine sache updaten, und nicht wieder jeden client der überall auf der welt sein kann
- Wir können permission sehr schön ausseinanderhalten
Naja nichts im leben ist "einfach" nur toll#
- Wir haben einen höheren entwicklungsaufwand, denn wir müssen jetzt auch noch einen Server entwickeln und die Clients müssen irgendwie auch mit dem Server kommunizieren
- Wir haben mehrere sachen die kaputt gehen können, denn jetzt haben wir ja auch noch den client
- Wenn der Server aus irgendwelchen gründen übernommen werden kann, ist unsere datenbank trotzdem hiii
  - Das ist halt wieder doof, weil wir denken, dass wir unserem server vertrauen können
  - Allerdings ist hier auch wieder die best practise wichtig, einfach generell so wenig daten zu verteilen wie möglich

Was ist jetzt die Erkenntnis?

Die Architektur die wir uns aussuchen hat am ende dann doch noch wirklich große auswirkungen auf die Sicherheit unserer App und ist dementsprechend auch sehr wichtig
- Leider kann man das auch irgendwie nicht später ändern und dementsprechend ist hier sehr gute überlegung vorher wichtig
Die Wahl der Architektur ist aber auch oft einfach mehr abhängig von den umständen in denen wir uns gerade befinden, als das wir wirklich einfach tolle sachen machen können
Manchmal kann man aber auch einfach mischen, was uns dann "the best of both worlds" liefern kann
- Es kann aber auch einfach maximal schlimm sein (oh no)
Die meissten DBMS unterstützen alle oben erwähnten modelle, weil sich für die halt am ende auch nicht so viel ändert

Programmierte nutzung von Datenbanken

wenn wir programme schreiben haben die programme auch gleichzeitig die möglichkeit unsicher zu sein
das ist (meisstens) nichts was wir uns aussuchen, aber dennoch kann das einfach passieren
So können z.b. SQL Injecitons passieren, wenn man unvorsichtig ist
- Die dinger kann man umgehen, wenn man seinen Input Sanitized
- Das machen wir, indem wir nach schemata suchen, und hier ist nicht einfach nur "String" eine sinnvolle abfrage
- Generell ist es eine dumme Idee, den nutzern überhaupt zu vertrauen
Wir sollten also vermeiden, direkt nutzersachen in die Datenbank zu kloppen
Wie machen wir das? mit prepared statements.
- Die prepared Statements können dann für uns einfach die sanitazation machen lassen
- Denn die können das bestimmt besser als du und ich (zusammen)
Allerdings schreiben wir hier immernoch unsere Queries selber
- Das kann zu fehlern führen, die oft auch schwer zu finden sind
- Zudem müssen wir die daten aus dem RDMS "von hand" in die SQL queries mappen, und andersrum
- Ausserdem passen oft die datentypen nicht, schaut euch teilweise auch einfach mal JS an (da passt eh nie irgendwas, also naja...)
Das können wir übergehen, indem wir einen Object Relational Mapper oder auch ORM nutzen.
- Das ding, kümmert sich darum, das sachen die wir "einfach" in unserer lieblingsprogrammiersprache anwenden können auch in der SQL datenbank dann funktionieren.
- Dadurch können oft fehler und sicherheitsücken unterbunden werden
- dann du interagiertst nicht mehr direkt mit der datenbank, denn eben das (was auch der "gefährliche" teil ist) macht jetzt der ORM
- Ausserdem ist das dann von der developer experience deutlich schöner, da alles einfach innerhalb deiner programmiersprache passiert

Hibernate

Ein (scheinbar) bekanntes ORM-System ist "Hybernate"
Das ding ist nen framework für Java was von einer Firma namens "JBoss" (schon kranker name) entwickelt wurde und heutezutage (wie so vieles) von den menschen mit dem Roten Hut (RedHat) maintained wird
Hibernate verfolgt hauptsächlich den weg des "Data Mappers", denn es generiert einfach allen SQL kran selber, und macht dementsprechend auch alle sachen die bei umzügen anfallen selber
Es greift auf Annotations zurück die mit den Tablestrukturen populiert werden, was dann dme ding alle "Wichtigen infos gibt"

Storage and Index Structures

Bisher haben wir uns nur die Architektur von Datenbanken selber angeschaut
Wir haben uns auch schon angeschaut wie man "gute" Applikationen mit Datenbanken schreiben kann
- So sachen wie Two- oder Three-Tier Architekturen sollten inzwischen ein Begriff sein
- Wir haben direkt damit auch schon gelernt, wie die Sicherheitsstrukturen von verschiedenen DBMSs aussehen können
- z.B. dass Prepared Statements sicherer gegen SQL-Injections sind und,
- dass ORMs uns die Arbeit mit Datenbanken vereinfachen
Wir haben also inzwischen nen guten Überblick über Datenbanken as a whole
So können wir dann also schon Systeme damit schreiben und sinnvoll mit Datenbanken interagieren
Heute wollen wir uns mal anschauen wie das DBMS unter der Haube funktioniert

Physical Storage

Wenn wir uns mal so einen PC anschauen haben wir diverse Speichermedien
In erster Linie kennen wir natürlich unser Systemspeicher (den RAM)
- der ist, wie wir inzwischen hoffentlich wissen, ziemlich schnell
- Da er direkt mit dem CPU verbunden ist
- Das bedeutet aber auch, dass wir nicht besonders viel davon haben
Daher haben wir auch das was wir als Sekundären Speicher bezeichnen
- Das sind "weiter entfernte" Speichermedien wie SSDs oder auch HDDs die via Storage Controller angesteuert werden. (Hier ein flashback an Rechnerarchitektur)
- Auf diese Sekundären Medien wird auch via den Primären Speicher zugegriffen, da alles erst in RAM geladen werden muss, bevor der Prozessor (oder auch andere Module wie eine GPU) damit arbeiten können, da sonst die Datenübertragungsgeschwindigkeit einfach nicht ausreicht
- Wenn wir genauer auf unsere Sekundären Speichermedien schauen sehen wir, dass das in den meissten fällen Block-Storage Devices sind

Block Storage Devices

Block Storage bedeutet, dass unsere Speichermedien in "Blöcke" separiert sind mit denen wir dann die Sachen speichern und darstellen können
Wir nennen diese "Blöcke" auch Sektoren
Jeder Sektor kann nur vollständig oder garnicht beschrieben werden
Daher sind die Sektoren meisstens eher klein, um so wenig speicher wie möglich zu wasten und gleichzeitig auch nicht zu viele sektoren für große Dateien zu brauchen
Jeder dieser Sektoren ist direkt addressierbar via Logical Block Addressing
Wie bei so vielen Dingen im Leben ist auch hier sequentielles Lesen deutlich schneller als Random Lesen
- Das liegt in der HDD grundlegend daran, dass sich der Kopf (dat ding was die Drehende Disk abliest) sich weniger bewegen muss
- Und bei SSDs bedeutet das, dass der Controller zwischen weniger Blöcken / Storagemedien hin und her springen muss (Eine SSD besteht meisstens aus mehreren NAND-Chips, google wat das ist, wenns dich interessiert)
Insgesamt können wir festhalten, dass wir versuchen unsere Daten so effizient und so Kompakt wie möglich zusammenpacken wollen damit wir am ende möglichst wenig Speicher verbrauchen
- Gleichzeitig versuchen wir aber auch, alles was zusammengehört zusammen (oder zummindest nah beieinander) zu speichern, damit wir möglichst sequentiell lesen können

File System

Damit wir irgendwas mit den Blöcken anfangen können liegt auf unseren Sekundären Speichermedien meisstens noch ein virtuelles Layer: Das Filesystem (FS) (Nicht verwechselnn mit fachschaften lol)
Das Filesystem funktioniert am ende ähnlich bzw. genau so wie unsere Blockstorage devices, denn auch das Virtuelle FS ist in blöcke bzw. Sektoren aufgespalten
Diese Blöcke entstehen dadurch, dass wir Physische Sektoren zu größeren Blöcken gruppieren, die auf unsere Anforderungen zugeschnitten sind.
- Diese Gruppierten Blöcke sind oft größer als die darunter liegenden Physischen Blöcke, aber genau deswegen machen wir das ja
Idealerweise starten diese Virtuellen Sektoren auch da, wo unsere Physischen Sektoren starten, das macht uns später das addressieren einfacher
Jeder Virtuelle Block kann bis zu einer datei enthalten (oder auch nur ein teil eineer Großen datei), sie werden aber nie unter mehreren Dateien aufgeteilt
- Sprich wenn eine Datei nur 1,5 Blöcke aufbraucht, ist der letzte halbe block frei
- Das ist ein bisschen wasteful, allerdings können wir so effizienter Addressieren

RDMS

Jetzt haben wir uns (mehr oder weniger) durch die Schichten durchgearbeitet und sind wieder beim DBMS angekommen
Unter der Haube speichert unser DMBS alles wie "normale" Programme auch als Dateien.
Diese Dateien spaltet as DBMS in sog. Pages
Diese sind praktisch dasselbe wie unsere "Blöcke" auf FS ebene
Diese Pages sind auch mit dem Sektorstart angeordnet
Wenn wir jetzt etwas von einer Bestimmtne Page laden wollen, wird diese zunächst auch in unser Primäres Speichermedium, also den RAM geladen
Von da aus können wir dann "schnell" auf diese Zugreifen, da RAM ja ziemlich schnell ist, wie wir wissen (hihihi)
Das nennen wir "buffering"

Records

Wenn wir in der Leiter der Abstraktion noch weiter nach oben rücken, sehen wir, dass wir inzwischen wieder da Angekommen sind, wo wir vor ein Paar wochen waren: Records
Diese sind, wie wir ja schon wissen, eine Kollektion von Werten in einem Reihen-Orientierten Modell
- Sprich jeder Record ist eine Reihe in einer Tabelle
- Jeder der werte die einen Tupel bzw. Record zusammensetzen hat daher auch seine eigene Zelle
- Wir nennen diese Speicherarchitektur auch ein $n$ -ary Storage-Model
Da wir alle unsere Werte in Records bzw. Tupeln speichern, können wir sicher gehen, das alles auch in Virtuelle und darunter dann in Physische Blöcke aufgeteilt wird, und das auch überall alles irgendwie Sortiert zusammenpasst
Wie genau das Funktioniert kann man hier sehen

Wie finden wir jetzt kram?

Naja, das ist die Frage die uns warscheinlich (mit) am meissten Interessiert
Wenn wir uns anschauen wie der kram gespeichert wird, sollten wir auch wissen, wie dieser gespeicherte Kram durchsucht wird
dafür gibt es (natürlich) verschiedene Möglichkeiten

Full-Table Scan

Wir laden uns eine Page in den RAM
Dann iterieren wir durch alle Records in dieser Page mithilfe des Slot-Array (das oben angegebene Beispiel)
Für jeden der Records schauen wir, ob unsere condition zutrifft (die, die wir bei der Query angegeben haben)
Und dann laden wir die nächste Page und machen das so lange, bis wir alle pages durchhaben
Am Ende spucken wir dann alles aus, wo die Condition gepasst hat

Index Structures

Indizes sollten uns allen schon ziemlich bekannt vorkommen
Mit denen können wir dinge "sinnvoll" und schnell durchsuchen
Wenn wir also in unserer DB alles sinnvoll durchnummerieren und mit indizes Versehen können wir vieles einfach schneller durchsuchen
Die Indizes werden dann genutzt, damit wir mit bestimmten Conditions schneller durch unsere DBs iterieren können
- (Daher sollte man auch immer ne ID haben lol)
Um einen Index zu bekommen können wir praktisch jedes (feld) attribut nutzen
- Ein Index kann zu mehreren Attributen passen
- Ebenfalls können mehrere Indizes zu einem Attribut gehören
Index strukturen brauchen allerdings zusätzlichen Speicher und auch zusätzlichen Aufwand

Hash-Indizes

Indizieren via Hashes ist inzwischen etwas was wir alle ziemlich gut kennen und auch irgendwie Hassen gelernt haben (besonders in Info 2 gott verdammt)
Wenn wir via Hashing indizieren wollen können wir das wieder mit unseren Eimern machen, und hoffen, dass das danach nicht alles im Eimer ist (haha)
Dafür brauchen wir dann eine weitere, interne Datenstruktur die sachen mit dem hash eines indizierten Attribut ausseinanderhält
Der Index besteht bzw, addressiert $q$ Eimer
Jeder der Eimer hat elemente $(K_{j}, P_{i})$ also das Indexierte Attribut $K_{j}$ und den Record-Identifier $P_{i}$
Wenn wir jetzt eine Reihe finden wollen, machen wir das indem wir den Hash von $K_{j}$ generieren
- Damit können wir dann den richtigen Eimer ausfindig machen
- und in diesem Eimer können wir dann "manuell" nach $K_{j}$ suchen
- yay

$B$ -Bäume

Wir kennen sie alle
Wir mögen sie warscheinlich (nicht)
Jede Node kann mehrere Einträge haben
Jede Node kann ausserdem mehrere Kinder haben (auch mehr als zwei, daher auch nicht binär)
Innerhalb der Node sind die Einträge Sortiert
Der Baum ist Balanciert, also haben alle Wege die selbe Länge
Der Baum hat den Parameter $m$ der die Minimale Anzahl von Einträgen pro Node bestimmt
Wie genau das Funktioniert, kannst du sehen wenn das Licht angeht

$B^{+}$ -Bäume

Wenn wir uns unsere bisherigen Strukturen anschauen können wir uns dann auch noch fragen, wie wir die Sache mit den Bäumchen noch verbessern können
Das machen wir indem wir alle Keys in die blätter quetschen
Und die blätter dann miteinander verbinden
Wenn wir das so machen, können wir den oberen Teil des Baums zum suchen verwenden und die Blätter des baumes zeigen direkt auf die zugehörigen Werte

Wasn jetzt der Unterschied?

Hauptsächlich differenzieren sich die beiden Herangehensweisen in der Internen Struktur der beiden Bäumchen
Der "normale" B-Baum hat schlüssel auch innerhalb des baumes, das hat der B⁺ Baum nicht, dafür hat dieser dann "pointer-schlüssel" die auf die "richtigen" schlüssel zeigen
Durch diese Referenzschlüssel können wir dann "einfacher" durch den Baum suchen.
- Diese Referenzschlüssel können Kopien des "richtigen" schlüssel sein, müssen das aber nicht, das entscheidet sich je nach DBMS und je nach Datentyp
Diese Referenzschlüssel müssen allerdings auch immer geupdated werden, wenn die "richtigen" schlüssel verändert werden
- z.b. wenn etwas hinzugefügt oder auch entfernt wird
Wenn wir uns die Komplexität anschauen unterscheiden sich die beiden Bäumchen kaum, allerdings sind B⁺ Bäume in der Praxis schon effizienter, wenn eine größere Datenmenge vorliegt, dafür verbrauchen sie allerdings auch mehr speicher
Je nach index level können B⁺ Bäume auch mehr indizes beinhalten

Aber warum Bäume?

Wenn wir unsere Daten mit der Hilfe von Bäumen speichern bzw. indexieren können wir sicher gehen, dass der kram Sortiert bleibt und wir so sequentiell durch unsere Daten iterieren können
- Das ist, wie wir ja oben schon gesehen haben, besonders schnell
Wir können ausserdem eine Liste von Hierachischen Keys im RAM behalten, damit wir möglichst wenig auf unseren Sekundären Speicher zurückgreifen müssen
- Das spart energie, Zeit und auch Festplattenleben, denn letztendlich ist jeder Zugriff "schädlich" für das Leben unsere Festplatte
Wir können darüber hinaus auch teilweise vollständige Blöcke nutzen um das Inserten und Löschen von Daten zu beschläunigen
Ebenso können wir durch den baum den Index balanziert behalten, damit wir möglichst wenig durch die gegend uschen müssen

Ja aber was hat das jetzt alles mit uns zu tun?

Physische Datenmodellierung in DBMS

Wir können in unserem DBMS auch Indizes erstellen
das machen wir mit dieser Query:
CREATE [UNIQUE] INDEX name ON table (column [ASC | DESC], [...]);
Hier ist zu beachten, dass jedes DBMS das anders handled und auch anderen Syntax dafür hat
Manche DBMS bieten auch "B-Tree-Indexes" an, allerdings ähneln diese von der Implementation oft eher B⁺ Bäumen
Clustered Indizes werden auf dem Table-Level deklariert, indem spezifiziert wird, welcher index wie geclustered werden soll. Mehr dazu hier

Wann wollen wir denn Indizes?

Bei welchen queries bringt das denn was?

DQL und DML queries können von Indizes profitieren
- Das allerdings nur, wenn die Selektions- oder Joinkriterien Indezierte Attribute sind
Ebenso können sachen die Unique sein müssen davon profitieren
- Wenn die Spalten die extra gechecked werden müssen auch indiziert sind
- Und man "einfach" schauen kann, ob nen index schon exestiert

Welche Attribute sollen wir Indizieren?

Am besten die sachen die oft abgerufen werden und oder in Transaktionen verwendet werden
Ebenfalls sachen die Zeitkritisch sind bzw. besonders schnell ausgeführt werden müssen

Wann sind Indizes eher ne doofe idee

Daten die oft modifiziert bzw. Angepasst / gelöscht / hinzugefügt werden sind eher unpassend fürs indizieren
- Da wir jedes mal neue Indexe generieren und einfügen müssen
- Und das updaten bzw. umherschieben von Indizes ist aufwändig
Ebenso sollten wir attribute die wir nie zum auswählen nutzen nicht indexieren, da uns das da keinen vorteil bringt und nur speicher und rechenleistung schluckt

Design-Decisions mit Indizes

Slotted Pages

Example: B-Bäume

Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides Slides

Query Optimization and Execution

Wir wollen uns jetzt mal anschauen wie wir Queries "vereinfachen" bzw. optimerein können, damit wir dann gut mit denen arbeiten können und die dann idealerweise sehr schnell ausgeführt werden können
Wir schauen uns dazu unsere relationelle algebra an
Damit können wir ja alles was wir ausführen wollen darstellen

Query processing

Die Queries werden in mehreren schritten evaluiert

Wir scannen, parsen und validieren die queries
- Wir schauen ob das valides SQL ist
- Wir überprüfen ob alles was dadrin abgefragt wird auch überhaupt da ist
- Was bedeutet dat eig?
Wir optimieren die query
- Wir schauen in welcher reihenfolge die queries optimal ausgeführt werden können
- Queries werden in "plans" gespeichert, das ist nen baum, der vorgibt wie was wann wo abgefragt werden soll
- Wenns irgendwie passt, fassen wir bäume zusammen
Query executor
- führt die query am ende dann auch wirklich aus
- führt die ganzen internen dinge aus, die passieren müssen damit der kram "wirklich passiert"

Relational Selection Operator

Wenn wir eine Relation $R$ betrachten, können wir eine selektion wie folgt definieren:
- $σ_{a = v} (R) := {r ∣ r \in R, r . A = v}$
Eine condition zur selektion kann auch aus mehreren conditions bestehen
Es gibt mehrere unerschiedliche algorithmen, die sich aber meisstens nur in der strategie für das finden con tupeln unterscheiden

Selections

Es gibt einige verschiedene Möglichkeiten zu selecten
Selection with Scan
- Wir scannen durch jede page vom speicher und seammeln uns so alles zusammen was wir brauchen
Selection with Index
- Wir gehen mal davon aus, dass es nen index gibt, der vom 1. bis zum n. element konstant bleibt
- Durch den iterieren wir, anstelle die ganze relation zu durchsuchen
- Das kann aber relativ teuer werden, naja teuer ist wie immer relativ
- je nachdem wie viele indizes es gibt, dauerts halt länger, nich?

The Projection Operator

yeahhh todo asdlasldlasdladslasld

Transactions, Serializbility and the ACID Principle

Heute wollen wir über tolle Transaktionen reden
mit ransaktionen können wir so tun als wären wir in einem tollen testenvironment und wir können gar nicht caren
wenn wir in der transaction was kaputt machen, dann ist das am ende nicht mehr kaputt (toll oder)
- Das bedeutet, das transactions einfach alles simulieren, bevor der kram wirklich ausgeführt wird
Dabei entsteht nen Problem, dass wir nämlich sehr viele lustige dinge tun können, wenn irgendwann mal

[ Angewandte Informatik ]