[GIOCO MUSICA] SPEAKER 1: Va bene, questo è CS50, e questo è l'inizio della quarta settimana, e come si può avere sentito o lettura, il mondo è stato per finire. Andando in tutto il Internet è stata la conoscenza e la consapevolezza di un bug in un programma, un linguaggio di programmazione chiamato Bash. Questo è stato meravigliosamente bollato come Shellshock, o la porta Bash, ma articoli come questi non sono stati infrequenti. E infatti, molti di loro portano ricordi indietro di Heartbleed, che avrete notato in premere di nuovo la scorsa primavera, che era ugualmente abbastanza drammatico. Ora, di quelli di voi qui oggi, come molti di voi hanno, anche se non si capisce che cosa è tutta una questione, sentito parlare di Shellshock? Va bene, e come molti di voi avere i computer che sono vulnerabili? OK, ci dovrebbe essere molto, molto più mani fino adesso, per ragioni che vedremo. Diamo uno sguardo a ciò che è accaduto in media e poi spiegare un po ' qui per noi tecnicamente. SPEAKER 2: Gli esperti di sicurezza hanno avvertito che un grave difetto potrebbe essere sul punto di influenzare centinaia di milioni di utenti web di tutto il mondo. Così che cosa è esattamente il bug che è stato doppiato Shellshock, e che cosa fa? Beh, Shellshock è anche conosciuto come il Bash bug, il software sfrutta. Gli hacker utilizzano il virus per la scansione vulnerabilità sistemi che eseguono Linux e Unix sistemi operativi e quindi li infettano. Bash è una shell a riga di comando. Ciò consente di impartire comandi agli utenti di lanciare Programmi e funzionalità nel software digitando nel testo. È in genere utilizzato dai programmatori, e non dovrebbe essere aperta al resto del mondo, se Shellshock che cambia. Beh, worringly, alcuni analisti avvertire che potrebbe essere una minaccia più grande, Shellshock perché permette una completa controllo di una macchina infetta, considerando Heartbleed solo permesso hacker per spiare i computer. E 'così grave, è stato valutato a 10 su 10 per gravità dal National Vulnerability Database. 2/3 di tutti i server web sono a rischio, tra cui alcuni computer Macintosh. Beh, assicuratevi di patchare i sistemi ora. Chiunque l'hosting di un sito web in esecuzione i sistemi operativi interessati dovrebbe intervenire il più presto possibile. Chiunque può permetterselo dovrebbe apparire alla loro applicazione e monitoraggio web firewall per guardare fuori per tutti gli attacchi. SPEAKER 3: cosa peggiore che potrebbe accadere è che qualcuno avrebbe scritto un codice che sarebbe andare a eseguire automaticamente la scansione Internet e inciderebbe tutti questi computer. E una volta che lo fanno, bene, la cosa peggiore che potessero fare è solo cancellare tutto, o chiudere i siti verso il basso. Così abbiamo potuto vedere i danni da questo punto di vista, dove avremmo persone malintenzionati che solo decidere di provocare il caos da sistemi di abbattere o cancellare file, e cose del genere. SPEAKER 2: Alcuni dicono che questo è uno dei più difficili da misurare bug in anni, ed è può richiedere settimane o addirittura mesi per determinare l'impatto finale. SPEAKER 1: Quindi tutto questo è vero, ma la cosa divertente è, quasi tutti delle immagini che hai appena visto, eccetto forse per la tastiera, non ha nulla a che fare con il bug di sorta. Server e fili e così via, è una sorta di tangenziale collegata, ma al centro è in realtà piuttosto familiare quello che sta succedendo qui. In realtà, mi permetta di andare in il nostro apparecchio CS50. Lasciami andare avanti e massimizzare la finestra del terminale qui. E voi ragazzi hanno utilizzato questo, o la versione integrata della stessa, in gedit per scrivere programmi, digitare i comandi, e così via, e questo è in realtà, e ha stato per settimane, Bash, B-A-S-H. Questa è la Bourne-again shell, che è solo un modo elegante per dire, questo è un programma che ha una lampeggiante rapido, efficace, che siede lì in attesa per l'ingresso per voi. Ed è il comando interfaccia a riga tramite la quale voi ragazzi sono stati l'esecuzione di comandi e in ultima analisi, compilazione e quindi eseguire programmi. Ma Bash è anche una programmazione lingua nel senso seguente. Voi sapete che ci sono comandi come cd e ls e anche clang e altri, ma è possibile definire i propri comandi dalla loro attuazione in Bash. Ora non stiamo andando a andare in grande dettaglio come per colpire il linguaggio di programmazione, ma Sappiamo, per esempio, che per il momento, non esiste un comando chiamato "ciao." Così può essere trovato in uno di questi pacchetti. Non è installato sul mio computer. Chiedere all'amministratore. Ma se io voglio che ci sia un programma chiamato "ciao" in Bash o alla mia richiesta, Posso effettivamente usare la sintassi che è abbastanza come C. Non è proprio la stessa cosa, ma sembra piuttosto simile a un funzione, anche se mancano alcuni dettagli. Nulla sembra accadere, ma ora se digito "ciao," si può effettivamente scrivere un programma, non in C, non in Java, non in un altro programmazione linguaggio, ma in Bash sé. Ora la chiave qui è che ho scritto il nome che ho voluto dare a questo nuovo comando, e le parentesi sono anche simbolica di questa essendo una funzione. Per inciso, si può anche fare divertimento le cose, e in effetti, anche su Mac OS, questo è un programma chiamato Terminal. Viene costruito in qualcuno di computer che dispone di un Mac in questa stanza, e si possono fare cose simili in Mac OS, ma si può andare più oltre. E questo è un po tangenziale, ma è una specie di divertimento. Mi è stato ricordato questa mattina, quando si pensa questo attraverso, di un piccolo gioco che ho usato per giocare con uno degli ex TF di CS50 per cui ogni volta che camminava lontano da la tastiera con il suo schermo sbloccato, Vorrei eseguire un comando come questo-- "dire ciao." E adesso ogni volta che è tornato al suo tastiera dopo aver cancellato lo schermo e si sedeva, provare a fare qualche lavoro, elencare il contenuto della sua directory-- [AUDIO RIPRODUZIONE] -Ciao. Ciao. SPEAKER 1: Così, in tutta onestà, non era in realtà "ciao." Di solito era qualcosa di più simile a che-- [AUDIO RIPRODUZIONE] -Beep. SPEAKER 1: --that I would-- così il suo computer sarebbe giuro su di lui ogni volta che in realtà sedette alla tastiera. E ben presto ha capito di non lasciare il suo schermo sbloccato. Ma questo suggerisce il tipo di divertimento stupido che si può avere con qualcosa come Bash. Ma è un po 'più serio, per essere sicuri, di quello. Ed in effetti, questo è uno dei maggior numero di bug pericolosi e duraturi che ha davvero colpito il mondo a livello globale. Questo bug è stato intorno per circa 20 anni, e sarete colpiti in un solo momento per la sua relativa semplicità. Quindi questo è un rappresentante ordinerà che se si possedere un Mac, letteralmente in questo momento quando avete il vostro coperchio aperto, si può provare a digitare in quella programma chiamato Terminal. Terminal è sotto Applicazioni Utilities-- per una volta, gli utenti di Windows non devono preoccuparsi di questo particolare threat-- ma quelli di voi con Mac possibile digitare questo in una finestra come farò qui, e se si digita che in questo programma chiamato Terminal, come farò adesso, se vedete la parola "vulnerabile" il computer è vulnerabili allo sfruttamento. Ora, che cosa vuol dire realmente? E questo è certamente una sintassi abbastanza pazzo, ma diamo almeno tirare fuori alcuni degli aspetti interessanti. Quindi c'è una certa sintassi che sembra un po 'familiare, almeno dal C e programmazione, più in generale. Vedo alcune parentesi, punto e virgola, parentesi graffe, e tali, ma si scopre che questa cosa stupida qui in giallo è essenzialmente una funzione che non fa nulla. I mezzi colon non fanno nulla, e la punto e virgola significa smettere di fare nulla. Quindi all'interno di questi parentesi graffe, il fatto che ho un uguale firmare a sinistra, questo è essenzialmente la creazione di un comando, o una variabile, chiamato x, e assegnandogli quel po 'di colore giallo di codice lì. Questo potrebbe essere qualcosa del tipo "echo ciao "o" bip dire "o qualcosa del genere simile a quello. Ma notare se i tuoi occhi vagare più a destra, c'è di più a questa linea di solo alla fine di quel punto e virgola. "Echo vulnerabile," e poi al di là che c'è ancora di più. Un altro punto e virgola, bash-c :. Quindi, per farla breve, questa riga di codice è sufficiente per avvincente un computer che è vulnerabile a fare qualcosa che vuoi che faccia, perché c'è un bug in Bash per cui anche se Bash doveva fermare linee di lettura di comando a destra lì dopo il testo giallo, per un 20-plus anni bug, Bash è stata in realtà la lettura oltre tale punto e virgola e abbastanza molto fare quello che viene detto. Allora, qual è l'implicazione di che alla fine? Ho solo detto "echo ciao" o "echo vulnerabile," ma cosa succede se hai fatto qualcosa di in realtà dannoso, come rm-rf *, che non si potrebbe hanno mai scritto prima, e francamente probabilmente non dovrebbe troppo presto, perché si può fare un sacco di danni con esso. Perché? rm fa quello, naturalmente? Rimuove. * Significa che cosa? Tutto. Quindi è un cosiddetto wild card, quindi significa cancellare tutto in la directory corrente. -r accade a significare ricorsiva, il che significa che se quello che stai cancellando è una directory, e dentro di lì è altri file e altre directory, ricorsivamente tuffarsi in là e cancellare tutto questo. E f è il peggiore di tutti. Qualcuno sa cosa significa -f qui? Forza. Quindi forzare mezzi, anche se questa è una cattiva idea, farlo senza di me chiedere conferma per ulteriore conferma. Così, sai, ridiamo questo, ma francamente, io probabilmente digitare questo più volte un giorno, perché la realtà è che è il modo più veloce per cancellare un sacco di roba. Ma anche io ho fatto qualche danno. Ma se si dovesse ingannare un computer nella definizione di alcune variabili stupido o funzione chiamata x, ma poi ingannando il computer in esecuzione al di là dei confini di quel funzione, oltre che punto e virgola, si potrebbe infatti ingannare un computer in esecuzione qualcosa come rm-rf o il comando mail o il comando Copia. Tutto ciò che letteralmente si può fare con la del computer, che si tratti di eliminazione di file, creazione di file, spamming qualcuno, attaccando alcuni server remoto, se si può esprimere con un comando, si può ingannare un computer a fare questo. Ora, ciò che è un esempio di come si potrebbe fare questo? Beh, c'è un sacco di computer su Bash internet esecuzione. Tutti noi utenti Mac sono tra di loro. Un sacco di server Linux sono tra loro pure, e server Unix. Finestre ottiene di nuovo relativamente fuori dai guai a meno che non hai installato software speciale. Ora un sacco di server, per esempio, server web gestiti, e infatti Linux è forse l' sistema operativo più popolare per funzionare su computer su internet che servono le pagine web. Ora, come vedremo più avanti nel semestre, quando si invia una richiesta da il tuo browser-- Chrome, Internet Explorer, whatever-- a un server remoto, si scopre che anche se appena digitata www.example.com, il browser invia un messaggio che è un po 'più arcane, come questo. Ma notare un po 'di qualcosa di strano. Le prime due righe Non ho mai visto prima, ma non guardano particolarmente minaccioso. Ma accorgo di quello che ho rubato per la terza linea qui. Se un ragazzo cattivo dovesse inviare un messaggio come questo dal suo computer di un Mac o di un vulnerabile server vulnerabile Linux, la cosa divertente è che Bash, che semplice prompt dei comandi poco, è onnipresente ed è spesso utilizzato per eseguire essenzialmente il contenuto di un messaggio che riceve. E da questa logica, è possibile ingannare un server web, quindi, inviando qualcosa come User-Agent, che di solito si suppone a dire il Nome del tuo browser. User-Agent Chrome, User-Agent Internet Explorer, Firefox User-Agent, questa è solo il browser del modo di identificare se stesso. Ma se un cattivo ragazzo molto dice abilmente, mm-mm, sono Non lo dirò ciò che il mio browser, Io invece intenzione di inviare questo criptico-guardando cosa con un rm-rf * In esso, si può letteralmente ingannare un web server vulnerabile su internet in esecuzione esattamente questo in lì per cancellare tutti i file. E, francamente, non è anche il peggio. Si può fare qualsiasi cosa. Si potrebbe iniziare una distribuita attacco denial of service se hai inviato questo messaggio a grappoli interi server web e poi li aveva tutti discendono, per esempio, su server Harvard.edu, e si può ordinare di botto diamine fuori di essi da un traffico di rete che era altrimenti innescato da questo cattivo ragazzo. Quindi, per farla breve, quasi tutti in questa stanza che possiede un Mac è vulnerabile a questo. Il rivestimento d'argento è che se non sei esecuzione di un web server sul vostro computer portatile, e se non hai effettivamente configurato per consentire qualcosa come SSH in esso, sei davvero sicuro. E 'vulnerabile, ma non c'è uno cercando di entrare nel vostro computer portatile, in modo da poter sorta di stare tranquilli. Tuttavia, Apple sarà presto essere l'aggiornamento di una correzione per questo. Il mondo di Linux ha già rilasciato una serie di correzioni per Fedora e Ubuntu e altre versioni di Linux, e anzi se si esegue l'aggiornamento 50 in dell'apparecchio, anche che troppo sarà aggiornato e corretto. Ma che non ha troppo stato davvero vulnerabile, perché a meno che non hai armeggiato con l'apparecchio e fatto il vostro computer portatile al pubblico accessibili su internet, che non è Per impostazione predefinita, hai effettivamente bene perché di firewalling e di altre tecniche. Ma è un esempio estremo di un bug che abbiamo vissuto per letteralmente per 20 anni, e chissà se qualcuno tutto questo tempo ha saputo su di esso? Ed in effetti, questo è uno dei le sfide fondamentali che vedremo più avanti nel semestre per la sicurezza, è che, proprio come nel mondo reale, i buoni sono in svantaggio. Per mantenere i cattivi fuori, dobbiamo fare in modo che ogni porta è chiusa a chiave, che ogni finestra è sicuro, che ogni punto di ingresso in una casa è sicuro per mantenere i cattivi fuori. Ma che cosa fa il cattivo deve fare per compromettere in realtà la vostra casa e rubare da voi? Lui o lei deve solo trovare uno sbloccato porta, una finestra rotta, o qualcosa del genere in tal senso, ed è il stessa cosa in sicurezza informatica. Possiamo scrivere milioni di linee di codice di programmazione e spendere centinaia o migliaia di ore cercando di farlo giusto, ma se fate un solo errore di correttezza, si può mettere l'intero sistema e infatti in questo caso, l'intera Internet ea rischio mondo. Quindi, se vuoi saperne di più su questo, vai a questo URL qui. Non c'è bisogno di un'azione stasera se non sei tra quelli più comodo che sono stati in esecuzione il proprio web server, nel qual caso si dovrebbe, infatti, aggiornare il software. E anche questo è il titolo di un discorso, e ora una carta, che abbiamo legati alla sito web del corso per oggi. Era da un collega di nome Ken Thompson, che è stato accettare un molto famoso premio in informatica, e ha dato questo discorso alcuni anni fa, in sostanza, su questo stesso argomento. Chiedere gente la domanda, si dovrebbe davvero fiducia, in ultima analisi, la software che hai ricevuto? Per esempio, tutti noi abbiamo stata la scrittura di programmi, e siamo stati compilando li con Clang. E per vostra conoscenza, hai scritto tutti i programmi per CS50 dove c'è una porta sul retro di sorta, c'è un modo che un cattivo ragazzo, se si esegue il programma, potrebbe prendere in consegna il vostro computer? Probabilmente no, giusto? Mario, e avidi, e di credito. Questi sono tutti piuttosto piccoli programmi. Dovresti essere abbastanza male se effettivamente fatto tutto il computer vulnerabile dopo aver scritto 10 o 20 righe di codice, o almeno a conoscenza di alcune delle implicazioni di sicurezza. Ora io dico che scherzosamente, ma stiamo andando a vedere oggi e questa settimana è in realtà davvero, davvero facile per essere cattivo e rendere ancora brevi programmi vulnerabili. Ma per ora, almeno, realizzare che la domanda che si pone qui è circa Clang in un compilatore. Perché siamo stati fiduciosi Clang per gli ultimi due o tre settimane? Chi può dire che chi ha scritto Clang non ha avuto un "se" condizione in là che in sostanza iniettata alcuni zeri e quelli in ogni programma si compila che avrebbe lasciato lui o lei di accesso il computer quando si è addormentato e il vostro coperchio del portatile è aperta e il computer è in esecuzione? Giusto? Noi abbiamo questa sorta di diritto sistema onore ora dove abbiamo fiducia che Clang è legit. Ti fidi che l'apparecchio è legit. Ti fidi che letteralmente ogni programma sul vostro Mac o PC è affidabile. E come suggerisce questa semplice bug, anche se non è dannoso, che non è assolutamente probabile che sia il caso. Così si dovrebbe avere paura come l'inferno. Francamente, non c'è semplice soluzione a questo altro di una sorta di consapevolezza sociale la crescente complessità che stiamo costruendo in cima dei nostri sistemi informatici, e come sempre più vulnerabili potremmo benissimo essere. Ora, con quello detto, Breakout. Così Breakout è un problema impostato tre, e Breakout è un gioco da ieri che si potrebbe ricordare, ma per noi nel problema impostare tre, che ci permette di prendere le cose su una tacca in modo che quando stiamo scrivendo programmi, anche in una finestra di terminale come questo, possiamo effettivamente correre, in ultima analisi, programmi grafici non a differenza di quelli che abbiamo avuto l'accesso al Scratch. Quindi questo è il personale di implementazione di Breakout, che è proprio questo mattone-rottura gioco, che si sposta il paddle schiena e indietro, e si colpisce la palla contro quei mattoncini colorati sulla parte superiore. Quindi questo ci sta portando sorta di nuovo a dove siamo stati in grado di essere molto rapidamente con Scratch, e ora con C, attuazione nostro interfacce grafiche. Ma più di questo, questo Set problema rappresenta il primo in cui stiamo dando un mucchio di codice. E infatti, io porto esplicito attenzione a questo, soprattutto perché per quelli meno confortevole, questo problema fissato, almeno a prima vista, sta andando a sentire come abbiamo preso su una tacca. Perché vi abbiamo dato, per alcune delle ricerche e smistamento problemi nel pset, un mucchio di codice che abbiamo scritto, e un paio di commenti che dire "da fare" dove si deve riempire gli spazi vuoti. Quindi non troppo spaventoso, ma è la prima volta vi stiamo consegnando il codice che avete bisogno di prima di leggere, capire, e poi aggiungere a e completarlo. E poi con Breakout, stiamo andando a fare lo stesso, dandovi qualche decina di più linee di codice che, francamente, dare un sacco di quadro di riferimento per il gioco ma fermarsi di attuare i mattoni e la palla e la racchetta, ma facciamo implementare alcune altre caratteristiche. E anche che a prima vista, ancora una volta, soprattutto se meno confortevole, potrebbe sembrare particolarmente scoraggiante e Pensi che ci sono tante nuove funzioni è necessario avvolgere la vostra mente intorno, e questo è vero. Ma tenere a mente, è abbastanza come Scratch. Le probabilità sono non ha utilizzato tutti i pezzi del puzzle in Scratch. Le probabilità sono che non ti importava di avvolgere la vostra mente intorno tutti perché è bastato un rapida occhiata per capire, oh, questo è quello che posso fare con quel pezzo di puzzle. E infatti, nel problem set 3 spec, ti segnaliamo voi la documentazione che verrà farvi conoscere alcune nuove funzioni, e in ultima analisi, la programmazione Costruisce si utilizza. Condizioni, i cicli variabili e funzioni è identico al quello che abbiamo visto finora. Così in effetti, ciò che noi daremo vi è un codice di esempio che consente di creare una finestra che non sembra a differenza di questo, e infine trasformarlo in qualcosa di molto simile. Approfittate quindi di CS50, discutere l'orario di ufficio e di più, e prendere conforto nel fatto che la quantità di codice da scrivere è in realtà non più di tanto. La prima sfida è solo per ambientarsi a voi stessi di qualche codice che abbiamo scritto. Hai domande su pset3, Shellshock, o in altro modo? PUBBLICO: Sembrava passando con Breakout che il codice è quasi uno stile orientato agli oggetti, ma ho pensato che fosse un C object-oriented programma. SPEAKER 1: Una domanda eccellente. Quindi, nel guardare attraverso il codice di distribuzione, il codice abbiamo scritto per pset3, per chi ha familiarità, si sembra come se fosse un poco orientato agli oggetti. Risposta breve è, è. Si tratta di una approssimazione di come si potrebbe fare di codice orientato agli oggetti utilizzando un linguaggio come C, ma è ancora in ultima analisi procedurale. Non esistono metodi all'interno di le variabili, come vedrete. Ma ricorda che. E vedremo ancora una volta che la funzione quando arriviamo a PHP e JavaScript verso la fine del semestre. Ma per ora, pensare ad esso come un accenno di ciò che è a venire. Buona domanda. Bene. Così merge sort è stato il modo in cui cose di sinistra ultima volta. E merge sort era fresco in senso che era molto più veloce, almeno sulla base delle prove sommarie abbiamo fatto la scorsa settimana, rispetto, ad esempio, bolla sort, selection sort, insertion sort. E ciò che era troppo pulito è solo come succintamente e pulito si può esprimere. E che cosa abbiamo detto che era un superiore bound sul tempo di esecuzione di merge ordinare? Sì? PUBBLICO: n log n? SPEAKER 1: n log n, a destra. n log n. E torneremo a ciò che significa realmente o dove che viene da, ma questo era meglio di quanto tempo di esecuzione che abbiamo visto per la bolla selezione e insertion sort? Così n quadrato. n al quadrato è più grande di questo, e anche se non è del tutto evidente, sa che log n è minore di n, quindi se si fa n volte qualcosa di più piccolo di n, che sta per essere inferiore a n al quadrato. E 'un po' di intuizione lì. Ma abbiamo pagato un prezzo per questo. Era veloce, ma un tema che ha iniziato emergere la scorsa settimana è stato questo compromesso. Ho ottenuto la migliore prestazione tempo saggio, ma cosa ho dovuto passare dall'altra mano, al fine di ottenere che? PUBBLICO: Memoria. SPEAKER 1: dire ancora? PUBBLICO: Memoria. SPEAKER 1: Memoria, o spazio più in generale. E non era super evidente con i nostri uomini, ma ricordare che i nostri volontari sono stati un passo avanti e un passo indietro come se ci fosse una matrice qui, e come se ci fosse un secondo array qui che potrebbero usare, perché noi da qualche parte necessaria per unire quelle persone. Non potevamo semplicemente scambiare sul posto. Così merge sort leva è più spazio, che non abbiamo bisogno di gli altri algoritmi, ma il lato positivo è che è molto più veloce. E, francamente, nello spazio reale mondo questi days-- RAM, hard disk space-- è relativamente a buon mercato, e così che è non è necessariamente una cosa negativa. Quindi, diamo un rapido sguardo, un po ' più metodicamente, a quello che abbiamo fatto e perché abbiamo detto che era n log n. Così qui sono le otto numeri e la otto volontari abbiamo avuto l'ultima volta. E la prima cosa che si fondono Ordina ci ha detto di fare era quello? PUBBLICO: Divide in due. SPEAKER 1: dire ancora? PUBBLICO: Divide in due. SPEAKER 1: Divide in due, a destra. Questo ricorda molto l'elenco telefonico, di dividere e conquistare più in generale. Così abbiamo guardato la metà sinistra. E poi una volta abbiamo detto, sorta la metà sinistra degli elementi, cosa abbiamo successivo diciamo? Ordina la metà sinistra della sinistra mezzo, che ci ha permesso di, dopo aver diviso in due, concentrarsi su quattro e due. Come si ordina un elenco ora, in giallo, di dimensione due, utilizzando Merge Sort? Beh, dividerlo a metà, e ordinare la metà sinistra. E questo era il luogo dove le cose ottenuto un po 'brevemente stupido. Come si ordina un elenco che è di Taglia unica, come questo numero quattro qui? E 'ordinato. Il gioco è fatto. Ma allora come si fa a ordinare un elenco di Un formato quando è il numero due? Beh, la stessa cosa, ma ora quello che era il terzo e il passo fondamentale per merge sort? Si doveva unire sinistra metà e la metà destra. E una volta che abbiamo fatto, abbiamo guardato alle quattro, abbiamo guardato due. Abbiamo deciso tutto bene, ovviamente due viene prima, così abbiamo messo due nella sua posto, seguito da quattro. E ora si deve tipo di riavvolgere, e questo è una sorta di caratteristica di un algoritmo come unione Ordina, riavvolgere in memoria. Qual è stata la riga successiva della storia? Cosa devo concentrarmi sul prossimo? La metà destra della sinistra mezzo, che è sei e otto. Quindi lasciatemi passo attraverso questo senza che belaboring il punto di troppo. Sei e otto, poi sei è ordinato, otto è ordinato. Unirli insieme come quella, e ora il prossimo grande passo è, naturalmente, ordinare la metà di destra da il primo passo di questo algoritmo. Quindi ci concentriamo su uno, tre, sette, cinque. Abbiamo poi concentriamo sulla metà sinistra. La metà sinistra di questo, la metà destra del che, e poi si fondono in uno e tre. Poi la metà destra, poi a sinistra a metà di esso, quindi la metà destra di esso. Unisci in, e adesso che passo rimane? Unire il grande metà sinistra e la grande metà destra, così si va laggiù, poi due, poi tre, poi quattro, poi cinque, poi sei, poi sette, poi otto. Così ora perché è questo in definitiva rivelando, soprattutto se n e logaritmi più generalmente piuttosto sfuggirti, almeno nella memoria recente? Beh, notare l'altezza di questa cosa. Avevamo otto elementi, e noi diviso per due, a due, da due. Così log in base due di otto anni ci dà tre. E credetemi su che se un po 'confuso su questo. Ma log in base due di otto è tre, così abbiamo fatto tre strati di fusione. E quando ci siamo fusi elementi, quanti elementi abbiamo guardiamo su ciascuno di tali righe? Un totale di n, giusto? Perché per unire la riga superiore, anche se abbiamo fatto frammentario, abbiamo infine toccato ogni numero una volta. E in seconda fila, a unire tali elenchi di dimensione due, abbiamo dovuto toccare ogni elemento una volta. E poi qui davvero chiaramente in ultima fila, abbiamo dovuto toccare ciascuno di quelli elementi di una volta, ma solo una volta, così si trova qui, allora, il nostro registro n n. Ed ora solo per rendere le cose un po ' più formale per un momento, se si dovevano ora analizzare questo in una sorta di livello superiore e cercare di decidere, bene come potreste andare su di esprimere il tempo di esecuzione di questo algoritmo solo guardando e non utilizzando un esempio forzato? Beh, quanto tempo si dovrebbe dire un un passo come questo in giallo avrebbe preso, se n <2 ritorno? Questo è un grande O di che cosa? Così sto vedendo uno, così un passo, forse due passi perchè è se e poi tornare, ma è costante di tempo, giusto? Così abbiamo detto O (1), e che è come io esprimo questo. T, basta essere tempo di esecuzione. n è la dimensione dell'input, quindi T (n), solo un modo elegante di dire la corsa tempo dato input di dimensione n sta per essere dell'ordine di tempo costante, O (1). Ma per il resto, che dire di questo? Come si dovrebbe esprimere il tempo di questa linea gialla in esecuzione? T di che cosa? È possibile tipo di barare qui e rispondere alla mia domanda ciclicamente. Quindi, se il tempo di esecuzione in generale diciamo solo è T (n). E ora stai tipo di punting qui e dicendo, beh, basta ordinare la metà sinistra, e poi ordinare la metà destra. Come potremmo simbolicamente rappresentare il tempo di esecuzione di questa linea gialla? T di che cosa? Qual è la dimensione dell'input? n più di due. Perché non dico solo che? E allora questo è un altro T (n / 2) e poi ancora una volta, se mi fondo due metà ordinate, quanti elementi sto andando dover toccare totale? n. Così posso esprimere questo, solo per essere una sorta di fantasia, come il tempo di esecuzione in generale. T (n) è solo il tempo di esecuzione di T (n / 2), più T (n / 2), a sinistra metà e metà a destra, più O (n), che è probabilmente n passi, ma forse, se sto usando due dita, è il doppio passi, ma è lineare. È certo numero di passi questo è un fattore di n, così potremmo esprimere questo come questo. E questo è dove ora ci Punt al posteriore del nostro libro di testo di matematica del liceo siamo che la ricorrenza in ultima analisi, finisce pari questa, n log n volte, se effettivamente fare fuori la matematica più formale. Ecco, questo è solo due punti di vista. Una numerico con una hard-coded esempio rappresentativo utilizzando otto numeri, e una più un'occhiata a come ci siamo arrivati. Ma ciò che è veramente interessante è, ancora una volta, questa nozione di ciclismo. Non sto usando per cicli. Sto tipo di definizione qualcosa in termini di se stessa, non solo con questa funzione matematica, ma anche in termini di questa pseudo codice. Questo pseudo codice è ricorsiva dal fatto che due delle sue linee è essenzialmente dicendogli di andare utilizzarsi per risolvere un piccolo problema di piccole dimensioni, e poi ancora e ancora e di nuovo fino a quando non si whittle fino a questo cosiddetto caso base. Quindi cerchiamo di disegnare una realtà più convincente take-away da questo come segue. Lasciami andare in gedit e prendo un guardare alcuni dei codice sorgente di oggi, in particolare questo esempio qui. Sigma 0, che aggiunge a quanto pare i numeri da uno a n. Vediamo quindi che cosa è familiare e sconosciuto qui. In primo luogo abbiamo un paio di comprende, quindi nulla di nuovo lì. Prototype. Sono un po 'confuso su questo dopo pochi giorni, ma che cosa abbiamo detto una prototipo di una funzione è? PUBBLICO: [incomprensibile]. SPEAKER 1: Che cos'è? PUBBLICO: Annunciamo esso. SPEAKER 1: Annunciamo esso. Quindi stai insegnando Clang, hey, in realtà non applicazione del presente ancora, ma da qualche parte in questo file, presumibilmente, sta per essere una funzione chiamata che cosa? Sigma. E questo è solo una promessa che sta andando a guardare come questo. Sta andando a prendere un intero come input-- e posso essere più esplicito e dire int n --e è andando a restituire un int, ma mezzo punto e virgola, mm, vado a prendere in giro per l'applicazione del presente un po 'più tardi. Anche in questo caso, Clang è muto. Sta solo andando a sapere che cosa si dice verso il basso, così abbiamo bisogno di almeno dare un accenno di ciò che è a venire. Ora diamo un'occhiata a principale qui. Facciamo scorrere qui e vedere cosa principale sta facendo. Non è che molto di una funzione, e infatti il ​​costrutto ecco familiare. Dichiaro una variabile n, e quindi I tormentare ancora e ancora l'utente per un numero intero positivo con getInt, e solo l'uscita di questo ciclo una volta che l'utente ha rispettato. Do While, abbiamo utilizzato per importunare l'utente in quel modo. Ora questo è interessante. Dichiaro di un int chiamato "risposta". Assegno che il valore di ritorno di una funzione chiamata "sigma". Non so che cosa che fa ancora, ma Ricordo che dichiara che un momento fa. E poi sto passando l' valore che l'utente ha digitato in, n, e poi vi riporto la risposta. Bene facciamo scorrere indietro solo per un momento. Andiamo avanti in questa directory, fare sigma 0, ed effettivamente eseguire questo programma e vedere cosa succede. Quindi, se vado avanti e correre questo programma, ./sigma-0, e digito in un positivo integer come due, Sigma, come il simbolo greco implica, è solo andando a sommare tutti i numeri da azzeramento su un massimo di due. Quindi 0 più 1 più 2. Quindi questo dovrebbe auspicabilmente darmi 3. Questo è tutto quello che sta facendo. E allo stesso modo, se corro questo nuovo e ho dato il numero tre, che è 3 più 2, in modo che sia 5, più 1 mi dovrebbe dare 6. E poi se ho veramente pazzesco e iniziare a digitare in numeri più grandi, dovrebbe dare me somme sempre più grandi. Ecco, questo è tutto. Così che cosa sigma assomiglia? Beh, è ​​abbastanza semplice. E 'come potremmo implementato questo da un paio di settimane. "Int" sarà il tipo di ritorno. Sigma è il nome, e ci vuole un m variabile invece di n. Cambierò che sulla parte superiore. Allora questo è solo un controllo di integrità. Vedremo perché in un attimo. Ora io dichiaro un'altra variabile, somma, inizializzare a zero. Poi ho questo ciclo For iterazione, a quanto pare per chiarezza, da i = 1 su un massimo di un = m, che è qualunque sia l'utente digitato, e poi ho incrementare la somma in questo modo. E poi restituire la somma. Così un paio di domande. Uno, mi sostengono nel mio commento che questo evita il rischio di un ciclo infinito. Perchè dovrebbe passare in un numero negativo indurre, potenzialmente, un ciclo infinito? PUBBLICO: Non sarai mai raggiungere m. SPEAKER 1: Mai raggiungere m. Ma m viene passato, quindi cerchiamo di considerare un semplice esempio. Se m viene passato dal utente come uno negativo. Indipendentemente principale. Principale ci protegge da anche questo, quindi sono appena essere davvero anale con sigma per fare anche sicuri che l'ingresso non può essere negativo. Quindi, se m è negativo, qualcosa di simile a uno negativo. Cosa succederà? Beh, mi sta per ottenere inizializzato a uno, e poi mi sta per essere minore o uguale a m? Stand-by. Che era-- cerchiamo di non, cerchiamo di NIX questa storia. Non ho chiesto questa domanda, perché il rischio che io alludo a non accadrà perché i è andando sempre maggiore OK than--, Ho ritrattare questa domanda. Ok. Concentriamoci solo su questa parte qui. Perché ho Dichiaro alcuni al di fuori del ciclo? Comunicazione on line 49 ho dichiarato i all'interno del ciclo, ma in linea 48 ho dichiarato alcuni fuori. Già. PUBBLICO: [incomprensibile]. SPEAKER 1: Certo. Quindi, prima di tutto io di certo non lo faccio vuole dichiarare e inizializzare somma a zero all'interno del loop su ogni iterazione, perché questo sarebbe chiaramente sconfiggere l' scopo di riassumere i numeri. Vorrei continuare a cambiare il valore a zero. E inoltre, qual è un altro più arcane ragione per quella stessa decisione di progettazione? Già. PUBBLICO: [incomprensibile]. SPEAKER 1: Esattamente. Voglio accedervi fuori dell'ansa troppo su quale linea? Su 53. E sulla base della nostra regola di pollice da un paio di lezioni fa, variabili hanno un ambito, in realtà, per il parentesi graffe che li comprendono. Quindi, se io non dichiaro somma all'interno di queste parentesi graffe esterne, Io non posso usarlo in linea 53. In altre parole, se ho dichiarato somma qui, o anche all'interno della Per il ciclo, non ho potuto accedervi in ​​53. La variabile potrebbe effettivamente andato. Così un paio di motivi lì. Ma ora torniamo e vedere cosa succede. Così sigma viene chiamato. Si aggiunge 1 più 2, o 1 più 2 oltre a 3, e poi restituisce il valore, memorizza in risposta, e printf qui è per questo che sto vedendo sullo schermo. Quindi questo è quello che chiameremo un iterativo approccio, dove l'iterazione solo significa utilizzare un ciclo. Un ciclo For, un ciclo While, un Do While loop, solo facendo qualcosa di nuovo e ancora e ancora. Ma sigma è una specie di una funzione ordinata in che ho potuto realizzare in modo diverso. Che dire di questa, che solo per essere genere di freddo, mi permetta veramente a sbarazzarsi di un lotto di distrazione perché questa funzione è davvero molto semplice. Facciamo whittle giù solo alle sue quattro linee principali e di sbarazzarsi di tutti i commenti e parentesi graffe. Questa è una specie di mind-blowing implementazione alternativa. Va bene, forse non mente-blowing, ma è una specie di sexy, va bene, guardare a questa molto di più succintamente. Con appena quattro righe di codice, Io prima ho questo controllo di integrità. Se m è inferiore o uguale a pari a zero, sigma non ha senso. Dovrebbe solo essere in questo caso per i numeri positivi, quindi sto solo andando a restituire zero arbitrariamente così che abbiamo almeno alcune cosiddetto caso base. Ma ecco la bellezza. La totalità di questa idea, aggiungendo l' numeri da 1 a n o m in questo caso, può essere fatto secondo la tipologia di passare la patata bollente. Ebbene, qual è la somma di 1 a m? Beh, sai una cosa? E 'uguale alla somma di m più la somma di 1 m meno 1. Beh, sai una cosa? Cosa c'è di sigma di m meno 1? Beh, se si segue questo tipo di logicamente, è lo stesso che m meno 1 più sigma di m meno 2. Così si può tipo di solo-- questo è come, se sei solo cercando di infastidire un amico e ti chiedono una domanda, è sorta di rispondere con una domanda, è possibile tipo di mantenere passare la patata bollente. Ma ciò che è fondamentale è che se si mantiene rendendo la domanda più piccolo e più piccolo, sei Non chiedere che cosa è sigma di n, ciò che è sigma di n, che cosa è sigma di n? Ti stai chiedendo che cosa è sigma di n, che cosa è sigma di n meno 1, qual è sigma di n meno 2? Alla fine la tua domanda sta per diventare cosa? Qual è la sigma di uno o pari a zero, qualche valore molto piccolo, e non appena si ottenere che, il tuo amico, non si ha intenzione di chiedere di nuovo la stessa domanda, si sta solo andando a dire, oh è pari a zero. Abbiamo finito di giocare questo tipo di stupido gioco ciclico. Quindi ricorsione è l'atto di programmazione di una funzione di chiamata stessa. Questo programma, quando viene compilato ed eseguito, è andando a comportarsi esattamente allo stesso modo, ma ciò che è fondamentale è che all'interno di una funzione chiamata sigma, vi è una linea di codice in cui stiamo chiamando noi stessi, che normalmente sarebbe male. Ad esempio, cosa succede se ho compilato questa, in modo da assicurarsi sigma-- rendere sigma 1 ./sigma-1. Intero positivo, per favore, 50 1275. Così che cosa la funzione sembra essere, sulla base di una prova, corretto. Ma cosa succede se ho un po 'pericoloso ed eliminare il cosiddetto caso base, e solo dire, anche io sto solo facendo questo più complicato di quanto non sia. Diciamo solo calcolare la sigma prendendo m e poi aggiungendo in sigma di un m meno? Ebbene, che cosa sta per succedere qui? Andiamo zoom out. Facciamo ricompilare il programma, salvarlo, ricompilare il programma, e quindi pronto ./sigma-1 zoom in, Inserisci il numero intero positivo per favore, 50. Quanti di voi sono disposti a fess fino a vedere che? Ok. Quindi questo può accadere per una serie di ragioni, e francamente questa settimana siamo per darvi più di loro. Ma in questo caso, provare a di ragionare a ritroso cosa sarebbe successo qui? Segmentation fault, dicevamo lo scorso tempo, si riferisce ad un segmento di memoria. Qualcosa di brutto è accaduto. Ma che cosa era meccanico che è andato storto qui a causa della mia rimozione di quel cosiddetto caso base, dove sono tornato un valore hard-coded? Cosa pensi andato storto? Già. PUBBLICO: [incomprensibile]. SPEAKER 1: Ah. Buona domanda. Quindi la dimensione del numero che stavo riassumendo up ottenuto così grande che ha superato la dimensione dello spazio di memoria. Buona idea, ma non fondamentalmente andando a causare un incidente. Questo potrebbe causare integer overflow, dove i bit appena capovolgere e poi ci scambiamo un davvero grande per numero come un numero negativo, ma che in sé non causerà un crash. Perché alla fine del giorno un int è ancora a 32 bit. Tu non stai andando a accidentalmente rubare un po '33 °. Ma un buon pensiero. Già. PUBBLICO: [incomprensibile]. SPEAKER 1: Il metodo non smette mai di correre, e infatti si chiama di nuovo e ancora e ancora e ancora e di nuovo, e nessuno di quelle funzioni sempre finire perché la loro unica linea di codice chiama themself ancora e ancora e di nuovo. E che cosa è veramente succedendo qui, e ora ci può sorta di disegnare questo pittoricamente. Lasciami andare verso un immagine solo per un attimo. Questa è una foto, che alla fine rimpolpare più in dettaglio, di quello che sta succedendo all'interno della memoria del computer. E si scopre che su la parte inferiore di questa immagine è qualcosa che si chiama lo stack. Questo è un pezzo di memoria, un pezzo di memoria RAM, questo è solo usato in qualsiasi momento una funzione viene chiamata. Ogni volta che, un programmatore, chiamare una funzione, il sistema operativo, come Mac OS, Windows, o Linux, afferra un mucchio di byte, forse un pochi kilobyte, forse pochi megabyte di memoria, li porge a voi, e poi lascia si esegue la funzione utilizzando qualunque variabili avete bisogno. E se poi chiama un altro funzione ed un'altra funzione, si ottiene un'altra fetta di memoria e un'altra fetta di memoria. E infatti, se questi vassoi verdi da Annenberg rappresentare quel ricordo, ecco cosa succede il primo volta che si chiama la funzione sigma. E 'come mettere un vassoio come questo su ciò che è inizialmente uno stack vuoto. Ma poi se quel vassoio si chiama, per così dire, chiamando un'altra istanza di sigma, che è come chiedere il sistema operativo, ooh, bisogno di un po 'di più memoria, me che dare. E poi viene accumulata su in cima. Ma ciò che è fondamentale è che il primo cassetto è ancora lì, perché ha invocato questo secondo vassoio. Ora invece, chiamano sigma sigma, è come chiedere di più memoria. Ottiene accumulato su qui. sigma chiamata sigma, che è un altro vassoio che viene accumulata qui. E se continui a fare questo, alla fine, tipo di mappare questo visiva a tale grafico, quello che sta succedendo a accadere con la pila di vassoi? Si sta per superare l'importo della memoria il computer dispone. E non appena questo vassoio verde supera la linea orizzontale sopra stack e sopra quella parola heap, che ci torneremo in futuro, che è una brutta cosa. Il mucchio è un diverso segmento di memoria, e se si lascia che questi vassoi palo e palo su, si sta andando a superare il proprio segmento di memoria, e un programma è davvero andando in crash. Ora, come un a parte, questa idea di ricorsione, quindi, può chiaramente portare a problemi, ma non è necessariamente una cosa negativa. Perché prendere in considerazione, dopo tutti, how-- e forse questo richiede un po 'di tempo per abituarsi a --Come elegante o come semplice che l'attuazione di sigma è stato. E non stiamo andando ad utilizzare ricorsione di tanto in CS50, ma in CS51, e davvero qualsiasi classe dove manipolare strutture di dati come alberi, o alberi genealogici, che hanno una certa gerarchia, è super, super utile. Ora, per inciso, in modo che si come aspiranti scienziati informatici hanno familiarità con alcune delle Google scherzi, se si va a Google e si guarda a ciò che è il definizione di, diciamo, ricorsione, immettere. Uh-huh. Per inciso, ho tirato su alcuni. Questo era come 10 minuti di procrastinazione questa mattina. Se anche Google "di traverso," avviso inclinando la testa slightly-- e allora questo è forse più atroce di tutti dal momento che qualcuno ha speso come la loro giornata attuazione del presente alcuni anni ago-- si accendono. Oh, wait-- questo è un bug. Quindi esecuzione su uno dei più grandi siti del mondo sono questi stupidi piccole uova di Pasqua. Probabilmente consumano una numero non banale di righe di codice solo così che possiamo avere piccole cose divertenti come quella. Ma almeno ora si ottiene alcuni di questi scherzi. Ora diamo uno sguardo ad alcuni dei bianco giace abbiamo raccontato di ritardo, e iniziare a sbucciare indietro alcuni strati tecnicamente in modo che si capisce davvero quello che sta succedendo e si può capire alcune delle minacce, come Shellshock, che hanno iniziato a diventare in prima linea di ognuno di attenzione, almeno nei media. Così qui è una funzione molto semplice che restituisce nulla, nulla. Il suo nome è di swap. Prende in due variabili e restituisce nulla. Prende in ae b. Quindi una rapida dimostrazione. Abbiamo portato questi in su. Potremmo anche prendere un po ' rompere qui solo per un attimo e hanno un po 'di qualcosa da bere. Se qualcuno non mi dispiacerebbe entrare me qui solo per un attimo. Come su di te con la camicia marrone? Andiamo su. Proprio quello di oggi. Grazie, però. Va bene, e abbiamo venire che qui? Come ti chiami? SPEAKER 4: Laura. SPEAKER 1: Laura. Andiamo su. Così Laura, molto semplice sfida di oggi. Piacere di conoscerti yo. Bene. Così abbiamo un po 'di latte qui e abbiamo un po 'di succo d'arancia qui e alcune coppe che abbiamo preso in prestito dalla Annenberg oggi. SPEAKER 4: Borrowed. SPEAKER 1: E intenzione di andare avanti e vi darò mezzo bicchiere di questo. Bene. E vi daremo la metà un bicchiere di latte. Oh, e solo così che si può ricordare ciò che questo era come, Mi sono ricordato di portare questo e oggi. Bene. Se non ti dispiace, vediamo, abbiamo li possono mettere sopra i vostri occhiali se vuoi. Questo sarà il mondo dagli occhi di Laura. Bene. Così il vostro obiettivo, dato due tazze di liquido qui, latte e succo d'arancia, è scambiare i due contenuti in modo che l' succo d'arancia va nella tazza del latte e il latte va in la tazza di succo d'arancia. SPEAKER 4: Ricevo un'altra tazza? SPEAKER 1: Sono così contento che hai chiesto, anche se sarebbe stato molto meglio di repertorio se non avessi chiesto. Ma sì, siamo in grado di offrire un terzo coppa che è vuota, naturalmente. Bene. Così scambiare il contenuto lì. Molto bello. Molto buona. Stai facendo questo notevole attenzione. E un passo tre. Bene. Eccellente. Un grande applauso sarebbe bene per Laura. Bene. Abbiamo un piccolo regalo d'addio per voi, ma mi permetta di prendere questi. Vi ringrazio tanto. Così un semplice esempio, però, per dimostrare che se si fa vogliono scambiare i contenuti di due contenitori, o chiamiamoli variabili, avete bisogno di qualche deposito temporaneo mettere in scena uno dei contenuti in modo che si può effettivamente fare lo swap. Così in effetti, di questo codice fonte qui in C rappresentativa esattamente questo. Se il succo d'arancia era una e il latte era b, e abbiamo voluto scambiare i due, si potrebbe provare qualcosa di creativo versando una nell'altra, ma che probabilmente non sarebbe finire particolarmente bene. E così usiamo una tazza terza, chiamata esso PGT, T-M-P per convenzione, e mettere il contenuto del GU in quella, poi scambiare una tazza, poi mettere la GU in tazza originale, così raggiungimento, esattamente come Laura ha fatto, lo swap. Quindi cerchiamo di fare esattamente questo. Lasciami andare avanti e aprire up un esempio che è denominata appunto "no scambiare, "perché questo non è fatto come semplice come si potrebbe pensare. Quindi, in questo programma, notare che Sto utilizzando stdio.h, il nostro vecchio amico. Ho il prototipo per lo swap lassù, che significa che la sua attuazione di probabilmente basso, e vediamo cosa principale programma sta andando a fare per me. Ho Dichiaro int x ottiene uno, e int y ottiene due. Quindi, pensare a quelli come GU e latte, rispettivamente. E poi ho solo un printf dicendo x è questo e y è questo, solo così posso vedere visivamente quello che sta succedendo. Poi ho printf sostenendo che sto scambiando i due, e poi stampare un sostengono che stanno scambiati, Io e stampare le x e y di nuovo. Quindi qui in swap è esattamente quello che ha fatto Laura, e esattamente quello che abbiamo visto su schermo un momento fa. Quindi cerchiamo di andare avanti e essere assai deluso. Non fare di swap, ed eseguire nessuna di swap, zoom sull'uscita qui. Immettere x è 1, y è 2, scambiando scambiati. x è ancora 1, e y è ancora 2. Così, anche se, francamente, questo sembra Esattamente come, anche se più tecnicamente, quello che ha fatto Laura, non sembrano funzionare. Allora perché? Beh, si scopre che, quando scriviamo un programma come questo che ha sia principale, evidenziato qui, e poi un'altra funzione, come scambio, evidenziato qui, che chiama, il mondo sembra un po 'qualcosa di simile questi vassoi un momento fa. Quando principale prima viene chiamato, che è come chiedere di sistema operativo per un po 'di memoria per ogni locale variabili come x e y che principale ha, e finiscono proprio lì. Ma se le chiamate principali di swap, e principale passa per scambiare due argomenti, a e b, succo d'arancia e latte, non è come consegnando il succo d'arancia e il latte di Laura. Ciò che un computer fa, è esso passa copie del succo d'arancia e copie del latte a Laura, in modo che ciò che è in ultima analisi, all'interno di questo vassoio è il valore di uno e due, o GU e latte, ma loro copie, in modo che a questo punto nella storia, ci è succo d'arancia e latte in ciascuno di questi vassoi. C'è un uno e due in ciascuno di questi vassoi, e la funzione di swap è effettivamente funzionando. Li sta scambiando all'interno del vassoio secondo più in alto, ma che lo scambio non ha alcun impatto. E sulla base di solo alcuni principio di base che abbiamo parlato prima, e anzi a pochi minuti fa, cosa potrebbe spiegare perché cambiare A e B all'interno di scambio non ha alcun effetto su x ed y, sebbene Ho passato x e y per la funzione swap. Qual è la parola chiave qui che potrebbe semplicisticamente spiegare? Penso che ho sentito qui? PUBBLICO: Return. SPEAKER 1: Return? Non tornare. Andiamo con un altro. Che cos'è? PUBBLICO: [incomprensibile]. SPEAKER 1: OK, così abbiamo potuto return-- rendere il lavoro ritorno nella storia, ma c'è una spiegazione ancora più semplice. PUBBLICO: Scope. SPEAKER 1: Ambito di applicazione. Prendo portata. Così ambito, ricordare dove la nostra x e y dichiarati. Sono dichiarate all'interno di principale fino qui. A e B, nel frattempo, sono effettivamente dichiarata interno di scambio, non del tutto in le parentesi graffe, ma ancora nell'area generale di swap. E così effettivamente, a e b esistere solo all'interno di questo vassoio da Annenberg, questo secondo pezzo di codice. Quindi stiamo davvero cambiando la copia, ma che non è poi così utile. Quindi diamo un'occhiata a questo livello un po 'inferiore. Ho intenzione di tornare in la directory di origine, e ho intenzione di primo zoom in qui, e solo per confermare che sono in questo finestra di terminale più grande, il programma è ancora comportarsi così. Supponiamo ora che questo non è intenzionale. Chiaramente volevo swap lavoro, così ci si sente come un insetto. Ora potrei iniziare ad aggiungere un sacco di printf di al mio codice, stampare x qui, y su qui, una qui, b qui. Ma francamente, questo è probabilmente quello che che hai fatto per un paio di settimane ora, in orario di ufficio e in casa quando si lavora su pset cercando di trovare alcuni bug. Ma vedrete, se non avete già, che problema ha impostato tre si introduce ad un comando chiamato GDB, dove GDB, debugger GNU, stessa ha un sacco di caratteristiche che può effettivamente cerchiamo di capire le situazioni in questo modo, ma più convincente, risolvere problemi e trovare bug. Quindi ho intenzione di fare questo. Invece di ./noswap, sono invece andando a correre GDB ./noswap. In altre parole, ho intenzione di correre la mia programma non in Bash, il nostro nuovo amico oggi. Io vado a correre la mia programma noswap all'interno di questo altro programma chiamato GDB, che è un debugger, che è un programma che è progettato per aiutare voi umani trovare e rimuovere i bug. Quindi, se ho colpito Corri qui, c'è un importo atroce di testo che hai davvero mai leggere. E 'essenzialmente una distrazione dal prompt, che Sto andando a colpire Control-L per arrivare fino in cima lì. Questo è il prompt di GDB. Se voglio eseguire questo programma ora, come questo piccolo foglietto di oggi scivolo suggerisce, Run è il primo I comandi che intendevamo introdurre. E sto solo andando a digitare correre qui dentro di GDB, e in effetti ha funzionato il mio programma. Ora c'è qualche ulteriore uscite della schermata come questa, ma questo è GDB solo di essere anale e ci dice cosa sta succedendo. Non devi davvero preoccupare su questi dettagli adesso. Ma ciò che è veramente cool GDB, se faccio questo again-- Control-L cancella il screen-- let me go avanti e di tipo "break principale," in tal modo, quando ho colpito Enter, l'impostazione che cosa è chiamato un punto di interruzione a noswap.c, linea 16, che è dove GDB capito il mio programma in realtà è, la mia funzione è in realtà. Questo ignoreremo per ora ma questo è l'indirizzo nella memoria specificamente di questa funzione. Così ora quando digito corro, notare ciò che è cool qui. Il mio programma interrompe alla linea I detto GDB per mettere in pausa l'esecuzione in. Quindi non devo cambiare ora il mio codice, aggiungere qualche printf di, ricompilare, eseguire nuovamente esso, cambiare, aggiungere un po 'di printf, salvarlo, ricompilarlo, eseguirlo. Posso solo a piedi attraverso il mio programma passo dopo passo per passo a velocità umana, non al tipo Intel-inside di velocità. Così ora notare questa linea appare qui, e se dovessi tornare al mio programma gedit, notare che questo è in realtà la prima riga di codice. C'è la linea 16 in gedit. C'è la linea 16 all'interno GDB, e anche se questa interfaccia in bianco e nero non è quasi come utente amichevole, questo significa tale linea 16 non è stato eseguito ancora, ma sta per essere. Quindi, in effetti, se digito stampa x, non printf, solo stampa x, Ottengo un valore fasullo lì pari a zero, perché x non è stata ancora inizializzata. Quindi ho intenzione di scrivere il prossimo, o, se si vuole essere di fantasia, solo n per il prossimo. Ma quando digito prossima entrare, ora notare che passa per la linea 17. Quindi, logicamente, se ho giustiziato linea 16 e ora tipo di stampa x, cosa devo vedere? Uno. E ora questo è certamente confuso. $ 2 è solo un modo elegante di, se vuole fare riferimento a tale valore in seguito, si può dire "il segno del dollaro due." E 'come un riferimento all'indietro. Ma per ora, basta ignorarlo. La cosa interessante è ciò che è sulla destra del segno uguale. E ora, se digito il prossimo di nuovo e stampare y, dovrei vedere 2. Posso anche ora stampare x di nuovo, e francamente, se sto diventando un po 'confuso su dove mi trovo, posso tipo di lista per lista e solo vedere alcune contesto attorno Il punto che sto davvero a. E ora posso scrivere prossimo, e c'è x è 1. Ora scrivo successivo. Oh, y è 2. E ancora, è confusa, perché l'output di GDB viene commista con la mia uscita. Ma se si tiene a mente, da guardando avanti e indietro al vostro codice o posa fuori lato a fianco, forse, avrete vedo che in realtà io sono solo passando attraverso il mio programma. Ma notare cosa succede dopo, letteralmente. Ecco la linea 22. Lasciami andare su di esso, spostando in tal modo il a 23, e se stampo x ora, ancora uno. E se stampo y ora, ancora uno. Quindi questo non è un esercizio utile. Quindi cerchiamo di rifare questo. Lasciami andare indietro fino alla ancora superiore e il tipo di esecuzione. E sta dicendo che il programma che è in fase di debug ha già iniziato, avviata dall'inizio. Sì, facciamolo di nuovo. E questa volta facciamolo prossimo, Avanti, Avanti, Avanti, Avanti, ma ora le cose si fanno interessanti. Ora voglio fare un passo in swap, quindi non mi tipo successivo. Digito passo, e ora notarlo mi ha saltato alla linea noswap.c 33. Se dovessi tornare a gedit, che cosa è la linea 33? Questa è la prima vera riga di codice all'interno di swap. Che è bello, perché ora posso tipo di curiosare e ottenere curioso quanto a che cosa sta succedendo veramente in là. Permettetemi di stampare tmp. Whoa. Perché tmp ha qualche pazzo, il valore spazzatura fasullo? PUBBLICO: Non è stato inizializzato. SPEAKER 1: Non è stato inizializzato. E infatti, quando si esegue un programma, si è dato un sacco di memoria dal sistema operativo, ma si non sono inizializzati i valori, così qualunque bit sei vedere qui, anche se è questo pazzo grande negativo numero, significa solo che quelli sono i resti di qualche precedente utilizzo di tale RAM, anche se non ho Mi serve ancora. Così ora ho intenzione di andare avanti e di tipo prossimo, e se io ora Tipo di stampa tmp, cosa devo vedere? Qualunque sia il valore di uno stato, a è il primo argomento, basta x come è stato il primo cosa che viene passato in, così un e x dovrebbe essere la stessa, quindi stampare tmp mi deve stampare una. Quindi, quello che vedrete nel set problema tre è un tutorial di sorta su GDB, ma si rende conto che questo è l'inizio di uno sguardo a uno strumento che sarà effettivamente aiutano a risolvere i problemi in modo molto più efficace. Quello che siamo in ultima analisi, andando a fare il Mercoledì è iniziare a sbucciare indietro di pochi strati e rimuovere alcune ruote di formazione. Quella cosa chiamata stringa che abbiamo usato per qualche tempo, stiamo andando a prendere lentamente che via da voi e iniziare a parlare di qualcosa di più esotericamente conosciuto come char *, ma stiamo andando a fare questa bella e prima dolcemente, anche se i puntatori, come si chiamano, può fare un po ' cose molto cattive, se abusato, guardando un po 'claymation da il nostro amico Nick Parlante da Stanford University, un professore di computer scienza che ha messo insieme questa anteprima di ciò che è a venire questo Mercoledì. [RIPRODUZIONE VIDEO] Ehi, Binky. Svegliati. E 'tempo di puntatore divertimento. -Che È? Ulteriori informazioni su puntatori? Oh, goody! [FINE RIPRODUZIONE VIDEO] SPEAKER 1: che vi attende il Mercoledì. Ci vediamo allora. [RIPRODUZIONE VIDEO] -E Ora, pensieri profondi, da Daven Farnham. -Perché Stiamo imparando C? Perché non A +? [Risate] [FINE RIPRODUZIONE VIDEO]