[SCRÂȘIT]
[FOSȘIT]
[CLIC]
JASON KU: Bună
dimineața, tuturor.
STUDENT: Dimineața...
JASON KU: Numele meu este Jason Ku.  Voi preda

această clasă în Introducere în
algoritmi cu
alți doi instructori aici --
profesori din departament --
Eric Demaine și Justin Solomon.
Sunt
oameni excelenți, așa că
vor lucra la predarea
acestui curs cu mine.
Voi preda
prima prelegere
și îi vom pune pe
fiecare dintre ei să predea
una dintre următoarele două prelegeri,
apoi vom merge de acolo.
Aceasta este Introducere în algoritmi.
OK, așa că vom începe să
vorbim despre conținutul acestui curs
acum.
Despre ce este acest curs?
Este vorba despre algoritmi--
introducere în algoritmi.
Într-adevăr, despre ce
este vorba în curs este să
te învețe să rezolvi
probleme de calcul.
Dar este mai mult decât atât.
Nu este vorba doar să
te înveți să rezolvi
probleme de calcul.
Scopul 1 - rezolvarea
problemelor de calcul.
Dar este mai mult decât atât.
Este, de asemenea, să comunici
acele soluții altora
și să poți comunica
că modul tău de a rezolva
problema este
corect și eficient.
Deci este vorba despre încă două lucruri--
să dovedesc corectitudinea, să
argumentezi eficiența
și, în general, este vorba
despre comunicare--
nu pot scrie, apropo--
comunicarea acestor idei.
Și veți descoperi că, pe parcursul
acestei cursuri,
veți
scrie mult mai mult decât faci
în multe dintre celelalte cursuri ale tale.  Poate că ar
trebui să
fie un fel de clasă CI,
pentru că veți
scrie mult mai mult decât
veți codifica, cu siguranță.
Desigur, rezolvarea
problemei de calcul
este importantă, dar
într-adevăr, lucrul pe
care îl obțineți din această
clasă și din alte clase de teorie
pe care nu le primiți la
alte clase din acest departament
este că ne
concentrăm cu adevărat să fim
capabili să dovedim  că
lucrurile pe care le faci
sunt corecte și mai bune
decât alte lucruri și,
fiind capabil să comunici
acele idei altora, și nu
doar unui computer --
altor oameni, convinge-
i că este corect.
OK, deci despre asta
e vorba în această clasă.
Deci, ce vreau să spun când spun
rezolvarea unei probleme de calcul?
Ce este o problemă?
Ce este un algoritm?
Oamenii își bat joc de mine pentru că
încep cu această întrebare,
dar vrea cineva să
răspundă la acea întrebare?
Nu?
Care este o problemă, din
punct de vedere computațional?
Nu?
OK, deci nu este
o întrebare atât de stupidă.
Da?
STUDENT: [INAUDIBIL]
JASON KU: Ceva ce
vrei să calculezi...
OK, da, este adevărat.
Dreapta.
Dar puțin mai
abstract, ceea ce voi
gândi despre o
problemă de calcul fiind -
și aici ar trebui să intervină
condiția dvs. prealabilă
în matematică discretă -

o problemă este că
aveți un set de intrări.
Poate am una, două, trei,
patru, cinci intrări posibile pe care le-aș
putea avea la algoritmul meu.
Apoi am un spațiu de ieșiri.  Nu
știu.
Poate că am mai multe dintre
ele decât intrări,
dar acestea sunt
ieșirile posibile pentru problema mea.
Și ceea ce este o problemă
este o relație binară
între aceste
intrări și ieșiri.
În esență, pentru fiecare intrare,
precizez care dintre aceste ieșiri
este corectă.
Nu trebuie neapărat
să fie unul.
Dacă spun, dați-mi indexul într-
o matrice care conține valoarea
5, ar putea exista mai multe
5 în acea matrice
și, prin urmare, oricare dintre acești
indici ar fi corect.
Deci, poate acest tip se mapează la acea
ieșire și poate acest tip se mapează
la --
nu știu -- două
sau trei ieșiri.
Această intrare merge la unu, doi...
Nu știu.
Există un fel
de cartografiere aici.
Aceste muchii reprezintă
o relație binară
și este un fel de
grafic, un grafic bipartit
între aceste
intrări și ieșiri.
Și acestea specifică
care dintre aceste ieșiri
sunt corecte pentru aceste intrări.
Aceasta este cu adevărat
definiția formală
a ceea ce este o problemă.
Acum, în general, dacă
am o problemă -
o
problemă de calcul, nu
vă voi specifica problema
spunând: OK, pentru intrarea 1,
răspunsul corect este
0, iar pentru intrarea 2,
răspunsul corect este 3.  ,
și așa mai departe și așa mai departe.
Asta ar dura o veșnicie, nu?
De obicei, ceea ce facem
atunci când definim o problemă
este să specificăm un fel de
predicat, spunând că, oh
, putem verifica--
dacă vă dau o
intrare și o ieșire,
pot verifica dacă acea
ieșire este corectă sau nu.  De
obicei, așa
definim o problemă,
dacă verific dacă
acest index conține un 5,
pot să merg la acea matrice, să mă
uit la indexul 5 și--
sau indexul pe care mi l-ai dat
și să văd dacă este egal cu 5
Deci, de obicei,
o punem în termeni de predicate
pentru că, în general,
nu
vrem cu adevărat să vorbim despre
cazuri mici de probleme.
Deci, să presupunem că am avut
problema ca,
printre elevii din această
clasă, vreo pereche dintre voi
are aceeași zi de naștere?
În regulă, probabil, dacă
sunteți mai mult de 365,
răspunsul este da.
Dreapta?  Cu
ce?

Principiul porumbeilor... doi dintre voi
trebuie să aibă aceeași zi de naștere.
Deci, să generalizăm
puțin, să spunem că...
Nu știu...
Am nevoie de un spațiu mai mare de
zile de naștere pentru ca această întrebare
să fie interesantă.
Poate abordez anul.
Poate mă refer la
ora la care te-ai născut.
Și acesta este un spațiu mai mare
de intrări
și nu m-aș
aștepta neapărat ca doi dintre voi să se
nască în
același an, în aceeași zi,
la aceeași oră.
Ar fi
puțin mai puțin probabil.
De fapt, atâta timp cât acel
spațiu este mai mare decât ceva de
genul pătratului
numărului dintre voi, atunci
sunt mai puțin probabil să
am o pereche de voi.
Este o problemă cu ziua de naștere pe care este
posibil să o fi văzut în 042,
potențial.
Dar, în general, nu...
nu o să mă încurc
atât de mult cu probabilitatea aici.
Vreau un
algoritm determinist, care să
verifice imediat dacă doi dintre
voi aveți aceeași oră de naștere, să
spunem.
Bine, deci, în general,
în această clasă,
nu ne vom
concentra pe intrări, cum ar fi,
există o pereche de
voi în această clasă
care au aceeași zi de naștere?
E cam plictisitor.
Aș putea face o mulțime de
lucruri diferite,
dar ceea ce facem noi în
această clasă...
este pentru o clasă fixă ​​a voastră.
Vreau să fac algoritmi
generali pentru orice sală de clasă,
să merg la recitarea ta.
Vreau un algoritm care să se
aplice recitării tale.
Vreau un algoritm care să se
aplice nu numai pentru această clasă,
ci și pentru
clasa de învățare automată din fața dvs.
Vreau un algoritm
care să-și schimbe --
poate accepta o
intrare de dimensiuni arbitrare.
Aici avem o clasă de
poate 300, 400 de studenți,
dar vreau ca algoritmul meu să
funcționeze pentru un miliard de studenți.
Poate încerc
să verific dacă există
o potrivire a ceva în
baza de date Facebook
sau ceva de genul ăsta.
Deci, în general,
căutăm probleme generale care
au intrări de dimensiuni arbitrare.
Deci, aceste intrări ar putea
crește foarte mult,
dar dorim un fel de
algoritm de dimensiune fixă
pentru a rezolva aceste probleme.
Deci, ce este un algoritm?  Chiar
nu pot scrie...
ți-am spus.
Nu te-am mințit.
Deci un algoritm este puțin
diferit de o problemă.
O specificație de problemă--
vă pot spune cum
arată acest grafic.
Un algoritm este într-adevăr...
Nu știu care
sunt ieșirile.
Nu știu ce
sunt aceste margini.
Dar vreau o
mașină sau o procedură de dimensiune fixă
care, dacă îi dau o intrare,
va genera o ieșire.
Și dacă generează
o ieșire, ar fi mai bine
să fie una dintre aceste ieșiri corecte.
Deci, dacă am un algoritm
care preia această intrare,
chiar vreau să
scoată această ieșire,
sau altfel nu este un
algoritm corect.  În
mod similar, pentru acesta, ar
putea scoate oricare dintre aceste trei
ieșiri, dar dacă scoate
acest tip pentru această intrare,
acesta nu ar fi un
algoritm corect.
Și așa, în general, ceea ce vrem
este un algoritm este o funcție.
Preia intrări la ieșiri.
Un algoritm este un
fel de funcție
care preia aceste intrări,
le mapează la o singură ieșire
și acea ieșire mai bine să fie
corectă pe baza problemei noastre.
Deci asta este algoritmul nostru.
Rezolvă
problema dacă returnează
o ieșire corectă pentru
fiecare intrare de problemă
care se află în domeniul nostru.
Are cineva un
posibil algoritm
pentru a verifica dacă
doi dintre voi
au aceeași oră de naștere,
așa cum s-a specificat mai înainte?  O să las pe

altcineva să încerce.
Sigur.
STUDENT: Întrebați pe toți
unul câte unul și de fiecare dată
[INAUDIBIL]
JASON KU: Grozav, așa că ceea ce
a spus colegul tău
este un algoritm grozav.
În esență, ceea ce va
face
este că
vă voi pune într-o anumită ordine,

vă voi oferi fiecăruia dintre voi
un număr, de la unul la cât de
mulți studenți
există în această clasă.
Și o să
vă intervievez unul câte unul.
Am să spun,
care este ziua ta?
Și am să-l notez.
O să-l pun într-
un fel de înregistrare.
Și apoi, în timp ce tot ți-am
interviu, o să

aflu ziua ta de naștere.
Am să verific înregistrarea.
Mă voi uita prin toate
zilele de naștere din înregistrare.
Dacă găsesc o potrivire, mă
întorc, da... am
găsit o pereche... și mă pot opri.
Altfel, dacă trec
prin lista de înregistrări,
nu-- și
nu găsesc o potrivire,
doar te lipesc la
sfârșitul înregistrării--
te adaug la
înregistrare, apoi trec
la  următoarea persoană.
continui sa fac asta.
OK, deci acesta este un
algoritm propus
pentru această problemă de naștere.
Pentru problema zilei de naștere,
care este algoritmul aici?
Păstrați o înregistrare.
Intervievați studenții
într-o anumită ordine.
Și ce
înseamnă intervievarea unui student?
Înseamnă două lucruri.
Înseamnă să verifici dacă
ziua de naștere este înregistrată.
Și dacă este, returnați o pereche.
Deci întoarceți pereche.
În caz contrar, adăugați un nou
student pentru înregistrare.
Și apoi, la final,
dacă trec prin toată lumea
și nu am găsit
încă un meci, o să
revin
că nu există.
OK, deci este o declarație
a unui algoritm.
Acesta este un fel de
nivel de descriere
pe care îl vom căuta
în cele trei părți ale acestei--
întrebări teorie pe care
vi le punem la seturile de probleme.
Este o descriere verbală
în cuvinte care--
poate că nu este suficient ca un
computer să știe ce să facă,
dar dacă ai spune acest algoritm
oricăruia dintre prietenii tăi
din această clasă, ei
ar înțelege cel puțin
ce anume ești  face.
Da?
STUDENT: Un algoritm
trebuie să fie o funcție pură
în sens matematic?
JASON KU: Un algoritm
trebuie să fie o funcție pură
în sens matematic?
Ca și în ea, trebuie să se mapeze
la o singură ieșire?
STUDENT: Ca în ea, nu se poate
modifica vreo stare externă.
Nu poate lua în stare
și nu poate face I/O.
JASON KU: Deci
vorbim despre un fel
de definiție de programare funcțională
a unei funcții.
Vorbesc despre
matematică--
am o
relație binară, iar acest lucru
are o ieșire pentru fiecare
intrare și există exact
o ieșire pentru fiecare intrare.
Aceasta este
definiția matematică a funcției pe
care o folosesc atunci când
definesc un algoritm.
Da?
STUDENT: Practic,
un algoritm este ca un plan?
JASON KU: Da.
Un algoritm este o
procedură care, cumva,
pot face orice
vreau, dar trebuie să
iau una dintre aceste intrări și
trebuie să produc o ieșire.
Și la sfârșit,
mai bine să fie corect.
Deci este doar o procedură.
Te poți gândi la ea
ca la o rețetă.
Este doar un
fel de procedură.
Este o secvență de lucruri pe
care ar trebui să le faci
și apoi, la sfârșit,
vei returna o ieșire.
Iată un posibil algoritm
pentru rezolvarea acestei
probleme de naștere.
Acum, ți-am dat...
ceea ce îți argumentez, sau îți
afirm,
este o soluție la această
problemă de naștere.
Și poate că sunteți de
acord cu mine
și poate unii dintre voi nu.
Deci, cum te conving
că acest lucru este corect?
Dacă aș rula
acest algoritm pe, să zicem,
cei patru studenți din
primul rând aici,
v-aș putea argumenta
destul de bine.  Le-aș
putea atribui
oamenilor zile de naștere
în diferite combinații
fie dintre ele--
niciunul dintre ei nu are aceeași
zi de naștere, unii dintre ei
au aceeași zi de naștere.
Aș putea încerca toate
posibilitățile și aș
putea trece prin multe
posibilități diferite
și trebuie să verific dacă
acest algoritm returnează
răspunsul corect
în toate astfel de cazuri.
Dar când voi avea...
nu știu...
300 dintre voi, asta va
fi puțin
mai greu de argumentat.
Și deci, dacă vreau să argumentez că
ceva este corect în...
Vreau să-ți demonstrez ceva
pentru o valoare mare, ce fel
de tehnică folosesc
pentru a dovedi astfel de lucruri?
Da?
Inductie, nu?
Și, în general, ceea ce facem
în această clasă, ceea ce facem
este că, ca informatician,
scriem o bucată
de cod de dimensiune constantă care poate prelua orice
intrare de dimensiune arbitrar de mare.
Dacă intrarea poate fi arbitrar de
mare, dar codul nostru este mic,
atunci acel cod trebuie
să facă buclă, să recurgă
sau să repete unele dintre
aceste linii de cod
pentru a
citi doar acea ieșire.
Și, deci, acesta este un alt mod în care
puteți ajunge la această concluzie,
că
probabil va trebui
să folosim recursiunea, inducția.
Și acesta este o parte
din motivul pentru care
vă cerem să urmați
un curs de demonstrații,
raționament inductiv
și matematică discretă
înainte de această clasă.
OK, deci cum demonstrăm
că acest lucru este corect?
Trebuie să folosim inducția.
Deci, cum putem
configura această inducție?
De ce am nevoie pentru
o dovadă inductivă?
Sigur.
STUDENT: [INAUDIBIL]
JASON KU: Caz de bază -
avem nevoie de un caz de bază.
Avem nevoie de un fel
de predicat.
Da, dar avem nevoie de
un fel de declarație
a unei ipoteze despre ceva
care ar trebui menținut.
Și apoi trebuie să avem un
pas inductiv, care practic
spune că iau o
valoare mică a acestui lucru,
folosesc
ipoteza inductivă și o argumentez
pentru o valoare mai mare a
mulțimii mele bine ordonate
pe care o induc.
Pentru acest algoritm,
dacă vom
încerca să dovedim corectitudinea,
ceea ce voi face
este să--
ce vreau să
demonstrez pentru acest lucru?
Că, la sfârșitul
interviului cu voi toți,
algoritmul meu
fie a
revenit cu
o pereche care se potrivește,
fie dacă ne aflăm într-un
caz în care
nu a existat o pereche undeva în
setul meu, că  a returnat niciunul.
Dreapta?
Asta ar fi corect.
Așadar, cum pot
generaliza acest concept
pentru a-l face ceva în care să
pot induce?
Ceea ce voi face
este să spun... să
spunem, după ce am
intervievat primii
elevi K, dacă a existat o potrivire
la acei primii K elevi,
vreau să fiu sigur că
m-am întors  o pereche--
pentru că dacă, după ce vă
intervievesc pe toți, am
păstrat
acea proprietate, atunci voi
fi sigur că, la
sfârșitul procesului,
voi fi returnat
o pereche, dacă există una.
Deci aici va fi
ipoteza mea inductivă.
Dacă primii K elevi
conțin o potrivire,
algoritmul returnează o potrivire
înainte de a intervieva, de exemplu,
elevul K plus 1.
Deci aceasta va fi
ipoteza mea inductivă.
Acum, dacă sunt n
studenți în această clasă
și, la sfârșitul
lucrurilor mele, încerc
să intervievez un student n plus
1 -- oh, studentul n plus 1
nu este acolo.
Dacă am menținut acest lucru,
atunci, dacă înlocuiesc K cu n,
atunci voi fi
returnat o potrivire
înainte de a intervieva
ultimul student --
când nu
mai am studenți.
Și apoi acest algoritm
nu returnează niciunul, așa cum ar trebui.
OK, deci această ipoteză inductivă
stabilește o variabilă frumoasă pe care să o
induceți.
Acest K I poate avea
creștere, până la n,
începând de la un caz de bază.
Deci, care este cazul meu de bază aici?
Cazul meu de bază este-- cel
mai ușor lucru pe care îl pot face--
sigur-- 2?
Este un lucru ușor pe care l-aș putea face.
Aș putea verifica acele
posibilități,
dar există un
caz de bază și mai ușor.
Da?
Există un
caz de bază și mai ușor decât 1.
STUDENT: 0--
JASON KU: 0, nu?
După ce am intervievat 0 studenți,
nu am lucrat, nu?  Cu
siguranță, primul
0 nu poate avea o potrivire.
Această
ipoteză inductivă este adevărată
doar pentru că acest
predicat inițial este fals.
Deci, pot spune, caz de bază 0--
verificați.  Cu
siguranță, acest
predicat este valabil pentru asta.
BINE.
Acum trebuie să mergem după
carnea chestia asta.
Să presupunem că
ipoteza inductivă adevărată
pentru K este egală, de exemplu, cu un K prim.
Și luăm în considerare
K prim plus 1.
Atunci avem două cazuri.
Unul dintre
lucrurile frumoase despre răpire
este că ne izolează problema
să nu luăm în considerare totul
dintr-o dată, ci să o
descompun într-o interfață mai mică,
astfel încât să pot lucra mai puțin
la fiecare pas.
Deci sunt două cazuri.
Fie primul K
avea deja o potrivire --
caz în care, prin
ipoteza noastră inductivă,
am returnat deja
un răspuns corect.
Celălalt caz este --
nu are o potrivire și
intervievăm elevul K plus al 1-lea --
elevul K prim plus al 1-lea.
Dacă există o potrivire în
primul K prim plus 1 elevi,
atunci va include K plus -
studentul K prim plus
1, pentru că, altfel,
ar fi existat o potrivire
în lucrurile dinaintea lui.
Deci sunt două cazuri.
Dacă K conține potrivire, K prim.
Dacă primul K conține potrivire -
deja returnat prin inducție.
Altfel, dacă K prim plus 1
student conține potrivire,
algoritmul verifică toate
posibilitățile --
K prim verifică
împotriva tuturor elevilor,
în esență prin forță brută.
Este o analiză de caz.
Verific toate
posibilitățile.
Verificați dacă ziua de naștere este înregistrată...
Nu v-am spus
încă cum să faceți asta,
dar dacă pot
face asta, voi
verifica dacă este în înregistrare.
Dacă este în evidență,
atunci va exista o potrivire
și o pot returna.
În caz contrar, am-- restabilim
ipoteza inductivă
pentru K prim plus 1 elevi.
Are sens, băieți?
Da.
OK, deci așa
dovedim corectitudinea.
Acest lucru este puțin
mai formal decât ți-am
cere să faci la
această clasă tot timpul,
dar cu siguranță este suficient
pentru nivelurile de argumente
pe care ți-o vom cere să le faci.
Bara pe care
încercăm de obicei să o setăm
este că, dacă ai comunica
altcuiva care ia
această clasă care
este algoritmul tău,
ar putea să-l
codifice și să-i spună unui computer prost
cum să facă acel lucru.
Aveți întrebări despre inducție?  Îl vei
folosi pe tot
parcursul acestei clase
și, deci, dacă nu ești familiarizat
cu această linie de argumentare,
atunci ar trebui să te
revezi o parte din asta.
Asta ar fi bine.
Bine, deci este corectitudine,
fiind capabil să comunice
că problema--
algoritmul pe care l-am
declarat a fost corect.
Acum vrem să argumentăm
că este eficient.
Ce înseamnă eficiență?
Eficiența înseamnă
nu numai cât de repede
rulează acest algoritm,
ci cât de repede se
compară cu alte modalități posibile
de abordare a acestei probleme?
Deci, cum am putea măsura
cât de repede rulează un algoritm?
Aceasta este un fel de
întrebare prostească.
Da?
STUDENT: [INAUDIBIL]
JASON KU: Da.  Ei
bine, înregistrați doar timpul
necesar unui computer
pentru a face acest lucru.
Acum, există o problemă cu
doar codificarea unui algoritm,
spunerea unui computer ce să facă
și cronometrarea cât timp durează.
De ce?
Da?
STUDENT: [INAUDIBIL]
JASON KU: Ar depinde de
dimensiunea setului dvs. de date.
Bine, ne așteptăm la asta, dar
există o problemă mai mare acolo.
Da?
STUDENT: [INAUDIBIL]
JASON KU: Depinde de
puterea computerului tău.
Așa că m-aș aștepta ca, dacă aș
avea un calculator cu ceas
și l-aș programa
să facă ceva,
ar putea dura mult mai mult pentru a
rezolva o problemă decât dacă aș cere
computerului de cercetare al IBM să
rezolve aceeași problemă folosind
același algoritm,
chiar și cu  același cod,
deoarece operațiunile sale de bază
sunt mult mai rapide.
Cum rulează este mult mai rapid.
Așa că nu vreau să
număr cât timp
ar dura pe o mașină adevărată.
Vreau să retrag
timpul necesar mașinii
pentru a face lucruri din imagine.
Ceea ce vreau să spun
este, să presupunem
că fiecare tip de
operație fundamentală pe care o poate
face computerul durează o
perioadă fixă ​​de timp.
Câte dintre aceste tipuri
de operații fixe

trebuie să efectueze algoritmul pentru a
putea rezolva această problemă?
Deci aici nu măsurăm timpul.
În schimb, numărați
operațiile fundamentale.
BINE?
Vom ajunge la unele dintre
aceste operațiuni fundamentale
într-o secundă,
dar ideea este că
vrem o măsură a cât de bine
funcționează un algoritm,
nu neapărat
o implementare
a acelui algoritm - un
fel de noțiune abstractă a
cât de bine acest algoritm  face.
Și așadar, ceea ce vom folosi
pentru a măsura timpul sau eficiența
este ceva numit
analiză asimptotică.
Înțelege cineva de aici ce
este analiza asimptotică?
Probabil, deoarece este în ambele
precondiții, cred...
dar vom trece printr-
o definiție formală
a notației asimptotice
mâine în recitare
și veți obține multă
practică în compararea funcțiilor
folosind o analiză asimptotică.
Dar doar ca să vă faceți
o idee, ideea
aici este că nu măsurăm timpul.  În
schimb măsurăm operațiunile.
Și așa cum spunea colegul tău
de aici înainte,
ne așteptăm la performanță --
Voi folosi performanța,
în loc de timp aici --
ne așteptăm ca asta să depindă
de dimensiunea contribuției noastre.
Dacă încercăm să
rulăm un algoritm
pentru a găsi o zi de naștere
în această secțiune, ne
așteptăm ca algoritmul să ruleze
într-un interval de timp mai scurt
decât dacă ar fi să rulez
algoritmul pe toți.
Așadar, ne așteptăm să
funcționeze diferit,
în funcție de
dimensiunea intrării
și cât de diferit este
modul în care măsurăm performanța
față de acea intrare.
De obicei, folosim n ca variabilă
pentru dimensiunea intrării noastre
, dar nu este
întotdeauna cazul.
Deci, de exemplu, dacă avem
o matrice pe care ți-o dau --
o matrice n-by-n, asta --
vom spune n,
dar care este
dimensiunea intrării noastre?
Câte informații
trebuie să vă transmit pentru a
vă oferi acele informații?
Este n pătrat.
Deci, aceasta este dimensiunea
contribuției noastre în acest context.
Sau dacă vă dau un grafic,
de obicei este numărul de vârfuri
plus numărul de muchii.
Atât de mare... de
cât spațiu mi-
ar trebui să vă transmit
acel grafic, acea informație.
Comparăm cât de rapid
este un algoritm în raport
cu dimensiunea intrării.
Vom folosi
notația asimptotică.
Avem notația mare O, care
corespunde limitelor superioare.
Vom avea omega, care
corespunde limitelor inferioare.
Și avem theta, care
corespunde ambelor.
Chestia asta e strânsă.
Este mărginită de
sus și de jos
de o funcție a acestei forme.
Avem câteva
funcții comune
care leagă
dimensiunea intrării unui algoritm de
performanța sa, unele lucruri pe care le-am
văzut tot timpul.
Poate cineva să-
mi dea unele dintre acestea?
STUDENT: [INAUDIBIL]
JASON KU: Spune din nou.
STUDENT: [INAUDIBIL]
JASON KU: Îmi pare rău.
Îmi pare rău.
Nu pun
bine această întrebare,
dar a auzit cineva
de un algoritm liniar -
un algoritm de timp liniar?
Practic, asta înseamnă că
timpul de rulare al algoritmului meu -
performanța algoritmului meu
este liniară în raport
cu dimensiunea intrării mele.
Dreapta?
Da?
STUDENT: [INAUDIBIL]
JASON KU: Spune din nou.
STUDENT: Ca să pun
ceva într-o listă...
JASON KU: Ca să pun
ceva într-o listă...
OK.
Există multe în
spatele acestei întrebări pe care le vom
aborda
mai târziu în această săptămână.
Dar ăsta e un exemplu,
dacă o fac într-un mod prostesc,
bag ceva în
mijlocul unei liste
și trebuie să mută totul.
Aceasta este o operație care
ar putea dura timp liniar.
Deci timpul liniar este
un tip de funcție.
Avem câteva dintre acestea.
Am să încep
cu acesta.
Știe cineva că acesta este?
Timp constant-- practic,
indiferent de modul în care schimb intrarea, de
cât timp durează
acest timp de rulare--
performanța
algoritmului meu,
nu depinde cu adevărat de asta.
Următorul este
ceva de genul acesta.
Acesta este timpul logaritmic.
Avem data n, care
este liniară, și log n.
Uneori numim
acest log liniar,
dar de obicei spunem doar n log n.
Avem un
timp de rulare pătratic.
În general, dacă am o
putere constantă aici,
este de la n la c
pentru o constantă.
Acesta este ceea ce numim
timp polinomial,
atâta timp cât c este o constantă.
Și asta chiar aici este
ceea ce înțelegem prin eficient,
în această clasă, de obicei.
În alte clase, când
ai seturi mari de date,
poate că acest lucru este eficient.
Dar în această clasă, în general,
ceea ce ne referim este polinom.
Și pe măsură ce renunți la
chestia asta, lucrurile
sunt din ce în ce mai eficiente.
Există o clasă
despre care am să vă vorbesc aici,
care este ceva de genul... să
facem asta... 2 la
theta lui n, timp exponențial.
Aceasta este o constantă pentru
o funcție a lui n care este,
să spunem, super liniară,
care va fi destul de rău.
De ce este destul de rău?
Dacă ar fi să trasez unele dintre aceste
lucruri în funcție de n-- să
presupunem că am reprezentat aici valori de până
la 1.000 pe scara mea n.
Cum arată constanta?
Poate că aici sunt 1.000.
Cum arată o constantă?
Arată ca o linie...
pare o linie
pe aici undeva.  Ar
putea fi atât de mare pe cât
vreau, dar în cele din urmă,
orice este o
funcție în creștere
va deveni mai mare decât aceasta.
Și pe această scară,
dacă folosesc baza de logare
2 sau o
constantă mică rezonabilă,
cum arată log?  Ei
bine, hai să facem unul mai ușor.
Cum arată liniarul?
Da, asta... asta am
văzut ce faceți mulți dintre voi.
Asta e liniar.
Acesta este genul de bază cu care
comparăm totul
.
Cum arată jurnalul?
Așa... OK,
dar la această scară,
într-adevăr, este mult mai aproape
de constantă decât de liniar.
Și de fapt, pe măsură ce n devine
mult, mult mai mare, aceasta aproape că
arată ca o linie dreaptă.
Aproape că pare o constantă.
Deci log este aproape la fel de
bun ca constant.
Cum arată exponențialul?
Este exact
inversul acestui lucru.
Este aproape o
linie dreaptă exactă în sus.
Deci asta e o porcărie.
Asta e chiar bună.
Aproape orice în această regiune
de aici este mai bine corect.
Cel puțin câștig ceva.
Nu pot să mă ridic prea mult în
raport cu dimensiunea mea de intrare.
Deci pătratic-- nu știu--
este ceva de genul acesta,
iar n log n este
ceva de genul acesta.
n log n, după
mult timp, chiar
începe să arate liniar
cu o constantă înmulțită
în fața sa.
Bine, deci lucrurile astea
bune, chestia aia rele...
OK?
Asta
încearcă să transmită.
Bine, deci cum
măsurăm aceste lucruri
dacă nu știu care sunt
operațiunile mele fundamentale pe care
computerul meu le poate folosi?
Așa că trebuie să definim un
fel de model de calcul
pentru ceea ce computerul nostru are
voie să facă în timp constant,
într-o perioadă fixă ​​de timp.
În general, ceea ce folosim
în această clasă este o mașină
numită cuvânt RAM, pe care o folosim
pentru concizia sa teoretică.
Word RAM este un fel
de termen încărcat.
Ce înseamnă aceste lucruri?
Stie cineva
ce inseamna RAM?
STUDENT: [INAUDIBIL]
JASON KU: Memorie cu acces aleatoriu --
înseamnă că pot
accesa aleatoriu diferite locuri
din memorie în timp constant.
Aceasta este presupunerea
memoriei cu acces aleatoriu.
Practic,
modelul nostru de computer este
ai memorie,
care este în esență
doar un șir de biți.
Sunt doar o grămadă
de 1 și 0.
Și avem un computer, ca
un procesor, care este foarte mic.
Practic poate deține o
cantitate mică de informații,
dar poate schimba
acele informații.
Poate funcționa pe baza
acestor informații
și are, de asemenea, instrucțiuni
pentru a accesa aleatoriu
diferite locuri din memorie, a
le aduce în procesor, a
acționa în funcție de ea și a le citi înapoi.
Are sens?
Dar, în general,
nu avem o adresă
pentru fiecare bit din memorie,
fiecare 0 și 1 din memorie.
Știe cineva cum se
adresează computerele moderne?
Da?
STUDENT: [INAUDIBIL]
JASON KU: OK, așa că
vom ajunge acolo.
De fapt, ceea ce se adresează unui computer modern

sunt octeți, colecții de 8 biți.
Deci există o adresă pe care o
am pentru fiecare 8 biți
în memorie --
8 biți consecutivi în memorie.
Și deci, dacă vreau să introduc
ceva în procesor, îi
dau o adresă.  Va
dura o bucată și
o va aduce în procesor, o va opera
și o va scuipa înapoi.
Cât de mare este bucata aceea?
Aceasta se referă la răspunsul pe care l-ați
întrebat, care--
sau spuneți, care este o
secvență de un număr fix
de biți, pe care noi îl numim un cuvânt.
Un cuvânt este cât de mare
o bucată pe care o
poate prelua CPU-ul din memorie
la un moment dat și să opereze.
În computerele dvs., cât de
mare este dimensiunea cuvântului?
64 de biți - cu atât
pot opera la un moment dat.
Când eram copil,
când aveam vârsta ta,
dimensiunea cuvântului meu era de 32 de biți.
Și asta a fost de fapt o
problemă pentru computerul meu,
pentru că pentru a
putea citi
adresa în
memorie, trebuie să
pot stoca acea adresă
în CPU, într-un cuvânt.
Dar dacă am 32 de biți,
câte adrese diferite pot
adresa?
Am o limitare a
adreselor de memorie pe care le pot adresa,
nu?
Deci câte
adrese de memorie diferite
pot adresa cu 32 de biți?
2 la 32, nu?
Are sens.  Ei
bine, dacă faci acest calcul
, cât de mare
pot avea să accesez un hard disk?
Este aproximativ 4 gigaocteți.
Așadar, pe vremea mea, toate
hard disk-urile
erau limitate la a fi
partiționate -- chiar dacă
aveai un hard disk mai mare de 4
gigaocteți,
trebuia să-l parționez în
aceste bucăți de 4 gigaocteți, pe care
computerul le putea
citi apoi.
Asta a fost foarte
limitativ, de fapt.
Asta este o restricție.
Cu 64 de biți, care este
limitarea mea de memorie
pe care o pot adresa -
octet adresabil?  Se
dovedește a fi ceva
de genul 20 de exaocteți --
pentru a pune acest lucru în
context, toate datele pe care
Google le stochează pe
serverele lor, pe toate
unitățile din întreaga lume --
este de aproximativ 10.
Deci nu vom scăpa
prea mult de această limitare.  curând.
Deci, ce avem,
avem un procesor.
Se poate adresa memoriei.
Care sunt operațiunile pe care le
pot face în acest procesor?  În
general, am
operații binare.
Pot să compar cu
cuvintele din memorie
și pot fie să fac aritmetică cu numere întregi
, operații logice,
operații pe biți --
dar nu
le vom folosi atât de mult în această clasă.
Și pot scrie și scrie
dintr-o adresă în memorie,
un cuvânt în timp constant.
Acestea sunt
operațiunile pe care le am la
dispoziție pe majoritatea procesoarelor.
Unele procesoare vă oferă
puțin mai multă putere,
dar, în general, aceasta este ceea ce
analizăm algoritmii
.
BINE?
Dar veți observa
că procesorul meu este
construit doar pentru a funcționa pe o
cantitate constantă de informații simultan -- în
general, două cuvinte în memorie.
O operație produce o a
treia și o scuip.
Este nevoie de o
cantitate constantă de timp
pentru a funcționa pe o
cantitate constantă de memorie.
Dacă vreau să operez pe o
cantitate liniară de memorie--
n lucruri-- cât timp va dura
?
Dacă vreau doar să citesc
totul din acel lucru,

îmi va lua timp liniar,
pentru că trebuie să citesc
fiecare parte din acel lucru.
OK, deci, în general,
ceea ce vom
face în prima jumătate
a acestei clase --
oricum primele opt prelegeri --
este să vorbim despre structurile de date.
Și va fi
îngrijorat de faptul că nu funcționează
pe o cantitate constantă de date la
un moment dat, așa cum face CPU-ul nostru,
dar, în schimb, ceea ce va face
este să opereze pe -- să
stocheze o cantitate mare de date
și să suporte diferite operațiuni
pe acele date.  .
Deci, dacă aș avea o înregistrare
pe care vreau să o păstrez
pentru a stoca acele zile de naștere pe
care le aveam înainte,
aș putea folosi ceva
de genul unei matrice statice, cu care
poate nu sunteți
familiarizați, dacă
ați lucrat în Python este
singurul vostru limbaj de programare  .
Python are o mulțime de
structuri de date cu adevărat interesante,
cum ar fi o listă și un
set și un dicționar
și toate aceste tipuri
de lucruri care de
fapt nu sunt în acest model.
De fapt, există mult cod
între tine și computer
și nu este întotdeauna
clar cât timp
durează acea interfață.
Și așadar, ceea ce vom
face începând de joi
este să vorbim despre modalități de
stocare a unei cantități neconstante
de informații pentru a
face operațiunile
pe acele informații mai rapide.
Așa că, chiar înainte de a pleca,
vreau doar să vă ofer
o privire de ansamblu rapidă asupra clasei.
Pentru a rezolva o
clasă de algoritmi - o
problemă de algoritm din această
clasă, avem în esență
două strategii diferite.  Ne
putem reduce fie la utilizarea
soluției la o problemă pe care
știm să o rezolvăm,
fie ne putem proiecta
propriul algoritm,
care va
fi recursiv în natură.
Fie vom pune
lucruri în structura de date
și vom rezolva o problemă de sortare,
fie vom căuta într-un grafic.
Și apoi, pentru a proiecta un
algoritm recursiv,
avem diverse
paradigme de proiectare.
Toate acestea sunt în notele tale,
dar aceasta este în esență
structura clasei.
Vom petrece testul 1,
primele opt prelegeri despre
structurile și sortarea datelor.  Al
doilea test va fi pe cele mai scurte
căi, algoritmi și grafice,
iar apoi ultimul va
fi despre programarea dinamică.
OK, acesta este sfârșitul
primei prelegeri.
Mulțumesc pentru vizită.