Nächste Seite: 2025-07-18 ...before ...pwdgen20250605.sh Aufwärts: The 11 ... Vorherige Seite: 2025-07-18 ...before ...nasm20250704sort.o
(C) David Vajda as Excerpt
2025-06-08
NP-Vollstaendigkeit
leichtes problem
schweres problem
nochmal:
leichtes problem
schweres problem
manchmal nur durch haarfeinen unterschied gegeben #
effizienter algo
durchschnittlicher fall
unguenstiger fall
graphentheorie, mathematische grundlagen
bitte trotz oekonomie bitte ueben
sha, gut, mit division und rest gutes thema
aufbau von zahlen
maedchen feiern, nicht schlimm, typ kommt: hey girl party, toll, aber
ganze zahl, kein thema, geile kurve, ehrlich, aber schau mal
mathematische grundlagen, aufbau zahl und
du kannst darauf verzichten, wenn du mathematik kannst, weil, das praktische problem
mit dem du zu tun hast, ist eigentlich nur eine verschiebung, du musst nur die kleinste einheit nehmen #
beispiel: AD-wandler, Atmega8, 256 werte
fourier-reihe ich einigermassen verstanden, interessant, FFT
warum: ich kann ein wenig Lempel Ziv, aber no problem, du kannst mit Atmega8, sound machst smartphone und co #
egal, du kannst lernen SMS protokoll und co. du musst komprimieren, FFT, oder Lempel Ziv
oder besser, du musst: Hash, du musst, Pruefsumme, du musst IBAN, du musst Abakus und Co#
was fragst du. dann kommt signal, da gibt es: gausfunktion, irgendwelche peaks, du fragst, hae, berechnen
es gibt ein buch: da sind funktionen drin, auf oszi, fuer nachrichtentechnik, du musst nur gucken, form #
hat namen
was willst du? SMS nur protokoll: musst pruefsumme und immer das gleiche brauchst ganze zahlen ...
ok, bitte
trotzdem an mich: graphen zur uebung machen, std. uebung jeden tag. geht nicht drum ob kurs entsprechend bis zum naechsten #
mal ueben einfach
das ist wie quine mc cluskey, schaltwerk in der computersysteme i/ii #
brauchte - 15 jahre oder so
jetzt robert sedgewick, kommt mit np vollstaendigkeitsproblem, was sehe ich
gleichung der booleschen algebra
bei problemen, deterministisch, nicht deterministisch, np vollstaendigkeit
haette nichts verstanden
... ok und ich denke, so muss es jetzt auch sein, algo mathematik lernen, immer weiter
uebung, uebung, uebung, irgendwann flow
also, erstes problem,
algo mathematik ist wie cs i/ii
cs 12 ist mathematik
algo mathematik immer machen uebung, uebung, uebung, spaeter pruefung...
ok, das ist mein problem, der flow
und dann geht es: naechstes thema, wir brauchen ueberall graphen
graphen, graphen, graphen, ...
und nebenbei ganze zahlen, wegen pruefsumme und co kg
aber, graphen: nie genug, habe noch skript, erweitert das problem
was fuer uebungen, ohne kurs einfach
euler, euler, euler
tiefensuche, breitensuche
und ein paar std. uebungen
gut, damit beim thema
anschauliches beispiel:
finde den kuerzesten pfad vom knoten x zu knoten y in einem gegben gewichteten graphen
algo math:
G=(E,V)
Pfad: P_n = (v_i, v_(i+1), ..., v_(i+m))
mit e_(i+1) = (v_(i+1), v_i)
irgendwie so, was halt ein pfad ist,
was ist ein kuerzester pfad
na ja, ein pfad ist menge
wenn |P_n| < |P_m|
fuer alle m, dann ist ersterer der kuerzeste, irgendwie so
viele definitionen wahrscheinlich, die anzahl der kanten, ...
deg(...)
es gab auch eine laenge und so
ich sage nicht jetzt, aber drueber nachdenken
pfad, robert sedgewick
mit zyklen
und ohne
drueber nachdenken, nicht jetzt aber spaeter
1.) wie lautet der kuerzeste pfad
2.) frage:
problem: np vollstaendigkeit
beim lernen, wo einbauen
ich finde, ehrlich gesagt, dass Hash werte gut in algo math passen, weil
da aufbau von zahlen pruefsumme immer gut
ich finde dass np vollstaendigkeit und all das laesst sich auch gut da unterbringen
drueber nachdenken, nicht jetzt aber spaeter
1.) wie lautet der kuerzeste pfad
2.) frage: wie lautet der laengste
gute frage, sedgewick
was ist mit zyklen
gut bedingung, ich darf einen zyklus nur ein mal durchlaufen.
ich finde dieses problem jetzt nicht so extrem kompliziert, weil ich kann
ja schlicht ergreifend den kreis nur so betrachten, dass er durchlaufen werden
muss so viele knoten wie im kreis
umgekehrt, frage ich mich: wenn ich viele kreise, eulertour habe, dann muss ich einfach alle durchlaufen
frage: geht es geschickter?
ich wuerde sagen, natuerlich nein, nur: dann muesste ich nur alle kreise zusammen tun
ich muesste ausprobieren wie besser
doch eulertour: egal, wie: die anzahl der durchlaufenden kanten bleibt die gleiche
ich kann so gehen oder so
irrtum: ein knoten mit 6 kanten ich gehe 3 mal rein und 3 mal raus,#
aber ich werde so oder so, bei einer eulertour immer gleich brauchen
was automatisch die loesung des problems darstellt, der laengste weg
es ist die eulertour
weil: die eulertour
falsch gedacht, wenn x gleich y ist, wenn beides x ist, anfang und ende gleich
dann ist es die eulertour
und wenn nicht, lautet die frage:
ich soll den laengsten weg nehmen, ich koennte so ungefaehr, vielleicht
zwei eulertouren nehmen, wie hier, muss ich jede kante bedienen
das waere doch eine idee
so oder so, selbst, wenn
x und y nachbarn
das entspricht nahezu: x = y
auf einem kreis, liegen sie dann nebeneinander ...
aber: wenn nicht, dass ist dasselbe problem wie bei der eulertour
es soll ja der laengste weg sein
ich muss also nur das machen
indem ich jede kante ablaufe, ein mal, mehr ist nicht erlaubt, habe ich automatisch
dasselbe problem
nur eine frage
sind es genau zwei knoten
x und y
dann lautet die antwort:
sind x und y im selben kreis
dann aehnlich wie: x=y
aber abzueglich der distanz von x und y im selben kreis
die frage, nach dem laengsten wege, kann keine kante doppelt gegangen werden, ist es die eulertour
dann frage: x und y sind nicht im selben kreis, bleibt das problem der eulertour
x im ausgangskreis, mit einem letzten unterschied
der kreis, in dem y ist und den muss es geben und nicht zwei mal
....
dann muss ich nur diesen kreis gesondert betrachten
er bringt irgendwo abzug
...
auser, ..
y hat 20 nachbarn oder 16 oder so
und kommt dazu, x auch noch und so
aber glauben wir, der laengste weg ohne zyklen
robert sedgewick sagt nicht besser, als pruefen aller pfade.
why, problem
ist tiefensuche, breitensuche mist
kann ich nicht glauben, letzten endes, wenn kein zyklus
er sagt, pruefen aller pfade, kein zyklus, heist kreisfrei
heisst baum, bedeutet,
ich finde das komisch, ehrlich gesagt, weil
er sagt, kein algorithmus besser, als das ausprobieren aller pfade in mathematik
ich glaube an sein problem, aber in diesem zusammenhang?
tiefen und breitensuche
was habe ich in algo mathematik gelernt
in einem baum, kreisfreier graph, fuehrt immer genau ein pfad von einem knoten zum anderen.
das ist eine relativ einfache sache, ich muss zu der wurzel, bei einem baum kann alles eine wurzel
sein ich muss ihn nur umdrehen
ich muss den baum in zwei baeume zerlegen, in den einen teil
ich waehle willkuerlich irgendeine wurzel, irgendwo
abhaengig von der, waehle, ich bei einem binaeren baum
und: jeder kreisfreie graph, der zusammenhaengend ist, aus einer komponente besteht, ist
ein baum, ich kann auch keine falschen pfade gehen, sonst muss ich zurueck, das geht nicht
gut, und: ich gucke, ausgehend von der wurzel, in welchem teil ist der knoten x und y irgendwie so
drueber nachdenken ...
gut, gehen wir davon aus alles ausprobieren
aber, das ist reiner bloedsinn
in einem graphen mit kreisen, gesetzt aus y gehen nicht 20 pfade rein und raus, aber dann bleibt eine eulertour
abzueglich
und ein baum, es gibt nur einen pfad, der zwischen x und y verlaeuft
nur einen..
gut
angenommen ich muss alles ausprobieren
sie haben recht, das problem ist es trotzdem
ich muss von der wurzel, zu den blaettern oder von den blaettern zu der wurzel, wo auch immer
diese willkuerlich gewaehlt, was einfach aussieht, bei ueblichen baeumen
sie haben ja recht, nur:
ich habe das so nicht kritisiert, warum so aggro: sie muessen erst mal argumentieren und nachdenken und nicht so tun.
ja, so ein baum,
wenn man so java und c nimmt, sieht klein nett aus, darum geht es ja nicht, es ist die frage, nach der effizienz
des algos, optische taeuschung
wie so oft. selbst, wenn: es nur 10 blaetter waeren, das problem bleibt
ok, dabei muss man bei einem baum klassischer weise nach links und rechts gehen, bis man kann
tiefensuche breitensuche klingt nett, ist aber das
in wirklichkeit std. algorithmus links und rechts
egal
kuerzeste pfad einfach
laengste pfad schwierig
aber das ist ja der unsinn, mein herr da draussen, du sagst,
aber wo verlaeuft das
das ist doch stumpfsinn
in einem kreisfreien graph, das ist dein stumpfsinn, lange oder nicht,
da steht
ach so, da steht den laengsten pfad ohne zyklen
ok, das sieht aus, nicht graph ohne zyklen und den laengsten pfad
sondern graph mit zyklen und laengster pfad, ohne zyklen zu machen
dann versagt eulertour und
aber das ist trotzdem doof
kreis, darin gehen 2 rein, 2 raus,
kurz der kreis, liegt so dran
ja und nun muss ich den zyklus gehen?
ohne zyklen also nein
aber knoten uebergangen, die nicht drin
...
und wenn ich das mache, automatisch
und so on
leichte: existiert ein pfad von x nach y mit einem Gewicht <= M
schwer: existiert ein pfad von x nach y mit einem Gewicht >= M
ok, sagen wir, ok
Breitensuche, erstes problem: lineare Zeit
Zweites problem: Exponentiell
nichtdeterminismus leicht gemacht
beispiel:
breitensuche
tiefensuche
ich muss raten
das geht einfach so, ich lege einen knoten in die schlange
dann gehe ich zu seinen nachbarn
ich lege alle wieder auf die schlange und mache so weiter
ich nehme den ersten nachbarn runter und wieder alle
ich rate. dieser weg oder dieser???
da steht deterministisch: der computer kann als naechstes nur eine sache tun
z.B. vermute ich:
eine schleife soll nach oben zaehlen und dabei, irgendeine zahl mit einer anderen multiplizieren
eine operation
oder hashtabelle
anderes, vielleicht: sortieralgorithmus, ich muss mich zwar entscheiden,
das ist ja so ungefaehr n!
ich habe eine schleife i und j und j wird entweder immer groesser oder kleiner
wie bei 4! = 4*3! dabei ist 3! gesondertes problem
3! = 3*2!
das entspricht so etwa, der sortierung
aber ich muss nicht entscheiden
graph, hier lang oder da lang
4 oder 6 nachbarn
eigentlich alle ausprobieren, aber
uebrigens, ergibt wald
aber ob ich jetzt hier, 1, 2, 3, 4 gehe ist hat auswirkungen auf das naechste, wo wieder
anders sortierung
ok,nicht deterministisch
ich brauche beim einsortieren einer zahl laenger oder kuerzer, aber sie wird irgendwo landen es hat #
keine auswirkungen auf das andere #
und ein prozess ist immer gleich lang
also, kein problem
es dauert immer j. oder m-j wie auch immer.
anderes problem:
schulmathematik
a*x^2 + b*x + c
mitternachtsformel
aber bei hoeherem ...
und nicht nur das
bei boolescher algebra, ich sage, ja kein problem
wahrheitswerte einsetzen gleichung aufstellen ja oder nein
ich sage: easy ist nicht so easy
ich muss ja alle werte einsetzen
bei 2^3 sind das 8 zeilen
und bei 2^64 ein haufen
aber man koennte sagen x0 ist abhaengig von x1 ist abhaengig von x2
je nachdem, weil ich oben anfange, mich entscheiden muss, ist x2 nun 0 oder 1
kommt es zur unterunterscheidung, x1 0 oder 1, jeweils 1 mal fuer ersteren der beiden faelle.
erfuellbarkeitsproblem
gibt es einen eingabevektor, der die gleichung wahr werden laesst
wann ist man wahr
gibt es ueberhaupt einen?
schulmathematik: glauben vermitteln, mit mitternachtsformel wert da, eingabewerte kriegt man raus
nicht so einfach: lineares newtonsche irgendwas ...
da bool auch variable, eigentlich klingt easy nicht besser, wie newton irgendwas.
das problem ist seltsam
weil ich muss nur die DNF aufstellen, mehr nicht
und wenn ich die habe, erfuellbarkeitsproblem
sobald ich die DNF habe, und die muss entstehen #
ist einfach nur die aussage, es geht nicht,
ich kann zwar fragen wie oft
ich kann zu jedem ausdruck eine dnf finden
und eine dnf muss jedesmal mindestens ein mal 0 sein und alle anderen 1 oder mindestens
ein mal 1 und alle anderen 0
ganz einfach, das geht nicht
und waeren es immer 1
dann umgekehrt: quine mc cluskey loesst sich die gleichung auf, das heisst es gibt sie nicht mehr.
das waere eine dnf, in der es so viele min terme gibt, wie ueberhaupt zeilen in der gesamten dnf
der stumpfsinn liegt in der erklaerung
wuerde ich einen compiler benutzen, optische taeuschung der aus irgendeinem
booleschen ausdruck sprachlich eine dnf mit lauter min termen macht, sieht das bei drei variablen
ja relativ einfach aus. what is the problem
falsch, tiefensuche und breitensuche sehen sehr easy aus bei 8 knoten
trotzdem, easy oder nicht, die mathematische laufzeit bleibt
2, 8 oder 16k knoten
das gesetz bleibt ist entsprechend proportional wie auch immer
optische taeuschung, weil im buch 4 knoten
so auch: die dnf, no problem
bei drei variablen sieht so aus, und der compiler macht den rest
blos wie lange braucht der?
das ist die frage: probiere ich alles aus, gut, entscheidbarkeit
brauche lange, denke ich. aber ich stelle alles um, compiler
gut, nur der compiler braucht eben wieder zeit, robert sedgewick lacht
ob der compiler n^2 braucht oder 1, ist egal, als ob es die entscheidung macht
optische taeuschung 3 variablen oder 64, sieht anders aus
glaube nicht an 64, nur: proportional vielleicht letzten endes, bei 3 nicht besser.
graph anders, hier hat ersteres problem auswirkungen auf das naechste