Merken

NP-Vollständigkeit, totale Unimodularität

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
DE höre ich ja das war ein so herzlich
willkommen zur heutigen Vorlesung wir wissen wir das letzte Mal mitten in beweist stecken geblieben wir haben angefangen uns wir ganzzahligen pro Liedern zu beschäftigen und den Zusammenhang hat uns interessiert zu sagen was was macht denn die Schwierigkeit aus wann Klima den sozusagen automatisch ganz geschenkt damit haben das letzte mal angefangen und und das wollen auch heute dann ein Stück weit fort setzen wir wollten aber bevor man sozusagen dort einsteigen nochmal klar den Unterschiede herausarbeiten dass es tatsächlich ich auch von der Komplexität der Unterschied macht ob ich mich herein um lineare Programme beschäftigt also wohl die ganz Seitwärtsbewegung nicht dabei habe wissen wir aus der Einführung dass diese Probleme in kolonialer Zeit lösbar sind und wir waren gerade das letzte Mal dabei sein den Beweis zu führen dass sobald ich ganz Forderung ab dass im Allgemeinen zu der Klasse der sogenannten endlich werden Probleme gehört also dort wirklich signifikanter Unterschied was auch dann für uns den Unterschied machen wird wenn wir dann tatsächlich Probleme lösen wollen in der Praxis oder auch in der Theorie ist als wir müssen mit unterschiedlichen Verfahren angehen um solche Probleme zu lösen die können wir können nicht mehr warten wenn man die globale optimale Lösung haben wollen wie immer in kurzer Zeit Lösungen finden das heißt über ist will dass es immer passieren können dass solche Algorithmen exponentielle Laufzeit haben das heißt es man müsse in der Theorie so akzeptieren Moment zumindest und natürlich auch wenn der praktische Probleme gelöst und sich dessen immer bewusst sein das egal welchen Algol bis wir uns entwickeln es durchaus auch mal schiefgehen kann wird sie so dass man länger warten muss alles die notwendige Kaffeepause die man normalerweise ein Plan gut gehts bist darin zum letzten Mal noch nachfragen und wenn dem nicht so ist der Bericht Beweis weitermachen die hat mir gesagt was wir beweisen wollten war das folgende also das war der Satz 2 8. war stecken geblieben so die Aussage existierten X sozusagen mit AIX kleiner gleich B und X aus der doch n wer diese Frage zu beantworten dies entweder vollständig aber stehen geblieben ist vollständig so mal zu Wiederholung das heißt ende vollständig ja das mal geklärt was heise behaupten Probleme in NP zu sein nochmals Wiederholung des mussten 2 Eigenschaften erfüllt sein aber eine es muss ein Zertifikat geben mit dessen Hilfe ich die Korrektheit überprüfen kann und das 2. war es mussten Algorithmus geben der als Input das Problem hat das Problem Beispiel und dieses Zertifikat und dann auch überprüft ob die ob die Anwort korrekt ist in kolonialer Zeit so wunderbar Marder beides zu überprüfen für unsere für unseren Fall mal die 1. Frage die wir einen Beweis zu klären hatten ja dann nochmal dieses Problem hier der 1. was man zu klären hatten hier ist sozusagen in dieser Klasse enthalten warum nochmal das war das Zertifikat Zertifikate Svensson X gibt das ist eine Dekade ist eine Lösung selber also wir geben so Lösung die erfüllt zu zeigen an also war mit dessen kann weil die Korrektheit überprüfen an wen ich ne Lösung hat kann ich die natürlich die Korrektheit überprüfen ob die Antwort hier auf ja korrekt ist wenn ich nehme die Lösung setze einfach einen ja wenn sie offensichtlich ganzzahliges und alles erfüllt ist auch ein ziemlich einfach Algorithmus der läuft linear durch und damit habe ich sozusagen alles da die Kat und Algorithmus um zu überprüfen ob die Antwort korrekt ist ja noch mal dass dieser Liste Entscheidungsprobleme stelle nur die Frage existiert als Geld geht aus der doch allen und das einzige was mir mein Orakel sozusagen Arnold ist ja oder nein ja und wir geben also den Mareks an legte er B und gesagt na ja so das Trauma der Antwort ja nicht wie wir prüfen wir und dann sagen hallo wir zu überprüfen wolle Zertifikat das der delikat ist die Lösung x ja und dann können wir überprüfen und sagen ja ich es ganzzahlige und vieleicht sein wird wie also Trauma dieser Antwort und es geht in kolonialer Zeit das Einsetzen ist linear Überprüfungs ganzseitiges auch ein sehr aufpassen mussten war ob dies ob die Länge von diesen Lösungsweg auch polynomial in A und B ist er und das ist dieser Satz den wir das letzte Mal oder das man es das letzte Mal vorgeschoben hatten womit wo gesagt hat ja wenn A und B denn sozusagen ist ist die immer eine ganzzahlige Lösungen der Kodierung Sleep Rolle im Jahr in der Eingabe A und B ist ja und damit sie wissen wie es in den NPE war das letzte Mal noch gestellt wie sieht es denn aus wenn ich jetzt die Frage die umgekehrte Frage stel also ein gibt es keine Lösung für System als kleine BX Auszeit auch allen was werden dann Zertifikat also wieder das gleiche Frage gibt es keine Vikar Fragen gibt es eine Lösung ist daher gleich BX 1. doch endlich sage einfachen Bundesorgane sagten nein was wären dann Zertifikat um die Korrektheit dieser nein Antwort zu überprüfen und sich man da Gedanken gemacht es Vorschläge es gibt es noch kein einfaches Zertifikat also bislang kennen keinen ein freies Zertifikat um zu überprüfen und in eine Antwort zu zertifizierten er die Probleme also wir sehen dass es unsymmetrischen ja und nein haben ein Amt nein antworten zu qualifizieren können schwieriger sein als antworten also zumindest in dem Fall ist es nicht klar sozusagen die man ein fast dadurch alle Zertifikate über bislang kennt und in einer Antwort korrekt zu machen ist sind sie ist exponentieller Natur bislang an also das sieht man an dieser Stelle sozusagen diese diese Diskrepanz zwischen ja und nein wenn man das die gleiche Frage finde einstellen würde spricht man von und Co mp Problemen waren und sozusagen dann interessiert ein auch der Schnitt zwischen NPD und Co und man weiß dass seine polynomial bis sind auf jeden Fall in dieser Schnittmenge enthalten aber gerade für diesen Bereich es gibt auch die Probleme die man schon kennt ihn NP und Co P sind aber für die man bislang noch keine Polen Algorithmus kenne also wenn unser Fahrer war die Frage gestellt die Nachfrage ist ist in dem Fall einfach zu zugleich gibt sie ihm einfach die Lösung dazu angeben so was wir jetzt noch brauchen ist aber wir wollten ja zeigen dass das Problem NP-vollständige ist so das heißt und jetzt kommt mir diese Schwierigkeit 3 zu zeigen also vollständig heißt nochmal um das zu wiederholen vom letzten Mal welchen Algorithmus hätte für dieses Problem der polynomial dieses in Polen eine 2. Problem ist dann kann ich auch jedes andere Probleme in NP in Polen gar zu erlösen ja es klingt jetzt erst mal
also hat er dann Bewegung weil ich kenne ja gar nicht alle jemals auf der die Probleme die vielleicht jemand zeigt dass die mal in MP sind wie soll ich denn dann nachweisen dass wenig denn ein Algorithmus hat für das Problem der sich damit auch alle andern lösen können war ja genau wer genau aber beginnt genau das wollen wir jetzt hier machen wir reduzieren das den Schritt machen wir aber brauchen das andere so irgendwoher kommt das müssen erst mal haben wir und das geht mir jetzt an man kann sie so die Frage stellen wo kommt es irgendwo her eigentlich der ja was heißt zu Fuß wir werden immer aber die Frage wie wir die wie sie das Konzept aus um zurück zum Beweis überhaupt führen zu können unabhängig davon ob ich ich kenne alle Probleme und trotzdem ist kann ich sagen das Problem was Merz gleich anschreiben egal welches ich hab ich kann's immer auf das zurückführen wie des ist ein zu sagen schaut sich was heißt Polen Jahre Laufzeit man meinen man beschränkt sich auf ein sehr einfaches Computermodell war dieses damals so genannten Turingmaschine er die konnte der allzu viel machen außer sozusagen auch zum es gab son Bahn auf dem man was drauf schreiben konnte was ein lesen konnte und die nach dem was man gelesen hat bloß das was dann gab sich als sehr einfache CPU der die Abhängigkeit von dem oder Lesekopf gar auf dem Band steht und dem Zustand aber in dem sozusagen eine gerade war sozusagen neuen Zustand berechnet hat und diese Lesekopf bewegt und was auf dieses Band gespielt hat als im Wesentlichen die weg das sind eigentlich die besten Elemente eines Computers mal die CPU jemand was in Abhängigkeit dessen was der Speicherinhalt gerade ist und schreibt wieder was im Speichel ist was von Speicher und ändert sozusagen seinen eigenen Zustand ja das lässt die funktional schön beschreiben und letztendlich lässt sich nahezu jedes Computerprogramm so Mehr einfache Maschine realisiert jedes was Sie schreiben Computer lässt sich mit etwas gut Willen sozusagen auf so ein einfaches Modell diese Tour die Maschine reduzieren und jetzt stellt sich sozusagen die Frage ist ein Problem oder Essen Probleme Pollen aller Zeiten lösbar stellt sich nur darin zu zeigen hält sich diese Turingmaschinen Polen aller Zeit er dazu Issen Endzustand angegeben der irgendwann erreicht werden soll der dann entweder auf dem Eingabe beim stehen oder in diese Einheit der und die Frage ist ,komma komm ich doch lese Schreiber Operation und sozusagen Modifikation des Zustands der werden der Einheit der Recheneinheit diese Tour die Maschine irgendwann in diesen halte Zustand und wenn mir das gelingt den Pollen Yala zeigt dann spreche von polynomial Algorithmus und wenn das nicht gelingt oder die Maschine nicht hält ja dann eben ist es in der gar kein Algorithmus wenn am Ende gar nicht hält oder westlichen Polen ja Leiter des keine Polen Algorithmus so und es geht also darum sozusagen zu entscheiden hält und einer gewissen Eingabe diese Maschine Na und es lässt sich sozusagen dat dat is dann diese Brücke nicht mehr ganz so schwer zu diesem Service freier Wille die Problem wo man wie die bisher eine Anzahl von Größen hat Liberalen die wahr oder falsch sein können und man frägt sich jetzt um alle diese lebte erhalten die zu mindern der verkoppelt Zensurgedanken Klausel immer frägt sich jetzt um alle diese Claußen sind da und das ist das was sie gerade gemeinsam zu Fuß kann man dann zeigen dass diese beiden Probleme tatsächlich über den Sinn des halten dieser Poliermaschine und das erfüllen dieses Feierwillige Problem ist aber entscheiden sozusagen das Sie jetzt jeden Algorithmus den ihre und die man auch dem Computer entwickelt von der von den ansetzen also was sozusagen es würde ja eines Algorithmus ausmacht letztendlich alles aus einer einfachen Maschine die der Steuereinheit unten unten schreibt Leseband hat alles realisieren lässt und von der Komplexität der sie auf die Frage reduzieren lässt hält diese einfache Maschine ja oder nein so und dieses Problem das ist dieses was sie schon paarmal erwähnt bis dieses es war billig Problemen will vielleicht zunächst definieren Definition 2 1 1 1 2 9 seit das steht für ist fragen zu so nicht Schlenzer des freier wird die verehrten ihn die also die 1. 3 Buchstaben von soll das ist jedes 2. Brille die richtig geschrieben ab sonst müssen noch nochmal rausschneiden muss 10 bis 2 Bericht aber stimmt oder denn es war wirklich Probleme also war was einmal gegeben wir logische Variablen X 1 bis Xn die können Werte war falsch annehmen also XI kann werde war oder falsch annehmen und es gibt ne Menge von Klauseln war das eine Menge für 1 bis cm und Clausen stehen so diese Klausel jede Klausel Spiel besteht aus einer Disjunktion von Variablen oder der Negation von beziehungsweise deren Negation an und die Frage die sich jetzt stellt ist existiert eine Belegung existiert Verlegung der XI wird man beziehungsweise freilich so dass alle Klauseln wahr sind so dass alle Klauseln erfüllt werden das alle er 14 Klaus und sollte natürlich im deutschen wird mit klarer hallo also ein Beispiel und wir sagen wir haben hier X 1 oder nicht x 2 oder x da ja das Werk Klauseln 1 ja da habe ich entsprechend mit 2. Klausel x 2 oder nicht X 3 und ich haben den 3. sagt nicht X 1 oder 3 ja ohne Frage finde ich jetz find ich jetzt Belegungen von x 1 x 2 x 3 1 so dass alle alle wahr sind kann es auch in einer Form ist im Schrein dem ich die alle Bitten und verknüpft alle alle war heißt C 1 und C 2 und C 3 soll gleichzeitig erfüllt sein kann soll dieses Problem bei dieser Fragestellung dies der vollständig also Bemerkung 2 10 sag ist endlich vollständigen des hat ein Cop gewesen 1900
71 zu allem was er gezeigt damit diese Idee wie ich sie beschrieben habe über diese Turing Maschine das sozusagen jedes Problem ja was jetzt und in der Sprache ist MP sozusagen das sind diejenigen Probleme die aus der Natur die Maschine R nichtdeterministische Polynomialzeit also in daher kommt das NPD nicht deterministisch Polen im Jahr was heißt es nicht deterministisch Polymnia mal wann immer sie eine Entscheidung fällen müssen also ist der Band in ihrem Programm falls das kleine Ding machen Sie das oder falls das wir selber machen sehen es was diese nichtdeterministische Turingmaschine an die Mächtigkeit hat ist sie kann beide Pfade gleichzeitig gehen ok das heißt nichtdeterministische ich kann sowohl in einer Art auf den andern Fahrt das entscheidende ist nur das irgendeine dieser Pfade in Polen im Zeit realisierbar ist und das ist eigentlich egal denn zu dem was man geschrieben haben zu sagen gibt es den Polen ja Lacey kann ich denn die Korrektheit wer infizieren das wissen die Diversifikation sie dann außer sich genau diesen einen Einfahrt auch wenn muss es immer so vorstellen Programm bei verschiedene Entscheidungen zu fällen die sind diese Entscheidung machen müssen Entscheidungsbaum auf das Problem von ließen von diesen Art von Problem ist dass dieser Entscheidungsbaum exponentiell wächst aber die Tiefe dieses Baumes bleibt Polen im Jahr um jetzt sogar infizieren das Mehr an Bord korrekt ist auch ich als Zertifikat nur diesen einen Pfad um sozusagen die Entscheidungen des Algorithmus getroffen hat nachvollzieht zu können die zu dieser Antwort geführt haben und wenn ich das hab haben wollen ja das Zertifikat ja ist es sozusagen diese Mächtigkeit die Normen nicht Determinismus hatte also es ähnlich nicht sozusagen den Zinnen der Algorithmus nicht immer die gleiche Entscheidung erst einmal Würfel und die Frage ist können Sie sowohl für das auf jeden Fall zu einer Lösung kommen ja das ist nicht Determinismus und dieses und das eben die Frage so Tageslicht Determinismus in die Szene stärker als Determinismus da hilft mir sozusagen wohl fühlen wenn ich richtig würde für das als wenig und so wie es der immer ausgedrückt habe sozusagen der infizieren einfacher als er als konstruieren gut also von denen das war sicherlich einer der großen Leistung muss man damals wirklich sagen wo ist denn dieses Thema der Komplexitätstheorie jetzt auch als Mann Stückweit fassbar gemacht hat das war Ende der Sechziger Anfang Siebziger wurden dem Bereich sehr viel gemacht sozusagen zu outen Konzepte zu entwickeln die die Algorithmen unterscheidbar machen Mehr die die Algorithmen klassifizieren und er und das ist wichtig ist dass wir daraus sozusagen die Analyse von Problemen letztendlich wo wie oder wie wollen Sie einschätzen zu 2 Siegen am Problem vor der Nase ist die schwerste tatsächlich Zielscheibe der Software dafür lassen Sie es laufen wie lange Kaffeepause machen um die Antwort zu geben war und dort gibts jetzt sind würde theoretisch fundierte Aussagen wie dies die Probleme untereinander klar unterscheiden und die Art von Problemen zu den können welche muss da können Sie Glück haben uns es kommt schnelle Lösung aber es gibt Beispiele wo ja Algorithmus des bislang dafür gibt auf die Nase fällt sprich exponentielle Laufzeit so wissen wir dieses Problem SNB vollständig sollen damit wir jetzt müssen wir ist steht mir jedoch 1 B verhalten wir müssen zeigen dass unser Problem NP-vollständige ist sonder weil schon der Vorschlag ist ja schon gemacht worden die Hauptarbeit steckt rechts so an der Tafel wir was mir so noch tun müssen ist er am also was müssen wir noch mal tun um zu zeigen dass pi vollständiges sei angenommen wir hätten ein Algorithmus den kolonialer Zeit läuft an dann wir jedes Problem in NP in Polen aller Zeiten ist er also hier so unser Problem P ja das gegen Polen und ja wir haben polynomial Algorithmus dafür so was wir jetzt machen wir kennen dieses satt ja von dem wissen wir dass es NP-Vollständigkeit das heißt einen Algorithmus wie dieses satt Problem hab ich da keine jedes Problem in NP lösen also hier ist die große Klasse der Probleme der und jedes Problem in NP lässt sich auf dieses satte reduziert soll diesen Schritt müssen wir dann mal machen der schon erledigt wir müssen nur diesen machen kann ich das denn es war Willi auf mein Problem reduzieren und Erde ziehen sie aufpassen diese Reduktion muss er sich in Polen im Jahr Lehrzeit machbar sein ja wenn dem so ist das dann gib mir irgendjemand sei des war würde die Probleme zum Beispiel eines Westsumatra versteht dann Transfer mich das in meiner Welt jählings um steht Polen Algorithmus löst das Problem hier und dann dann soll man die Lösung wieder zurück in meines es war will die Welt und damit hab ich dann dieses Problem gelöst also ich lag so zeigen muss immer das Rad neu erfinden dabei immer guten Algorithmus hatten so wie alles andere auf dieses Problem zu transformieren in der guten Algorithmus und lösest dar bei diesen Trick macht man häufig in der Mathematik sowieso versucht man wenn man schon mal Lösung hat das auf das zu reduzieren was man was man schon kennt und lege sie alt auch algorithmisch aufgießen vor aufgezogen wird so das heißt wir müssen jetzt ist ja das war würde die Probleme heißen Eisen IP formulieren zu Vista links oben steht wie sieht es aus das wir so weitermachen Herrscherhauses mal wie das Beispiel anders müsste dazu machen alle brauche jetzt aus und X ganzzahlig was wäre das X ganzzahlig die Belegung also außer aus können weibliches X direkt neben der anstatt war falsch sagen wir halt 0 oder 1 waren also den XJ gleich 1 ist die Billigung des einst um den Sinn oder ist es die Billigung 0 wir also ist also XI auf 1 falls mit der Wahl XI gleich war wir selbst auf 0 falls es gleich falsch ist und sorgen die die wie schreibt sich hier zu zahlen die 1. Klausel unsere Sprachen in der in der IP sprachen so dass wir zu machen was wird oder das werden +plus und die Negation 1 mir das nur also schauen uns es an dem die 1. ließ sich das X 1 +plus 1 wie das X 2 +plus x 3 soll es dem muss wahr sein das heißt wir werden jetzt herauskommt muss mindestens ne 1 das man ok wann es gleich Spielchen immer nur für die andern auch der Name hier x 2 +plus 1 -minus x 3 größer gleich 1 und die und die 3. Zeile ist 1 -minus x 1 +plus X 3 größer gleich 1 ist vor sollen aber das ist noch in Matrix vorschreiben oder Name X 1 -minus x 2 +plus x 3 wir gleich 0 ja x 2 -minus x 3 größer gleich 0 und die haben wir -minus x 1 +plus x 3 größer gleichen und als die einst noch die rechte Seite gebracht so das ist jetzt unser es ist dem X kleiner gleich B wenn es ist ein kleiner gleich Name überall -minus sehen und schreibe über bei kleiner gleich ja und dann ist das genau und das ist dem X kleiner gleich B also noch dazu nehmen müssen sehr aufpassen dass genau in der Form haben wollen das nur noch dafür sorgen dass bin nicht
ganz nah wir müssen noch dazu schreiben bis hin zu voreilig also einerseits müssen fordern dass X nicht jede beliebige ganze Zahl annehmen kann sondern 0 0 oder 1 Venedig sein kann das heißt wir müssen noch dazu schreiben -minus x 1 kleiner gleich 0 und x 1 kleiner gleich 1 und das noch mal für alle Variablen E gleich 1 2 und ja so genau dieses ganze denn hier ist unser System A X kleiner gleich weg so will das lösen Mehr ja wenn wir die jetzt in Lösung haben dann kriegen 0 1 wird daraus x 1 x 2 x 3 ja und den Kammer direkt zurück übersetzen in dieses des verwendeten .punkt so die Transformation es offensichtlich polynomial warum sozusagen wie jede Klausel gegen eine Zeile wie die logische dem auch eine Variable ist ne 1 zu 1 Transformation an dieser Stelle an die beiden Systeme sind gleich groß also damit haben wir damit haben wir sozusagen also die Transformation ist polynomial und wer daraus folgt zuzuhören so zu 8.
ok gibt es dann noch Fragen dazu also Rückfragen der ständig hab da immer wieder nicht also ich merk's machen wollen in Prüfungen das dieses Konzept wollen wir alle nicht wollen Mehr nicht allen so geläufiges MNP entge vollständig und so weiter also wenn es da Schwierigkeiten gibt noch mal nachfragen oder am Anfang der nächsten Stunde noch mal nachfragen oder ist die große Frage stelle lösen ob das P gleicht dem NPS alle was weiß natürlich habe mir das dieses Mal von der Komplexitätstheorie anschauen wir die große Klasse der NPD Probleme oder den 10 vollständigen und wir wollen ja allen sind wir auch da in dieser Menge enthalten sind auch da drin ist in dem unter anderem bei uns in Polen Jahr in der Menge der NT Probleme drin schulde ich muss so man glaube normalen also wenn bei der PS sind auch da drin was in die die Polen ja lösbaren der 3 der NPD Group ja ja freuen genau also wenn wir jetzt nicht Problem aber sowohl in der Eizelle nicht fragt den sozusagen eine Norm ab BX ganzzahlige ist wer Polen ja lösbar ja und was machen wir dann der Frage so vage dass Tag also die an wurde es ja glaube der so glauben wir nicht mehr wir haben polynomial Algorithmus zu handele sich dem Polymer Algorithmus laufen sagte Oberst der sagt um eine seit Jahren den Spruch mir auch die Lösung aus ausgelesen nach Wissen über das in Ordnung ja alles waren Polen aller Zeiten also die PS sind tatsächlich ne wird Teilmenge ist ein davon und in die große Frage sozusagen also das also mir offensichtlich ja in die andere Richtung das ist das große Fragezeichen also gibt es sozusagen welchen MP Problem hat kann ich das in den Poren im Jahr Zeit lösen und das und das und das interessante ist um um diese Frage beantworten zu können wird reichen 1 von diesen NP-vollständige zu lösen er warum weil ich ja jedes Problem in NP daraufhin zurückführen kann ja wenigen polynomial Algorithmus NP-vollständige sah hätte der dich automatischen polynomial für alle Probleme in NP ich ja und damit hätt ich das gezeigt ja das heißt wenn ihn jetzt ab oder Algorithmus also um das Problem der links oben zu lösen wollen wir Algorithmus dann nahm sie automatisch gezeigt dass p gleich PS oder das Problem was am Anfang geguckt Hannes Rucksack Problem des stabile Mengenproblem des Peking Problem alle diese Probleme sind alle von diesem Typ NP-vollständige er ist für irgendeine von diesen Problemen guten Algorithmus Finnlands automatisch das gezeigt es gibt Hunderte von von Problemen also wahrscheinlich Hunderte der reicht schon gar nicht mehr Pause vom Probleme nachgewiesen wurde dass die vollständig sind also unterschiedlichsten Bereichen der Informatik der Mathematik und der Physik und den Naturwissenschaften allgemein die MP vollständig sind und von keiner dieser Probleme ist bislang ein gut Algorithmus eingefahren das Wege sind die Vermutung liegt nahe dass es sie in echt das Timing Zeichen ist aber diesen Nachweis zu führen denn der Saal auch noch niemand gelogen mehr ich habe schon erwähnt am Anfang das ist eine dieser 7 Probleme die zur Jahrtausendwende als im mathematischen Problem identifiziert worden des nächsten Jahrhunderts und die Lösung eines jeden dieser Probleme gibt es 1 Million Dollar also wenn rauskriegen das sind 6 im Lotto Na +plus die geringe Professor ziemlich sicher auch mit dazu wenn Sie das rauskriegen war gut also wir wissen jetzt aber wir uns jetzt erst mal mehr ,komma wir zurück auf den Boden der Tatsachen sozusagen für uns heißt es diese Art von Problem oder auch allgemeine Gemisch ganz ergo gramme sind viel schwerer zu lösen als lineare Programm ja egal was wir jetzt machen an Lösungsverfahren entweder wenn wir die optimale Lösung wollen dann hat an sich haben sind wir das Case exponentielle Laufzeit ja oder wenn aber in Polen gar Zeit bleiben wollen also schnelle Algorithmen garantiert Stelle Algorithmen wollen können wir nicht unbedingt garantieren dass wir immer die optimale Lösung finden und genau mit diesen 2 Arten von Problemen werden uns haben aber der voll sind beschäftigen was sind gut geht für exakte Verfahren die nach Möglichkeit so gut es geht diesen exponentiellen Charakter wegnehmen und November einige von diesen kennen lernen die 2 übers Käse und dieser Unterschied zwischen Theorie und Praxis dessen theoretisches Resultat eines Müllers Käse tat es heißt immer es gibt ein Beispiel oder Algorithmus auf die Nase fällt haben und das ist das was Auto ohne stilistische mehr Komplexität Serie nach in der Praxis Komplexitätstheorie sagte ich sie müssen wir Algorithmus geben und ich überlegen Beispiel so dass der Algorithmus auf die Nase fällt wer und wie diese Aussage er sagt ich finden Beispiel sodass die Algorithmus auf die Nase fällt sprich exponentielle Laufzeit auf in der Praxis ist aber umgekehrt der G 7 zur 1. Problem wir versuchen ihren Algorithmus zu entwickeln so dass er möglichst gut dieses Problem ist ja und da kann man dann häufig trotzdem auch für an sich schwere Probleme auch im Sinne der Komplexitätstheorie endlich schwere Probleme häufig trotzdem der gute Verfahren bekommen allerdings darf man nie vergessen dass durchaus wenn man den Algorithmus weint wie dass irgendeine Beispiel kommen kann oder eben auf die Nase fällt an dass es diese Aussage aber richtig ist auch für Sie wenn Sie später mal in der Praxis so wo Probleme lösen oder Probleme auf sie zukommen überlegen Sie erst mal welcher Schublade System überlegen Sie erst mal sind ist es unendlich schwer das Problem lösen wollen ja lösbares Problem ja aber wenn sie eine beschwerst müssen sie anders daran gehen sie wenig Zeit da man wegen 10 würden ist die irgendwas muss schnell sozusagen der Lösung die sehr schade wenn es dies nach herausstellt dass doch Polonia lösbar ist ja weil dann sagte der Kollege und was heißt es da rumgefummelt mit irgendeinem heuristische Verfahren hätte das Verfahren gegeben was in kolonialer Zeit genauso schnell kann und das sollte man vermeiden das heißt wenn in dieser Klasse den Beschwerden ist der Nachweis hat dann weiß man es gibt kaum jemand der vermutlich ein gutes Verfahren entwickeln kann das heißt es man hat eine gewisse Legitimation durchaus auch mal mit heuristischen die denen der dann auch noch das ein oder andere kennen lernen es da gibt an solche Probleme heranzugehen gut also jetzt wollen wir uns so langsam herantasten an die
Algorithmen des 1. das muss natürlich anschauen wollen sind jetzt erst mal noch solche Fälle wo man wo man Glück hat also wo man wo es zwar aussieht wie ganzzahliges Programm aber wurde Matrix stirbt und die rechte Seite so strukturiert sind dass man automatisch Ganzheitlichkeit geschenkt bekommen ja das Eis wohl Ecken alle automatisch ganzzahlig sind und diese Glücksfälle die wollen uns in Folge noch anschauen aber da gibt es nicht allzu viele Typen von Glücksfällen will die lassen sich auch ganz gut charakterisieren welche das sind mehr wo alle dazu erst mal was was heißt Glücksfall nun also Glücksfall ist die folgende Situation Definition 2 11 ein rationales Polyeder heißt ganzzahlig falls P vielleicht P ist nur das heißt wenn wir uns das anschauen wir haben hier einen Brasiliens zum per wenn er einen automatisch sozusagen so ziemlich schlecht gemalt es ist die ganzzahligen Punkte wenn man den Sieg der USA dann muss man so wir das heißt das ist unser eigentliches Polyeder wir schauen setzt die konvexe Hülle der ganzzahligen Punkte an das in unser ganzzahligen Punkte Kontexte würde davon es genau dieses teilen wir wissen ja dass er lange nationales Polyeder haben ist die konvexe Hülle wieder pro Lieder also das blaue sie dem Polieren in der Weise dass Weise mit dem blauen übereinstimmt der Sprecher von ganzzahligen Politiker ihre Wohnung soll das heißen wenn es wenn das so 1 hätten dann wissen automatisch alle Ecken sind ganzzahlig in alle Ecken ganzzahlig sind dann können wir einfach ihre Programme wenn ich sage also Al für lineare Programme anwenden also zum Beispiel Simplex ja Weißenbergs Wissmann Ende dem man optimal Ecke die Ägäis ganzzahlig damit haben automatisches ganzer Goblin genannt nur aufpassen dass Simplex dafür nicht nehmen zum Polen lität G R Simplex er hilft uns nicht an und es hat uns nicht geholfen nachzuweisen Lehrer Programmen Polen aller Zeit lösbar sind welches Simplex im wirst Geldes Weißenbergs immer noch exponentiell an das Beispiel haben unser kennen lernen kann die Würfel wacklig wie Debbie wo Auswahl des Geldes man in einen Halswirbel so falsch verdrehen kann dass der alle Ecken Abläufen damit exponentielle Laufzeit aber von unter wir müssen meldet sie mit denn die oder jene Punkte Verfahren die uns garantieren dass Apollonia Laufzeit dann haben wir so ist ein Paar Bemerkungen zu ganzzahligen polieren ist die Bemerkung am 2. 12. seit die ein rationales Polyeder dann 10 äquivalent 1. Aussage P es tatsächlich sich leicht P E das 2. ist jedes Seitenfläche enthält ganzzahligen .punkt Mitte der Aussage es jedem jemals Seitenfläche enthält in ganzer Länge .punkt enthält in ganzzahligen .punkt und die letzte Aussage ist das wenig optimieren das ist das was machen wollen maximiere CTX X aus P wird von einem ganze wird von eine ganzzahlige Lösung angenommen für alle 10 aus aber auch für die das Maximum endlich ist für die Maximum endlich hallo zudem jeweils schauen und Sinn der Übung an aber an sich im Bild damals ja schon dargestellt Mehr was heißt doch meist Seitenfläche Seitenfläche sind alle sozusagen jedes ist eigentlich minimales in dem Sinne als bezüglich Inklusion minimal wenn die kleinsten Seitenflächen also nicht trivial jede minimale Seitenfläche ungleich leere Menge natürlich ja das sind wenn Ecken gibt die Ecken
mussten ganz zeigen .punkt enthalten oder wenn es eben keine Ecken gibt dann sind das eben in die entweder ja gerade oder man zentral über ebnen wendet den ganzzahliges da muss müssen auch die Ränder sozusagen ganzzahlige .punkt enthalten und es auch so zwar dass sie lieber die minimal und was soll ich dann als Konsequenz haben wenn wir optimieren in Westberlin Jahre Zielfunktion ja über über einen Polly Truppe dem man Rand eingenommen das heißt damit muss auch sozusagen die ganzzahlige Lösung also muss auch jede die jetzt Optimierungsprobleme ganzzahlige optimale Lösung haben dass das was in den steht gut ok das vielleicht nur in dem er dann auch später immer wieder mal spielen wolle man nachweisen wollen das sind Rohleder ganzzahliges ist ja manchmal gar nicht so einfach das dann wirklich nachzuweisen ob wirklich jede LG ganzzahliges so ohne jede anzugucken was man euch die typischerweise macht es auch diese Charakterisierung zu nehmen wenn man schaut beliebige Zielfunktion an eine Liste die optimale so wenn man nachweisen kann dass es für diese dann immer ganzzahlige Lösungen gibt wenn das diese Sperre 6. Stunde auch gleich einem Beispiel sehen ja dann aber dann weiß man dass es den ganzzahliges ohne dass wir jede Ecke explizit angeschaut hat gut so jetzt wollen wir uns nach den vor sozusagen über ganzzahlige Polyeder und und empirisch Vollständigkeit des Problems uns mit solchen beschäftigen wo man eben noch Glücksfälle haben und eine dieser Glücksfälle ist totale Modularität und das ist das nächste Kapitel das heißt Tal ohne Modularität geworden noch 9 hallo wir schauen einfach noch mal sozusagen angenommen würden die ganze Herrlichkeit nicht berücksichtigen und tun so als wären alles Kunden jährliche Größen alles aus was würde es denn dann zum Beispiel des Index Verfahren am Ende liefern und da muss man mal kucken welche Eigenschaften wären die Matrix stellen können damit das Ding automatisch ganzzahliges unter wenn wir sehen wir uns das anschauen das führt genau auf diesen Begriff was man unter totaler ohne Modularität versteht gut ja da alle schauen meine linearen Welt was bei Überschrift 2 2 totale und Modularität also es Simplex Verfahren angucken dann die Hamas um Probleme minimiert CTX dämmerigen Standardformen X größer gleich 0 bisweilen immer länger als Programmen sowie wussten wenn Sie sich erinnern Zuwächse gerade neue Basen argumentiert er und der 1 ich immer sagen von Basis zu Basis glaubte jeder Basis gab ne zugehörige Basis Lösung die man Ecke entsprochen hatten und wir haben die Lösungen ausgesehen also den B der Basis sehr war eine Teilmenge von den Variablen 1 bis Ende der Kardinalität M und AB reguläre ja dann hat jede Ecke Lösung auch die optimale Lösung sieht dann so aus x p =ist gleich AB um -minus 1 b und alle anderen Xn haben auf 0 gesetzt wobei bei n gerade diesen ohne Display an so so sieht die Lösung aus ja so wir jetzt wollen dass dieses Ding ganzzahlige ist also das ging mir geschenkt hier ja das offensichtlich ganz aus er noch wenn wir das also das entscheidende ist sozusagen ja wie kriegen wir das hin dass das ganzzahlige es an und dazu bräuchten wir eigentlich das dieser Tage ganzzahlige ist dann die Klima des hin wenn sie nochmal sie sind lineare Algebra denn die kann man solche Lösungen ausrechnen wie wie kann man Lösungen zum gleichen System aus ein er will damit daraus Elimination oder man kann auch mit der dominanten rechnen sich an die keramische werden jahrelanges her für die Garage des gesagt der 10 und schwach ja ja kümmern Alemannia Lösung ist wichtig wir schauen so Komponente an ja dann stand hier unten bei der man nannte von A wie Aids in unserem Fall wir oben steht der Termin nannte von einig auch WE nur an dieser Stelle an der Ebene stellen steht sozusagen der Rektor wegen mir der Rest ist sozusagen ap aus einer Stelle setzt doch den Vektor B so jetzt wir ja wenn die Daten und davon gehen wir mal außer wenn die Daten nicht ganz sein Sinn macht zur Ganzheitlichkeit zu reden dass wir so wechseln also jetzt mal davon ausgehen dass unser A und B also sind doch im Kreuz N und außen auch ja dann wissen wir dass diese dass diese Determinante oben immer ganzzahlige Sortierung des immer ganz zu allen so jetzt garantieren möchte dessen ganzzahlige weg rauskommen sie einig fordern ja dass das Ding plus oder minus 1 ist ja nicht vor dass das plus oder minus 1 ist dann ja dann hab ich garantiert Suzanne ganzzahlige Lösungen ich sogar noch mehr garantiert nämlich unabhängig von welche von der rechten Seite diese Forderung ist sogar noch schärfer als sie eigentlich brauch ja aber jetzt wenn ich diese Eigenschaft habe dann habe ist nicht mehr viel Zeit für dieses spezielle ganz zeigen kam sondern für alle 4 ab
alle von dieser Form wieder beliebigen rechten Seite es ist scheint mir sehr steige Forderung zu sein ist es auch aber es gibt 13 Fälle in denen es auftritt und sie wollen und in noch anschauen das N-Gage gar nicht so wenige wo auftritt aber das ist ein die Grundidee dass ein womit sei technisch aufpassen müssen sind 2 Dinge einmal wir müssen das ist natürlich irgendwie für alle fordern wir wissen ja dass wir am Anfang nicht namens macht es keine Aussage sowie für Arzu zu fordern wir wissen dass wir das denn nicht wissen dass er meine was ist mein optimales B am Ende also musste sowie für alle forderten wir sonst kommt noch dazu dass ich wir sind der Form habe reicht es mir sozusagen wirklich für die im Kreuz Matrizen uns anzugucken ich aber das ist denen kleine gleich gegeben hat ist eine Teilmenge der Variablen der Gleichungen daher mit gleicher hält er für die andern völlig auch im schlug vor Jahren das heißt er muss ist einige auch noch fordern für alle unter Matrizen Gra kreuz K untermalt Mehr und dann zu Beginn einen Begriff was man nur total ohne modular verstehen doch das das ist hier eben nicht weiß vor der ist eben für alle und ist für alle fordern dann weiß ich bin auf der sicheren Seite also das ist zusammengefasst in der der Definition 2 2 13 wir A Kreuz n Matrix mit vollem Zeilen lang aha ist oder falls alle als 1. mal alles ganzzahliges also alles außen dennoch Kreuz NS und jeder Kreuz und der Matrix der Termin nannte ich +plus mir so 1 hatte man kennt das heißt um die A reicht das ist der Fall den wir hier oben haben a =ist gleich px größer gleich 0 und für den anderen Fall brauchen wir noch mehr dann das was viele K kreuz K und der Matrix fordern also B heißt total und Imola Falles jede K kreuz K und der Matrix Ralf kleiner gleich der Termin nannte +plus -minus 1 oder 0 hat an so Warnung vor mir hier nicht mehr ganz Einigkeit zusätzlich wenn es damals bei Union 0 aber gefordert falls an ganzzahlige ist und wieder im GSM und der Matrix rechts nicht mehr gefahren 1 kurz 1 ist auch ne unter Matrix ja das heißt und damit muss jeder Eintrag selber in dieser Matrix schon +plus -minus 1 oder 0 sein das heißt es einmal immer an damit automatisch an so zwischen den beiden gibt es der Reihe von Beziehungen schreibe mal vielleicht zusammen der Beobachtung 2 14 weil so bis total und im genau dann wenn e und Module es also ich kann einfach aus der Totalen oder Lane modulare machen weniger 1 20. lebt oder umgekehrt wenn ich hat hier die 1 zwar nix dann aber nicht dass die weg in muss es aber selber schon total und Imola sein das eines 2. S wenn total um die modulare ist es genau dann der Fall wenn ich kann sozusagen teilen Doppel oder in den negativen skalieren wenn dieses Ding total und oder ist alle zahlen wir nicht besoffen negativ ist sozusagen zahlen doppelt dabei hab oder Einheits spalten Zeilen dazufügen es tut mir weh und ob Zeile spalten das ist das letzte auch also alles total und modular genau dann wenn transponiert total und im oder ist wir also was jeder letztendlich steht mit dem beide zusammen ist egal ob ich Einheit Spalten dazu Aldi oder wegnehmen oder ob ich bald oder Zeit publiziert windiges 1 mach kein Unterschied mehr und das ist das was hier steht die Beziehung zwischen Uli modular einmal hier sozusagen zwischen Basis Matthes ob ich auf m Kreuz gehen kann oder K kurz K und der Marie sagen kann ich sozusagen hier von einer Welt in die angekommen ja den Beweis dazu schauen uns auch eine Übung an das ist nicht tragisch aber ist nun bis nachrechnen was wieder Fiktion ist trifft für die Frage ist wie wie es scheint werden es sehr starke Forderung zu sein die hier steht gibt es denn überhaupt solche Matrizen und die gibt es tatsächlich die des erfüllen und kann sie alles definieren was aber die ja dafür sorgen dass das da auch Dinge gibt die diese Definition erfüllen und es tatsächlich so schauen und zwar Beispiele an wer von Ihnen schon mal von Grafen und Algorithmen sowas kann wenn sagten dass Max floh Problem das wenn sagt das nächste
Fragen umgekehrt aber doch einige ok kürzesten Wege Probleme er davon noch nie was gehört vor die kürzeste jahrelang gut Marxloh ist der nicht viel was anderes oder mal ich normal sind wenn dann sagt er sagen alle schon was was geraten sind was Algorithmen Aufgaben sind und wenn man wenn man sich Bund graben man kann geraten auch sozusagen wenn die Daten speichern möchte dann kann man die gar nix bei dem man mal gerne 100 wurden kann man sie den Matrix kommt damit aus der Grafen Welt sozusagen in die wie in die wir in unsere Welt sozusagen die lineare und ganz zahlen die Programmierung swelt und was wir hiermit tun wolle sowohl das natürlich gerade Terium Grabmal können einmal anschauen immer viele der Ergebnisse aus der Graben der hier wiederfinden in der sozusagen die eigene Matrizen wählen und einige davon es sind diese Knoten kannten Inzidenz Matratzen von gerichteten Grafen als Chancen Beispiel an das ist das Beispiel 2 15 also der Mann Grafen G war ,komma li und er war das gerichtet sei die Knoten könnten Inzidenz Matrix also dass schon und zwar ein Beispiel hier Peer 4 Knoten oder wie hier kann laufen ja nicht nur die die auch mal doch von 1 2 3 4 5 wie sie dann die Matrix dazu aus Knoten kann sie Inzidenz Matrix sieht so aus ich hab ich hab so viel Seil mit Knoten und ich hab so viel spalten wie kannten ja nicht mal jetzt einfach an jeder Stelle ein in der Kante wenn in den Knoten rein geht immer so gemacht wenn die aus dem Knoten rausgeben 1 plus 1 und wenn sie einen Knoten reingehen -minus 1 also hier die kann der A 1 geht aus dem 1 heraus dass wegen jene +plus 1 sind die in den 3 eine zehnjährige -minus an die 2 bekannte 2 geht aus den 3 heraus und in den 4 war in der und so weiter also das heißt das sind schon mal die eine notwendige Bedingung ist um sich wieder für die Einträge Sinne +plus -minus 1 oder den Urlaub ich jetzt mehr gemalt also vielleicht das Formale Definition das unser aber und war es die Menge aller agiert I aus VJ aus E mit 3 J =ist gleich +plus 1 falls ja aus der DAB +plus von und -minus 1 falls J aus der Terminus von Ihnen ja ok ist die formale Definition so was die Aussage es ist diese Matrix als Zuzahlung oder La ich hoffe so wenn sich das genau anschauen was hier eigentlich steht für diejenigen die kürzesten Wege schon kennen das ginge jetzt dann automatisch wenn wir das mal anschauen wenn die Matrix anschauen einer Schauer diese nehmen wie des Matrix an als gleich 0 mit dieser Matrix was steht denn da eigentlich ich hab wie jeden Knoten Randbedingungen wir haben was steht denn da nicht fürs vielleicht doch noch mal außerdem den 3 hier anguckt dann geht hier bekannte 3 geht aus den 3 heraus und in Zweierreihen viele geht aus dem 1 heraus und in den n und der 5. geht aus dem 4. aus und in den n dran uns das ist mal anschauen wie jede für jeder Zeile hat mir nie wieder an jedem Knoten was steht jetzt hier welche als gleich 0 anschauen dann steht hier alles ist den alle kannten die aus dem 1 daraus alle Böhni rausgehen Gegenstände mit plus ja und und wir stehen alle die in der reingehen mit -minus treten sind 2 gehen nur welche reihen sich an die alle hier Minuszeichen aus dem eisigen hieraus an einem "anführungszeichen und jeder dreier musste an Kloten 3 geht der 203 heraus und ein sehr Generalen das heißt ich kann dieses Ding auch schreiben 6 anders als die Summe alle Kranken er hat aus der der Plus von Frau x f sie aufpassen das in der gleichen oder tional wird aus dort aus Ideen -minus so alle x JJ aus der Terminus von I =ist gleich 0 ja das ist das was hier steht an sondern sich es dann werden dann war man kann Wege aus so auf was nicht schicken was von A nach B und das mache ich immer so wenig los schickt dann muss einen Knoten auch was aber sicher einlaufen lassen soll wieder auslaufen wenn das was hier steht wann immer ich was Knoten reines also sich in so ein Knoten rein schien muss aber liegt die Knoten die Ausgänge verteilt werden sie bitte melden wenn man Fluss Haltungsbedingungen aber das ist in Form von Flüssen auffassen möchte und damit kann man jetzt Molly wie zum Beispiel kürzeste Weg gerne mal den Mächten kürzesten Weg von Eis nach vielen tu ich solche wich eine Einheit mit Knurren reinen das auf kürzestem Art und Weise an den Knoten 4 ankommt wenn die eine einheitliche reinschieben lieber mit zwischen Knoten Lauf da wo ihrer Einheit reinkommt soll sie wieder rauskommen das heißt es ist genau diese Bedingungen gewährleistet natürlich auf die Kosten minimieren ich auf der Bogen Kurkosten hat dann kann ich jetzt noch die entsprechende Zielfunktion formulieren minimiert CTX so auch linear unsere kann ich das kürzeste Wege Problem als zum Problem auffassen Mini-CD CDX und X gleich 0 bis auf die 2. starrenden in Knoten oder die MA in die Flüsse können den Koslow Probleme oder Max Woche bleme lassen sich genau so formulieren und das nette ist diese Matrix ist total und ohne modular das heißt wird tat sich dieses lineare Programm hier oben lösen dazu beging automatisch ganzzahlige Lösungen geschehen war das ist das was wir jetzt noch dann zeigen wollen dass den tat sich immer so ist wer den Satz bewiesen haben wir damit bis na seine können auch solche kombinatorischen Problemen aus der aus der Graphentheorie kürzeste WG ja man Koslow Probleme Marxloh Problem widersetzt sich 1 zu 1 in unsere Welt hier und wir halten auch die Ganzheitlichkeit lieber dort automatisch mit kommt der Kunde Thurgood wieso bekommen bekommt wir ja auch direkt geschenkt ja indem einfach die zugehörigen linearen Programme lösen zur den Beweis schauen uns auch wieder als Übung an zu und
damit der setzt auf seine Richtigkeit hat was ich gesagt habe aber das Ganze noch in den folgenden 2 Sätzen zusammengefasst Satz 2 16 an aus noch Kürzung allen mit vollem Zeilen Rang dann gilt das Polier X aus in Aix gleich B ist ganzzahlig für alle die aus Zeitung n genau dann wenn total ohne modularer ist ein das ja dann werden oder lass es kann aber nicht muss sowie beweisen das alle Mal aber sei und die modularen so und wir schauen uns Nike eine Ecke an seine Xperia X keine Ecke von diesem wohl jeder per so jetzt ist man aus Einführung es existierten B 3 1 1 bis Kardinalität von B vielleicht eben genau das was als links oben steht mit nächste RWE =ist gleich AB um -minus 1 b und X wer ist gleich 0 vor wenn wieder da ist so ist der Teil ist ganzzahlig und das ist aus der N und des liefert mit der Kramer Schneeregen auch ganz Ehrlichkeit ich muss aufpassen Zeitung SMS-Center aus das ist die Einrichtung also wir jetzt die umgekehrte Richtung noch also müssen zeigen dass das A und im Modul A ist das heißt wir müssen den uns der beliebige im Kreuz Matrix wir
wäre also sei AB mit B gleich regulär ja zu zeigen ist das Bett AB gleich plus oder minus 1 ist an so wir gucken uns jetzt die zugehörige Ecke an und dazu in sei X der die zugehörige Ecke also X Player mit X klären wir gleich aber es 1 B und X quer ende zugehörige Endlösung wo wir wissen mit der Me vielleicht aber auch mehr als 1 b es Element z hoch n für alle aus der doch wobei das wir sollten das für ein bisschen anders schreiben aber das Zentrum ich was sich dieselben Komponenten sind also das gilt für alle also insbesondere auch wieder Einheitsvektoren also insbesondere auch für E aus der doch er Moment das Wii einsetze weil sich jede einzelne Spalte ja ist ist ganzzahlig von den aber 1 1 B daraus folgt sozusagen insgesamt nach nachdem jede Spalte folgt aber wie es 1 ist ganz wir so ABS auch ganz ehrlich so und wir wissen wer der Männer und der Frauen aber wir 1 ist nix anderes als 1 doch die Determinante von AB ja und mit den Dreien zusammen bleibt gar nichts anders übrig als dass an der plus oder minus 1 ist Wuttke oh also damit haben wir jetzt den Fall immer noch mal rechts um schauen im Fall A X gleich B X Gesell gleich 0 weg entspricht dem um die modulare um den und Imola Anfall welches jetzt kleiner gleich erlaubt ja und größer gleich Randbedingungen dann wo sie zur zur Tarnung in Lola lität gehen bis in den nächsten Satz oder jetzt als Folgerung formuliert 2 17 aber eigentlich der obige Satz wie diese Folgerung ein zurück auf ob man und Crystal die diesen diese in Zusammenhang also eigentlich müsste es um Meister 16 Shader die diesen Zusammenhang gesehen ganz ernst wird damals zu Fuß sozusagen für den kleiner gleich Fall gleich direkt bewiesen also sei aber ganzzahlige Matrix dann ist aber total und modular genau dann den die Menge aller x A X kleiner gleich px größer gleich 0 ganzzahlig löste für alle B aus der doch also hier noch mal der Unterschied wenn zur zu Rom was sich ändert ist sozusagen jedes total kommt dazu dafür steht hier ein kleiner gleich er so verwunderlich
dass dem so ist weil wenn sie sich an 10 Verfahren erinnern sie leider seiner Tages aber wie es 1 B sehr diejenigen mit den
gleichen Halsring normalerweise ist sieht man sie als kleiner gleich B haben erfüllen sie das mit Mitschrift Variablen auf ich schlug variabel sind wenn sie in der Basis sind ja diejenigen die nicht mit gleich alten Oma 14 eben nicht der gerade Fall ja das heißt sie müssen dann dafür sorgen dass wenn schlug aus den das 1. Team aus dem AB immer noch sozusagen regulär ist und damit damit setzt ganz Ganzheitlichkeit erhalten müssen sie von diesen Rest System fordern dass dann auch die Determinante plus oder minus 1 ist also das Flemmer wie folgt zusammen also das eine was man was man haben es dieses Ding AX daher gleich X das Ganze zerlegt für alle die aus der doch allen genau dann wenn und das Schauer Sinn der Übung an wenn es Freundes ist dem ganzzahliges ist die Menge aller Z und ich einfach die Einheitsmatrix nebendran AZ gleich ganzzahlig für alle B aus ZUM es ist ja nicht schwer einzusehen da ich ganzzahlige Lösung hat da muss der Schlupf auch ganzzahlig sein umgekehrte jeden Schlupf ab und wann muss sozusagen zugehört wenn der Stoff ganzzahliges indes den ganzseitiges muss es Excel so ganz sein also dass keine tragische Übungen so
sondern ist jetzt wenn wir unseren Satzanfang oben das ist offensichtlich äquivalent Satz 2 16 also das haben wir jetzt genau in der Form derzeit größer gleich nur soll man noch dazu schreiben mir der Mann aber auch das ist nach unseren Satz dort oben genau dann wenn AI Uni oder war es und das Ding ist nach der Vorbemerkung immer am Anfang gemacht haben zwar Beobachtungen immer gleich am Anfang gemacht haben so mal gucken und so war das 2 14 wenn a total und den Modulen der es um gut zum damit damit haben wir eigentlich alle Fälle zusammen was noch fehlt ist sozusagen aber das ist die die nächste Folgerungen die die sparen uns aber vielleicht hinzuschreiben was meinen derzeitige beider machen kann ist jetzt hier noch oben untere Schranken ja ich kann Anixe sowas fordern noch dran setzen es tut nicht weh ja das Wissen aus kann diese Beobachtung bei kann Einheit Spalte oder Zeile zu nehmen oder nicht der das tut das tut überhaupt nicht weh ich kann auch hier noch größer gleich Bedingungen dran machen also von der Form ja also das wäre sowie allgemeine sehr vornehmer lineare Programme auch schreiben kann ja und da gilt das gleiche sozusagen das bleibt über bei total und die modulares weil das Merkel die beiliegenden Ungleichungen aus größer gleich 0 und Gleichungssystemen Ungleichung System drin hat wollen total ohne Modularität nun das liegt einfach daran wenn man den 10 schauen Simplex läuft immer auf gleich als Bedingung dafür Thyrsosstab variabel Lupfer variabel übernehmen die Rolle ist sozusagen um die Matrix auf vollen Zeitlang zu bringen und damit sozusagen den Uni Modularität Fall anwenden zu können also damit habe jetzt charakterisiert unter welchen Randbedingungen der Matrix im Automarkt an weniger als Umlagesystem oder länger als Programm automatisch ganzzahlige Lösungen die war und das ist sogar der Charakter Beziehung also genau dann wenn man das heißt es sind wirklich die einzigen Fälle durch alle rechten Seiten und für alle da unter Lobenstein ich jedenfalls an die Variablen hat sozusagen garantiert dass ne ganzzahlige Lösung rauskommt ja und das wollen wir dann noch ein bisschen erweitern für Matrizen Dino +plus +plus 1 und 0 enthalten die für die Hilfen muss dann aber auch mit interessanten Anwendungsfall wir schauen aber dann am Mittwoch an der
Lösung <Mathematik>
Länge
Zusammenhang <Mathematik>
Momentenproblem
Laufzeit
Klasse <Mathematik>
Schnittmenge
Diskrepanz
Schnitt <Mathematik>
Ganzzahlige Lösung
Computeranimation
Mathematische Größe
Mathematik
Pfad <Mathematik>
Laufzeit
Klasse <Mathematik>
Modifikation <Mathematik>
Baum <Mathematik>
Aussage <Mathematik>
Tiefe
Formation <Mathematik>
Disjunktion <Logik>
Norm <Mathematik>
Entscheidungsbaum
Computeranimation
Komplexitätstheorie
Entscheidungstheorie
Variable
Menge
Würfel
Siebzig
Zustand
Minimalgrad
Vorlesung/Konferenz
Mathematik
Laufzeit
Physik
Klasse <Mathematik>
Heuristik
Komplexitätstheorie
Richtung
Teilmenge
Variable
Menge
Ganze Zahl
Pore
Vorlesung/Konferenz
Mathematisches Problem
Mathematische Größe
Ebene
Länge
Punkt
Matrizenmultiplikation
Simplex
Laufzeit
Maximum
Ganzzahlige Lösung
Index
Variable
Vollständigkeit
Ganze Abschließung
Stützpunkt <Mathematik>
Zielfunktion
Inklusion <Mathematik>
Einfach zusammenhängender Raum
Polyeder
Determinante
Konvexe Hülle
Vektor
Teilmenge
Lösung <Mathematik>
Menge
Würfel
Lineare Algebra
Ecke
Matrix <Mathematik>
Matrizenmultiplikation
Total <Mathematik>
Dimension 6
Reihe
Gleichungssystem
Fluss <Mathematik>
Kante
Randbedingung <Mathematik>
Inzidenzalgebra
Ganzzahlige Lösung
Maßeinheit
Teilmenge
Summe
Variable
Menge
Ganze Abschließung
Vorlesung/Konferenz
Zielfunktion
Graphentheorie
Einfach zusammenhängender Raum
Zusammenhang <Mathematik>
Menge
Determinante
Betrag <Mathematik>
Momentenproblem
Vorlesung/Konferenz
Randbedingung <Mathematik>
Rang <Mathematik>
Ganzzahlige Matrix
Ecke
Richtung
Variable
Menge
Determinante
Ganze Abschließung
Vorlesung/Konferenz
Ganzzahlige Lösung
Matrix <Mathematik>
Variable
Untere Schranke
Bimodul
Ungleichung
Matrizenmultiplikation
Simplex
Uniforme Struktur
Vorlesung/Konferenz
Randbedingung <Mathematik>
Ganzzahlige Lösung

Metadaten

Formale Metadaten

Titel NP-Vollständigkeit, totale Unimodularität
Alternativer Titel NP-Vollstaendigkeit, totale Unimodularitaet
Serientitel Diskrete Optimierung (Optimierung II)
Teil 06
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/31790
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...