[SCRÂȘIT]
[FOȘIT]
[CLIC]
JUSTIN SOLOMON: Așadar,
astăzi, vom
continua discuția
despre programarea dinamică.  De
fapt, am găsit acest set
de probleme legate de sesiunile cu probleme
ca fiind mai ușor decât
precedentul.
Există un
lucru amuzant, care este că am
învățat în clasă despre programele dinamice în
stil pseudo polinomial
.
Cumva, acel limbaj este
puțin eliberator,
în sensul că folosești
parametri pe care chiar
nu ar trebui, când vine vorba de timpul de
rulare al algoritmului tău.  Ei
bine, presupun că ar trebui, în
sensul în care este permis,
dacă numiți algoritmul dvs.
timp pseudo polinomial.
Dar, într-un fel, este
puțin mai ușor
să formulezi
algoritmul tău de programare dinamică,
deoarece toate numerele
te privesc drept în față.
Nu trebuie să fii atât de
atent la ce este un joc corect
și ce nu, atunci când postezi
algoritmul, atâta timp cât este
eficient în valorile la
care îți pasă.
Așadar, sesiunea de probleme de astăzi
are cinci probleme stors în loc
de cele patru obișnuite.
Vom vedea cât de departe ajungem,
văzând că
oricum de obicei vorbesc prea mult.
Dar voi încerca să rămân
în program aici
și vom vedea cât de bine ne descurcăm.
Aveți întrebări de la studenții noștri
despre programarea dinamică
înainte de a începe aici?
PUBLIC: Puteți
tăia unul, dacă doriți.
JUSTIN SOLOMON: Putem tăia unul?
Oh, voi tăia cu plăcere
unul dacă voi rămâne fără timp.
Da.
OK, deci fără alte
prelungiri, să
începem cu monede,
care este problema 9-1 aici.
Așa că presupun că ar
trebui să fie Ceal Naffrey,
dacă ar fi să-mi rezolv
cum trebuie aici.
În orice caz,
avem un hoț care are
nevoie disperată de bani,
la fel ca mulți hoți, altfel,
desigur, nu ar
recurge la lumea primelor.
Și Ceal Naffrey
are aici n monede identice.
Am fost foarte
conștient de felul în care
scriu scrisoarea I, de
când Eric a subliniat-o,
și s-a înrăutățit doar.
Acum este inconsecvent
și greu de citit.
Dar, în orice caz,
avem n monede identice.
Și, desigur, aceste monede
au marcaje foarte distinctive.
Și așa că nu putem
fugi cu ele
așa cum sunt, pentru că dacă
le duci la bijutierul tău standard,
ei vor recunoaște imediat
că aceste marcaje sunt
rele și furate.
Și asta nu e așa de bine.
Deci, în schimb, putem topi aceste
monede în alte obiecte.
Așa că hoțul nostru ascuns de aici a
identificat un potențial cumpărător.
Și cumpărătorul are
câteva criterii aici.
Deci avem un cumpărător, iar
cumpărătorul are un sistem de valori foarte ciudat
, că
aparent, este
ușor să iei monede și să
le transformi în alte lucruri.
Dar, în orice caz,
cumpărătorului, ceea ce îi pasă
nu este faptul că
monedele sunt făcute din aur,
ci mai degrabă că îi plac
anumite obiecte mai mult
decât altele făcute
din aur menționat.
Deci, în special,
au o rată diferită
pentru fiecare obiect, un
preț diferit pe care sunt dispuși să-l plătească.
Și astfel au o
listă de n obiecte de
care sunt interesați.
Și fiecare este asociat
cu două lucruri din n obiecte.
Au un preț,
deci suma pe care
cumpărătorul este dispus să o plătească
pentru acel obiect, care, din nou,
nu este doar greutatea în aur,
dintr-un motiv oarecare.
Există o taxă pe valoarea adăugată
în acest univers.
Și este nevoie de un
număr diferit de monede pentru fabricare.
Dreapta?
Așa că poate pot face o
fântână de ciocolată aurie
și asta necesită 10 monede.
Dar nu vreau două dintre ele.
Deci, dacă fac asta, atunci
următorul lucru pe care trebuie să-l fac
este o figurină cu Eric și
Jason pe care să o pun alături.
Și să ai mai multe
dintre acestea
ar fi, de asemenea, înfiorător și ciudat.
Deci nu pot face decât
unul din fiecare obiect.
Și, desigur, scopul meu
aici este că am n monede.
Apropo,
faptul că există
n monede și n obiecte pentru
cumpărător nu prea contează.
Adică, va fi pentru timpul de rulare.
Dar vă puteți imagina că
acesta este n și m.
Așa că nu aș fi
prea obosit de asta.
Și ceea ce încerci
să faci este, desigur, să-ți
maximizezi veniturile,
sub rezerva constrângerilor
că ai n monede
și nu poți face
două obiecte care sunt la fel.
Sper că am surprins
esența problemei noastre OK.
OK, fabulos.
Deci, ca și în cazul tuturor
problemelor noastre de programare dinamică din 6006,
avem o paradigmă despre
cum să le abordăm,
care are un
acronim drăguț, care este SRTBOT
și cred că SRTBOT este o abordare total
relevantă și simplă
a acestei probleme aici.
Da, deci, în special, să
ne acordăm
un pic de notație.
Deci ne vom numerota
obiectele între 1 și n,
doar pentru comoditate.
Deci vom spune că Pi este
prețul obiectului i.
BINE.
Și vom spune că Ki este
ceea ce problema numește
numărul de topire.
Cu alte cuvinte, dacă
vreau să fac obiectul i,
aceasta este cantitatea de
monede pe care ar trebui să le
topesc pentru a face acel obiect.
BINE?
Deci doar o mică notație.
Și în general,
deci OK, ce
facem când ne formulăm
problemele de programare dinamică?
Unele probleme pe care le-am putea
rezolva sunt mai mici.
Și când
le compunem pe toate împreună,
obținem
soluția finală la problema noastră.
Și această problemă specială, care
implică fabricarea de obiecte
din monede, cred că este
una cu adevărat clasică, când
vine vorba de programare dinamică.
Acesta este genul de
lucruri în care într-o zi,
când încerci să-ți
plătești școlarizarea
participând
online la aceste concursuri de hackeri,
acesta este genul de lucruri
care apar tot timpul
în acel univers, nu?
Deci, în special, cele
două variabile de aici,
când fac un obiect nou,
este ce obiect am făcut?
Și câte monede
am cheltuit când am făcut asta?
Deci, aceștia sunt cei doi
parametri naturali
de utilizat, atunci când îmi rezolv
problema de programare dinamică.
Da.
Și, desigur, va
fi recursiv, în sensul
că pot alege
să fac obiectul i sau nu.
Și nu contează în ce
ordine îmi fac obiectele
sau, în mod similar, în ce ordine îmi
cheltuiesc monedele,
ceea ce este de obicei o
proprietate frumoasă
într-un
univers de programare dinamic.
Deci, în special... oh,
chestia asta este dușmanul meu.
Aceasta este fata.
Cred că această clasă
este deosebit de
grea pentru oamenii scunzi, deoarece se
mișcă în sus și în jos tot
timpul.
OK, deci având în vedere observația noastră
aici, dacă facem SRTBOT,
deci care este S-ul nostru din nou?
Lasă-mă să mă întreb că...
Sub-probleme.
Mulțumesc, domnule profesor Demaine.
Apoi, în esență,
ceea ce vrem să facem, pe
baza a ceea ce am argumentat
verbal, este poate
să definim variabila noastră
x i, j lucrul pe care îl vom
calcula, să fie
venitul din folosirea i monedelor
și obiectelor de la 1 la j.
BINE.
Deci, cu alte cuvinte, am
i monede rămase în bancă
și am voie să
folosesc doar primele j obiecte.
Și putem deja să vedem că
aceasta este o modalitate sensibilă
de a aborda această problemă de
programare dinamică
, în
sensul că există
o recursivitate evidentă aici.
Aleg să fac un obiect.
Am mai puține monede.
Și îmi pot imagina într-un fel că
există o ordine topologică,
în sensul că aș putea
decide mai întâi despre obiectul 1,
apoi despre obiectul 2 și despre obiectul
3 și așa mai departe, sau invers, în
funcție de faptul că ești un
prefix sau  sufix fel de tip-- pe
care încă îl primesc înapoi.
Dar vestea bună este că
nu prea contează.
Ceea ce contează este
formularea ecuației.
OK, vreo întrebare despre
definiția noastră a lucrului

după care vom urmări aici?
Fabulos.
Ah-- OK, corect.
Deci, să continuăm SRTBOT.
Deci următoarea noastră piesă
a puzzle-ului nostru aici
este R. Cred că R
înseamnă recursivitate.
Acesta este un
acronim nou și pentru mine.
Deschide, nu, relatează.
Dar ar putea la fel de bine
să fie Recursie
pentru majoritatea acestor probleme.
Corect, deci relația de bază
aici este că, desigur,
pot fie să folosesc obiectul j,
fie nu pot folosi obiectul j.
Și în ambele cazuri,
dacă j este ultimul tip pe
care îl voi lua în
considerare, aceasta va
fi o
regulă recursivă total rezonabilă, nu?
Deci, în special,
am că xi,
j pot lua în esență
una dintre cele două valori.
Asta e o paranteză, în
caz că vă întrebați.
Și, desigur, încercați
să vă maximizați veniturile.
Deci hai să facem asta, ok?
Deci avem două
posibile opțiuni.
Dar trebuie să fim puțin atenți.
Există un caz în care
nu pot face obiectul j?
Da, clasa, exista,
care este cazul in care
nu mai am suficiente monede
in banca, nu?
Așa că vreau să fac
fântâna aceea foarte scumpă,
dar am doar o monedă.
Atunci am ghinion, nu?
Deci, să facem aceste două cazuri.
Deci, mai întâi, dacă... hopa, mi-am
luat cazurile înapoi.
Asta e ok.
Dreapta.
Deci, să spunem că aleg
să nu fac obiectul j.
OK, deci ce înseamnă asta?
Deci am cheltuit monede?
Nu.
Și în plus, care
este profitul meu maxim?  Ei
bine, va fi
același cu profitul maxim,
folosind obiectele de la 1
la j minus 1,
pentru că nu am folosit obiectul j.
Da?
Deci, în special,
acesta ar fi x.
Să vedem, l-am luat
înapoi în notițe,
așa că o vom face
live, așa.
BINE?
Și altfel, să spunem că am
ales să fac obiectul j.
Ei bine, ce sa întâmplat?
Deci am primit niște
venituri acum, nu?
Omule, ce naiba
am scris pe aceste notițe?
Deci primesc prețul
obiectelor j aici ca venit.
Dar am cheltuit câteva
monede în acest proces.
Deci am i minus K sub i,
care este numărul de monede.
Ce-i asta?
PUBLIC: K sub j.
JUSTIN SOLOMON: Oh, mulțumesc... îmi
pare rău, K sub j.  De
aceea ar trebui să fim
consecvenți cu indicii noștri
atunci când notăm aceste lucruri.
Așa că am cheltuit K sub j monede
făcând acest lucru, obiectul j.
Și mai mult,
încă pot alege să fac
oricare dintre obiectele anterioare.
Deci tot este doar j minus 1.
Dar trebuie să fiu atent,
pentru că nu pot face asta întotdeauna.
În special, acesta ar fi mai bine să
fie un număr pozitiv pentru n,
sau cel puțin un
număr nenegativ.
Pentru că dacă ajung cu un
număr negativ de monede, ei
bine, acesta nu este
un univers fizic în
care aleg să mă aflu.
Deci, în special, ceea ce
avem nevoie, într-un anumit sens,
este i minus k minus
j și k și j
să fie mai mare
sau egal cu 0.
Sau echivalent, i este mai mare
sau egal cu K sub j.
Cred că ați putea
face asta acasă.
OK, și aceasta este recursiunea noastră.
Sper că am înțeles
bine, pentru că nu este de acord
cu lucrul nebunesc pe care l-am scris în
notele mele ieri la 1:00 AM.
Dar cred că este
destul de simplu.
În esență, fie pot
alege să folosesc ultimul obiect,
fie aleg să nu o fac.
Și oricare dintre
acestea, desigur,
scade j, pentru că
acesta este indicele
obiectului pe care îl iau în considerare.
Și fie contabilizez
prețul, dar trebuie să plătesc în aur,
fie nu țin cont
de preț.
Deci, implicit, există un 0 și
nu trebuie să plătesc în aur.
OK bine.
Bine, deci hai să
continuăm cu SRTBOT.
Ne-am putea, mai târziu în
sesiune, să ne relaxăm
parcurgând fiecare
dintre acești pași,
deoarece multe dintre
argumente sunt similare.
Dar, deocamdată, vom face
una sau două cu atenție.
Deci T, cred,
reprezintă ordinea topologică.
Și aici,
ne privește în fază.
Pentru că observați că
xi, j depinde doar
de x semn de întrebare,
virgulă, j minus 1.
[Râde] Nu?
Deci, bineînțeles, pe
setul de probleme, ar
trebui să scrieți
lucrurile cu mai multă atenție.
Dar punctul de bază
aici este că există
o ordine topologică clară
, doar privind
acel al doilea indice.
Pentru că dacă te gândești la toate
x-urile tale ca variabile într-un grafic, pe
care de fapt le-am
desenat în prelegere --
deci poate acestea sunt toate
i-urile și apoi j--
așa că i coboară, iar
j merge la dreapta.
Apoi, în esență,
acest argument
spune că toate săgețile
indică la stânga în acest grafic.
Presupun că felul în care mi-am desenat
săgețile nu este tocmai exact.
Dar de fapt nu contează.
Singurul lucru care
contează este că
merge de la dreapta la stânga.
Dar o să șterg asta,
ca să nu-ți amintești.
BINE.
Deci, în general,
exact atunci când doriți să
faceți
argumentul ordinii topologice,
cred că cel total
sensibil se
uită la
indicii de recursivitate
și apoi încearcă doar să găsească
un număr care scade.
De altfel, dacă urmezi un
curs de ecuație diferențială,
cam așa demonstrezi
că și multe dintre aceste lucruri
converg.
Deci, există o verificare matematică generică pe
care o folosim foarte mult.
Cum numiți asta
în ODE unde există
un număr care scade?
PUBLIC: Aș numi
această funcție potențială.
JUSTIN SOLOMON:
Funcția potențială...
aceasta este una perfect sensibilă.
Nu este Lipschitz.
Este un alt matematician.
Oricum, OK, deci să
continuăm SRTBOT.
Deci în continuare avem nevoie de B,
care este cazul nostru de bază.
Deci, în acest caz, este
destul de simplu.
Dacă nu am nicio monedă,
nu pot face niciun ban.
Am acasă un tricou pe care
scrie asta.
Și mai mult, dacă
nu pot să vând nimic,
nu pot face niciun ban.
Deci sunt
cazuri destul de simple.
Deci avem că 0
este egal cu x de 0, virgula j.
Amintiți-vă, primul index este
numărul de monede pe care le aveți.
Deci asta înseamnă că
nu pot face nimic.
Nu am nicio monedă.
Și, în mod similar, este egal cu x
i, virgula 0 pentru tot i, j.
Deci acestea sunt monedele
și obiectele.
BINE.
Deci, să vedem.
Continui să scriu aceste
sesiuni cu probleme prea mari
și apoi petrec
jumătate din ele ștergând.
Deci haideți să încercăm să punem
asta pe o singură placă aici.
Deci vom face SRTBOT.
Apoi al doilea -
nu, primul O,
pentru că nu există O în SRT --
este problema inițială pe
care doriți să o rezolvați.
Deci, desigur, începeți
cu n obiecte și n monede.
Deci problema inițială pe care
vrem să o rezolvăm
este echivalentă cu
calculul x venit n.
Și apoi, în sfârșit,
trebuie să ne facem timpul de rulare.
T înseamnă runtime,
sau Time, presupun.
Deci, în primul rând,
câte probleme sunt?  Ei
bine, există x i, j.
Ambele pot merge de la 0 la n.
Aceasta este o
modalitate excelentă de a fi oprit cu 1.
Deci, există n plus 1
subprobleme la pătrat.
Și câtă muncă face
fiecare sub-problemă?
Ei bine, face o treabă plictisitoare.
Este doar o formulă.
Dreapta?
Deci, este comandat 1
lucrare pentru fiecare sub-problemă.
Deci algoritmul general
durează n timp la pătrat.
Așa că am promis că voi face ceva
în ultima noastră sesiune cu probleme.
Atunci nu am făcut-o de fapt.
Așa că m-am gândit că voi petrece
doar un minut aici traducând
ce ar însemna acest lucru SRTBOT
în termeni de cod.
Pentru că cred că
aici este puțin implicit.
În special,
cred că acest pas aici,
adică, veți vedea
că în mod clar

vă va oferi un algoritm.
Dar cred că este ușor
să, din nou, doar să uiți cum
arată codul tău de fapt.
Și, de fapt,
problemele de codare
din aceste sesiuni cu probleme
sunt aproape prea interesante
și le pot ascunde puțin.
Așa că m-am gândit să
facem o problemă plictisitoare
și să-ți arătăm că nu este chiar
atât de greu să faci asta.
Și, de fapt, am acoperit două
strategii diferite în clasă
pentru a lua
SRTBOT și a-l converti
într-o bucată de cod.
Deși, s-ar putea să fi trecut
pe lângă tine în acest lucru de 2x viteză pe
care îl poți face acum.
Deci, aici sunt două opțiuni.
Una dintre ele se
numește memorare.
Și cealaltă, nu
știu, de jos în sus, cred,
este o
expresie rezonabilă de descris.
Și așa m-am gândit să
le facem pe amândouă,
pentru că amândouă sunt ușor
pentru această problemă specială.
BINE.
Dreapta.
Deci hai să facem asta.
Deci este necesar acest lucru
la temele tale?
Strict vorbind, nu.
Dacă ați trecut prin SRTBOT,
atunci, în esență, tot ceea
ce se întâmplă după
aceea este boilerplate,
în ceea ce privește convertirea acestor
pași într-o bucată de cod
sau un algoritm.
Dar cred că, doar
pentru a înțelege de
ce SRTBOT are
sens, merită să ne
gândim un minut.
Deci, opțiunea A aici este memorarea.
În mod ironic, am predat și am predat
algoritmi TA de câteva ori
și nu am știut niciodată
ce înseamnă memorarea.
Așa că am învățat ceva din
prelegerea lui Eric zilele trecute.
Ceea ce ține minte, memorarea
este cheia în ceea ce,
aparent, este un
cuvânt inventat, este memo--
dacă te-ai întors în vremuri și
ai avut un bloc de steno
și ai notat lucruri.
Pentru că așa ai rezolvat
problemele, cu regula ta de calcul.
Apoi, în esență, ideea
este că, dacă calculez x i,
j pentru o pereche i, j,
nu ar trebui să o calculez din nou.  Ar
trebui doar să-l notez
pe blocul meu de note.
Stenoizarea mi se pare
mai bine.
Dar presupun că ar trebui să ne
întoarcem în anii 1940 și să o reparăm.
OK, deci să
scriem de fapt.  O să
scriu
pseudocod, probabil că va
arăta mai mult ca Matlab,
pentru că sunt genul ăsta de tip.
Deci, să presupunem că
am vrut să fac
o funcție, care, cred,
este venitul i, j, așa.
Bah.
Și acesta este lucrul pe care am
vrut să-l calculez.
Asta va fi de fapt
o problemă, pentru că nu vom
putea vedea.
OK, corect.
Deci, pe lângă asta, voi
trece într-o matrice
x, care va
fi ca blocul meu de note.
Aceasta va fi o
practică groaznică de codificare,
dar o practică ușoară de codare pe placă.
Deci, dacă aș fi în C++, poate
trec prin referință,
astfel încât atunci când editez --
asta este o
cheie de sol, dar orice--
când editez x, de fapt
persistă când recurg.
Aceasta este o
practică teribilă de codare
și nu ar trebui să o faci.
BINE?
Dar va
fi doar pentru că
nu vreau să scriu prea multe
rânduri pe tablă aici.
Și poate inițializam.
Avem o
funcție de ajutor pentru... să
vedem, vrem ca
veniturile noastre să fie mari.  Ei
bine, de fapt nu.  Îl
vom inițializa
cu nu un număr,
astfel încât să știm că
nu l-am calculat încă.  Ce
zici de asta?
OK, deci ce ar trebui să facem?  Ei
bine, dacă avem de gând să memorăm,
primul lucru pe care ar trebui să-l facem,
de fiecare dată când îmi apelez
funcția de venit pe o pereche i,
j este să verificăm dacă am
calculat-o deja.
Da?
Deci, în stilul meu prost și prost de codare a plăcii
aici, ce aș putea face?
Aș spune, ei bine, dacă l-am
calculat deja,
atunci acest lucru nu va
mai fi egal cu NaN
și nu va fi un număr.
Așa că pot spune, OK, dacă x
nu este egal cu nu un număr -
deci, cu alte cuvinte,
este un număr -
returnează.
Și asta, cred că această
mică linie de cod de aici, se
pierde puțin.
Dar asta, ar trebui să
punem străluciri în jurul lui.
Aceasta este magia
programării dinamice,
pentru că tocmai am ucis
apelurile recursive.
Chiar dacă i și j sunt 17 și
23, dacă l-am calculat deja,
am terminat, nu?
Nu trebuie să-mi sun din
nou recursiunea.
BINE.
Și în rest, ce o să
fac?
Ei bine, altfel,
poate voi suna...
Vreau să notez totul?
Nu vreau să
scriu totul.
Deci, altfel, voi
evalua, R, unde
R este această formulă de aici.
Observați că acest lucru va necesita
apeluri recursive, nu?
Și o voi stoca în
x i, j și apoi returnez x i, j.
BINE?
Deci, practic,
singura diferență
între ceea ce am văzut
în primele 2/3 din 6006
și acum este această frumoasă linie
de cod, care spune, dacă am
calculat deja acest lucru, returnați-l.
Și aceasta este
versiunea memorată a algoritmului nostru.
Cred că acesta este cel mai ușor de
gândit.
Dar de fapt, dintr-
o analiză a timpului de execuție,
este puțin enervant.
Nu în sensul în care ne-am
convins
că SRTBOT este OK.
Dar, desigur, dacă vă
gândiți la
arborele recursiv, ceea ce se întâmplă
este că poate
vă convingeți că
această piesă poate fi tăiată
în apelurile dvs. de funcție.
Așa că trebuie să vă
numărați cu atenție.
Există o modalitate diferită de a
implementa același lucru.
Deci aceasta ar fi
opțiunea B. Aceasta este poate
mai eficientă,
poate mai puțin eficientă, în
funcție de problema dvs.
Dar acestea sunt toate în
factori constanți unul de celălalt, în cea
mai mare parte -
nu întotdeauna, ci
în cea mai mare parte.
Asta ar fi de jos în sus.
Și aceasta este ideea
, mai degrabă decât să
luăm algoritmul nostru recursiv pe
care îl cunoaștem deja
și apoi să verificăm un
tabel pentru a spune, cum ar fi, OK,
am făcut deja asta?
Și în acest caz, returnați-l,
în versiunea de jos în sus,
voi construi matricea mea
x i, j pentru că deci
nu există nicio recursivitate.
Deci cum ar arăta?
Deci, în cazul de jos în sus,
observați că, într-un anumit sens,
memorarea este o
strategie de sus în jos.  L-
aș numi pe n, virgulă n.
Aici, vom
începe de la 0
și vom merge
spre n, nu?
Deci vom începe
cu x 0, j este egal cu
x i, 0 este egal cu 0 pentru tot i, j.
Evident, pot face
asta cu o buclă for.
Și acum, bine,
amintiți-vă, dacă ne gândim
la ordinea noastră topologică
, x i,
j depinde doar de
j-urile anterioare, nu?
Deci, are sens să existe o
buclă exterioară, care este peste j.
Și acum, în interiorul
acestei bucle exterioare,
pot calcula orice
vreau în acea coloană j a lui x.
Și sunt într-o formă bună, pentru că o
construiesc câte o coloană
, nu?
Deci, în special, acum
putem face bucla peste i
și apoi avem doar x j și
acum evaluăm pasul nostru R
în paradigma noastră SRTBOT.
Și observă că
asta e perfect.
Pentru că până
ajung la calculul x i,
j, am completat deja
x i, j minus 1,
ceea ce este tot ce aveam nevoie pentru a
evalua acea formulă.
Deci, care sunt avantajele
și dezavantajele aici?
Așa că observați că aici, timpul nostru de execuție
vă privește în fază.
Dreapta?
Avem n subprobleme la pătrat,
comandați 1 lucrare și ați terminat.  Pe de
altă parte,
există o oarecare posibilitate.
Dacă ai fi o
persoană cu inteligență artificială de școală veche,
ai putea să faci niște
tăieturi pe partea stângă
pe care nu le pot face aici.
Dreapta?
Deci aici,
evaluez literal
fiecare intrare a lui x i, j.
Nu este cazul pentru
această problemă specială,
dar poate x i, j
depinde doar de x i, j minus 5.
Această strategie va
construi tot acel tabel.
Acesta, poate puteți
sări peste unele intrări.
Deci, în practică, ar putea ajuta.
Pe de altă parte, aici,
am o grămadă de apeluri recursive pe care le-am
pus pe
stiva computerului meu, pe
care aici, nu le am.
Deci, cred că, de fapt, din cauza
supraîncărcării recursiunii,
de obicei,
strategia din dreapta
este preferată;  de asemenea, pentru claritate.
Dar asta e o declarație generală
pe care nu ar trebui să o fac.
Bine, deci oricum, cred că am
făcut această problemă până la moarte.
Sunt întrebări aici?
M-am gândit că voi completa
ceva ce am promis data trecută
și nu am făcut de fapt.
OK, fabulos.
Deci vom trece la problema 9-2.
Așa că aceasta continuă
de la ultima dată
în saga lui Tim
Castorul aici.
Așa că uit ce făcea Tim Castorul
în ultima noastră
sesiune cu probleme.
Dar astăzi, Tim Castorul
merge la târgul de carieră.
Și după cum știm cu toții,
singurul scop real
al merge la un târg de carieră
este de a ridica lucruri gratuite.
Glumim.
De fapt, ar trebui să
mergeți cu toții la târgul de carieră.
Mi-am luat primul loc de
muncă din facultate
mergând la un
târg de carieră și hărângând
pe cineva care ne alege
standul, până mă lasă să intru.
Dar, în orice caz,
deci Tim castorul
nu este interesat
să-și obțină un loc de muncă,
ci vrea doar slujbă.  ,
vrea doar lucruri gratuite
din cabinele de la târgul de carieră.
BINE?
Deci, în această
problemă specială, există n cabine --
sunt cabine?  Cu
siguranță nu sunt cizme.  Nu
știu.
Există n cabine, fiecare
dintre ele având un buton.
Și în special,
fiecare swag are asociată o valoare
,
care este Ci, care
este răcoarea obiectului i.  În
plus, are Wi.
Aceasta este greutatea obiectului i.
Și tocmai pentru a face această
problemă dificil
de comunicat verbal, există un
W-A-I-T asociat fiecărui
obiect, care este timpul
necesar pentru a aștepta la coadă și a
ridica obiectul i.
BINE?
Și Tim Castorul, dacă există
un obiect ridicol de grozav
cu puțin timp de așteptare, s-
ar putea să continue să se alinieze
și să primească mai mult din acel obiect.
Așa că, spre deosebire de Ceal Naffrey
la prima noastră problemă,
Tim the Beaver este perfect
fericit să aibă mai mult de unul
din același lucru.
BINE.
Pe lângă
asta, tocmai pentru a face
această problemă, după
părerea mea, ceva mai
enervantă și mai rătăcitoare,
Tim castorul are nevoie
și de un minut pentru a
ajunge la coadă la orice cabină.
Așa că va
trebui doar să ne amintim asta atunci când ne luăm în considerare
timpul nostru.
BINE.
Deci, să continuăm să adăugăm câteva
constante la problema noastră.
Deci fiecare cabină are un obiect
care are răcoare, Ci,
greutate Wi, timp ti.
Tim poartă o geantă.
Geanta poate sustine o
anumita greutate.  b.
Deci aceasta este greutatea maximă
pe care Tim o poate ține în geantă
în orice moment.
Și, în cele din urmă, Tim
este un castor lacom,
dar poate să meargă acasă
sau să se întoarcă la barajul său,
presupun, și să-și golească geanta.
Dreapta?
Și deci h este
timpul necesar pentru a merge acasă și înapoi și pentru a-
și goli geanta,
între timp.
Și din nou, doar pentru a
fi enervant, nu
uitați că face plus 1
pentru a intra în rândul următor.
Acesta este ceea ce a greșit răspunsul meu
și sunt amar.
Așa că o să mă
plâng în continuare de asta.
BINE.
Deci, desigur, ceea ce
vrea el este maximul.
Cum ar numi asta economiștii?  Nu
știu.
Dar pentru Tim the Beaver, el vrea
răcoarea totală maximă, sau MTC,
care este, desigur, un
număr pe care încercăm cu toții
să-l optimizăm, în k minute.  S-
ar putea să vă amintiți
acele emisiuni TV vechi, în
care aveți un minut
într-un magazin alimentar
pentru a goli cojile în
cărucior.
Deci el vrea să facă asta,
iar timpul de calcul pe
care l-a rezervat pentru
aceasta este o comandă nbk.
Și știu că este o configurație mare.
Am încercat să documentez toate
constantele diferite care
sunt în această problemă.
Nu cred că am ratat niciunul de aici.
OK, fabulos.
Deci, întâmplător, continuând pe...
AUDIENTĂ: Ce este k?
JUSTIN SOLOMON: k-- k este
timpul total
pe care Tim Castorul i-a alocat-o
pentru a-și descurca târgul de muncă.
Fabulos.
Oricare altul?
Misto.
BINE.
Observați că acesta va
fi un exemplu de problemă care
nu a fost kosher în
sesiunea cu probleme de săptămâna trecută,
în sensul că k este
inclus în timpul nostru de execuție.
Dreapta?
Dar ce este k?
Este doar un număr.
k nu crește în dimensiunea
problemei dvs. într-un mod liniar.
Deci nu va conta
pentru modul în care ne rezolvăm problema,
dar este doar o caracteristică
care merită subliniată.
BINE.
Deci, cum rezolvăm
problemele de programare dinamică?
Folosim SRTBOT, sau un Señor BST,
dacă urmăriți
iterațiile anterioare ale acestui curs.
Bine, deci bine, deci hai să facem asta.
Vezi, încerc
să economisesc spațiu.
Acest lucru nu va
sfârși prin a reuși.
Deci, din nou, care sunt
diferitele sub-probleme aici?  Ei
bine, care sunt
diferitele lucruri care îl
limitează pe Tim Castorul?
Care sunt constrângerile lui?  Ei
bine, are doar atât de mult timp.
Și asta va suna
mai filozofic în intenție,
dar timpul merge întotdeauna
înainte pentru Tim Castorul.
Deci, acesta este un
candidat destul de bun
în ceea ce privește programarea dinamică.
Pentru că nu va
exista o dependență ciclică.
Amintiți-vă că, în
programarea dinamică,
totul este să încercăm să
identificăm ordinele topologice
în subproblemele noastre.
Și când vezi
ceva ca timpul,
nu numai că începe și cu
t, dar este util în sensul
că timpul înaintează.
Nu există niciodată un caz în
care Tim Castorul să
cumpere un
avion ciudat Warp Speed
și să se întoarcă cumva în timp.
Asta nu se întâmplă în această
problemă specială cu teme
și, de
dragul lui Tim, Castorul,
sper să nu fie probleme cu temele.
Deci, acesta este un
mod îndelungat de a spune
că timpul este o
constrângere destul de rezonabilă
de pus în problema noastră, nu o
constrângere la fel de mult ca un index,
cred.
Mai mult, există un
alt lucru care îl
limitează pe Tim
Castorul, și anume
capacitatea genții sale.
Amintiți-vă, el poate
ține doar greutatea b.
Dar acesta ar trebui să-ți ofere
un pic de heebie-jeebies.
Pentru că această
problemă, ca o răsucire,
a permis sacul
să se golească singur.
Deci nu este adevărat
că, cumva,
poți veni cu sub-probleme
în care Tim Castorul doar își
scădea monoton
greutatea genții.
Cu toate acestea, dacă alege să
scadă greutatea genții sale,
trebuie să petreacă timp făcând asta.
Deci timpul continuă să avanseze
pentru Tim Castorul.
Și asta
ne va da ordinea topologică.
Da?
Asta e puțin prea
filozofic, cred.
Dar, într-un anumit sens, acesta este
un mod îndelungat de a spune,
pentru paradigma noastră SRTBOT de aici, un
lucru total rezonabil de făcut
ar fi să avem x i, j--
Nu cred că, în această clasă,
facem această definiție  notaţie.
Deci, doar x i, j este egal cu
răceala maximă în
care are i minute
și are j greutate --
permiteți-mi să arunc o privire la
răspunsul meu pentru a vedea
dacă a rămas în geantă sau
greutatea pe care o poartă.
Lăsat în geanta lui...
oricare ar fi
o problemă rezonabilă.
Doar că sunt prost să mă
uit la notele mele
și să le văd că
nu sunt de acord cu tabla.
Așa că o să încerc
să rămân consecvent.
OK, deci x i, j este MTC, dar
în i minute cu j greutate rămasă,
mai degrabă decât în ​​k minute
cu b greutate, care
va fi problema noastră de bază.
BINE.
Oh, nu, am făcut-o din ordine.
Ignoră asta.
Ajungem la b într-un minut.
BINE.
OK, deci acestea sunt sub-problemele noastre.
Deci acum să facem R în SRTBOT.
[Râde] Urăsc
atât de mult această clasă.
Îmi pare rău.
Așa că bine, deci să spunem că Tim
castorul mai are 1 minute
pe ceas.
Și are j greutate în geantă.
Are o serie de
acțiuni pe care le poate întreprinde.
Da?
Și să ne gândim care
sunt toate acele acțiuni.
Apropo, există un lucru pe
care Tim castorul l-
ar putea face în mod plauzibil.
Dar nu prea are nevoie,
este să nu facă nimic acum, dar apoi
în 10 secunde, fă ceva.
Ai putea explica
asta în această problemă,
dar nu există un motiv, nu?  Ar
putea la fel de bine să-și
strângă toate acțiunile
și apoi să-și lase tot
timpul rămas la sfârșit.
Te convingi
că e în regulă.
Tim preferă un
program comprimat.
Dreapta.
Deci, el are multă
energie, acest Castor.  Asta
spun ei.
Sunt muncitori în construcții ai naturii
, ceva?
BINE.
Bine, deci să ne gândim
la toate opțiunile noastre.
Deci, unul, Tim Castorul
nu a putut face nimic.  Ar
putea să stea pe aici
pentru restul timpului
și asta ar fi
perfect.
Deci, un alt mod de a pune
asta este că ar putea renunța.
Câtă răcoare ar primi
Tim renunțând?
0.
Așa este, copii.
Renunțarea te face zero cool.
Deci OK, deci Tim Castorul
încearcă să maximizeze.
Are o mulțime de
opțiuni diferite.
Unul dintre ei este 0,
adică a renunțat.
Dreapta?
Observați că ar putea recurge.
Cum ar fi, x-- Presupun
ce ar fi-- ar
putea renunța pentru un minut,
și să fie x i minus 1j,
sau ceva de genul ăsta.
Am uitat dacă o să
fac i plus 1 sau i
minus 1. i minus 1j.
Dar nu există niciun motiv.
El poate să renunțe și să se oprească.
Acesta ar fi doar un
cost recursiv suplimentar
fără un motiv întemeiat.
BINE.
Următorul lucru pe care l-ar
putea face este că se
poate pune la
coadă pentru un stand.
Dreapta?
Deci, mai întâi, haideți să aflăm
ce se întâmplă atunci.
Așa că, unul, capătă răcoare.
Să presupunem că
intră în cabina k.
Așa că primește răcoare
Ck când face asta.
Și acum poate recurge.
Deci, mai întâi, trebuie să ținem
cont de timp.
Deci este nevoie de tk--
asta este un t-- timp.
Sau o face?
Nu.
Pentru că îi ia un
minut în plus pentru
a ajunge în linia următoare,
sau pentru a intra în această linie.
Bănuiesc că asta e mai bine.
Și mai mult, trebuie să
țină seama de j minus Wk,
așa.
Poate face asta mereu?
Nu, trebuie să-i mai
rămână atât de mult timp
și are nevoie de atât de
mult timp în geantă...
sau atât de multă greutate
rămasă în geantă.
Voi băieți puteți
rezolva inegalitatea.
Dar din moment ce
am doar un picior aici,
voi spune doar, dacă este cazul.
Aceasta este o modalitate excelentă de a pierde
puncte la teme.
Dar pentru scriere pe tablă, este în regulă.
Deci, când spun aplicabil, vreau să spun că
aceste două numere ar fi mai bine
să fie mai mari sau egale cu 0.
OK?
Și poți face asta
pentru toți k, nu?
Deci, cu alte cuvinte, el poate
alege să intre în standul k.
Și Tim are a treia opțiune, și anume că
poate merge acasă.
BINE?
Deci ce se întâmplă dacă se duce acasă?
Tim castorul se
răcește când se duce acasă?
Nu, mi-e frică să spun.
Dar își petrece timpul.
Deci, cât timp petrece?
h--
PUBLIC: Ar fi trebuit să-și
piardă răcoarea.
JUSTIN SOLOMON: Ce a fost asta?
PUBLIC: Ar fi trebuit să-și
piardă răcoarea.
JUSTIN SOLOMON: Ar fi trebuit să-și
piardă răcoarea mergând acasă.
Nu, acasă e cool, băieți,
mai ales în acest semestru.
Stai acasă.
Stai înăuntru.
Dreapta.
Așa că pierde timpul acasă h și
1 pentru a ajunge în linia următoare.
BINE?
Dar are un fel de târg de diavol
.
Pierde timp, dar
câștigă geantă, bagaj.
Greutate este cuvântul pe care îl
caut, b, așa.
BINE?  Din
nou, în acest caz,
amintiți-vă că mai are
nevoie, dacă i este mai mare decât h.
Altfel, are probleme.
Apropo, am scris
asta într-un mod enervant.
Un mod diferit de a spune
că este i minus h minus 1
este mai mare sau
egal cu 0, ceea ce
este cu adevărat aplicabil
în fiecare apel recursiv.
Dar acest lucru este strict
mai mare decât [INAUDIBIL]..
Mai este un lucru mic
care m-a prins din urmă, când
citeam răspunsul aici.
Bine, și acestea sunt toate
opțiunile pentru Tim Castorul,
da?
Observați că
fiecare dintre opțiunile noastre
fie renunță complet,
fie scade timpul.
Deci avem
ordinea noastră topologică,
care este, din nou,
săgeata timpului
continuă
să meargă înainte.  Voi
demonstra acest lucru cu
rigurozitate punând o
bifă lângă litera T.
Din nou, la teme, ar
trebui să scrieți
răspunsurile.
Care este cazul nostru de bază pentru Tim?  Ei
bine, câtă răcoare
ai, dacă nu ai timp?
0 răcoare.
Atât.
Deci avem această expresie,
x0j este egal cu 0 pentru tot j.
De altfel, deși
este perfect ca
acesta să fie cazul tău de bază
, de fapt, într-un anumit sens,
nu am avut nevoie de el, pentru că
Tim Castorul a
avut întotdeauna opțiunea de a renunța.
Deci, cred că ați putea,
în această problemă, să
nu aveți un caz de bază,
dacă doriți cu adevărat.  Ar fi
ok, dar
cam ciudat.
BINE.
Și care este problema noastră inițială?  Ei
bine, el începe cu
timpul k și capacitatea de greutate b
în geantă.
Deci este x k, b.
Și apoi, în sfârșit, trebuie
să ne facem analiza timpului de rulare.
Deci câte
subprobleme există?  Ei
bine, din nou, o
sub-problemă este practic
doar numărul de indici pentru
majoritatea problemelor noastre de programare dinamică
.
Dreapta?
Deci primul indice este timpul.
Al doilea este dimensiunea pungii.
Acesta este întotdeauna între 0 și b.
Acesta este întotdeauna între 0 și k.
Deci există
sub-probleme de ordine kb.
Cât timp
durează fiecare sub-problemă?  Ei
bine, observați că
trebuie să parcurg toate
opțiunile mele diferite k aici.
Așa că am... oh, observ că
k este abuzat în răspunsul nostru
la această problemă.  Ar
trebui să folosim k o singură dată.
OK, deci aici am
făcut o greșeală.
Și cred că este în
soluția scrisă,
dar nu o voi lua acum.
Există k, care este
timpul total pe care îl are Tim Castorul,
și există k pe care îl
folosesc ca index aici.
Și acestea nu sunt la fel.
Cred că pot face
acest k bar foarte rapid.
Iată, problema rezolvată.
Și tocmai am observat asta,
pentru că îmi făceam timpul de rulare.
Și nu este ordinul k.
Este bucla peste
toate k bare.
Câte k bare sunt?  Ei
bine, acestea sunt toate
cabinele diferite
și acestea sunt n dintre ele.
Deci, acesta este ordinul n
timp per sub-problemă,
ceea ce îmi oferă o
durată totală de rulare a ordinului kbn, care,
cred,
oh-oh, timpul de
rulare dorit a fost comanda nbk.
Dar cred că ne putem convinge
că într-adevăr, acestea
sunt același lucru.
OK, deci scuzele mele pentru un
caracter ușor supraîncărcat aici.
Dar sincer, este unul dintre acele
lucruri, dacă ai citi răspunsul,
probabil nici
nu ai observa.
Dar acum că o spun cu voce
tare, sunt.
BINE.
Și asta rezolvă
problema de maximizare a lui Tim Castorul.
Este un castor foarte tare.
Aveți întrebări despre acesta?
Observați că ambele
probleme
sunt foarte asemănătoare ca natură.
Practic, am
scris doar sub-probleme
indexate după fiecare
lucru posibil și apoi am enumerat
fiecare soluție posibilă.
Cred că acest lucru este
absolut sensibil.
Din nou, îmi amintesc că am avut un
profesor de matematică la facultate care
întotdeauna folosea această expresie --
este important să
nu gândești aici.
Și cred că acest lucru
este absolut adevărat
pentru aceste
probleme de programare dinamică,
că, cumva, par mult
mai complicate decât sunt.
Fabulos.
Deci problema 3, analiza proteinelor.
Ah, da, așa că și acesta m-a
împiedicat pentru un minut.
Pentru că timpul de execuție pe care îl
doresc nu este
timpul de execuție al
soluției evidente,
dar este, într-un fel,
după un pic de remediere.
BINE.
Deci profesorul Leric
Ander are un laborator.
Și acel laborator
procesează ADN-ul.
Ta-da.
OK, așa că permiteți-mi să merg
la notele mele aici,
pentru că cred că
sunt mai ușor de citit.
Așadar, un fir de ADN,
așa cum știm cu toții,
pentru că suntem studenți MIT,
este practic egal cu un șir
de caractere care sunt ACTG.
Dacă îmi ceri să numesc
ceea ce au reprezentat aceia,
aș putea să pun un junghi
pe unul sau doi dintre ei.
Dar sunt un eșec al...
Nu am avut GIR,
pentru că am fost la Stanford.
Și acesta este motivul pentru care se pare că sunt
o persoană slab educată,
conform unei persoane
într-o întâlnire a facultății.
Dar, în orice caz,
avem o componentă de ADN.
Practic este un
șir lung de caractere
care sunt una dintre cele patru opțiuni.
Mi se spune că uneori există o
a cincea și o a șasea opțiune,
dar nu prea des.
În această problemă, nu există.
Și mai mult, astfel încât o
șuviță poate fi tăiată.
Deci am această
șuviță mare și lungă și
caut anumite markere.
În special, am
o listă P de markeri,
care sunt într-adevăr o secvență
mai mică sau egală cu k
nucleotide.
Apropo, asta chiar este
ceva ce fac oamenii.
Căutarea șirurilor este într-adevăr
aplicabilă procesării
acestor catene de ADN.
Evident, .
Cred că, în practică,
aceste tehnici
trebuie să fie mult mai
rezistente la erori.
Dar, într-adevăr, mulți dintre acești
algoritmi pe care îi acoperim
nu sunt atât de
departe de modul în care
oamenii procesează aceste seturi de date uriașe
, ceea ce este destul de grozav,
cred.
OK, deci ce vom face?
Avem o sfoară.
Și apoi vom
face o împărțire.
Deci, vom numi șirul nostru
S și diviziunea noastră
D, care
arată ca d1 la dm,
care sunt subșiruri
care se concatenează
pentru a face tipul complet.
Deci, dacă S este șirul nostru de intrare
, atunci o diviziune D
este la fel ca tăierea
S în subșiruri mici,
fiecăruia dintre care putem da
un nume mic d aici.
Atât de mare D este divizia completă.
Micul d sunt toate
piesele mici.
Există vechea melodie despre
trecerea prin marele D
în [INAUDIBLE], Dallas.
Cred că e pentru divorț.
Bine, OK, deci
valoarea unei diviziuni
este numărul de fire.
Deci șuvițe sunt aceste mici d
aici, care sunt în lista noastră P.
OK?
Deci, având în vedere S și P, ceea ce
dorim este valoarea maximă.
Și timpul de rulare
pe care ni-l avem în buget
este un timp de rulare ciudat.
Și asta ar trebui să
ne facă puțin suspicioși.
Deci, valoarea maximă este mare O din--
Cred că am scris-o ușor
diferit în problemă,
dar indiferent-- distribuit
la k, așa.
Deci este k mod P plus
k pătrat.  mod S.
Deci avem doi termeni
aici, care miroase cumva
amuzant în programarea dinamică.
BINE.
Deci ce să facem?  Ei
bine, ceea ce am făcut a fost că am
ignorat timpul de execuție dorit, am
venit cu un
program dinamic și am observat
că era puțin
greșit și apoi l-am reparat.
Prin greșit, vreau să spun că a fost corect.
Doar că nu a fost suficient de rapid.
OK, deci să facem versiunea 1 aici -
1.0, care o face mai
precisă sau mai precisă.
Întotdeauna îi confund pe cei doi.
Deci iată un lucru care va
fi puțin amuzant.
Pentru că va
părea că vom
avea o
problemă de calcul ușoară.
Dar apoi se va dovedi
că de fapt este prea lent.
Deci, în special,
în S-ul nostru din SRTBOT,
ceea ce am putea face
este să spunem, xi va
fi valoarea maximă a unui sufix.
Dacă vă întrebați,
nu știu diferența
dintre prefix și sufix.
Dar am scris
sufixul cuvântului în notele mele
și l-am verificat acasă.
Si, virgulă, două puncte -- vezi, este
sufix, pentru că începe la i
și merge până la sfârșit.
PUBLIC: [INAUDIBIL]
JUSTIN SOLOMON: Nu?
PUBLIC: Fără virgulă.
JUSTIN SOLOMON: În Matlab,
ar fi o virgulă.
Și acesta este un punct
și acesta este un i.
BINE.
[Râde] Mulțumesc.
Îmi inventez propriul
limbaj de programare pe placă
în timp ce mergem astăzi.
Bine, deci și observați că
acesta este un set rezonabil
de sub-probleme, nu?
Pentru că, evident, dacă îmi tai
o bucată din șir,
atunci valoarea maximă pe care o
pot obține este doar
valoarea a ceea ce rămâne.
Din punct de vedere spiritual,
aceasta se simte cumva
ca
programarea dinamică potrivită.
Și într-adevăr, vom
vedea că este.
Dar necesită doar
o mică
listă care ar putea fi
să ruleze la momentul potrivit.
BINE?
Deci, să facem un apel recursiv.
Și acest lucru este de fapt
simplu.
Cel puțin,
apelul recursiv pe care doriți să îl efectuați
este simplu.
Și apoi vom vedea că
există o formulă echivalentă, care
este cea pe care o veți vedea
în soluție, care
pare mai complicată.
Dar este același lucru.
Așa că
îl voi scrie ca pseudocod
pentru apelul nostru recursiv, mai degrabă
decât ca o formulă uriașă,
pentru că cred că este
mai ușor de urmat.
Nu pseudocod--
știu că este descurajat
în această clasă, o
descriere a unui set de pași
pentru obținerea unui
apel recursiv, mai degrabă decât o formulă.
Deci, în special, vom
inițializa xi la 0.
Vrem să facem o
problemă de maximizare.
Deci inițializarea unei variabile la
0 este un lucru sensibil de făcut.
Și ține minte, ce
putem face aici?
Deci ne uităm la un sufix.
Aș putea coborî lista P cu
toți diferiții marcatori, să
văd dacă vreunul dintre ele se potrivește cu
primele două caractere
ale șirului meu.
Dacă o face, primesc
ceva valoare și apoi
trec la următorul lucru.
Are sens?
Hopa, îmi dau seama că am
o mică greșeală aici.
În loc să inițializez
la 0, [Râde]
am de fapt o
opțiune suplimentară
pe care am uitat să o iau în considerare.
Pentru că pur și simplu
nu puteam folosi acest personaj.
Aș putea să-l pun în
propriul său fragment
și să nu obțin nicio valoare din el.
Deci, poate inițial, fac
un apel recursiv ca acesta.  Ar fi
OK să-l
inițializați la 0
și apoi să faceți asta -- dar orice.
Observați că deja
vedem că t-ul din SRTBOT-ul nostru
începe să iasă în evidență la noi.
Vom depinde doar
de indici mai mari i.
BINE.
Dar pe lângă asta,
asta nu este suficient, nu?
Acest lucru ar
recurge, evident, la sfârșitul listei noastre
și nu ar face nimic.
Obținem valoare dacă putem găsi un
subșir care se află în lista noastră.
Deci, ceea ce am putea face este,
pentru fiecare marker din P--
amintiți-vă că P este lista de
lucruri pe care le căutăm--
OK, ce aș putea face?
Dacă markerul se potrivește cu
S începând de la i-- pur
și simplu nu voi
încerca să fac Python--
începând de la i și terminând la
lungimea markerului, ei bine,
ce aș putea face?
Aș putea obține 1 USD
potrivind acel obiect.
Și apoi trebuie să sar înainte pe
lungimea șirului
din apelul meu recursiv, nu?
Ei bine, aș putea face asta,
sau nu aș putea face asta.
Și vreau să maximizez, nu?
Așa că pot să-mi păstrez vechea valoare,
sau aș putea obține un punct
folosind asta ca
potrivire, plus xi
plus lungimea markerului.
BINE?
Acesta este de fapt, în
mintea mea, cel mai simplu
program dinamic posibil
cu care ai putea veni.
Acesta este de fapt un
program dinamic foarte bun.
Vom vedea doar că
timpul de rulare nu este suficient de bun.
BINE.
Deci toată lumea este
de acord că aceasta este o modalitate prin care aș
putea rezolva această
problemă și mi-
ar oferi un răspuns corect?
Voi face TBOT.
PUBLIC: [INAUDIBIL]
JUSTIN SOLOMON: Da, asta vom
face.
Dar poate vom
sări peste unele părți din SRTBOT.
Deci, în special, care este
ordinea topologică?
Observați că mă uit întotdeauna în
dreapta, când fac un
apel recursiv.
Care este cazul meu de bază?  Ei
bine, în acest caz, este
doar un x de 0, cred,
pentru că aștept cu nerăbdare.
Oh, îmi pare rău.
Cazul meu de bază este x din întreaga
lungime a șirului, care va
returna 0, nu?
Pentru că dacă nu am șir,
nu pot obține nicio valoare din el.
Originalul este x de 0, ceea ce înseamnă
că vreau întregul șir.
Și să facem de fapt
analiza timpului de execuție,
așa cum sugerează Jason,
pentru că acesta este, desigur,
calculul relevant aici.
Deci acesta este T2, pentru că este
al doilea T din SRTBOT.
OK, deci câte
subprobleme există?
Ei bine, vreau să spun,
aproape că se pare că ar
trebui să avem un algoritm rapid.
Pentru că subproblemele noastre sunt
indexate doar de i, nu?
Deci, există o sub-problemă
pentru fiecare caracter
din șir.
Deci sunt
sub-problemele mod S total.
Dar cât timp
durează fiecare sub-problemă?  , Ei
bine, hai să fim atenți.
Deci, există o buclă for
peste toți markerii din P.
Așa că știu că am cel puțin
mod P lucrează în sub-problema mea.
Asta e toată
munca pe care o fac?
Cam așa arată,
pentru că există o singură
buclă pentru și există un dacă.
Dar cum verific
dacă șirurile sunt egale?  Ei
bine, trebuie să repet pe
lungimea șirului.
Deci suport un al doilea
cost, care este verificarea
dacă două șiruri sunt egale.
Știm că
șirurile noastre sunt cel mult... ei
bine,
de fapt nu am notat-o.
Dar problema
ne spune că șirurile noastre
au lungimea maximă k.
Deci am un alt
factor de k în fiecare
dintre subproblemele mele.
Și asta implică că
întreg algoritmul nostru, pe
care v-am subliniat mai
sus, ia mod S k pătrat...
oh, îmi pare rău.  A
fost o minciună.
Dacă înmulțesc aceste
lucruri împreună, ceea ce primesc este... îmi
pare rău.
[Râde] Am nevoie de mai mult somn...
S P k.
Și asta contravine regulilor.
Deci asta e o față încruntă, da.
Pentru că, în special, am luat
două numere mari, într-un fel,
și le-am înmulțit împreună,
și asta nu e bine.
Deci, ce trebuie să facă o persoană?
Am încercat să-mi rezolv problema.
Am venit cu...
apropo, din perspectiva creditului parțial
, cred că te-ai
descurca
dacă ai ajunge în acest punct.
OK, nu grozav, dar OK.
Dar, desigur,
problema este să
vă ceară să rezolvați
acest lucru amuzant, care
este kP, plus k pătrat S.
Când văd o sumă ca aceasta--
și amintiți-vă că
există două probleme de rezolvat.
Există două strategii
pentru rezolvarea problemelor
din clasa de algoritmi.
Există unul care este util
în viața de zi cu zi, și anume
să elaborezi algoritmi.
Există un al doilea, care este să-ți
diagnosticezi psihologic
instructorii.
Și cred că a doua strategie
este de fapt destul de eficientă
aici.
Văd doi termeni.
Majoritatea lucrurilor noastre de programare dinamică

implică completarea unui
tabel, unde te-ai
aștepta să existe un produs.
Așa că, în general, m-aș stramba la
asta și m-aș gândi, hm, poate că
trebuie să fac niște
calcule prealabile.
Da?
În special, trebuie să
facem o mulțime de potrivire a șirurilor
în problema noastră și poate că
putem face asta mai eficient.
Da?
Cam asta e
întrebarea principală aici.
Deci chestia asta este prea lent
și încercăm să o reparăm.
Modul în care voi
încerca să o rezolv
este să spun, de genul, OK, ei bine,
am sub-probleme cu mod S.
Dacă mă uit la acești doi
termeni, cât de multă muncă pot
face de fapt în
sub-problema mea, ceva
care arată ca k pătrat,
poate plus această cantitate
de pre-calcul.
Vezi ce am facut acolo?
BINE.
Deci hai să facem asta.
Deci, în special,
iată tipurile
de interogări pe care
va trebui să le fac.
Există o grămadă de
ori în codul meu când...
iată un număr care...
[HICCUPS] Da,
mă destramă.
Asta primesc pentru că am sprintat
prin campus pentru a ajunge aici.
Voi găsi
un număr m i, j.
Și va fi 1
dacă subșirul S i--
oh, man-- la j este în lista mea
de markeri P și 0 în caz contrar.
Apropo, de ce este suficient?
Observați că nu
răspund, care marker?
Dar problemei nu
prea interesează, nu?
Această problemă verifică doar
dacă există un marker.
Și dacă da, atunci
folosesc asta, da.
Deci, dacă am acest
lucru, asta va
face cumva acest lucru
pentru bucla mult mai
ușor, pentru că acum nu
trebuie să fac potrivirea șirurilor.
Vom reveni la
asta într-un minut.
BINE.
Deci întrebarea mea este, cum
pot calcula acest lucru?
Și apropo,
observați că știu
cum să calculez acest lucru atunci când
diferența dintre i și j
este mai mare decât k, pentru că
știu că toți markerii mei
au lungimea k sau mai mică.  Va
fi
important, pentru că,
deși m este dublu indexat,
nu trebuie să fac asta.
De fapt, l-aș putea
stoca folosind mai puțină memorie
decât atât, dacă aș
vrea, doar
stochând acel bloc diagonal.
OK, corect.
Deci, celălalt lucru,
pe care cred că l-am
văzut și într-o
sesiune anterioară cu probleme,
este că atunci când facem
multă potrivire a șirurilor,
adesea merită să ne punem
șirurile într-o tabelă hash,
astfel încât să fie mai ușor
de  uită-te mai târziu.
Există
sau nu acest șir în chestia asta?
În loc să potriviți fiecare
personaj de fiecare dată.
Așa că poate facem
asta, doar pentru distracție.
Și, în general, când vedeți
o problemă de potrivire a șirurilor -
și aveți o listă
de șiruri, aș
sugera să vă gândiți
la tabelele hash,
doar pentru distracție și profit.
Deci, la pasul unu aici, poate
am pus toate șirurile din P
într-un hash.
BINE?
Cât timp durează asta?  Ei
bine, trebuie să procesez
fiecare șir, să-i găsesc codul,
ceea ce va
dura mai mult de k timp.
Există mod P dintre ele,
deci acesta este timpul k mod P.
Observați că acest lucru este de
acord cu primul nostru termen
de aici.
Așa că simțim că, aha,
suntem în formă bună.
Facem progrese aici.
Și acum, poate vreau să completez
aceste obiecte m, i, j aici.
Cum as putea sa fac asta?  Ei
bine, pentru unul, cu siguranță voi
repeta peste toate
i-urile posibile.
BINE?
Deci hai să facem asta.
Deci vom face 2.
Apropo, folosesc 1
și 2 și a și b
și orice.
Acestea sunt doar moduri de a
desemna etapele lucrurilor.
[Râde] OK, deci să
spunem că vreau doar
să completez m folosind
un algoritm de moarte cerebrală.
Așa că aș putea trece de la 1 la
dimensiunea șirurilor mele pentru i.
Atent.
Acum nu pot suporta un S pătrat.
Dar știu că șirurile mele
sunt întotdeauna în mare parte k.
Deci aș putea face pentru j este egal cu
i plus 1 până la i plus k.
Deci, această buclă for implică de fapt
k timp, nu mod S timp.
Și acum pot face două lucruri.
Pot găsi hash-ul
șirului de la i la j.
Aceasta va
dura k timp.
Și pot să-l caut...
ah, nu... pentru a vedea dacă este de
fapt în tabelul nostru hash al lui P.
Și dacă este, atunci am
stabilit m egal cu 1. În
caz contrar, am stabilit m egal cu 0.
Și acestea sunt
operațiuni în timp constant,
cel puțin în așteptări.
Deci cât costă?
Și astfel, vă puteți convinge că
completează acea matrice m.
Cât timp durează?  Ei
bine, am o buclă de mărimea
lui S. Am o buclă de mărimea k.
Am o a doua buclă de dimensiunea
k aici pentru a calcula hash-ul.  Deci
toată chestia asta va
lua ordinea k pătrat mod
S timp, așa.
Acum, în mod convenabil...
există cretă pe podea.
Și acesta este al doilea
mandat din timpul nostru.
Deci, acesta este cușer.
Putem completa m.
Și acesta este un
obiect convenabil de avut în preajmă.
Deci, singurul lucru
care rămâne este
să ne revizuim R de sus, să
folosim m-ul pe care îl avem.
Și asta e destul de
simplu.
Deci trucul este să nu te
sprijini de acest lucru
și să apeși efectiv
butonul de oprire.
Eu invat.
Deci acum presupun că am avut T2 pentru al
doilea T. Deci, pentru R revizuit, ar
trebui să avem R prim.
[Râde]
Publicul: [Inaudibil]
JUSTIN SOLOMON: Ce a fost asta?
PUBLIC: Derivatul.
JUSTIN SOLOMON: Așa este.
Derivata-- da, am
putea face simboluri Christoffel,
cum ar fi i, j prim și punct
și virgulă k.
Luați 6838 dacă doriți să aflați
ce sunt simbolurile Christoffel.
Corect, deci acum, care este
apelul meu recursiv pentru xi?  Ei
bine, vreau să maximizez.  Ei
bine, ce pot face?
Pot verifica fiecare
lungime posibilă
a unui șir care
ar putea fi în P, pot verifica
dacă este, folosind matricea mea m
și să obțin acea sumă de profit.
Deci, în special, primesc m.
Apropo, tot folosesc
aici cuvântul profit.
În esență, folosesc
asta pentru a însemna creșterea
în fiecare dintre
problemele noastre de aici.
Îmi place să mă gândesc la
problemele noastre ca la maximizarea profitului,
pentru că sunt un profesor lacom.
Deci acesta este m, i j, care ar
fi 1 dacă aș găsi un șir acolo
și 0 dacă nu sunt, plus xi plus
j, pentru a ține seama de lungimea
aici, unde j este în 1 la - ei
bine, fie
lungimea  a șirului,
sau ajung la sfârșitul--
fie
lungimea maximă a unui șir în P,
fie ajung la sfârșitul
matricei mele, așa.
BINE.
Și acesta este
noul nostru apel recursiv.
Singurul lucru pe care ar
trebui să-l verificăm
este, care este timpul de rulare pentru
completarea efectivă a x acum?  Ei
bine, există încă
sub-problemele mod S.
Și acum cât durează?  Ei
bine, acum am doar
o buclă peste k lucruri.
Acesta este modul S ori k.
De fapt, este mai puțin decât
oricare dintre termenii care sunt
în timpul nostru de execuție.
Și așa e bine.
Acesta este de fapt
un exemplu amuzant,
în care partea de programare dinamică
a algoritmului nostru,
odată ce am făcut toate aceste
pre-calculări drăguțe,
este de fapt nesemnificativă, în
comparație cu toate
pre-calculele pe care a trebuit să le
facem în timpul nostru final de rulare.  --
ascuns.  În
regulă, aveți întrebări
despre plierea proteinelor
sau orice altceva
tocmai am făcut?
BINE.
Deci, ca de obicei,
vorbesc prea mult.
PUBLIC: [INAUDIBIL]?
JUSTIN SOLOMON: Da, pe care ai
prefera să o tai?
PUBLIC: [INAUDIBIL]
JUSTIN SOLOMON: Am
foarte puține preferințe.
Bine, deci una dintre problemele tale...
aș vota,
dar cu publicul nostru,
există o mare probabilitate
de divizare a juriului aici.
Dreapta.
Deci, au
rămas două probleme
în sesiunea cu probleme.
Ca de obicei, instructorul tău...
PUBLIC: [INAUDIBIL]
JUSTIN SOLOMON:
Poți să-l lași acolo.
Aceasta este o altă
problemă de care trebuie să înveți.
Ca de obicei, am vorbit prea mult
și nu am ajuns la final.
Am impresia că,
în 6006, chestia asta cu picăturile de ouă
este, oricum, un pic de tradiție.
Așa că poate vom acoperi
această problemă foarte repede.
Fac asta în
secțiune, unele variații?
PUBLIC: Nu.
JUSTIN SOLOMON: Nu de data asta...
chiar mai bine.
OK, deci da, deci poate vom
face acest lucru cu picăturile de ou,
mai ales pentru că
celălalt, cred,
necesită multă configurație verbală.
Celălalt este...
Aș spune că, dintr-o
perspectivă de programare dinamică, poate că nu este
foarte interesant.
Dar dintr-o
perspectivă interesantă a problemei,
este oarecum cool
să te gândești.
Așa că v-aș încuraja
să-l lăsați acolo,
iar voi, băieți,
îl puteți citi acasă.
Din perspectiva codificării,
este și un fel de distractiv.
Am observat că soluția
nu a făcut ceea ce aș face eu, și
anume să
folosesc biții din--
presupunem că ceva
nu era prea înalt,
utilizați biții într-un număr întreg pentru a
stoca variabilele binare.
Dar asta e un hack vechi.
Este ca acest vechi
hack pentru a calcula
rădăcina pătrată a unui
număr, care se pare că este
în codul
jocului video Doom, care implică
schimbarea biților, și se întâmplă
să fie de acord cu rădăcina pătrată,
dintr-un motiv magic, pe care
analiștii numerici o urăsc cu adevărat  .
OK, deci hai să facem
picătură de ou leneș.
Deci asta e problema 4.
OK.
Deci suntem într-o clădire.
Clădirea noastră are n
etaje și k ouă.
Bănuiesc că este discutabil
dacă clădirea are
ouă sau rezidenți --
dar, în orice caz,
aveți un set de ouă.
Și poate sunt în
acest centru de date
sau într-o altă clădire ciudată.
Deci nu am înălțimi ale
podelelor care sunt izotrope,
ci mai degrabă, fiecare etaj
are o înălțime diferită,
care ar putea varia.
Deci este înălțimea podelei, sau i.
Îmi doresc foarte mult să scriu
făină, dar mă abat.
Și vom presupune că
lista noastră este deja sortată.
Deci, cu alte cuvinte,
etajul cinci
este mai înalt decât
etajul al patrulea și
nu trebuie să petrecem n
timp de conectare făcând asta.
BINE.
Dreapta.
Deci, aparent, în
problema noastră,
avem un ou cu o
proprietate mecanică misterioasă
pe care încercăm să o recuperăm.
Și toate ouăle, după cum
știm, sunt identice.
Deci singura diferență dintre
ouă este pui, versus gâscă,
față de...
Mă chinui să mă gândesc la o a
treia categorie de păsări de curte -
curcan.
Mulțumesc.
Dar presupunând că mi-am
luat toate ouăle
la același Stop-N-Shop
și toate
provin din aceeași
specie, atunci
au aproximativ aceleași
proprietăți mecanice.
De fapt, probabil
cea mai bună configurație
este că podelele sunt
foarte îndepărtate față
de dimensiunea unui ou.
Și dacă ajung
suficient de sus, oul meu,
când le scap pe
pământ, așa, se rupe.  Nu s-a
rupt.
Dar s-ar fi putut sparge.
Și bineînțeles, dacă îl scap
de la o înălțime și mai mare,
oul meu tot se va rupe.
Totuși, dacă am o
podea foarte joasă... aparent,
o podea foarte joasă.
Poate că aceasta este o casă pentru șoareci.
Și îmi scap oul,
de fapt rămâne intact.
Și întrebarea, așa cum
vor să știe toți oamenii de știință buni,
este care este cel mai înalt etaj
din clădirea mea din care
pot arunca un ou și să-
l rămân intact?
Și întrebarea este
cam amuzantă.
Este un fel de
design experimental, într-un fel.
Nu se cere, având în vedere aceasta
și o listă de experimente, să încerce să dau
seama, să deducă
ceva despre ouă.
Dar mai degrabă, se
spune, dacă proiectez cu atenție
o secvență de etaje de pe care
să-mi arunc ouăle,
din care să-
mi arunc ouăle, atunci
care este
numărul maxim de experimente pe care
trebuie să le fac pentru a triangula
pe acel etaj,
acel etaj critic.  ,
deasupra căruia îmi rup ouăle?
Deci ceea ce mi se oferă sunt
înălțimile podelelor
și o grămadă de ouă.
Într-un anumit sens,
bugetul ouălor
nu contează mai mult decât să
limităm dimensiunea
problemei noastre, într-un anumit sens.
Ceea ce contează cu adevărat este că aș
dori să folosesc mai puține de k ouă
pentru a determina asta.
Pentru că, desigur, pe cele
rămase o să le
folosesc
pentru a face o omletă.
Dar observă că
pot fi puțin
furiș în
designul meu experimental,
că ce se întâmplă dacă îmi
arunc oul de la un
podea foarte joasă a clădirii mele?  Ei
bine, rămâne intactă.
Așa că pot coborî scările.
Îmi pot ridica oul și
îl pot folosi pentru următorul meu experiment.
Și nu am plătit un ou.
Da?
Așa că prima întrebare pe care
ați putea-o pune
este, de ce naiba
n-aș
începe doar de la primul
etaj, las oul.
Dacă nu este rupt,
treceți la următorul
și apoi aruncați
oul și așa mai departe?
Acesta ar fi cel mai
eficient plan de ouă.
Și într-adevăr așa este
, pentru că vei
sparge cel mult un ou.
Dar te plimbi în
sus și în jos pe scări de
câteva ori când
rezolvi asta, nu?  De
fiecare dată, trebuie să
mergi să recuperezi acel ou nerupt.
Trebuie să fugi
pe scări, să
ridici chestia și apoi să
fugi la următorul etaj.
Și poate că în
problema dvs. de optimizare, în
loc să încercați să
minimizați numărul de ouă pe
care le spargeți, încercați
să minimizați cheltuielile
pentru quads.
Și, în schimb, ați sărit peste
ziua piciorului sau orice altceva,
iar lucrul pe care
încercați să îl minimizați
este suma peste înălțimile
picăturilor din experimentele dvs.
Așa că încercați să determinați
proprietățile mecanice
ale oului prin proiectarea
unui experiment, un fel
de procedură, care să
minimizeze numărul de ori în
care trebuie să aruncați ouă.
Pentru că de fiecare dată când o
faci,
trebuie să alergi până în jos pe
scări
și să te uiți la trotuar
și să vezi dacă oul s-a spart sau nu.
E multă muncă.
BINE.
Aceasta este diferită de
problema clasică egg-drop 6006, pe
care vă încurajez
să o căutați,
în iterațiile anterioare
ale acestui curs.
Staţi să văd.
Și, deci, întrebarea este, care este
numărul minim de picături de ouă pe care
trebuie să-l faceți pentru a vă asigura
că pentru orice tip de ou-- așa că
vă dau un
coș misterios de ouă
și trebuie să proiectați
procedura experimentală
și să legați numărul  de
această valoare particulară aici,
având în vedere un buget de k ouă.
BINE.
Și timpul pe care îl
avem pentru a face asta este ordinea n
cub k.
Aparent,
clădirea noastră, avem
multe ouă și nu
foarte multe etaje.
BINE.
Are
vreun sens configurația noastră aici?
Încercăm doar să evităm să
alergăm în sus și în jos pe scări.
Acesta este principalul lucru.
BINE.
Deci ce vom face?
SRTBOT, pentru că asta e tot ce
știm să facem, da?
Și în special, vom
face o observație, care
este oarecum utilă.
Dacă scap un podea...
ooh, dacă scap un
ou de pe podea,
în acest univers determinist,
în care mecanica ouălor este
foarte previzibilă, se

poate întâmpla doar unul dintre cele două lucruri.
Ori s-a
rupt oul, ori nu s-a rupt,
în timp ce eu dau din
nou peste scândură.
Deci, să ne gândim la
experimentul nostru.
Ține minte, la sfârșitul
zilei,
încercăm să descoperim cel mai
înalt etaj din clădirea mea
din care pot
arunca în siguranță un ou.
Deci, dacă mă gândesc la
acea înălțime a acelui etaj,
pentru un singur lucru, am
nevoie vreodată de un parantez
care să nu fie un set continuu sau
conectat de numere?
Răspunsul este nu, nu?  Nu
ar trebui să fie niciodată
cazul ca, oh,
cred că ouăle mele
ar putea fi la etajele unu--
doar numărul prim de etaje
din clădirea mea, sau ceva de genul.
Asta chiar
nu are sens, nu?
Pentru că dacă mă conving
oul meu se sparge la patru sau cinci,
atunci evident, de la etajele șase
la n, mi se sparge și oul.
Și așa pot întotdeauna să continui să
restrâng un interval.
Dreapta?
Deci, în special,
iată un S inteligent
în SRTBOT-ul meu, care înseamnă
că voi
spune că x, i, j,
e este egal cu minimul --
apropo, scriu asta
ca total minim  înălţime.
Așadar, acesta este numărul minim de
ori în care trebuie să cobor pe
scări și să-mi verific ouăle,
sau înălțimea totală pe care o cobor pe
scări -- numărul
de scări pe care le cobor,
presupunând că scările mele
au o înălțime de 1 picior --
unde  Mi-au rămas ouă.
Observați cum am
scris problema de data aceasta,
aș putea la fel de bine să folosesc
toate ouăle mele.
Asta nu mă costă nimic.
Ceea ce mă costă este să alerg în
sus și în jos pe scări.
Și că am etajele de la i la
j inclusiv de verificat.
Deci, cu alte cuvinte, dacă sunt
la un etaj sub etajul i,
m-am convins că
oul meu nu se va sparge.
Dar dacă mă aflu la un
etaj deasupra etajului j,
sunt convins că oul meu se va sparge.
BINE?
Deci ce fac?
Ei bine, amintiți-vă că aceasta este o
problemă de design experimental.
Îmi pot arunca oul de la orice
etaj f, care se află în intervalul de la i
la j.
Și, desigur, nu există
niciodată un motiv pentru care să
arunc un ou de la un
etaj sub i sau deasupra j,
pentru că știm deja
ce se întâmplă în acest caz.
BINE?
Deci, ce se întâmplă când facem asta?  Ei
bine, dacă
îl scap de la etajul f,
trebuie să plătesc, în ceea ce privește
funcția mea de cost, nu?
Pentru că, pentru a plăti înălțimea lui f,
am fugit pe scări.
BINE?
Dar în schimbul asta,
învăț puțin
despre problema mea cu ouă.
Obțin fie o limită superioară, fie
o limită inferioară a lui f,
în funcție de dacă
oul s-a rupt.
BINE?
Deci, hai să formalizăm
asta matematic.
Deci, în special,
avem x i, j, e.  Ei
bine, ce pot să
controlez în viața mea?
Și cu ce am de-a face?
Ei bine, cu ce am de-a
face este faptul
că nu știu ce se va
întâmpla cu oul.
S-ar putea rupe.
S-ar putea să nu.
Dreapta?
Și oul ar putea fi
un ou advers --
vrea să alergi în sus
și în jos pe scări.
Și trebuie să socotesc pentru asta.
Dar eu și
adversarul oului trebuie
să alegem pe ce etaj
îl scap.
Deci, amintiți-vă, am văzut un exemplu.  Am
uitat ce, de la clasă,
unde era un joc.
Un tip încerca să minimizeze.
Celălalt
încerca să maximizeze.
Într-un anumit sens, oul încearcă
să maximizeze cantitatea de muncă pe care trebuie să o
faci, alergând în sus
și în jos pe scări pentru a-ți face
experimentul.
O modalitate mai bună de a
spune este că
încercăm să limităm
cantitatea de lucru
în procedura dumneavoastră experimentală.
Și încerc să
elaborez o procedură care să-
mi minimizeze munca.
Deci, să spunem că
eu sunt jucătorul.
Așa că vreau să minimizez.
Și decizia pe care trebuie să o
iau, controlul pe care îl am,
ce este?
Ei bine, este ce podea aleg.
Deci, să presupunem că aleg etajul f.  Ei
bine, trebuie să
cobor scările.  Deci asta mă ia
hf.
Aceasta a fost urcarea
scărilor, este probabil
ceea ce presupune că coborârea nu
este nimic.
Dar mă abat.
Dar acum încă nu am terminat.  L-am
restrâns într-
unul din cele două cazuri, nu?
Fie f este noua mea
limită inferioară, fie noua mea limită superioară.
Și trebuie să țin cont de
ambele din recursiunea mea
și, de fapt, de maximul
celor două, în sensul
că am nevoie, în
fiecare caz posibil,
ca experimentul meu cu picături de ouă să îmi
îngusteze
podeaua la o lățime de 0.
Deci, în  în special, aceasta
este o problemă mini-max.
Există un maxim
de un minut aici.
Deci, ori s-a spart oul în
experimentul meu, ori nu.
Dreapta?
Deci, dacă s-a rupt, atunci, ei
bine, ce s-a întâmplat?  Ei
bine, să vedem aici.
Dacă oul s-a rupt, atunci am primit
o limită superioară pentru podeaua mea.
Deci limita mea inferioară
rămâne aceeași.
Sunt eu.
Limita mea superioară este f minus 1,
deoarece s-a rupt la etajul f.  Ei
bine, ce se întâmplă cu
ouăle când se sparg?
Nu le pot scăpa
din nou de pe podea.
Așa că am pierdut un ou.
BINE?
Deci acesta este oul meu rupt.
BINE?
Sau oul meu nu s-a rupt.
Deci, în acest caz,
dacă oul mi s-a spart,
acum am o limită inferioară.
Deci nu sunt clar doar
despre etajele f plus 1.
Dar limita superioară
nu s-a schimbat.
Mai este j.
Și câte ouă am?  Ei
bine, oul meu nu s-a
spart, așa că pot să cobor
scările, ceea ce
va fi obositor,
am dat seama de asta aici.
Dar măcar îmi
pot reutiliza oul.
Deci nu am pierdut nimic.
BINE?
Și pot să aleg.
Deci, observați... hopa...
deci
vedeți de ce există un maxim aici?
În esență, trebuie să țin cont
de fiecare scenariu posibil
atunci când îmi proiectez
procedura experimentală.
Dar ajung să
minimalizez, în sensul
că pot alege ce
podea la fiecare pas.
Deci, în special, f aici este
în intervalul i la j, așa.
OK, iar acum avem
formula noastră recursivă
pentru picătura de ou, care
minimizează înălțimea totală.
Deci acum să terminăm
SRTBOT în patru minute.
De fapt, nu este prea greu.
Așa că cred că vom reuși o

dată, eliminând
20% din problemele pe care
trebuia să le acopăr.  În
regulă.
Deci, în primul rând, care este
ordinea noastră topologică?  Deci
asta pare cam
enervant.
Pentru că, de
obicei, cred că ne gândim să
cheltuim lucruri în multe
dintre aceste probleme de programare dinamică
.
Dar cheltuim de fapt un ou?
Nu neapărat, nu?
Pentru că în acest
apel recursiv, numărul de ouă pe care le
aveam a rămas același.
Deci, poate că nu este de fapt
o modalitate grozavă de a stabili
o ordine topologică.
Dar, în schimb, ce știm?
Care este
scopul unui experiment în știință?
Este pentru a ne îmbunătăți
înțelegerea lumii.
În acest caz,
lumea noastră este formată doar
din ouă și etaje ale clădirilor.
Și în special,
odată ce scapă acel ou,
învăț ceva
despre clădirea mea.
Și am restrâns
gama de etaje
care sunt incerte pentru mine.
Deci, în special,
știu că x i,
j, e depinde doar de x, presupun,
i prim, j prim, e prim,
cu ce?  Ei
bine, sub-problemele mele,
am întotdeauna o gamă mai mică de defecte
decât am avut înainte.
Deci, în special,
j prim minus i
prim va fi mai mic
strict decât j minus i.
Și asta îmi va da
ordinea topologică.
Misto.
Și asta e de fapt, cred,
genul de parte enervantă,
în afară de a rezolva această
expresie mini-max aici.
Lucrurile rămase
nu sunt atât de grele.
Deci, care sunt cazurile noastre de bază?  Ei
bine, să zicem că
mai am 0 ouă.
Dar mai am un set
de etaje incerte.
Sunt vești proaste.
Da?
Da, deci ar
trebui să fie infinitul.
Și motivul este, desigur, că voi
lua minul aici.
Dreapta?
Și, evident, nu ar trebui să
aleg niciodată infinitul ca min.
Deci, cu alte cuvinte,
nu ar trebui să aleg niciodată o opțiune
pentru o podea care
ar putea să mă conducă
la un scenariu incert,
când rămân fără ouă, da?
În plus, există un
alt caz de bază aici.
Acesta este că nu mai am ouă,
dar câteva etaje de verificat,
este al doilea, i minus 1e.
Deci, în acest caz, mi-au
rămas ouă și am terminat, nu?  L-am
restrâns
până la limite.
De altfel, felul în care l-am scris
în termeni de incluziune,
versus exclusiv, ar putea
fi puțin neplăcut.
Aici, băieți,
nu ar trebui să plecați cu 1,
așa cum face adesea instructorul vostru.
Dar în orice caz,
aici, ești 0, nu?
Nu mai sunt
etaje de verificat.  L-
ați
restrâns la un interval de 1.
Din nou, ceva
ce nu am timp,
așa că nu voi
verifica cu atenție,
este dacă limitele mele sunt inclusive,
dacă ar fi i, j minus 1--
i  minus 1 sau doar eu, eu?
Dar cred că
sunteți suficient de deștepți ca să
rezolvați asta acasă.
Care ar fi cazul meu inițial
, ei bine, acum
am toate etajele de
verificat și toate ouăle mele
în coșul meu metaforic aici.
Deci am etajele 1 la n aici.
Și problema îmi spune că
am k ouă când încep.
Și apoi, în sfârșit, trebuie
să-mi rezolv sub-problemele aici.
Cred că poți
simplifica
puțin argumentul scris.
Și din nou, uită-te
la subproblemele tale.
Sunt indexate
după trei numere,
voi face o
estimare foarte conservatoare.
Cred că problema
realizează o estimare mai bună,
dar apoi asimptotic,
este la fel.
Care este limita noastră pentru
primul și al doilea indice?  Ei
bine, ambele sunt
doar indicele
etajelor, care
merg între 0 și n.
Da?
Evident, ai putea face mai bine
decât atât, pentru că
etajul inferior este întotdeauna mai mic decât
etajul superior, ceea ce
explică problema.
Dar dacă sunt leneș,
atunci, ei bine, există
n subprobleme pătrate pentru a
explica cele două etaje.
Iar al treilea
indice sunt ouăle tale, din
care ai cel mult k.
OK, câtă muncă
avem pe sub-problemă?  Ei
bine, să vedem aici.
Există o buclă for peste f.
f Este peste etaje.  Din
nou, dacă voi
fi cu adevărat conservator,
ei bine, există cel mult n
etaje în total în clădirea mea.
Și asta ne duce la
un timp de rulare și n cube k,
care este ceea ce ne-am dorit,
la sfârșitul zilei.
BINE?
Acesta ar trebui să fie un O mare aici,
deoarece cred că din punct de vedere tehnic,
acesta este n plus 1, pentru a ține
cont de etajul zero.
BINE.
Și asta rezolvă
experimentul nostru cu picăturile de ou.
Cred că acesta este unul frumos.
Și cred că, în
mintea mea, de fapt,
în ceea ce privește
programarea dinamică, acesta
este unul dintre lucrurile mai greu
de corectat,
care sunt aceste jocuri mini-max.  Ar
trebui să mă gândesc
la asta, ceea ce
în cele două minute negative,
nu voi avea timp să fac.
Cred că în curs, modul în
care rezolvăm problema de minimizare
a fost separarea
minului și maximului
și ne-am gândit că
există două probleme de programare dinamică
care
interacționează una cu cealaltă.  Probabil că ați
putea să-l scrieți și pe
acesta în acea formă,
cred, doar scoțând
acest termen și gândindu-vă
la el ca pe o matrice diferită.
Dar și această formă este
perfectă.  Oricare e
bine.
Dar în mintea mea, acestea
sunt cele mai greu
de rezolvat în
programarea dinamică.
Așa că aș alege oricare dintre ele se află
în creierul tău.
Deci, în treaba ta, ar trebui să
alegem să o lăsăm în pace?
Este o a cincea problemă
aici, la care, ca de obicei,
nu am reușit să ajung,
unde construiești pereți
punând plăci.
Acesta este unul interesant
, deoarece timpul de rulare
este exponențial.
Dar problema
îți spune că asta e permis.
Dar există unele
lucruri exponențiale care sunt în regulă
și altele care nu sunt.
În esență, ceea ce
nu vrei este produsul
a două exponențiale uriașe.
Ați dori să
o reduceți doar la unul.
Publicul:
Practic spune că va
fi polinom
[INAUDIBIL] mic [INAUDIBIL]..
JUSTIN SOLOMON: Așa este.
Sau este polinom în
orice, cu excepția lucrurilor în care
este exponențial.
Și, în plus, lucrurile
în care este exponențial sunt mici.
Și problema spune asta.
Așa că vă încurajez
să aruncați o privire.
Pentru că într-adevăr este nevoie de
ceva timp pentru a logic prin ea.
Dar configurația pentru
acea problemă este,
cred, mai lungă decât poate suporta
scrierea mea glacial de lentă pe tablă
.
Dar cu asta,
o vom numi pentru ziua respectivă.