okay wir hatten beim letzten Mal mit dem Appetitmacher angefangen also wir hatten einen rekursiven Algorithmus denn Wesentlichen darauf beruhte die zwei zu multiplizierenden zahlen A und B als A1 mal B Hochkar plus A0 bzw B1 mal groß B hochk plus B 0 zu schreiben und dann haben wir die Multiplikation von zwei endstelligen Zahlen auf vier Multiplikationen von ein halbe stelligen Zahlen reduzieren können die Analyse hat dann gesagt es gibt quadratische Zeit das ist im Prinzip die gleiche Zeit die auch der Schule Algorithmus benötigt der Grund oder der wichtigste Grund wieso ich Ihnen diesen Twist vorgestellt habe ist dass man mit einem rekursiven Ansatz erstaunlicherweise noch erhebliche effizienter sein kann sogenannte Kara zu beaufmann Algorithmus die Beobachtung ist die folgende wenn man jetzt nicht diese einzelnen Komponenten A0 A1 B0 B1 separaten multipliziert sondern sich einfach mal anschaut A1 plus A0 mal B1 plus B0 dann kommt dabei was raus wo schon alle diese Kombinationen die ich brauche mit drin sind insbesondere auch diese beiden gemischten Therme A1 mal B0 A0 mal B1 die in der Form auch in dem anderen Algorithmus benötigt werden die schlechte Nachricht ist die Dinger werden zwar benötigt aber verschoben ja die beiden sollen mit um B verschoben sein der hier mit eins und der hier mit B Quadrat bei der Trick ist einfach ich berechne jetzt in diesem rekursiven Algorithmus der sieht in den ersten Zahlen genauso aus wie der alte rekursive Algorithmus berechne ich erstmal diese beiden Teilprodukte und die kann ich jetzt in zweierlei Art verwenden erstens naja wie in dem alten Algorithmus wird das Ding um B Quadrat verschoben und das hier c00 gar nicht so und jetzt kann ich die verwenden um dieses Ding hier zu korrigieren was ich haben will ist das und in dem um B Hochkar verschobenen stören die Dinger aber die habe ich sowieso schon berechnet die muss ich nur noch abziehen und was ich davon habe ist dass ich jetzt plötzlich eine langsam Multiplikation habe bei der ich nicht vier Multiplikationen der Länge in halbe brauche sondern nur drei was ich dafür bezahle ist dass ich ein bisschen mehr addiere aber der Trick ist addition ist billig ja hier sitzen Beispiel das gleiche dass wir vorher hatten ich berechne das hier direkt multipliziere das mit 10.000 unsere Basis war hier 100 oder die Basis des 10 aber das ks2 also muss ich bitte 100 mal 100 multiplizieren dann habe ich hier zehn plus eins mal 19 plus 84 und ich ziehe das und das ab und hier muss ich jetzt das noch addieren und dann kriege ich das gleiche Ergebnis wie vorher so die Analyse da war es jetzt so bei dem alten Algorithmus hatten wir hier vier Teil Multiplikationen und da stand glaube ich 7n oder sowas jetzt habe ich hier eine weniger dafür drei zusätzliche Additionen sozusagen aber wenn Sie das jetzt mal per vollständiger Induktion nachrechnen oder wenn wir dieses Master Theorem dass wir später noch kennenlernen anwenden merken wir plötzlich da kommt eine symptotische Laufzeit raus nicht mehr n hoch lockt zur Basis 2 von 4 sondern lockt zur Basis 2 von 3 das ist sowas wie 1,58 ja und das ist ein totes schnellerer Algorithmus wird da gleich auch noch Besserung zu vorführen ja genau also die Theorie sagt jetzt für hinreichend große Zahlen ist das schneller jetzt kann man sich fragen ist das auch in der Praxis so die Methodik die sich dahinter verbirgt wenn man so praktische Experimente mit algorithmentheorie verbinden soll nennt man auch im Engineering da gibt es zum Beispiel auch ein DFG Schwerpunktprogramm ist ein großes Forschungsprogramm der DFG dass ich koordiniere wo solche Dinge eine große Rolle spielen deshalb will ich jetzt mal kurz vorstellen was das überhaupt ist algerufen engineering man hat das Problem dass algorithment Theorie das ist im Prinzip das was wir hier machen ja aber naja wir machen Algorithmen eins ich mache die algorithment theorieergebnisse die sich in der Praxis bewährt haben wenn man das aber weiter treibt immer bessere komplizierte ausgefeiltere Algorithmen entwirft hat sich herausgestellt dann entfernt sich diese das was man da theoretisch entwickelt von dem was man in der Praxis braucht ja der Grund ist insbesondere dass die Frage da hinten jetzt probieren das mal ein bisschen leiser und die in der letzten Reihe sagen wir dann bitte ob es in Ordnung ist noch also wer hört mich in der letzten Reihe ja okay dann können wir es mal so versuchen genau also was hier passiert ist wenn man nur asymptotik betreibt ja und sagt wir machen Algorithmen da ist das Hauptziel dass eine worst case-schranke im OKAL cool möglichst gut aussieht da kommen halt auch Algorithmen raus bei denen der Algorithmen Entwurf vor allem auf dieses Ziel hin ausgerichtet ist eine gute Analyse zu machen und das heißt nicht dass der unbedingt implementierbar ist in der Praxis gut funktioniert und so weiter die Theoretiker würden vielleicht gerne haben dass die Praktika ihre tollen papers lesen und das dann nur noch implementieren und dann verwenden und das ist dann ganz toll das passiert dabei in der Praxis nicht immer ja aus guten Gründen auch deshalb hat sich dann eine andere Methodik als viel sinnvoller heraus kristallisiert nämlich angerufen Engineering was man da hat ist man macht Experimente und zwar nicht irgendwie völlig losgelöst sondern in unserem Zyklus dann entwirft Algorithmen analysiert sie auch weiterhin implementiert sie aber auch und macht Experimente und die Ergebnisse der Experimente werden dann nicht einfach Adapter gelegt sondern man lernt daraus verbessert Algorithmen und das kann mehrmals rundherum gehen auch die Denkweise dabei ist eine etwas andere als diese mathematische Denkweise in der algorithmentheorie man arbeitet nämlich eigentlich ähnlich wie in den Naturwissenschaften wo man falsifizierbare Hypothesen in den Mittelpunkt stellt und dann Experimente macht die diese Hypothesen entweder untermauern oder eben fallen ja man hat dann auch neben diesem Kreislauf vielfältige Kopplungen zu realen Anwendungen und arbeitet mit realen Eingaben erfolgreicher Algorithmen werden dann auch in algorithmen- beeinflusst dann auch die Modellbildung und und viele andere Aspekte hier das nur so als einen kleinen Überblick im Moment fange ich gerade eine Vorlesung an engineering da machen wir das dann in größeren Detail also zurück zu langsam mit Applikation was bedeutet algerufen Engineering verlangsam Multiplikation naja man überlegt sich jetzt wenn ich den Cara zu beauffahren Algorithmus wirklich in der Praxis anwenden soll wie implementiere ich das ganze dann wie mache ich Experimente dazu zunächst mal hat man einen tuningparameter das ist diese Basis B die zifferngröße da wir bei den meisten Rechnern heute einen landen eine wortweise Multiplikation schon eingebaut haben sollte man hier wahrscheinlich nicht B gleich ziehen verwenden wie in den Beispielen oder B = 2 mit bitweise Arbeit sondern zum Beispiel B = 32 wenn das die maximale Anzahl Bits ist die man mit einer Multiplikation mit einem Maschinenbefehl hinkriegen kann oder man könnte sich überlegen wir machen das über fließkomma Multiplikation muss sich dann aber überlegen wie viele Bits man daraus kriegt die exakt sind naja ja weitere tuningparameter oder eine eigentliche Verfeinerung des Algorithmus besteht darin zu sagen hier gibt es ein basisfall wenn ich nur eine einzige Ziffer habe dann mache ich eine Ziffern Multiplikation hindert mich aber auch niemand zu sagen ich mache eine größeren Wert als Abbruchbedingungen und ruft dann die schulmultiplikation auf weil erfahrungsgemäß ist halt so ein rekursiver Algorithmus hat Overheads dadurch dass man halt ein rekursiven Aufruf machen muss Daten auf den Stack kopiert und eben diese Additionen die zusätzlichen durchführt es gibt gute Gründe anzunehmen dass das erst ab einer Mindestgröße der Eingabe funktioniert ja ist also eine wichtige Tuning Maßnahme und dann natürlich Implementierungsdetails dass ich Assembler Befehle verwende vielleicht auf modernen Architekturen smd-befehle nehme wo dann mehrere Multiplikationen parallel durchgeführt werden und so weiter wir haben das jetzt nicht bis ins Letzte getrieben wir haben eine vernünftige cc++ basierte Implementierung genommen und dann kann man erst mal vor Experiment machen ne also jetzt nur für den Karat super auf meiner Algorithmus was ist denn jetzt eigentlich ein guter Wert für diesen Tuning Parameter weil ich umschalten soll auf den Schulleiter gewinnt muss und da stellt man hier fest aha sowohl für 2048 Ziffern als auch für 496 Ziffern ist 32 eigentlich ein ganz guter Wert kleinere Werte sind richtig schlecht bei größeren wird dann langsam schlechter okay das ist schon mal gute Nachricht hat was gebracht dieser Tuning Maßnahme und jetzt ist hier ein Vergleich mit dem schulargorithmus bin jetzt nicht hundertprozentig glücklich damit wie man einen Co-Autor das hier geplottet hat aber man kann schon was erkennen also wir variieren jetzt einfach mal die Anzahl Ziffern der Eingabe und messen die Ausführungszeit ich nehme an das ist eine mittlere Ausführungszeit in Sekunden über eine Anzahl Wiederholung und was wir hier sehen ist zunächst mal die der Schule Algorithmus das ist diese Kurve mit den Kreuzen die verläuft tatsächlich steiler als die beiden Kurven mit dem Karat Algorithmus und da haben wir jetzt zwei Varianten einmal mit Basisgröße 4 und Basisgröße 32 das ist wie man das aus der Theorie auch erwarten würde eine flachere Steigung nämlich nicht zwei sondern 1,5 8 und hier ist dann noch dann Offset ne die laufen parallel die beiden Kurven und was wir sehen ist dass diese Variante karatsu bei 32 die ist immer die beste eigentlich ne also die ist immer besser als karazuba 4 wenig überraschend ist sie bis zwei hoch fünf identisch mit der schulmethode also aber auch nicht schlechter und dann hat sie aber eine kleinere Neigung wird sie immer besser und ist dann tatsächlich am Ende sowas wie eine Größenordnung schneller ist das für große Eingaben habe ich wirklich eine deutliche Verbesserung und das war jetzt so dass das Ziel dieses kleinen experiments gibt es Fragen zu dem Fahrrad zu Hoffmann Algorithmus okay ja eine Sache die ich auch in dieser Vorlesung immer machen möchte ist ein Blick über den Tellerrand dieses eine zweitsemester Vorlesung wir machen hier die einfachsten Algorithmen für die jeweilige wichtigsten Probleme aber ich möchte Ihnen auch zeigen dass die Forschung weitergeht dass viele der Algorithmen die wir hier kennenlernen sind in den 60er oder 70er Jahren gefunden worden und ich möchte den Eindruck vermeiden dass Algorithmen irgendwie so eine Wissenschaft ist die stecken geblieben ist in den 70ern und seitdem macht man lieber weiß ich nicht weltweit Web oder alle möglichen Sachen aber das Spannende ist selbst fundamentale Algorithmen werden immer noch weiterentwickelt in entspannende Art und Weise also Blick über den Tellerrand was gibt's denn noch wie kann man die Ideen die wir hier kennengelernt haben weiter treiben wir haben ja jetzt gezeigt wie man durch aufspalten unserer Zahl in mehrere Komponenten Multiplikationen sparen kann das kann man tatsächlich weitertreiben man spaltet nicht in zwei Teile sondern in 48 oder sowas und dann kann man diese Potenz also dann steht da nicht mehr Enoch 1,58 sondern vielleicht auch noch 3,4 oder sowas die kann man sogar beliebig klein machen nur wird das natürlich so dass die Anzahl Additionen immer größer wird und man kann sowas sagen wie für jedes y größer 0 gibt es ein Algorithmus mit für Multiplikation der Info von N hoch 1 + y läuft es gibt aber tatsächlich nur noch stärkere Aussage wir können nämlich eine Technik namens Transformation benutzen um das sozusagen noch mal zu verallgemeinern und dann kommen wir tatsächlich auf eine lineare Anzahl von Multiplikation und das ist ein gewisser Weise bestmöglich wobei das ja auch ganz spannend ist das ist ein gutes Beispiel dafür dass wir sehr genau definieren müssen was unser Berechnungsmodell ist ich werde gegen Ende der Stunde argumentieren dass es gute Gründe gibt das Berechnungsmodell so zu definieren dass wir auf Logarithmus vielen Bits in konstanter Zeit rechnen können ja das wirkt auf den ersten Blick ein bisschen merkwürdig weil ich werde argumentieren es gibt gute Gründe dafür wenn wir das Akzeptieren gibt es wie gesagt diesen linealgorithmus der auch verhältnismäßig einfach ist ja also man muss schon wissen was diese schnelle Folie Transformation ist aber die kann man für viele andere Dinge verwenden und wenn man das verstanden hat die die Übertragung auf Arithmetik mit langen zahlen ist dann nicht so schwierig es gibt bei den Theoretikern andere Modelle wo die bit-komplexität angeschaut wird also man sagt dann naja meine Ziffern Multiplikation darf wirklich nur auf Ziffern konstanter Größe stattfinden oder vielleicht nur auf einzelnen Bits das ist vielleicht sinnvoll wenn man das in Hardware implementieren will direkt als Schaltkreis und dann gab es ein ganz klassisches Ergebnis von 1971 das sagt wir haben bitkomplexität n Login Lock login schon diese Ausdruck sagt dass das vermutlich ein bisschen kompliziertere Algorithmus ist und der ist dann tatsächlich vor wenigen Jahren noch mal verbessert worden zu zwei Hochofen Loks Sternen mal ein Login und da überhaupt die Funktion zu lesen erfordert ein bisschen Erfahrung ja log-stern ist der iterierte Logarithmus das heißt man nimmt das n logarithmiertes logarithmiertes noch mal du das so lange bis man eine Zahl kriegt die kleine gleich eins ist und da kann man sich überlegen das ist selbst zu astronomisch große Zahlen fast eine konstante aber eben mathematisch nicht ganz und auch zwei hochende Konstante ist immer noch eine konstante wirklich ist das hier ganz nah an in unserem Maschinenmodell ist das alles gar kein Thema da ist das einfach linear und Punkt und es ist für mich ein weiterer Grund in diesem Maschinenmodell weiter zu argumentieren ja trotzdem spannend dass man da immer noch Verbesserungen finden kann so das beendet das Kapitel des appetitmachers gibt es da noch Fragen zu okay dann das nächste Kapitel einführendes da habe ich jetzt die Steine von Stonehenge genommen weil ich so sage wir brauchen jetzt Handwerkszeug Hammer und Meißen was brauchen wir überhaupt loslegen zu können mit richtiger Algorithmik das sind viele Dinge die sie in Grundbegriffe der Informatik schon kennengelernt haben dich aber hier noch mal wiederholen möchte also erstmal was ist überhaupt Algorithmen Analyse was ist unser Maschinenmodell wie beschreiben wir Algorithmen auf einer abstrakten Art und Weise und auch was ist mathematischer Notation Fotografen so erstmal ja was ist also im tropischer Algorithmen Analyse eigentlich möchte ich ein Programm analysieren das sind Algorithmus implementiert und ich hätte gerne die Laufzeit dieses Programms für alle Eingaben das ist sozusagen die Maximalforderung an einer Algorithmen Analyse was ist die Laufzeit naja sagen wir mal Anzahl Takte und naja die hängt ab von der Instanz ne von der Eingabe Instanz da gibt's ganz viele beeingabelänge Enden verschiedene Eingaben und man kann sich überlegen dass das eine ziemlich komplizierte Funktion sein könnte der Mann dann auch wenig ansehen kann deshalb versucht man sich in einer kompakteren Beschreibung der Komplexität indem man etwas vergröbert dass man nicht mehr ganz so genau hinguckt und eine wichtige Vereinfachung die die Theoretiker sich anschauen ist dass sie nicht für jede Instanz das anschauen wollen sondern in Worst Case für alle Instanz in einer gegebenen Größe schreibe ich jetzt mal als Maximum über alle instanzgrößen gleich n t von i ja und wenn ich da geschickte Abschätzungen mache ist dieses Maximum manchmal einfacher auszurechnen als irgendwie in der geschlossenen Form für beliebige Eingaben das anzugeben und wir werden später auch Varianten davon kennenlernen zum Beispiel der mittlere Fall wäre sinnvoll dass man statt hier zu maximieren den Mittelwert berechnet oder den besten Fall dann hätte man hier ein Minimum stehen könnte auch sein dass man nicht nur einen Parameter eingabegröße hat sondern mehrere Parameter zum Beispiel wenn ich einen Grafen habe die Anzahl Knoten und Kanten des Grafen ja das Bild illustriert das ein bisschen wenn das hier alle die Ausführungszeiten für alle Eingaben mit einer Größe end sind dann interessiere ich mich hier für das Maximum Fragen dazu so die die andere Vereinfachung ist asymptotik grob gesagt ich lasse konstante Faktoren Weg etwas genauer gesagt ich lasse auch sozusagen anfangs Stücke weg also Verhalten für kleine Enden ja sie kennen alle haben auch letztes Mal das noch mal angeguckt die Definition von Ofen fnn das ist eigentlich eine Beschreibung für die Menge aller Funktionen die bis auf konstante Faktoren und anfangsstücke sich genauso verhalten wie er oder höchstens so stark wachsen genau nicht genauso sondern höchstens so stark wachsen ja da habe ich zwei existenzquantoren die mir sagen aha das ist der konstante Faktor er soll es eingeben und ein Null ab dem diese Aussage gilt so dass eben für alle in größer gleich null geh von in durch zehn Mal F von N nach oben beschränkt ist so und diese Definition kann ich variieren wenn ich das kleiner gleich durch ein größer Greif austausche dann kriege ich Omega von f&n das sagt sowas wie mindestens also F von N wächst mindestens so schnell nee geh von innen wächst mindestens so schnell oder genau bis auf konstante Faktoren und anfangsstücke ist tetta ist dann einfach die Schnittmenge von oben oh mein Gott und etwas weniger bekannt sind kleinofen f&n und kleinen Omega von f&n die sagen sowas wie echt weniger oder echt mehr und was man da macht ist dass man die Existenz Quantoren für die Konstanten durch alkantoren austauscht also z.B jetzt klein oh von F von N heißt geh wächst echt langsamer als es und das bedeutet für jede beliebige Konstante ist ab einem bestimmten Null geht von in kleiner gleich zehn Mal ff und entsprechend Omega von FN wächst echt schneller genau und alle diese fünf Dinger werden wir regelmäßig verwenden um halt einigermaßen abstrakte Aussagen für Algorithmen Analyse zu formulieren gibt es dazu fragen welche dieser Konzepte kennen sie nicht aus Grundbegriffe der Informatik genau haben sie gemacht prima da ist die unteren beiden sind neu okay ja genau aber wie gesagt das ist sehr ähnlich außer dass man hier den den quantoraustauscht wir werden da auch wenig drauf eingehen also wir haben traditionell auf Übungsplatz und auch in der Klausur ein paar relativ einfache Aufgaben dazu aber das wird nicht kein zentrales Thema dieser Vorlesung sein so das schöne ist diese OKAL kühl Rechenregeln man muss nicht immer zurück auf die Definitionen sondern es gibt einfach Rechenregeln die man routinemäßig verwenden kann um entsprechende Aussagen zu treffen zum Beispiel naja wenn ich eine Funktion C mal F von N habe dann ist die sowohl offen als auch Omega F von innen als auch Täter von FN oder wenn ich ein Polynom habe dann interessiert mich nur der der höchste polynomgrad oder wenn ich zwei Sachen summiere dann ist wächst das mindestens so schnell wie wie irgendeine der beiden Seiten oder wenn wenn ich hier zwei Funktionen habe wo wo wo geh gleich oh von F von N ist dann kann ich das einfach als Ofen schreiben Produkte kann ich in das Ohr reinziehen und so weiter da gibt's eine ganze Menge regeln da könnten wir auch Übungsaufgaben zu stellen mit denen man relativ intuitiv rechnen kann ohne dann jedes mal im Detail auf diese Definition zurückgehen zu müssen so dann Maschinen Modell wenn ich eine solide Algorithmen Analyse machen will dann muss ich auch überlegen auf was für einer Maschine läuft das eigentlich ab und das Problem ist reale Maschinen sind viel zu kompliziert die Laufzeit eines Algorithmus auf einer realen Maschine hängt von sehr vielen Dingen ab und jedes Mal wenn ich den auf einer anderen Maschine ausfüllen lasse kriege ich wahrscheinlich wieder andere Ergebnisse deshalb verwendet man für die Algorithmen Analyse vereinfachte Maschinenmodelle im Prinzip geht das auf John von Neumann zurück der 1945 einen Papier geschrieben hat wo sie eigentlich erstmal um was anderes ging damals waren Rechner sehr teuer ja man brauchte für jede logische Einheit irgendwie eine Röhre die weiß ich nicht 10 Euro kostet oder sowas und damit man sich das leisten kann also die zehn Euro kostet und außerdem nach zwei Wochen durchgebrannt ist wenn man Pech hat und dann ausgetauscht werden muss und damit man nicht die nicht schneller Röhren tauscht als das der Rechner überhaupt weiter läuft musste man möglichst einfache Rechner bauen kam dann ein paar Hundert oder einer niedrigen vierstelligen Zahl Röhren aus glaube ich und er hat sich dann halt ein Architektur überlegt für den Rechner der halt minimalistisch ist er beruhte insbesondere darauf dass einen meinen Uniformen Speicher hat der für alles mögliche gebraucht werden kann der sehr flexibel einsetzbar ist der natürlich nur ein Rechenwerk hat dieses ursprüngliche von neumann-modell hatte genau einen Register und hat ansonsten sehr viel Daten direkt aus dem Speicher geholt heute beschreibt man das ein bisschen anders es gab dann Anfang der 80er Jahre so eine Bewegung die sagt naja eine vernünftige Rechner Architektur arbeitet eigentlich mit einem Register Fall von Karl Registan und macht alle arithmetischen Operationen zwischen diesen Registern und hat außerdem noch einfacher lade- und speicherbefehle zwischen Registern und speichern das macht jetzt aus theoretischer Sicht keinen Riesenunterschied aber ich übernehme halt diese moderne Sichtweise sagen wir mal und man kriegt dann etwas was man auch als renomme bezeichnen kann nämlich so wir haben Register wir haben eine arithmetische Einheit es gibt eine ganze Menge Maschinenbefehle die zwei Register lesen und das Ergebnis in drittes Register schreiben dann gibt es lade und speicherbefehle und es gibt halt eine Kontrolle die ausfällt welche Befehle gerade ausgeführt werden die kann ich durch bedingte Sprünge zum Beispiel steuern aber im Großen und Ganzen geht das immer noch auf diese von Neumann Architektur zurück und ja dieses Modell möchte ich jetzt ein bisschen genauer erklären die Register und auch die Speicherstellen speichern kleine ganze Zahlen und jetzt wie groß sollten diese Zahlen sein naja die werden unter anderem verwendet die Register um den Speicher zu adressieren damit das überhaupt geht muss ich hier mindestens wenn ich einen Platz Verbrauch von S habe muss ich mindestens log-s-bits in diesen Registern speichern können sonst kann ich in diesem Modell gar nicht den Speicher adressieren ein Praktiker würde jetzt sagen naja ich habe eine konstante Bitbreite und damit auch ein konstantes Speichergröße die ich erreichen kann und das ist dann halt mein Rechner das ist schön für die Praxis aber für die theoretische Informatik nicht akzeptabel weil dann wird aus dieser Maschine unnötig komplizierte Beschreibung eines endlichen Automaten ja außerdem sind dann wenn man also symptotik betreibt plötzlich alle Eingaben konstant groß alle Ausführungszeiten sind konstant und ja das nicht sinnvoll ja deshalb muss man um mir die asymptotik überhaupt mal in Gang zu bringen die Maschine ein bisschen mächtiger machen und der einfachste Art ist halt hier größere Register zuzulassen es gibt andere Varianten von registermaschinen die dann konsequent sind und sagen dann lasse ich doch beliebig große Register zu das ist aber auch keine gute Idee weil dann kann man sozusagen Tricks machen um riesige Register Inhalte zu produzieren die diese Maschine unrealistisch schnell macht dann kann man insbesondere Komplexitätstheorie vergessen das ist was was sie im nächsten Semester in Grundlagen theoretischer Informatik dann kennenlernen deshalb ist das hier ein guter Kompromiss zu sagen wir machen die Register so klein wie überhaupt nur sinnvoll nämlich logarithmisch in der im Platzverbrauch des Algorithmus und das ist meistens dann auch logarithmisch in der eingabegröße genau dann ja die Anzahl Register ist eine konstante K der Hauptspeicher na ja das sind auch wieder diese Maschinen Worte mit blogspace vielen mit und das ist sowas wie ein unbeschränkter Größe ja und ich muss alle meine Datenstrukturen da irgendwo in diesen Speicher packen Speicher Zugriff schreibe ich jetzt mal als Pseudo-Code Teilen Register i Krieg den Inhalt von des Speichers an der Stelle die durch den Inhalt von Register J dargestellt ist das ist jetzt sowas wie indirekte Adressierung nennt man das in der Hardware Welt oder eben ich kann umgekehrt den Inhalt von der riottenspeicherstelle in Register i speichern das sind die in diesem einfachen Modell die einzigen Befehle die Speicherstellen zugreifen es kann sein dass ich noch Befehle brauche die irgendwie konstanten laden oder aber ist nicht so wichtig rechnen naja das schreibe ich auch als eine Zuweisung ri gleich RJ verknüpft mit RL und dieses Verknüpfung kann alles mögliche sein Arithmetik also addition Multiplikation Subtraktion Division aber auch Vergleiche ja dann ist das Ergebnis 0 oder 1 je nachdem ob es ja oder falsch ist oder Logik irgendwie logische unverknüpfung vielleicht auch bitweise logische unverknüpfung oder exklusives oder Negation alles was sie in technischer Informatik kennenlernen oder wahrscheinlich auch schon in den Grundbegriffen gesehen haben und was halt so Operatoren von Java auch sein können schiebe Befehle genau bedingte Sprünge kann sowas schreiben also wenn Register i0 ist springe zur Programmspeicher Stelle J Uhu ja so das habe ich schon erklärt also warum habe ich diese kleinen ganzen Zahlen konstant viele Bits wird es endlich ein Automaten führen beliebige Genauigkeit würde die Komplexitätstheorie zerstören man verwendet sowas aber manchmal für Berechenbarkeit also in je nachdem wie genau ihr Kurs Grundlagen theoretischer Informatik ist mögen sie da einen registermaschinenmodell kennenlernen das im Prinzip das hier ist ganz ohne den Hauptspeicher und dafür sind die Register aber beliebig groß das ist ein komisches Modell aber es ist halt mathematisch ein bisschen einfacher zur Hand haben als dieses Modell für die Klassifikation was überhaupt brechenbar ist denn endlich vielen Schritten macht es keinen Unterschied ja und wir haben halt diesen Kompromiss hier gewählt so zurück zur Algorithmen Analyse in unserem Modell was wir jetzt machen im Prinzip ist Befehle also wie viele Befehle in unserem Rahmen Maschinenprogramm wenn ausgeführt in der Annahme dass ein Befehl in einem Takt ausgeführt wird das ist Quatsch in der Praxis können Maschinenbefehle mal mehrere Takte brauchen mal mehrere Maschinenbefehle in einem Takt ausgeführt werden das hängt von sehr vielen Dingen ab aber das ist uns alles zu kompliziert und wir rechtfertigen das mit dem ukühlen ja konstante Faktoren werden weggeworfen und unter bestimmten Annahmen ist das dann egal ob das jetzt eintakt pro Befehl ist oder mal ein bisschen mehr oder ein bisschen weniger also ignorieren dann insbesondere komplexe Hardware Aspekte wie Cashews Pipelines instruktions Parallelismus etc ja wir können auch andere Ressourcen analysieren klassisch Platzverbrauch das gar nicht so klar wie man den definiert wir könnten die letzte belegte Speicherzelle nehmen dann können auch Löcher da drin sein aber wir sagen die Löcher muss man mit bezahlen oder die Anzahl belegter Speicher stellen oder müssen wir dann auch gucken wie das Betriebssystem den Speicher verwaltet wenn wir das in einer höheren Programmiersprache formulieren im Detail sehr kompliziert aber bei den Algorithmen die wir betrachten kommt eigentlich nicht so drauf an wenn wir konstante Faktoren ignorieren in entsprechend werde ich Speicherverwaltung etwas stiefmütterlich behandeln in dieser Vorlesung ich werde halt immer mal wieder eine Bemerkung machen ah hier kommt jetzt bei der realen Implementierung drauf an wie man die Speicherverwaltung macht aber das lässt sich meistens lösen okay genau also man kann natürlich auch noch viele andere Dinge analysieren zum Beispiel Energieverbrauch naja da würde ich mich jetzt in so einem einfachen Modell auch darauf zurückführen dass jeder Takt irgendwie konstant viel Energie verbraucht stimmt auch nicht aber so genau weiß das ohnehin niemand also auf dem abstraktionslevel dieser Vorlesung setzen wir eigentlich Energieverbrauch eine zeitgleich ja also wir effiziente schneller Algorithmen haben dann kann ich den Rechner auch vorher abschalten und ich verbrauche weniger Energie und das ist eine ganz gute Ernährung ein paar Worte möchte ich doch noch rüber komplexere Maschinenmodelle verlieren was in der Praxis tatsächlich sehr wichtig ist sind Caches also schnelle Zwischenspeicher die haben eine begrenzte Größe aber sind so organisiert dass sie kürzlich zugegriffene Daten oder häufig zugegriffene Daten in diesem schnellen Zwischenspeicher halten und wenn ich Algorithmen schreibe die halt ein kleines working Set haben sagt man auch also die meisten zugegriffenen Daten in so einem kleinen Cache halten können profitiere ich und haben eine weitere Eigenschaft es wird blockweise zugegriffen das heißt wenn ich einen maschinenwort zugreife und das ist nicht im Cash dann geht die Maschine her und holen den ganzen Speicher Block von mehreren Maschinen Worten in den Cache schreiben das heißt insbesondere wenn ich konsekutive Speicherbereiche zugreife ist das schneller als wenn ich zufällig hin und her sprenge in meinem Speicher das ist eine wichtige Abweichung vom Rahmenmodell und ich werde das immer mal wieder als informelles Argument bringen warum Algorithmus a in der Praxis vielleicht besser ist als Algorithmus B so und schließlich parallel Verarbeitung heutzutage hat selbst ein Smartphone vier kernprozessor Desktops noch mehr und wenn sie richtig rechnen intensive Aufgaben haben benutzen sie parallel Rechner mit tausenden oder in Einzelfällen auch mal mit Millionen von Prozessoren selbst eine Grafikkarte hat tausende von Recheneinheiten und wenn sie die vernünftig nutzen wollen müssen sie sogar logischen Parallelismus zur Verfügung stellen der nochmal zwei Größenordnung größer ist also zigtausende von parallelen rechenvorgängen laufen eigentlich gleichzeitig ab auf einer Grafikkarte und entsprechend ist es eigentlich sehr wichtig Algorithmen so zu formulieren das mehrere Dinge unabhängig voneinander parallel stattfinden können das ist ein Moment ein großes Thema in der Algorithmik klassisch die meisten Algorithmen die man sich anschaut erstmal sequenziell für einen Prozessor und manchmal ist es einfach den zu parallelisieren manchmal unmöglich man brauchen komplett neuen parallelen Algorithmus und wir haben lange darüber nachgedacht ob wir Ihnen sofort parallele Algorithmen beibringen haben uns dann aber dagegen entschieden im Endeffekt weil es so viel über Algorithmen zu lernen gibt dass man irgendwo erstmal Dinge weglassen muss also was wir hier machen ist in Algorithmen eins werden sequenzielle Algorithmen unterrichtet wird ab und zu mal eine Bemerkung darüber fallen lassen was leicht parallelisierbar ist und was nicht und sie lernen dann in Algorithmen zwei einige Grundlagen von parallelen und in Programmierparadigmen lernen sie auch ein bisschen paralleles programmieren das erscheint uns im Moment der beste Kompromiss zu sein ja und sie lernen dabei in der Technischen Informatik auch schon einiges über die Rechner Architektur Aspekte von parallel rechnen so gibt es Fragen zum Maschinenmodell nur dazu dem Konzept der Algorithmen Analyse im Allgemeinen okay ja hier ist noch mal so ein Bild wie man abstrakt gesprochen dieses einfache von neumann-modell in dem Bild aufbohren könnten dann hat man vor allem den Eindruck dass alles so ein bisschen unscharf aussieht alles wird vervielfältigt das fängt an auf der feinstkörnigen Ebene ich habe mehrere Rechenwerke ich habe vielleicht auch Register die breiter sind die hätte ich auch noch vervielfältigen können ich habe sowas das Intel hyper-trading nennt dass ich mehrere programmkontexte parallelhand haben kann die auch eigene registersätze haben nebenbei gesagt dann kann es mehrere Kerne geben in diesem Fall acht Stück oder sowas die auf einem Chip zur Verfügung stehen die schnellsten Cache Levels werden vielleicht auch repliziert in dem Fall war das ist das sowas wie zwei Kerne teilen sich jeweils einen one Cash sagen wir mal oder sagen wir mal eine momentan beliebte Konfiguration ist ich habe zweifaches hyper-trading zum Beispiel auf den internetprozessoren die teilen sich aber einen one Cash und dann teilen sich mehrere Kerne einen L2 Cash und noch mehr Kerne teilen sich ein L3 cash und noch mehr Kerne teilen sich einen Zugang zum Hauptspeicher und dann gibt es aber mehrere Sockel die mehrere Speichermodule gleichzeitig zugreifen können aber es gibt Geschwindigkeitsunterschiede dabei welche Speichermodul man zugreift und dann gibt es irgendwie ein Netzwerk wo viele von diesen Computern wieder verbunden werden das auch wieder irgendeine Hierarchie haben kann also man kommt dann zu sehr komplexen hat der Strukturen wo wenn Sie die ganzen Quellen von paralismus die dazu Verfügung stehen multiplizieren man auf immense Zahlen kommt wie gesagt viele hunderttausend oder auch Millionen von parallel ausfüllenden Einheiten ist durchaus denkbar so pseudokot habe ich beim letzten Mal schon ein bisschen zugesagt möchte ich auch nicht irgendwie so programmierenden pseudokon eine ganze Vorlesung machen das wäre glaube ich ziemlich langweilig sondern ich werde das so Justin time die einzelnen Sachen einführen die ich da verwende die Hoffnung ist dass das was sie erwarten aus Java oder sowas man irgendwie eins zu eins aus dem Pseudocode übersetzen kann nur dass das sie halt eine kompaktere und typografische schönere Formulierung ist aber vielleicht manchmal nicht ganz so präzise ist wie eine reale Programmiersprache gucken uns mal ein Beispiel an nehmen wir an wir wollen eine Klasse für komplexe Zahlen definieren dann würde ich in meinem pseudoku Schreiben klar ist komplex das ist sowas wie generizität die Parameter number der sagen soll nachher eine reelle Zahl hat ein Realteil und immer generell und diese diese beiden Komponenten werden wieder als eine normale Zahl repräsentiert das könnten aber verschiedenste Dinge sein das könnte zum Beispiel Single precision floating point sein was ich hier einsetze double precision floating point vielleicht auch Ganzzahl dann kriege ich sowas wie ganzzahlige komplexe Zahlen oder irgendwie eine langzahl Arithmetik Repräsentation oder alles mögliche und dann Krieg der Typ Name hier Parameter das klingt jetzt ein bisschen komisch aber was ich damit im Prinzip mache ist ich habe eine kompakte Beschreibung eines Konstruktors gleich mit der mit der Klassen Deklaration mit dabei ja also der der Default Konstruktor von Komplex kriegt zwei ganze Zahlen das sollte number stehen nicht Element und intern habe ich die members oder so wie die in C++ danke schön intern also ich repräsentiere eine komplexe Zahl mit den Attributen ehren und real teilen und immer gelehrtal und die werden halt initialisiert auf diese Parameter des Konstruktors X und Y ja Semikolons lasse ich weg und dann kann ich innerhalb der Klasse gleich Funktionen deklarieren zum Beispiel absolut wert einer komplexen Zahl ist die Wurzel aus den Quadraten von Reha aus der Summe der von realtal zum Quadrat plus Imaginärteil zum Quadrat return sagt halt das ist der Rückgabewert was wir hier auch sehen ist es gibt Funktionen ohne Parameter das ist bei objektorientierter Programmierung sinnvoll weil man ja schon auf den den Zustand des Wertes selber zurückgreifen kann ja und in C hätte ich hier jetzt so komische leere Klammern das ist typografisch nicht schön und redundant und es hat noch einen anderen Vorteil ich könnte mir jetzt überlegen eine andere Repräsentation von komplexen Zahl zu nehmen nämlich komplexe Zahl auch definieren durch den absolut wert und ein Winkel zwischen 0 und und damit kann man dann bestimmte Operationen effizienter machen und das könnte ich jetzt machen ohne das Interface zu ändern dann wäre plötzlich dieser absolut wert keine Funktion mehr sondern Attribut aber die Programme die das benutzen würden das gar nicht mitkriegen ja das ist ein gutes Argument warum man Funktionen ohne Parameter so schreiben will ja dann geht's noch eine Funktion App die addiert eine weitere komplexe Zahl zu sich selbst hinzu und gibt eine komplexe Zahl zurück und die berechnet hier den Real Teil von sich selber plus den realtal von C Strich als neuen real teil und den Imaginärteil von sich selber Plus in Imaginärteil von zerstrich baut daraus eine komplexe Zahl ruft also den Konstruktor auf und gibt das ganze zurück gibt es an dieser Stelle fragen zum pseudokot okay ach so gute Frage also man konnte natürlich sagen könnte jetzt sein dass man sagt number soll irgendwie sowas alles sein was ich für eine Zahl verhält hier meine ich aber was anderes das ist sowas wie ein Typ Parameter das heißt Realteil und immer die gemerkt hat sollen selber wieder zahlen sein das sind aber jetzt keine komplexen Zahlen oder sowas genau also das ist tatsächlich auch sowas in in Pascal gibt es keine echte generizität aber es gibt ja und da kann man sagen hier das hier ist eine Reihe von und dann ein Typ das ist im Prinzip das gleiche wie generizität nur eben sehr eingeschränkt und das habe ich hier übernommen um eine einfache Notation für Parameter zu haben weitere Fragen okay so ich bin ein bisschen schnell ja also wir sollen schon noch ein bisschen weiter machen denke ich das passt eigentlich auch jetzt noch gut zum Pseudo-Code eine Sache die wir für die wir hier ein bisschen syntaktischen Zucker dazu gebaut haben sind Sachen die eigentlich eher mit Programmdokumentation zu tun haben als direkt mit dem Programm und auch mit ja Korrektheit von Programmen und so weiter es gibt ein Konzept aus der Softwaretechnik das heißt Design bei contract und es gibt Konzepte zur ich sag mal zum zum mathematischen Verständnis dessen was ein Programm überhaupt tut das sind Schleifen in Varianten und Datenstruktur in Varianten und das Konzept möchte ich hier kurz vorstellen ja in der einfachsten Form gibt es schon Statement Assault das kann irgendwo im Programm stehen und steht und irgendwie eine Bedingung und damit stelle ich eine Behauptung auf ich sage zu diesem wenn dir das Programm an diese Stelle kommt dann muss eine bestimmte Bedingung gelten für den Zustand dieses Programms also vor allem für die wertebelegung des Speichers und der Register und die Aussage lautet naja ich behaupte das gilt und wenn das nicht gelten sollte dann gibt's ein Problem ja man kann dann optional diese searchance auch wirklich zum Laufzeit überprüfen lassen und dann wird halt eine Fehlermeldung ausgegeben wenn die nicht gilt es ist falsch wir werden dir aber viel allgemeiner verwenden da können dann zum Beispiel Prädikaten logischer Aussagen mit Al Quantoren drin stecken die man gar nicht effizient überprüfen kann aber wir können trotzdem damit das Programm dokumentieren und sagen dieses Programm ist nur korrekt wenn an dieser Stelle im Programm folgende Bedingungen gilt und das hilft einem zu verstehen was das Programm überhaupt tut so und jetzt gibt es spezielles die besonders nützlich sind und die man besonders häufig verwendet das ist zum Beispiel eine Vorbedingung eine Bedingung für das korrekte Funktionieren einer Prozedur oder Funktion und sagt am Anfang ein man macht eine assechen am Anfang eines programmstücks oder einer Prozedur und sagt dann aha das die wird insbesondere Aussagen machen über die Parameter dieser Prozedur und schränkt damit sozusagen die das ein was diese Prozedur tun kann das hat auch was mit Design bei contract zu tun also die Idee ist diese Prozedur formuliert Bedingungen an ihr korrektes Funktionieren die verlangt also vom aufrufenden diese Vorbedingung einzuhalten sonst garantiert sie nichts ja wenn die Vorbedingung aber eingehalten wird dann garantiert sie eine nachbedingung das ist sozusagen eine Aussage darüber was dann geleistet wird wenn die Vorbedingungen eingehalten wird und das ist kann man sich vorstellen eine sehr nützliche Art zu dokumentieren was ein Programm tut indem man für alle wichtigen Prozeduren Vorbedingungen und nachbedingungen angibt was für die Verständnis dessen was zwischendrin passiert noch wichtiger ist und Invarianten das sind Aussagen erst mal ganz allgemein die an vielen Stellen im Programm gelten und was meine ich mit vielen Stellen da gibt es zwei wichtige Kategorien zunächst mal sogenannte Schleifen Invarianten die gelten vor und nach jeder Ausführung einer Schleife und die charakterisieren im Prinzip den Fortschritt den eine Schleifen Ausführung ermöglicht und es gibt Datenstruktur in Varianten die gelten vor und nach jedem Aufruf einer Operation auf diesem Datentypen und beschreiben sozusagen auf eine abstrakte Weise das was diese Datenstruktur überhaupt repräsentiert und wir werden halt im Laufe der Vorlesung sehen dass diese Invarianten in zentrales Werkzeug für den Algorithmen Entwurf sind und insbesondere auch von den korrektheitsbeweis also wir werden ganz oft diese Invarianten mit angeben dann auch auf einer abstrakten Niveau argumentieren warum diese Invarianten eingehalten werden und damit einen high-level korrektheitsbeweis geben was man tatsächlich auch machen kann ist sehr detailliert und formal zu beweisen dass solche Invarianten eingehalten werden indem man Schritt für Schritt verfolgt was die einzelnen Zeilen des Programms tun und dann gelangt man zu einer formalen Programm Verifikation das ist etwas was den hier nicht vertiefen was aber zum Beispiel in der Vorlesung formale Systeme eine große Rolle spielt an dieser Stelle fragen dazu was Vorbedingungen nachbedingungen in Varianten sind das ist wahrscheinlich im Moment noch ein bisschen abstrakt aber wir werden halt viele Beispiele sehen und ich werde auch jetzt schon mal gleich einen nicht triviales Beispiel angegeben was übrigens ein anderes als das im Buch hier ist eine Funktion die für sagen wir mal eine reelle Zahl eine ganzzahlige Potenz dieser Zahl ausrechnet also wir wollen a hoch Null ausrechnen wenn es die Vorbedingung naja könnte man sagen ja ich möchte auch auch -1 ausrechnen können da muss ich dividieren das kann diese Prozedur nicht wie funktioniert nur wenn er null größer gleich Null ist Entschuldigung dann brauche ich irgendwie stumm Schalter und außerdem drücke ich mich um den Fall dass sowohl A als auch null beide Null sind weil da ist muss man sich irgendwie überlegen wie man das überhaupt definiert ob das nun oder einzahlen soll insbesondere so aber wenn du so Vorbedingungen erfüllt ist dann garantiere ich das der Rückgabewert eher am Ende auch null ist so wie mache ich das ein naheliegender Algorithmus um Potenzen auszurechnen wäre zu sagen okay ich mache eine vorschleife die Null Mal durchgeführt wird und das Zwischenergebnis jeweils mit Arm multipliziert da brauche ich keine große programmverifikationen um zu verstehen dass das korrekt ist aber das wären lang war langsamer Algorithmus hier werde ich ein Algorithmus angeben dessen Laufzeit nur Logarithmen Null ist und um den zu verstehen ist es durchaus nützlich sich der Schleifen in Variante anzuschauen okay gucken wir uns den Algorithmus erstmal allgemeiner an ich habe temporäre Variablen P und er die initialisiere ich auf A bzw eins und die Invariante die ich jetzt jeweils aufrecht erhalte ist das P hochn mal R gleich auch null ist auch null ist das Ergebnis dass ich am Ende haben will und der Trick ist ich habe hier eine waldschleife die abbricht wenn n gleich Null wird okay genau ich habe eine waldschleife die abbricht wenn n = 0 wird so das ist der Trick diese Variante gilt insbesondere auch nachdem die waldschleife zu Ende gelaufen ist ja und was steht dann da P hoch 0 mal R gleich auch null okay P hoch 0 ist 1 also eher gleich auch null ich bin fertig ja also ich habe jetzt eine Invariante formuliert die wenn das Ding überhaupt terminiert uns das richtige Ergebnis liefert was ich jetzt noch brauche ist eine Möglichkeit ist das n systematisch kleiner zu kriegen eine Möglichkeit es wäre das immer zu dekrimentieren und mit und das P mit Art zu multiplizieren dann wäre das Ganze trivial aber langsam und ich mache was geschickteres so ich habe zwei Fälle wenn in ungerade ist dann wird endekrementiert und er mit P multipliziert PS einfach mein a und ja das stimmt dann offensichtlich so damit komme ich aber nicht sehr viel weiter also wenn ich das könnte ich auch immer machen dann hätte ich meinen trivial angeht muss der Trick ist wenn in gerade ist dann gibt es eine effizientere eine schnellere Möglichkeit das end zu reduzieren ich sage da nämlich aha ich halbiere n und ich quadriere und dann kann man sich überlegen bleibt die Schleifen in Variante auch erhalten und das ist jetzt nützlich weil was passiert hier das n wenn es ungerade ist wird es zwar nur dekrimentiert aber anschließend ist es gerade und dann wird es halbiert das heißt jeweils maximal zwei Durchläufe ist das Schleife halbieren mein Engel das heißt insgesamt brauche ich nur von Login Durchläufe und die Invariante wird erhalten na gut das muss man im Detail sich noch mal anschauen gucken uns erstmal ein Beispiel an ja ich rechne 2 hoch 5 ja Iteration 0 P wird auf zwei initialisiert er auf eins ns5 und p hochnmal r das ist meine Invariante ist 32 und wir sehen hier schon das bleibt immer der Fall okay 5 ist ungerade also wird in degmentiert er wird mit P multipliziert also einmal zwei ist zwei und ja das war's hier in Variante bleibt erhalten jetzt ist n = 4 im nächsten schleichen Durchlauf sehe ich aha vier ist gerade also ich halbiere n es geht von vier auf zwei und ich quadriere P das geht von zwei auf vier und wir sehen in Variante bleibt erhalten nächste Schleifendurchlauf NS2 das ist immer noch gerade also halbiere ich n das geht von zwei nach eins ich quadriere P es geht von 4 auf 16 in Variante bleibt erhalten nächsten Schleifen Durchlauf ist n gleich 1 das ist Ungerer das wird dekrementiert ich multipliziere er mit P kriegt ihr 32 in Variante bleibt erhalten und wo Alarm ein Endergebnis 32 ist 2 hoch 5 gucken wir uns das mal etwas genauer an also warum bleibt die Invariante erhalten wenn ungerade ist ja der Wert der mich interessiert kann ich ja auch schreiben als P hochn-1 mal P mal R naja aber wie auch n -1 das ist mein neues n also n -1 ist mein neues n und pi mal er ist mein neues er das heißt P hoch neues n mal neues R ist der gleiche Wert wie vorher also bleibt die in Variante erhalten wenn in gerade ist dann mache ich das so ähnlich ich schreibe P hochn als P mal P hoch n halbe naja aber P mal P ist mein neues P und ein halbes mein neues n der Wert bleibt der gleiche ja damit ist in beiden Fällen die Invariante allen und ich habe kein Problem genau jetzt noch ein bisschen zu Pseudo-Code in diesem Beispiel was lernen wir hier gut eine Funktion wird deklariert die hat einen Funktionswert als Typ mit Doppelpunkt und denke ich zu fotografisch ganz okay es ist search steht halt vor dem logischen Ausdruck ich schreibe nicht irgendwie oder auch dieses logische und Zeichen benutze also Mathe ich benutze für Datentypen und manchmal auch die die mathematischen Datentypen wie natürliche Zahlen reelle Zahlen auch wenn ich in der Realität natürlich Repräsentationen mit endlicher Genauigkeit wähle ich habe eine wildschleife weil Bedingungen du Schleifen Körper wird eingerückt und gehört alles zu derweil Schleife die Invariante ist bedeutet das gleiche wie die assurtgen aber sagt dies ist eine Schleifen in Variante ist ja was wozu gehört wird durch Eindrücke klar hier ist jetzt mal ein Semikolon weil ich in einer Zeile mehrere Statement schreibe ich benutze durchaus so Post dekriment Operatoren wie ein Tier oder aber und eine Sache die hier glaube ich ganz interessant ist ist dieser das könnte man eine parallele zufallsung nennen man könnte ja hier auch schreiben Eltz und jetzt zwei Zeilen n = 1/2 und dann in der nächsten Zeile P = P mal P aber der Trick ist wenn ich mit diesen Invarianten arbeite dann kann ich ganz oft durch diese Parallelen Zuweisungen dafür sorgen dass sowohl vor der Zuweisung als auch nach der Zuweisung die Invariante gilt wenn ich hier zwei Einzel Befehle schreiben würde dann wäre zwischendurch die Invariante verletzt das wäre jetzt nicht schlimm weil meine einzige Bedingung ist dass die Invariante am Anfang und am Ende des Schleifen Körpers gilt ich mache keine Aussagen darüber was zwischendrin passiert aber irgendwie ist es schöner und auch für den Beweis einfacher wenn man sozusagen in dieser Truppe Schreibweise angibt welche Zuweisungen ausgeführt werden müssen damit die Invariante komplett erhalten bleibt und es gibt auch ein Hinweis darauf welche Variablen hier Zusammenhängen bezüglich der Invariante ja was gibt's hier noch an sind Tags ja Kommentare werden wir jeden Tag aber mit so Doppel Backslash Doppel Slash dargestellt sonst noch Fragen zu diesem Algorithmus dem pseudoku dafür oder sowas davon nun mal überlegen also gucken wir erstmal an was vorher ist also hier müsste eine 16 sein sagt Kommilitone also wenn P = 16 und n gleich eins in der Zeile davor da sind wir uns einig dass das noch stimmt da sehe ich NS1 das ist Ott also wird n von 1 auf 0 und er von 16 auf ja ja da haben sie recht da ist irgendwas falsch er war zwei genau das ist richtig unter die 16 sollte stehen bleiben ja okay genau vielen Dank hier sollte eine 16 stehen weil die im Fall North verändert sich Pia gar nicht danke schön weitere Fragen okay so noch mal zurück zur programmanalyse ja ich habe erstmal bei der asymptotik gesagt was ist programmanalyse und wie hängt das mit OKAL kühl und Worst Case zusammen dann habe ich bei Maschinenmodell gesagt wie mache ich programmanalyse für Assemblerprogramme das war schon ein bisschen vereinfachen also ich zähle nur mal assembla Befehle aber wir werden in der dieser Vorlesungen eigentlich nie Assembler Programme hinschreiben oder gar analysieren wir werden immer diese pseudokudes analysieren und ich werde aber jetzt versuchen zu argumentieren dass man sozusagen einen arme Leute Compiler einsetzen kann um den pseudokrit in Maschinenbefehle zu übersetzen und da uns konstante Faktoren nicht interessieren kann man da auch ein sehr schlechten Compiler nehmen und sehr einfachen und das werde ich jetzt so ein bisschen skizzieren wie sollen Compiler aussehen könnte und wie man daraus regelt für die programmanalyse vom Pseudocode ableiten kann ja also wir haben die Pseudo-Code einfach übersetzungsregeln in Maschinenbefehle und können daraus umgekehrt Regeln ableiten um direkt im pseudokultisch zu analysieren fangen wir mal langsam an wenn wir zwei Statements hintereinander haben naja dann erzeugen wir Code für diese beiden Statements führen das hintereinander aus und die Ausführungszeit ist halt die Summe dieser Befehle ja das ist eine ganz einfache Übersetzung das ist die Zeit für if-bedingungen Dennis gut das ist die Zeit für die Auswertung der Bedingungen plus naja entweder t von ihr oder t von i- eine möglich eine konservative Abschätzung ist zu sagen naja höchst ist das Maximum von den beiden passiert nicht immer ausreichend für die Analyse aber das zum Beispiel eine gültige Analyse Regel oder was ist die Zeit von wiederhole ein bisschen Bedingungen gilt naja das ist sowas wie die Summe über alle Ausführungen der repeat Schleife Zeit für die Iteration und das schließt natürlich die Bedingungen mit ein die muss jedes Mal mit getestet werden oder rekursive aufrufe dann kriege ich halt so rekurrenz relation also so habe ich eine Abbildung von pseudokot auf programmanalyse analysieren zum Beispiel das rettschleife und im Buch wird dann erklärt wie man eine Analyse für repeat übersetzt benutzt um auch weil und vorschleifen zu analysieren das ist kann man als syntactic sugar von der repeat Schleife ansehen im Endeffekt wenn ich schleifenanalysiere da muss ich im Endeffekt Summen ausrechnen ich muss für jede Schleifen Iteration angeben wie lange braucht diese Iteration und das muss ich sie mir über alle Schleifen Iteration und wenn ich Glück habe kann ich das geschlossen ausrechnen und da haben sie tatsächlich erstaunlich viele Möglichkeiten das was ihr in H&M lernen anzuwenden ja und das haben wir zum Beispiel gesehen bei der schulmultiplikation da wurden dann in jeder Iteration leicht unterschiedlich lange Zahlen addiert und Ziffern Multiplikation durchgeführt und daraus kam irgendwas quadratisches und jetzt möchte ich mir etwas genauer angucken dieses Master Theorem dass ich bereits mehrfach erwähnt habe besonders einfache Form von rekursiven Programmen die aber so oder ähnlich in dieser Vorlesung immer wieder auftauchen wird so nehmen wir an wir haben eine rekurrenzrelation eher von N ähm eine basisfall für n = 1 ist das A sonst ist das zehn mal n plus D mal R von N durch B also wir haben hier einen pattern das sehr ähnlich zu dem ist was wir für schulmultiplikationen und Cara zubehoffmann Multiplikation schon hatten basisfall der braucht konstante Zeit wenn man auch konstant große Eingaben hat wir haben einen teileschritt und einen Hersteller der linear ist in der eingabegröße und wir reduzieren dann auf Detailprobleme die und Faktor B kleiner sind bei den multiplikational Algorithmen war jeweils B = 2 und bei der schulmultiplikation war die gleich 4 und bei karats 3 und wir haben gesehen Unterschied machen hier ist das Bild dass das so ein bisschen charakterisiert ich habe Eingaben einer bestimmten Größe die blauen Pfeile geben jeweils an was für Kosten man hat um das zu transformieren in mehrere aufrufe dann werden die Aufrufe der Größe n durch B produziert die dann rekursiv jeweils wieder weiter aufgespalten werden und ich muss jetzt halt die die Zeit diese Zeit diese Zeit diese Zeiten alles auf addieren im Endeffekt und wie mache ich das und das Master Theorem das gibt es in einer deutlich allgemeineren Form ich möchte hier nur eine spezialisierte Form vorstellen die die Grundidee sozusagen gibt und die wir sehr einfach beweisen können also wir haben hier positive Konstanten a für den Basis Zahl B und D für den Teile und C für den lokalen berechnungsteil und was wir hier sehen ist C&A sind für die also politische Analyse eigentlich gar nicht wichtig sondern B&B und da gibt es drei Fälle wenn die kleiner Bier ist kriege ich lineare Zeit oder Lineal Wert für diese rekurrenz wenn die gleich B ist steht da ein Login und wenn die größer B ist steht da n hoch lockt zur Basis B von D und Ausführungszeiten dieser Form werden wir halt immer wieder in dieser Vorlesung sehen und die beruhen auf diesem Master Theorem oder kleinen Verallgemeinerungen davon so zumindest ein Spezialfall möchte ich jetzt beweisen und dann müssen wir natürlich eine Falle Unterscheidung machen nach diesen drei Fällen im Endeffekt ist das wichtig ist dass der Schlüssel das was ich hier als Bild dargestellt habe wir können ebenenweise summieren ja weil so wie die rekurrenz formuliert ist es auf einer bestimmten Ebene habe ich eine bestimmte Anzahl Teil Probleme einer bestimmten Größe und alle blauen Pfeile hier kosten gleich viel ja ich habe insbesondere auf der Ebene habe ich wie hoch i Teil Probleme der Größe n durch B hochi und entsprechend ist die sind die Gesamtkosten für die blauen Pfeile auf Ebene i die hochi mal C mal n durch B hochi das kann ich umschreiben als 10 mal n mal D durch B hochi ja also insbesondere mal n schon rausgezogen und daraus folgt dann auch schon fast dass das C also symptotisch gar nicht so wichtig ist und wir sehen außerdem schon das Verhältnis von D durch B ist ganz wichtig weil wenn die durch B kleiner eins ist dann kriegen wir hier eine geometrische Reihe bei der im Prinzip klar ist dass der erste Level bis auf konstante Faktoren alles dominiert wenn die größer B ist dann geht das hier exponentiell hoch mit i das heißt der letzte Level dominiert alles und wenn die durch die gleich eins ist also die gleich B dann steht die auf jedem Level zehn mal hin und alle Level sind gleich wichtig und ich habe Login Levels und dann kriege ich auch schon das Ergebnis gucken wir uns das mal etwas genauer an also Fall die kleiner B dann habe ich hier so ein geometrisches schrumpfen und eigentlich alles was zählt ist das hier und insbesondere kann ich das hier halt schreiben ich habe ein basisfall a mal die hoch K du musst natürlich auch berücksichtigen aber der ist das ist zum Beispiel für das kleinofen der Trick ist wenn wenn die kleiner B ist dann ist die hoch klar K gleich kleiner Ofen Ende und da ist eine konstante ja und dann steht da ansonsten zieh mal n habe ich rausgezogen und mal so eine gleich null bis kam -1 die durch B hochi das ist eine geometrische Summe die können sie geschlossen ausrechnen wenn sie wollen das ist dann eins durch 1 - die durch B oder sowas wenn sie gleich und endlich einsetzen und halten noch irgendwie was komplizierteres für Kamin eins aber der Trick ist das ist halt eine Funktion von D&B das ist einfach eine konstante wieder wir uns in der asymptotischen Analyse überhaupt nicht interessiert prima die gleich B ja in diesem Beispiel sieht man in jedem Level das gleich viel da also habe ich zehn mal n mal Lok zur Basis BN die Anzahl levels und in basisfälle a man das ist Täter in login hier habe ich eine rechenregel angewendet das U von N plus o von N Login ist wovon Login und das gleiche für Omega und schließlich Fall die größer gleich B da wird hier immer mehr das heißt ich kann hier einfach den das Abschätzen als Täter von hier den letzten term im Endeffekt und das kann ich aber jetzt umschreiben das ist Deo K genau ist dann auch mehr als die durch B hoch kam -1 das kann man sich auch vorstellen und das hier kann ich schreiben de hoch K als na ich schreibe dir als zwei hoch lockd dann steht da also zwei hoch K mal log.de das kann ich noch komplizierter schreiben als Karma Log B durch log-by mal lockd das ist einfach eine Eins hier ne und jetzt mache ich den Trick aha 2 hoch Log B ist B dann steht da plötzlich wie hoch K Lok B äh Log die durchlog B ist gerade ein Lok zur Basis die von DM und B Hochkar ist jetzt gerade wieder m das steht da n hochlog BD also ein bisschen Rechentricks aber eigentlich recht simpel so Beispiele machen wir nächstes mal vielen Dank