Und wenn wir diese Frage stellen, können wir natürlich auch gleich fragen, also wie lange

meint im Wesentlichen wie teuer? Also mit diesem lange hier meine ich im Wesentlichen eine gewisse

Kostenfunktion, also wie teuer wird die Berechnung und dieses teuer kann sich im Wesentlichen einmal

darauf beziehen, dass wir an der Laufzeit interessiert sind, aber auch am Speicher.

Wie gesagt, wenn wir bei kleinen Eingabemengen über kleine Eingabemengen reden, dann ist das

ganze nicht so spannend, aber wenn Sie beispielsweise mal Ihren eigenen ChatCTP-Algorithmus

implementieren wollen, dann werden Sie sich schon fragen, okay wie viel Speicher habe ich überhaupt

und wie lange kann ich es mir erlauben zu rechnen, bis ich zu einem zu einer Antwort kommen muss.

Es gibt auch noch andere Verfahren, wie gesagt hier betrachten wir immer ein Algorithmus A,

der eine Eingabe X bekommt und eine Ausgabe Y berechnet. Es gibt auch noch sogenannte

interaktive Algorithmen und wie der Name schon sagt, wie der Name schon sagt, sind das Algorithmen,

die miteinander interagieren, also zum Beispiel nehmen wir mal an, gut dass wir noch ein paar

Plätze frei haben, also nehmen wir mal an wir haben wir haben zwei Algorithmen A und B und die haben

eine Eingabe X und Y. Interaktive Algorithmen brauchen sich in gewisser Weise gegenseitig, um

ein Problem zu berechnen. Also ein ganz bekanntes Beispiel, wie gesagt ich möchte Sie ja während

Ihres Studiums insgeheim für die Kryptographie begeistern, das mache ich total unterschwellig,

deswegen kommt jetzt ein Beispiel aus unserem Bereich, nehmen wir mal an Alice und Bob, die

nehmen wir irgendwie immer, Alice und Bob möchten gerne herauskriegen, wer von ihnen eigentlich mehr

Geld hat. Es gäbe eine total einfache Variante, sie schicken einfach ihre Kontostände hin und her,

X und Y und sie wollen im Wesentlichen die Funktion von X und Y berechnen, die sagen wir mal A ausgibt,

falls X größer Y, von mir aus auch größer gleich und B ausgibt, falls Y größer X. So die einfache

Variante wäre, die tauschen einfach ihre Kontostände aus und dann hätten wir das Problem gelöst,

es findet also eine Interaktion statt, aber weil wir Kryptographen natürlich immer so ein bisschen

vorsichtig sind, wollen wir natürlich nicht unseren Kontostand offenlegen, das heißt was

sie stattdessen machen ist, also das hier mögen wir nicht, geht hier nämlich gar nichts an, ich möchte

nur mein Ergebnis wissen, was wir stattdessen machen ist, wir führen ein Protokoll aus, das nennen

wir einfach mal Pi und dieses Protokoll macht sagen wir einfach mal ein bisschen Kryptomagie und es

kann am Ende im Wesentlichen garantieren, dass die Teilnehmer entweder A oder B lernen und nichts

über die konkrete Eingabe. Also wie man sowas macht, gerne zur Vorlesung Krypto beziehungsweise MPC,

aber im Wesentlichen finden Interaktionen statt, also dieses Protokoll spezifiziert, was jeder

Teilnehmer machen muss und am Ende erfahren sie dieses Ergebnis und hier sind wir nicht nur daran

interessiert, wie viel muss ich rechnen, wie viel muss ich speichern, sondern wir sind auch noch

daran interessiert, wie viel muss ich eigentlich reden, also sprich eine andere Größe, die wir

hier messen, ist zum Beispiel die Komplexität und interaktive Algorithmen, da finden sie wirklich

viele, sei es irgendwelche Wahlverfahren oder Versteigerungen, also in wesentlichen Algorithmen,

die eine Interaktion benötigen. So was machen wir jetzt als erstes, wir haben jetzt im Wesentlichen

gesehen, was wir heute machen wollen, wir schauen uns als erstes ein weiteres Berechnungsmodell an,

also wir fangen an mit einem weiteren Berechnungsmodell und das des Random Access Models.

So warum machen wir das, ich gehe mal in zwei darüber. Naja das Ziel, wir könnten das natürlich

auch alles direkt auf Touringmaschinen machen, das ist in der Analyse aber ein bisschen aufwendig,

weil wir überlegen müssen, ok wo schreiben wir eigentlich hin, außerdem ist es von dem, was sie

im täglichen Leben so tun, nämlich sich mit relativ einfachen Computern zu beschäftigen,

in gewisser Weise sehr weit entfernt, das heißt wir gucken uns ein Modell an, das versucht dem

Modell, was sie täglich benutzen, näher zu kommen und wie sieht das aus, das sieht im Wesentlichen so

aus, dass wir einen Block haben, in dem ein Programm läuft, das ist also unser ganz normales

Programm und die Anweisungen werden, wie sie sich das vorstellen können, einfach von oben nach unten

abgearbeitet. Damit wir die von oben nach unten abarbeiten können, müssen wir wissen, an welcher

Position wir stehen und um dies zu tun, verfügt das Modell über einen gewissen Registereintrag,

der auf der aktuellen Anweisung zeigt, ok also hier in dem Fall zeigt C zum Beispiel auf 2.

Außerdem haben wir einzelne Register, die haben wir hier mit zum Beispiel R0, R1 und R2 spezifiziert