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)=\text{max}\{time(I)|size(I)=n\}$
  • Alternativ:
    • Analyse im besten Fall:
      $T(n)=\text{min}\{time(I)|size(I)=n\}$
    • Analyse im mittleren Fall:
      $T(n)=\frac{1}{|\{I|size(I)=n\}|}\sum _{\{I|size(I)=n\}}time(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:
• 

Korrektheit von Algorithmen

• Wenn wir die korrektheit überprüfen wollen, also zeigen wollen, dass etwas das tut was es behauptet zu tun, machen wir das oft mit der sog. Schleifeninvariante
• So heissen Eigenschaften, die vor jedem Durchlauf einer Schleife bzw. einer Wiederholgen Eingabe gelten
• Davon gibt es auch noch nen paar andere Begriffe, deswegen wollen wir hier einmal über alle davon reden:

Ein Konkretes Beispiel dafür ist:

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=lenght$

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 $\ge$
  • 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(nlogn)$
• 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 $nlogn-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(nlogn)$

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 $key(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=\Theta (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
• 

Analyse

-

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

$InformatikII$ Ü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
  • $if(h(f)\le i<j\vee j<k\le h(f))$

Aufgabe 1: Hashing mit Verkettung

a)

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

1. $e_1=(2,3)$
2. $e_2=(1,2)$
3. $e_3=(3,0)$
4. $e_4=(2,1)$
5. $e_5=(0,2)$
6. $e_6=(3,3)$
7. $e_7=(4,4)$

Mit Hashfunktion: $h_a((x_1,x_2))=\left(\begin{array}{cc}2& x_1\\ 7& x_2\end{array}\right)mod11$

1. Iteration:

$h_a((2,3))=3$

2. Iteration:

$h_a((1,2))=5$

3. Iteration:

$h_a((3,0))=6$

4. Iteration:

$h_a((2,1))=0$

5. Iteration:

$h_a((0,2))=3$

6. Iteration:

$h_a((3,3))=5$

7. Iteration:

$h_a((4,4))=3$

Tabelle:

b)

$h_0(x)=(x+5)mod3=(x+2)mod3$
$h_0(x)=(x+7)mod3=(x+1)mod3$
$h_0(x)=(x+9)mod3=xmod3$

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\ne y\in \mathbb{N}:|\{h\in H|h(x)=h(y)\}|\le \frac{c\cdot |H|}{m}$

=> $H$ ist nicht $1$-universell für $Key=\mathbb{N}$

Aufgabe 2: Hashing mit linearem Sondieren

Mit Hashfunktion: $h(x)=xmod11$

a)

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

$Insert(14)$

$Insert(42)$

$Insert(19)$

$Insert(3)$

$Insert(17)$

$Insert(20)$

$Insert(6)$

$Insert(31)$

$Insert(25)$

$Insert(28)$

Insgesamt: (Lösung)

• (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:

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:

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

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:

• 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:

1. DFS besucht 1, 5, 2 und identifiziert {1, 5, 2} als Komponente. 1 wird als repräsentant ausgewählt
2. 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)

a)

Djikstras Algo lolsies

b)

• 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
  • $\text{Zusammenhangskomponente }=\{1,3\},\{2\},\{4\},\{5\},\{6\},\{7\},\{8\}$
  • $T=\{(1,3)\}$
• Einfügen $(2,5)$
  • $\text{Zusammenhangskomponente }=\{1,3\},\{2,5\},\{4\},\{6\},\{7\},\{8\}$
  • $T=\{(1,3),(2,5)\}$
• Einfügen $(7,8)$
  • $\text{Zusammenhangskomponente }=\{1,3\},\{2,5\},\{4\},\{6\},\{7,8\}$
  • $T=\{(1,3),(2,5),(7,8)\}$
• Einfügen $(1,4)$
  • $\text{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)$
  • $\text{Zusammenhangskomponente }=\{1,3,4,7,8\},\{2,5\},\{6\},$
  • $T=\{(1,3),(2,5),(7,8),(1,4),(4,7)\}$
• Einfügen $(5,8)$
  • $\text{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)$
  • $\text{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

a)

• 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}_{kosten}+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:

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

b)

• max Kantengewicht $O(|V|+|E|)$ (Adj, listen)
• Absteigend bei Kante aus $\hat{E}:O(|V|+|E|)\to$ Graph mit $|V|Knoten$
• Janik-Prim $O(|V|log|V|+|E|+|V|-1)\le |E|+|V|-1$ Kanten
• $O(|V|log|V|+|E|)$
• Entfernen den Kanten aus $\hat{E}/E:O(|V|+|E|)$

Übung 12

Aufgabe 1: Suchbäume

a)

• 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 {\mathbb{N}}_i\forall 1\le n\le n$ gekte, dass ein binärer Suchbaum mit $n^{\prime }$ Blättern genau $n^{\prime }-1$ innere Knoten hat.
• Induktionsschritt: $n\to n+1$. Sei $T$ binärer Suchbaum mit $n+1$ Blättern $n+1\ge 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\le n,n_2\le n$ Blättern auffassen
• $1\le n_1\le n=>T_1$ hat $n_1-1$ innere Knoten
• $1\le n_2\le 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$
• $$\begin{gathered} =n_1+n_2-1 \\ =(n+1)-1=n \end{gathered}$$

Vollständig

1. Fehlt
2. Dine
3. ?
4. ?
5. ?
6. Fehlt
7. Done
8. Fehlt
9. ?
10. Fehlt
11. Fehlt
12. Done
13. Unvollständig

Informatik 3

Äquivalenzreaktionen

• Reflexiv: für alle $A$ gilt $(x,x)\in R$
• Transitiv: für alle $A$ gilt $(x,y)\in R,(y,z)\in R⟹(x,z)\in R$
• Symmetrisch: für alle $A$ gilt $(x,y)\in R⟹(y,x)\in R$

Nerode Relation

• Hier können wir das akzeptierveralten bestimmen bzw. formal ausdrücken
• Das machen wir wenn wir einzelnd sachen definieren, und diese modifizieren. Wenn dabei nicht dasselbe rauskommt, sind die dinger die wir uns anschauen nicht equivaelent
• ein DFA ist minimal, wenn alle Strings die äquivalent sind zu demselben Zustand führen
• Wenn die nerode Relation einer sprache $L$ endlichen index hat, dann kann ein DFA für $L$ konstruiert werden
  • Dieser DFA verwendet dann die vorher definierten Äquivalenzklassen
  • Deswegen nennen wir das ding dann auch äquivalenzklassenautomaten

Äquivalenzklassenautomaten?

• Die dinger nutzen wir um herauszufinden, ob zwei dinge Äquivalent sind
• Folie 12
• Wie gesagt, wir dein wort genau dann vom Automaten akzeptiert, wenn wir das wort mit einem wohl definierten "modifikator" modifiziert wird und das erwartete Ergebnis dabei dann heraus kommt

Untere Schranke für die größe von DFAs

• Kein DFA für eine reguläre Sprache ist kleiner als ihr Äquivalenzklassenautomat
• Wir könen aber auch Verfeinerungen betrachten
  • Die haben dann mindestens so viele Äquivalenzklassen wie die Relation die sie verfeinert
  • Genau so trifft natürlich auch mindestens alles aus der zu verfeinernen Relation zu

Satz von Myhill und Nerode

• Eine Sprache $L$ ist genau dann regulär, wenn $r_L$ endlich viele äquivalenzklassen hat
  • Hieraus können wir die Methode zum Nachweis basteln, und ebenfalls eine Methode um nachzuweisen, dass das am ende nicht regulär ist

Minimaler Automat

VL 05

Pumping Lemma

• Wir schauen, ob wir unseren kram Zerlegen können (also den automaten)
• Wir schauen genauer gesagt, ob wir eine schleife haben, die wir zum "aufpumpen" nutzen können, indem wir sie dauerhauft durchlaufen
• Auch wenn wir das $n$ mal durchlaufen, sollte die Schleife nichts an der Akzeptanz ändern
• Das funktioniert übrigens auch, bei begrenzten Sprachen
• Wir wollen aber mit dem pumping Lemma herausfinden, wenn irgendetwas nicht regulär ist
  • Das finden wir heraus, wenn wir einfach den "dann" teil des Pumping-Lemmas invertieren, sprich einfach umdrehen
  • Dann ist das natürlich aber dann auch nicht regulär

Beispiel

• Wir haben eine Sprache mit beliebig vielen as und ms, aber gleich viele
• Wir müssen für jedes $n$ Zeigen, dass es für das n die geforderten eigenschaften braucht
  • alias mindestens muss der String die Länge $n$ haben
  • Wenn wir einen String mit $n$ wählne, hat der string die mindestlänge von $2n$ was ja unserer forderung gerecht wird
• Wichtig ist, dass die Variablen wir wählen, auch immernoch die "regeln" beziehungsweise die "Vorgaben" der Sprache respektiert
• In unserem Beispiel reden wir von dem $n$
  • Wichtig ist da, dass wir das nicht wählen können, sondern dass uns das von "aussen" angegeben wird
  • Geanu so gilt das für die Zerlegung

Spieler?

• Wir können uns das so vorstellen, dass wir wie zwei Spieler gegeneinander Spielen
• Wir versuchen auf der einen Seite alles zusammenzuhalten, und gleichzeitig versucht unser gegenspieler, dass alles wieder kaputt zu machen >:(

Aber wie hat das was mit regulären Ausdrücken zu tun?

• Wir können viele dinge einfach über DFAs usw. definieren
• Wir schauen uns eine tolle Kaffemaschine an
  • Die funktioniert nur, wenn wir eine Münze (oder so) eingeworfen haben
  • Das können wir auch regulär ausdrücken
    • Erst muss das zeichen für Münze kommen, und dann den rest
• Wie können wir den überprüfen, ob ein Automat die eigenschaften unserer Sprache erfüllt?
  • Wir müssen sicher gehen, dass alle wörter die der Automat akzeptiert, auch in unserer Sprache liegen
• Wenn wir uns das so anschauen, wäre es schon sehr cool eine "Toolbox" zu haben, aus der wir "Bausteine" kopieren könnten
  • Achja und testen bestimmt jaja

Synthese endlicher Automaten

• Wie machen wir jetzt aus einem Regex einen Automaten?
• Wir wollen das, damit wir das "einfacher" berechnen können
• Interessant ist für uns folgendes:
  • Wir denken uns erstmal unseren Boolsche dinge
  • Damit wir das vernünftig verarbeiten können, muss man
    • den durchschnitt zwischen zwei als regulär einstufen können
    • und ein Komplementär ebenfalls
  • Ausserdem sollten die operationen mögloichst effizient ausgeführt werden

Weitere Algorithmen

• Wir können diese tollen automaten ja auch umziehen
• 

Leerheitstest

• Wir wollen erstmal schauen, ob nen Automat leer ist, denn wenn ein Automat leer ist (keine transaktionen hat) können wir logischerweise auch nichts sinnvolles damit machen
• 
• 

Beispiel für Äquivalenzerfassung

• Wir betrachten zwei automaten
• Wir wollen wissen, ob die beiden Equivalent sind
• Wir bauen erstmal einen tollen Produktautomaten, für jeden DFA den wir inspizieren wollen
• Dann entfernen wir alle Zustände die nicht erreichbar sind
• Wenn die beiden Sprachen äquivalent sind, dann sind die beiden Automaten auch äquivalent

Algorithmen Äquivalentstest für NFAs und REs

• Wir wandeln

A6: Anwendung und Erweiterungen

Kapitel B4: Eigenschaften Kontextfreier Sprachen

Einleitung

• Wasn kontextfrei und was nicht?
• Wir können das auch wieder mit einem Pumping-Lemma beweisen
  • Fast so wie beim Regex
• Leider gibt es kein eqiv zum satz von nerode
• Einige algorithmische Problems für kontextfeie Sprachen lassen sich schon effizient lösen

Pumping-Lemma für Kontextfreie Sprachen

• Wir wollen sowas für Kontextfreie Sprachen finden
  • Das kontextfreie pumpinglemma wird genau so wie das "normale" sein, von der Sturktur her
• beim Kontextfreien wird die grundidee sein:
  • Wenn wir einen langen ableitungsbaum haben
  • wird es einen langen pfad geben, auf dem sich variablen wiederholen
  • und was auch immer dazwischen ist, das pumpen wir dann auf
  • oder wir lassen das halt komplett weg
  • aber egal was wir tun, am ende isat das Wort immernoch in der Sprache

B5: Wortproblem und Syntaxanalyse

• Wir sind auf der Suche danach, ob wir ein Wort oder eine Sprache beweisen / nutzen können
• Wir haben uns mit $L_1$ Grammatik angeschaut, wie wir das mit Linksableitungen modellieren können

$LL(1)$-Grammatiken

• zuerst brauchen wir $FIRST(\alpha )$
  • Das ding beinhaltet, alle ersten Terminalzeichen von Strings, die aus $\alpha$ abgeleitet werden können
• $FOLLOW(X)$
  • Das beinhaltet alle Terminalzeichen, die in der Sprache DIREKT nach $X$ kommen
• Wir wollen zeigen, dass man die Mengen effizient berechnen kann
  • Denn wir wollen schauen, wie wir das idealerweise gut parsen können
• Die grammatiken haben feste Regeln, die wir beachten müssen
  • $FIRST(\alpha )\cap FIRST(\beta )\ne \varnothing$
  • IF $a⟹\ast ϵ$ then $FOLLOW(X)\cap FIRST(\beta )=\varnothing$

Parsing

• Wenn wir parsen wollen, bauen wir uns erstmal eine Tabelle, die uns sagt, wann wir wie welche Regel brauchen
  • Diese Tabelle brauen wir aus der Grammatik zusammen
  • Die bestimmen wir genauer gesagt aus den $FIRST$ und $FOLLOW$-Mengen
• Wenn wir dann also mal was Parsen müssen, schauen wir uns immer erst die Tabelle an
  • Die gibt uns dann, relativ Stupide vor, wie wir den kram ableiten müssen.
  • Sprich, die sagt uns wie wir (schritt für schritt) zu einem $c$ kommen, beispielsweise

Bottom-Up Syntaxanalyse (Ausflug)

Statistik

Kombinatorische Grundformeln

Mächtigkeit berechnen

• Das machen wir (wie man denkt) mit den Urnenmodellen
• Wir müssen etablieren,
  • wie oft wir ziehen
  • ob wir wieder zurücklegen
  • ob uns die Reihenfolge interessiert

Beispieldurchlauf

• Wir ziehen mit zurücklegen und der beachtung der reihenfolge
• Wir haben $n=18$ Kugeln
• Die, die wir gezogen haben, schreiben wir auf mit $\omega =\{14,6,15\}$
• Wir haben insgesamt $k=3$ kugeln gezogen
• Wir könnten jetzt aber auch "einfach" münzen oder würfel geworfen haben
  • Dynamisch können wir halt dasselbe verfahren auf alles mappen, was wir brauchen

Aufgabe 1

• Wir können das ganze dann einfach ausdrücken mit $\frac{\text{\# "akzeptierter" Mo¨glichkeiten}}{\text{\# Mo¨glichkeiten}}$ modellieren
• We found out: fakultäten steigen fakultätsweise

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 \phi )$ (Negation)
  • $({\phi }_1\wedge {\phi }_2)$ (Konjunktion)
  • $({\phi }_1\vee {\phi }_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

1. Wir modellieren unser Programm in einem Transitionssystem, damit wir den fluss von Daten / Informationen schön und sinnvoll darstellen können
2. 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
3. Dann testen wir, ob das Transitionssystem auch unseren Formeln "Standhält"
4. Wenn das nicht der fall sein sollte, konstruieren wir ein Gegenbeispiel

• betrachten können wir das ganze durch typische Logiken
  • $LTL$ Linear temporal logic
  • $CTL$ 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?
• 2. "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 $\phi$ oder $\psi$ haben können wir auch
  • $\neg \phi ,\phi \wedge \psi$ und $\phi \vee \psi$
  • $EX\phi ,EF\phi ,EG\phi$ und $E(\phi U\psi )$
  • $AX\phi ,AF\phi ,AG\phi$ und $A(\phi U\psi )$ 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
• $\square \varphi$ Bedeutet, dass eine Aussage in allen erreichbaren Welten gilt
• $◊\varphi$ Bedeutet, dass es eine erreichbare Welt gibt, in der $\varphi$ gilt
• $\neg \square A\equiv ◊\neg A$

Beispiele

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

Aufgaben

Aufgabe 1)

a)

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

b)

1. $H\to \square S$
2. $U\leftrightarrow (S\vee ◊S\vee ◊◊\vee ◊◊◊S)$
3. $\square (\neg U\wedge \neg S)\to \neg ◊H$

Aufgabe 2)

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 $\varphi$ 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.
  • ${\varphi }_1=AG(\neg c_1\vee \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)
  • $AG({\omega }_1\to AF{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,EU$
  • $AX,AF,AG,AU$
• 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\varphi$: In der nächsten Welt gilt $\varphi$
  • $F\varphi$: In einer zukünftigen Welt gilt $\varphi$
  • $G\varphi$: In allen zukünftigen Welten gilt $\varphi$
  • $\delta U\varphi$: $\delta$ gilt bis $\varphi$ gilt
• Insgesamt ist CTL eine Verallgemeinerung der Modallogik
  • $EX$ entspricht $◊$
  • $AX$ entspricht $\square$
• 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

• 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\vee \neg A)\vee (B\wedge \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?

Sind diese Folgen Equivalent?

• $AFa\vee AFb$
• $AF(a\vee b)$

Modallogik und CTL

a) 1.

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

• CTL
  • $AG(f\to AG\neg a)$
• ML
  • Wir können das ggf. einfach nicht auswerten, weil wir theoretisch eine unbeschränkte menge von $\square$-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 \psi )$ anstelle von $\forall x\in R:\psi$ schreiben
• Ebenso kann man $\exists x\in R:\psi$ durch $\exists x(R(x)\wedge \psi )$ 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\models \phi \iff I\models \psi$
  • Das schreiben wir "einfacher" so: $\phi \equiv \psi$
• 
• 

Nachweise von Äquivalenzen

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

• Sei ${\phi }_1$ eine prädikaten-logische Formel mit einer Teilformel ${\psi }_1$
• Sei ${\psi }_2$ eine weitere Formel mit ${\psi }_2\equiv ps{i}_1$
• Wenn ${\phi }_2$ aus ${\phi }_1$ entsteht, indem ein Vorkommen von ${\psi }_1$ durch ${\psi }_2$ ersetzt wird,
  dann gilt ${\phi }_2\equiv {\phi }_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 ,\vee ,\neg$ verwendet, aber bene nicht $\forall$ und $\wedge$
  • $\phi$ ist in Negationsnormalform (NNF), wenn Negationen in $\phi$ nur unmittelbar vor atomaren Formeln vorkommen
  • $\phi$ ist in prännexform wenn sie so aussieht: $Q_1{x}_1{Q}_2{x}_2...Q_k{x}_k{\phi }^{\prime }$
    • Dabei ist $Q_i$ entweder $\exists$ oder $\forall$
    • $x_i$ muss paarweise verschieden sein
    • ${\phi }^{\prime }$ 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 $\phi$ heisst Modell von $\phi$, wenn $I\models \phi$ gilt.
  • Wenn $\phi$ ein Model hat, ist $\phi$ erfüllbar, sonst nicht
  • Wenn jede passende Interpretation von $\phi$ ein Modell von $\phi$ ist, ist $\phi$ allgemeingültig
    • Eine andere Bezeichnung für das ist die Tautologie
  • $I$ ist ein Nodell einer Menge prädikatenlogischer Formeln $\varphi$, falls $I\models \phi$ für alle $\phi \in \varphi$ gilt.
• Die Begriffe "erfüllbar" und "allgemeingültig" haben für Mengen von Formeln $\varphi$ die gleiche bedeutung
• Beispiele:
  • $\exists x\forall y(R(x)\vee \neg R(y))$ ist allgemeingültig
  • $\forall x\exists y(\neg R(x)\wedge R(y))$ ist unerfüllbar
• Anmerkungen:
  • Der Zusammenhang zwischen unerfüllbaren und allgemeingültigen Formeln ist genauso wie in der Aussagenlogik:
    $\phi$ unerfüllbar $\iff$ $\neg \phi$ allgemeingültig
  • Ist $\phi$ einge geschlossene Formel mit Modell $I=(\mathrm{A},\beta )$, so nennen wir auch $\mathrm{A}$ ein Modell von $\phi$ und schreiben $\mathrm{A}\models \phi$
• Fun-Fact: Der Unterschied zwischen $\phi$ und $\varphi$ 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 $\phi$ testen wollen, können wir auch "einfach" eine "simplere" Formel $\psi$ 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:
    • $\phi$ und $\psi$ 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\psi$, wobei $\psi$ 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 $\phi =\forall x_1\forall x_2...\forall x_k\exists y\psi$ und kommt das Funktionssymbol $f$ in $\psi$ nicht vor, so ist die Formel $\forall x_1\forall x_2...\forall x_k\psi [y/f(x_1,...,x_k)]$ erfüllbarkeitsäquivalent zu $\phi$
• Bemerkungen dazu:
  • $\psi$ 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)

a)

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

b)

Grundmenge: $\{N1,N2,N1000,...,N1003,S1,...,S100,K1,K2,K3\}$

$N=\{N1,N2,N1000,...,N1003\}$ Nutzer
$P=\{N1,N2\}$
$S=\{S1,...,S100\}$
$R=\{(N1,S16),(N2,S17)\}$
$k(x)=\{\begin{array}{ll}K1,S1\le x\le 20& x\in \{S1,...,S20\}\\ K2,S21\le x\le 70& x\in \{S21,...,S70\}\\ K3,S71\le x\le S100& x\in \{S71,...,S100\}\\ 0\text{ sonst}& \\ x\text{ sonst}& \end{array}$
$b=N1$
$S=N2$

• 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

b)

• $D$
• $(i)\wedge (ii)\wedge ...\wedge (\vee )\wedge \neg D{\to }^{KNF}\{\{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.

• Aufbau
• Moore's Law
• Dennard Scaling
• Multicore und Amdahl's Law
• In Anderen Aspekten der Prozessortechnik
• Höhere Sicht eines Rechners.
• Modellierung eines RISC-Rechners
• Modellierung eines CISC-Rechners
• Virtueller Rechner
  • Hirachie: Illustriert
• Übersetzung versus Interpretation
  • Übersetzung
  • Interpretation
  • Abwägung
• Performanzmaße eines Rechners
• Kernbegriffe:
• Hardware VS Software
  • Der Kram zwischen Software und Hardware
• Exkurs: Hardware / Software Co-Design
• Prinzipieller Aufbau eines Rechners
• John von Neumann (1903-1957)
• Der Arbeitsspeicher (Hauptspeicher)
• Der Prozessor (+ Cache)
• Register des Prozessors
• Prinzipielle Arbeitsweise eines Prozessors
• Ebenensicht : The SQL
• Assembler $\leftrightarrow$ Höhere Programmiersprachen
• Befehlssatz
• Klassen von Befehlen
• Wofür steht RISC-V?
• Wat is das überhaupt
• Die verschiedenen Register
• Arithmetische Befehle
  • Rechenbefehle
  • Vergleichsbefehle
  • Schiebebefehle
  • Ladebefehle
  • Speicherbefehle (Memory)
  • Logische Befehle
  • Sprungbefehle
  • Systembefehle
• Beispiele für Systembefehle
  • Rechenbefehle
  • Logische Befehle
  • Sprungbefehle
  • Datentransportbefehle
• Datentransportbefehle
• Adressierungsarten
• Unterprogramme
  • Beispielprogramm: $n!$
• Instruktionskodierung
  • Instruktionsformat R-Typ
  • Instruktionsformat I-Typ
  • Instruktionsformat S/B-Typ
  • Instruktionsformat U/J-Typ
• Assembler $\leftrightarrow$ Maschinenschprache
• Verarbeitung einer Instruktion (RISC-V)
• Aufbau eines RISC-V Prozessors
• CISC - Complex Instruction Set Computer
  • Was spricht für CISC?
  • Was spricht dagegen?
  • Eine Statistik für CISC-Rechner (ca.1990)
• RISC - Reduced Instruction Set Computer
• RISC VS CISC
• Designprinzipien für Rechner
• Wat dat überhaupt?
• Speedup
• Hazards
  • Bedingte Verzweigung: Control Hazards
  • Mögliche Lösung: Branch Prediction
  • Zusammenfassend
• Out of Order Execution
• Datenabhängigkeiten
• Out-Of-Order-Execution
• Modifikation Registerbank
  • Struktur dieser "Warteräume"
  • Verteilung der Ergebnisse
• SRAM
• DRAM
• Aufbau von Zellfeldern
• Funktionsweise des RAM
• Gründe für Komlexe Speicheroganisation
• Lokalitätsprinzip
• Speicherorganisation Heute
• Big Endian vs Little Endian
• Caches
  • Lage des Caches
  • Ziel des Cache Einsatzes
  • Wie sieht das in der Praxis aus?
• Mittlere Zugriffszeit beim Lesen
• Aufbau eines Caches
• Cache als assoziativer Speicher
• Was passiert mit Alten daten?
• Direct Mapped Cache
• Prinzipielle Funktionsweise: Schreibzugriff
  • Writeback VS writeallocation
• Festplatte (Hard Disk Drive)
  • Adressierung
  • Partitionierung
  • Ausführung eines Festplattenzugriffs
• Alternative: Solid State Disk (SSD)
• Das problem mit dem Hauptspeicher
  • Daher: Festplatte als virtuellen Arbeitsspeicher verwenden
  • Ja aber was machen wir jetzt mit dem Adressraum?
• Segmentierung
  • Paging
  • Paging: Zugriff auf Datenseite $i$
• Übersetzung von virtuellem Speicher auf physikalischen Speicher
• Meltdown
• Spectre V1
• Spectre V2
• Formen der Parallelität
• Amdahl's Law
• Formen der Parallelverarbeitung auf prozessor-/ Rechnerebene(1)
  • Arrayprozessoren
  • Multiprozessoren:
  • Multi-Core Prozessoren
  • Koprozessoren
  • Multicomputer
• Beispiele für parallele Rechnerarchitekturen:
  • Cache Koeärenz
• Verbindungsstrukturen
• Modellierung von Verbindungen
  • Stern
  • Ring
  • CDDI / FDDI-Ring
  • MESH ("torusähnliches Gitter")
  • HYPERCUBE ($d$-Dimensionaler Würfel)
  • Cube Connected Cycle (CCC)
• Beispiele für parallele Rechnerarchitekturen
  • Beispiel AMD Phenom II X4 (2009)
  • Beispiel: Cell Chip
• Grafikprozessor
• Aber wie funktioniert das eigentlich?
• Die Schritte in der Grafikpipeline:
  • AMD Radeon RX 580
• Klassifikationsmerkmale bei Parallelen Rechnerarchitekturen
  • Speichermodell:
  • Homogenität der Prozessoren
  • Hirachie zwischen den Prozessoren
  • Eigenständigkeit der Prozesoren:
• Klassifikation nach Flynn [1966]
• Motivation?
• ASCII
• Unicode
• Definition: Code
• Probleme bei Binär-encoding:
  • Was kann alles Passieren?
• Fehlererkennender Code
• Beweis Lemma [Fehlerkorrektur]
  • Idee
• 1-Fehlerkorrigierender Code
• Hamming code
  • Idee:
  • Hamming Code an einem Beispiel
  • Hamming Code Berechnen
• Memory - I/O Busse
• Heutige Bussysteme
• Morgige?
• Selbstaktende Codierung
• Prinzipieller ablauf einer Kommunkation
• Direct memory Access
• Optionen eines Busses

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

Ü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:

$$\begin{gathered} varcmd:=\text{erste Instruktion des }{L}_i\text{ Programms}; \\ while(L_i\text{-Programm}hat\text{Instruktionen})\{ \\ cm{d}_2=convert(cmd); \\ execute(cm{d}_2); \\ cmd=\text{na¨chste Instruktion aus dem }{L}_i\text{ Programm}; \\ \} \end{gathered}$$

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

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

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 $\text{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 $[\mathrm{0..}n-1]$
  • Nix kann kleiner sein als Wortbreite, also ist eine speicherzelle die kleinste adressierbare einheit des speichers