[MIZIK jwe] DAVID J. Malan: Sa a se CS50. Lè sa a se kòmansman an nan semèn twa. Se konsa, nou te gen yon anpil nan enteresan bagay yo kouvri jodi a. Yon anpil nan opòtinite pou volontè moute sou etap yo. Epi finalman, jodi a se pa sou Kòd nan tout. Men, li la sou lide, ak li a sou algoritm, ak aktyèlman pote tounen kèk nan leson yo aprann nan semèn zewo, dans sonje, nou prezante atrosite sa a. Apre sa, prete enspirasyon de sa, yo kòmanse yo rezoud tout tan pi plis sofistike pwoblèm algorithmically. Men, anvan, yon koup la anons. Se konsa, yon sèl, si ou ta renmen yo rantre nan Anplwaye CS50 a ak kamarad klas yo nan manje midi sa a Vandredi, tou de isit la ak nan Cambridge, ak nan New Haven, tanpri vizite a nan kou sit entènèt, kote ka yon URL ka jwenn li. Konferans sa a Mèkredi pral Ou pa bezwen isit la nan Sanders. Li pral sou entènèt sèlman, se konsa melodi nan nan sit wèb CS50 a, si wi ou non isit la nan Cambridge ou nouvo Haven tou. Lè sa a, pwoblèm mete de se deja nan men ou. Si ou pa gen plonje nan ankò, pèmèt mwen yo ofri sijesyon an fòtman remak bwèf sa, espesyalman kounye a, kòm pwoblèm nan kouche avanse, ou reyèlman vle kòmanse kounye a, si se pa travayèz yon ti jan sou fen semèn nan oswa anvan lè yo te premye ale deyò sou Vandredi, paske ou pral jwenn yo ke yo ap pa nesesèman ap resevwa pi long oswa pi difisil pou chak SE. Mwen panse ke w ap jwenn ke, nan jeneral, yo gen tandans pran apeprè alantou an menm kantite tan. Men, li sètènman depann sou elèv la, epi li depann sou attitude a ak ki ou apwòch li. Men, toujours, w ap ale nan kouri moute kont kèk mi, ak w ap ale nan frape kèk ensèk, epi w ap jis pa ale pou kapab jwenn sou li nan kèk pwen. Lè li nan lajman ki gen anpil valè yo dwe kapab nan etap lwen, tounen jou kap vini an vini, ale nan lè biwo, pòs sou CS50 Diskite sou oswa tankou an, ki aktyèlman jwenn debloke. Se konsa, kenbe sa nan tèt ou. Koumanse pi bonè ke posib se bagay ki pi bon ou ka fè. Se konsa, isit la nan kote nou te kòmanse klas la, plis pase nan semèn zewo. Epi yo ka nou jwenn yon volontè isit la ede m 'jwenn mikro? OK. Kanpe deja. Vini non sou yo. Devine sa a, se li montre kouman li k ap pase nan travay. Ki sa ki nan non ou? ALAN ESTRADA: Alan Estrada. DAVID J. Malan: Alan Estrada. Vini non sou yo. Nice al kontre ou. ALAN ESTRADA: Nice al kontre ou. DAVID J. Malan: Epi ou te isit la avèk nou nan semèn zewo, nan kou. ALAN ESTRADA: Mwen te. Mwen te. DAVID J. Malan: Se konsa, te kapab ou ale pi devan epi jwenn pou nou Mike Smith, osi vit ke ou kapab? Osi vit ke ou kapab. Literalman chire pwoblèm nan nan mwatye jan ou bezwen. ALAN ESTRADA: Sou. DAVID J. Malan: Literalman chire pwoblèm nan nan mwatye. ALAN ESTRADA: Oh. Mm. Trè byen. DAVID J. Malan: OK. Bon. Mèsi poutèt ou. ALAN ESTRADA: Trè bon. OK. DAVID J. Malan: Se konsa, kounye a, ou te amenwize li desann nan mwatye gwosè a nan pwoblèm nan. Koulye a, nou ap desann nan yon trimès. Èske ou peye atansyon sou ki bò nou ap kenbe? [Ri] ALAN ESTRADA: Wi, mwen panse DAVID J. Malan: Ki sa ki seksyon yo se nou nan? ALAN ESTRADA: Ne, se konsa. DAVID J. Malan: OK. Men, Mike Smith ki pral yo dwe apre Ne. So-- [Ri] Tout dwa. ALAN ESTRADA: Kote nou kap? DAVID J. Malan: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. Malan: Koulye a, nou ap nan chirijikal. Koulye a, doktè. Now-- ALAN ESTRADA: Let's- kite nan ale ak reyèl. Reyèl. DAVID J. Malan: Imobilye. OK. Si ou bezwen Imobilye. Koulye a, ki fason se Mike Smith? ALAN ESTRADA: Fason sa a. DAVID J. Malan: Ki fason? ALAN ESTRADA: Rete tann. M is-- dwa? Nou te kòmanse with-- DAVID J. Malan: Yeah. Yo ap kite. Dwat ou. ALAN ESTRADA: Yeah. DAVID J. Malan: Se konsa, Mike a nan isit la. ALAN ESTRADA: Ki sa? [Ri] Move egzanp, guys. Regrèt. DAVID J. Malan: Sa a pral moutre ou kwasans soti nan chèz ou yo. ALAN ESTRADA: Oh. Oh. Mwen te resevwa ou. Mwen te resevwa ou. Oh. Oh. Sa a is-- OK, mwen te resevwa ou. Smith dwa isit la? DAVID J. Malan: Smith, di ou mèsi. Se konsa, mwen pral kenbe leve je l 'Smith? ALAN ESTRADA: Oh, yeah. Pa gen, pa gen, pa gen. Oh, pa gen okenn. Sa a se mwen yo ye. DAVID J. Malan: Oh, ou te resevwa Smith. OK. ALAN ESTRADA: Yeah, mwen te resevwa Smith dwa isit la. Padon, guys. Mwen te panse nou Michael-- te kap chèche Mikayèl la. Regrèt. DAVID J. Malan: Se OK. Tout dwa, kounye a nou ap nan Paccini ak pitit gason. ALAN ESTRADA: Paccini ak pitit gason. DAVID J. Malan: Se sèlman ou ak mwen se nan sou sa. OK. Jwenn nou Mike Smith. Smith. ALAN ESTRADA: Smith. DAVID J. Malan: Smith. Nou ap nan R pou fatra. ALAN ESTRADA: Fatra. Oh. Sa a se pral pran yon ti tan. [Ri] DAVID J. Malan: Soulye. Nou ap nan soulye. ALAN ESTRADA: Koulye a, nou ap gonna-- DAVID J. Malan: Nice. ALAN ESTRADA: Which-- [Ri] Oh, sa a se gwo. [Ri] DAVID J. Malan: Se OK. ALAN ESTRADA: Oh, sa a se yon bon bagay. Mwen pa panse mwen pral gen ami PSAT apre sa a. DAVID J. Malan: Bon. Atik. ALAN ESTRADA: Atik. Sou, L, M, N, O, P. DAVID J. Malan: OK. Se konsa nou chire sa a nan mwatye. Li nan OK. Sa a fini mal de tout fason, paske Mike Smith pa pral nan paj sa yo jòn. ALAN ESTRADA: Aw. DAVID J. Malan: Se pa, li la OK. Men, kite a pretann tankou li se sou paj sa a. Se konsa, kounye, ou te amenwize pwoblèm nan desann nan yon sèl paj, epi nou te jwenn Mike Smith. [Bat bwavo] OK, di ou mèsi. OK. Sa ki te ekstraòdinè. Men, li te toujou pi vit pase rechèch lineyè, kote nou kòmanse nan la kòmanse nan liv la, epi nou deplase wout nou de gòch a dwat, evantyèlman kap chèche Mike Smith. Se konsa, si liv la telefòn te gen petèt 1,000 paj, petèt li ta yo te pran nou 10 oswa konsa dlo nan je paj. Men, ou ka te exploitées manyen yon sipozisyon pandan tout de sa, sa vle di ke liv la telefòn nan avanse te ki sa? ODYANS: Ranje. DAVID J. Malan: Li nan Ranje. Dwa? Li nan Ranje par, se konsa Tout moun nan nan tout sa yo non ak nimewo yo ranje soti nan la a Yon nan la Z a, ak par nan ant. Men, jodi a, kounye a nou mande kesyon an, byen, ki jan te fè Verizon oswa telefòn lan konpayi jwenn li nan eta sa a? Paske li nan yon sèl bagay yo ogmante ki sipozisyon, se poutèt sa, rezoud yon pwoblèm ak yon algorithm pi plis efikasite. Men, nou pa janm reyèlman mande nan semèn zewo, byen, konbyen lajan te fè li pri Verizon oswa yon lòt moun yo ka resevwa ke liv telefòn nan Ranje lòd? Dwa? Li pa enpòtan si leve je l 'Mike Smith se super vit, si li pran ou yon ane a sòt paj sa yo okòmansman. Dwa? Ou ta ka kòm byen jis vannen atravè yon liv telefòn owaza, si li k ap pase yo dwe super chè yo sòt li. Se konsa, si nou ka gen yon lòt volontè. Ann pran yon gade moute isit la nan ki jan nou might-- vin sou leve- Ki jan nou ta ka ale sou klasman sa yo. Men, si lòt bò larivyè Jouden te kapab aktyèlman rantre nan nou moute isit la sou sèn. Vini non sou moute pou jis yon moman. Ki sa ki nan non ou? CAROLINE: Caroline. DAVID J. Malan: Caroline, vin sou yo. Men, ou pral gen pou jwenn pa m 'ak lòt bò larivyè Jouden isit la. Caroline, di ou mèsi. Tout dwa. Se konsa, sa nou gen isit la pou Caroline se 26 liv ble ki FAS sèvi ak yo administre sèten egzamen final la. Sa yo ap resevwa difisil jwenn, men ki sa nou te fè nan avanse se ke nou te mete non yon moun nan sou devan an nan chak nan sa yo, men nou te kenbe li senp pa Lè sa a, mete deyò non plen. Se konsa, nou ta ka mete moun nan ak non an L, D, J, B, tout wout la nan Yon Z, men yo ap nan lòd o aza. Se konsa, si ou ta, ou pale chemen pou rive nan pwoblèm nan menm jan ou li, èske ou kapab ale pi devan epi sòt sa yo pou nou, soti nan A jiska Z. ODYANS: OK, se konsa L se tankou, mitan yo. C se kòmansman. B. J anvan L. B, K. DAVID J. Malan: Kenbe ki te panse pou yon dezyèm fwa. Paske otreman, sa a se sèlman enteresan nou la a, m ', epi lòt bò larivyè Jouden. Gen nou ale. ODYANS: [fèbl]. R. DAVID J. Malan: OK. Kisa wap fe la? CAROLINE: M vin apre O. DAVID J. Malan: OK. CAROLINE: O. DAVID J. Malan: O, Bon. CAROLINE: E. DAVID J. Malan: E, F. Yeah. CAROLINE: T, U, V. DAVID J. Malan: V, T, U, V. Se konsa, li sanble tankou w ap making-- kenbe prale. Li sanble ke ou ap fè yon gwo pil sou isit la, ak kalite yon gwo pil sou la. Se konsa, pwemye mwatye nan alfabè a, dezyèm mwatye nan alfabè a. OK. Bon. Kalite divize pwoblèm lan nan de. M, N, X. Yeah. CAROLINE: K. DAVID J. Malan: OK. K. Se konsa, ou ap kalite chwazi yo youn apre lòt, mete l 'swa bò gòch oswa dwa, oswa Z k ap pase sou etaj la. OK. CAROLINE: Z k ap pase sou etaj la. DAVID J. Malan: OK. Y k ap pase etaj la. Koulye a, nou ka mete X. CAROLINE: G. DAVID J. Malan: G k ap pase kite. S ki pral dwat. Tout dwa, Yon ki pral tout wout la kite. CAROLINE: A, B, C, D. DAVID J. Malan: Koulye a, bon. Nou te gen A, B, C. W a pral desann la. Tout dwa, T. CAROLINE: H, I, J. DAVID J. Malan: H, I, J. Bon. CAROLINE: Nan sant la, mwen gonna-- DAVID J. Malan: OK. Se konsa, kounye a, nou ap ale nan kalite a rantre pil sa yo divès kalite. Se konsa, A jiska C, Lè sa a, mwen wè D, ak E, ak F, ak G, ak H, ak I. Nice. J, K. Apre sa, lè sa a, sa a se pil tèt anba, men sa a OK. Asire w. Nou ka koupe kèk kwen. OK. Lè sa a, nou bezwen W, X, Y, Z. CAROLINE: Yeah. DAVID J. Malan: Excellent. Se konsa, yon gwo mèsi ou nan Caroline pou klasman sa yo. [Bat bwavo] Mèsi poutèt ou. Mèsi anpil. Se konsa, kounye a kite a konsidere pou yon moman ki jan Caroline t'ap mache nan fè sa, ak ki sa egzakteman nou yo te kapab to-- ki jan nou yo te kapab rezoud ki pwoblèm lè nou te jis bay yon pakèt antye nan entrain o aza. Oke, li sanble gen te yon ti jan nan yon sistèm la? Dwa. Se konsa, lèt yo pi bonè nan alfabè a, li te mete sou bò goch la, ak nan lèt pita nan alfabè a, li te mete nan bò dwat la. Apre sa, le pli vit ke li te jwenn kèk lèt ​​amon, yo menm ki ale dwa pwochen nan chak lòt, li ta mete moun ki nan lòd. Se konsa, nou te gen kalite sa yo ti nan entrain Ranje ki fèt pil. Se konsa, sa a, se byen tankou sa pi fò nan nou moun ta fè. Nou ta sòt de pase atravè li, epi nou ta kalite gen yon mekanis. Men, li ta kapab difisil yo ekri li desann nan yon fòmil se pou chak. Li te santi yon ti kras plis òganik pase sa. Se konsa, kite a wè si nou kapab kounye a mare pwoblèm nan ki gen mwens entrain. Olye pou yo 26, se pou yo fè yon bagay lwen mwens ak jis di, sèt, dèyè pòt sa yo, se konsa pale. Èske gen jis sèt nimewo? Men, si objektif la kounye a nan men se jwenn yon valè, kite a wè ki jan avèk efikasite nou ka ale sou fè sa a. Li kite yo wè si nou kapab kounye a kòmanse aplike kèk nimewo, oswa kèk fòmil ak ki dekri efikasite nan liv telefòn nou an algorithm, algorithm liv egzamen nou an, epi plis jeneralman, jwenn enfòmasyon. Se konsa, pou sa a, kite m 'ale pi devan, ak sou ekran an touche sou isit la, mete yon navigatè entènèt ki gen egzakteman sèt pòt sa yo. Men, si nou te ka jwenn yon lòt sèvi kòm volontè yo vini sou sou isit la, Mwen te mete pòt sa yo menm sou isit la. Quick kòm volontè. Sa a Demonstrasyon yonn-yo ale nan yon pi vit ak pi vit kounye a. Vini non sou desann. Ki sa ki nan non ou? TREVOR: Trevor. DAVID J. Malan: Trevor? Tout dwa, Trevor, vin sou desann. Se konsa, Trevor te travay kòm volontè la a yo fè yon pwoblèm ki similè yo, men se yon sèl sa a, se pi etwat nan sijè ki abòde, e ke k ap pase yo ki pèmèt nou pou yo eseye formalizra kounye a pwosesis la pou klasman nimewo sa yo. Se konsa, Trevor, bèl al kontre ou. Se konsa, isit la se yon etalaj, se konsa yo pale, yon lis ki gen sèt pòt yo. Ale pi devan epi jwenn nou nimewo a 50. Lè sa a, apre reyalite a, di nou ki jan ou te jwenn li. Ta dwe be-- tout dwa. Yeah, sa a se youn nan isit la? Uh-oh. OK. Ou klike ke youn. Bon. Epi li bon. Koulye a, ou klike ke youn. Se pou m 'ba ou mikwofòn la, se konsa ke ou genyen li nan jis yon moman. Ale pi devan, epi klike nan pòt pwochen ke ou gen entansyon. Wi, bon. TREVOR: Èske mwen ka unclick yon pòt? DAVID J. Malan: Non, ou pa ka unclick. TREVOR: OK. Yon sèl sa a. DAVID J. Malan: Ki kote ou vle ale? Ki youn? TREVOR: Sa yon sèl. DAVID J. Malan: No TREVOR: OK. Yon sèl sa a. DAVID J. Malan: Wi. Sa ki te bon. Tout dwa. Se konsa, sa ki te algorithm ou a oswa pwosedi pou fè sa, Trevor? TREVOR: Mwen jis mache ale nan tout pòt jouk tan mwen te jwenn yon 50. DAVID J. Malan: OK. Excellent algorithm. Se konsa, sa a, se amann. Paske an reyalite, si mwen revele sa ki nan dèyè sa yo de lòt pòt, ki sa nou pral jwenn isit la se ke nou gen sèlman opinyon o aza. Se konsa, ki te aktyèlman kòm bon jan ou ta ka pran. Ak an reyalite, ou te resevwa pi bon pase limitativ chèche etalaj la antye, paske li ta gen reyèlman malheureux si ou te frape nimewo a 50 a trè dènye pòt la. Men, sa ki si nou olye pou te ban nou yon sipozisyon. Sipoze mwen sòt tout nan sa yo pòt alantou li, pou ke ou gen nan nimewo Ranje tan sa a, men fwa sa a li la aktyèlman yon different-- tan sa a, li la aktyèlman Ranje pou ou. Epi, koulye a objektif la nan men se frape nimewo a 50. TREVOR: OK. DAVID J. Malan: Ki sa ki nan algorithm ou pral fè? TREVOR: Bon, si li nan Ranje, li nan swa ale be-- si pi gwo nan pi gwo, desann, li pral fè yon sèl la an premye, oswa si li nan opoze a, li pral fè yon sèl ki sot pase a. Se konsa, mwen pral jis tape pòt sa a, epi Lè sa a, jis tape dènye pòt la. DAVID J. Malan: Excellent. Tout dwa. Se konsa, nou te jwenn nimewo a 50. Se konsa, le pli vit ke ou te konnen yo te Ranje, nou yo te kapab ogmante sipozisyon sa a. Se konsa, yo ap twò anpil tankou egzanp lan liv telefòn. Le pli vit ke ou gen, menm avèk yon ti pwoblèm tankou sa a, entrain ou Ranje pre-, nou ka aktyèlman jwenn valè a joui pi plis efikasite. Apre sa, mwen pa t 'di ou si li te Ranje ti gwo, oswa gwo yo piti, e konsa li te trè rezonab yo kòmanse nan youn nan kwen oswa lòt la ki aktyèlman jwenn ke valè sib. Se konsa, mèsi Trevor kòm byen. Apre sa, mwen pral propose-- joliman fè. Nou gen yon ti kras clip, aktyèlman, ki se nan mitan moman pi renmen nou an nan CS50, kijan pafwa Demonstrasyon sa yo pa byen ale selon plan. Ak tout bon kounye a, mwen rale moute koòdone nan sa ki mal ak ki yo sèvi ak ekran an touche. Se konsa, sa ki te fòt mwen la. Se konsa, sa a pral fè pou clip ane pwochèn la kòm poukisa mwen te klike sou ekran m 'pwòp. Men, kite a pran yon gade rapid a sa ki te pase ane pase a ak Jay, ki moun ki te vini, anpil tankou Trevor isit la, volontè, ak nan sa a kout clip, ou ap wè ki jan Demo sa a menm pa t 'byen revele menm leson yo aprann. [VIDEO lèktur] -Tout Mwen vle nou fè kounye a se jwenn pou m ', ak pou nou, reyèlman, nimewo a 50 yon sèl etap nan yon tan. -La Nimewo 50? -La Nimewo 50. Epi ou ka fè ou konnen sa ki nan dèyè chak nan sa yo pòt tou senpleman pa manyen l 'ak yon dwèt li. Modi li. [Ri] [END lèktur] DAVID J. Malan: Se konsa, ki te trè byen. Moun sa yo ki te pòt ki klase. Apre sa, Jay, nan kou, jwenn li tout twò byen vit. Trevor te fè yon pi bon travay an tèm de yon moman skolarizabl, se konsa pale, ane sa a nan pran plis tan yo jwenn li ankò. Natirèlman, lè sa a nou te bay Jay yon chans dezyèm, kijan nou Ranje pòt yo, menm jan nou te fè sa pou Trevor, ak Trevor te fè super byen tan sa a. Men, Jay te fè li kòm byen vit mwatye. [VIDEO lèktur] Objektif -La kounye a se tou jwenn nou nimewo a 50, men fè li algorithmically, ak di nou ki jan w ap ale sou li. -OK. -epi Si ou jwenn li, ou kenbe fim nan. Si ou pa jwenn li, ou ba li tounen. -Man. -Oh! - [Fèbl] OK. Se konsa, mwen pral tcheke pwent yo premye detèmine si there's-- Oh. [Aplodisman] [END lèktur] DAVID J. Malan: OK. Se konsa, Fouye pòt klèman mennen nan pi gwo efikasite. Se konsa, de fwa osi vit se sa m 'vle di la. Se konsa, Jay gen chans tou de fwa. Apre sa, li tou te gen chans nan ke dènye ane, mwen te pase lòd kèk disk Blu-ray ki aktyèlman bay soti. Mwen regrèt ane sa a, nou pa t 'gen menm bagay la, Trevor. Men, pi bon toujou te yon kèk ane tounen. Se konsa, kèk nan ou ta ka konnen sa a parèy, Sean, ki moun ki lè li te nan CS50, te defye ak egzak la menm pwoblèm, kwake nan SD, jan ou pral byento wè, tounen nan jounen an. Apre sa, w ap jwenn ki pa sèlman te fè li pran yon ti tan ankò pase Jay, yon ti kras pi lontan pase Trevor, li te aktyèlman opòtinite sa a bèl bagay angaje prèske tout moun nan nan foul moun yon pri la ki dwat, ankouraje l 'jwenn nimewo a nou te chèche. Se pou yo. pran yon gade rapid. [VIDEO lèktur] -OK. Se konsa, travay ou isit la, Sean, se sa ki annapre yo. Mwen te kache dèyè sa yo pòt nimewo a sèt. Men, rantre lwen nan kèk nan sa yo pòt osi byen lòt nimewo negatif. Ak objektif ou se yo panse nan tèt ranje sa a nan nimewo kòm jis yon etalaj, oswa jis sekans nan moso papye ak nimewo dèyè yo. Ak objektif ou se, se sèlman lè l sèvi avèk tèt la etalaj isit la, jwenn mwen nimewo a sèt. Epi nou yo Lè sa a ale nan kritike ki jan ou ale sou fè li. -Tout Dwa. -Jwenn nou nimewo a sèt, tanpri. No Senk, 19, 13. [Ri] Li pa yon kesyon Trick. Yon. [Ri] Nan pwen sa a, nòt ou a pa trè bon, se konsa ou ta ka kòm byen kenbe prale. Twa. [Ri] Ale sou. Franchman, mwen pa ka ede men mande ki sa w ap menm panse osijè de, so-- [Ri] Se sèlman tèt ranje a, se konsa ou te gen twa kite. Se konsa, jwenn mwen sèt. [Ri] 17. Sèt. [Aplodisman] Tout dwa. [END lèktur] DAVID J. Malan: Se konsa, nou te kapab gade sa yo tout lajounen. Ak nan kou, kèk nan Demonstrasyon ane sa a petèt pral kounye a fini nan pwochen videyo ane a kòm byen. Se konsa, kounye a kite a aktyèlman konsantre sou algoritm yo isit la, ak wè si nou pa kapab kounye a kòmanse formalizra ki jan nou ka ale sou kesyon pran done nou an nan eta sa a ke li nan klase, se konsa ke finalman, nou ka aktyèlman rechèch li pi plis efikasite. E menm si nou ap ale yo sèvi ak aparèy televisyon HD done san patipri piti, tankou nou nan uit nimewo gen isit la sou tablo a, finalman ide sa yo menm te kapab aplike a 1,000 entrain, yon milyon entrain, 4 milya de dola entrain, paske algoritm yo yo pral yo dwe fondamantalman menm bagay la. Se konsa, sa a se dènye nou an opòtinite pou volontè jodi a, men petèt youn nan pi patisipe, pou ki nou bezwen uit volontè vini ak mache a nan nou pwosesis pou Fouye ki sa ki pral byento gen sou sa yo mizik kanpe isit la. Kite m 'kòmanse tounen isit la. Se konsa, yon sèl nan vèt la turquoise-- sa li ye? Èske ou komèt? De. Vini non sou desann. OK. Twa. Kat. Se pou mele l OK, senk. Ou se ke yo te nominasyon pa zanmi ou yo. Sis, sèt, ak wit. Vini non sou yo. Tout dwa. Mèsi anpil. Vini non sou yo. Vini non sou yo. Tout dwa. Se konsa, sa nou gen isit lan-- ak sa a se nan mitan yo menm ki plis gòch, depi sa a yo pral mande pou ke ou imè m 'pou jis yon ti jan nan tan. W'a dwe nimewo yon sèl. Ki sa ki nan non ou? Annan: Annan. DAVID J. Malan: Annan. David. Ki sa ki nan non ou? JOSEPH: Jozèf yo. DAVID J. Malan: Jozèf, ou se nimewo de. SERENA: Serena, nimewo twa. Stefan, nimewo kat. CYNTHIA: Cynthia. DAVID J. Malan: Cynthia, nimewo senk. [Fèbl] DAVID J. Malan: [fèbl]. David, nimewo sis. MATT: Mat. DAVID J. Malan: Nimewo Matt la sèt. Apre sa,? WAVERLY: Waverly. DAVID J. Malan: Waverly, nimewo uit. Tout dwa. Si ou could-- whoops. Si ou tout, tankou ou premye defi, gen se uit pozisyon mizik isit la fè fas a odyans la. Si ou te kapab mete nimewo ou sou sa yo mizik kanpe nan yon fason yo ke yo liy moute ak nan nimewo menm sou tablo a. Se konsa, fè tèt nou gade tankou ke pa mete nimewo ou sou sa yo mizik kanpe isit la. Excellent byen lwen tèlman. Ekselan. OK. Se konsa, kounye a, nou ap ale nan mande a kesyon nan yon kèk fason diferan. Ki jan nou ka ale sou Fouye sa yo jan moute isit la? Paske nou te gen yon apwòch kèk pi bonè, annakò ak sa nou te kalite fè de bokit diferan. Lè sa a, nou tout nou te jeneralman piecing bagay ansanm. Le pli vit ke nou te wè de nonb sa ki ansanm, nou mete yo ansanm. De lèt ki apatni yo ansanm. Men, kite a wè si nou pa ka formalizra sa a, pou nou finalman gen kèk pseudo-Kòd ou pral, ak kote ou ka rezoud pwoblèm sa yo. Se konsa, kounye a, M 'ap chache soti a nimewo sa yo isit la. Apre sa, mwen wè yon pakèt antye nan erè. Alafen, mwen vle yon sèl sou la kite la ak uit sou bò dwat la. Se konsa, mwen ap gade sa yo de, kat ak de. Ak sa ki nan pwoblèm nan, evidamman? Yeah. So. De evidamman vini anvan kat, kidonk, ou konnen ki sa? Kite m 'premye pran yon apwòch visye, si ou vle, anpil tankou pwoblèm mete yonn-si ou sonje soti nan la Creole Edition a pwoblèm Mete Youn, kote mwen jis lokalman rezoud pwoblèm nan sa a, se dwa isit la nan devan m ' epi wè ki kote li mennen m '. OK. Se konsa, de ak kat, kite m 'ale pi devan epi jis swap ou de. Si ou kapab deplase fizikman nou ak papye ou, Mwen sanble yo gen vinn nan lis nan yon eta pi byen. Koulye a, yo ap bon. Mwen pral pou avanse pou pi sou li a, kat ak sis, sanble bon. Pa yon pwoblèm. Sis ak uit, OK. Uit ak yon, yon lòt pwoblèm. Paske sa ki nan vre sou uit ak youn? Youn vini anvan uit, ak pou ki sa nou dwe fè? Se pou nou boukante sa yo de. Youn ak uit. Epi, koulye a, mwen pral kenbe prale. Mwen pral kenbe kap vini yo. Li kite yo wè sa ki rive. Uit ak twa, nan kou, parèt nan lòd. Se pou swap la. Uit ak sèt, nan kou. Soti nan lòd. Se pou swap la. Uit ak senk, nan kou, se pou yo swap. Tout dwa. Se lis Ranje. repons lan se wi? OK, evidamman pa. Men, li se yon ti kras pi byen, dwa? Paske avi sa ki te pase. Chak fwa nou fè yon swap, yon pi piti Nimewo kalite percolated fason sa a, ak yon nimewo pi gwo percolated fason sa a, oswa nou pral kòmanse li di bul nan la gòch la oswa bul a dwat la. Koulye a, li la pa ase, paske nan pi bon yon PO ta ka yo te deplase yon sèl plas pou pi devan, oswa nan pi move, yon PO ta ka gen demenaje ale rete yon sèl plas pi lwen. Se konsa, ou konnen ki sa, sa a kalite a te travay trè byen byen lwen tèlman. Kite m 'jis eseye l' ankò. De ak kat, yo ap OK. Kat ak sis, yo ap OK. Sis ak youn, soti nan lòd. Se konsa nou boukante ou de. Epi, koulye a, remake pwoblèm nan nan kòmanse yo ka resevwa yon ti kras pi byen ankò. Sis ak twa, soti nan lòd. Se pou nou boukante ou de. Sis ak sèt, w ap bon. Sèt ak senk, nan kou, soti nan lòd. Sèt ak wit, yo nan lòd. Epi, koulye a, mwen ta ka bezwen fè sa yon tijan plis fwa. Lè an reyalite, panse pou nou petèt konbyen fwa omaksimòm ta ka mwen gen nan mache dèyè, yo soti? Nou pral tounen vin jwenn sa. Se konsa, de ak kat yo toujou OK. Kat ak yon sèl, Nope. Se konsa, kite swap la. Epi ankò, avi vizyèlman se yon sèl kalite ebulisyon sou bò goch la, kote li ta dwe. Kat ak twa swap. Kat ak sis. Sis ak senk swap. Sis ak sèt. Sèt ak wit yo se bon. Bon. Nou ap vin menm pi bon. Se konsa, kite a wè. Koulye a, nou gen de ak yon sèl. Natirèlman, swap. De ak twa, twa ak kat, kat ak senk, sis ak sèt, sèt ak wit. Bon. Epi ou konnen ki sa? Paske mwen te fè yon chanjman a, kite m 'fè yon sèl chèk saniti. Kite m 'ale tout wout la tounen nan konmansman an. OK. Youn, two-- wi, gade? Yon bagay te mal. Twa, kat, senk, sis, sèt, uit. Ak nan sa a devan dènye a, se ou konfòtab ak mwen kounye a reklame li se Klase? OK. Vizyèlman, sa a, se absoliman vre. Men, fonksyonèl, ki sa t 'tou jis rive nan ki pas dènye ki pèmèt ou nan konfime ke lis sa a se tout bon Ranje? Ki sa m 'fè oswa ou pa fè sa pas sot pase a? ODYANS: Pa te gen okenn chanjman. DAVID J. Malan: Padon? ODYANS: Se pa chanjman. DAVID J. Malan: Pa te gen okenn chanjman. Se konsa, li ta dwe estipid nan m ' fè sa algorithm menm ankò si mwen pa t 'fè okenn chanje premye fwa. Apre sa, eta a pa te chanje. Se vre wi, mwen pa pwal fè nenpòt chanjman dezyèm fwa. Se konsa, li nan san danje kounye a yo di, lis se Klase. Ak tout bon, sa a se kounye a yon bagay ki nou pral jeneralman rele sòt jarèt, annakò ak sa pèr, ou korije erè ankò, e ankò, epi ankò, epi ou kenbe prale retounen ak lide, ak dèyè, yo soti, jiskaske ou pa fè okenn echanj sa yo, nan ki pwen ou ka gen konfyans, yeah, mwen fini ranje tout nan erè sa yo. Se pou yo Reyajiste epi eseye yon lòt apwòch. Si ou nèg te kapab ale tounen nan lòd la ou te yon ti moman de sa, ki te sanble ak sa a. Koulye a, kite a pran yon apwòch yon ti kras pi plis tankou liv la egzamen, kijan nou te toujou ap chwazi lèt la nan alfabè a ke nou te vle kalite fè fas ak kap vini an. Petèt li te yon lèt segondè, tankou A, oswa yon Z. lèt ba Se konsa, tout moun nan tounen nan lòd sa a. Epi, koulye a kite m 'fè sa. Ann wè mwen konnen mwen gen uit nimewo isit la. Mwen pral ale pi devan epi jis fè espre chwazi pi piti eleman yo. Dwa? Sa a sanble entwisyon tou. Poukisa nou pa mwen jwenn pi piti a eleman, mete l 'kote li fè pati, lè sa a jwenn pwochen eleman ki pi piti a, mete li kote li fè pati, ak jis repete. Paske entwitif, ki ta dwe travay tou. Se konsa, kat, sa a, se yon nimewo trè piti. Mwen pral sonje kote sa a se. Rete tann yon minit. De se pi piti. -Kite M 'sonje kote de se, ak bliye sou kat. Nou pral fè fas ak ki pita. Sis, mwen pa enterese. Uit, mwen pa enterese nan. Youn nan se nouvo ti kantite m 'yo. Se konsa, mwen pral sonje kote se yon sèl. Twa, pa enterese. Sèt, pa enterese. Senk, pa enterese. Se konsa, san yo pa tonbe nan sèn nan ane sa a, Mwen pral gen tan pwan nimewo yonn- ak sa ki non ou te ankò? Annan: Annan. DAVID J. Malan: Annan. Men, si ou te kapab rantre nan m 'nan nan konmansman an nan lis la, se pou yo mete ou kote ou ye. Unfortunately-- sa ki nan non ou? STEFAN: Stefan. DAVID J. Malan: Stefan se nan chemen an. Se konsa, anvan Stefan rezoud sa a pwoblèm, ki sa nou dwe fè? Ki sa nou fè ak Stefan? ODYANS: [fèbl]. DAVID J. Malan: OK. Se konsa, nou ta ka fè sa. Nou te kapab sòt de pran Stefan ak li kat, ak jis mete l 'nan yon varyab ak kenbe fèm nan fè li pou kèk kantite tan, kidonk fè plas pou nimewo yon sèl. Epi sa a, pa move. Mwen te kapab sijere, poukisa pa fè sa nou jis mete Stefan isit la? Poukisa sa a ta ka vyole youn nan lide yo nou te kòmanse ap pale de dènye fwa, semèn pase a? Yeah? ODYANS: [fèbl]. DAVID J. Malan: Gen nan pa gen endèks pou li. Si ou panse sa a, tout bon, kòm yon etalaj, sa a se tankou yonn negatif, se konsa gen nan pa gen memwa aktyèlman isit la si sa a se tout bon yon etalaj, tankou nou te deklare semèn pase a nan konferans. Se konsa, nou pa ta dwe fè sa. Nou ka magazen li nan yon varyab. Ou, ou konnen ki sa? Mwen tande yon lòt moun sijere li. Ki lòt bagay nou te ka fè ak Stefan? Poukisa nou pa nou jis degèpi l ', li mete l 'sou kote nimewo yon sèl te ye a. Se konsa, si ou vle ale sou la. Ak tout bon, sa a se yon trè bon solisyon. Koulye a, sou yon bò, Mwen te kalite a te fè pwoblèm nan vin pi mal. Kat se kounye a pi lwen ki soti nan kote li ta dwe. Li ta dwe nan direksyon mwatye sa a. Men, ou konnen ki sa? Sa yo te kapab vin move chans. Petèt nimewo uit te isit la. Se konsa, petèt nou ta gen vinn chans, ak pouse uit pi pre nan fen an. Se konsa, nan fen jounen an, li kalite tout mwayèn deyò. Nou pa bezwen pran swen sou kat. Tout sa mwen pran swen sou kounye a se chwazi eleman ki pi piti a. Epi, koulye a, ki sa mwen pral fè se bliye sou nimewo yon sèl pou tout tan, paske mwen konnen nan Se lis dèyè do m 'kounye a Ranje. Se konsa, lis mwen an te deja gwosè uit. Koulye a, li la nan gwosè sèt. Se konsa, pwoblèm mwen a ap vin ki pi piti, kwake linear. Se konsa, kounye a, mwen pral chwazi nan aktyèl pi piti eleman, de. Sis, uit, kat, twa, sèt, senk. Sa ki te eleman ki pi piti a. Se konsa, sa ou yé pral fè with-- sa non ou te ankò? JOSEPH: Jozèf yo. DAVID J. Malan: Jozèf? Nou pral kite Joseph nan plas li. Koulye a, mwen pral pretann ki mesye sa yo sont- byen, Mwen konnen ke sa yo de yo deja Ranje. Se pou nou kounye a konsantre sou la rès nan lis la. Sis se pi piti a kounye a. Uit se pi gwo. Kat se kounye a pi piti a kounye a. Twa se kounye a pi piti a kounye a. Se konsa, kounye a, mwen pral chwazi twa, ki is-- sa ki nan non ou ankò? SERENA: Serena. DAVID J. Malan: Serena, si ou te kapab gen tan pwan nimewo ou ak swap with-- KALSANG: Kalsang. DAVID J. Malan: Kalsang. Vini non sou do, epi nou ap ale nan swap sa yo de. Epi, koulye a, se pou yo mete sa a sou pilot. Mwen pral ale epi kite l 'bay ou nèg yo ka chwazi pwochen pi piti eleman yo. Bradstreet, Bradstreet, Bradstreet, Bradstreet. Nimewo kat, ki sa ou ta dwe fè? Ekselan. Koulye a, mwen pral fè yon lòt pas. Bradstreet, Bradstreet, Bradstreet, Bradstreet. Mwen wè senk se pwochen pi piti a. Koulye a, mwen pral pran yon lòt pas. Bradstreet, Bradstreet, Bradstreet, Bradstreet. Sis se pi piti a. Bon. Sèt se pi piti a. Pa gen chanjman. Uit se pi piti a. Fè. Se konsa, sa nou te jis fè pa iterativman chwazi yon sèl eleman apre lòt la se aplike yon bagay ke nou ap ale nan formalizra kòm sòt seleksyon. Lè li nan petèt menm ki pi senp yo eksplike, nan ki literalman tout sa ou vle fè se jis kenbe ale dèyè, yo soti nan lis la chwazi, pwochen eleman ki pi piti a, jiskaske ou ap fè. Se konsa, li menm ki pi senp, petèt entwitif, pase pase. Ann eseye yon dènye yon sèl. Si ou nèg te kapab Reyajiste tèt nou nan pozisyon sa yo youn final tan, kite a wè si nou pa kapab kounye a formalizra yon lòt apwòch. An reyalite, yon moun ta yo deyò renmen pwopoze ki jan lòt bagay nou ta ka ale sou fè sa a? San yo pa yo tap voye soti buzzwords oswa sòt nan repons ki deja li te ye, jis entwitif, sa ki ta nou fè? ODYANS: [fèbl]. DAVID J. Malan: Yeah. Se konsa, gen nan kèk entwisyon gwo a. Bon bagay sanble yo rive konsa byen lwen nan syans òdinatè lè nou divize ak konkeri pwoblèm lan nan divize l 'nan mwatye ak mwatye ak mwatye. Se konsa, tout bon, nou te kapab kòmanse fè sa. Ak an reyalite, ki k ap pase yo dwe, nou pral wè, youn nan pi bon solisyon nou an ankò. Men, kite a tounen nan ki vini anvan lontan. An reyalite, nou ap ale nan fè ki yon ti kras pita semèn sa a. Ki lòt bagay nou ta ka fè yo rezoud sa a? Se konsa, tout moun isit la se nan lòd w pèdi o aza. Ou konnen ki sa? Olye ke ale retounen ak lide, retounen ak lide, retounen ak lide chak fwa, sa a santi l tankou M ap fè yon anpil nan mache. Poukisa nou pa mwen jis kòmanse nan nan konmansman an nan lis la, ak jis mete kat kote li fè pati? Se pou m 'asime pou moman sa a ki lis mwen an se sèlman sa a eleman an premye. Se kat Ranje nan moman sa a nan tan, si tout mwen pran swen sou se tout bagay isit la? Sa a se sòt de trivyalman vre, dwa? Fè tankou lis la ki gen yon sèl nimewo, ak se ke nimewo kat evidamman Ranje. Se konsa, kite m 'jis ladann ki lis sa a Ranje. Men koulye a, mwen gen rès la nan lis sa a. Se konsa, koulye a, mwen rankontre de. Ki kapab de evidamman apatni ki gen rapò ak kat? Anvan kat. Se konsa, sa mwen kapab fè isit la? Ki sa ki nan non ou ankò? JOSEPH: Jozèf yo. DAVID J. Malan: Jozèf, si ou ta ka etap tounen pou jis yon ti moman avèk nimewo ou yo. Epi, koulye a sa ki ta Stefan fè isit la? Se pou yo chanjman Stefan sou isit la. Epi, koulye a, se pou Jozèf vini nan isit la. Epi, koulye a, kite m 'reklamasyon ke tout bagay isit la se Klase. Se konsa, menm jan rezilta, men yon fondamantalman diferan apwòch. Mwen pa gen menm gade sa ki nan desann la. Mwen jis kenbe pran eleman yo menm jan yo ap lage m 'konsa: epi fè fas avèk yo. Se konsa, kounye, mwen wè nimewo sis. Ki kote nimewo sis apatni? Nou gen de, kat, sis. Egzakteman ki kote li se kounye a. Se konsa nou kite ki pou kont li, epi kounye a reklamasyon ke pati sa a nan lis la se kounye a Ranje. Se konsa, sa a santi l fondamantalman diferan nan ke mwen se jis k ap deplase nan lis la isit la linear, ak mwen pa janm double tounen. Wi. Tout dwa. Se konsa, uit, kote ou fè pati? Dwa isit la. Pafè. Se konsa, kounye a, yon sèl. Uh-oh. Sa a santi l tankou li nan pral fè chè. Koulye a, nan algorithm a anvan, Mwen jis échanges moun. Se konsa, mwen ta ka mete l 'tout wout la nan kòmansman an, Lè sa a, demenaje ale rete Jozèf men. Men, si mwen deplase Jozèf, kounye a sa k ap pase yo dwe mal? Koulye a, mwen te sòt de undone-- Mwen te pran yon sèl etap pou pi devan ak Lè sa a yon sèl etap tounen, paske kounye a Jozèf ta dwe parèt nan lòd. Se konsa nou fè sa. Si ou te kapab pran nimewo en ak etap tounen pou jis yon ti moman. Ki jan nou ka put-- sa non ou te ankò? Annan: Annan. DAVID J. Malan: Annan nan plas? Ki sa ki bezwen yo rive ki gen rapò nan de, kat, sis, ak wit? Yo tout bezwen chanjman. Se konsa, si uit ta renmen chanjman premye, Lè sa a, sis, Lè sa a, kat, Lè sa a, de. Lè sa a, Annan, si ou ta renmen vini nan isit la, bon. Men, isit la, nou te jis kalite peye yon pri nan yon pwen diferan nan algorithm nan. Lè nou konsidere ke dènye fwa ak seleksyon sòt, e menm sòt jarèt, M 'ap mache retounen lakay yo epi soti, retounen ak lide, ki se sètènman ajoute moute tan-gen bon konprann, ak literalman pwogresif. Sòt ensèsyon, nan premye gade, sanble li nan super pi entelijan, nan ke mwen se jis fè dousman, pwogrè incrémentielle, men mwen pa pwal sa a retounen ak lide. Men, si yon moun se vre soti nan lòd, avi tout travay la mwen jis te gen nan fè. Mwen te gen pou avanse pou pi mwatye nan lis la jis pou fè plas pou nimewo yon sèl. Se konsa, li menm kantite lajan an nan travay konsa byen lwen li santi l, jis yon kalite diferan nan travay yo. Se pou nou kontinye. Se konsa, kounye a nou konnen ke tout moun ant youn ak uit yo ranje. Isit la, mwen gen nimewo twa. Si ou renmen nan ranmase Nimewo twa, etap tounen yon sèl. Ak sa ki ou nèg bezwen fè? Oui. Se konsa, sa a, se yon lòt yon sèl, de, twa etap. Twa inite nan tan ki jis koute m ', se konsa ke twa kapab kounye a anfòm. Finalman, sèt. Se pou nou ale pi devan epi yo gen ou pran yon tounen etap. Sa a se sèlman pral koute nou yon inite de tan, men sa a OK. Epi, koulye a, senk nan ale nan gen yon ti kras pi plis chè. Si w ta renmen nan etap tounen. Nou bezwen pou avanse pou pi uit, ak sèt, ak sis. Lè sa a, tout moun ap Apre sa, kounye a Ranje. Se konsa, yon gwo men nan volontè nou yo isit la. Mèsi anpil. [Aplodisman] Mèsi poutèt ou tout. Mèsi poutèt ou tout. Se konsa, kite a wè ki jan kounye a jis koute chè nan tout sa te ye a. Se pou nou konsidere petèt nan pi senp nan sa yo, sòt ti wonn. Apre sa, mwen di pi senp, sèlman paske ou ka rezoud li kupidman pa jis ranje pwoblèm nan pèr isit la. Ranje pwoblèm nan pèr isit la, ankò e ankò e ankò, repete kòm anpil fwa tankou ou aktyèlman bezwen. Se konsa, li sanble ke ak yon sòt jarèt, byen, ki jan anpil etap mwen dwe pran sou pas nan premye nan ki algorithm? Mwen ta ka take-- kite nan see-- yon sèl, de, twa, kat, senk, sis, sèt. Apre sa, nan uit eleman isit la. Se konsa, li tankou n mwens 1 etap sa yo jwenn depi nan konmansman an nan lis la nan fen a nan lis la. Men, avèk sòt seleksyon, sonje ke mwen se chwazi eleman yo ankò e ankò e ankò sa a, se pi piti a, M 'ap mete l' nan plas, men Lè sa a mwen pa kap dèyè do m 'ankò. Se konsa, mwen panse ke li nan yon ti kras plis klè Lè sa a, ki premye fwa a, mwen ta ka dwe pran tout n mwens 1 etap jwenn eleman ki pi piti a. Apre sa, mwen mete yo nan isit la, mwen degèpi moun ki va te isit la deja. Men, Lè sa mwen pa gen kenbe gade nan sa a eleman, paske mwen konnen li nan deja pi piti a. Se konsa, koulye a, mwen ka gade nan jis sèt eleman, Lè sa a, sis eleman, Lè sa a, senk eleman, lè sa a kat eleman. Se konsa, matematik, si n se nimewo a nan eleman oswa nimewo ke nou te kòmanse avèk, ou ka imajine ke sa a se menm bagay la kòm n mwens 1, plis n mwens 2 etap, plis n mwens 3 etap, plis n mwens 4 etap yo, tout nan fason desann nan jis yon sèl etap. Apre sa, mwen se sou moun pase mwen. Men, si ou sonje ke yon anpil nan stats liv oswa liv matematik gen sa yo fòmil sou mòn lan Paperback tounen oswa devan yo, li sanble ke seri sa a kapab eksprime plis tou senpleman kòm fwa n n mwens 1 plis pase 2. Lè li nan amann si sa a pa nan forefront de lide ou. Men, sa a se vre vre. Se jis yon fason ki pi senp nan ekri li. Lè sa a, si ou panse tounen nan lekòl la klas, lè ou jis kòmanse miltipliye bagay sa yo soti, sa a nan kou, se jis n okib mwens n divize pa 2. Tout sa mwen te fè se elaji ekspresyon yo a. Se konsa, kite a ekri sa a yon ti kras yon lòt jan. Sa a n okib divize pa 2 moins n / 2. Se konsa, ankò, mwen jis kalite k ap aplike kèk aritmetik règ la. Men, remake kounye a ke tèm nan pi gwo nan ekspresyon sa a, se konsa pale, se ke n okib. Se konsa, repons lan se wi, li la n okib divize pa 2, mwens n / 2. Men, jeneralman, si n se pral fè yon gwo valè, Mwen pral reklamasyon ke n okib a pwal faktè a dominan. Li nan jis pral fè yon kontribitè pi gwo ak kantite etap pase n / 2. Se konsa, sa mwen vle di pa sa a? Ann eseye yon egzanp ki senp, menm menm si matematik la vin yon ti kras gwo. Se konsa, te gen Sipoze nou 1 milyon moun sou sèn, oswa 1 milyon dola bagay sa yo ke nou vle sòt. Se pou nou ploge yon milyon nan egzakteman sa fòmil yo wè ki jan anpil etap li pran manm sòt yon milyon eleman lè l sèvi avèk di, seleksyon sòt. Se konsa, nou ta gen menm fòmil la tankou anvan. Mwen ta ploge yon milyon, se konsa ke mwen jwenn yon milyon okib divize pa 2, mwens yon milyon divize pa 2. Si m 'fè sa matematik nan avanse isit la, nou gen 500 milya dola mwens 500,000, ki ba nou 499.999.500.000, ki se trè reprize gwo. An reyalite, si ou konpare kounye a 499 milya dola, 999 milyon dola, 500,000 kont valè orijinal nou an, 500 milya dola, li la se konsa modi fèmen. Dwa? N okib divize pa 2 bay fi Fiziyad Kous ou pito, n okib divize pa 2 te ban nou 500 milya dola. Sa a trè reprize fèmen 499.999.500.000, sa vle di soustraksyon koupe 500,000, oswa plis jeneralman, soustraksyon koupe n okib, pa reyèlman yon kontra gwo. N a okib fè sa yo nimewo grandi reyèlman vit. Koulye a, sa a se enpòtan sèlman tèl degre jan nou, kòm syantis konpitè, yo jeneralman pa ale nan pran swen anpil sou nuans ki nan fòmil sa yo ak ekzakteman ki sa a repons egzak ye. Nou pran swen sèlman sa, ou konnen ki sa? Nan fen jounen an, sa a fòmil se sou lòd la n okib. Wi, nou ap divize pa 2 nan la. Wi, nou ap soustraksyon koupe n mwens 2. Men, nan fen jounen an, tèm nan ki vrèman fè m mal nou epi koute nou yon anpil nan etap se ke tèm kare. Se konsa, sa ki yon syantis òdinatè ki pral jeneralman fè se inyore tout moun sa yo pi piti lòd tèm, ak jis gade nan yon sèl la ki kontribye pi plis nan yo ka koute an. Lè sa a se bèl, paske nou kapab kounye a pale nan pi plis générales sou algoritm, e yo ka konpare yo. Ak lefèt ke mwen se lè l sèvi avèk sa a O se ekspre. Lè m 'di sou lòd la a, mwen se espesyalman refere li a yon bagay rele gwo O. Lè gwo O se yon notasyon ki yon òdinatè syantis sèvi ak a dekri yon anwo mare sou yon bagay. Se konsa, si ou di ke yon algorithm se nan gwo O nan n okib, jan mwen pwopoze jis yon ti moman de sa, ki vle di ke an tèm de kouri li yo tan oswa efikasite li yo, li pran sou lòd la nan n okib etap. Petèt plis, petèt mwens. Men, li la sou lòd nan n okib. Epi sa a, mare nan anwo kay la. Li pa nan pral yo dwe plis ki fè mal pase sa. Li pa nan pral yo dwe n Gleason, oswa 2 n nan, oswa yon bagay pi gwo anpil. Sa a se yon anwo mare sou tou sa ki koute se. Se konsa, bay sa, se pou yo konsidere jis yon kèk egzanp. Lè sa a se jis yon lis fini tan ki gen trè komen kouri pou algoritm ki nan vle di yo dwe ilistrasyon nan kèk bagay nou te wè deja. Se konsa, pou egzanp, nan ka a nan sòt seleksyon, sa m ap reklame isit la ap kouri ki sòt seleksyon an tan se sou lòd la n okib. Nan ka ki pi mal la, mwen pral gen yon pakèt antye nan nimewo o aza isit la. Ak jan nou te wè matematik, si mwen kenbe mache nan lis la, nan la lis, chwazi pwochen an pi piti eleman ankò e ankò, si mwen aktyèlman ekri desann tout nan etap sa yo M 'ap pran jan mwen pwopoze formulaically anvan, li nan sou lòd la n okib etap ke mwen pran. Apre sa, li vire soti ke ti wonn sòt ak sòt ensèsyon yo se jis kòm dousman nan ka ki pi mal. Konsidere, pou egzanp, sòt ensèsyon, algorithm nan trè dènye nou te fè fas ak, ki te gen nou gade nan eleman an, ak Lè sa a insert l kote li ki dwe. Lè sa a, nou te gade eleman kap vini an, ak eleman li kote li fè pati. Se konsa, konsidere senaryo a pi byen posib. Sipoze mwen te volontè mwen liy moute literalman tankou sa a, yon sèl nan uit, deja klase. Konbyen etap se sòt ensèsyon pral pran yo sòt uit moun, si yo rive sou sèn kap tankou sa a? Uit moun ki deja klase. Apre sa, mwen sèvi ak sòt ensèsyon. Sa sot pase yo nan algoritm yo. Oke, kite la re-jwe reyèl vit. Se konsa, si mwen kòmanse isit la, mwen wè yon sèl. Ki kote yon sèl pati? Li fè pati isit la menm. Mwen wè de. Kote de apatni? Dwa isit la. Mwen wè twa. Ki kote twa apatni? Dwa isit la. Mwen wè kat. Dwa isit la. Senk, sis, sèt, uit. Gen nan pa gen rezon ki fè nou repete tèt mwen. Se konsa, ki jan anpil etap se ke an tèm de n? Li nan sou lòd la nan n etap, dwa? n mwens 1. Men, mwen te pran yon nimewo lineyè nan etap, epi kounye a mwen se fè. Se konsa, sa a, se ka ki pi bon, menm si. Ki sa ki sou ka ki pi mal? Ki sa ki uit te lòt bò a, ak sèt te desann la, ak youn ak de yo te sou isit la, se konsa ke lis la te se vre wi: ranvèse? Oke, sa k ap pase tout bon si sa a se nimewo a? Epitou, n ap fè sèlman yon koup nan egzanp. E si, tout bon, nimewo a uit se isit la, ak whoops yo number--. Se konsa, sa si, tout bon, nimewo a uit se tout wout la sou isit la, ak mwen lè l sèvi avèk sòt ensèsyon? OK. Mwen reklame nan moman sa a li a nan plas li. Men koulye a,, seven-- kote sèt ale? Natirèlman, li ale sou isit la. Se konsa, mwen gen pou avanse pou uit sou yon sèl kote. Koulye a, sis, kote li ale? Oke, tout dwa. Koulye a, mwen gen pou avanse pou uit sou yon kote, ak sèt sou yon plas, ak Lè sa a mwen plok desann sis. Se konsa, premye fwa a, li pri m 'yon sèl etap yo ranje bagay sa yo, lè sa a li koute m 'de etap yo ranje bagay sa yo. Konbyen etap se li pral pran yo ranje bagay yo mete senk nan plas la dwa? Twa. Paske kounye a mwen gen yo deplase yon sèl, de, twa. Konbyen etap se li pral pran yo mete kat nan plas la dwa? 4 plis 5, plis 6, plis 7. Se konsa, li nan matematik ki idantik ak ki sa nou dekri pou sòt seleksyon. Nou gen seri sa a sa se sèlman ogmante. 1 plis 2 plis 3 plis 4, oswa Kontrèman, 7 plis 6 plis 5 plis 4 ajoute moute pou jodi a rezon a sou lòd la n okib. Se pou m 'ladann tou ki sòt ti wonn se tou nan n okib. Paske ak sòt jarèt, chak fwa mwen ale nan lis la, M 'ap pran apeprè konbyen etap? Chak fwa mwen literalman mache soti nan gen yo genyen? Apeprè N etap. Men, ki jan anpil fwa ta ka mwen bezwen yo ale nan lis la? Oke, apeprè n tan. Petèt n mwens 1, men apeprè n fwa. Oke, poukisa se sa? Oke, ak sòt jarèt, si nou kòmanse ak sòt jarèt, ak lis la nan posib ki pi mal la sitiyasyon, ki ankò se konplètman bak, ki sa ki pwal pase? M 'ale nan lis la, ak nimewo youn ki dwe tout wout la sou la. Men, avèk sòt jarèt, ki jan lwen fè yon sèl deplase sou pas premye fwa mwen nan lis la? Konbyen tach li jwenn pi pre plas la kòrèk? Jis yon sèl. Se konsa, si ou kalite rezon nan sa a, chak fwa nan sa a algorithm, Pran apeprè n etap David. Men, ki jan anpil pase nan lis la se li pral pran pou youn nan ti wonn sou bò goch la kote li fè pati? Li te resevwa pou avanse pou pi tankou, espas N fason sa a. Se konsa, jis fè klasman an nan lis la, Mwen gen nan mache dèyè, yo soti fwa n. Epitou, chak tan, mwen se gade nan n eleman. Se konsa, fè bagay sa yo n fwa n sou lòd la n okib. Koulye a, nou pral wè nan kèk nan bout pantalon yo ki yo entegre nan pwochen pwoblèm CS50 nan mete, yon lòt apwòch nan sa yo, men pou kounye a, se pou yo jis konsidere kèk fwa lòt kouri, espesyalman si yo menm ki klasman pran yon ti kras nan tan yo koule nan. Ki sa ki nan yon algorithm nou te wè deja ki pran sou lòd la nan etap n? Ki sa ki ta dwe pran yon PO lineyè nan etap ki nou te wè konsa byen lwen? Ki sa ki nan sa? Rechèch la anyè telefòn. Algorithm nan premye. Dwa? Ki kote nou ap linear pou chèche Mike Smith? Vreman vre. Soti nan semèn zewo, lè mwen te kòmanse vire yon paj nan yon moman, ak mwen menm te di ke li te kalite nan yon algorithm santi lineyè, epi nou te gen foto ki sou mòn lan tablo ak liy lan tou dwat wouj ak jòn a dwat liy, sa yo te tout bon algoritm ki nan gwo O nan n. Paske yo jwenn Mike Smith nan yon telefòn liv nan paj n, nan ka ki pi mal la, ta ka pran m 'N etap. Ki sa ki sou pran prezans? Youn, de, twa, kat, senk, sis. Ki sa ki nan tan an kouri nan sa a algorithm pou pran prezans? Big O nan n, paske se nan teyori mwen gen nan pwen tout moun nan sal la. Koulye a, kòm yon sou kote, sa ki sou la lòt optimize soti nan semèn zewo? De, kat, sis, uit, 10, 12. Yon syantis òdinatè ta reyalize, rete tann yon minit, sa a, se sou lòd la N divize pa de etap. Dwa? Paske m ap fè de moun nan yon tan. Men, nou ap ale nan inyore moun pi ba tèm lòd, epi nou ap jis ale nan jete divize an pa 2, ak jis di, gwo O nan n pou ki algorithm kòm byen. Ki sa ki sou yon sèl sa a? Nou pral sote sou kèk nan sa yo, men sa ki te yon algorithm ki te boutèy demi lit plen n? Ki te pran apeprè ouvri sesyon etap n? Divize an ak konkeri. Egzakteman. Fè tankou egzanp lan liv telefòn nan semèn zewo ak pi bonè jodi a, kote nou divize pwoblèm lan ankò, li ankò e ankò. Nou te trase l 'sou tablo a nan semèn zewo kòm yon liy koube vèt, epi nou di jou sa a li te yon algorithm logaritmik. Ak tout bon, ki kantite etap li pran yo fè separe ak konkeri, oswa rechèch binè kòm nou pral kòmanse rele li, tankou nan liv la telefòn, se sou lòd la boutèy demi lit ak etap. Lè sa a se yon ti jan nan yon yon sèl etranj. Ki sa ki pran yon sèl etap, oswa plis espesyalman yon PO konstan nan etap? Petèt li nan de, petèt li nan twa, men yon syantis òdinatè jis senplifye li kòm gwo O nan 1, kèk nimewo konstan nan etap. Ki sa ki nan yon bagay ou te kapab fè sa pran yon PO konstan nan etap? Ki sa ki nan tan an kouri nan bat bravo? Constant tan. Dwa? Tankou, sa ki nan tan an kouri nan fè anyen ki pran sèlman yon sèl operasyon an, tankou enprime F Alo Mondyal la. Ke sa ta kapab di ke yo dwe tan konstan, sof si mwens ka kwen ak ekri an lèt detache F, sa ki ka tan an kouri a ekri an lèt detache F aktyèlman ta dwe ye? E poukisa? Ki sa ki se n pou mezire nan ka sa a? ODYANS: [fèbl]. DAVID J. Malan: Egzakteman. Nimewo a nan karaktè nou vle enprime. Se konsa, li trè kontèks-sansib. Jodi a, nou ve yo te konsantre yon anpil sou lèt ak chif isit la sou tablo a. Men, li ta ka tou gen karaktè nan yon fisèl vrè. Se konsa, li vire soti gen nan yon lòt mezi ki pral kòmanse pran swen sou, e ke sa a opoze a nan gwo O, se konsa pale. Sa a notasyon Omega. Lè nou konsidere ke gwo O vle di sa ki nan la, anwo mare sou tan kouri ou a? Omaksimòm, konbyen tan ta ka yon bagay pran? Omega-- regrèt sa a kenbe vini leve- se opoze a nan sa, kijan li nan yon pi ba mare sou mòn lan kantite tan yon bagay ta ka pran. So. pou egzanp, sa ki nan yon algorithm ki pran toujou n okib etap? Oke, youn nan algoritm yo nou te wè jodi a, an reyalite, ta ka ke kòm byen. Seleksyon sòt. Seleksyon sòt a trè estipid. Menm si regrèt nan algorithm, menm si se etalaj la deja klase, sòt seleksyon ki pral kenbe mache nan lis la a asire w li gen pi piti a eleman ankò e ankò e ankò. E menm si ou moun nan nan odyans konnen ke, rete tann yon minit, ou deja pase nan pi piti eleman, òdinatè a pa konnen ke jouk li sanble tout wout la nan lis la. Menm jan tou, yon pi ba mare ki ta ka tou dwe pran an kont ta kapab tan lineyè. Konbyen tan li pran yo eleman sòt n nan pi bon an ka lè l sèvi avèk yon bagay tankou sòt jarèt? Sipoze se lis ou a deja klase. Nou te di sòt jarèt pran sou lòd la n okib etap. Men, sa ki si li nan deja klase? E si ou reyalize apre youn pase nan etalaj la ke ou te fè pa gen okenn echanj? Ou bezwen kenbe fè plis pase? No Se konsa, yon pi ba mare sou sòt jarèt ta ka di ke yo dwe lineyè. Omega nan n. Apre sa, nou ka gade nan lòt moun nan sa yo kòm byen. Se konsa, kite a pran yon gade rapid nan jis yon vizyalizasyon isit la yo wè ki jan sa yo fè distenksyon ant tèt yo. Mwen pral desann ale isit la nan sa a paj sa a, se disponib sou sit entènèt C50 la, men li pral yon doulè yo ka resevwa travay, depi li sèvi ak yon teknoloji rele Applets Java, ki se yon lajman suporte jou sa yo, omwen pa Chrome ak sèten lòt moun. Ak kite m 'ale pi devan epi pi vit sa a leve, li eksplike sa k ap pase sou. Sa a se yon demonstrasyon de ti wonn sòt, algorithm nan premye nou te gade. Lè li nan yon vizyalizasyon nan ke chak nan ba sa yo reprezante yon kantite. Pi gwo a ba a, pi gwo a nimewo a. Ki pi piti nan ba a, ki pi piti a nimewo a. Ak sa ki ou ka wè vizyèlman, menm menm si sa a ki pral super vit, se ke ba a wouj se tankou m ', ap mache dèyè, yo soti repare-pwoblèm. Ou ka wè ke eleman yo pi gwo yo tout bon ebulisyon jiska bò dwat la, ak eleman yo ki pi piti yo ebulisyon jiska bò gòch la. Apre sa, desann isit la, si nou aktyèlman gade plis ak anpil atansyon, nou ka aktyèlman konte nan kantite konparezon ak echanj ki te ke yo te fè fè yo. Men, olye de sa, kite pou yo gade nan dezyèm algorithm nan nou te gade pi bonè ak nou volontè, sòt seleksyon. Vizyon, li gen yon trè diferan efè. Men, li la, ankò, trè entwisyon, nan ke nou kenbe chwazi pwochen an pi piti eleman, epi nou te resevwa yon ti kras chans. Sa te santi fondamantalman pi vit. Men, si nou kouri sa a ankò e ankò e ankò avèk anpil entrain, nou ta renmen wè ke li nan tout bon toujou nan gwo O nan n okib. Se pou yo fè yon dènye yon sèl isit la, sòt ensèsyon, ki te twazyèm algorithm nan nou te gade, ak rapèl ki yon sèl sa a kontra avèk a eleman kòm li rankont yo, men lè sa a li petèt orè bagay nan men fè plas, mete eleman kote yo fè pati. Lè sa a twò fini moute bay la rezilta final la. Koulye a, tout twa nan sa yo te santi trè vit. Ak tout bon, mwen kouri yo Yon trè bon clip. Men, fondamantalman, you tout bèl terib, yo dwe onèt. Tout moun nan algoritm sa yo konsa byen lwen ki kouri nan gwo O nan n okib pran byen yon ti jan nan tan kouri nan fen an. Ak tout bon, nou ka wè epi yo santi sa a anfen si mwen rale moute sa a twazyèm ak dènye Demo. Sa se yon lòt vizyalizasyon ki k ap pase yo montre sòt jarèt sou bò gòch la, sòt seleksyon nan mitan an, ak yon bagay, kòm youn nan nou an men ogmante pi bonè sijere, rantre sòt sou bò dwat la. Yon separe ak konkeri estrateji sou bò dwat la. Epi sa a,, an reyalite, ki sa nou ap ale fè yon gade nan nan Mèkredi. Men, nan kite tan sa yo nan kouri nan paralèl. Li nan apeprè menm kantite eleman yo, tout kouri nan menm tan an. Sòt jarèt vs seleksyon sòt vs sòt unifye. Koulye a, yo ap tout kouri nan teyori nan menm tan an. CPU a se kouri nan vitès la menm, men ou ka santi ki jan raz sa a se trè byen vit ale nan vin, ak jis konbyen vit lè nou enjekte yon ti jan nan semèn algoritm zewo nan ka nou pi vit bagay yo. Epi, koulye a kite a konpare sa yo nan yon dènye fòm. Mwen pral ale pi devan nan sit entènèt CS50 a, kote nou gen sa a lyen final pou jodi a, kote yon moun sou entènèt la dous mete ansanm yon videyo ki kaptire sa diferan klasman algoritm son tankou. Sa a se sòt ensèsyon. [Bip] Kijan w ap aplike yon frekans ki baze sou wotè nan ba a ba. Sa a se sòt ti wonn. [Deformation bip] Vini pwochen is-- vini moute pwochen sòt seleksyon is--, kote ankò, nou ap chwazi pwochen pi piti eleman an, epi nou ka wè li ap grandi de gòch a dwat. Rantre sòt, gayan nou an konsa byen lwen jodi a. Avi sou jan li a divize bagay nan [fèbl] mwatye ak trimès. Luten sòt, nou pa gen te pale osijè de, epi kreye vizyèlman ak audally yon ti jan nan yon diferan fòm ak son. Ale retounen ak lide, netwaye bagay yo. Epitou tcheke deyò heapsort sou sit entènèt sa a Guy a. Epi sa a, li. Nou pral wè ou pwochen fwa. [Whooshing AK MIZIK]