Merken

Ganzzahlige Polyeder: Zulässige Mengen

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
ich Pop rohe ja müssen musste
so herzlich willkommen zur heutigen Vorlesung er eine kurze Ankündigung vorne weg und zwar die Übung vom Patrick Schmidt wäre man diese Übung muss sie leider eine Stunde nach hinten verschieben weil sie wird künftig dienstags von 15 Uhr 30 bis 16 30 statt wenig Entschuldigung die Sprechstunde nicht Übung seine Sprechstunde ok also Dienstag 15 Uhr 30 bis 16 30 in Raum 4 4 4 3 mal die 4 ok sonst organisatorische habe ich nichts denn aus meiner Sicht können wir gleich inhaltlich einsteigen werden das letzte Mal sozusagen dann damit geendet dass über die Früchte gehandelt haben die immer alles sozusagen aus der vor dem Ausgehen Elimination uns gearbeitet haben sprich wir wissen affine Transformation vom Poledance wieder Polyeder wir wissen jetzt auch die die doppelte Darstellung wurde die zweifache Darstellung einmal als äußere Beschreibung einmal ist in der Beschreibung also Politiker sehen genau dadurch charakterisiert dass sie sich zum 1 Politwoops und eines politischen Kiedis sind wobei Politwoops sich immer darstellen ist als konvexe Hülle endlich wieder Punkte und politische gegen immer als chronische Kombination endlich viele Punkte an das haben als Darstellung Satz bezeichnet und die beide die zweierlei Sichtweisen wie wär es spielen immer wieder eine Rolle auch in Optimierung später in den Verfahren und auch in den theoretischen Resultaten damit aber sozusagen diesen Grundlagen der Bolide Theorie das letzte Mal abgeschlossen und steigen jetzt einen haben das letzte mal damit angefangen zu sozusagen das Lösen ganzzahlige Programme und haben damit begonnen uns erst mal anzugucken was sind denn sozusagen leichte Fälle leichte fehlen "anführungszeichen in dem Sinn dass wenn man dieses X aus Z n weglässt und dafür nix aus aber auch Englisch schreibt also sich die Galaxie um die sogenannte Pedelecs Jung anschaut man hat man denn dann Glück also in dem Sinn dass wenn ich über das der Galaxie und optimiert das sich dann automatisch ganz Bedingungen bekommen und das letzte mal angefangen und das 1. was uns überlegt haben sind solche Geschichten wenn ich mir die zulässigen Punkte anschaue sich haben Politiker und ich beschränke mich auf die ganzzahligen .punkt innerhalb eines Politikers sich bestimmt die konvexe Hülle daraus konnte dann wiederum aus das in das letzte Mal geblieben am Beispiel wo man schon gewisse Schwierigkeiten gesehen haben dass das im Allgemeinen nicht zustimmen aber was letzte Mal dabei das herauszuarbeiten wurden da der Wurm steckt sozusagen gibt es aber bis dahin zu dem was das letzte Mal gemacht haben es auf das Beispiel noch Rückfragen nicht der Fall gut würde ich sagen steigen wir nochmal in dieses Beispiel 1 ich schreibt es dann noch mal hin uns geht es jetzt auch noch mal grob also wir haben folgendes Problem uns angeschaut maximiere was läuft 2 x -minus was 2 x +plus y unter der Nebenbedingung -minus Wurzel 2 x +plus y kleiner gleich 0 x sollte größer gleich 1 sein y größer gleich 0 und beide ganzzahlig das war unser Problem so wenn wir uns das gerade schon mal anschauen hier steckt praktisch wenn hier gleich setzen würden die Geradengleichung drin y gleich muss für 2 X es geht Größenordnung wenn ich das einigermaßen richtig zeichne zeigen will ungefähr mit so einer Steigerung und wir haben uns angeguckt alles was da drunter liegt sagt diese Bedingungen dann aber alles war das y größer gleich 0 sagt diese Bedingungen Hammer noch x größer gleich 1 das heißt es war diese Bedingung war also das ist das Polyeder was wir uns anschauen und darin aber das letzte Mal die ganzzahligen Punkte markiert ich immer nur ein paar ein so in der Art wenn das in das letzte Mal stecken geblieben und die Frage war welche konvexe Hülle bilden kommt da wieder und Politiker aus allen hat sich das sie hat sich dazu ihre Gedanken gemacht also wir dürfen auch nicht nur kommerzielle kann auch chronisch kombinieren was passiert denn dann der nehmen wir an wir würden den Versuch machen ein Ansatz können der sein zu sagen denn in dem einfach alle blaue Punkte und will die konvexe Hülle machen was ist an dem Argument falsch immer gesagt konvexe Nationalheld
Poli Eigenschaft also man Polyeder n nahe das unendlich viele nehmen haben also und das immer sind scheinbar Politiker ja immer es geht immer um endlich Mengen endlich Durchschnitt endlich vieler Bräune konvexe will endlich viele Punkte und chronische Kombination endlich viele Punkte das heißt wir dürfen als konvex Kombination nicht alle nehmen wenn wir alle nehmen dürften hätten das natürlich an die konvexe Hülle aller blauen Punkt ist natürlich das Objekt was aber was wir wollen nur das sind unendlich viele und damit kommen keine politische Struktur mehr heraus und das heißt wir müssen uns irgendwie endlich viele herausgreifen und wenn wir uns das mal und gucken egal jetzt seine Augen einer Zeichnung erstmal egal was man sitzt herausgreifen müssen ein irdener Stelle misst in der diese Punkte hier die man dann immer näher an die Sie gerade auf der Geraden selber Legende wie auf der Geraden selber Punkte gerade selber liegen keinen ich aber hier stehen y =ist gleich Wurzel 2 x angenommen da würden ganzer gepunktet liegen dann hätt ich wusste zwar sehr rationale Zahl dargestellt wäre also auf der der gesamten geraden kommt keine ganzzahlige .punkt ja so und jetzt hab ich genau das Problem wenn ich auch im egal wo ich jetzt hier meine können konventionellen Operation anwende immer hier als Beispiel waren es muss ich noch ein chronischen Kegel dran nehmen aber ich komme nie an die gerade das heißt wenn hier oben wieder irgendwo ein ganzzahliger .punkt kommt und um den mitzunehmen kriege ich hier sozusagen gerade die irgendwann diese gerade schneiden damit nicht den zulässigen Bereich abdeckt dar beziehungsweise umgekehrt wenn ich wenn ich in dieser Richtung laufen würde dann völlig irgendwann ganz sein .punkt bei die größte ich X und Y wilde Gänse vielleicht aus der Approximation mal keiner wußte 2 beliebigen nahe doch das der rationale Zahl approximieren das heißt doch in X und Y es ehrlich Kombi aber an diese gerade an aber ich komme nie genau dann das heißt wenn immer ich vorher irgendwo Schluss machen meine in meinem Endlichkeit Argument aus dem kommen mir nichts anders übrig als es das sich von dort weg wenn strahlt definiert der aber einen steileren Winkel zum Bild gesprochen als diese gerade damit würden sich irgendwann schneiden und damit wir dich nicht den .punkt aber ok also das ist es geometrisch und man kann sie auch algebraisch sich anschauen nahm war wurde dieser Spruch her kommt also die eine Aussage die wir haben ist sicherlich was wir sehen dann muss dieses Programm hier anschauen das ist sicherlich nach oben beschränkt explizit da steht die Zielfunktion Tiefen zwischen das Nebenbedingung also dieses Problem ist nach oben beschränkt es nie gibt immer nahm im Skript heißt es 2 1 2 1 ist nach oben das nächste was wir wissen es es hat auch zulässige Lösung sehen ob es in der Zeitung Vecernje x gleich 1 es ungleich 0 zum Beispiel einsetzen also hat er hat zulässige Lösungen und Liste der was man hat keine optimale Lösung er war während der optimale Lösung hätte wären dann würden wir hier die 2 also nationale Zahl darstellen können also hat keine optimale Lösung während da Wurzel 2 nicht National Aids so und damit haben schon zusammen immer der setzt er muss das überlegen wir haben nach oben beschränkt unzulässige Brunnen angenommen wir wir hätten wieder das werden pro Lieder also wir schauen uns an angenommen maximiere -minus Wurzel 2 x +plus y und der X aus S ja wir machen jetzt die konvexe Hülle Operation X aus konnte es hören dann wüssten wir das ist schon in Ordnung aber wenn dessen pro Leder wär angenommen dass werden Polyeder er dann müssten wir sozusagen optimale Lösungen werden immer angenommen und werden
auch immer angenommen und werden in eine optimale Ecke angenommen dann wissen nach oben beschränkt die Funktion des darum beschränkt konvexe Hülle Operation bis wir wohl jeder Winsen Politiker ist es nach oben beschränkt wird die Funktion in einer optimalen Ecke angenommen angenommen Polyeder daraus würde folgen sozusagen es existiert und optimale Endlösung des es nur noch aus der Einführung und das ist sehen Widerspruch um so also wir müssen aufpassen wenn man jetzt sozusagen uns
erstmal beliebige Umlagensystem erlauben und einfach sagen konvexe Hülle Operation müssen immer aufpassen dass man der endlichen Welt bleiben kann so und liegt die Crux an dieser Stelle ist eigentlich nur diese Wurzel 2 aber mit diesem was zu 2 argumentiert ja letztendlich was hier steht sobald er ganz ganze Zahlen erlauben und in der Form sozusagen kann man manchmal aufpoliert darstellen dass wir schaffen seine ganzen Zahl auch jede Art von Brüchen darzustellen ja wir schaffen es eben nicht irrationale Funktionen zum Beispiel zu approximieren soll sobald eine rationale Zahl aus schließen ist die Welt in Ordnung ja und das ist das was wir uns jetzt anschauen wollen und wenn man dann diese Polyeder speziell auch rationale Polyeder weil sozusagen die nur aus rationalen Daten entstehen und das ist die nächste Definition 2 2 1 ein Polyeder zu ok außen Hochenheimer ist rational falls es aber aus dem Kuchen Kreuz N und P was und Co hoch n gibt mit wir gleich IAB und entsprechend natürlich beschreiben es nicht extra in heißt es natürlich auch wenn das National ist dann wissen auch dass alle Ecken rational sind weil nichts anders als der Durchschnitt von allen dieserhalb räumen müsse auf Gleichheit setzen ja mich hier nur nationale Daten nach unten Gleichungssystem löse dann kommen die und rationale Daten raus und genauso das heißt alle Ecken ist 10 damit auch oder rational oder aus Kuh und genauso gilt natürlich für die chronischen Kombination die sich ergeben aus dem gleichen Umgang System als kleiner gleich 0 also deswegen extra hin aber wenn wir die an Darstellung von von grauen Forbes kaum E impliziert das natürlich das gleiche für Frauen diese das er soll noch eine weitere Bezeichnung meiner so zeigen jetzt künftig mit und liebt er mit ganzzahligen ihren arbeiten wollen oder so P I kleinen P bezeichnet folgende Menge die konvexe Hülle alle x aus P mit XLS aus Auszeit Rucht P Kreuze ein hoch N -minus P des genau wie unser ganz Tagesprogramm X aus B heißt der er AX letztendlich als kleiner gleich B und hier stecken die Ganzheitlichkeit Forderungen würden wobei Display andeuten soll dass wir die Variable was so sortieren dass die 1. die davon die Ganzheitlichkeit Forderung haben ja und wir schreiben auch als Kurzform P E definieren wenn mal einfach als PIN das heißt wenn nicht vor dass alle Variablen ganzzahlig sind ja dann für diesen unter Index hier nicht mehr mit anschauen einfach nur P I und so was man bislang eben nicht wissen und das wollen jetzt zeigen wenn es Polyeder P rationales ist dieses Ding auch wieder ein Politiker er und dieses Beispiel hier zeigt wenn wir diese Forderung nicht haben das dann die IP ist zwar definiert aber es kein Politiker gut also das schauen uns mal an so ist ist um kann ist mit der Stange holen gut also dass es in der nächsten Bemerkungen Beobachtung oder Beobachtung 2 3 der 1. Beobachtung ist SPD beschränkt dann folgt das PEI ein Pol Eder ist die 2. Bemerkung ist Sven die rationaler Rolle Kegel dann folgt das P gleich an so beide Aussagen sind eigentlich einfach warum die die 2. offensichtlich kann also wenn ich in nationalen politischen Kegel habe er dann das was sozusagen jedes unserer gegen das Korn E da is rationale kommt aus irgend einer hoch Kreuz N ja warum ist dann sozusagen das man Politiker ist und ich schaue mir ich schaue mir das PEI an warum kommt er dasselbe aus also dass das offensichtlich dass P die muss offensichtlich mitteilen er sei von dem für definiert haben es die konvexe Alex aus Bremen der zusätzlichen Eigenschaft nein das heißt wie sicherlich Teilmenge von P Wankel auch die Umkehrung also wenn wäre eine müsste hier sozusagen das für das PEI so kleine aus also wenn dann nicht mehr das PEI anschauen müsse vielleicht irgendwie so aus kann es das sein was das eben also das kann nur sein wenn auf der auf dieser Geraden zum Beispiel nichts liegt nichts keine Anzeige .punkt liegen denn auf dieser Geraden keine ganzzahliger .punkt anders
basieren also hier diese diese Vektor wir haben ja auch immer der VI der Sausgruber auch n so was tun dann machen wir das mit den positiven Skala multiplizieren kommt dann irgendwann da oben wenn ich weit genug Joe Lauf über die Decke hinaus im nächsten Stock kommt dann irgendwann ganzzahliger .punkt oder nicht es kommt einer wenn es aber nur mit allen Männern doch multiplizieren man Mulde beziehen einfallen absolut Beträgen aller Länder durch dann bleiben wir also Produkte von ganzen Zahlen stehen sind offensichtlich ganze Zahlen und damit kommt hier irgendwo ganzzahliger .punkt wird und das heißt das hab ich hier falsch gezeichnet während dieser Strahl nicht aber den ganz Eigentum nicht vergessen der tatsächlich hier ja und der auch also deswegen von rational auf ganzzahliges der Weg nicht zu weit denn wir können das heißt je nachdem die weil weg definieren mag aber zumindest kann man immer der Skalierung des Problem aus nationalen zum ganzzahligen machen eskalieren einfach alle rationalen Zahlen und durch doch alle Männer und dann über ganze Zahlen stehen also inzwischen so erst mal von der Theorie her praktische das anders auf einer Theorie Tag müssen wir einig diese Fälle unterscheiden kann gut also dass die eine Eigenschaft das war dann der BVL was ist mit dem Abfall ja haben wir schon argumentiert also wenn das P beschränkt ist ja das heißt wenn P beschränkt ja dann folgt so sagen dass die Menge aller X aus der doch allen mit X aus ist endlich um also beschränkt heise kann ich Box bauen und um das wieder rum sodass das also P komplett in dieser Box liegt dann enorme ich schau ich mal .punkt an diesem der Anzeigenkunden der Boxlegende sind offensichtlich endlich ja und damit habe ich diese Eigenschaft die ich brauchen dann ist ja auch der konvexe Hülle Operator anwendbar konvexe Hülle von endlich vielen Punkten habe ich hier also daraus folgt das Grund von diesen Konstrukt ist und Polyeder ja das haben einen Satz von weil wir diesen end konvexe will auch endlich viele Punkte gibt und Politiker so dieses Argument gilt auch für rationale Funktion ja also das Leiden als beide Bemerkungen 2 4 1. Bemerkung 2 3 aber gilt auch für nicht rationale tolle inne nicht zu verwechseln mit dem Beispiel oben das Pol Eder was wo man es nicht beschränkt aber die Zielfunktion ist beschränkt ja also da man das Argument weil die Zielfunktion argumentiert aber lieber dass Politiker an sich war wir hier oben oder mit noch mehr Boxen gemacht hätten X kleiner gleich 3 Millionen oder so dann hätten wieder argumentieren können ja und dann ist alles wieder wohldefiniert gewesene kommerzielle Obertor machen können wenn man optimales und außerdem können die aber nicht die Funktionen er nicht zu sagen die rationaler eine die irrationale so Funktion oder Zahl Wurzel 2 approximiert und nur auf wie diese Genauigkeit die Genauigkeit hieß sozusagen wenn ich den Männern bis auf 3 Tausend beschränkt so das 2. was ich auch anmerken will dass es gilt diese Aussagen gelten alle auch für auch für diesen gemischten Fall gut so was wir jetzt geerntet gerne hätten ist dass diese Aussage um diesen konvexen Hülle operabel werde ich wie man das da tat sich ein rauskommen und da ist mir jetzt aufgefallen für diejenigen die sich das alte es gibt es 2006 anschauen im nächsten Satz kommt sowas vor Rezession Sky gehen denn man aus der Einführung noch nicht kennen weil der 3 genau weggelassen worden es deswegen weil ich dort ist in kleinen Exkurs Außenwelt Sessions Kegel und vielleicht auch eine der Eigenschaft kurz beweisen wir uns dann hilft sozusagen den beweist immer dann eingehen wollen also kleiner Exkurs ich geht den Drahtzieher Nummer 1 ich nun jetzt einfach mal wird aber ARD und so weiter also Definitionen wir sind ja gerade bei 2 3 nicht dass es 2 3 a also sei es eine beliebige Teilmenge des auch allen dann wahr ist weg von S ich ist die Menge aller y aus einer hoch n mit der Eigenschaft ist existierten X aus S für das x +plus Lander y ist aus es für alle Landauer größer gleich 0 heißt Rezession Sky was er Mehr als Rezession Skelette von es an also was steht hier Preise schauen uns alle y an sodass wenn ich wenn ich im zulässigen .punkt haben X und denk eskaliert ich jetzt beliebig ja für alle Lande größer gleich 0 und Adidas drauf dann bleibe ich in der
Menge wenn das sieht man schon an dieser Eigenschaft dass ich genau das ist es was man dem auch haben einen Mehr als wenn Polyeder den Besitz allgemeine Menge es aber hier Politikern denkt dann ist da ist's ja eigentlich genau die Elemente die aus dem Korn stecken warnt Cohen Frau kon i denken wir müssen da genau die diejenigen drinstecken Kron heißt da ich nehme ein X aus dem kommt vor und es existierten aus dem Grund Frau Ort und jetzt kann ich bloß heißt kann beliebig viele nicht negative Zahl auf diese Elemente aus grauen erlaube deren bleibt drin also es scheine intuitiv zu sein dass für Polly Edelbert Sessions geht egal dieses Krone is er in den ist auch tatsächlich so mehr ich kann ich nicht ja wird ja da also schon auf einen kleinen Satz in Satz 2 3 D in den Polyeder ist er mit n WDR ich BAB gleichkommt V Pluskom E ja dann Enkeln Rezession von P =ist gleich P a 0 es gleich E vor aber das ist nur ein der war ist immer hier in der einst mit 2 die 2 zweimal meine Übung was dieses Gleichheitszeichen gilt schauen Übung an und wir schauen uns das an das 1. an also in 1. Eigenschaft während dieses enthalten zeigen also wir nehmen uns ein aus 2 y aus aber es aus direkt von P er für das heißt es existiert was folgt es existierten X mit der Eigenschaft dass x +plus an der y Element P für alle Lander größer gleich 0 ja das heißt nicht dass es übersetzt in die Sprache das heißt am Alex +plus Landammann y Sport also ist man so von x +plus Lander y ist ja nichts anderes als a x +plus Lande A Y muss kleiner gleich sein für alle Lander größer gleich 0 das heißt es ja so angenommen hier gibt es eine Komponente die ich größer 0 ist angenommen das existiert im war sozusagen mit A Y sein weg der die Dekade Komponente ist echt größer 0 wenn es immer schon dass es schief läuft der und werden einfach das Langener als die in die entsprechende wir können wir das dann also wenn es Positives können es dann das so groß werden dass a x +plus Land als dann über das B hinausgeht und das waren das ist tot es ist folgende wenn im Landtag definieren wir alles B e -minus XDK Komponente fallendes durch auf A Y Dekade Komponenten addieren einfach 1 drauf nur so mit dem ohne die +plus 1 Crime genau Gleichheit in der Komponente aber das einfach einsetzen hier das Land aber meiner diese eine Komponente anschauen wenn wir genau das BKA des AX K fliegt weg kürzlich gegen das raus das als Loncar kürzlich hier draußen denn dann bleibt genau das BKA stehen und im Lande 1 übergeben nicht übernehmen also das heißt es folgt also x +plus Landtag wäre y ist größer als P und dass ein Widerspruch gute andere Richtung ist wir es einfacher oder genauso einfach also wir nehmen uns y aus oder aus wir und wir schauen uns an 2 x aus P und Landa größer gleich 0 beliebig während der war einfach ein A von X +plus y ist sicherlich gleich a x +plus an der A Y als 1 kleiner gleich 0 per Definition als ist das Landesgröße größer gleich 0 also es kleiner gleich A X X war zulässig als ist kleiner gleich PIN ja und das Wort nach Definition unsere Rezession Slide stehen ja wir habens und x so dass x +plus Landestrainer immerhin in dem poli Eder ist für alle Lande größer gleich 0 daraus folgt auch y ist in der
Rezession Skelette von entgehen können jetzt da Fragen dazu also man hat eigentlich
wie gesagt diese interessante Sichtweise auf wenn bezüglich der inneren Darstellung und was wenig interessant ist wenn man so möchte ich ja mal den letzte Stunde diesen Satz geraten ist immer bis zum Außenpolitk hob unpolitischen Kegel her wie dieses letzte sonst Kegel heißt ja vergessen Kegel vor jeder Fall ist auch einen politischer Kegel wir kennen wir diesen wolle er diesen Wert Sessions Kegel wenn hier stets sehr kennen in der ein darstellen sowie offensichtlich kommt Forbes grauen II und den anderen Darstellungen das Alter in dem die rechte Seite auf 0 setzt also alle Sektoren als kleiner gleich 0 wir also auch in anderen darstellen erkennen wir leicht erst mal wie wo was sozusagen Äxte mal Stahlwerk liegen hier im Wasser die explizit hier müssen wir noch was rechnen wir also immer wirklich die strahlend kriegen wollen diese hier muss noch unendlich geht hier habe man nur die Beschreibung über Ungleichung Systeme werden noch nicht explizit Direktor und also das heißt hier müssen wir in die Oper gehen wie immer Ecken bestimmen wollen also sowas machen wie früher Mods gehen oder ähnliches gut also weit vielleicht alles der Exkurs dazu so jetzt immer in der Lage in den wenn wir uns also wieder finden wir den Satz den Mai beweisen wollen uns anzugucken ist der Satz 2 5 also seit P nationales dann folgt die ist ebenfalls rationales Polle Eder und Rezession Skelette von P ist der gleiche wieder zur tionskette von PI und dem ganzzahligen Pole wir beides das Ding ist abgehakt nur warum was nix zu beweisen um und das ist das was wir gerade schon diskutiert haben wir stets doch der Ort 2 3 also legt P Rezession Skelette von per 1. politische Kennedy wer hier steht das Kegel wir wir steht das nationale Polyeder habe nationaler politischer gegen wir besteht p =ist gleich P I also das heißt wir man die Hamas auch nochmal explizit immer hier schauen regt P es über kon i beschreiben wie Sie es sind alle rational und wenn man jetzt im Marstall rational sind kommt auch irgendwann nach der eine Skalierung auf diesen Strahlen ganzzahlige .punkt das heißt die Sie es denn im Wert von P sind müssen auch in dem von weg von PI Design und um ja also der Fall es ist offensichtlich da und wir müssen ein bisschen bisschen arbeiten also das 1. was mir das mal wissen das ist es was mir das letzte Mal gezeigt haben dass P lässt sich sicherlich darstellen in der Form ja das ist ein Pulli tobt das den dessen politischer Kette und wir eben gerade argumentiert haben sie lässt sich schreiben alles kommt kaum Entschuldigung grauenvollen von gewissen YES die gleich 1 bis oder Zahl S wobei y e eine ganzzahlige Vektoren sind nur so was wir jetzt machen es wie wie ,komma auf zu der Aussage des Mehr sind kleinen Trick und ankommt was als Trick wir können nicht einfach was es intuitiv wäre ja ja wir nehmen einfach zu sagen wie sie das ganzzahlige Polyeder dazu aus wenn einfach von den PC setzen um den Index dran ja dann wissen wir dass es das gleiche wie das C das aber gerade diskutiert besetzt albernes Q und den Index tja es Probleme wenn das klappt nicht ganz wir schauen uns gleich an wurde der oh ja er also es geht da schief anschauen muss um Polyeder an hier typische so typisches Standard Polyeder so und was ist wenn wir jetzt aber ich nur es wäre das ist der eine Punkt der immer mal wieder die ganz zeigen .punkt irgendwie so dahin wo und so weiter und hier auch noch eine so dass wenn unsere ganz eigene Punkte zuletzt wenn wir uns und was wir unser Kuhn was wir unser C wir unser Korea das Kusel erstmal konvexe Hülle der Ecken sondern es das würde das ist der Cosco und Frau also unser Faust in die Ecken es wäre dieses Tal in nein das wäre unser Ecken von dem Projekt P also wenn wir konvexe viel davon nehmen wir das oh ok so was wäre unser Koch und Ideen also das dass wir unsere Ko und das C wäre das nun also das ist unser unser C ich wir das doch mal also der unter und also normales ist Sitz der natürlich jene also hier sagen dass ist unser Kegel das ist unser C sowas was wird zwar Sätze intuitiv nahe ist zu sagen dass uns anschauen PI wer gleich Guy das E
war was geht da schief was ist also CE wissen wir das ist geschenkt als Garage reiben oder auch nicht weisen politischer Ggs ist aber was mit dem GUI was wäre in dem Fall des Kuli das müssen wir machen einfach alle ganz seien .punkt in den blauen angucken wir alle ganz sollen .punkt in dem blauen aber keinen 3. Frage also hier es ja wir mixen will Operation machen immer genau diesen Bereich Mehr also dass es kommt voran Guy nur sondern wird schon das Problem ich jetzt einfach das ist sehr darauf an wie er dann fällig .punkt denen wir jetzt einmal dieses sehr war der und wir völlig ganzzahlige Punkte an also ganz so einfach geht es nicht also einfach sonst an auch sozusagen den sind interessant zu sehen dieses ab Intel dranhängen also macht mir aus dem Poli der BIP unter das konformer gar aber schon so definierten also dass unser eine konvexe Hülle schon dabei also ich kann nicht ich kann nicht einfach ich Summe von 2 polieren hab gar nicht einfach wenn ich jetzt die dann sagen .punkt 1 ein Bolide anschau konvexe Hülle machte jedem Politiker Arlands entsteht bis zum ist überträgt sich nicht auf die zum Operationen ja diese ganz Calls dort wo wir müssen ein bisschen aufpassen müssen allzu stark aufpassen da nicht was man nur garantieren müssen wir müssen wir müssen aufpassen dass wir diese Punkte einsammeln ja das hier keine Punkte verlorengehen und wie kann man das sicherstellen dass hier keine Punkte verlorengehen Inhalt halt nicht nur das Blau ist sondern dem einmal den gelben dazu 1 gelbe der Name so so skaliert dass der ganzzahlige ist dass es an dieser Stelle an mein Bild passen den ganz normalen bisschen länger an an dieser Stelle tauchte wieder ein ganzzahliger .punkt auf soll das heißt ab bis dahin muss sich die Ihnen frei sich ab dem ganz ein .punkt eingefangen und wir hier ab da alles drauf er dir gar nix mehr passieren weil sich aber alle in diesem Zwischenbereich auch mit dabei und es auch keine Probleme einmal den brauche den Kandidaten minimal auch endlich wer den blauen plus einmal die den chronischen drauf hat dir bleib ich immer noch im ähnlichen Fall kann konvexe will oder ob anwenden und Krieg wieder Politiker sollen das genau das was wir machen es für so dass wir nur noch nachrechnen das ist auch tatsächlich so stimmt also wir schauen unser B an das ist genau der Bereich der mir zu nehmen das ist die Summe allein nie y e i gleich 1 bis S und wir erlauben als Skalare sozusagen nur zwischen 0 und 1 also maximal den 1 dazu für die gleich 1 bis S sollen jetzt die Behauptung ist die folgende E gleich oh +plus b und davon dass ihr größtes Ziel ja wenn wir das gezeigt haben dann Hamas geworden weil das bin jetzt endlich konvexe Hülle auf dem ist in Ordnung gibt wieder Pole jeder von denen wissen wir schon dass der ganze Rezession Stil von ganz zeigen gleicht dem vom vom rationalen ist also Madame genau die aus sagen wir wollen ja Addition 1 Politwoops mit einem politischen kegelt dann muss das PEI ein Politiker sein gut also machen uns auf den Weg das zu zeigen sie eine Richtung also sei im P aus diesem P E ganzzahlig wir wissen wenn es Pläne dem es sicherlich auch in den P das heißt es gibt ne Darstellung der Form p =ist gleich gut +plus c mit Kunden aus im groß Q und dem C ausdehnen kleinste und die Darstellung gibt sicherlich für dieses C selber keinen kennen eine Darstellung der vom Summe Menü y e i gleich 1 bis S hinwies 10 größer gleich 0 so Nester legen wir dieses erst in den Anteil der in den Weg legt und Plänen der drüber hinaus ragt also das heißt definieren ein C strich gleich Summe man sie abgerundet y e i gleich 1 bis es und wir definieren als B vielleicht 10 -minus C stetig an so ist es mir folgendes das C strich es ganzzahlig warum gibt es denn es war ein ganzzahliges ist abgerundet also ist kommt ja das ganzzahliges ist auch eine ganze Zahl damit liege insgesamt ne ganze Zahl und damit ist auch das gut +plus wir das es mal aufschreiben nix anderes als éliminés eine Chance Sommerabend p =ist gleich Q +plus 10 sch Marcel B und bestätigt also haben wir die Beziehungen zur von den von dem P wissen wir das ist ganz von C Zielstrich bis wir dass es ganz sei also ist das auch ganz ehrlich gut +plus b ist ganz allein da so und was mir auch noch wissen ist das P in den B ist in dem groß besonders ergab definiert bei SBS in genau alles gerade die zwischen 0 und 1 liegen SPD schlug genau sozusagen in dem gebrochenen Anteil diese Nüs und damit und daraus folgt das Q +plus b ist enthalten in dem groß +plus ganz Einigkeit drauf angewandt Cubes bis ganz zeige und ist im Gum P also in den ganzzahligen Teiler von und daraus folgt wenn man das jetzt wie Display anschauen die definieren hier stets nochmal wir ausschreiben SQ +plus b +plus c strich ja und das ist damit Element Kobes B daraus und das C strich ist sicherlich auch aus dem C das ein andere Skalierung hier also diese Eigenschaft nachgewiesen werden so die andere Richtung also das können wir direkt nachweisen wir schauen uns Coup +plus b er +plus das C das ist
sicherlich enthalten Q +plus b is halt P also haben Beziehung P PI los C ja das ist sozusagen aufgrund dieser enthalten sein schafft Grundriss Besen P enthalten dann bis wir an der Stelle aufgrund der Bemerkungen über gemacht haben also an der Stelle einfach ne dran machen können ja und damit bis wir da das C ist auch Teilmenge von NP damit können wir an der Stelle das ihn nach außen ziehen einmal Folgendes und das ist nichts anderes als schön und sehr natürlich hier CDs Teilmenge von NP also ist es gleich DE gut an damit damit haben wir sozusagen diese Eigenschaft nachgewiesen hier oben steht sie noch einmal also wenn ich ein nationales Polyeder aber ich habe den die konvexe Hülle alle ganz .punkt an die da drin sind oder alle ganz eigene Punkte darin dann beschreibt es wieder Politiker das ganz wichtig auch nach wenn wir allgemein ganzer lösen wollen wer damit unterscheiden wir uns doch diesen Zusatz verbissener mein System haben minimiert oder maximiert c't iX und als kleiner gleich B es nehme die Ganzheitlichkeit beginnende 2 X aus der Druck B dann weiß ich wieder dass die zulässige Menge um die es sich handelt beschreibt wiederum Polyeder also das ist sozusagen das was uns jetzt hierher geleitet haben das heißt wenn es nochmal im Rückblick und überlegen das heißt sie zulässige Menge auch wenig X aus der doch das ändert ja doch wieder zu schreiben ist wieder ein Politiker das heißt wir haben eine lineare Zielfunktion überm polieren optimieren so genial zieren Polly optimieren es eigentlich lineare Programmierung nein so das heißt letztendlich eine ganzzahlige Programme in dem dass auf theoretische an sich erstmal zurückgeführt wirklich auf lineare Programme waren und geniale Programme sind polynomial lösbar zusammen Einführung kennen gelernt das heißt einzig ist der Weg geht mit sozusagen aus einem kleiner sehen den einzig schweren Problemen auf dem ein Probleme die Schwierigkeit ist nur diese Transformation tat sich in zugeht aber wissen Sie gibt es da das ist das was mir jetzt hier sozusagen nachgewiesen es gibt tatsächlich die Transformation die 1. das war auf das was man eigentlich tun müssen ist wie finde ich dieses Politiker und wie kann ich das möglichst gut beschreiben bricht das schafft dann bin ich ein in der Welt die ich schon kenne und in der Welt ich auch gut verstanden hat und der Welt in der es auch wirklich sehr gute und effiziente Verfahren dazu gibt so das ganz sah das da trotzdem noch ein schwieriger Schritt dazwischen ist es wollen uns das anschauen wenn ich das ganzzahlige Programme selber gehören leider nicht oder bis lange nicht du den polynomial lösbaren Problem obwohl jetzt sozusagen eher von theoretischer sei uns dann Weg geebnet hat wir also das charmante 10 Folgen an er wer also wir wollen ja mal zu malen ich habe schon mal nachgefragt sozusagen auch wieder der Begriff NP-vollständige oder endlich Weltbild des Wurmes an der Stelle auch nochmal mit kurz wiederholen weil das Ziel bei jetzt zu zeigen dass ganz eigen Programme an sich zu der Klasse der endlich schweren Problemen gehöre ja und linearen Programme die wissen wir aus der einführen gehören zu den Polen lösbaren also da ist sozusagen das aus der theoretischen sich so im Graben in dem man dann letztendlich schauen müssen wie man den algorithmisch schließen oder wenn überhaupt schließen können aber zumindest konzeptionell wird hier wieder einmal gesagt immer ungefähr in der gleichen Welt nur wenn ums algorithmisch Jungs lösen geht sind das ist eben nicht und das schauen und schauen uns im Folgenden an bevor ich diese Definition NP-vollständige bringt leider möglich die Eigenschaft die wir dann auch brauchen nachzuweisen dass es aber an ein bevorstehendes Problem ist es nämlich sagt gleich nochmal groben Worten was es betreut die formale Definition bringt also voll Sticks wenigstens sind solche Probleme bei den ich aber als mal die Ziehung Entscheidungsprobleme Jahr also nehmen unser Beispiel ich haben ganz Tagesprogramm A X kleiner gleich BX aus der doch allen nicht nur entscheidend gibt es den zulässigen .punkt ja oder nein was Entscheidungsproblem sind solche muss nur die Antwort ja oder nein gibt in dem Fall wäre es zugelassen Optimierung außen vor wir sagen nur also Fragen der an die Antworten ja nein erlauben die vergeht es zulässigen .punkt also diese Frage wenn wir gleich sehen gehört zu der Probleme der NPD vollständigen so und was ist was heißt NP in dem Fall man dessen ein Problem in diesen NP ich kümmere mich nicht um die Lösung ja jemand gibt mir eine Lösung und ich muss nur überprüfen ob die Lösung korrekt ist also das sind die Probleme in NP sind man kann es ihnen die kleinen Stücke aus Informatik ,komma kann wird wohl die Maschinen definieren also nicht deterministische Algorithmen aber letztendlich geht es darauf zurück zu sagen ich nehme und zum Problem Beispiele auf dem die Antwort ja lautet also nehmen uns sind ganz Tagesprogramm für die die Antwort ja lautet ja dann gibt es für dieses Problem im Zertifikat mit dessen Hilfe ich nachprüfen kann ob die Antwort korrekt ist es ist ein ganz sein Programm einfach warum was wäre es ein Zertifikat und überprüfen ob die Antwort korrekt ist ich haben ganz Programm als kleiner gleich B sag X aus Z Woch en ich stelle die Frage gibt es in ganz sagen .punkt ja oder nein und ich behaupte es ja es gibt ein und sie glauben mir nicht was muss ich ihnen gehen wie kann ich sie dann einfach überzeugen dass meine Antwort korrekt ist ja ich gehe wieder einfangen ganzzahligen Punkte wären und dann nehmen Sie diesen ganz sein .punkt einsetzen und ein überprüfen Mister ganzzahlig er das können sehr einfach machen und sie setzen es Umlagensystem 1 wenn alle Ungleichungen erfüllt ist die Antwort offensichtlich korrekt also 4. Unfall gibt es Zertifikaten mehrmals überlegen also und das ist die große Frage zwischen polynomial lösbar und und nicht vor dem Jahr diesen NP Probleme sind es 2 unterschiedliche Klassen ich muss sozusagen hier in polynomial derzeit überprüfen können ob die Antwort korrekt ist ich muss aber nicht in Polen die Lösung konstruieren können wir eine Algorithmen sind solche die man die es schaffen wollen in Zeit die Lösung zu konstruieren dann sehr lineare Programme kann man Algorithmus ist die Methode der gibt ihn tatsächlich die optimale so in Polen aller Zeiten zum die große Frage sozusagen konstruieren schwerer als wer infizieren der und MP vollständig sind alle die Probleme die man in Polen Zeit verifizieren kann wer und Dekor die Frage ist eben ist aber den Unterschied zwischen den beiden Klassen es gibt natürlich noch vom komme besser deshalb beliebig schwierige Probleme kann sie jede beliebige Funktion vor dem 7 Problem definieren und zu vom Algorithmus mindestens solange sie diese Funktion ja aber an die an die an dieser Stelle ist sozusagen eine entscheidende Frage sozusagen ist konstruieren tat sich schwer das verifizieren so kann es vielleicht vereinfacht auszudrücken und das ist bislang kein gelungen weder das eine noch das andere nachzuweisen also geht es verifizieren tatsächlich einfach nur wenig über die Lösung gibt es nur zu überprüfen gut also um um dahin zu kommen ich habe es an einer Stelle ein bisschen gemogelt nämlich ich gebe Ihnen ganzzahligen .punkt und Sie müssen das im folgenden Jahr derzeit überprüfen können das setzt natürlich
voraus dass ich Ihnen ganz sagen .punkt geht der auch nur koloniale Größe hat wenn ich ihn jetzt ein .punkt geht der Komponenten alle doppelt exponentielle Komponenten oder sowas haben dann kostet Sie das ja schon exponentiell viel Zeit diesen legt dazu speichern und dann auch zu überprüfen ob der ganzzahlige ist also was man natürlich brauchen damit es korrekt es ist das Wesen ganz sagen .punkt gibt dann gibt es auch ein ganz ein .punkt der klein ist sozusagen in der Kodierung senken war und das ist das geht tatsächlich also wenig irrationale und er hat dann gibt es auch immer ganzzahligen .punkt dessen Kodierung Zwänge klein genug ist und das ist das was das nächste Lehmann sagt das war einfach mal an ohne dass was beweisen aber sie sozusagen essenziell um dann nachweisen zu können dass das ist wird als dass das Problem ganz sei zu lösen endlich schwer ist also wir schauen uns den Polyeder P an es muss ich nur mal nachfragen zu aus der Einführung Kodierung Zwängen sowas Hansenne Tat gemacht also gut wunderbar also dann hat sein nationales Pohl Eder sei ein nationales Polyeder und Vieh Seite Kodierung strenge jeder Ungleichung die Kuh Zwänge zur Dekodierung Zwänge wir gleich um seine maximal VI also noch mal zur Erinnerung die Kodierung hänge von der Zahl vielleicht aber definiert wenn ich hier der Zahl n haben dann definiert als sowas wie log der Zahl +plus 1 aufgerundet +plus 1 Größenordnung also der Speicherplatz der notwendig ist umso eine Zahl Computer abzuspalten also das ist die Anzahl die notwendig ist die Anzahl Bits ich brauchen wir ganze Zahl zu speichern +plus 1 1 Vorzeichen rechnen will oder kann man man könne jedes an der Codierung Schema nehmen aber angenehm das aus Computer und die sind auch in was Polyhymnia lität betrifft sind wir alle Schema sozusagen zueinander äquivalent sondern normal entsprechende viele Dinge rationale Zahl ab dann ist es so Q-DSL vom Zähler plus die vom nenne wobei ich da vorher gesagt hat dass die das die Kopien sind zueinander welche Matrix abgesehen die Summe aller Matrix Einträge und so weiter das vielleicht nochmals Erinnerung und wenn ich was den IQ die Jungs länger einer Ungleichung ist eindeutig ich nehmen die Summe aller Koeffizienten diese Ungleichungen +plus wie er also die Summe der Kodierung Sleng aller Koeffizienten plus die Kodierung Zwänge der rechten Seite ja das ist sozusagen die Kodierung Svenja eine Ungleichung und wir schauen uns die die übelste Ungleichung an im Sinne der Speicherung sozusagen in die Herr soll sozusagen gute Jungs Länge 4 haben kann vor also das heißt dieses Vieh gibt und sich dabei an wie also zu sagen was kostet was ist der Speicher Aufwand um mein Umlagensystem als kleiner gleich be abzuspeichern der und die Frage die sich jetzt stellt wenn ich sonst es dem aber Angst er gleich wie kompliziert können denn die Ecken werden ins Weise haben Sie dessen Einführung auch gemacht und man braucht sich über der zlib oder wenn ich in einem kontinierlich empfahl ich hab einfachen Polyeder Angst eine gleich wie die Kodierung Zwänge 6. wieder ,komma ausrechnen was ist die Komplexität gibt die übelste Komplexität eine Ecke von diesen Politiker das waren sowas wie viele ein Quadrat 4 oder sowas und das habe man gebrauchen mit die Methode auch starten zu können und keine ganz sein .punkt zu vergessen was uns 4. interessiert ist wir wissen dass das es für die Ecken von diesen rationalen Polyeder Geld aber die auch für die ganz 1 Punkte die innen drin sind er also wir haben Männer die Situation die Aussage die wenn Einführung hatten was natürlich wer sagen jedes von diesen Ungleichungen gut Jungs Länge kleiner gleich hat dann kann meine Aussage machen über diese Ecken hier das sehe ich aber das würde der genannte gemacht dann verschafft sich die Determinanten dann von diesem kleinen Systeme ,komma Aussagen machen über über die Ägäis sozusagen was die maximal welche welche Kurse 10. Übel ist der im übelsten Fall auftreten können denn Sie auch die Regel das Gleichungssystem lösbar nimmt sozusagen Männer die der Termin nannte und dem Celler indem man die Idee spaltet auch die Rechte sei der Tausch kriegt man die Lagekomponente des Lösungsweg Trost und über das würde dort argumentiert wie Übel in diese Ecke maximal von Akkordeonklänge werden kann soll jetzt investieren sie aber nicht dieser .punkt der ganzzahlige dann würden ja und die Frage ist welche Kodierung sehe kann er im dümmsten Fall haben und da es nicht ganz leicht zu argumentieren weil hier nicht direkt mit diesem und dem System arbeiten können wir hier ist immer irgendwie ändern und das kann sein dieser .punkt mit einem keiner in der gegebenen Ungleichungen hier an ja und das ist eben anders argumentieren aber es lässt sich auch argumentieren es ein bisschen technisch aufwendig und es kommen bis eine größere Zahl raus aber es geht auch ich gebe einfach jedes Ergebnis dazu an und wenn man Lust hat nach zu lesen kann es kann zum Beispiel ins Kleiber machen über Theorie der ganz linearen ganzzahligen Programmierung also die Aussagen sind dann so geschah es dieses Polyeder an dann gibt es dann existiert nun B X kleiner gleich die Mehr mit der ihn ist nichts anderes als P BD während das wissen wir ja schon das was man bewiesen haben dass es wieder ein nationales Polyeder nationales Polyeder dazu muss man wartet eine rechte Seite gehen wir kennen sich nicht aber anderen gibt es wie wir wissen dass es gibt aber so das die Kodierung Zwänge jeder Ungleichungen maximal 15 m noch 6 4 ist also letztendlich aber wir wissen ja schon die mir dieses Text daher leicht die konstruieren kann man über früher motzt gehen können wir das deshalb konstruieren und muss es einfach verfolgen sozusagen wie bläht sich die Komplexität auf es gar nicht ist immer schon wieder das Gebaren zwischen Theorie und Praxis im Moment ein bisschen uns einfach polynomial lität so Polen ja eh noch 6. Polen und Polen Jahr praktisch ist es natürlich nicht handelbar der Wende war also eh noch 6 bis jenseits von gut und böse dass mir irgendwas wer rechnen kann aber und an der Stelle des Südens reine Theorie so und wenn wir dieses ist dem man es dann kann er wieder genau so argumentieren wir sehen konnte Fall ja auch getan haben also falls dann dieses TI ungleich leer ist ja und dann dann existierten ganzzahliger .punkt mit gute Jungs Länge maximal 5 n hoch 4 wie vor so wäre wer Interesse hat kann nachschauen in ich weiß zum Beispiel ins Buch was sich auch in in der Literatur angegeben ist so sobald sie mir jetzt erst in der Lage sozusagen nachzuweisen dass es Probleme Ende vollständiges und das formulieren Erzieher aus Satz Satz 2 8 das Entscheidungsproblem .punkt
had a x kleiner gleich B aus dem Hof im Kreuz entweder aus q hoch M er einen ganzzahligen eine ganzzahlige Lösung ist endlich vollständig gut gut 3 also schauen was es an die wenigen etwas waren zu keine normalen bis 2 3 Wahnsinn und nehmen den Begriff MP gehört haben dass sich die Nummer 2 dabei genau 4 5 ok also dann sagte ihnen seit dem polynomial lösbar was gibt ungefähr also Freitag dazu nochmals Größe Rückblicke kann Schauern für die anderen glaube zumindest in den Prüfungen fragen was ist dann das offen auf also ich formuliere es trotzdem schon den Beweis also was man macht in der Komplexitätstheorie ist man was sucht Algorithmen dienen die also Probleme zu klassifizieren und zwar in solche ich nenn es mal einfach so solche die einfach lösbar sind und solche die spielt lösbar sind sie so die Frage wie definiert man schwierige und einfach und der Ansatz ist zu sagen wer also einfacher heißt es sozusagen den Algorithmus erledigt ich innig kurzer Laufzeit das Problem löst was an die offensichtlich ist dass wir nicht denn ein großes Beispiel gibt das hat natürlich dann auch länger braucht es um die offensichtlich also wenn ich im jetzt Matrix gibt 2 Kreuz 2 Matrix sollen ist solltest einem System lösen es offensichtlich dass vermutlich schneller geht als wenn ich mit 2 Millionen 2 Millionen Matrix gehen also man man kann das nicht sozusagen komplett losgelöste nur Probleme abhängig sondern er muss es einig abhängig von der Eingabe Größe sehen und danach werden Algorithmen bemessenen schaut sich also die Länge der Eingabe an als in dem Fall Beispiel Eicks ich muss die Matrix A 1 gegen 7 Matrix und die den Vektor B eingeben eines koste den Computer so und so viel Speicherplatz oder so wie wir sie angegeben haben bis in dieser Notation denn das kostet nicht die der eines der Matrix Eintrag Größenordnung logarithmisch der 1 er der Logarithmus der Summe der Einträge dieser Matrizen vor das ist meine Eingabelänge und das sage ich er jetzt da sie mein Algorithmus darum so wie man sich jetzt die Laufzeit eines Algorithmus Spieler aus den eigenen eines Algorithmus mäßig einfallende Anzahl Operationen die er braucht um dieses Problem zu lösen das ist die Frage was erlaubt man als Operationen was man klassischerweise erlauben möchtes plus minus mal geteilt und Vergleich an von jeder Ayse diese Operation zählt man so ein bisschen beim Multiplizieren zum Beispiel Sonderfall aufpassen dass eine Feinheit wenn man es kann sein dass die Anzahl Schritte zwar dann Polen wir als aber die Zahlen groß werden ja wenn ich immer eine Zahl mit sich selber zum Beispiel wird sie über die Plastik exponentiell ja und dann kostet mich das schon mal Exmann auf sie die Zahl überhaupt zu lesen ist das soll diese Freiheit lassen wir mal weg zumal bei uns maximal Gleichungssysteme zu lösen sind und da dieses Problem nicht auftritt also erlauben plus minus mal geteilt und Vergleiche und zählen jetzt in unserm Algorithmus jeden einzelnen Schritt und setzen den ins Verhältnis zu der Eingabe gelöst so und wenn diese Zahl sozusagen für alle eine haben doch ein Polynom beschränkt werden kann ich mir das nämlich erst Laufzeit die Anzahl Schritte und ich das doch ein Polynom beschränken kann dann spreche von der Polen im Jahre Laufzeit n so und jetzt n es hat mal eben dazu zähle zum Beispiel geniale Programme das was in Einführung gemacht haben da wenn Sie mir noch mal die genauen Zahlen angucken weil sie mit Ruhe da kommt dann irgendwie Laufzeit was von Kodierung Zwänge von aber es gediehen Senkung des blablabla und so weiter kommen genau diese Zahlenreihen mal n hoch irgendwas also wenn man sich diese Größe anschaut dies polynomial in der Länge der Kodierung Länge der Eingabe an damit haben aber die Nummer 1 Verfahren so und jetzt gibt es eben Probleme und dazu zählt jetzt eben auch diese die nicht oder bist danke für die nicht bekannt dass die innerhalb kolonialer Zeit lösbar sind aber der Korrektheit ich in kolonialer Zeit verifizieren kann und das in genau diese NP Probleme und die die wollt ich einfach die Definition noch mal hinschreiben ja also zur Änderungen schon mal ein also ein Problem geh gehört zur ende des Falles folgende Eigenschaften erfüllt sind als 1. also eine entschuldigen Sie eigentlich ein Entscheidungsproblem also wir erlauben im Moment hier nur Entscheidungsprobleme also dass wir hier oben ist auch Entscheidungsproblem zur für alle beispiele aus Problem Beispiele aus diesem Problem Klasse ja mit Antwort ja existiert ein das muss polynomial in in der Kodierung es länger von diesem
Beispiel sein mit dessen Hilfe die Korrektheit überprüft werden kann mehr wir werden .punkt würden also und es ist wieder ein seidige fikat mit dessen Hilfe hätte die Korrektheit der Antwort überprüft werden können .punkt und billige es existierten Algorithmus ab mit Input so ein I unten Zertifikat Z der wieder polynomial in in der Gott wir uns Länge von den I der die Antwort bestätigt der die Antwort ja so also was steht Schifflein bisschen kompliziert aber noch mal in der Sprache in dem es in mal etwas populärwissenschaftlich mischbare der anderen Problemen er und die man von in der Haupt wer kann das lösen Zwillich Wings in der Lage sein zu überprüfen ob das stimmt also verlange ich von ihm so ein Zertifikat ja das ist diese 1. Punkt das Zertifikat alleine nützt mir noch nichts wenn ich selber nicht in der Lage bin dann die Korrektheit dieses Zertifikat zu überprüfen ist dieser Punkt und was sich auch verlange ist ich bin ich brauch die Überprüfung so laufen dass sich nur in der ausge indem Ausgangs Problem Polen sein muss nicht dass der Mehr zum Zertifikat gibt was ich gar nicht schafft es sozusagen abzulesen weiß viel zu groß ist ja mal Algorithmus muss muss sozusagen polynomial in denen ihr laufendes heißt diese Größe dieses Zertifikat das Ende gibt es ja ich darf da keine Rolle spielen so das heißt damit kann ich mit wenn ich sowas habe dann kann ich wirklich jemand über prüfen in vernünftiger Zeit spielen Polen Zeiten ob der nicht mehr übers Ohr hauen also sonst kann er nie alles haben daran Probleme super toll aber wie soll ich das überprüfen hier steht wenn es der Klasse der NT Probleme gebe es ein dann gibts Instrument zu überprüfen ob die Antwort korrekt ist also schauen uns das mal an heißt es denn genau für unsere unser Problem hier ja vielleicht 2 Definition vorneweg ja vielleicht als ein Toupet da wir noch dazu die heißt endlich schwer falls falls sich im polynomial Algorithmus ab 4 die war es ein wollen wir alle Algorithmus für P verwendet werden kann jedes Problem in NP zu lösen bei so hat der Randbedingungen war also jedes Problem in NP wir Kinder gar nicht alle Probleme in NP aber die wir schwer heißt sagen so wenn ich nen guten Algorithmus hat ist der gleich so gut dass alle Probleme Datteln erschlägt an und das heißt NP-Vollständigkeit wie heißt endlich vollständig falls es in den PS in den PS unendlich schwer weil das sind wie ich schweren Entscheidungsprobleme sozusagen in NP 10 der bislang nur Entscheidungsprobleme in diesem Endbericht schwersten jetzt auch Optimierungsprobleme da wird nix darüber ausgesagt aus mentales Probleme so wenig so nur in der vollzieht ist dann die Teilmenge der schweren Entscheidungsprobleme sind aber auch diese Eigenschaft haben jedes Problem in NP lösen zu können wir haben so die Schwierigkeit ist da gibt es überhaupt solche Probleme ja und die gibt es tatsächlich gegessen ganz berühmten das Resultat von Cook von 71 der nachgewiesen hat dass es deshalb die Problem zu diesen NP-vollständige Probleme gehört ja und genau das werden wir gleich auch verwenden um nachzuweisen dass unser Problem auch endlich wie es bisher in der vollständigen er vielleicht vorneweg noch eine Sache die wir jetzt schon mal klären können den Beweis der vollständigen Furchen beweisen das nächste Mal die 1. Frage dieser ich stellen es unser Entscheidungs abholen da droben in NP also was wir müssen 2 Dinge klären wir nachweisen weil das NP-vollständige ist bis wir 2 Dinge tun
erstmals muss zu NDR gehören und das 2. ist es muss endlich schwer sein das endlich schwer ist eigentlich schwer nachzuweisen wenn man nicht schon bestehende das Upgrade verwendet man kennt Beispiele die NP vollständigsten um Wasser Dreck ist ja und ich haben in der folgendes Problem ist nämlich mein Problem mehr nehmen wir mal an ich hätte jetzt ein Algorithmus wir mal an ich hätte ein Algorithmus für mein Problem wenn ich jetzt das von dem ich weiß dass es schon vollständig ist auf mein Problem transformieren kann ja ich dann soll mir das was ich kenne also das dem verlässt das Weibl Gewinn auf mein Problem mir mein Polen ein Algorithmus und dann dann zunächst wieder zurück dann hab ich das andere Problem auch gelöst müssen aufpassen dass die Transformation polynomial bleibt insgesamt polynomial Algorithmus kann weil die Schwierigkeit steckt nur dann drin wenn man mal ein zum Problem haben und die gibt es ist Ihnen das erzähle ich Ihnen das nächste Mal dann muss ich nur noch ne polynomial Transformationen gekommen weil sich meint es genauso schwer wie das andere bei männlichen Algorithmus hätte ein Transfer mich das an einfach auf Mainz löst es mit meinem Algorithmus tanzen es wieder zurück an das ist der Gedanke das Tor des (klammer auf klären ist unser Problem in NP Unbekümmertheit gerade noch mal die wir sind diese Definition Revue passieren lassen also was wir jetzt brauchen ist aber die Definition von MP anschauen so für alle Probleme tanzen also was heißt das für alle ihn aus Pi das heißt jedes Problem beispiels heißt wie jede konkrete Matrix und ungelegen konnte wegen Vektor B r und das ist dann zum Problem Beispiel hier die Klasse P ist sozusagen die Menge der Ruhm bleibt ist die Frage da oben allgemein hatten und Gleichungssystemen ganzzahligen .punkt das spezi hilft spezifiziert noch nicht dass Gleichungssystem will jetzt nämlich nicht konkretes ihr aus von dem ich weiß dass es den zulässigen .punkt hat das ist das mit der Antwort ja also ich nehmen einst eine gleich be aus ich weiß es gibt kann ganzzahligen .punkt soll jetzt muss ich enden jetzt muss ich mir sonst hat es muss es ein Zertifikat geben wenn es aber gerade stand diskutiert das Zertifikat wissen ganzzahlige .punkt ich gebe Ihnen ganzzahligen .punkt die einzige Schwierigkeit die wir noch haben ist dass dieser ganzzahlige .punkt zu spei tief sein kann dass der den zu speichern nicht Polen ja alles aber des kann man hiermit erschlagen wer mit dem mit dem mit dem wir hier wenig wenn man ganz zeigen .punkt gibt also den P ungleich leer ist dann existierten ganzzahliger .punkt dessen Kotierung Sänger höchstens 5 n hoch 4 4 ist das heißt der wenn lösbar ist dann gibt es auch einen Punkt der nicht allzu kompliziert es um allzu komplex das heißt damit ,komma tat und Zertifikat er soll es müssen überprüfen was ist der Algorithmus sagen der Algorithmus hier ist einfach aber wir müssen überprüfen ist sind die Komponenten alle ganzzahligen der das kann einfach machen ja nicht einfach jede Komponente an und dann setzt würden .punkt einfach eingerechnet aus a x ja und das Mac da mal Matrix ist im Jahr ist in Bagdad Operation und prüfen ob die ob es die rechte Seite erfüllt kleine gleicht der rechten Seite ist das heißt diese Operation ist Polen wie alles was wir haben ist ein Algorithmus der sind ebenfalls sehr simpel aber es ist ein Algorithmus der als Eingabe genau dieses Zertifikat sind und es um Gleichungssystem und überprüfen ein weiterer einsetzt wenn alle damit wissen wir sozusagen unser Problem also obiges Problem es schon mal in NP wisst ihr auch die Frage ist unsymmetrisch Anwender die Anwender die gleiche Frage stellen würden mit Nein dann wird muss schon viel schwerer tun wir agieren würde ich hier schreiben charmantes entscheiden so hat an hat Alex daher gleich B keine ganzzahlige Lösungen wir haben was wären dann Zertifikat das klären wir vielleicht das nächste Mal ok danke schön
Nebenbedingung
Polyeder
Punkt
Verweildauer
Konvexe Hülle
Vorlesung/Konferenz
Größenordnung
Optimierung
Computeranimation
Nebenbedingung
Punkt
Polyeder
Endlichkeit
Konvexe Hülle
Zahl
Richtung
Lösung <Mathematik>
Rationale Zahl
Vorlesung/Konferenz
Durchschnitt <Mengenlehre>
Zielfunktion
Gerade
Polyeder
Punkt
Aussage <Mathematik>
Konvexe Hülle
Gleichungssystem
Teilmenge
Index
Variable
Menge
Ganze Zahl
Rationale Zahl
Ganze Abschließung
Bruch <Mathematik>
Vorlesung/Konferenz
Umkehrung <Mathematik>
Durchschnitt <Mengenlehre>
Gerade
Ecke
Funktion <Mathematik>
Punkt
Große Vereinheitlichung
Richtung
Negative Zahl
Operator
Vorzeichen <Mathematik>
Gleichheitszeichen
Vorlesung/Konferenz
Zielfunktion
Funktion <Mathematik>
Einfach zusammenhängender Raum
Polyeder
Rationale Funktion
Konvexe Hülle
Aussage <Mathematik>
Karhunen-Loève-Transformation
Biprodukt
Vektor
Zahl
Teilmenge
Rechenschieber
Menge
Betrag <Mathematik>
Ganze Zahl
Rationale Zahl
Strahl
Darstellung <Mathematik>
Polyeder
Punkt
Vektorrechnung
Konvexe Hülle
Kommensurabilität
Zahl
Index
Ungleichung
Kettenregel
Rationale Zahl
Vorlesung/Konferenz
Ecke
Ebene
Addition
Folge <Mathematik>
Entscheidungsproblem
Polyeder
Punkt
Gruppoid
Klasse <Mathematik>
Konvexe Hülle
Skalarfeld
Richtung
Teilmenge
Summe
Ungleichung
Menge
Ganze Zahl
Ganze Abschließung
Lineare Optimierung
Vorlesung/Konferenz
Zielfunktion
Optimierung
Matrix <Mathematik>
Länge
Matrizenmultiplikation
Punkt
Große Vereinheitlichung
Momentenproblem
Laufzeit
Klasse <Mathematik>
Gleichungssystem
Ganzzahlige Lösung
Komplexitätstheorie
Multiplikation
Quadrat
Logarithmus
Ungleichung
Vorzeichen <Mathematik>
Vorlesung/Konferenz
Einfach zusammenhängender Raum
Entscheidungsproblem
Polyeder
Determinante
Gruppoid
Ganzzahlige Optimierung
Aussage <Mathematik>
Vektor
Zahl
Summe
Polynom
Zahlenreihe
Ganze Zahl
Koeffizient
Rationale Zahl
Größenordnung
Ecke
Einfach zusammenhängender Raum
Länge
Punkt
Matrizenmultiplikation
Klasse <Mathematik>
Gleichungssystem
Randbedingung <Mathematik>
Vektor
Ganzzahlige Lösung
Entscheidungstheorie
Teilmenge
Menge
Vorlesung/Konferenz

Metadaten

Formale Metadaten

Titel Ganzzahlige Polyeder: Zulässige Mengen
Alternativer Titel Ganzzahlige Polyeder: Zulaessige Mengen
Serientitel Diskrete Optimierung (Optimierung II)
Teil 05
Anzahl der Teile 26
Autor Martin, Alexander
Lizenz CC-Namensnennung - keine kommerzielle Nutzung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen und nicht-kommerziellen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben.
DOI 10.5446/31779
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...