[SCRÂȘIT] [FOSȘIT] [DĂ CLIC] JASON KU: Bună, tuturor. Bun venit la ultima prelegere din 6.006. Ultima prelegere, am vorbit despre rezumarea acestei clase și despre cursurile viitoare în departamentul care utilizează acest material. Doar ca un indicator la unele dintre aceste clase, am aici un mic diapozitiv la care nu am ajuns la ultima prelegere, vorbind despre ceea ce vorbeam la sfârșitul ultimei prelegeri despre diferite modele -- diferite clase de specialitate despre diferite aspecte ale materialului 006 -- de exemplu, mai multe elemente grafice, diferite modele de calcul, aleatorie, complexitate. Toate aceste lucruri au propriile lor clase de specialitate în departament, precum și o mulțime de aplicații pentru acest material în subiecte precum biologie, criptografie și, în special, pentru instructorii tăi, domeniul graficii și geometriei. Toți instructorii tăi din acest termen s- au întâmplat să fie geometri și să fie interesați de problemele legate de geometrie. Eu în special, nu am început în informatică. Am început în inginerie mecanică. Și lucrul care a fost pasiunea mea când am venit la MIT a fost origami. Iată câteva piese pe care le-am proiectat-- piese origami, o foaie pătrată de hârtie fără tăiere. Iată un homar și iată un dinozaur protejat prin drepturi de autor dintr-un anumit film al anului în care l-am proiectat. Când eram tânăr, în liceu, am început să-mi proiectez propriile modele origami. Și ceea ce nu mi-am dat seama a fost că procedurile pe care le-am urmat pentru a proiecta aceste modele erau de fapt algoritmi. Și pur și simplu nu aveam limbajul matematic pentru a înțelege exact ce făceam, dar am putut obține o intuiție ca artist origami și am putea proiecta aceste lucruri folosind unele dintre aceste tehnici algoritmice. Abia la licență, ca inginer mecanic, am început să vorbesc cu celălalt instructor al nostru de aici, profesorul Demaine, despre folosirea algoritmilor și a informaticii pentru a proiecta nu doar origami, ceea ce facem amândoi, ci și structuri pliate care pot fi folosit pentru aplicații mecanice cum ar fi zborul spațial, poduri desfășurate în momente în care nu poți - ai nevoie de un pod temporar sau un adăpost sau ceva de genul. Structurile implementabile în care s-ar putea să fie nevoie să faceți structuri pliate - structuri transformabile care pot avea aplicații diferite pentru scopuri diferite - trebuie reconfigurate. Visul este că avem aceste dispozitive puternice în buzunare chiar acum -- telefoane mobile -- care sunt cu adevărat puternice pentru că putem reconfigura biții din ele pentru a face software de toate tipurile, nu? Există un număr exponențial de programe diferite pe care le putem scrie. Și asta face parte din motivul pentru care ești aici, este să scrii următorul cel mai bun. Dreapta? Așa se face un fel de dispozitiv universal la nivel electronic. Dacă am putea face asta din punct de vedere material? Ce se întâmplă dacă aș putea reprograma problema în telefonul meu, astfel încât, nu numai că aș putea reprograma aplicația care este pe telefonul tău, dar în loc să am, să zicem, iPhone 10 sau orice altceva ai și vrei să mergi pe iPhone 11 , în schimb, descărcați o aplicație software care apoi reconfigurează problema în telefonul dvs. - se pliază sau se reconfigurează în iPhone de următoarea generație. Nu trebuie să-l arunci pe cel vechi. În esență, puteți recicla materialul pe care îl aveți pentru a economisi material, a economisi costuri și, eventual, a fi mai bun pentru mediu. Așa că am început să trec în informatică pentru că am descoperit că este o modalitate foarte bună de a modela lumea și de a rezolva unele probleme cu adevărat interesante despre pliere, care mi-au plăcut foarte mult. Noi trei astăzi vom petrece ceva timp vorbind puțin despre cum putem folosi algoritmi -- 6.006 materiale și nu numai -- în propria noastră cercetare. Și vom începe cu profesorul Demaine, apoi cu profesorul Solomon. ERIK DEMAINE: Mulțumesc. Așa că permiteți-mi să trec aici la origami de calcul și algoritmi de pliere geometrică, un fel de umbrelă mai largă pentru lucruri legate de pliere, care este încapsulată în această clasă, 6.849, care se va întâmpla în toamna viitoare. Deci ar trebui să o luați cu toții. 006 ar trebui să fie un fundal rezonabil. Și, în general, suntem interesați de două tipuri de probleme. Unul-- cel mare este designul origami sau, în general, designul pliabil, unde aveți câteva specificații despre ceea ce doriți să construiți. În acest caz am vrut să fac un logo pentru 6.849. Și mi-am imaginat extrudarea textului în a treia dimensiune. Și apoi am vrut un algoritm care să-mi spună cum să pliez acea structură. Și așa că există un algoritm, despre care voi vorbi într-un moment, care vă oferă un model de cute. Și apoi, în prezent, îl pliezi cu mâna. Visul este că în cele din urmă vom avea mașini de pliat care să facă totul pentru noi. Și așa este designul origami, unde treci de la forma țintă înapoi la modelul cutelor. Direcția inversă este un fel de pliabilitate. Dacă ți-am dat o structură ca asta și am vrut să știu, se pliază? Aceasta este problema pe care o numim pliabilitate -- în general, o clasă de probleme. Și, din păcate, majoritatea acestor probleme sunt NP-grele. Jason și cu mine am dovedit că plierea este dificilă pentru un general-- având în vedere un model de cute ca acesta, spunându-ți dacă se pliază în ceva, se dovedește a fi NP-hard. Deci sunt vești proaste. Așa că ne concentrăm mult pe problema designului, pentru că asta tinde să fie de fapt mai ușor. O putem rezolva cu algoritmi ca cel pe care îl vedeți. Cu mult timp în urmă, am demonstrat că poți plia totul. Dacă îți dau o bucată pătrată de hârtie și iei orice poligon pe care vrei să-l faci -- sau poate că hârtia este albă pe o parte, neagră pe cealaltă, vrei să îndoiți un model în două culori , ca o zebră, sau în În general, o suprafață tridimensională, cum ar fi acești tipi, există o modalitate de a o plia dintr-un pătrat suficient de mare de hârtie. Și este de fapt foarte ușor să demonstrezi asta cu un algoritm. Am schița celor două pagini de dovadă pe care le parcurgem în 6.849, dar voi face doar un pic de mână. Dacă luați o bucată de hârtie, cum ar fi notele mele de curs aici, primul lucru pe care îl faceți este să o pliați într-o fâșie foarte lungă și îngustă - mult mai lungă și mai îngustă decât aceasta - irosind cea mai mare parte a materialului. Și apoi îți iei banda și îți dai seama cum să o răsuci într- un mod general, apoi faci un fel de zig-zag înainte și înapoi de-a lungul suprafeței. Așa că este foarte tare prin faptul că poți dovedi cu un algoritm și, într-un timp foarte scurt , cuiva poți de fapt să pliezi totul. Desigur, este o pliere groaznică, pentru că în primul pas aruncăm tot materialul, cu excepția epsilonului. Dar este un punct de plecare. Acesta a fost în anii '90-- sfârșitul anilor '90-- unul dintre primele rezultate în origami computațional. Și în vremurile moderne, căutăm algoritmi mai buni, care să fie mai eficienți, care încearcă să minimizeze factorul de scară de la, de la cât de mare o bucată de hârtie încep până la, cât de mare de model primesc? Și una dintre modalitățile interesante din zilele noastre, care a fost inventată de Tomohiro Tachi și apoi analizată de noi doi -- se numește Origamizer. Este software gratuit. Luați un model 3D și puteți... îl transformă într-un model pe care îl pliați dintr-un pătrat. În acest caz, folosește 22% din suprafață, ceea ce este destul de bun - similar cu acești tipi în ceea ce privește eficiența. Dar un fel de pliere foarte, foarte diferit față de ceea ce ați obține dintr-un design origami mai tradițional , care utilizează algoritmi diferiți, despre care nu voi vorbi. Dar ar trebui să iei cursul. Jason ține o prelegere în clasă, ca să poți învăța de la el. Dar viziunea este că putem lua orice foaie de material care poate ține o cută, cum ar fi această foaie de oțel pe care o pliază Tomohiro. A fost tăiat de un mare tăietor cu laser la MIT. Și acesta este el în acest Centru de Date în urmă cu câțiva ani, pliându- l într-un iepuraș de oțel. Și deci acesta este un mod cu totul nou de a fabrica obiecte 3D. Și puteți realiza obiecte deosebit de interesante care fie se prăbușesc plat pentru transport, fie se transformă, așa cum vorbea Jason. Dar îți dau doar o aromă. Cred că prima lucrare pe care am scris-o împreună a fost despre plierea labirintului. Deci acesta este un exemplu de pliere a unui labirint dintr-un dreptunghi de hârtie. Și toți puteți încerca asta. Doar căutați pe Google folderul Maze. Puteți genera un labirint aleatoriu. Și această structură 3D poate fi pliată din acest model de cute. Este foarte greu, așa că poate încercați ceva mai mic. Puteți, de asemenea, să scrieți mesajul preferat și să pliați acest labirint -- grafic extrudat -- din acest model de cute. Poate vrei să încep cu ceva mai mic, dar asta este ideea generală. Și este de fapt destul de ușor să dovediți acest lucru algoritmic, dacă aveți un origami foarte bun ca Jason în echipa ta. Ceea ce faceți este să proiectați cum să pliați fiecare tip de vârf. Acesta este doar un grafic pe o grilă. Există un număr constant de moduri diferite în care ar putea arăta fiecare vârf. Ar putea fi gradul 4. Ar putea fi gradul 3, ca T. Ar putea fi gradul 2, fie o viraj, fie o dreaptă. Și proiectați mici gadgeturi, mici modele de cute, care se pliază în fiecare dintre acele mici structuri. Și dacă puteți face acest lucru într-un mod în care aceste limite să fie compatibile, atunci pentru a plia întreaga chestie, faceți un fel de gluon împreună cu acele modele de cute. Și așa funcționează acel software. Acest lucru a fost deosebit de interesant, deoarece puteți plia un grafic arbitrar complicat -- labirint complicat arbitrar , n cu n, cu un factor de scară constant. Atâta timp cât înălțimea la care extrudați acel labirint este constantă, atunci aceasta este o familie de forme pe care știm să o pliăm foarte bine. În general, încercăm să înțelegem ce face ca acest homar să aibă o formă frumoasă, în sensul că poate fi reprezentat cu o bucată de hârtie nu prea mare. Și nu avem răspunsuri generale la această problemă. Cred că a fost un tur vârtej de origami computațional. De asemenea, joc foarte mult în sculptura algoritmică. Una dintre marginile de vârf în origami și matematica origami este înțelegerea modului în care funcționează cutele curbate. Și unul dintre modelele noastre preferate este acesta, în care îndoiți cercuri concentrice alternând munte și vale, tăiați o gaură circulară și se pliază în acest tip de formă Pringle ca un lucru frumos de echilibru fizic. Și apoi îl poți transforma în sculpturi distractive ca aceasta. Acestea sunt făcute cu tatăl meu, Martin Demaine, care este și aici la MIT, sau tipul ăsta. Această hârtie a fost imprimată cu un model conform căreia a fost ars de sticlă. Și apoi este pliat și apoi pus în sticlă, de asemenea. Făcut aici la MIT. Folosim sculptura pentru a încerca să explorăm și să înțelegem intuitiv cum funcționează cutele curbate și apoi înțelegem din ce în ce mai bine matematica chiar-- nici măcar nu știm dacă această suprafață există, dacă este posibil să se plieze în acest fel, deşi apropiindu-se de a-l dovedi. Asta era cam la nivelul superior al acestei ierarhii. Geometria computațională este o umbrelă mai mare, care este reprezentată de o altă clasă, 6.850, care se predă acest termen. Și apoi am vorbit despre plierea geometrică în acea ramură. Permiteți-mi să vă spun pe scurt despre o altă lume a geometriei - foarte diferită în ceea ce privește modelul de calcul. Oh, am sărit puțin înainte. Rebobinați. Lasă-mă să-ți arăt încă o demonstrație distractivă, care... dacă îmi găsesc foarfecele. Dacă iau un dreptunghi de hârtie și îl îndoiesc și fac o tăietură dreaptă, ce forme pot obține? Se numește problema tăieturii pliabile. Are sute de ani. Aici, de exemplu, primesc o lebădă. Iată, primesc... o tăietură dreaptă. Mă desfac și iau pește-înger. Public dur astăzi. Trebuie să continui. Ai mai văzut toate acestea înainte. Acesta este unul deosebit de dificil de pliat - doar de pliat. Și să tai, da. BINE. Asta funcționează bine. Acesta este sigla MIT. Ooh, ah. PUBLIC: Ooh, aah. MIT, da! ERIK DEMAINE: Da. Du-te, MIT. În regulă. Aceasta este de fapt prima problemă la care am lucrat în origami computațional. Este foarte distractiv. Și există un algoritm cu adevărat interesant aici, de asemenea, pentru calcularea modelului de îndoire, cum să vă pliați bucata de hârtie pentru a o alinia - de fapt, orice grafic pe care îl desenați pe o bucată de hârtie, puteți alinia toate aceste margini și nimic altceva . Deci tăiați de-a lungul liniei și obțineți exact ceea ce doriți. Misto. În regulă. Acum, vreau să vorbesc despre ceva complet diferit, care este auto-asamblarea. Un lucru distractiv pe care îl poți face cu ADN-ul, pe care îl avem cu toții. Alegeți câteva fire de ADN grozave și proiectați-le într-un mod inteligent, astfel încât să se potrivească împreună pentru a forma un fel de pătrat cu capete atârnate, pe care le voi numi lipici și fiecare dintre aceste capete atârnate poate avea un model foarte particular și doar identic. sau modele complementare se vor atasa unele de altele. Și astfel puteți folosi acest lucru pentru a vă proiecta propriul sistem de auto-asamblare , așa cum o face biologia, dar proiectat, de exemplu, pentru a construi un computer. Acesta este un exemplu de a lua o grămadă de aceste plăci pătrate și de a construi un contor binar. Acest lucru se numără aproximativ în binar de-a lungul diagonalei. Este puțin înclinată, așa că este greu de văzut. Dar modelul general este că aveți pătrate - acesta este un fel de model de calcul - cu patru adezivi diferite. Și puteți construi orice pătrat doriți, dar nu aveți foarte multe dintre aceste cleiuri diferite, în mod ideal. Și apoi, dacă aveți două plăci cu lipici complementare, acestea vor dori să se potrivească împreună. Dar depinde cât de puternic este acest adeziv, cât de multă afinitate există pentru cât de lungă sunt acele capete care atârnă ADN-ul și, de asemenea, temperatura sistemului tău. Daca ai temperatura foarte mare , nimic. Se vor lipi la temperaturi scăzute, lucrurile vor rămâne împreună chiar dacă nu ar trebui. Dacă vă reglați foarte bine sistemul, puteți proiecta un sistem astfel încât poate acești băieți... acești cleiuri să fie foarte puternici. Și să scriem „E” aici, nu știu, Erik. Și astfel, aceste plăci se vor lipi întotdeauna împreună, dar numai atunci când toate trei sunt lipite împreună poate această plăci, care are complement C și complement F. Apoi , dacă setați temperaturile corect, doar pentru că ambele margini se potrivesc, acest cadran va putea intra. Și aceasta este baza pentru construirea acelui contor binar. Acesta este un model de calcul foarte diferit de cel cu care ne-am obișnuit în această clasă, în care te gândești la instrucțiuni și rulează pe rând. Aici, modelul de calcul este geometric. Aceste pătrate sunt doar care plutesc și se lipesc împreună. Și astfel, programul tău, în orice moment, este un conglomerat de pătrate. Am vrut doar să o menționez pentru că este un model cu adevărat distractiv. Puteți dovedi lucruri interesante în acest model, cum ar fi cum să construiți orice formă printr-o succesiune de pori amestecați între plăci pe care le puteți executa în paralel. Și așa este nevoie doar de log și de timp de pași paraleli, un număr liniar de operații de amestecare diferite , pentru a face o formă arbitrară - chiar și folosind un număr constant de adezivi diferite, ceea ce este cool și poate practic. De asemenea, îl puteți folosi pentru a construi un replicator, în care vi se dă un obiect ca acesta de care nu cunoașteți forma, cum ar fi, nu știm dacă acesta există și nu îl putem modela foarte matematic. Ei bine, și îl bagi într-o cuvă, și toate aceste plăci s-ar atașa și, practic, construiau o matriță, apoi începeau să fotocopiați, în 3D, acea matriță. Și puteți construi asta cu un sistem cu doar doi pași, cred, și un număr constant de tipuri de plăci. Și face toate acestea, în acest model, în timp constant. În realitate, ar trebui să alimentați această mașină și să așteptați ca ea să imprime toate aceste lucruri, iar aceste experimente durează ore, dacă nu zile, pentru a rula. Dar, în teorie, este foarte tare. Și obții niște modele cu adevărat distractive și rezultate foarte generale. De asemenea, îl puteți folosi pentru a construi un miniaturizator sau o lupă și alte lucruri distractive. Acesta a fost un scurt tur al geometriei computaționale. Lucrez mai ales în patru domenii diferite de algoritmi -- geometrie, structuri de date, algoritmi grafici și ceea ce eu numesc algoritmi recreaționali. Cred că am inventat acel termen. Și să trecem la structurile de date, care este reprezentată de această clasă, 6.851. Toate clasele pe care le-am menționat au prelegeri video online, în special pentru cei care urmăresc acasă pe OpenCourseWare. Cele mai multe dintre aceste clase sunt pe OpenCourseWare, iar dacă nu, sunt pe pagina mea web. 6.851, Advanced Data Structures, este o extensie a tipurilor de structuri de date pe care le-ați văzut aici, în 006 și a celor pe care le veți vedea în 6.046. M-am gândit să vă ofer o aromă a unui astfel de rezultat, care este o problemă pe care am văzut-o la această clasă făcută mai bine. Să presupunem că doriți să stocați un set ordonat dinamic. Aceasta este interfața setată. Dinamic în sensul că am inserare și ștergere și ordonat în sensul că vreau să accept find-next și find-previous. Exact ce subset al interfeței setate pe care îl alegeți influențează structura de date pe care ați văzut-o. Am văzut că, pentru seturile dinamice, doriți să utilizați hashing. Dacă nu-ți pasă de find-next, dacă îți pasă doar de find, atunci hashing-ul este grozav - constant așteptat. Puteți dovedi lucruri mai puternice despre hashing. Și facem în acea clasă. Dar dacă vrei dinamic și ordonat, nu poți face timp constant pe operație. Puteți dovedi asta, ceea ce este cool. Ce structură de date am văzut care rezolvă destul de bine această problemă ? Setați arbori AVL, care rezolvă totul în jurnalul n. Deci log n este un concurent. Da. Mă interesează cuvântul model RAM, care este singurul model pe care l-am văzut în această clasă. Se întâmplă să funcționeze într-un model mai puternic. Și putem face mai bine decât să înregistrăm n în următoarele -- îmi va lua ceva timp până să mă fac mai bine, dar iată, cel puțin, o altă limită pe care o putem obține -- log w. Aceasta se face printr-o structură numită van Emde Boas, care este o persoană. AVL este doi oameni. van Emde Boas, chiar m-am întâlnit. Log w-- amintiți-vă, w este dimensiunea cuvântului nostru. Deci, acesta este un timp de rulare puțin ciudat. Este grozav dacă w este log n, atunci acesta este log log n. Și știm că w este cel puțin log n, dar ar putea fi mai mare. Nu prea avem o idee cât de mare am putea ajunge. Poate chiar e n. Poate că e mare... și atunci acestea sunt la fel. Poate că este mai mare decât n, și atunci aceasta este poate mai rău. Dar pentru majoritatea ws, acest lucru este de fapt destul de bun - și într-adevăr, optim. Dar nu este strict mai bine, în niciun sens, încă. Pe de altă parte, există o altă structură de date care rulează în log n împărțit la log w. Acest lucru se numește arbori de fuziune. Acest lucru a fost inventat pe vremea când fuziunea la rece a fost în știri și așa au vrut ca structurile de date să reprezinte. Putem atinge această limită sau putem atinge această limită. Și această limită este bună dacă w este mare. Această bandă la fel de bună dacă w este mică. Poți oricând să iei minul celor doi, orice este mai bun. Și, în special, minimul acestor două lucruri este cel mult-- Cred că este rădăcina pătrată log n peste log log n. Dacă doriți să legați doar în termeni de n, atunci punctul de încrucișare dintre acestea două este acest loc. Și așa ești întotdeauna, cel mult, acest lucru, care este destul de mai bun decât log n-ul AVL. Avem o rădăcină pătrată și avem un lucru ușor în numitor. Destul de mic. Dar cel mai mare lucru este rădăcina pătrată. Și asta e cam misto. Și se pare că este destul de optim. În ceea ce privește o limită n, aceasta este optimă. Minimul acestor două, în general, este aproximativ optim până la log termeni. Pentru distracție, am aruncat formula reală pentru limita dreaptă, care este strânsă până la factorii constanti de potrivire a limitelor superioare și inferioare , despre care vorbim. Sunt minim trei lucruri -- patru lucruri, inclusiv log de w peste un împărțit prin log de log w peste un log de log n peste a. Acesta este ultimul termen pe care tocmai l-am citit. Asta a fost dezordonat. În mod surprinzător, acesta este răspunsul corect pentru această problemă foarte particulară - o problemă foarte naturală. PUBLIC: Ce este un? ERIK DEMAINE: A este jurnalul spațiului pe care îl utilizați. Deci este dimensiunea adresei. Buna intrebare. Dacă îl arunci... deci depinde. Dacă aveți o structură de date în spațiu polinomial, atunci, practic, acestea sunt optime. Și asta se generalizează dincolo de asta. Poate că aveți puțin mai mult decât spațiu polinomial. Misto. Deci sunt structuri de date. Am de gând să trec înainte la algoritmii grafici, pe care, dacă doriți să urmați această clasă, vă recomand un dispozitiv de călătorie în timp . Întoarce-te în toamna anului 2011. S- ar putea să nu mai fie predat niciodată. Dar are video, așa că poți să vizionezi-- în loc să călătorești în timp, dacă nu vrei să- l urmărești live, poți doar să urmărești versiunea înregistrată. A fost predat de o grămadă de postdocs care au fost aici, și puțin eu. Ceea ce îmi place să fac cu graficele este lumea graficelor plane, sau a graficelor aproape plane. Am vorbit mult despre această clasă, algoritmi care funcționează pentru grafice arbitrare. Iar algoritmii pe care i-am văzut în această clasă sunt aproape cei mai buni pe care îi știm pentru o mulțime de probleme pentru grafice arbitrare. Dar dacă graficul tău are o anumită structură, ca și cum ar fi o rețea de drumuri și nu există prea multe pasageri, poți de obicei să desenezi aceste grafice în plan fără treceri. Acesta este sensul lui planar. Poate nu tocmai. Poate doar câteva traversări. Există o generalizare a acestui lucru, în care nu voi intra. Dar să ne gândim doar la graficele plane. Graficele plane au câteva caracteristici frumoase, ca și cum ar avea întotdeauna un număr liniar de muchii. Sunt mereu rare. Deci, puteți conecta imediat asta la limitele noastre existente. Dar chiar și așa, Dijkstra, într-un astfel de grafic, ar lua v log v timp. Pentru graficele plane, puteți face echivalentul lui Dijkstra, adică pot calcula cele mai scurte căi cu o singură sursă cu greutăți de margine negativă în timp liniar. Fără jurnal. Nu este atât de impresionant, dar eliminați un jurnal. Mai impresionant este că putem face echivalentul lui Bellman-Ford, care este o singură sursă cele mai scurte căi cu greutăți arbitrare ale muchiilor într-un grafic plan într-un anumit timp - timp aproape liniar. Jurnalul v pătrat peste log v. Deci există câțiva factori aici -- dar pentru timp aproape liniar , în timp ce Bellman-Ford ar lua v pătrat. Deci aceasta este o îmbunătățire uriașă față de ceea ce am văzut în clasă. Aceștia sunt algoritmi destul de complicati, dar sunt acoperiți în acea clasă, dacă sunteți interesat de ei. Atunci domeniul în care lucrez foarte mult este algoritmii de aproximare pentru grafice plane. Și permiteți-mi să vă ofer o aromă distractivă folosind ceva ce știm, care este căutarea pe lățime. Căutarea prin respirație la care te poți gândi ca construind un fel de inele în jurul unui singur nod rădăcină. Și există această abordare generală - aceasta a fost introdusă de Baker în 1994, pe care am folosit-o pentru o mulțime de probleme diferite. Vrem să rezolvăm o problemă NP-hard pe un grafic. Deci, rulați căutarea pe lățimea întâi dintr-un vârf arbitrar și descompuneți graficul în aceste straturi. Le-ai putea numerota - 0, 1, 2, 3. Acestea sunt niveluri. Și hai să ștergem câteva dintre acele straturi. Să spunem, să ștergem fiecare al patrulea strat. Deci poate îl șterg pe acesta. Șterg toate nodurile din acel strat. Și apoi șterg toate lucrurile din stratul 8 și din stratul 12 și așa mai departe. Banuiesc... Nu știu cu care să încep, dar de la... O să le încerc pe toate. Și apoi șterg fiecare al patrulea strat după aceea. Așa că am șters, în medie, aproximativ un sfert din grafic. Și se dovedește, pentru o mulțime de probleme care vă pasă, cum ar fi alegerea unde să plasați stațiile de pompieri în acest grafic pentru a minimiza timpul de călătorie, dacă există un incendiu undeva în grafic, asta se întâmplă, știi? Incendii și grafice. Atunci acest lucru vă va afecta soluția doar cu un factor de 1 plus un sfert. Așa că veți obține o soluție care se află în 25% din cea optimă, pentru o mulțime de probleme. Și asta funcționează pentru orice valoare 4. Așa că aș putea să o fac pentru 10 și apoi aș ajunge în 10% din soluția optimă. OK, dar cum rezolv de fapt problema după ce șterg fiecare al patrulea strat? Ei bine, atunci graficul tău are această structură suplimentară specială, care este un număr constant de straturi, să spunem. Un număr constant de straturi de căutare pe lățimea întâi. Dacă te uiți doar la această porțiune, această componentă conectată sau la această componentă conectată aici, poți-- graficul tău este aproape ca un ciclu. Este ca și cum patru cicluri stivuite împreună cu unele conexiuni între ele. Și se dovedește că asta este ceva pe care îl poți rezolva cu o programare dinamică foarte elegantă, cum ar fi lucrurile pe care le-am văzut în această clasă, care se concentrează doar pe o singură cale sau pe un singur ciclu. Dacă aveți doar un număr constant de cicluri, cu mai multă muncă, tot puteți face totul în timp polinomial. Aceasta este o abordare foarte generală pentru obținerea de algoritmi de aproximare arbitrar buni. Acestea le numim aproximativ 1 plus epsilon pentru orice epsilon. Dar cu cât epsilonul este mai mare, cu atât îți iei mai mult timp. Este ceva de genul 2 la ordinul 1 peste epsilon ori polinomul n. Deci, atâta timp cât epsilonul este constant, acesta este timpul polinomial. Aceasta se numește PTAS. Oricum, au fost algoritmi grafici. Ultimul subiect este algoritmii recreaționali, care este poate cel mai bine cuprins în această clasă. 6.892 este cel mai recent nume. Își schimbă numele din când în când. Și l-am menționat în prelegerea de complexitate a durității, deoarece această clasă este despre dovezi de duritate, analizând jocuri și puzzle-uri distractive. Am văzut duritatea Tetris NP în acea prelegere. Dar poți și dovedi că Super Mario Brothers este greu, sau Portal este greu, sau Mario Kart este greu sau The Witness, un joc video modern, este greu. Sau, unul dintre cele mai recente rezultate ale noastre este că Recurse-- jocul din dreapta sus-- este indecidabil. Nu există un algoritm pentru a juca perfect acel joc. Și poți chiar să descarci nivelul -- un exemplu al nivelului și să-l joci, dacă îndrăznești. Așa că este mult... ne distrăm foarte mult în lumea aceea de duritate a diferitelor jocuri și puzzle-uri. Unde vreau să merg mai departe? BINE. Următorul subiect este răsucirea baloanelor. Total diferit. Acest lucru este recreațional, dar nu despre duritate. Acesta este un octaedru răsucit dintr-un balon. Am mai făcut unul pe un băț. Fiecare dintre acestea este făcută pentru un balon. Ce grafice poți face pentru un balon? Ei bine, ar trebui să citiți ziarul nostru. Și puteți caracteriza de câte baloane aveți nevoie pentru a face fiecare poliedru. Și unele dintre aceste probleme sunt NP-grele și este foarte distractiv. Misto. Cred că acesta este sfârșitul diapozitivelor. Ultimul lucru pe care am vrut să-ți arăt este o problemă, un puzzle/truc magic -- vine din lumea puzzle-ului -- numită problema agățarii imaginilor. Așa că imaginează-ți că ai o poză. Vrei să-l atârnești pe un perete. Așa că ai investit într-o frânghie frumoasă și ai atârnat-o pe un cui. Dacă cade cuiul, poza cade și ești trist. Așa că investești în două unghii, așa cum am eu aici, și poate îți agăți poza pe ambele unghii. Acum, dacă una dintre cuie cade, mai ai o poză atârnată strâmb. Dacă cade cealaltă unghie , OK, a dispărut. Vreau să atârn o poză pe două unghii astfel încât, dacă scot oricare dintre cuie, poza să cadă. Deci, Jason, alege un cui, la stânga sau la dreapta. Stânga, scoatem. Asigură-te că asta nu cade... și, bum, poza cade. Aceeași împachetare. Poți verifica... poți derula înapoi videoclipul, asigură-te că am făcut aceeași împachetare. JASON KU: Și scoateți dreapta. ERIK DEMAINE: Atunci scoate-l pe cel potrivit. Buna alegere . Apoi, de asemenea, poza cade. Acesta este un puzzle clasic, dar îl puteți generaliza. Așa că lasă-mă să o fac pentru trei unghii, care este tot ce am aici. Această unghie se lasă puțin. y, x-- y invers, x invers. Cred că este corect. Deci, aceasta este o modalitate de a atârna o poză pe trei cuie, astfel încât, dacă scot vreuna dintre unghii, poza să cadă. Justin, 1, 2 sau 3? 2. OK. Da, vreau să ies din drum și să mă asigur că nu trec peste margine aici. Da. Este mult mai ușor să- l faci să funcționeze. Dar poți vedea, bum, poza cade acolo. Și, desigur, imaginați-vă gravitația infinită. Și poza cade. Ta-da! Puteți generaliza acest lucru pentru a face în esență orice -- ceea ce se numește o funcție booleană monotonă -- pe orice set de unghii. Adică, puteți face ca orice subset de unghii să facă ca imaginea să cadă și orice colecție de subseturi de unghii să o facă să cadă. Desigur, dacă scoți mai multe unghii, tot va cădea. Acesta este sensul monoton. Dar altfel, puteți face un model arbitrar, care este distractiv. Acesta este de fapt un rezultat cu Ron Rivest și o grămadă de alți oameni. Cred că am ajuns aproximativ la timp. Deci a fost un tur rapid. Și, evident, există diferite clase aici pe care le puteți lua. 6.892, clasa de duritate, tocmai a fost oferită semestrul trecut, așa că probabil că nu va mai fi pentru o perioadă. Dar toate aceste cursuri sunt online. Urmăriți videoclipurile, nu ezitați să-mi puneți întrebări. Și acum îl avem pe Justin. Ți-am lăsat spațiu aici pentru schița ta. Nu trebuie, dar am să-ți pun numele. JUSTIN SOLOMON: Mulțumesc. JASON KU: Deci Justin este și geometru. ERIK DEMAINE: Da, avem o mulțime de oameni de geometrie în 006 în acest semestru. JUSTIN SOLOMON: Mulțumesc. BINE. Nu pot să nu împărtășesc că, pe chat-ul nostru cu instructor, Erik a trimis un mesaj text că va fi... era cumva nervos că tipul aplicat ar avea toate lucrurile interesante pentru a le arăta, iar acum mă simt complet plictisitor . [Râde] Corect. Da. Avem trei instructori de geometrie diferiți în această clasă. În această clasă, cred că avem multe arome diferite de geometrie care sunt într- un fel reprezentate în această cameră aici, de la inginerie mecanică, la teorie și multe alte lucruri interesante, la orice fac eu. De asemenea, sunt profesor la CSAIL și conduc un grup care studiază probleme de geometrie puțin mai aplicată, într-un anumit sens, iar în CSAIL, depășim o mulțime de granițe -- de fapt, mai aproape de departamentul de matematică decât de grupul de teorie și informatica, despre care aș spune că este în mare măsură un artefact istoric, mai degrabă decât ceva interesant despre informatică sau matematică. Continuând în turul nostru vârtej de cursuri de geometrie interesante aici la MIT, mai am câteva lucruri distractive de adăugat la listă. Și vom prezenta câteva dintre idei în următoarele două diapozitive aici. Deci, în mod normal, în fiecare toamnă, predau 6.837, care este cursul de introducere în grafica computerizată. De fapt, background-ul meu a lucrat într-un studio de animație pentru un pic de timp și am obținut un credit pentru film până când au schimbat standardele pentru creditele pentru film, iar apoi a încetat să se mai întâmple. Dar în orice caz, dacă te uiți... ce este filmul... Sus, cu bătrânul. Dacă apăsați pe pauză la momentul potrivit, mă puteți găsi chiar deasupra listei de bebeluși care s- au născut în timpul producției. Dar, în orice caz, deși grafica pe computer s-ar putea să nu sune ca o disciplină algoritmică, voi încerca să vă conving că, într-un anumit sens, puteți lua aproape pe oricine din departamentul nostru, ați putea să predea 6.006 și să oferiți un lucru similar. spune că, de exemplu, materialul pe care l-ai întâlnit în acest curs va fi relevant pentru viața ta. Celălalt curs pe care îl predau și care ar putea fi de interes -- și de fapt, este puțin mai aromat teoretic -- pe care îl predau este 6.838. Deci, din moment ce Erik mi-a pus numele pe tablă aici, cred că pot desena The So, principalul obiect de interes din 6.838 este un lucru special numit complex simplial. De obicei, în 6.006, petrecem mult timp gândindu-ne la grafice. Lasă-mă să-ți desenez un grafic. Așa că voi lua un pătrat și îl voi împărți. Și acum, să presupunem că am pus marginile în diagonală așa. Acum, în 6.006, acest lucru este doar o grămadă de noduri conectate prin margini. De fapt, dacă aș lua această margine și l-aș muta în jos sau așa ceva, ar fi același grafic. Dar, desigur, în multe aplicații de grafică pe computer, acest lucru arată foarte mult ca un pătrat. Și motivul este că, desigur, graficul de aici conține triunghiuri în interiorul acestuia. Și așa, de exemplu, poate mă gândesc la graficul meu ca la o colecție de vârfuri, o colecție de muchii. Acesta este genul de notație pe care l-am mai văzut. Și apoi adaug un al treilea lucru la descrierea mea, care este un set de tripleți. Acesta este un set de triunghiuri aici. Și putem lua mulți algoritmi despre care am vorbit în această clasă și îi putem extinde la acest caz. De exemplu, iată unul înșelător de enervant. Să presupunem că vreau calea cea mai scurtă între două vârfuri ale graficului meu. Cu siguranță am învățat algoritmul lui Dijkstra. Aceasta este o tehnică pentru a face asta. Și într-adevăr, practica obișnuită în grafica pe computer, ceea ce este rușinos, este pe rețeaua triunghiulară, dacă doriți calea cea mai scurtă între două vârfuri, rulați algoritmul lui Dijkstra pe margini. Și să vedem dacă funcționează foarte repede. Să presupunem că vreau calea cea mai scurtă între-- și, apropo, voi presupune că lungimea marginilor mele sunt lungimile așa cum le-am desenat pe tablă aici. Deci este ca 1, 1, rădăcină pătrată a lui 2. OK. Deci, să presupunem că vreau calea cea mai scurtă între stânga jos și dreapta sus. Dacă rulez algoritmul lui Dijkstra, suntem într-o formă bună, nu? Primim... Vă las să faceți calculele acasă. Veți obține calea care este aceste două margini. Dar iată un lucru cu adevărat enervant. Să zicem, în schimb, am vrut calea cea mai scurtă din stânga sus la dreapta jos. Dacă rulez algoritmul lui Dijkstra pe acest pătrat triangulat, care va fi calea cea mai scurtă? Da. De fapt, sunt o grămadă. Unul dintre ei ar putea merge până la capăt, apoi până la dreapta. Care este lungimea acestui drum? 1, 2, 3, 4. Aceasta este lungimea drumului cel mai scurt? Ei bine, probabil că nu. Ei bine, am dori ca drumul nostru cel mai scurt să facă așa ceva. Dar graficele nu știu să vorbească cu triunghiurile. Și asta va fi o problemă. De fapt, abia recent termenii istorici [INAUDIBILI] am putut să elaborăm algoritmul corect pentru calea cea mai scurtă într-un domeniu triangulat ca acesta. Și acesta este timpul de rulare la care ne-am aștepta. Aceasta se numește MMP. Bănuiesc că Erik și Jason ar putea face o treabă mai bună descriindu-l decât mine. Dar ideea de bază a algoritmului MMP este, de fapt, o extensie frumoasă a modului în care am predat algoritmul lui Dijkstra în 6.006, pentru că ei țin evidența acestor seturi de nivel ale funcției de distanță. Dar acum, seturile de niveluri trebuie să-- hopa-- trebuie să fie ferestre și margini așa atunci când calculez calea cea mai scurtă, ceea ce este o durere de cap uriașă. Acesta este unul dintre acești algoritmi care a fost cunoscut în teorie cu aproximativ 10 ani înainte ca cineva să se obosească să-l implementeze într-un mod în care să se convingă că a rulat în n log n timp. Și în zilele noastre, există o industrie de cabană în lucrările de cercetare grafică pe computer pentru a implementa acest lucru și apoi îl accelerează în moduri diferite. Și, din păcate, realitatea este că un alt algoritm pe care îl acoperim în 6.838 numit fast marching -- care de fapt nu vă oferă cea mai scurtă cale, dar o aproximare a acesteia -- este mai rapid, mai ușor de utilizat și practic imposibil de distins. În orice caz, în 6.838, avem oarecum o dublă mentalitate interesantă. Vom vorbi despre o mulțime de algoritmi care arată ca ceea ce am făcut în oricare ar fi această clasă -- 6.006. Dar, în același timp, începem să avem o aromă mai geometrică și nu ne îngrijorăm atât de mult cu privire la [INAUDIBIL].. Deci, în modelul nostru de calcul , de multe ori, suntem oarecum de acord cu numerele reale, pentru că asta nu este unde este durerea de cap. Și, desigur, când scrieți cod în această clasă, utilizați virgulă mobilă cu precizie dublă . Dacă ești mai responsabil, ca în prelegerea anterioară a lui Jason, probabil că ar trebui să ții evidența numărului de operațiuni pentru a te asigura că eroarea ta este numărată. Dar nu sunt sigur că ne deranjam cu adevărat cu asta. În orice caz, acest lucru ne permite să avem două mentalități diferite. Există o singură mentalitate, care este discretă. Există o altă mentalitate, care este netedă. Ne gândim la înțelegerea geometriei, precum aceste domenii triunghiulare, ca o aproximare a unei suprafețe netede. Și apoi am putea dori să facem lucruri precum calculul curburii și așa mai departe, care este într-adevăr asociat cu derivatele de calcul, pe care, desigur, le vom avea pe aceste tipuri de obiecte simple. Și asta duce la această zonă cu adevărat distractivă a matematicii și informaticii, oricare ar fi, numită geometrie diferențială discretă , care sună ca o contradicție în termeni. Și este ceva despre care am tratat destul de detaliat în acest curs. Așa că construim, tot calculul, că singurele calcule pe care rămâi să le faci sunt pe vârfurile și muchiile și triunghiurile unei rețele triunghiulare. Și ajungeți destul de departe, incluzând unele construcții de topologie, cum ar fi complexul Duran și așa mai departe. Aș argumenta, de fapt, dacă urmați cursul nostru și apoi cursurile de geometrie diferențială din acel departament, cumva, unii dintre indici și dureri de cap pe care le întâlniți adesea în lumea aceea sunt mult mai concrete atunci când încercați să le faceți să funcționeze pe o plasă. . În orice caz, cred că mi-am petrecut deja tot timpul. Vă pot spune puțin despre cercetările din grupul nostru. Conduc cu adevărat un grup ciudat, extrem de [INAUDIBIL], în care unii dintre studenții noștri sunt în esență studenți la teorie-- atingeți-vă tastatura. Îmi pare rău. A fost un reflex. Dar a fost rapid. În regulă. Așa că avem câțiva studenți a căror pregătire este în matematică, alții care sunt în industria de conducere autonomă și au decis să se întoarcă și să lucreze în cercetare. Din această cauză, avem acest set extrem de larg de probleme de cercetare, totul, de la genul de probleme clasice de învățare automată pe care le-ați putea întâlni în lumea geometriei, cum ar fi dacă am o mașină care se conduce singur și aș vrea să identific pietonii și alte mașini pe drumul într-un mod eficient și precis. Apropo, o parte din aceasta este învățarea automată și profund orice, dar mai există o altă parte, care sunt algoritmii. Pentru că, de fapt, ceea ce vine în scanerul tău LiDAR este de ordinul [INAUDIBIL] cu puncte și o mică fracțiune de timp. Și complexitatea temporală a algoritmului tău de învățare este de fapt esențială pentru a-l face corect, și ceva care există o mulțime de probleme deschise în acest moment, deoarece nu este într-adevăr compatibil cu arhitectura hardware pe care o folosesc adesea aceste mașini. Ne uităm și la problemele de geometrie [INAUDIBILE] , de exemplu, dacă vă dau date, pot găsi o structură geometrică? Deci este un exemplu clasic de procesare a limbajului natural. Când folosim cuvinte precum aproape și departe, în termeni de semantică și semnificație, tot timpul. Întrebarea este, putem găsi de fapt o încorporată a datelor noastre de cuvinte într-un spațiu geometric pentru a facilita algoritmii statistici la care ne pasă? Și, bineînțeles, aplicăm geometria la o mulțime de probleme practice, totul, de la meshing și calcul științific, care cred că este un fel de clasic - de fapt, cred că suntem primul grup care a enumerat toate cele mai interesante. lucruri care se pot întâmpla cu ochiurile decaedrice, care este această cifră de jos aici. Ar trebui să le arăt oamenilor asta. Sunt câteva lucruri distractive de văzut acolo. Pentru alte probleme practice, cum ar fi luarea... Erik a luat o zebră și a împăturit-o. Putem lua o zebră și să-i mutăm textura pe o pisică sau un porc -- sau, de fapt, pe partea laterală a ecranului. Dar dacă nu mutăm hârtia, [INAUDIBLE] pentru scanarea 3D a ceea ce ar putea [INAUDIBIL]. În orice caz, în cele cinci minute pe care le-am rămas aici, m-am gândit să aflu în detaliu două-- sau poate o aplicație, în funcție de când se plictisesc Jason și Erik. Și, în esență, mesajul meu pentru voi este, desigur, [INAUDIBIL]. Nu sunt cu adevărat un membru central al grupului de teorie CS aici la MIT. Dar, din păcate pentru voi , 6.006 este inevitabil. Chiar dacă vrei să intri în învățarea profundă, statistici, orice -- știința datelor -- vei întâlni materialul pe care l-ai văzut în acest curs. Și, de fapt, este cu adevărat painea și untul pentru aproape tot ceea ce face toată lumea aici, în acest Centru de date. Așadar, vă voi da două exemple rapide, dintre care unul extras din predarea mea, unul din cercetarea mea. Dacă veți continua cu mine în toamna viitoare, vom preda 6.837, care este cursul Introducere în grafica computerizată . Un lucru care este întotdeauna uimitor pentru studenți este că acești algoritmi care produc aceste imagini cu adevărat frumoase pot încadra în aproximativ 10, 20 de linii de cod. Deci, într-adevăr, acest lucru este complet fațios, pentru că dacă vrei acele imagini frumoase și folosești acele 20 de linii de cod, vei aștepta până la moartea universului pentru a calcula efectiv aceste lucruri. Dar, în orice caz, una drăguță pentru randare-- deci desenați o grămadă de forme [INAUDIBILE], ceva numit ray casting, sau vărul său mai cunoscut, ray tracing. De obicei, diferența este dacă razele tale pot sări de pe suprafață și pot avea un lucru secundar. Dreapta. Iată algoritmul de turnare a razei. Să presupunem că am o scenă construită din sfere și cuburi. Voi avea o buclă for peste fiecare pixel de pe ecranul computerului. Pentru fiecare pixel, trebuie să descopăr ce culoare ar trebui să fie. Așa că trag o rază din globul ocular prin acel pixel și găsesc primul obiect în care se lovește. Nu este atât de greu să intersectezi o linie a unei sfere sau o linie a unui cub. Deci, ce este acel algoritm? Ți-am dat-o pe ecran aici. Nu e prea rău să te gândești. Și cred că sunteți cu toții extrem de bine echipați pentru a analiza durata de rulare a acestui lucru, care este aproximativ numărul de pixeli ori numărul de obiecte. Pentru că pentru fiecare pixel, trebuie să decid ce obiect lovește prima raza din globul meu ocular. Deci am nevoie de o buclă for peste [INAUDIBIL].. Ai sens? Misto. Deci, să ne uităm la o problemă de bază de randare. De fapt, Erik l-a furișat deja pe acesta în secret aici. Există un model 3D foarte faimos numit iepurașul Stanford. Iepurașul de la Stanford este de fapt un exemplu grozav de complex simplist - de fapt, unul multiplu, suprafață triangulată. De fapt, nu sunt sigur că este divers în forma sa originală. Dar, de obicei, este. Și acest model 3D cu aspect inocent și extrem de faimos este de fapt destul de pernicios. Este compus din 69.000 de triunghiuri. Și dacă am vrut 1080p - ca o redare de înaltă definiție a triunghiului meu - atunci, desigur, sunt două milioane de pixeli pe ecran. Deci, dacă ne uităm la marea noastră expresie O, aproximativ, timpul nostru de calcul se scalează ca produsul acelor două numere mari. Așa că doar pentru a reda acest iepuraș gri urât îmi ia destul de mult timp. Și, de fapt, realitatea... apropo, iepurașul este acest caz de testare faimos în grafică computerizată, așa că, dacă iei cursul meu, vei fi prieteni toată ziua. Realitatea este că nu vrem doar iepurași gri, umbriți. Vrem iepurași care să fie transparenți și care reflectă , iar eu îmi împușc iepurașul cu un glonț și se sparge într-un milion de bucăți și toate aceste lucruri interesante. Deci, desigur, algoritmul de turnare cu raze, cu fiecare dintre aceste noi caracteristici grafice pe care le adaug, nu face decât să adauge la complexitatea timpului tehnicii pe care o implementez. Așa că destul de repede – și într-adevăr, dacă vă scrieți propriul ray tracer acasă, ceea ce vă încurajez cu tărie să faceți – ceea ce veți descoperi este că un [INAUDIBIL] ar fi expresia tehnică. Care este calea noastră de ieșire din asta? Ei bine, dacă o luați 837, veți vedea că calea noastră de ieșire din aceste probleme, în grafică, sunt structurile de date și algoritmii. Este complet inevitabil. De exemplu, evident, am petrecut destul de mult timp în acest curs vorbind despre arborii AVL. În 837, vom petrece o mare parte din tururile noastre vorbind despre copacii de compartimentare a spațiului. Aici... chiar am uitat ce fel de copac este acesta. Cred că este un arbore KD. Nu contează. În orice caz, un lucru pe care l-aș putea face este să iau toate triunghiurile iepurașului meu și aș putea pune întregul iepuraș într-un cub uriaș cu proprietatea că cubul este în afara iepurașului. Să presupunem că arunc o rază și raza nu atinge cubul. Poate raza să atingă iepurașul? Fara drept? Zinge chiar pe lângă el. Deci, dintr-o dată, mi-am economisit mult timp de calcul, nu? Nu trebuie să repet peste toate triunghiurile din interiorul corpului pentru a vedea dacă lovesc raza sau nu, pentru că deja m-am convins, prin acest test conservator, că nu am lovit nici măcar căsuța de delimitare a întregului iepuraș. . Ei bine, este un fel de comandă bună de accelerare. Dar, în funcție de cât de mare este iepurașul în raport cu dimensiunea imaginii mele redate, acesta ar putea să nu fie un test de eficiență foarte util. Dar bineînțeles, ce aș putea face? Aș putea să iau cutia care conține iepurașul, aș putea s-o felii în două, iar acum se spune, raza mea lovește fața sau spatele iepurașului? Sau poate ambele. Acolo trebuie să... acolo lucrurile devin noduroase. Și așa mai departe. Așa că acum aveți această structură de copac recursivă drăguță, în care tot iau cutia care conține iepurașul meu și o tai în jumătate și așez -- într-un anumit sens, de obicei, triunghiurile -- poate nu frunzele copacului meu, dar [INAUDIBIL] probabil că este suficient de bun. Obțineți o structură ca cea pe care o vedeți pe ecran aici. Și de ce ar trebui să faci asta? Ei bine, amintiți-vă, este nevoie de mult timp pentru a reda imaginea mea despre iepurașul meu în mod normal. Ei bine, acum, imaginea este de fapt înșelător de sugestivă. Dar ați putea crede că, poate, este nevoie de aproximativ -- amintiți-vă, n este numărul de obiecte din scena mea -- p log n timp pentru a reda iepurașul meu acum, pentru că pot să traversez arborele de obiecte din scena mea. Desigur, observați, am pus un semn de întrebare aici. Și diavolul e în detalii aici. De fapt, cred că oamenii de grafică pe computer cred adesea că algoritmul lor de randare durează p log n timp. Adesea, acest lucru nu este posibil, deși este o întrebare interesantă, și anume, euristicile pe care le folosesc pentru construirea acestor tipuri de copaci le oferă adesea, în medie, timp de log n. Și, așadar, există ceva despre date care face această problemă mai ușoară decât ar părea. Așa că vom cerceta puțin în asta în clasa de grafică. Desigur, nu vei demonstra atâtea limite cât ai putea într-un curs teoretic. Dar cu siguranță ne bazăm pe intuiția pe care am văzut-o în această clasă pentru a construi pe structuri de date practice . Și aceste structuri de date apar peste tot în grafica computerizată. De exemplu, graficele aciclice direcționate apar peste tot în literatura de grafică pe computer pentru a descrie scene 3D. De exemplu, această sală de clasă ne aduce aminte de ce avem nevoie de DAG-uri și grafică pe computer, pentru că avem toate aceste locuri goale aici și toate sunt copii unul după altul. Deci, ar avea sens pentru mine să depozitez câte 100 de matrițe 3D ale aceluiași scaun? Probabil ca nu. Deci, în schimb, ce să fac? Stoc o instanță a unui scaun și apoi câteva instrucțiuni despre cum să-l plasez în întreaga mea scenă. O modalitate prin care pot face asta este să mă gândesc că există un nod într-un grafic care știe să deseneze un scaun. Și acum, pot avea o grămadă de noduri diferite în scena mea pentru toate instanțele scaunului și apoi pot stoca o transformare diferită pentru fiecare. Deci, dacă vă gândiți la structura graficului de aici, fiecare dintre aceștia va indica același model 3D al scaunului pentru randare. Și asta face o structură de graf aciclică direcționată numită graf de scenă, despre care vom petrece destul de mult timp vorbind în 837, despre cum să traversăm și să construim toate acele lucruri bune. Și există o mulțime de modele diferite de calcul în acel univers, de asemenea. Placa dvs. grafică este un tip foarte specific de procesor paralel, care seamănă cu Lucille Ball pe banda transportoare, lovind același obiect din nou și din nou. Dar dacă îi ceri să facă altceva decât singurul lucru pe care știe să-l facă pentru o grămadă de date odată, atunci toate calculele tale se oprește. Acesta se numește paralelism de date multiple cu instrucțiuni unice , SIMD. Algoritmii numerici contează foarte mult pentru lucruri precum simularea fluidelor. Și algoritmii de aproximare sunt, de asemenea, destul de critici. În grafica computerizată, complexitatea este destul de interesantă, deoarece, desigur, globul ocular este sensibil la aproximativ 29,97 cadre pe secundă de material. Puteți alege acel moment pentru a face foarte bine randarea unui obiect, dar apoi scoateți din timpul redării altceva. Există un fel de lege de conservare interesantă pe care trebuie să o echilibrezi atunci când rezolvi aceste tipuri de probleme, care este un echilibru interesant, acum, între complexitatea și timpul de rulare al algoritmului și percepției tale. Cu ce ​​lucruri poți scăpa când desenezi o scenă? Și poate pot face o mulțime de calcule suplimentare pentru a obține acea umbră suplimentară, dar pur și simplu nu merită. Voi schița rapid o altă aplicație complet diferită a materialului pe care l-am acoperit în 6.006 din propria mea cercetare. Din nou, la fel ca Erik-- cred că, într-un mod amuzant, ambele grupuri, cred, sunt destul de ample în ceea ce privește subiectul, mai degrabă decât-- unii dintre colegii noștri se concentrează cu adevărat pe un subiect sau altul . Un alt domeniu de cercetare în care m- am oarecum susținut este zona redistribuirii politice. Acest lucru este relevant în Statele Unite. Recent, am citit această propunere grozavă despre alte țări, ceea ce este foarte interesant, cum fac aceste lucruri. În SUA, când votăm pentru oamenii din Congres, apropo, nu neapărat pentru președinți. Aceasta este o concepție greșită comună. Dar, cu siguranță, pentru Congres, statul tău este împărțit în regiuni mici, fiecare dintre ele alege un membru al Camerei. Și există un fel de problemă subtilă dacă nu ești obișnuit să te gândești la asta, sau una care te privește în față și țipă, în funcție de cât de des citești știrile și politica. Există o problemă numită gerrymandering, în care legislatura dvs. trasează liniile pentru ce zonă de pe hartă alege un membru al Congresului. Și în funcție de modul în care trasați liniile, puteți crea rezultate diferite pentru cine este probabil să fie ales. Deci, de exemplu, poate că există o minoritate. Le pot grupa pe toate într-un singur district electoral. Atunci ei vor avea doar posibilitatea de a alege o singură persoană. Dar poate, dacă împart spațiul în care locuiesc în două, am reușit să proiectez două districte cu o mare probabilitate de a alege pe cineva având în vedere interesele lor politice. Se pare că redistribuirea politică, în sens larg, este o mare problemă, din punct de vedere computațional. Chiar dacă ești un teoretician total lipsit de inimă, există câteva probleme cu adevărat distractive aici. Deci, de exemplu, statul Iowa-- noi toți alegem Iowa pentru că are o lege unică, și anume că districtele trebuie construite din județe, care sunt mult mai mari decât unitatea tipică de recensământ, deci este mai ușor din punct de vedere computațional. Dar chiar și în Iowa, care este o grilă uriașă-- cu excepția unei schimbări la mijloc, care este fascinant pentru mine-- știu [INAUDIBIL], fapt amuzant. Literal, oamenii făceau harta Iowa și lucrau de jos în sus și de sus în jos, iar aceasta se întâlnește la mijloc și grilele lor au fost deplasate, iar acum am rămas blocați cu asta. Și are un efect interesant asupra topologiei graficului, pentru că arată ca pătrate, dar apoi sunt triunghiuri în mijloc. Dar, în orice caz, chiar dacă există doar 99 de județe în patru districte, există aproximativ chintilioane de moduri posibile prin care poți împărți acel stat în patru districte învecinate care îndeplinesc regulile așa cum au fost -- cel puțin, dacă citești codul literal în lege. Se pare că computerele sunt utile, dar, din păcate, este puțin subtil cum. De exemplu, nu există un singur „cel mai bun” plan de district. Nu mă pot gândi la un singur stat cu o lege care să vă ofere o funcție obiectivă, asemănătoare cu orice personaje drăguțe pe care le-am avut în 6.006. De multe ori au obiective foarte clare în viață, dar, din păcate, redistribuirea, așa este foarte rar. Trebuie să echilibrezi contiguitatea, echilibrul populației, compactitatea, toate aceste lucruri diferite. Verificarea realității numărul doi este că, chiar dacă cineva ți-a dat o funcție obiectivă, pentru aproape orice funcție obiectivă interesantă, este foarte evident că generarea celui mai bun plan de district este NP-greu. Și apropo, nici nu contează, pentru că legea nu spune că computerele trebuie să deseneze cele mai bune raioane. Chiar dacă P este egal cu NP ar putea într-adevăr extrage cel mai bun plan de raionare posibil folosind un algoritm, nu înseamnă că trebuie să îl utilizați, cel puțin așa cum este scrisă legea acum. Interesant, acest lucru nu este adevărat în anumite părți ale Mexicului, unde de fapt te fac să compari planul tău de district cu unul generat de computer, ceea ce este cu adevărat interesant din punct de vedere filozofic, deși în practică, nu funcționează teribil de bine. Cercetătorii noștri au studiat în schimb analiza planurilor de district. Deci, în loc să rulați un program care preia statul dvs., vă desenează districtele și apoi ați terminat-- în schimb, punem întrebări statistice despre, propun un plan de district, cum arată în raport cu spațiul posibilitatile? Deci asta, desigur, ridică întrebarea, care sunt posibilitățile? Deci acestea sunt partițiile grafice conectate. Adică, aveți un grafic și luați vârfurile și le grupați într-un mod în care sunt conectate între ele. Singurul lucru asupra căruia suntem cu toții de acord -- de fapt, filozofic, este îndoielnic de ce -- este că ar trebui să poți începe în orice punct din districtul tău și să mergi la oricare altul fără să pleci. În zilele noastre, cu internetul, nu este clar că acesta este de fapt cel mai bun criteriu. Dar aceasta este o lege care, cred, nu va fi niciodată adoptată în viitorul apropiat. Oricum, cred că nu mai am timp, așa că nu cred că vă voi ghida prin teoria aici. Poate o voi lăsa în diapozitive. Există un fel de dovadă foarte simplă care poate arăta că, cel puțin cel mai simplu lucru la care te-ai putea gândi pentru a-ți analiza planul de district, și anume, propui un plan, iar acum vreau ca planul tău să fie cel puțin la fel de bine, sub o anumită axă, deoarece este una desenată aleatoriu din spațiul tuturor partițiilor posibile conectate - toate modalitățile posibile în care aș putea desena liniile. Ei bine, atunci, ar putea fi util să aveți o bucată de software care să deseneze la întâmplare așa ceva. Deci, cu alte cuvinte, pentru a desena ceva în care probabilitatea unei partiții este 1 peste numărul de partiții. Asta pare nevinovat. De fapt, există o serie de lucrări care pretind că fac astfel de lucruri. Dar se dovedește că este dificil din punct de vedere computațional, presupunând că credeți că P nu este egal cu NP. Așa că, poate, voi lăsa câteva imagini sugestive în diapozitiv pe care le putem... dacă îmi trimiteți un mesaj sau dacă avem o conversație profesor-student, sunt bucuros să vi le schițesc atunci. Există o dovadă foarte drăguță, ușoară, care reduce acest lucru la ciclul hamiltonian și vă arată că poate nu ar trebui să aveți încredere în aceste instrumente, așa cum se discută despre ele, literalmente, la Curtea Supremă în urmă cu câteva luni. Apropo, a fost destul de distractiv. Raportul nostru de expertiză a fost menționat în apărarea cazului vara trecută. Și când citiți discuția, puteți vedea judecătorii încercând să discute despre complexitate. Și este o lectură interesantă, dacă oarecum uscată. În orice caz, acesta este doar punctul de plecare al cercetării noastre, care spune că, desigur, aceste probleme de eșantionare sunt foarte grele. Întrebarea este, ce poți face? [INAUDIBIL] sau nu. Dar adevăratul mesaj aici este, desigur, că acest curs este inevitabil. Chiar și în aceste probleme extrem de aplicate care apar în cauzele judiciare sau pe placa dvs. grafică, încă... complexitatea și algoritmii și structurile de date vor reveni la joc. Așa că, cu asta, ceilalți doi instructori ai noștri aici sus pentru ultim rămas bun... să ne distanțem corespunzător. ERIK DEMAINE: Deci algoritmii sunt peste tot. Sper că v-a plăcut această clasă. A fost foarte distractiv să vă predau și să vă avem studenți. Chiar dacă nu ești aici fizic în cameră, încă simțim prezența ta. Și aștept cu nerăbdare să vă văd pe toți în curând. Mulțumesc că faci parte din acest lucru distractiv. Vreau să le mulțumesc celor doi... celor doi co-instructori ai mei pentru un timp minunat în acest semestru. A fost foarte distractiv să vă predau. JASON KU: Mulțumim că ai cheltuit 006 cu noi în acest termen. JUSTIN SOLOMON: Da. Mulțumesc. Și sperăm că ne vom revedea curând. ERIK DEMAINE: La revedere. JASON KU: La revedere.