herzlich willkommen zurück zur einführen informatik teil 2 weiter führten programmierung mit java heute wird uns euro aber recht wenig interessieren wir haben heute ein sehr schwieriges thema sehr theoretisches thema vor uns was aber sehr sehr wichtig ist um überhaupt informatik grundlagen sage ich mal im programm ihr technischer grundkonzepte zu verstehen und die auch bewerten zu können und sie bewerten zu können wie gut ihr algorithmus ist wie gut eine lösung ist was sie überhaupt technisch realisieren können was überhaupt keinen sinn macht gut wir steigen also ein worum geht es denn überhaupt aufwand eines algorithmus wenn ich also eine klasse verschiedene algorithmen habe zum beispiel verschiedene suchverfahren oder verschiedene verfahren um irgendwelche daten zu berechnen was ist denn das beste na ja es gebe fragen wie was ist optimal ich hatte ihn ja massen sind das dann gesagt optimal ist kein allgemeiner aus thun optimal bezieht sich immer auf einen parameter und genau so ist wenn ich sage was ist denn hier der beste muss ich sagen ja was gehe ich denn überhaupt sind also bewertungskriterien werden natürlich ist unser fall primär wäre das speicherplatz oder rechenzeit also wie viele brauchen jetzt einfach um die aufgabe zu bewältigen oder wie viel zeit brauche ich auf meinem pc zum beispiel bei einer codierung von einem video oder um codierung ja das heißt hier mal aufgezeichnet wie kann ich das überhaupt auseinander klasse und aufwand eines programme speicher zeitaufwand beim speichern muss ich jetzt unterscheiden ist es bei mir der speicher bedarf für das programm selber der konstante saison dass meine ram nicht immer weiter wächst je länger mein programm läuft oder ist es eigentlich der speicher bitte auf der daten die reinkommen die irgendwo abgelegt werden müssen verrät ich also tatsächlich von der speicher komplexität wenn ich zehn millionen nutzerdaten vorarbeiten muss dann wird natürlich mein programm selber stabil bleiben am rand bedarf die daten muss ich auch natürlich irgendwo ablegen und je nachdem in welcher struktur ich die abschläge waren sie vielleicht unterschiedlich viel platz benötigt und da sprechen sie tatsächlich von speicher komplexität die in unserem fall jetzt hier linie aus eingabe wer je mehr ich personen meine datenbank und mein programm aufnehmen desto mehr spaß ich brauche nicht beim zeitaufwand ist denke ich klar je mehr ich solche datensätze verarbeiten muss mit ihrer datensatz stellen uns ein schleifer form die jungen wie handhaben muss die ich verarbeiten muss entsprechend brauche ich mehr zeit dass er die rechen komplexität gut dann werden sich auch sicherlich vorstellen können dass ein konkreter bedarf an speichern rechenzeit bei einem algorithmus erstes von der implementierung abhängt und zweitens sehr schlecht so exakt geführt werden kann wir brauchen auch in der informatik zwar schön qualitative aussagen aber die genauen aussagen die vieles und exakt ist es schwierig und die brauchen aber auch gar nicht also wer von uns sagt uns denn dass es wichtig ist ob ein programm jetzt 1,2 gigabyte ram benötigt oder 1,18 gigabyte ram wir brauchen knapp in gigabyte oder im bereich für einigen gigabyte ram das macht einen unterschied ob ich im programm habe was rund und megabyte ram braucht nur zehn megabyte ram oder und gigabit ja aber es macht keinen unterschied ob dort bei einem megabyte ein halbes megabyte mehr oder weniger das heißt solche qualitativen aussagen sind wichtig aber meistens nur die grössenordnungen abhängigkeit vom umfang und art der eingaben das heißt wir wollen wissen wenn wir die eingaben vergrößern erhöhen intensivieren wie verhält sich unser programm bezüglich speicher oder bezüglich berechenbarkeit in unserem falle primär natürlich die berechenbarkeit muss überhaupt mit sehr vielen eingaben ein programm lösen eine ergebnis ein sinnvolles ergebnis generieren ja und jetzt wollen wir uns vorstellen ist eine idee machen das ganze wie idealisiert also jetzt unsere computer heißen abstrakte maschine und wir sagen einfach zur einfachheit halber jeder operation auf dem computer braucht exakt die gleiche zeit 1 zeiteinheit und alle elemente datentypen jeder datensatz jedes jede information braucht auch den gleichen speicherplatz so da könnte was dran brauchen das ist so unpräzise macht aber im großen und ganzen keinen unterschied wird müssen eigentlich nicht exakt definieren wie viele mikrosekunden operationen auf dem 10 gebraucht wir sagen einfach in der groß kariertem welt mit vielen milliarden und billionen operationen spielt die null eine rolle auch und nicht ob eine operation 1,09 sekunden oder 1,19 sekunden brauchen das heißt wir brauchen dimension und das ist unser abstrakte computer mit dem rechnen wir mit dem denken die jetzt mal nächsten zeigt so und jetzt brauchen wir durch innovationen was für die berechnung relevant ist zum beispiel die elemente in unserer datenstruktur kommen welche daten rein und wir müssen wissen wie viel am ende hat es zum beispiel in unserem wie viele elemente sind enthalten die ich durch suchen muss wie viel schleifen durchläufe muss ich denn durch gehen um zu einem ergebnis zu kommen stichwortsuche für eine irgendwelchen informationen stichwort sortierung von herrn welchen daten wie oft muss ich eine schleife durchlauf und zum ergebnis gekommen das hat mich interessiert es nicht ob die schleife jetzt ja zwei mal irgendein zuweisungen hat oder dreimal oder viermal auch nicht interessiert mich die schleife selber einmal oder zehnmal oder bzw abhängigkeit von der eingabe einmal durchlaufen muss wenn ihm eine eingabe ist ja und mich interessiert hat sich die auto funktions aufrufe wie viele sind als entschuldigung die art ist schon relevant aber uns wesentlich die anzahl der funktions aufrufe von interesse wo wir uns selber mehrfach auf müssen wir eine statische funktion relativ häufig einbinden ist die auch noch abhängigkeit eingabe unterschiedlich häufig aufzurufen und gibt es irgendwelche bedingungen die rechnungen vereinfachungen die unsere laufzeit mitten drinnen plötzlich abkürzen das sind relevante informationen gut wir machen das kann zum einen einfachen beispielen das heißt ich möchte von ihnen wissen wir wollen die potenz von irgendwo zwei berechnen zb hier die zahlenbasis 3 und exponenten 132 nicht nächstes ergebnis haben und ich möchte von ihnen jetzt eine aussage haben wie aufwändig wird ein algorithmus sein und das für beliebige eingang zu berechnen das heißt meine basis ist beliebig ich kann ihnen nur drei sagen weil 419 und mein exponent ist auch nach hingehört das kann 132 sein es kann fünf sein das kann auch auf 50.000 sein und ich möchte von ihnen haben eine aussage haben sie schreiben einem rhythmus und sagen einfach wie aufwändig da ist und wie lange der brauchen wird ist der in einer ordentlichen zeit berechenbar und wie verhält er sich wenn meine eingabe also sprich ein exponent oder meine basis immer größer wird diese aussage müssen sie jetzt informatiker treffen können sie ihnen würden ihren programm und sie müsse sagen wird das programm zunehmend langsamer mit immer größeren eingaben bleibt es konstant in seiner berechnung oder wie verhält es sich so ein primitiver im rhythmus und ich jetzt einfach sagen ich mache es immer wieder schleifen durch läufe und mit jeder schleife reduziere ich meinen exponenten um 1 und rechne sozusagen mein bisheriges ergebnis mal die basis also ich fange an 332 ist das gleiche wie drei mal drei hoch 131 das heißt ich habe 3 x 3 gerechnet und habe den exponenten um 1 reduziert damit habe ich meine einfach ein womit muss dann kommt zu einer lösung und er hat eine bestimmte anzahl operationen dieser operation habe ich jetzt hier mal aufgeschrieben die müssen wir uns gerade ins detail angucken das ist bei einer telefonischen bisschen nervig was wir aber auch sehen können aber es vielleicht wichtig ist wir haben hier unten in den tatsächlichen aufwenden ein konstante zahl sechs und einmal unsere in unserer eingaben wir sehen also den prozent die potenz zur basis b mit dem exponenten ende auch noch einmal dargestellt und bei der ganzen berechnung nach diesem algorithmus habe ich also einmal 6n solche durchläufer um irgendwo auf ergebnis zu kommen das heißt mein aufwand für diese funktion ist linear zur eingabe ist meinem ein exponent sehen wo sie sozusagen die schleife zehn mal durchlaufen ist mein exponent 100 muss ich meine schleife 100 durchlaufen dh sie größer meine exponent also mein enden diese fallen hier oben wird das teufel muss ich diese schleife durchlaufen und entsprechend wird der aufwand eines programm ist größer wir sprechen hier also von einer linearen abhängigkeit warum weil wenn ich diese operation hier betrachten und mein ändern immer größer kann ich sorgen die sechs operation werde die zehen operation in den geheimen operationen die kann ich vor nachlesen die spielen keine rolle mehr genauso wollen die sechs ob wir eine 6 steht ohne sie besteht macht für uns alle zwar schon gefühlt spielt es keine rolle ob man sie uns überlegt ob das jetzt bei einer million oder bei einer milliarde das wird zwar mehr aber es bleibt linie abhängig zur eingabe deswegen sechs vernachlässigung sprachwitz das heißt hier wir haben uns einen rhythmus linear zeigen glaube wir haben einen lineare komplexität jetzt kann man es auch vielleicht noch ein bisschen schlauer gibt es noch in besseren algorithmus was macht denn der nicht zum beispiel war habe zwei 1856 habe ich also mein b2 und meinen wenn ich an der b 8 das wäre das gleiche wie die basis 4 zum exponenten firma und die basis 16 zum exponenten 2 sprich tschi mir immer das kann sie 102 x 24 x 4 entsprechend mache die basis hören und mein exponent wird immer wieder halbiert das heißt ich nehme immer die punkte das bisherige die bisherige potenz ist musik potenz mal die basis und dann entsprechend nehme ich mir meine entschuldigung die basis ist die basis mal die basis und mein exponent wird immer halbiert was ist ergebnis ja ganz einfach ich muss halt nicht größer meint wird diese schleife einmal durchlaufen ein exponent sind viel schneller mainschleife ab wird viel schneller erfolgen wie viel schneller publizieren wir die berechnungen an nun auch hier wieder mein impotenz iks aus der basis und den exponenten ende kommt noch meine berechnungen raus und wenn nicht das kannst du jetzt hier mal rum berechnen möchte jetzt hier mal die ganze an der tafel assmanns mal weg kommen wir zum ergebnis dass jetzt unsere schleifer höchstens lockt zum basis 2+ einmal durchlaufen und für große m kann ich dieses plus 1 ebenso wären und ich sage ich habe jetzt einen maximal logarithmischen aufwand warum wenn mein ansteigt und ich muss ja um einen entweder immer halbiert und plötzlich wird meine eingabe um 1 mehr dann habe ich auch gar nicht mehr berechnungs schritte weil hier trotzdem ohne halbieren da fällt es einfach mal weg deswegen ist jetzt dieser bessere algorithmus nicht mehr von linearen komplexen und in die a liga aufwand sondern von einem logarithmischen aufwand die uhr zu den zahlen gekommen dass ein bisschen mathematik das kann man sich schenken wichtig ist aber durch die halbierung des schleifen durchlaufs oder durch die halbierung des exponenten bei jedem schleifen durchlauf brauche ich deutlich weniger schleifen wohl weisen dem ersten algorithmus und ich komme auch eine logarithmische laufzeit viele von ihnen werden sich relativ schwer tun mit dem logarithmisch deswegen möchte ich auf den noch mal zurückkommen müssen auf jeden für ein gutes gefühl für den werden sogar it muss sagen dass ich im ersten semester schon mal fragen eingegangen logarithmisch kommen in der schule grenzwertig vor was sollte aber auch verstehen was damit gemeint ist das mache ich die folie hermann komplett ran und wir sehen ihren rechten bereich unsere exponential funktion ist eine ganz eklige steil ansteigend haben wir mittendrin linear funktion so gerade hieraus ein lob muss um wir sehen schon unser logo rhytmus ist bei 1 sozusagen durchquert er die y achse und dann ist das für uns informatiker sehr schön weil wenn das unsere eingabe es uns einfach immer mehr und diese kurve immer flach so was macht denn jetzt unser algorithmus ich würde vorschlagen stellen sich den algorithmus vor wie viel sind zustände mit einer bestimmten zahl oder mit einer bestimmten größe und einwohnerzahl baustellen können dagegen dass man dezimalsystem an selben uns vor dezimalsystem ist also die zehner basis da bei allen berechnungen 10 hoch 0 ist immer eins da kann ich also ein zustand darstellen 10 hoch 1 ist also eine 10 kann ich 10 zu stellen auch entspricht mit zwei solchen ziffern mit den exponenten mit dem exponenten 1 habe ich sozusagen die 0 1 habe ich zehn zustände 10 hoch 2 habe ich erst jetzt 100 zustände die c02 ist also die 00 bis zu 99 wenn ich jetzt 100 asten zustand haben möchte brauche ich eine dezimalstelle mehr dann bin ich hier unten habe ich also 10 hoch 3 dh mit 1000 zuständen kann ich die dezimalzahlen 0 bis 999 darstellen und schauen was wir vorne mal in loco rhytmus dazu an der rhythmus von einst zur basis 10 ist 0 haben wir genau das was hier oben ist der rhythmus von 10 21 10 11 das heißt wie viel stellen brauche ich und 10 zu stellen zu können eine stelle eine dezimalstelle nämlich von 0 bis 9 wie viele stellen brauche ich um 100 zustände darstellen zu können zwei nämlich von 0 0 bis zu 99 wie viele dezimalstellen brauche ich um 1000 zustände darstellen zu können drei von der 000 bis zur neuen dahin ein system verstanden gehen wir jetzt ein hohes binärsystem dort haben wir immer nur die basis immer nur zwei zuständig ist sozusagen unser unser jeweiliges mit darstellen kann ihre genauso 20 ist ein zustand körper nur ein zustand darstellen gibt es nichts ist hoch 1 in zwei zustände nämlich 0 und 12 sind vier zuständen das heißt 242 kann ich also von 0 0 bis 11 4 zustellbar stellen so hoch drei und so weiter und so fort gehen wir daher vor genau umgedreht wie viele stellen brauche ich im binärsystem zur basis wo also um einen zustand darzustellen 0 kann ich einfach machen einen statischen zustand wie viel stellen brauche ich im binärsystem was du brauchst dazu um zwei zustände darstellen zu können genau eine stelle nämlich nur den einst unserem bild kann zwei zustände haben wie viele schiffe oder wie viele ja wie viele elemente brauche ich um 8 zustände darstellen zu können ich brauche drei stellen nämlich von 0.00 bis zu 111 um diese acht zustellt ausstellen zu können hexadezimal den ausgleich analog dazu wie viele elemente oder wie viele stellen brauche ich um 4096 zu stellen zu können im hexadezimal system also bis 16.3 nämlich von 600 bis fff damit sollte zumindest schon mal das verständnis darstellen dass der chor it muss sagt man nichts weiter aus wie viele stellen ich brauche in meinem jeweiligen zahlensystem und eine bestimmte anzahl von zuständen darzustellen ja nehmen uns also mal die zahl sieben im dezimalsystem oder nehmen wir die zahl 7 im binärsystem 7 ist texas binär ausgedrückt die 111 das sind drei stellen von null bis zu sieben passt habe ich jetzt eine nacht zustand reichen mir meine drei bits nicht mehr aus um diese achten zustande zu kriegen das heißt ich muss mit dem achten bitte eine oder mit deren züchter entschuldigung mit der zahl acht eine neue stelle einführen um diese zahl repräsentieren zu können eine vierter stelle deswegen alles was sozusagen jetzt größer ist als dieser 8 wird mit 3,8 das heißt ich brauche mehr als drei stellen und meinen zustände ausdrücken zu können das ganze hat sich jetzt wieder annähern von der drei hier bis zu 416 zustände also von der null bis zu 15 darstellen zu können brauche ich vier stellen das heißt bei der logarithmisch von 16 ich schon mal bis zu 512 kommt hier das 4 aus sobald ich wieder ein mehr habe habe ich wieder 4,0 gend was das heißt ich brauche mehr als 4 also und ich auf zu 5 da wird man sehr einfach ganz einfach mehr wie viele zustände kann ich entsprechende anzahl von stellen mein jeweiligen 2 system reinpacken das sollten sich merken sollten sie verstanden haben und natürlich die aussage dass hier wir sehen schon die x-achse unsere spiegelung unserer logarithmisch spiegelt sich zur funktion hier an dieser achse in dieser funktion nix damit ist schon sehr viel gewonnen aber das ganze mal an einem zweiten konkreten beispiel nehmen wir uns mal trafen er also ein baum wien ersucht werden ja auch super müssen sehr die linken elemente von der wurzel sind immer kleiner als element die rechten indem es jetzt mal die tiefe des baumes wie viele knoten ja so ein baum reingepackt kommen also informatiker bauen der wechsel soll nach unten dass unsere muskeln unser eigenes element das heißt unsere ebene 0 kriegen wir ein element rein unser element kann zwei knoten haben diese elemente können wieder kinder knoten haben und so weiter und sofort gucken uns jetzt die ebenen ankommt genau wieder unseren rhythmus zu tragen unsere tiefe ist null die informatik die kinder waren zu zählen ein knoten 1 ist auch kleiner als 2 das klar in der ersten ebene kriegen nur drei knoten rund um die drei ist auch in der präsentation kleiner vier weise von 0 bis zur nächsten ebene kriege ich wieder vier knoten dazu tiefe 2007 knoten oder auch weniger als 8 sehen sie das genau das gleiche auch unser vorgehen folie haben oder nächsten ebenen tiefe 30 123 kriegen wir insgesamt 15 knoten oder oder aber auch weniger als 16 sobald den 16 knoten haben möchte muss ich eine neue ebene aufmachen so merke also die tiefe des baumes ist logarithmisch abhängig zur menge der knoten im baum das heißt wenn ich von hier oben absteigen möchte zu einem beliebigen punkt zu kommen ist mein schlimmster fall logarithmische aufwand zur eingabe wenn ich jetzt die 15 von den nöten und zu einem beliebigen knoten zu kommen ich brauche also wenn ich irgendwas trainersuche nicht mehr außer dieser wenigen abfragen um einen beliebigen punkt in diesen bauern zukommen ja die suche nach einem knoten dem baum ist mit nach maximal locken integration abgeschlossen geben sie diese einzelnen elementen die zahlen und sie werden danach suchen müssen eben auch die kleineren zahlen sind immer links vom von dem jeweiligen kunden die größeren 20 rechts davon egal was suchen sie müssen immer mehr bis zur eingabe anfragen stellen um zum ergebnis zu kommen auch hier wieder eine element mehr ich brauche eine komplett neue ebene dann kann ich diese kompletten der ebene voll fühlen auch bis dahin ist es nur eine ebene mehr die ganze reihe kann ich voll machen und habe nur eine abfrage mehr als einem beliebigen ergebnis zu kommen so einfach ist das ganze gut zurück zu unserer komplexität für die komplexität und die formal zu fassen wurde die sogenannte operation eingeführt so ist eine landauer konstant lande aus symbolen landau notation so hieß der typ der das damals eingeführt hat und das wachstum von funktionen der mathematik geschrieben hat auch jeder da ist viel zeug das man dort haben machen müssten wir machen es auch mal jetzt relativ kompakt wir sagen einfach wir haben eine mathematische funktion und wir müssen diese mathematische funktion grob abschätzen wie komplex die ist und das group machen zu können sagen wir einfach es gibt eine andere funktion die sind irgendwann ordner gleichen komplexität aber meine einwilligung zu lösen möchte wird niemals mehr zeit benötigen als diese referenz funktion das heißt meine funktion gehe gehe von ändern so irgendeine funktion von eingabe abhängig ist in ähnlicher komplexität wie eine referenz funktion f von n und meine funktion aber niemals steigen steiler ansteigen als diese grenze funktionen dhg von hendrix proportional niemals schneller als diese grenze funktion f warum kann man also sagen dass sozusagen diese gehen von ende funktionen in element ist von der rotation von f von ender schreiben aber einfach vereinfacht das geht von n gleich die station oder die lambda notation land auf innovation von f von ändert kling ist alles wieder sehr komplex wir machen uns auch gleich einem beispiel das hier ist in unserer funktion die uns in vorder komplexität betrachtung hat für uns interessant sind dass man eine konstante wir hatten beim letzten vorlesungen kooperation unserer random access fall konstanter zugriff auf beliebige elemente 1 ob nur diese konstante bei 113 bei 20 oder bei 10.000 ist uns eine komplexität betrachtung egal weil sie ist immer gleich und egal wie groß unsere eingaben werden sie ist gleich haben wir uns unsere anderen sachen angucken verändern die sich unsere konstante ist ihr waagerecht drin ernährung weil die konstante ganz weit oben keine ahnung bei 10.000 da erscheint die uns riesig hoch wären wir auch unser ende entsprechend groß zum beispiel eine million oder 10.000 skalierung genauso wie ort zu finden das heißt in relation zu diesen anderen komplexität ist unsere konstant immer ideal ja sodann habe jetzt schon alle anderen funktionen sind nicht konstant sind abhängig von der hingabe spricht sie verändern ihren wert in abhängigkeit was für eine eingabe größen einkommen das heißt macht ein unterschied ob ich eine zehnerpotenz ausrichten oder eine potenz mit experimenten ausrechnen möchte oder impotenz mit den exponenten eine million das heißt diese eine million als and eingabe fließt immer mit ein so und hier sehen wir schon logarithmisch ist immer schön wir unser abflachende kurve die größe unserer ende dass der weniger eine rolle spielen wir brauchen beide millionen kann man von einer million bis 9,9 millionen kann man alles mit einer ziffer abdecken erst bei zehn millionen brauchen wir eine ziffer mehr das ist sozusagen als wunderbar haben hier wurzel ändern es hier unsere lineare eingabe die sich relativ steil haus ist aber das format immer noch schön je mehr wir all die größe und unsere eingabe wegen das bemerkt steigt unser aufwand auch an aber nur sehr planbaren geraten form so jetzt hier um was schon kritisch wir sehen schon einmal unsere login fließt noch mit 1 aber der multiplikator vorne dran spitzen entscheidende rolle sprich wir gehen ja schon ganz schön steil bergauf noch krasser wird sozusagen wenn man hier quadratischen aufwand haben ein quadrat wie stein das kann sie ihre musik bei größeren zahl kam noch dass sie eine tragende kurve dran ist und dann exponential geschichten zu hochegger steht also unser exponenten ja wir reden ja nicht von der eingabe also nicht wie bei unserer potenz thema ausgerechnet haben wir mal sagen wollen 332 ausrechnen sondern wir reden vom aufwand da ist also die 132 wer bei unserer potenz der lineare auffallen müssen also 132 mal die schleife durchlaufen hier wäre der aufwand 232 und das macht einen riesenunterschied das heißt diese sachen hier vorne sind für uns der albtraum quartal zwar schon richtig schlimm aus auch was ich ändern drei entwurf vier alles mögliche kann alles ist alles schon schlimm aber im vergleich zu diesen hier es ist dafür der eintracht so nach oben springt dass man innerhalb von kleinsten springen hier in der eingabe schon massive zuwächse laufzeit haben kommen spielt noch mal dazu so nochmal die asse tote komplexität das ist hier noch einmal kompakt dargestellt das heißt also das ist unsere funktion irgendeine funktion die darstellt wie unsere aufwand wächst in abhängigkeit von der eingabe und es gibt auch irgendwie grenz funktion das ist unsere f von n die liegt irgendwo drin und unsere eigene funktion wird niemals steil ansteigen als dieser die ordination gibt offensichtlich eine obere schranke zur laufzeit eines algorithmus die selbst im ungünstigsten falle nicht überschritten und das heißt unser grüne linie ist unsere grenzlinie oder untergehen kann ja alles mögliche machen aber die wird niemals steine ansteigen also unser f das waren wir uns merken das muss hängen bleiben und das muss man auch anwenden können verschiedenen beispielen so und jetzt muss man noch sagen es macht einen unterschied ob ich zb bei sony bei so einer funktion hier das jetzt irgendwas quadratisches ob ich da jetzt sage ich ein faktor davor also 1,123 das macht in diesem kleinen tier schon eine wichtige wichtigen unterschied im große skalieren wenn ich entsprechend richtig groß werden wird auch dieser fakt oder vernachlässigbar klein zeit verlassen auch weg das kommt jetzt hier auch nochmal das heißt wir haben irgendeine konstante kann die forum so ohne dazu entsteht zum beispiel brauchen wir bei dem schleifen durchlauf in abhängigkeit von der eingabe dreimal and das heißt wir müssen eine eingabe von enden müssen wir unsere schleifen dreimal so häufig durch laufen also bei zehn bis dreißig mal durchlaufen 200 - 300 mal verlaufen das heißt unser n ist ein faktor der trainer und der restliche faktor ist sozusagen um sowas hatte ich gesagt unsere drei davor und das ist unser kann das spielt aber bei großen endzone vernachlässigbaren dass es einem weglassen können das heißt kam mal irgendwas wird einfach reduziert auf nur diese lineare funktion und nur diese funktion fnn habe ich jetzt zwei solche mutationen ich mit multipliziere multipliziere ich die sachen hier in der fhm und hafen ist dasselbe die uhr von fmh haben das ist stellen sie sich vor sie müssen einschlagen more durchlauf unter anderem auch durch laufen dann ist der gesamtaufwand halt ma lin ja so dass heißt konstante faktoren spielen keine rolle mehr komplexität und mehrere in abhängigkeit der eingabe sich ändernde faktoren werden miteinander entsprechend multipliziert oder entsprechend zusammengefügt so bei den summen börse aus summiert werden zwei schachteln schleife ist natürlich eine multiplikation und der höchster faktor spielt eine rolle wenn ich jetzt hier zwei zusammen auch hier habe ich eine linie habe also wenn ich jetzt hier eine lineare hat in den jahren bleibt es eine lineare wenn ich hier eine quadratische augen quadratische laufzeitende also wie m ² und havel mbh zehn jahre funktion dann fällt das bei großen hinweg dann stellen sie sich vor sie haben eine eingabe von dem milliarde die milliarde zum quadrat spielt die überproportional viel wichtigere rolle als diese milliarde als einzelwert nach hinten tragen deswegen lass ich's einfach weg gut das heißt einfache anweisungen geben zum normalen algorithmus wir wollen unsere potenz berechnungen und auch was machen einfache zuweisungen einfacher operationen wo ich einfach irgendwas machen muss der woche ordnet definieren wo ich auseinander abziehen muss final einmal ist alles konstante lauf zeigen alles laufzeit komplexität offen 1 landau notation vereins spielt sozusagen von nachrichten sprache wurde sequenzen also nacheinander ausführungen mehrere grund operation abhängigkeit von n die dann einfach nacheinander weg geschrieben und dann werden sie einfach miteinander vereint und ich nehmen wir das maximum davon ich habe alle möglichen geschichten mal was den jahr erstmal was logarithmische was quadratisches die einfach nacheinander aufgeführt habe acht nacheinander nicht geschaffte ja dann nehme ich mir das größte davon alles andere kann ich vernachlässigen wenn ich eine logarithmische eingabe eine funktion hat die logarithmische eingabe ist eine lineare ein quadratischer die nacheinander ausgeführt werden kann ich mir meinen großen eingaben das logarithmische oder senioren die tasche stecken das macht keine rolle mehr sondern nur das quadratische und rüschen schleifen sind ja wieder richtig wichtig hier müssen wir aufpassen einschleifen durchläuft entsprechend ab unter eingabe in malen also wir schleifen körper eine kommunität von ufern fnm durchlaufen so kann die gesamte schleife einmal irgendetwas zugeordnet werden wenn ich ihnen das schleife noch nicht schleife habe dann muss ich das ganze multiplizieren wenn ich also in abhängigkeit von der eingabe eine schleife habe und in der schleife kommt nochmal eine schleife wo ich in abhängigkeit von der eingabe größe das ganze buch sprechen musste habe ich einmal in heimischen quadratische laufzeit gut und auswahlkriterien und sagen wir auch ich betrachten wir das maximum hier sollte ich mal genau hinschauen dann wenn sozusagen eine apu kriterien relativ häufig auftaucht dann ist es natürlich schon wichtig für die laufzeit des algorithmus um allgemein sagen auch für die laufzeit betrachtungen für die ansage unsere funktion des worst case betrachtung das heißt unser algorithmus wird immer weniger zeit verbraucht eine bestimmte komplexität klasse und deswegen nehmen wir uns bei gift denn erst bedingungen auch immer nur den porträts der einfach am meisten ins gewicht fällt und hier sind die komplexität klassen die sich später dann auch mal praktisch in der klausur aufgabe und ein praktikum zu wenig später auch berufsleben einsetzen müssen das heißt sie müssen wissen wenn sie irgendwas programmiert haben ob das einen konstanten aufwand hat weil es vollkommen unabhängig von der eingabe ist beispielsweise schauen sie [Musik] fest dass logfile an und gucken einfach nur das lokal ist so es wird immer konstanter aufwand seien vollkommen unabhängig wie groß dieses lock frei ist sie prüfen nur ob es das oder nicht das ist eine attraktion und selbst wenn es jetzt noch drei zuweisungen machen würden irgendwelche konsolen ausgaben auf basis dieser entscheidung treffen müssen es bleibt ein konstanter aufwand er ist unabhängig von der eingabe ja noch offen aber quatsch ihm gesagt binärer super willkommen spielen noch dazu das heißt eine eingabe fließt schon mit den aufwand rein aber noch wird mischling aufwand ist das was für sie wahrscheinlich am einfachsten ist wenn ich einfach eine schleife habe die genauso auf durchlaufen werden muss oder mit dem faktor wie meine eingabe ist dann habe ich in den jahren aufwand beispielsweise was man gesagt haben wir zähe schleife sie sollen sie geben war der eingabe 1 10.000 dann müssen sehr von der null bis zu 10.000 alle arbeiter ausgaben auf der konsole machen und von hunderttausenden müssen seien 500.000 machen dann müssen sie für jede generation das ganze einmal durchgehen sie haben einen linearen aufwand dann kommen wir noch entlocken das ist doch mal ein schöner komponist wir haben das später bei dort ihr verfahren noch als eine sehr sehr gute lösung haben das ist so ja immer dass zwischen dem quadratischen aufwand das heißt hier muss ich schon einige schachteln der schleife durch laub auch das wird uns bei den suchverfahren und entschuldigung sortierbar vor noch betrachten kubischer aufwand beispielsweise drei schachteln schleifen dieser ändern da haben und dann die ganz böse sachen alles was exponentielle auf wände sind das heißt hier steht unser in unsere eingabe nicht mehr wunderbar zum exponenten wie die basler sind es uns völlig egal so bald wieder eine exponentielle unsere eingabe oben exponenten haben wird es so komplex dass es mit normalen aufwenden mit normalen rechnet systemen für große eingaben kaum noch realisierbar ist gut algorithmen mit höchstens grüne premium neuen aufwand gelten für größere probleme als durchführbar das heißt stellen sich sehr sehr große nv dann sagen wir alles das was in dem projekt um auszudrücken dass politik kennen sie noch aus der unterstufe 2 ist also eine verkettung von verschiedenen thermen wo jeweils fester feste exponenten im mit enthalten sind und die eingabe immer nur unten an der basis zum beispiel ein hoch 3 + 2 in quadrath plus vier und plus 1 wir haben politik das sind aufwände die in der informatik als durchführbar die exponenten sind statisch wir können das berechnen der aufwand ist verkraftbar es ist gut lösbar bei höherem spezielle exponentiellen aufwand gelten sie für größere probleme als undurchführbar sobald sie also irgendwas entdecken wo sie an ihrem algorithmus teams implementieren so einen exponentiellen aufwand hamburg diesen diese eingabe im exponenten stehen haben könnte das ganze eigentlich für große karriere probleme vergessen sie können so etwas kleines zu hause machen sie können das kann sie aber nicht für große eingaben ja nutzbringend einsetzen weil war der schnellste rechner den sie haben immer noch viel zu langsam sein muss gut und das ganze mal greifen zu können habe ich das ganze mal ja beispielhaft gemacht wir haben also hier oben eine eingabe also m sind unserer heim kam noch manchmal gesagt haben wir beispiele unseren potenz berechnungen haben wir jetzt hier hoch zwei hoch 16 256.000 24 minuten und jetzt haben wir hier unsere komplexitätsgrad nicht vorhatten o von locarno von nn locken im quadrat also quadratische laufzeit kubische laufzeit und dann hier exponentiell laufzeit zuerst gucken wir mal die viele operationen hierfür benötigen wir sehen schon hier eine operation vier operationen hin sind nutzt waren sich operationen sehen also wie schön unser logo rhytmus ist weiß welchen großen eingaben linie sieht auch noch gut aus und das kann sie hingeht das zu sagen hast du viel kraft brauchen grünes licht bei quadratisch habe ich jetzt hier schon zehn hoch 12 das ist eine ganze menge operation die hier durchführen muss eindruck drei auch und 10 hoch 18 und das dauert eine richtige menge setzt mit vielen vielen millionen operationen pro sekunde so und sobald ich auch hier exponentielle laufzeit kommen ist das extreme ganz schön braun mal auf dem blatt papier schreiben so und jetzt kann mal geben wir ein ganz schritt weiter ist unsere stellen normal dass jeder von diesen operationen das ist eine anzahl hier oben von operationen dass jeder diese operation nur eine mikrosekunde auf irgend einer laufzeitumgebung auf irgendeinen mikrocontroller mcu brauchen würde jetzt gucken was machen die lange die zeit frau wie viel zeit wir brauchen wir entsprechende problem zu lösen weil dort gerade einmal 20 mikrosekunden bei händlern eine sekunde 21 sekunden die zwölf tage dies sind auch schon richtig lange bei selbstloser monopoly aller zeiten also nur ein ende auch drei hätten wir schon viele viele tausend jahre und bei exponentiell laufzeit körpers selbst hier vorne beim kleinen einige komische niemand darstellen bei der unterschied von android 3.2 ende ist da immer hier schon gut sichtbaren von 16 7 sekunden was jeder von uns ohne probleme machen kann man hier schon bei 3 x 10 63 jahren so heftig steigt das an das heißt mit keinem rechnung der welt können sie das jetzt noch rechnen selbst quantencomputer können zwar vier gleichzeitig machen aber bestimmt dimensionen und auch schwierig gut die komplexität einer problemklasse bremste aufwand aber algorithmen die das konkrete problem der klasse lösen kann versuchen also irgendwas was das effizient berechnen kann jetzt gibt es für sein problem mannschaft zum beispiel und sortierung von zahlen ja weil sie nach eingabe von bestimmte menge von zahlen soll diese zahlen sortieren und für dieses problem klasse des sortiments gibt es unterschiedliche verfahren und wir suchen natürlich den algorithmus mit dem geringsten aufwand um eine komplette komplette das problem ohne probleme klasse zu lesen das semester haben algorithmus löst mit problemklasse unsere problemklasse dass die sortierung von natürlichen zahlen die eingabe ist variabel und wir müssen jetzt halt verschiedene algorithmen implementieren die das gut oder schlecht können so und jetzt haben wir aber hier ein problem klasse die sortierung für den natürlichen zahlen und das wird der komplexität und wir werden das in problem aller zeiten lösen können das problem und alles was in solchen politischen zeiten lösbar ist fassen wir zusammen als ein problem klasse p ja so dass unsere politik allzeit algorithmen oder politiker sarah bleiben rhythmus der klasse p besonders schöne formalismus in die sich jetzt einfach mal eine vorlesung raum vor ein problem wird ein kurzer zeit löst burgenland wenn es von einem algorithmus gelöst wird das benötigte rechenzeit höchstes polio nell mit und größe oder eingaben des problems wächst ja das heißt unsere quadratische laufzeit ist 2m entschuldigung quadrat und der laufzeit und das ist natürlich ein politikum und damit ist es in der klasse p so das heißt alles wo wir in unserem exponenten von unserer laufzeit hier ein cover eine konstante stehen haben die konstante kann größer gleich eins sein wenn sie kleiner als 10 dann wäre es eine konstante zweiter wäre es keine polizei kein problem mehr aber sobald wir sozusagen ein eine konstante größe gleich eins drin steht haben wir einen polynorm hier auslösen können achtung erst wenn das ändert die eingabe ihrer exponenten kommen wir eine exponentielle oder nicht primär auf zeit beispiel habe ich mal aufgeführt suchen von daten sortieren von daten solche probleme geht natürlich vor als durchführbar ist auch gut so weil sonst ein richtiges problem der informatik jetzt auch viele probleme die wir nicht in polen lösen können und wo es nur durch sinnvolles tester durch erfahrungen weitergeht sich alle daran dass vielleicht kennen hier an der hochschule zum beispiel unsere stundenplanung das heißt wenn sie die ganzen seminargruppen haben die ganze studiengängen und sie müssen die räume plane wann welche vorlesungen stattfinden kann dieses problem ist so komplex dass es nicht automatisiert vor dem computer in polen nominal zu ein lösbares man kann in noch sehr schnell zeiten prüfen ob eine lösung gültig ist oder nicht aber von der eingabe ich jetzt einfach mal alle meine seminare minister und lasse mir einen plan erstellen das ist nicht in brühl nominal zeit lösbar genauso wie das rundreise problem travelling salesman problem der eine oben und haben vielleicht von ihnen schon mal gehört das heißt ich soll über eine landkarte hinweg eine bestimmte anzahl von orten bereisen oder einen computer oder ein programm sollen wir rausfinden was die perfekte route ist um möglichst wenig sprit zu verbrauchen oder möglichst schnell alle orte auf dieser karte die wahllos verteilt sind ab sofort auch dieses problem ist nicht in polygamie allzeit lösbar und das optimum zu finden man kriegt in polen derzeit eine lösung man kann aber nicht in grünem neue zeit die perfekte idealen lösung ja genauso wie produktionen fertigungsplanung geschichten oder das netzwerk problem kommt alles jedenfalls noch in den eindrücken der daten strukturen vorlesungen das sind alles probleme die nicht in pro jahr zahlen lösbar sind so gut und derartige probleme ist dass bei dieser dimension noch heute erkenntnis fragwürdig ob es exakt algorithmen gibt die das ganze berechnen wahrscheinlich nicht zu aber wir haben praktisch aus wegen des richtigen was ist neu ristic touristik ist eine möglichkeit um mit begrenzten wissen also nicht den vollständigen mit nur begrenzten zeit setze ich mir auch hat bestimmte vorgaben ein bestimmtes ergebnis erzielen was mit einer bestimmten wahrscheinlichkeit das optimum annähernd dh ich könnte mit den aktuellen informationen über den dax und mit nur einer stunde zeit wird er wie jetzt ins internet gucken würde mir alle möglichen formation zusammenziehen und würde ihnen ein ergebnis liefern wie sich der dax morgen entwickelt wird so weil sie die börsen positionen nicht das tier und diese das ergebnis wird mit einer bestimmten wahrscheinlichkeit zutreffend sein und wird mit einer bestimmten annäherungs quote ans optimum herangeführt das option wäre wenn ich exakt den börsenkurs morgen um 16 uhr definieren könnte kann ich aber nicht aber ich kann sagen dass bestimmte rahmen faktoren hatte indizien dafür sind dass am boden nach oben und nach unten geht in der heutigen volatilen zeit ist es natürlich tatsächlich glasbläserei aber und normalen zeiten könnte man das so und dann hätte ich also immer einmal lustig eine 80 prozentiger wahrscheinlichkeit serbien und zielkorridor befinde und das mit einem sehr begrenzten wissen und noch sehr sehr kurzen zeit das heißt ich nutze gar nicht sonst wie viel aufwand um irgendwelche exakten ergebnisse zu berechnen sondern ich nehme diese kurze zeit und versuchen der kosten zeiten möglichst gute annäherung an die ideale lösung zu finden so sagen wir jetzt hier zurückgezogen auch unser problem ihr könnt also nehrung lösungen entwickeln die sozusagen in polen die mahlzeit zu dem sehr guten ergebnis kommen und jetzt aber nicht ihre theoretischen formaten genannt ist auch gar nicht weiter beleuchten das geht es hier deutlich zu weit gibt nämlich die klasse n p das sind also die nicht pro junior lösbaren problemstellungen für all diejenigen algorithmen die in polen jahr zeit entscheiden können ob ein lösungsvorschlag tatsächliche lösung ist also achtung solche mp algorithmen finden nicht die ideallösung politi minar zeit auch sie können in polonia zeit prüfen ob lösungsvorschlag tatsächliche gültige lösung ist zum beispiel ob ich bestimmte europa bestücken planung ob alle bedingungen erfüllt sind alles konfliktfrei funktioniert oder beim trading statement problem ob ich sozusagen alle punkte abgefahren habe oder was vergessen zu haben oder unterhalb einer bestimmten spritverbrauch meine ganz viele abgefahren zu haben das kann in polen derzeit prüfen aber wie ich sozusagen diese ganzen punkt auf der landkarte verbinde das muss ich erst mal zufällig zeuge zufällig entscheiden und dann kann ich in so einem mp algorithmus in poley neonazi überprüfen ob es eine gültige lösung ist das smp also nicht lösung des problems nur prüfung ob ein problem entsprechend in prien mahlzeit und stelle auch in polen problem gelöst wurde also für android probleme kann eine mögliche lösung kurs codiert oder getestet werden und dann herauszufinden ob diese lösung projekte oder nicht gibt also nein antwort so dass natürlich auch die mp nicht deterministisch problem lösbar so die frage oder bisher sagt man es gilt dass die pferde die polizeit also wird man den teil menge sind für diese np geschichte und ob sie aber gleich das aktuell in die forschungsfrage theoretisch matic wenn sie das lösen können dann kriegen sie den nobelpreis für naturwissenschaften informatik das wird aber noch sehr lange dauern und wahrscheinlich nicht so einfach lösbares problem seien gut hier noch heute visualisierung also die npd vollständigen geschichte nochmal eine aufteilung von dnp von einem problem klasse np vollständig also für die klasse der probleme die sich nicht er mir die nicht die termin ist im portfolio der zeit lösen lassen das ist tatsächlich was wo ich also sage ich weiß nicht nicht zum ziel kommen aber ich kann nur sagen mit dem pseudo zufall zu einer lösung kommen und dann gibt es noch die mp schweren probleme die überhaupt nicht lösbar sind dann gibt es also einfach keine lösung hier nochmal die visualisierung das müsste aber ebenfalls noch mal vor wir machen das macht jetzt hier wenigstens gut nochmal für die eigenen rhythmen oder für die klassen 1 gewinnt mit einem rhythmen kennt also bezüglich ihrer laufzeit komplexität durchführbarkeit in zwei oder drei klassen unterteilt werden nämlich die polymeren und die exponentiellen also natürlich der laufzeit gewisse exponentiell beschränkte probleme sind nur dann bush für morgen lösungsvorschlag zufällig aufgestellt werden kann und die sodann in polen derzeit überprüft wird richtig und ein solches vorgehen das problem heißt entscheiden also die unterschiede der und die unterscheidung auch im kopf zwischen lösbar und scheinbar kann ich eine ideallösung berechnen oder kann ich entscheiden ob eine gültige oder eine gute lösung gefunden wurde so es gibt dabei algorithmen die für identische eingaben verschiedene resultate liefern und da kommt also tatsächlich den zufall komponente mit drei also richtiger zu fallen damit sind sie entsprechen nicht mehr den determiniert und lassen sich auch nicht mehr durch eine funktion beschreiben sondern vermitteln nur noch eine zuordnung zwischen einen ausgemacht dass wieder der theorie behaftet hier kann ich nicht mehr sagen die zur in der ergebnisse komponist ich kann nur sagen es gibt bestimmte sorgen ich habe irgendwie eingabe rhein geworfen und habe irgendeine ausgabe rausbekommen dazwischen ist ein großes fragezeichen und das wird nur durch eine zufalls komponente gespeist die ich nicht beeinflussen kann das heißt ich kann das ergebnis nicht reproduzierbar wieder bekomme ich kann auch dieses ist gut damit sollte auch an der stelle genug sein für sie ist wichtig dass sie die komplexität klasse in der rotation oder landet aktion kennen das heißt gucken sich verschiedene algorithmen an und entscheiden sie ob sie in jahre quadratische kugelte laufzeit haben ob sie überhaupt noch im frühjahr zu einbrechen aussehen oder ob sie die exponentielle laufzeit haben und lernen sie bitte auch zu hause was dann der wind muss ist und was eine logarithmische laufzeit ist verstehen sie bitte den zusammenhang zwischen zustands raum und 0 grad muss und sich sozusagen mit einer logarithmischen erlaubt hätte nach sich haben könnte den rest machen oder an später ich hoffe dann auch warum ihm praktisch an diversen beispielen in dem reich der sortierung da nämlich für der aufmerksamkeit viele grüße