[SCRÂȘIT] [FOSȘIT] [CLIC] JASON KU: Bun venit, tuturor, la penultima prelegere din 6.006. În această prelegere, am acoperit în mare parte tot materialul testabil pe care îl vom avea la finală sau la testul 3. Astăzi, ceea ce vorbim este să punem în context tot materialul pe care l-am învățat de-a lungul trimestrului la un nivel înalt și să vorbim despre unde putem merge de aici în ceea ce privește alte clase de teorie și alte clase din catedra care au legătură cu acest material. Acum, majoritatea lucrurilor din departament sunt într-un fel legate de acest material. Și de aceea există un curs de bază. Dar vom încerca să vorbim despre asta de la un nivel înalt și să vorbim despre cum se leagă unele lucruri viitoare care v- ar putea interesa. Bine, așa că am început trimestrul, în prelegerea unu, vorbind despre 6.006, și aveam patru obiective principale pe care le aveam pentru cursul nostru - într-adevăr trei obiective principale Își amintește cineva care au fost acele obiective? Deci ai ajuns primul la ultimul. Prima a fost de a rezolva probleme de calcul grele, pentru a putea rezolva probleme. Deci, aceasta este un fel ca partea „să facem un algoritm” a cursului. 1, rezolva probleme de calcul dificile. Bănuiesc că „greu” aici ar trebui să fie între ghilimele pentru că am văzut în ultima prelegere ce înseamnă greu în sens tehnic. Greu ar putea însemna că nu există un algoritm eficient pe care să știm cum să rezolvăm o problemă. Asta ne avansăm puțin pe noi înșine. Problemele de calcul cu algoritmi sunt într-adevăr partea cheie a acestui obiectiv. Este cam același obiectiv pe care îl aveți într-o clasă ca 6.0001 sau 6.009. Încercați să convingeți un computer că ați rezolvat o problemă cu un set finit de intrări. Dar, de fapt, această clasă este despre alte două lucruri, care se referă mai mult la comunicarea cu oamenii decât la computere. Algoritmul tău poate fi corect sau eficient, dar trebuie să poți comunica asta oamenilor. Și asta sunt celelalte două obiective. Deci, a doua este argumentarea corectitudinii. Practic, lucrul pe care îl fac intrărilor mele mă va conduce întotdeauna la o ieșire corectă. Indiferent de intrare pe care i-o dau, orice intrare validă - ar putea exista un spațiu infinit de intrări posibile, iar în această clasă, acesta este cazul, pentru că dorim ca dimensiunea intrării noastre să crească arbitrar mare - trebuie să fim capabili să argumentați corectitudinea că îmi va returna lucrul corect, indiferent care sunt intrările mele. Și pentru a face asta, în esență, asta înseamnă 6.042. Toată această clasă a fost aplicată practic 6.042. Ți-am dat câteva proceduri și trebuie să dovedești lucruri despre aceste proceduri. Sau de cele mai multe ori, ți-am dovedit-o și apoi le-ai folosit ca cutii negre. Dar despre asta este o mare parte din această clasă. Iar a treia este eficiența - argumentați că este „bun”, din lipsă de un lucru mai bun. Aceasta este eficiența. Ce înseamnă „bun”? Ei bine, asta a fost greu de știut la începutul orei noastre. Și așa am creat acest model de calcul, un cadru, prin care am putea determina cât de buni sau răi sunt algoritmii noștri spunând-- prin definirea unui model de calcul, spunând ce lucruri putem face în timp constant și apoi construind doar din asta. Deci acesta este practic modelul nostru plus niște asimptotice sau ceva de genul ăsta. A rămas fără spațiu. Ce? PUBLIC: Este vorba de scalabilitate. JASON KU: Da, este vorba despre scalabilitate. Un model de calcul ne spune cât timp putem petrece, dar este comparat cu dimensiunea noastră de intrare. Este întotdeauna vorba despre cum funcționează algoritmul nostru în raport cu rata creșterii dimensiunii problemei noastre? Și asta este ceea ce înțelegem prin „bun”. Și în această clasă, nu avem tendința să vorbim despre probleme de dimensiune constantă . Este vorba despre modul în care algoritmii pot scala, deoarece aveți intrări arbitrar de mari. De aceea avem nevoie de recursivitate și inducție pentru a putea demonstra lucruri despre algoritmii noștri, pentru că sunt pentru n arbitrar. Și de aceea avem nevoie de această dimensiune relativă la intrare, factorul de creștere al performanței algoritmului nostru, în raport cu intrarea. OK, și apoi ultimul lucru este, pentru mine, unul dintre cele mai importante lucruri, este comunicarea acestor lucruri unui alt om. Deci comunicarea este cheia aici. Dacă poți scrie întotdeauna un cod bun, este întotdeauna corect, bine pentru tine. Nu pot face asta tot timpul. Dar asta ar putea însemna că poți fi foarte... un programator independent, competent . Dar vei fi limitat în ceea ce poți face dacă te poți baza doar pe tine. Multe lucruri despre informatică sunt colaborarea cu alții pentru a rezolva probleme de calcul. Și când lucrezi cu alții pentru a rezolva probleme de calcul, trebuie să fii capabil să comunici cu ei și trebuie să le poți comunica atât ceea ce faci, cât și de ce faci asta. - că faci lucrul corect și că este eficient. Și asta este o parte importantă despre ceea ce este acest curs. La sfârșitul zilei, în chestionarul tău, dacă notezi scriptul Python pentru un algoritm corect, dar nu știm ce face, dar este corect, nu o să-ți oferim puncte complete, pentru că nu îndeplinești condițiile acestei clase. Este vorba într-adevăr de comunicare aici. OK, deci doar pentru a revizui, deoarece nu am discutat cum se potrivește cea mai recentă prelegere în seturile dvs. de probleme . Nu am avut seturi de probleme care să acopere complexitatea, așa că cum se potrivește asta? Ei bine, argumentați că modurile în care ne rezolvăm problemele sunt bune. Ceea ce am demonstrat în ultima prelegere a fost că majoritatea problemelor nu pot fi rezolvate bine. Ele nu pot fi rezolvate în timp polinomial în funcție de dimensiunea intrării dvs. Cu toate acestea, majoritatea problemelor la care ne gândim, într-un fel, vă pot demonstra că este o soluție da. Vă pot arăta o cale simplă în acest grafic care are o anumită lungime. Sau vă pot arăta un subset care însumează o anumită valoare într-o anumită problemă. Vă pot da un certificat prin care vă pot dovedi într-un timp rezonabil că, da, vă pot dovedi că acesta este... răspunsul la acest lucru este corect. Și despre asta am vorbit în ultima prelegere. Deci nu sunt întotdeauna algoritmi „buni” pentru rezolvarea problemelor, dar multe probleme la care ne gândim pot fi verificate fie în timp polinomial - acesta este conceptul de a avea un certificat pe care vi l-aș putea da cu dimensiunea polinomului care ar putea fi verificat în timp polinomial - - într-un sens, asta e un mod... verifica... verificat în timp polinomial. Acest lucru duce la clasa noastră de probleme de decizie, NP. Sau poate fi rezolvată prin forță brută în timp exponențial. Majoritatea lucrurilor despre care am vorbit în această clasă se încadrează într-una dintre aceste două categorii. Putem doar forța brută asupra spațiului combinatoriu al posibilelor ieșiri și să verificăm dacă sunt corecte. Sau pot să vă dau un certificat prin care să vă spun, uite, pot rezolva -- de fapt, orice este de această formă poate fi verificat în această formă, pentru că există doar un număr polinom de lucruri de verificat -- sau, îmi pare rău, un posibil exponențial numărul de certificate de lungime polinom de verificat. Dar, practic, aceasta înseamnă că problemele la care ne gândim în mare parte se încadrează în aceste două categorii. Și deci există de obicei algoritmi pentru a rezolva problemele care ne pasă, chiar dacă majoritatea problemelor aleatorii în ceea ce privește șirurile de biți pe care le-am analizat în ultima prelegere demonstrează de fapt că majoritatea problemelor aleatoare nu sunt rezolvabile. Într-un fel, problemele la care ne gândim nu sunt întâmplătoare. Au cam această structură pe care pot fi verificate destul de repede. OK, deci la asta ne referim când vorbim despre complexitate. În scopul finalului, veți putea vedea la examenul final problemele de practică pe care vi le vom oferi, cea mai mare parte a ceea ce acoperim în ceea ce privește materialul final care va testa cursul 19 materialul va fi fie în ceea ce privește definițiile. Înțelegeți care este clasa de probleme de decizie NP? EXP este? Știți cum se leagă acestea între ele? EXP este cu siguranță un superset de NP aici. NP se cuibărește aici. Ar putea fi egali... probabil că nu. Acestea sunt tipurile de lucruri pe care le-am aborda. Cunoașterea unei direcționalități a unei reduceri. Dacă aveți o problemă A și o problemă B și știu că aceasta este dificilă într-o oarecare măsură -- Mi s-a întâmplat să știu deja că este foarte greu, ca NP-hard sau ceva de genul ăsta. Dacă aceasta este o problemă despre care sunt interesat să cunosc complexitatea și pot demonstra că o pot rezolva dacă aș avea o cutie neagră pentru a rezolva B, orice cutie neagră pentru a rezolva B și aș putea face această reducere în timp polinomial, iar dacă acest lucru este greu, înseamnă că nu poate fi - asta înseamnă că dacă este greu, atunci mai bine nu pot rezolva asta în timp polinomial, pentru că atunci aș putea să rezolv asta în polinom. timp. Deci, acesta este practic tipul de argument de obicei într-o întrebare adevărat/fals pe care l-am putea avea la examenul final pentru ca tu să înțelegi definițiile de bază de nivel înalt implicate în ceea ce s-a vorbit în prelegerea 19. Duritate -- cea mai dificilă problemele acestor clase-- și completitudine-- îmi pare rău, ceva mai greu decât lucrurile din aceste clase. În timp ce completitudinea sunt cele care sunt în acest set, dar cel puțin la fel de greu ca orice în acele clase. Deci, doar pentru a vă oferi o scurtă prezentare generală a singurului material care nu a fost testat, dar care ar putea fi testat în final. Deci, atunci când nu avem un algoritm bun, putem demonstra că probabil nu are un algoritm bun. Și aceasta este o problemă pe care o vei putea rezolva în cursurile viitoare, dacă vei continua pe această cale. OK, deci care este conținutul real despre care am vorbit? Aceasta este o prezentare generală la un nivel foarte înalt despre motivul pentru care luăm acest curs, de ce luați acest curs. Dar care este conținutul pe care l-am acoperit de fapt? Îmi place să o împart în trei unități și, într-un fel, două subunități. Deci, materialul testului 1 și materialul testului 2 au fost despre a vă arăta niște cutii negre frumoase. Practic, dacă voi avea intrări de dimensiuni neconstante, îmi va fi util să pot găsi lucruri printre acele elemente. Deci despre asta se referă testul 1 - structuri de date pentru găsirea lucrurilor în baza de date de dimensiuni neconstante. Sigur. Și când stocam aceste lucruri, dorim să acceptăm poate două tipuri diferite de interogări -- cele care erau intrinseci articolelor, care erau elementele și cele bazate pe ce -- a fost plasată o comandă extrinsecă pentru aceste articole. Și acesta a fost un mod în care ne-am eșuat, cum ar trebui să abordez această problemă? Vreau să pot suporta interogări și să mențin o ordine extrinsecă asupra acestor lucruri. S- ar putea să vreau o secvență. Aceasta este o ordine extrinsecă a secvenței. Sau vreau să pot căuta în sus, este chestia asta în setul meu, printr-o cheie pe care o identificăm, cu o cheie unică. Deci, acestea sunt niște interogări intrinseci și, adesea, ordine. Un tabel hash nu menține nicio ordine pe cheile mele. Dar acceptă interogări intrinseci - acest lucru este în setul meu sau nu? Dar v-am arătat și alte structuri de date ale setului care acceptă o ordine intrinsecă care îmi permite să văd care este următorul mai mare și următorul anterior - următorul mai mare și următorul articol mai mic din setul meu. Deci, iată un rezumat al acelor structuri de date pe care le-am avut. Nu am de gând să intru în modul în care să folosesc aceste lucruri sau cum să aleg dintre ele aici. Despre asta a fost vorba despre testul 1 . Dar, în principiu, ideea aici este că, dacă avem o secvență, de cele mai multe ori când programați, a fi capabil să apăsați și să popiți la sfârșitul unei liste este destul de bun. De aceea, Python, cea mai fundamentală structură de date pe care o aveți, este o listă, pentru că este un lucru super util. Vreau doar să stochez o grămadă de lucruri, să am acces aleatoriu la, să zicem, al 10-lea element al meu, dar nu trebuie neapărat să actualizez dinamic ordinea acestor lucruri în mod dinamic. Nu trebuie neapărat să introduc ceva în mijlocul listei. Dar de cele mai multe ori, ceea ce pot face este să-l pun la sfârșitul listei și poate să-l schimb la locul său dacă este nevoie. Deci, de aceea o listă este super utilă. Un arbore AVL de secvență, util, dar nu la fel de omniprezent ca o listă legată -- Adică, ca o matrice dinamică, îmi pare rău. Am spus listă legată, mă refeream la lista Python, care este o matrice dinamică. Deci, matricea dinamică tindea să fie, în practica dvs. de codificare, cea mai comună structură de date secvențe de aici. Cu toate acestea, putem deveni destul de buni pentru această inserție în operația de mijloc cu secvența AVL. Bine, atunci, în ceea ce privește structura de date setată, clasific aceste lucruri în câteva categorii diferite aici în ceea ce privește operațiunile pe care le putem sprijini în aceste lucruri. Toate acestea sunt operațiuni intrinseci - găsirea lucrurilor, inserarea, ștergerea lucrurilor. Consider că primele trei sunt operații de dicționar. Vreau doar să mă uit dacă există ceva acolo. În timp ce ultimele două sunt operațiuni de păstrare a ordinii, unde contează în ce ordine sunt stocate aceste lucruri. Și așa cum puteți vedea din complexitatea asimptotică a diferitelor operațiuni de aici, tabelul hash este de fapt foarte bun dacă doriți ca dicționar opera-- dacă doriți doar să susțineți operațiunile dicționarului. Dar în cazurile în care trebuie să mențineți ordinea în mod dinamic, un set AVL este calea de urmat. Dar dacă nu aveți nevoie de el dinamic, dar aveți totuși nevoie de acele operațiuni de comandă, o matrice sortată este suficient de bună dacă nu trebuie să schimbați ceea ce sunt. Deci, aceasta este o privire de ansamblu rapidă a materialului structurilor de date de tip test 1 . Dar apoi am folosit majoritatea acestor structuri de date pentru a obține algoritmi de sortare mai rapidi în diferite contexte. Practic, totul din această listă a implicat realizarea unei structuri de date și exploatarea acelei structuri de date pentru a obține un timp de rulare mai bun, toate cu excepția sortării de îmbinare, într-adevăr. Primele două le-am prezentat în termeni de coadă de prioritate, indiferent dacă am folosit o matrice sortată sau o matrice. Am reprezentat-o ​​la sfârșitul prelegerii opt pentru a obține timpul de rulare n pătrat. Am generalizat asta până la n log n folosind un heap. A fost o optimizare frumoasă. Dar am obținut și structuri de date interesante folosind un-- Adică, algoritmi de sortare interesanți folosind un arbore AVL datorită puterii de a menține o ordine dinamică în timp. Dar apoi exploatarea unei matrice cu acces direct pentru a putea sorta în timp liniar pentru intervale de numere mici - mărginite în termeni de intrare, mărginite polinomial în termeni de intrare. Deci, folosim acea matrice de axe directe pentru a obține sortarea de numărare. Și apoi am cam amplificat acest efect sortând pe o grămadă de cifre de mai multe ori pentru a obține, practic, o explozie polinomială în ceea ce privește numerele pe care le-am putea sorta în timp liniar. Deci, aceasta este o privire de ansamblu asupra conținutului testului 1. În testul 2, am fost cam de genul, OK, acum știți cum să găsiți lucruri într-un set de doar o listă plată de lucruri, le puteți pune într-o structură de date. Dar într-un anumit sens, un grafic este un tip special de structură de date care leagă diferitele lucruri din intrarea dvs. Deci, dacă aveți o grămadă de vârfuri, există o relație acum între acele vârfuri care sunt marginile voastre. Și acesta este un cadru foarte util în a vorbi despre sisteme discrete, deoarece vă puteți gândi la un vârf ca la o stare a sistemului dvs. și apoi conectați aceste tranziții ca un grafic. Acesta este motivul pentru care... Adică, graficele sunt minunate, dar sunt minunate pentru că pot fi folosite pentru a modela atât de multe lucruri diferite în lumea noastră. Nu este vorba doar despre rețelele de drumuri. Poate fi vorba și despre jocul tău preferat pe rând, cum ar fi Tilt. OK, așa că am vorbit despre o mulțime de tipuri diferite de probleme pe care le puteți rezolva, diverși algoritmi, cu accent pe o grămadă de moduri diferite de a rezolva cele mai scurte căi dintr-o singură sursă. Și din nou, la fel ca algoritmii de sortare și la fel ca structurile de date, am prezentat mai multe dintre ele, deoarece am avut acest compromis de generalitate a graficului căruia i se aplică în contrast cu timpul de rulare. Deci, cred că, în special, linia de sus acolo este, într-un anumit sens, cea mai restrictivă. Nu avem niciun ciclu în graficul nostru. Acesta este un tip foarte special de grafic și putem obține timp liniar. Dar apoi, chiar dacă avem cicluri în graficul nostru, ne putem descurca mai bine dacă avem o limită a ponderilor în lucrul nostru, indiferent dacă acestea sunt -- există o conversie ușoară la un algoritm de timp liniar printr-un proces neponderat, sau dacă acestea lucrurile nu sunt negative, deci nu pot exista cicluri negative de greutate și nu trebuie să ne confruntăm cu asta. OK, deci acesta este materialul testului 2. Și apoi materialul testului 3 a fost un fel de aplicare a acestui material grafic într-un cadru recursiv. Care a fost cadrul nostru recursiv? Toată lumea o spune cu mine. PUBLIC: Programare dinamică. JASON KU: Programare dinamică, iar cadrul a fost SRT BOT, nu? Lipsește o scrisoare, dar SORT BOT, nu? De fapt, vă puteți gândi la materialul testului 3 ca la o aplicație a materialului grafic. Ce facem în SORT BOT? Definim un set de subprobleme. Acestea sunt un set de vârfuri dintr-un grafic. Ce face relația? Se spune, care sunt relațiile dintre subprobleme, definind în esență muchiile unui grafic? Și apoi această ordine topologică și cazurile de bază, toate aceste lucruri doar spun, care este problema pe care vreau să o rezolv pe acest grafic? Și cum calculez asta pentru lucruri care nu au margini de ieșire? Trebuie să încep să scriu din nou pe tablă. Acestea sunt grafice. A fost o sortare și aici. Aceasta este practic o aplicație. OK, graficele a fost practic o relație cu aceste lucruri non-constante. Așadar, acestea au fost un fel de cutii negre utile pe care le puteți împacheta și introduceți în unele intrări, scoateți câteva ieșiri și ești de aur. În timp ce testul 3 a fost foarte diferit, materialul din testul 3 este foarte diferit. Programarea dinamică, deși era, într-un anumit sens, legată de acest material grafic -- construiesc un grafic -- trebuie să construiesc acel grafic. Există un proces creativ în încercarea de a construi acel grafic. Nu vă dau un set de vârfuri. De obicei, ceea ce vă ofer este un set de... o secvență sau ceva de genul ăsta. Și trebuie să construiți vârfuri, subprobleme, care vor putea fi legate într-un mod recursiv, astfel încât să puteți rezolva problema. Acesta este un lucru mult mai dificil decât aceste alte lucruri, cred, pentru că este mult mai multă creativitate în asta. În același mod în care doar aplicarea - reducerea la algoritmii grafici pe care îi avem este destul de ușoară. Dar, de fapt, să faci niște transformări ale graficului pentru a schimba forma graficului, astfel încât să poți aplica acești algoritmi, este un lucru mai greu de făcut. Dificultatea cu aceste două seturi de materiale este foarte asemănătoare. A afla care ar trebui să fie graficul, a afla care ar trebui să fie subproblemele și cum se relaționează, este de fapt întreaga parte a— întreaga dificultate în rezolvarea problemelor recursiv. Și ți-am dat doar un gust de a rezolva probleme recursiv. În clasele viitoare, cum ar fi 6.046, care este continuarea acestuia în programa de licență, totul este despre introducerea în algoritmi. Următorul este despre proiectarea și analiza algoritmilor. Este ceva mai dificil, deoarece v-am lăsat în cea mai mare parte să utilizați lucrurile pe care vi le-am oferit sau să vă creați proprii algoritmi bazați pe acest cadru foarte frumos asemănător cărții de bucate la care puteți conecta un algoritm recursiv. Acum, de fapt, acea carte de bucate este super drăguță pentru orice mod de a privi o problemă recursiv, dar în timp ce în programarea dinamică, ipoteza inductivă de a vă combina subproblemele este aproape trivială, în alte tipuri de algoritmi recursivi, nu este neapărat cazul. Mai ales atunci când, în loc să te uiți la toate opțiunile posibile, de exemplu, într-un algoritm lacom în care te uiți doar la una dintre alegeri, cel mai bun lucru local și recurgi înainte, nu faci toată munca. Nu ești forțat la nivel local. Alegeți local un lucru optim la nivel local și sperând că acesta vă va conduce la un lucru bun. Aceasta este o paradigmă algoritmică mult mai greu de utilizat. Și așa seamănă mai mult cu materialul despre care veți vorbi în 6.046. Deci, acesta este 006, o prezentare generală foarte rapidă a conținutului acestei clase. Și ne place foarte mult structura modului în care este structurată această clasă, deoarece vă oferă o idee fundamentală despre lucrurile pe care oamenii le folosesc pentru a stoca informații pe un computer și o idee despre cum rezolvați problemele din punct de vedere computațional și cum să argumentați că sunt corecte. si eficient. Despre asta este problema... acest curs. Și dacă simți că îți plac astfel de lucruri, acolo mergi pentru a lua 6.046. Și 6.046 a fost de fapt prima clasă de algoritmi pe care am luat-o vreodată aici la MIT, de fapt, ca student absolvent. Asta a fost greu pentru mine. De fapt, este greu să te uiți la aceste probleme, aceste tipuri și să gândești într-un mod computațional, mai ales că nu ai luat această clasă, 6.006. Așa că sperăm că sunteți cu toții într-o poziție mai bună decât eram eu când am luat-o. Există două moduri în care îmi place să mă gândesc la conținutul din 6.046. Unul este un fel de extensie a lui 006. Este continuarea naturală a lucrurilor pe care le facem în această clasă. Încă se vorbește despre structurile de date. Aceasta nu este partea centrală a lui 046, dar se referă la structurile de date pentru mai complicate -- care au analize mai complicate implicate în ele. Este vorba într-adevăr despre -- de obicei în 046, a afirma ce face algoritmul nu este atât de greu. Practic, a vă oferi algoritmul, numărul unu aici, nu este atât de dificil, să spuneți ce se întâmplă în algoritm. Dar numărul doi și numărul trei de aici, argumentând că acel lucru este corect și argumentând că lucrul este eficient, aici intervine complexitatea în 046. Partea de analiză este destul de mai complicată în 046 decât în ​​006. Deci rezolvă o problemă. problema numită union-găsește și da o mult-- am vorbit puțin despre amortizare. Acest lucru merge într-un mod mult mai bun, un mod mult mai formal de a demonstra că lucrurile se desfășoară în timp amortizat. Deci, aceasta este practic amortizare prin ceea ce numim o analiză potențială. Practic, facem acea noțiune despre care am vorbit când vorbeam despre matrice dinamice, nu facem acest lucru scump prea des. Practic, ceea ce facem este să ținem evidența costului tuturor secvenței de operațiuni și să dovedim că costul mediu este mic. Cam asta face această analiză potențială. Este un proces puțin mai formal pentru a face acest argument un pic mai formal. Dreapta. BINE. Deci, din partea graficului, aceasta este un fel de extensie a materialului de tip test 1. Aceasta este, ce este această structură de date de găsire a uniunii? Practic, este o chestie de tip set, în care pot face un set dintr- un singur element, pot lua două seturi, le pot îmbina, le fac unirea lor și apoi i se oferă un obiect, spun eu, care set sunt eu o parte din, în esență, prin alegerea unui lider într- un set și spunând, returnați-mi un indicator la acela. Și astfel, acest lucru poate fi util în menținerea dinamică, să zicem, a componentelor conectate într-un grafic care se schimbă dinamic care susține interogarea, sunt eu în aceeași componentă cu celălalt tip? Acesta ar putea fi un lucru foarte util de știut despre un grafic pe măsură ce se schimbă. Deci aceasta este o aplicație a acestei probleme. Și obțin performanță aproape constantă pentru multe dintre aceste interogări. Nu este chiar, dar destul de aproape. OK, din partea graficelor, ei rezolvă o serie de probleme foarte utile pe grafice. Arborele de întindere minimă - așa că încerc să găsesc un arbore care să conecteze toate nodurile dintr-o componentă conectată a graficului meu. Și încerc să găsesc... într-un grafic ponderat, încerc să găsesc arborele care are greutatea totală minimă. Deci, aceasta este o problemă - o problemă fundamentală în algoritmii cu grafic ponderat. Au rezolvat asta printr-un algoritm lacom. Și rețeaua curge și cred că se reduce. Deci asta este... ce este asta? Asta înseamnă că mi se oferă un grafic ponderat. Practic, fiecare dintre greutăți corespunde unei capacități. Aș putea împinge apa de-a lungul acestei margini. Și mi se poate da un vârf sursă și un vârf de chiuvetă. Și vreau să spun, vreau să împing apă prin vârful sursei de-a lungul marginilor cu diferitele lor capacități. Și voi primi o cantitate de apă la celălalt capăt în sursă. Deci întrebarea este, care este cea mai mare cantitate de apă pe care o pot împinge prin asta? Ei bine, aș putea construi acea rețea de conducte cu diferite lucruri și să fac asta experimental. Am doar o grămadă de... poate... Sunt inginer mecanic, așa că poate că are sens pentru mine. Dar vrei să poți să te uiți la acele numere și să-mi poți spune câtă apă pot împinge. Despre asta vorbește fluxul maxim într-o rețea. Și vă oferim câțiva algoritmi de timp polinomial din această clasă, practic algoritmi incrementali care, un fel ca Dijkstra, sau un fel ca Bellman-Ford, vor actualiza progresiv estimările la -- unui flux maxim și le vor îmbunătăți în timp. Apoi, în practic, paradigmele de proiectare, te-ai implicat mai mult în crearea propriilor algoritmi de împărțire și cucerire , algoritmi de programare dinamică , algoritmi lacomi. Practic, ei merg mult mai în profunzime în ceea ce privește modul de proiectare a acestor algoritmi și aceste paradigme decât facem noi în această clasă. Și apoi ultimul lucru este... am atins doar complexitatea. Și într-un fel, 046 va atinge doar complexitatea. Este un domeniu foarte mare. Dar vă va oferi instrumentele pentru a putea demonstra că ceva este NP-greu, în timp ce noi doar spunem că, oh, există acest lucru numit o reducere. Nu ți-am dat probleme în care să fii nevoit să reduci o problemă la alta. Și vei face mult mai mult din asta aici. Deci, reduceri. Deci, într-un sens mare, 046 este într- adevăr doar o extensie naturală a materialului 006, plus câteva chestii suplimentare, la care voi ajunge într-o secundă. Da, întrebare? PUBLIC: Doriți să adăugați randomizare pentru paradigmele de timp? JASON KU: Voi vorbi despre asta într-un mod separat... Voi ajunge la întrebarea ta în doar o secundă. Îmi place să mă gândesc la el ca pe un subiect separat, pe care îl voi aborda chiar acum. Subiectul separat îmi place să mă gândesc la el ca, în loc să fie extensia naturală a lucrurilor din unitățile 006, ceea ce voi face este să relaxez fie ceea ce înseamnă să ai un algoritm corect, fie să relaxez ceea ce înseamnă la... care este modelul meu de calcul. Deci, 006, aceasta este un fel de extensie a lui 006. Și aceasta este un fel de 6.046, deoarece îmi schimbă definiția a ceea ce înseamnă a fi corect sau eficient. Așa că am făcut deja acest lucru puțin în 006. Practic, unul dintre lucrurile pe care le putem face, care este întrebarea despre care a pus o întrebare un student , a fost despre algoritmi aleatorii, care este o mare parte din 046 de fapt -- analiza randomizată a algoritmilor care nu sunt determiniști. Nu este garantat că vă va oferi aceeași ieșire de fiecare dată sau nu este garantat că va face aceleași calcule pe parcursul algoritmului de fiecare dată. Dar exploatează o anumită randomizare. Și în 006, aceasta este... în cea mai mare parte nu am atins acest lucru, cu excepția unui domeniu. Unde am folosit randomizarea? În hashing, nu? Când am folosit hashing, ce făceam? Am schimbat definiția corect versus eficient. Nu am schimbat cu adevărat definiția, ceea ce am făcut a fost că am spus că e în regulă că uneori algoritmul nostru a fost mai lent decât noi-- decât on-- în așteptări. La asta ne referim acolo. Relaxăm ideea de eficient, dar tot spunem că este bine, pentru că de cele mai multe ori este bine. Deci, există două tipuri de algoritmi randomizați. Au aceste nume ciudate bazate pe regiuni de pariuri ale lumii, să spunem? Sunt... acesta este L-O? Los Vegas? Sunt algoritmi Las, OK, Vegas. Acestea sunt întotdeauna corecte, dar probabil eficiente. Într-un fel, asta este hashingul. Îți voi oferi întotdeauna ceea ce trebuie, indiferent dacă acest lucru este în setul meu sau nu. Dar, uneori, este ineficient. Trebuie să mă uit printr- un lanț de lungime de... care este liniar în dimensiunea lucrurilor pe care le depozitez. Și acest lucru este în contrast cu un algoritm Monte Carlo, care este întotdeauna eficient pentru o anumită definiție a eficientei, dar numai probabil corect. Și vreau să spun, aș putea defini un tabel hash care are în schimb semantică Monte Carlo. Să spunem, de exemplu, spun că voi merge... va fi exact la fel ca o tabelă hash, doar că în loc să stochez toate lucrurile care se ciocnesc într-un loc, le stochez doar pe primele două, să zicem. Ei bine, de fapt, asta va fi întotdeauna eficient. Mă voi uita prin lucruri și voi vedea dacă este acolo. Iar lanțurile pe care le depozitez acolo au doar două lucruri. Va fi întotdeauna eficient. Îmi va oferi mereu timp constant. Dar, uneori, va fi un lucru greșit, pentru că nu stochez totul din acel lanț. Deci, există o oarecare probabilitate ca asta să nu fie corect. Și deci ăsta este un alt fel de... poate vreau ca tabelele mele hash să fie întotdeauna rapide, dar îmi pot permite să greșesc uneori. Nu știu. În practică, acesta este uneori un bun compromis în sistemele reale. Uneori este în regulă să greșim uneori, dacă obținem performanțe bune. OK, dar în general se poate face mai bine dacă permiteți randomizarea. Și prin mai bine vreau să spun, de obicei putem obține limite mai rapide pentru o mulțime de probleme dacă permitem randomizarea și lucrurile nu sunt neapărat întotdeauna corecte sau întotdeauna eficiente. Deci, aceasta este o zonă mare în 046 care necesită mult mai multă analiză folosind aleatoriu și probabilitate. Deci, dacă ai nevoie de niște grunduri despre asta... nu am avut multe din asta în 006, dar dacă treci la 046, acesta va fi un lucru foarte important pe care să îl perfecționezi. Următoarea parte despre 006 este un fel de schimbare a ceea ce înseamnă definiția noastră de corect sau eficient. Adică, ne-am limitat în această clasă la o clasă de probleme în care vorbim doar despre numere întregi. Dar există o mulțime de probleme în această lume, în special în calculul științific, unde vreau să pot afla care este acest număr real. Și nici măcar nu pot stoca un număr real pe computer. Deci ce naiba , Jason? Ce vrei sa spui? Nu pot face asta pe computer. Dar ceea ce pot face este să calculez lucrurile într-un sens numeric - algoritmi numerici. Și în 046, de multe ori punem asta în contextul optimizării continue, continuu fiind cuvântul oportun aici, nu sisteme discrete. Aveți un continuum de soluții posibile, în esență numere reale. Cum facem asta pe un computer care este un sistem discret? Practic, în 046 ceea ce poți face, și în alte clase de metode numerice , ceea ce poți spune este, ei bine, știu că nu- mi poți returna un număr real. Am inteles. Sau poate aveți un model de calcul care permite numerelor întregi să reprezinte alte tipuri de numere reale, cum ar fi radicali sau raționale sau ceva de genul ăsta. Și pot face manipulări asupra acestora. Dar, de fapt, acești algoritmi sunt de obicei despre calculul numerelor reale nu complet, ci cu o anumită precizie mărginită. Și plătesc pentru acea precizie. Cu cât vreau mai multă precizie pe numărul meu, trebuie să plătesc pentru ele. Așadar, aceasta este de bază - le consider o aproximare - o aproximare a numărului real cu o anumită precizie și plătesc pentru precizie în timp. Deci, să presupunem că am vrut să calculez rădăcina pătrată a unui număr. Aș putea avea un algoritm la fel ca algoritmii-- sau cred că divizare, corect, diviziune lungă. Cunoașteți cu toții algoritmul diviziunii lungi. Puneți coeficientul aici cu astea... un AB și obțineți C pe deasupra sau orice altceva. Acesta este un algoritm. Aceasta este o procedură care utilizează în esență numere mici. Vorbesc doar despre cifrele de la zero la nouă aici când fac acel algoritm. Deci, este o procedură care utilizează numai numere întregi mici pentru a calcula precizia arbitrară a unei diviziuni. Deci, acesta este un algoritm și trebuie să plătesc timp pentru a obține mai multe cifre. Așa că acesta este un exemplu de acest tip de... cum trăim în lumea numerelor reale când tot ce avem este un sistem discret. Și apoi ultima categorie despre care aș vrea să vorbesc aici este de fapt algoritmii de aproximare. În timp ce acesta este un fel de algoritm de aproximare, îmi aproximez rezultatele, acesta este un algoritm de aproximare din punctul de vedere al, ei bine, există o mulțime de probleme pe care nu le pot rezolva eficient. Sunt NP-hard. Au probleme EXP sau chiar mai grele. Dar poate că sunt de acord să nu obțin soluția optimă. Deci aceasta este în domeniul problemelor de optimizare. Deci, majoritatea problemelor de programare dinamică pe care vi le-am dat au fost probleme de optimizare. Sunt cele mai scurte probleme. Sunt probleme de optimizare. Practic, ieșirile posibile sunt clasificate într-un fel - distanța unei căi pe care o întoarceți sau ceva de genul acesta. Sunt clasate într-un fel. Există una optimă - cea cu cea mai mică valoare sau ceva de genul ăsta. Ei bine, într-un algoritm de aproximare, ceea ce fac este, OK, înțeleg că este dificil din punct de vedere computațional pentru tine să-mi oferi cea mai lungă cale simplă din acest grafic sau cea mai scurtă cale posibilă pentru vânzătorul meu călător, dar poate că este în regulă. Adică, ingineria mea Spidey-Sense îmi spune că în 10% este bine. Deci, poate, în loc să- mi dau cel mai optim lucru, vă pot oferi un algoritm care să fie garantat la o anumită distanță de lucrul optim? De obicei, căutăm aproximări cu factori constanți care au o constantă scăzută, sau poate chiar trebuie să mergem mai rău dacă astfel de lucruri nu există. OK, deci sunt algoritmi de aproximare. Ne putem apropia de o soluție optimă în timp polinomial? BINE. Și apoi ultimul mod în care am putea schimba lucrurile, în special în clasele viitoare, deși uneori se vorbește despre asta și în 046 , este că am putea schimba modelul de calcul. Practic, am putea schimba ceva despre computerul nostru pentru a fi pus într-o altă paradigmă ciudată de rezolvare a problemelor cu mai multă putere, în esență, sau vă aflați într-o situație în care este mai puțină putere. OK, deci schimbați modelul de calcul. Deci, ceea ce v-am vorbit în ceea ce privește modelul de calcul este cuvântul nostru-RAM-- cuvântul-RAM. Și asta spune în esență că pot face operații aritmetice și că pot căuta lucruri în memoria mea în timp constant. Și dar dacă aloca o anumită sumă, trebuie să plătesc acea sumă și așa ceva. Așa că acesta este modelul cuvânt-RAM. Dar, de fapt, toate computerele tale, îmi este mult mai ușor să-mi dau seama -- să găsesc și să citesc memoria care este pe procesorul meu într-un registru decât pentru mine să merg pe hard disk, întreabă asta -- ei bine, pe vremea mea, obișnuia să fie acest cap mecanic mobil care trebuia să scaneze puțin pe o unitate CD-ROM și să citească de fapt ce era acel lucru. Astfel, putem adăuga complexitate modelului nostru pentru a ține cont mai bine de costurile operațiunilor pe mașina mea. Unul dintre aceste modele se numește modelul cache-- modelul cache. Practic este o ierarhie a memoriei. Am registrele mele la bordul procesorului meu. Am poate un cache L1 care este aproape de procesorul meu. Apoi am un alt set de cache și un alt set de cache, poate în RAM. Și citirea de pe un hard disk, o unitate SSD de un fel, acesta este cel mai lent lucru de accesat. Și pot pune un cost asociat cu fiecare dintre aceste lucruri. Și în loc să trebuiască să... să se spună că toate operațiunile noastre sunt constante, constantele sunt de fapt diferite și trebuie să plătesc pentru acea diferență. Și asta înseamnă extinderea modelului nostru pentru a fi puțin mai realist pentru mașina noastră. Un altul este că avem computere acum care funcționează în fizica clasică, care exploatează lucrurile din fizica clasică. Dar, în realitate, lumea noastră permite tipuri și mai complicate de operații, cum ar fi operațiunile cuantice, în care exploatezi întricarea și suprapunerea diferiților atomi pentru a obține potențial operații pe care le pot acționa pe datele mele, care sunt de fapt mai puternice decât modelele clasice. intr-un anumit sens. Deci, acesta este un motiv uriaș pentru care se lucrează mult în, să zicem, o mulțime de unități de cercetare din industrie pentru a descoperi aceste modele. Pentru că poate dacă poți face un computer cuantic suficient de mare, poți rupe criptarea și alte chestii în timp polinomial. Și asta e ceva de care poate NSA este interesată. Și nu voi intra în asta. Dar stii. Adică, unii oameni... te uiți la inteligența artificială și la lucruri precum discuțiile despre inteligența artificială, creierul meu ar putea face lucruri pe care un computer clasic nu le poate face. Ar putea folosi suprapunerea cuantică într-un fel. Și computerele noastre care sunt în telefonul tău și laptopul tău și lucruri de genul acesta nu exploatează aceste operațiuni, așa că cum am putea vreodată să obținem inteligență, pentru că într-un anumit sens, creierul nostru este mai puternic. Și așadar, o mare parte din ceea ce ar trebui să se uite AI este, care este modelul real de calcul al creierului nostru care ne poate oferi puterea de a avea simțire? OK, deci este un fel de calcul cuantic. De fapt, nu știu prea multe despre asta. Și apoi sunt lucruri de genul, poate am mai mult de un procesor. Adică, majoritatea computerelor -- toate computerele pe care le ai, chiar și cele din telefonul tău, probabil au mai multe nuclee. Într-un fel, aveți o mulțime de procesoare care rulează în paralel. Deci, acesta este ca par-- există un R în paralel? Calcularea paralelă spune, practic, că este ieftin pentru mine să fac un alt computer potențial. Dacă am două computere care rulează cu aceeași problemă, poate pot obține o viteză de două ori mai mare pe... în timpul necesar pentru a-mi rezolva problema. Acum, să presupunem că aveam atunci 100 de procesoare care rulează pe o mașină. Poate pot obține o accelerație de 100 de ori. Și de fapt, în viața reală, accelerarea de 100 de ori face diferența. Este, aștept asta timp de 10 minute? Sau aștept asta 1.000 de minute? Asta e toată ziua. Nu vreau să fac asta. Poate e în săptămâni. nici nu-mi amintesc. Dar calculul paralel, dacă pot obține o viteză de 100 de ori, ar putea fi un câștig uriaș. Dar pentru unele probleme, nu este posibil - dacă am k procesoare, pot obține o accelerare a factorului k? Nu este întotdeauna posibil de făcut. Deci, calculul paralel este o altă paradigmă în care există o mulțime de teorii interesante. Există o mulțime de complicații acolo, pentru că există câteva modele diferite. Puteți avea o configurație multicore, în care aveți o mulțime de computere care accesează aceeași bancă de memorie. Și atunci nu vrei ca toți să citească și să scrie din ele în momente diferite, pentru că nu știi neapărat care este starea lor și primești aceste ciocniri, care sunt ceva la care trebuie să te gândești cu adevărat în asta. lume. Sau aveți situații în care poate am o grămadă de nano-muște sau ceva care se întâmplă în jur, și au creier foarte mic de computer . Dar ei pot vorbi între ei și pot transmite informații unul altuia, dar nu au acces la un depozit central de informații din rețea. Acesta este ceea ce numim un sistem paralel distribuit, în care toate procesoarele pe care le aveți pot interacționa între ele poate local, dar nu au acces la același sistem de memorie. Așa că trebuie să lucreze împreună pentru a afla informații despre sistem. OK, deci aceasta este o scurtă prezentare generală a diferitelor direcții din această clasă, 6.006, și teoria în general, te-ar putea conduce-- într-o gamă uriașă de teorie a ramurilor diferite și diferite probleme pe care le- ai putea aborda cu diferite tipuri de computere. Așa că știu că aceasta este o prelegere la un nivel foarte înalt și poate mai puțin aplicată decât ar dori unii dintre voi. Dar sper că acest lucru vă oferă o bună înțelegere a direcțiilor pe care le puteți urma după această clasă despre care cred că sunt foarte entuziasmați în ceea ce privește modul de rezolvare a problemelor din punct de vedere computațional. Deci, cu asta, aș vrea să închei aici.