1 00:00:00,000 --> 00:00:12,040 >> [MÚSICA DE XOGO] 2 00:00:12,040 --> 00:00:16,460 >> COLUMNA 1: Todo ben, esta é CS50, e este é o inicio da cuarta semana 3 00:00:16,460 --> 00:00:20,420 e como xa debería ter oído ou ler, o mundo está acabando. 4 00:00:20,420 --> 00:00:23,520 Indo ao redor de Internet foi de coñecemento e concienciación 5 00:00:23,520 --> 00:00:27,100 dun erro nun programa, un linguaxe de programación chamada Bash. 6 00:00:27,100 --> 00:00:32,729 Este foi fermoso marca como Shellshock, é a porta Bash, 7 00:00:32,729 --> 00:00:35,485 pero artigos como estes Non foron pouco frecuentes. 8 00:00:35,485 --> 00:00:38,807 E, de feito, moitos deles traen lembranzas de Heartbleed, 9 00:00:38,807 --> 00:00:41,640 que pode ter notado na prema de novo na primavera pasada, que 10 00:00:41,640 --> 00:00:43,980 foi igualmente moi dramática. 11 00:00:43,980 --> 00:00:47,110 Agora, aqueles de vostedes aquí hoxe, como moitos de vostedes teñen, 12 00:00:47,110 --> 00:00:50,330 mesmo se non entende o que é todo sobre, escoitou falar de Shellshock? 13 00:00:50,330 --> 00:00:51,370 14 00:00:51,370 --> 00:00:54,245 Todo ben, e como moitos de vós teñen ordenadores que son vulnerables? 15 00:00:54,245 --> 00:00:55,680 16 00:00:55,680 --> 00:01:00,250 OK, non debe ser moi, moito máis mans ata o momento, por razóns veremos. 17 00:01:00,250 --> 00:01:02,580 >> Imos dar un ollo ao que está vén pasando nos medios de comunicación 18 00:01:02,580 --> 00:01:05,304 e, a continuación, explicar un pouco aquí para nós tecnicamente. 19 00:01:05,304 --> 00:01:07,670 20 00:01:07,670 --> 00:01:11,250 >> COLUMNA 2: Os expertos en seguridade teñen advertiu que un fallo grave podería 21 00:01:11,250 --> 00:01:15,650 ser de arredor de centos de afectar millóns de usuarios da rede no mundo. 22 00:01:15,650 --> 00:01:20,600 Entón, cal é o erro que foi apelidado Shellshock, eo que fai? 23 00:01:20,600 --> 00:01:23,720 24 00:01:23,720 --> 00:01:28,910 Ben, Shellshock tamén é coñecido como o Bug Bash, o software que explota. 25 00:01:28,910 --> 00:01:33,230 Hackers usan virus para escanear vulnerable sistemas rodando Linux e Unix 26 00:01:33,230 --> 00:01:36,300 sistemas operativos e infecta-las. 27 00:01:36,300 --> 00:01:38,730 Bash é un shell de liña de comandos. 28 00:01:38,730 --> 00:01:43,460 Isto permite aos usuarios enviar comandos para lanzar programas e funcións no software 29 00:01:43,460 --> 00:01:45,250 escribindo texto. 30 00:01:45,250 --> 00:01:49,980 É normalmente usado por programadores, e non debe ser aberto ao mundo exterior, 31 00:01:49,980 --> 00:01:51,590 aínda Shellshock cambia iso. 32 00:01:51,590 --> 00:01:54,160 33 00:01:54,160 --> 00:01:57,910 >> Ben, worringly, algúns analistas advirten que podería ser unha ameaza maior, 34 00:01:57,910 --> 00:02:01,580 Shellshock porque permite total control dunha máquina infectada, 35 00:02:01,580 --> 00:02:06,030 Considerando Heartbleed só permitiu hackers para espiar ordenadores. 36 00:02:06,030 --> 00:02:09,130 É tan serio, é foi avaliado a 10 de 10 37 00:02:09,130 --> 00:02:11,900 á gravidade do National Vulnerability Database. 38 00:02:11,900 --> 00:02:15,530 39 00:02:15,530 --> 00:02:20,015 2/3 de todos os servidores web están no risco, incluíndo algúns ordenadores Mac. 40 00:02:20,015 --> 00:02:22,760 41 00:02:22,760 --> 00:02:25,600 Ben, asegúrese de corrixir os seus sistemas agora. 42 00:02:25,600 --> 00:02:29,330 Calquera que hóspede un sitio en funcionamento os sistemas operativos afectados 43 00:02:29,330 --> 00:02:31,800 debe actuar o máis rápido posible. 44 00:02:31,800 --> 00:02:35,390 Calquera que pode pagar debe ollar para a súa aplicación de seguimento e web 45 00:02:35,390 --> 00:02:37,355 firewalls de ollar para calquera ataque. 46 00:02:37,355 --> 00:02:39,979 47 00:02:39,979 --> 00:02:41,770 Palestrante 3: A peor cousa que podería acontecer é 48 00:02:41,770 --> 00:02:45,080 que alguén vai escribir un código que ía e comprobar automaticamente 49 00:02:45,080 --> 00:02:48,280 Internet e afectaría todos estes computadores. 50 00:02:48,280 --> 00:02:50,710 E xa que eles fan isto, así, o peor que podería facer 51 00:02:50,710 --> 00:02:53,300 é simplemente borrar todo, ou pechar os sitios de abaixo. 52 00:02:53,300 --> 00:02:55,360 Para que poidamos ver os danos a partir dese punto de vista, 53 00:02:55,360 --> 00:02:58,300 onde teriamos persoas mal intencionadas que decide causar estragos 54 00:02:58,300 --> 00:03:02,534 recollendo sistemas abaixo ou a exclusión arquivos, e cousas así. 55 00:03:02,534 --> 00:03:05,200 COLUMNA 2: Algúns din que este é un dos máis difíciles de medir 56 00:03:05,200 --> 00:03:08,080 erros en anos, e Pode levar semanas ou mesmo 57 00:03:08,080 --> 00:03:10,820 meses para determinar o seu impacto final. 58 00:03:10,820 --> 00:03:12,180 59 00:03:12,180 --> 00:03:15,560 >> COLUMNA 1: Entón, todo isto é certo, pero o curioso é que, case todos 60 00:03:15,560 --> 00:03:18,330 das imaxes que acaba de ver, excepto talvez o teclado, 61 00:03:18,330 --> 00:03:20,930 non ten nada que ver con o erro ningún. 62 00:03:20,930 --> 00:03:23,960 Servidores e fíos e así por diante, É unha especie de tanxencialmente relacionado, 63 00:03:23,960 --> 00:03:27,410 pero no centro é realmente moi familiarizado o que está pasando aquí. 64 00:03:27,410 --> 00:03:30,050 De feito, déixeme entrar noso aparello CS50. 65 00:03:30,050 --> 00:03:32,910 Deixe-me ir adiante e dar a xanela de terminal aquí. 66 00:03:32,910 --> 00:03:36,020 E vostedes teñen benvida a utilizar este, ou a versión integrada da mesma, 67 00:03:36,020 --> 00:03:39,460 no gedit para escribir programas, escribir comandos, e así por diante, 68 00:03:39,460 --> 00:03:43,690 e esta é en realidade, e ten foi por semanas, Bash, B-A-S-H. 69 00:03:43,690 --> 00:03:46,890 Este é o Bourne-again Shell, que é só un xeito elegante de dicir, 70 00:03:46,890 --> 00:03:50,220 este é un programa que ten un palpebrar rápido, eficaz, 71 00:03:50,220 --> 00:03:51,970 que queda alí esperando para a entrada para ti. 72 00:03:51,970 --> 00:03:53,920 E é a orde interface de liña a través da cal 73 00:03:53,920 --> 00:03:57,650 Vostedes foron a execución de comandos e en definitiva, compilación e logo, executando 74 00:03:57,650 --> 00:03:58,400 programas. 75 00:03:58,400 --> 00:04:01,320 >> Pero Bash é tamén unha programación linguaxe no seguinte sentido. 76 00:04:01,320 --> 00:04:05,460 Vostede sabe que existen comandos como cd e ls e tamén clang e outros, 77 00:04:05,460 --> 00:04:09,580 pero pode definir os seus propios comandos por implementar las en Bash. 78 00:04:09,580 --> 00:04:11,420 Agora non imos entrar en grandes detalles 79 00:04:11,420 --> 00:04:16,089 como a bater a linguaxe de programación, pero sabe, por exemplo, que, no momento, 80 00:04:16,089 --> 00:04:17,607 non hai ningún comando chamado "Ola". 81 00:04:17,607 --> 00:04:19,440 Por iso, se pode atopar en un deses paquetes. 82 00:04:19,440 --> 00:04:20,856 Non está instalado no meu ordenador. 83 00:04:20,856 --> 00:04:21,870 Pregunta ó seu administrador. 84 00:04:21,870 --> 00:04:26,030 Pero se eu quero que haxa un programa de chamado "Ola" en Bash, ou polo meu aviso, 85 00:04:26,030 --> 00:04:30,810 Podo realmente usar unha sintaxe que é así como C. Non é así o mesmo, 86 00:04:30,810 --> 00:04:35,020 pero parece moi semellante a un función, aínda faltan algúns detalles. 87 00:04:35,020 --> 00:04:38,090 Nada parece acontecer, pero agora si escribir "Ola", 88 00:04:38,090 --> 00:04:40,960 realmente pode escribir unha programa, non en C, non en Java, 89 00:04:40,960 --> 00:04:44,280 non noutro programación linguaxe, pero en si Bash. 90 00:04:44,280 --> 00:04:47,630 >> Agora, a clave aquí é que escribín o nome eu quería dar a esta nova orde, 91 00:04:47,630 --> 00:04:50,820 e os parénteses son tamén simbólica de este ser unha función. 92 00:04:50,820 --> 00:04:54,010 Como un aparte, tamén se pode facer o desfrute as cousas, e de feito, mesmo en Mac OS, 93 00:04:54,010 --> 00:04:55,620 este é un programa chamado Terminal. 94 00:04:55,620 --> 00:04:58,800 Vén integrado no de ninguén ordenador que teña un Mac nesta sala, 95 00:04:58,800 --> 00:05:03,640 e pode facer cousas similares en Mac OS, pero pode ir máis aló. 96 00:05:03,640 --> 00:05:07,110 E iso é algo tanxencial, pero é o tipo de diversión. 97 00:05:07,110 --> 00:05:09,715 Remember me hoxe de mañá, cando se pensa sobre iso, 98 00:05:09,715 --> 00:05:13,279 dun pequeno partido que eu adoitaba xogar cun dos ex TFS do CS50 99 00:05:13,279 --> 00:05:16,570 en que en calquera momento ía a pé teclado con a súa pantalla desbloqueado, 100 00:05:16,570 --> 00:05:23,611 Quere executar un comando como isso-- "dicir Hola". 101 00:05:23,611 --> 00:05:26,610 E agora calquera momento el volveu para a súa teclado despois limpar a pantalla 102 00:05:26,610 --> 00:05:27,985 e ía sentir, tentar facer un traballo, 103 00:05:27,985 --> 00:05:29,250 consultar o contido da súa directory-- 104 00:05:29,250 --> 00:05:29,510 >> [AUDIO REPRODUCIÓN] 105 00:05:29,510 --> 00:05:30,010 >> Alô. 106 00:05:30,010 --> 00:05:31,621 107 00:05:31,621 --> 00:05:32,120 Ola. 108 00:05:32,120 --> 00:05:35,030 >> COLUMNA 1: Entón, para ser xusto, non era, en realidade, "Ola". 109 00:05:35,030 --> 00:05:36,894 Xeralmente era algo máis parecido que-- 110 00:05:36,894 --> 00:05:37,560 [AUDIO REPRODUCIÓN] 111 00:05:37,560 --> 00:05:37,750 -Beep. 112 00:05:37,750 --> 00:05:39,320 COLUMNA 1: --aquela I would-- así que o seu ordenador fose 113 00:05:39,320 --> 00:05:42,170 Xuro para el en calquera momento realmente sentouse á do teclado. 114 00:05:42,170 --> 00:05:46,265 E moi rapidamente descubriu non deixar a súa pantalla desbloqueado. 115 00:05:46,265 --> 00:05:48,730 Pero iso suxire o tipo de diversión estúpida que 116 00:05:48,730 --> 00:05:50,210 pode ter algo como Bash. 117 00:05:50,210 --> 00:05:52,770 Pero é un pouco máis serio, con certeza, que iso. 118 00:05:52,770 --> 00:05:57,235 E, de feito, este é un dos A maioría dos erros perigosos e duradeiros 119 00:05:57,235 --> 00:05:58,860 que realmente chegou ao mundo global. 120 00:05:58,860 --> 00:06:02,060 Este erro foi en torno a preto de 20 anos, 121 00:06:02,060 --> 00:06:05,780 e vai ser alcanzado en só un momento da súa relativa simplicidade. 122 00:06:05,780 --> 00:06:07,990 >> Polo tanto, este é un representante manda que se 123 00:06:07,990 --> 00:06:10,448 posuír un Mac, literalmente agora cando ten a súa tapa aberta, 124 00:06:10,448 --> 00:06:12,940 podes probar escribir en que programa chamado Terminal. 125 00:06:12,940 --> 00:06:15,410 Terminal está baixo Aplicacións Utilities-- 126 00:06:15,410 --> 00:06:18,790 Por primeira vez, os usuarios de Windows non ten que preocuparse tanto threat-- especial 127 00:06:18,790 --> 00:06:22,310 pero aqueles de vostedes con Macs pode escribir isto nunha fiestra que vou facer aquí, 128 00:06:22,310 --> 00:06:24,210 e se insire que a este programa 129 00:06:24,210 --> 00:06:28,830 chamado Terminal, como eu vou facer agora, Se ves a palabra "vulnerable" 130 00:06:28,830 --> 00:06:32,200 o ordenador é vulnerables á explotación. 131 00:06:32,200 --> 00:06:33,850 >> Agora, o que iso realmente significa? 132 00:06:33,850 --> 00:06:35,870 E este é recoñecidamente unha sintaxe moi tolo, 133 00:06:35,870 --> 00:06:39,050 pero imos polo menos sacar algúns dos aspectos interesantes. 134 00:06:39,050 --> 00:06:42,567 Polo tanto, hai unha sintaxe parecer algo familiarizado, polo menos, desde o C 135 00:06:42,567 --> 00:06:43,950 e programación en xeral. 136 00:06:43,950 --> 00:06:47,550 Vexo algúns parénteses, punto e coma, claves e tal, 137 00:06:47,550 --> 00:06:50,820 pero verifícase que este cousa estúpida aquí en amarelo 138 00:06:50,820 --> 00:06:53,580 é esencialmente unha función que non fai nada. 139 00:06:53,580 --> 00:06:57,840 Os medios de colon facer nada, ea punto e coma significa deixar de facer nada. 140 00:06:57,840 --> 00:07:00,250 Así, dentro destas claves, o feito de 141 00:07:00,250 --> 00:07:02,440 que eu teño un igual asinar á esquerda, este 142 00:07:02,440 --> 00:07:05,500 É, esencialmente, crear un comando ou dunha variable, 143 00:07:05,500 --> 00:07:09,520 chamado x, e atribuíndolle lle que pouco amarelo de código alí. 144 00:07:09,520 --> 00:07:14,040 Isto podería ser algo así como "echo Ola "ou" dicir bip "ou algo 145 00:07:14,040 --> 00:07:15,120 semellante ao. 146 00:07:15,120 --> 00:07:17,780 Pero teña en conta se os seus ollos vagar máis á dereita, 147 00:07:17,780 --> 00:07:22,150 non hai máis a esta liña de só o fin dese punto e coma. 148 00:07:22,150 --> 00:07:25,160 "Boto vulnerable", e logo ademais hai aínda máis. 149 00:07:25,160 --> 00:07:26,530 Outro punto e coma, o bash-c:. 150 00:07:26,530 --> 00:07:28,120 151 00:07:28,120 --> 00:07:34,050 >> Entón, longa historia curta, esta liña de código é 152 00:07:34,050 --> 00:07:36,660 suficiente para convincente un ordenador que se 153 00:07:36,660 --> 00:07:39,830 vulnerables a facer algo que queres que faga, 154 00:07:39,830 --> 00:07:44,290 porque hai un erro no que Bash aínda Bash debería deixar 155 00:07:44,290 --> 00:07:48,980 liñas de lectura da dereita comando alí despois do texto amarelo, 156 00:07:48,980 --> 00:07:52,520 por un ano de idade erro 20-plus, Bash foi realmente lendo 157 00:07:52,520 --> 00:07:56,780 alén dese punto e coma e fermosa moi facendo o que se di. 158 00:07:56,780 --> 00:07:59,070 >> Entón, cal é a implicación de que, en definitiva? 159 00:07:59,070 --> 00:08:01,340 Eu só dixo "echo Ola" ou "echo vulnerable" 160 00:08:01,340 --> 00:08:05,449 pero que se fixo algo realmente maliciosa, como rm-rf *, 161 00:08:05,449 --> 00:08:07,240 que non pode xa escribiu anteriormente, 162 00:08:07,240 --> 00:08:08,920 e, a verdade, probablemente non debe moi pronto, 163 00:08:08,920 --> 00:08:10,700 porque pode facer unha moitos danos con el. 164 00:08:10,700 --> 00:08:11,210 Por que? 165 00:08:11,210 --> 00:08:12,990 rm fai o que, por suposto? 166 00:08:12,990 --> 00:08:14,270 Eliminar. 167 00:08:14,270 --> 00:08:15,930 * Significa o que? 168 00:08:15,930 --> 00:08:16,430 Todo. 169 00:08:16,430 --> 00:08:18,180 Polo tanto, é un chamado wild card, entón iso significa 170 00:08:18,180 --> 00:08:20,410 borrar todo en o directorio actual. 171 00:08:20,410 --> 00:08:23,379 r pasa para referirse recursiva, o que significa que se o que está excluíndo 172 00:08:23,379 --> 00:08:26,420 é un directorio, e dentro é outros arquivos e outros directorios, 173 00:08:26,420 --> 00:08:28,950 recursivamente mergullo alí e borrar todo isto. 174 00:08:28,950 --> 00:08:31,040 Correo-f é o peor de todos eles. 175 00:08:31,040 --> 00:08:32,580 Alguén sabe o que significa f aquí? 176 00:08:32,580 --> 00:08:33,690 177 00:08:33,690 --> 00:08:34,360 Force. 178 00:08:34,360 --> 00:08:37,830 Así forzar os medios, incluso Se esta é unha mala idea, 179 00:08:37,830 --> 00:08:40,939 facelo sen me avisar para confirmación. 180 00:08:40,939 --> 00:08:43,230 Entón, vostede sabe, nós rimos iso, pero, francamente, eu probablemente 181 00:08:43,230 --> 00:08:44,972 escriba isto varias veces un día, porque a realidade 182 00:08:44,972 --> 00:08:47,210 é que é o camiño máis rápido para eliminar unha morea de cousas. 183 00:08:47,210 --> 00:08:48,590 Pero, aínda que eu teña feito algún dano. 184 00:08:48,590 --> 00:08:53,100 >> Pero se fose para enganar un ordenador para definir algunha variable estúpido 185 00:08:53,100 --> 00:08:56,810 ou función chamada x, mais despois enganar o ordenador en execución 186 00:08:56,810 --> 00:09:00,030 ademais dos límites desa función, ademais punto e coma, 187 00:09:00,030 --> 00:09:04,430 podería realmente enganar un ordenador para realizar algo como rm-rf 188 00:09:04,430 --> 00:09:07,810 ou a orde de correo ou a orde Copiar. 189 00:09:07,810 --> 00:09:11,400 Calquera cousa, literalmente, pode facer co ordenador, sexa borrando arquivos, 190 00:09:11,400 --> 00:09:15,350 a creación de ficheiros, enviar spam a alguén, ataca algún servidor remotamente, 191 00:09:15,350 --> 00:09:17,190 se pode expresar-lo cunha orde, ten 192 00:09:17,190 --> 00:09:19,120 pode enganar un ordenador para facelo. 193 00:09:19,120 --> 00:09:21,510 >> Agora, o que é un exemplo de como pode facelo? 194 00:09:21,510 --> 00:09:24,300 Así, hai unha morea de ordenadores no Bash internet funciona. 195 00:09:24,300 --> 00:09:26,390 Todos os usuarios nos Mac están entre eles. 196 00:09:26,390 --> 00:09:30,390 Unha morea de servidores Linux están entre eles tamén, e servidores Unix. 197 00:09:30,390 --> 00:09:32,630 O Windows novo queda relativamente fóra do gancho 198 00:09:32,630 --> 00:09:34,590 a menos que teña instalado software especial. 199 00:09:34,590 --> 00:09:37,130 Agora unha morea de servidores, polo exemplo, servidores web son executados, 200 00:09:37,130 --> 00:09:39,840 e, de feito, é posible que o Linux máis popular sistema operativo 201 00:09:39,840 --> 00:09:43,060 para rodar en computadores en internet que están servindo páxinas da rede. 202 00:09:43,060 --> 00:09:44,910 Agora, como veremos máis tarde no tempo, cando 203 00:09:44,910 --> 00:09:48,470 envía unha solicitude de seu browser-- Chrome, 204 00:09:48,470 --> 00:09:50,790 Internet Explorer, whatever-- para un servidor remoto, 205 00:09:50,790 --> 00:09:53,730 verifícase que, a pesar de acaba de escribir www.example.com, 206 00:09:53,730 --> 00:09:59,590 seu navegador está enviando unha mensaxe iso é un pouco máis escuro, como este. 207 00:09:59,590 --> 00:10:01,239 >> Pero teña en conta un pouco de algo raro. 208 00:10:01,239 --> 00:10:03,030 As primeiras dúas liñas Nunca vira antes, 209 00:10:03,030 --> 00:10:04,904 pero eles non se parecen particularmente ameazante. 210 00:10:04,904 --> 00:10:08,030 Pero teña en conta o que eu roubei para a terceira liña aquí. 211 00:10:08,030 --> 00:10:13,390 Un bandido foron para enviar unha mensaxe así do seu ordenador 212 00:10:13,390 --> 00:10:17,270 a un Mac ou vulnerable servidor Linux vulnerable, 213 00:10:17,270 --> 00:10:21,580 o curioso é que Bash, que ventá de consola pouco simple, 214 00:10:21,580 --> 00:10:27,450 é omnipresente e moitas veces é Usado para realizar esencialmente 215 00:10:27,450 --> 00:10:30,020 o contido dun mensaxe que recibe. 216 00:10:30,020 --> 00:10:33,490 E por esa lóxica, pode enganar un servidor web, polo que, 217 00:10:33,490 --> 00:10:36,370 enviando algo parecido User-Agent, que xeralmente 218 00:10:36,370 --> 00:10:38,300 se quere dicir o Nome do seu navegador. 219 00:10:38,300 --> 00:10:42,420 User-Agent Chrome, User-Agent Internet Explorer, Firefox User-Agent, este 220 00:10:42,420 --> 00:10:44,590 é só o seu navegador de xeito de identificarse. 221 00:10:44,590 --> 00:10:46,605 Pero se un cara mal moi intelixentemente di: mm-mm, eu son 222 00:10:46,605 --> 00:10:47,930 non vou dicir a vostede o meu navegador é, 223 00:10:47,930 --> 00:10:50,888 Estou en vez de ir a enviarlle esta cousa enigmática-mirando cunha -rf rm 224 00:10:50,888 --> 00:10:55,840 * Nel, pode literalmente enganar un servidor web vulnerable en internet 225 00:10:55,840 --> 00:10:59,055 para realizar o que, en alí para borrar todos os ficheiros. 226 00:10:59,055 --> 00:11:00,930 E, francamente, iso non é mesmo o peor de todo. 227 00:11:00,930 --> 00:11:01,763 Podes facer calquera cousa. 228 00:11:01,763 --> 00:11:04,480 Podería comezar a distribución ataque de denegación de servizo 229 00:11:04,480 --> 00:11:07,030 se enviou esta mensaxe a acios enteiros de servidores web 230 00:11:07,030 --> 00:11:10,256 e despois tiña todos eles descenden, para exemplo, en servidores Harvard.edu, 231 00:11:10,256 --> 00:11:12,130 e pode clasificar de Bang o inferno fóra deles 232 00:11:12,130 --> 00:11:15,490 por un tráfico de rede que se se non, desencadeada por unha cara mal. 233 00:11:15,490 --> 00:11:18,760 >> Entón, longa historia curta, case todos nesta sala que posúe un Mac 234 00:11:18,760 --> 00:11:20,240 é vulnerable a iso. 235 00:11:20,240 --> 00:11:24,100 O consolo é que, a menos que é executando un servidor web no seu portátil, 236 00:11:24,100 --> 00:11:27,780 e, a menos que realmente configurado para que algo así como SSH para el, 237 00:11:27,780 --> 00:11:28,670 está realmente seguro. 238 00:11:28,670 --> 00:11:31,710 É vulnerable, pero non é un tentando entrar no seu portátil, 239 00:11:31,710 --> 00:11:33,290 así pode clasificar de estar seguro. 240 00:11:33,290 --> 00:11:36,210 Con todo, Apple pronto estar a actualizar unha corrección para iso. 241 00:11:36,210 --> 00:11:39,660 O mundo de Linux xa lanzou unha serie de correccións para Fedora e Ubuntu 242 00:11:39,660 --> 00:11:43,790 e outras versións de Linux, e de feito se executar update 50 no dispositivo, 243 00:11:43,790 --> 00:11:45,930 aínda que tamén será actualizados e corrixidos. 244 00:11:45,930 --> 00:11:47,764 Pero iso tampouco ten foi realmente vulnerable, 245 00:11:47,764 --> 00:11:49,804 porque a menos que ten reparou co aparello 246 00:11:49,804 --> 00:11:52,770 e fixo o seu portátil publicamente accesible en Internet, o que non é 247 00:11:52,770 --> 00:11:54,910 Por defecto, vostede ten en realidade, foi bo porque 248 00:11:54,910 --> 00:11:56,890 de cortalumes e outras técnicas. 249 00:11:56,890 --> 00:12:01,000 >> Pero é un exemplo extremo dun erro que vivimos para, literalmente, para 20 250 00:12:01,000 --> 00:12:04,050 anos, e quen sabe se alguén todo este tempo souben sobre iso? 251 00:12:04,050 --> 00:12:06,300 E, de feito, este é un dos os retos fundamentais 252 00:12:06,300 --> 00:12:08,690 que veremos máis tarde na semestre coa seguridade, 253 00:12:08,690 --> 00:12:13,020 é que, así como no mundo real, os mociños están en desvantaxe. 254 00:12:13,020 --> 00:12:16,500 Para manter os bandidos fóra, temos que asegúrese de que cada porta está pechada, 255 00:12:16,500 --> 00:12:20,340 que cada fiestra é segura, que todos os puntos de entrada nunha casa 256 00:12:20,340 --> 00:12:21,980 é seguro para manter os bandidos fóra. 257 00:12:21,980 --> 00:12:26,870 Pero o que o Vila ten que facer para realmente comprometer a súa casa 258 00:12:26,870 --> 00:12:28,200 e rouba-lo? 259 00:12:28,200 --> 00:12:32,574 El ou ela só ten que atopar un desbloqueado porta, unha fiestra rota, ou algo 260 00:12:32,574 --> 00:12:35,240 nese sentido, e é o mesmo en seguridade de ordenadores. 261 00:12:35,240 --> 00:12:37,660 Podemos escribir millóns de liñas de código de programación 262 00:12:37,660 --> 00:12:40,570 e gastar centos ou miles de horas a tentar obtelo correcto, 263 00:12:40,570 --> 00:12:43,370 pero se fai só un erro na corrección, 264 00:12:43,370 --> 00:12:47,030 pode pór todo o sistema e en realidade, neste caso, toda a Internet 265 00:12:47,030 --> 00:12:48,660 e do mundo en perigo. 266 00:12:48,660 --> 00:12:51,950 >> Entón, se quere saber máis sobre iso, vai a esta URL aquí. 267 00:12:51,950 --> 00:12:54,450 Non é necesario unha acción esta noite, a menos que é 268 00:12:54,450 --> 00:12:57,116 entre os que máis cómodo foron executando o seu propio web 269 00:12:57,116 --> 00:12:59,810 servidor, no caso de que vostede debe, que, En realidade, actualizar o seu software. 270 00:12:59,810 --> 00:13:03,244 >> E este é tamén o título de un discurso e, agora, un papel, 271 00:13:03,244 --> 00:13:05,410 que temos conectado na sitio do curso para hoxe. 272 00:13:05,410 --> 00:13:07,600 Foi por un compañeiro chamado Ken Thompson, que 273 00:13:07,600 --> 00:13:10,120 estaba aceptando un famoso premio en ciencia da computación, 274 00:13:10,120 --> 00:13:13,495 e deu a este discurso de algúns anos hai, esencialmente, sobre o mesmo tema. 275 00:13:13,495 --> 00:13:18,250 276 00:13:18,250 --> 00:13:20,520 Preguntar persoas a pregunta, Se realmente 277 00:13:20,520 --> 00:13:23,480 confianza, en definitiva, o software que lle foi dado? 278 00:13:23,480 --> 00:13:26,100 Por exemplo, todos temos escribindo programas, 279 00:13:26,100 --> 00:13:27,820 e estamos compilando los con tinido. 280 00:13:27,820 --> 00:13:31,830 E para o seu coñecemento, escribiu calquera programa de CS50 onde hai 281 00:13:31,830 --> 00:13:35,310 unha porta traseira do tipo, hai un xeito que un cara mal, se executar o programa, 282 00:13:35,310 --> 00:13:37,410 podería asumir o seu ordenador? 283 00:13:37,410 --> 00:13:38,310 Probablemente non, non? 284 00:13:38,310 --> 00:13:40,180 Mario e Greedy e crédito. 285 00:13:40,180 --> 00:13:41,680 Estes son todos moi pequenos programas. 286 00:13:41,680 --> 00:13:43,910 Vostede tería que ser moi mal se o 287 00:13:43,910 --> 00:13:47,310 fixo todo o seu ordenador vulnerable despois de escribir 10 ou 20 liñas de código, 288 00:13:47,310 --> 00:13:49,690 ou, polo menos, algúns descoñecen das implicacións de seguridade. 289 00:13:49,690 --> 00:13:52,023 Agora digo isto de broma, pero imos ver hoxe 290 00:13:52,023 --> 00:13:54,600 e esta semana é realmente moi, moi fácil 291 00:13:54,600 --> 00:13:57,980 ser mal e facer aínda programas curtos vulnerables. 292 00:13:57,980 --> 00:14:02,880 >> Pero, polo de agora, polo menos, entender que a cuestión que se pon aquí 293 00:14:02,880 --> 00:14:04,850 é sobre Clang nun compilador. 294 00:14:04,850 --> 00:14:08,360 Por que fomos confiando Clang nos últimos dous ou tres semanas? 295 00:14:08,360 --> 00:14:12,650 Quen vai dicir que quen escribiu Clang non tiña un "se" condición alí 296 00:14:12,650 --> 00:14:17,680 que, esencialmente, inxectado algúns ceros e aqueles en cada programa que compila 297 00:14:17,680 --> 00:14:21,180 que permitiría a el ou ela o acceso seu ordenador cando está durmindo 298 00:14:21,180 --> 00:14:23,580 ea súa tapa do portátil é aberto e seu ordenador funciona? 299 00:14:23,580 --> 00:14:24,080 Correcto? 300 00:14:24,080 --> 00:14:28,350 Temos este tipo de dereito sistema de honra agora onde nós confío que Clang é legal. 301 00:14:28,350 --> 00:14:30,000 Confía que o aparello é legal. 302 00:14:30,000 --> 00:14:34,430 Confía en que, literalmente, todos os programas no seu Mac ou PC é de confianza. 303 00:14:34,430 --> 00:14:37,510 E como este erro simple indica, mesmo se non é malicioso, 304 00:14:37,510 --> 00:14:40,580 iso non é absolutamente susceptible de ser o caso. 305 00:14:40,580 --> 00:14:42,350 >> Entón ten que estar asustada como o inferno. 306 00:14:42,350 --> 00:14:45,560 Francamente, non hai simples solución a esta outra 307 00:14:45,560 --> 00:14:48,185 que un tipo de conciencia social da crecente complexidade 308 00:14:48,185 --> 00:14:50,310 que estamos a construír encima dos nosos sistemas de ordenador, 309 00:14:50,310 --> 00:14:53,740 e como cada vez máis vulnerables que podería moi ben ser. 310 00:14:53,740 --> 00:14:55,570 >> Agora, co que dixo, Breakout. 311 00:14:55,570 --> 00:14:59,889 Entón Breakout é problema establecer tres, e Breakout é un xogo de outrora 312 00:14:59,889 --> 00:15:02,180 que ten que se lembrar, pero para nós no conxunto de problemas de tres, 313 00:15:02,180 --> 00:15:04,450 que nos permite tomar as cousas de volta ata un entalhe 314 00:15:04,450 --> 00:15:08,880 para que, cando estamos a escribir programas, mesmo nunha fiestra de terminal como este, 315 00:15:08,880 --> 00:15:14,670 podemos realmente executada, en definitiva, programas gráficos non 316 00:15:14,670 --> 00:15:17,800 ao contrario dos que tivemos acceso a en perigo. 317 00:15:17,800 --> 00:15:20,910 Polo tanto, este é o persoal do implantación de Breakout, 318 00:15:20,910 --> 00:15:23,930 que é só iso de salto de ladrillos xogo, que mover a súa raqueta para atrás 319 00:15:23,930 --> 00:15:27,590 e cara atrás, e bater na pelota contra os ladrillos de cores enriba. 320 00:15:27,590 --> 00:15:30,020 Entón, iso está nos levando especie de volta a onde 321 00:15:30,020 --> 00:15:33,180 , Foron capaces de ser moi rápido co Scratch, e agora con C, 322 00:15:33,180 --> 00:15:35,800 implementación da nosa propia interfaces gráficas de usuario. 323 00:15:35,800 --> 00:15:38,960 >> Pero máis que iso, este conxunto representa o primeiro problema 324 00:15:38,960 --> 00:15:41,000 en que estamos dando ti unha morea de código. 325 00:15:41,000 --> 00:15:43,940 E, de feito, eu traio explícita atención para iso, porque sobre todo 326 00:15:43,940 --> 00:15:47,090 para aqueles menos cómodo, este conxunto de problemas, polo menos a primeira vista, 327 00:15:47,090 --> 00:15:49,170 vai sentir como demos-se un entalhe. 328 00:15:49,170 --> 00:15:51,540 Porque che dei, para algunhas das buscas 329 00:15:51,540 --> 00:15:54,930 e clasificar os problemas no pset, unha morea de código que escribiu, 330 00:15:54,930 --> 00:15:56,680 e un par de comentarios que din "facer", 331 00:15:56,680 --> 00:15:58,221 onde ten que encher os espazos en branco. 332 00:15:58,221 --> 00:16:00,020 Entón, non moi asustado, pero é a primeira vez 333 00:16:00,020 --> 00:16:03,370 estamos entregando-lle un código que precisa primeiro ler, entender, e logo, engade a 334 00:16:03,370 --> 00:16:04,290 e completa-lo. 335 00:16:04,290 --> 00:16:05,940 >> E entón, con Breakout, imos facer o mesmo, 336 00:16:05,940 --> 00:16:08,740 dándolle unha ducia de máis liñas de código que, francamente, darlle 337 00:16:08,740 --> 00:16:11,490 unha gran parte do cadro de o xogo pero paran 338 00:16:11,490 --> 00:16:14,304 de aplicar os ladrillos e o balón e na raqueta, 339 00:16:14,304 --> 00:16:15,970 pero facemos aplicar algunhas outras características. 340 00:16:15,970 --> 00:16:18,280 E, aínda que a primeira vista, unha vez máis, especialmente se menos cómodo, 341 00:16:18,280 --> 00:16:21,480 Pode parecer particularmente difícil e Pensas que hai tantas novas funcións 342 00:16:21,480 --> 00:16:24,070 precisa involucrar súa mente ao redor, e iso é verdade. 343 00:16:24,070 --> 00:16:26,281 Pero lembre, é así como do risco. 344 00:16:26,281 --> 00:16:28,780 As probabilidades son que non usar todos as pezas do puzzle en cero. 345 00:16:28,780 --> 00:16:31,120 As probabilidades son que non lle importaba para embrulhar súa mente en torno de todos eles 346 00:16:31,120 --> 00:16:33,617 porque todo o que tiña era unha rápida ollada para comprender, oh, 347 00:16:33,617 --> 00:16:35,450 iso é o que podo facer con esta peza do puzzle. 348 00:16:35,450 --> 00:16:38,260 E, de feito, o conxunto de problemas 3 spec, imos sinala-lo 349 00:16:38,260 --> 00:16:41,370 na documentación que se presenta-lo a novas funcións, 350 00:16:41,370 --> 00:16:43,570 e, finalmente, a programación constrúe usa. 351 00:16:43,570 --> 00:16:47,610 Condicións, lazos, variables e funcións 352 00:16:47,610 --> 00:16:50,720 será o mesmo que o o que vimos ata agora. 353 00:16:50,720 --> 00:16:53,560 >> Entón, en realidade, o que nós imos dar vostede é un código de exemplo que 354 00:16:53,560 --> 00:16:56,110 permite crear un diálogo que non parece, ao contrario diso, 355 00:16:56,110 --> 00:16:59,540 e, finalmente, transformalo en algo parecido con iso. 356 00:16:59,540 --> 00:17:02,250 Entón, aproveitar CS50, discutir o horario de expediente e máis, 357 00:17:02,250 --> 00:17:05,290 e se consolar co feito de que a cantidade de código que ten que escribir 358 00:17:05,290 --> 00:17:06,760 en realidade non é tanto así. 359 00:17:06,760 --> 00:17:10,359 O primeiro reto é para aclimatar -se dalgún código que escribiu. 360 00:17:10,359 --> 00:17:11,450 361 00:17:11,450 --> 00:17:15,810 >> Calquera dúbida sobre pset3, Shellshock, ou doutro xeito? 362 00:17:15,810 --> 00:17:19,226 >> Audiencia: Parecía que pasando con Breakout 363 00:17:19,226 --> 00:17:22,154 que o código é case un estilo orientado a obxectos, 364 00:17:22,154 --> 00:17:24,675 pero eu penso que era un C programa orientado a obxectos. 365 00:17:24,675 --> 00:17:26,050 COLUMNA 1: Unha excelente pregunta. 366 00:17:26,050 --> 00:17:28,258 Así, en mirando a través da código de distribución, o código 367 00:17:28,258 --> 00:17:30,180 escribimos para pset3, para os que están familiarizados, el 368 00:17:30,180 --> 00:17:32,230 Parece que é un pouco orientada a obxectos. 369 00:17:32,230 --> 00:17:33,800 A resposta curta é, é. 370 00:17:33,800 --> 00:17:38,130 É unha aproximación de como pode facer código orientado a obxectos utilizando 371 00:17:38,130 --> 00:17:41,850 unha linguaxe como C, pero é aínda, en definitiva procesual. 372 00:17:41,850 --> 00:17:44,900 Non existen métodos dentro as variables, como vai ver. 373 00:17:44,900 --> 00:17:46,180 Pero lembra-se diso. 374 00:17:46,180 --> 00:17:48,780 E nós imos ver este recurso novo cando chegamos ao PHP e JavaScript 375 00:17:48,780 --> 00:17:49,946 ata o final do semestre. 376 00:17:49,946 --> 00:17:53,667 Pero, por agora, pense nisto como unha información do que está por vir. 377 00:17:53,667 --> 00:17:54,250 Boa pregunta. 378 00:17:54,250 --> 00:17:56,051 379 00:17:56,051 --> 00:17:56,550 Todo correcto. 380 00:17:56,550 --> 00:17:59,730 Entón, merge sort era coma nós cousas deixadas por última vez. 381 00:17:59,730 --> 00:18:03,250 E merge sort foi legal no sentido de que era moito máis rápido, 382 00:18:03,250 --> 00:18:07,100 , Polo menos, con base nos ensaios superficiais fixemos a semana pasada, que, digamos, burbulla 383 00:18:07,100 --> 00:18:08,710 tipo, a selección de clasificación, ordenación por inserción. 384 00:18:08,710 --> 00:18:11,780 E o que era limpo tamén é só como forma sucinta e limpa 385 00:18:11,780 --> 00:18:12,810 pode expresar la. 386 00:18:12,810 --> 00:18:15,840 E o que podemos dicir que foi un superior obrigados, baixo o tempo de execución da fusión 387 00:18:15,840 --> 00:18:16,340 Ordenar? 388 00:18:16,340 --> 00:18:17,633 389 00:18:17,633 --> 00:18:18,495 Si? 390 00:18:18,495 --> 00:18:19,360 >> Audiencia: n log n? 391 00:18:19,360 --> 00:18:20,819 >> COLUMNA 1: n log n, certo. n log n. 392 00:18:20,819 --> 00:18:23,776 E nós imos voltar para o que isto realmente significa é de onde vén iso, 393 00:18:23,776 --> 00:18:25,570 pero este foi mellor que o tempo de execución 394 00:18:25,570 --> 00:18:28,440 que vimos a burbulla selección e inserción tipo? 395 00:18:28,440 --> 00:18:30,610 Entón n ao cadrado. n ao cadrado é maior que iso, 396 00:18:30,610 --> 00:18:34,650 e mesmo se non é evidente, sei que log n é menor que n, 397 00:18:34,650 --> 00:18:36,910 por iso, se fai n veces algo menor que n, 398 00:18:36,910 --> 00:18:38,680 será menor que n ao cadrado. 399 00:18:38,680 --> 00:18:40,130 É un pouco de intuición alí. 400 00:18:40,130 --> 00:18:42,190 Pero pagamos un prezo por iso. 401 00:18:42,190 --> 00:18:47,000 Foi máis rápido, pero un tema que comezou a xurdir a semana pasada foi esa compensación. 402 00:18:47,000 --> 00:18:49,804 Eu teño un mellor desenvolvemento tempo sabio, pero o que 403 00:18:49,804 --> 00:18:52,470 que teño que pasar por outro banda, a fin de conseguir isto? 404 00:18:52,470 --> 00:18:53,591 >> Audiencia: Memoria. 405 00:18:53,591 --> 00:18:54,465 COLUMNA 1: Diga de novo? 406 00:18:54,465 --> 00:18:55,173 Audiencia: Memoria. 407 00:18:55,173 --> 00:18:57,040 COLUMNA 1: Memoria, ou espazo de forma máis xeral. 408 00:18:57,040 --> 00:18:59,040 E non foi super obvia cos seres humanos, 409 00:18:59,040 --> 00:19:02,240 pero recordar que os nosos voluntarios foron avanzando e pisando 410 00:19:02,240 --> 00:19:04,780 de volta como se houbese unha matriz aquí, e como se houbese 411 00:19:04,780 --> 00:19:07,130 un segundo conxunto que aquí eles poderían usar, porque 412 00:19:07,130 --> 00:19:09,080 un lugar necesario para mesturar estas persoas. 413 00:19:09,080 --> 00:19:11,480 Non poderiamos simplemente trocalos no lugar. 414 00:19:11,480 --> 00:19:13,800 Entón, merge sort alavancagem hai máis espazo, que 415 00:19:13,800 --> 00:19:15,620 nós non necesitamos os outros algoritmos, 416 00:19:15,620 --> 00:19:17,410 pero a vantaxe é que é moito máis rápido. 417 00:19:17,410 --> 00:19:20,780 E, francamente, no espazo do mundo real estes RAM dias--, disco duro espaço-- 418 00:19:20,780 --> 00:19:25,030 é relativamente barato, e por iso é non necesariamente unha cousa mala. 419 00:19:25,030 --> 00:19:28,320 >> Entón, imos dar un ollo rápida, algo máis metodicamente, polo o que fixemos 420 00:19:28,320 --> 00:19:30,220 e por iso que dixo que estaba n log n. 421 00:19:30,220 --> 00:19:33,260 Entón aquí están os oito números ea oito voluntarios que tivemos a última vez. 422 00:19:33,260 --> 00:19:35,718 E o primeiro que se funden Ordenar nos dixo para facer o que era? 423 00:19:35,718 --> 00:19:37,010 424 00:19:37,010 --> 00:19:38,010 Audiencia: Divídese en dous. 425 00:19:38,010 --> 00:19:38,663 COLUMNA 1: Diga de novo? 426 00:19:38,663 --> 00:19:39,650 Audiencia: Divídese en dous. 427 00:19:39,650 --> 00:19:40,610 COLUMNA 1: Débeda en dous, seguro. 428 00:19:40,610 --> 00:19:42,818 Isto lembra moito o libro de teléfono, de dividir 429 00:19:42,818 --> 00:19:44,220 e conquistar máis xeral. 430 00:19:44,220 --> 00:19:45,640 Entón, miramos para o lado esquerdo. 431 00:19:45,640 --> 00:19:48,700 E, a continuación, xa dixemos, tipo a metade da esquerda dos elementos, 432 00:19:48,700 --> 00:19:49,690 o que nós fixemos próxima dicir? 433 00:19:49,690 --> 00:19:51,210 434 00:19:51,210 --> 00:19:54,860 Ordena a metade esquerda da esquerda metade, o que nos permitiu, 435 00:19:54,860 --> 00:19:57,570 despois de dividir en dous, concentrarse en catro e dous. 436 00:19:57,570 --> 00:20:01,280 >> Como clasificar unha lista agora, en amarelo, de tamaño dous, utilizando Merge Sort? 437 00:20:01,280 --> 00:20:02,330 438 00:20:02,330 --> 00:20:04,580 Ben división lo ao medio, e clasificar a metade esquerda. 439 00:20:04,580 --> 00:20:07,100 E este era o lugar onde as cousas quedou un pouco brevemente estúpido. 440 00:20:07,100 --> 00:20:10,720 Como clasificar unha lista que é de tamaño un, como este número catro aquí? 441 00:20:10,720 --> 00:20:12,330 442 00:20:12,330 --> 00:20:13,210 É clasificada. 443 00:20:13,210 --> 00:20:14,200 Está feito. 444 00:20:14,200 --> 00:20:17,300 >> Pero entón como clasificar unha lista de un tamaño cando é o número dous? 445 00:20:17,300 --> 00:20:21,640 Ben, o mesmo, pero agora o que era o terceiro eo paso fundamental na Merge Sort? 446 00:20:21,640 --> 00:20:24,020 Vostede tiña que se funden á esquerda metade e metade dereita. 447 00:20:24,020 --> 00:20:26,580 E xa que fixemos iso, nós miramos en catro, nós miramos para dous. 448 00:20:26,580 --> 00:20:28,750 Decidimos todo ben, obviamente dous ven en primeiro lugar, 449 00:20:28,750 --> 00:20:31,840 entón poñemos dous na súa lugar, seguido por catro. 450 00:20:31,840 --> 00:20:35,010 E agora ten que tipo de retroceso, e iso é unha especie de característica 451 00:20:35,010 --> 00:20:37,570 dun algoritmo como Unir Ordenar, retroceder na memoria. 452 00:20:37,570 --> 00:20:40,240 Cal foi a liña seguinte da historia? 453 00:20:40,240 --> 00:20:41,780 O que eu debería estar centrada na próxima? 454 00:20:41,780 --> 00:20:43,110 455 00:20:43,110 --> 00:20:47,350 A metade dereita da esquerda metade, que é de seis e oito anos. 456 00:20:47,350 --> 00:20:50,320 >> Entón deixe-me pasar por este sen belaboring o punto moito. 457 00:20:50,320 --> 00:20:53,330 Seis e oito, a continuación, seis son clasificadas, oito son clasificados. 458 00:20:53,330 --> 00:20:57,190 Fundín-las así, e agora o seguinte gran paso 459 00:20:57,190 --> 00:21:00,990 É, por suposto, ordenar a metade dereita da o primeiro paso deste algoritmo. 460 00:21:00,990 --> 00:21:02,870 Entón, nos concentrados en un, tres, sete, cinco. 461 00:21:02,870 --> 00:21:04,540 Nós, entón, concentrar-se na metade esquerda. 462 00:21:04,540 --> 00:21:09,400 A metade esquerda do que a metade dereita que, a continuación, fundir nun e tres. 463 00:21:09,400 --> 00:21:13,100 A continuación, a metade dereita, despois á esquerda metade do mesmo, a continuación, a metade dereita do mesmo. 464 00:21:13,100 --> 00:21:15,985 Unir-lo, e agora o que paso permanece? 465 00:21:15,985 --> 00:21:18,040 466 00:21:18,040 --> 00:21:22,460 Unir o gran media esquerda eo gran metade dereita, de xeito que un vai alí en baixo, 467 00:21:22,460 --> 00:21:27,330 despois dous, despois tres, despois catro, despois cinco, despois seis, despois sete, despois oito. 468 00:21:27,330 --> 00:21:31,990 >> Entón agora por que isto acaba por revelar, especialmente se n máis e logaritmos 469 00:21:31,990 --> 00:21:35,487 xeralmente bastante escapar de ti, polo menos na memoria recente? 470 00:21:35,487 --> 00:21:37,070 Ben, teña en conta a altura desa cousa. 471 00:21:37,070 --> 00:21:41,230 Tivemos oito elementos, e nós dividido por dous, por dous, por dous. 472 00:21:41,230 --> 00:21:44,590 Entón rexistro base dous dos oito dános tres. 473 00:21:44,590 --> 00:21:45,640 474 00:21:45,640 --> 00:21:48,540 E confiar en min que, se algo vago sobre iso. 475 00:21:48,540 --> 00:21:54,710 Pero rexistro base dous dos oito é tres, así fixemos tres capas de fusión. 476 00:21:54,710 --> 00:21:57,170 E cando se fundiu elementos, cantos elementos 477 00:21:57,170 --> 00:21:58,950 se miramos para cada unha destas liñas? 478 00:21:58,950 --> 00:22:00,212 479 00:22:00,212 --> 00:22:01,437 Un total de n, non? 480 00:22:01,437 --> 00:22:04,020 Porque se fundir a liña superior, aínda que nós fixemos iso aos poucos, 481 00:22:04,020 --> 00:22:05,990 que en definitiva, tocou en cada número unha vez. 482 00:22:05,990 --> 00:22:09,054 E na segunda liña, a mesturar estas listas de tamaño dous, 483 00:22:09,054 --> 00:22:10,470 tivemos que tocar cada elemento unha vez. 484 00:22:10,470 --> 00:22:12,690 E entón aquí realmente claramente na última fila, 485 00:22:12,690 --> 00:22:15,430 tivemos que tocar cada un destes elementos dunha vez, pero só unha vez, 486 00:22:15,430 --> 00:22:18,400 entón aquí está, entón, a nosa log n n. 487 00:22:18,400 --> 00:22:21,780 >> E agora só para facer as cousas un pouco máis formal só por un momento, se 488 00:22:21,780 --> 00:22:24,260 eran agora analizar esta a unha especie de nivel máis alto 489 00:22:24,260 --> 00:22:28,340 e tentar decidir, así como pode ir sobre expresando 490 00:22:28,340 --> 00:22:31,780 o tempo de execución do algoritmo só de ollar para el e non 491 00:22:31,780 --> 00:22:33,590 usando un exemplo inventado? 492 00:22:33,590 --> 00:22:36,590 Ben, canto tempo diría que un paso como este en amarelo levaría, 493 00:22:36,590 --> 00:22:37,173 Se n <2 retorno? 494 00:22:37,173 --> 00:22:38,840 495 00:22:38,840 --> 00:22:39,830 Isto é un gran O de que? 496 00:22:39,830 --> 00:22:41,450 497 00:22:41,450 --> 00:22:44,540 Entón, eu estou a ver un, polo que unha única etapa, quizais dúas etapas porque é se 498 00:22:44,540 --> 00:22:47,110 e despois volver, pero é constante de tempo, non? 499 00:22:47,110 --> 00:22:49,960 Entón nós dixemos O (1), e que se como vou expresar iso. 500 00:22:49,960 --> 00:22:51,480 T, basta ter tempo de execución. 501 00:22:51,480 --> 00:22:54,150 n é o tamaño da entrada, entón T (n), só un xeito elegante 502 00:22:54,150 --> 00:22:56,330 de dicir que o funcionamento dado tempo de entrada de tamaño n 503 00:22:56,330 --> 00:23:00,220 será na orde constante de tempo, en O (1). 504 00:23:00,220 --> 00:23:01,970 >> Pero doutra banda, o que sobre iso? 505 00:23:01,970 --> 00:23:05,660 Como se expresa a tempo desta liña amarela que funcionan? 506 00:23:05,660 --> 00:23:06,250 T de que? 507 00:23:06,250 --> 00:23:09,440 508 00:23:09,440 --> 00:23:12,665 Pode tipo de fraude aquí e responder a miña pregunta cíclica. 509 00:23:12,665 --> 00:23:14,770 510 00:23:14,770 --> 00:23:17,900 Así, se o tempo de funcionamento en xeral que acabamos de dicir é T (n). 511 00:23:17,900 --> 00:23:18,950 512 00:23:18,950 --> 00:23:22,490 E agora está tipo de punt aquí e dicindo, así, só ordenar a metade esquerda, 513 00:23:22,490 --> 00:23:23,920 e, a continuación, clasificar a metade dereita. 514 00:23:23,920 --> 00:23:27,520 Como podemos representar simbólicamente o tempo de execución desta liña amarela? 515 00:23:27,520 --> 00:23:28,020 T de que? 516 00:23:28,020 --> 00:23:29,360 Cal é o tamaño da entrada? 517 00:23:29,360 --> 00:23:30,510 518 00:23:30,510 --> 00:23:31,057 n máis de dous. 519 00:23:31,057 --> 00:23:32,140 Por que non dixo iso? 520 00:23:32,140 --> 00:23:36,449 E, a continuación, esta é outra T (n / 2) e, a continuación, de novo, se eu fundir dúas metades ordenada, 521 00:23:36,449 --> 00:23:38,615 cantos elementos é que eu vou ter que tocar todo? 522 00:23:38,615 --> 00:23:39,780 523 00:23:39,780 --> 00:23:40,320 n. 524 00:23:40,320 --> 00:23:42,790 Para que eu poida expresar isto, só para ser unha especie de fantasía, 525 00:23:42,790 --> 00:23:44,430 como o tempo de funcionamento en xeral. 526 00:23:44,430 --> 00:23:51,140 T (n) é só o tempo de execución T (n / 2), ademais de T (n / 2), deixou metade e metade dereita, 527 00:23:51,140 --> 00:23:55,360 ademais S (n), que é, probablemente, n pasos, pero quizais, se eu estou a usar dous dedos, 528 00:23:55,360 --> 00:23:57,960 é o dobre pasos, pero é lineal. 529 00:23:57,960 --> 00:24:00,440 É unha serie de pasos iso é un factor de n, 530 00:24:00,440 --> 00:24:02,270 así podemos expresalo como este. 531 00:24:02,270 --> 00:24:05,550 E é aí que agora imos chutar a traseira do noso libro de matemáticas do ensino medio 532 00:24:05,550 --> 00:24:10,290 estamos en definitiva, que a recorrencia termínase igual a este, n veces log n, 533 00:24:10,290 --> 00:24:12,530 se realmente facer a a matemática máis formal. 534 00:24:12,530 --> 00:24:13,950 >> Entón, iso é só dúas perspectivas. 535 00:24:13,950 --> 00:24:17,500 Unha numericamente cun codificado exemplo representativo 536 00:24:17,500 --> 00:24:21,140 usando oito números e un máis ollo xeral como chegamos alí. 537 00:24:21,140 --> 00:24:25,670 Pero o que é realmente interesante aquí é, unha vez máis, esta noción de ciclismo. 538 00:24:25,670 --> 00:24:26,900 Eu non estou a usar para loops. 539 00:24:26,900 --> 00:24:29,860 Eu son o tipo de definición algo en termos de si mesmo, 540 00:24:29,860 --> 00:24:31,950 Non só coa presente función matemática, 541 00:24:31,950 --> 00:24:34,860 pero tamén en termos de este código pseudo. 542 00:24:34,860 --> 00:24:38,260 Este código pseudo é recursiva en que dúas das súas liñas 543 00:24:38,260 --> 00:24:42,310 é, esencialmente, dicindo-lle para ir utilizarse para resolver un menor 544 00:24:42,310 --> 00:24:45,400 problema de menor tamaño, e, a continuación, unha e outra vez 545 00:24:45,400 --> 00:24:48,820 e de novo ata que tallar ata este chamado caso base. 546 00:24:48,820 --> 00:24:52,810 >> Entón, imos realmente tomar un máis atractivo take-away de iso do seguinte xeito. 547 00:24:52,810 --> 00:24:58,420 Deixe-me ir en gedit e un ollar para algúns dos código fonte de hoxe, 548 00:24:58,420 --> 00:24:59,930 en particular, este exemplo aquí. 549 00:24:59,930 --> 00:25:03,709 Sigma 0, que, ao parecer aumenta os números de un a n. 550 00:25:03,709 --> 00:25:05,750 Entón imos ver o que é familiar e descoñecido aquí. 551 00:25:05,750 --> 00:25:08,690 En primeiro lugar, temos un par de inclúe, polo tanto, nada novo nisto. 552 00:25:08,690 --> 00:25:09,190 Prototype. 553 00:25:09,190 --> 00:25:11,370 Eu son un pouco vago sobre isto despois de algúns días, 554 00:25:11,370 --> 00:25:13,790 pero o que dicimos un prototipo dunha función é? 555 00:25:13,790 --> 00:25:15,099 556 00:25:15,099 --> 00:25:16,015 Audiencia: [inaudível]. 557 00:25:16,015 --> 00:25:16,905 COLUMNA 1: ¿Que é iso? 558 00:25:16,905 --> 00:25:17,800 Audiencia: Nós anunciala-lo. 559 00:25:17,800 --> 00:25:18,883 COLUMNA 1: Nós anunciala-lo. 560 00:25:18,883 --> 00:25:22,290 Entón, está ensinando Clang, hey, non realmente aplicar iso aínda, 561 00:25:22,290 --> 00:25:25,740 pero en algún lugar neste ficheiro, presuntamente, vai ser unha función chamada que? 562 00:25:25,740 --> 00:25:26,930 563 00:25:26,930 --> 00:25:27,540 Sigma. 564 00:25:27,540 --> 00:25:30,540 E esta é só unha promesa de que que vai mirar como esta. 565 00:25:30,540 --> 00:25:33,720 Vai levar un enteiro como input-- e podo ser máis explícito 566 00:25:33,720 --> 00:25:36,570 e dicir int n -E é devolverá un int, 567 00:25:36,570 --> 00:25:39,900 pero medio punto e coma, mm, eu vou dar a volta para aplicar esta un pouco máis tarde. 568 00:25:39,900 --> 00:25:40,989 Unha vez máis, Clang é burro. 569 00:25:40,989 --> 00:25:43,280 El só vai saber o que diga a el de arriba abaixo, 570 00:25:43,280 --> 00:25:45,765 por iso necesitamos polo menos dar unha información do que está por vir. 571 00:25:45,765 --> 00:25:47,330 >> Agora imos ollar para o principal aquí. 572 00:25:47,330 --> 00:25:50,040 Imos rolar para abaixo aquí e ver o principal está facendo. 573 00:25:50,040 --> 00:25:53,780 Non é que a longo dunha función, e en realidade, a construción aquí é familiar. 574 00:25:53,780 --> 00:25:57,590 Eu declaro unha variable n, e despois Eu importunar o usuario novo e de novo 575 00:25:57,590 --> 00:26:01,880 a un número enteiro positivo usando getInt, e só saír fóra deste circuíto 576 00:26:01,880 --> 00:26:03,280 xa que o usuario teña cumprido. 577 00:26:03,280 --> 00:26:05,670 Do While, que usan para importunar ao usuario dese xeito. 578 00:26:05,670 --> 00:26:06,670 Agora isto é interesante. 579 00:26:06,670 --> 00:26:08,510 Declaro un int chamado "resposta". 580 00:26:08,510 --> 00:26:11,420 Eu atribuílo lo o valor de retorno dunha función chamada "sigma". 581 00:26:11,420 --> 00:26:15,200 Eu non sei o que iso fai aínda, pero Lembro declarar que un momento atrás. 582 00:26:15,200 --> 00:26:18,310 E entón eu estou pasando no valor que o usuario inseriu, n, 583 00:26:18,310 --> 00:26:20,420 e entón eu informar a resposta. 584 00:26:20,420 --> 00:26:22,260 Ben, imos rodar atrás por só un momento. 585 00:26:22,260 --> 00:26:28,620 Imos adiante neste directorio, facer sigma 0, e realmente executar este programa 586 00:26:28,620 --> 00:26:30,490 e ver que pasa. 587 00:26:30,490 --> 00:26:35,930 Entón, se eu ir adiante e executar Neste programa, ./sigma-0, 588 00:26:35,930 --> 00:26:40,139 e eu escribir un positivo enteiro como dous, Sigma, 589 00:26:40,139 --> 00:26:43,180 como símbolo grego indica, é só vai sumar todos os números de 590 00:26:43,180 --> 00:26:44,320 zerar en ata dous. 591 00:26:44,320 --> 00:26:46,560 Así 0 máis 1 máis 2. 592 00:26:46,560 --> 00:26:48,830 Polo tanto, este debe espero darme 3. 593 00:26:48,830 --> 00:26:49,750 Isto é todo o que está facendo. 594 00:26:49,750 --> 00:26:52,690 E do mesmo xeito, se eu executar isto de novo e eu darlle o número de tres, 595 00:26:52,690 --> 00:26:56,721 iso é 3 + 2, de xeito que é 5, máis 1 debería darme 6. 596 00:26:56,721 --> 00:26:59,470 E entón se eu ficar moito tolo e comezar a escribir en números grandes, 597 00:26:59,470 --> 00:27:01,290 debe darme sumas cada vez maiores. 598 00:27:01,290 --> 00:27:02,250 Entón, iso é todo. 599 00:27:02,250 --> 00:27:04,010 >> Entón, o que sigma parece? 600 00:27:04,010 --> 00:27:05,430 Ben, é moi sinxelo. 601 00:27:05,430 --> 00:27:08,940 É como poderiamos ter implantado isto para o último par de semanas. 602 00:27:08,940 --> 00:27:11,120 "Int" será o tipo de retorno. 603 00:27:11,120 --> 00:27:14,330 Sigma é o nome, e hai que m dunha variable no canto de n. 604 00:27:14,330 --> 00:27:15,940 Vou cambiar isto enriba. 605 00:27:15,940 --> 00:27:17,340 Entón este é só unha proba de sanidade. 606 00:27:17,340 --> 00:27:18,430 607 00:27:18,430 --> 00:27:19,950 Vexamos por que en un momento. 608 00:27:19,950 --> 00:27:24,220 Agora eu declarar outra variable, suma, inicialize-o a cero. 609 00:27:24,220 --> 00:27:28,140 Entón eu teño ese loop iteración, aparentemente, para maior claridade, 610 00:27:28,140 --> 00:27:33,810 desde i = 1 enriba dun m =, que é todo o que o usuario inseriu, e entón eu 611 00:27:33,810 --> 00:27:35,690 incrementar a suma así. 612 00:27:35,690 --> 00:27:37,360 E, a continuación, voltar a suma. 613 00:27:37,360 --> 00:27:38,440 >> Así, un par de preguntas. 614 00:27:38,440 --> 00:27:42,370 Un, eu afirmo no meu comentario que esta evita risco dun loop infinito. 615 00:27:42,370 --> 00:27:45,620 Por que pasar en un número negativo inducir, potencialmente, un loop infinito? 616 00:27:45,620 --> 00:27:49,396 617 00:27:49,396 --> 00:27:51,290 >> Audiencia: Vostede non vai chegar a m. 618 00:27:51,290 --> 00:27:52,880 >> COLUMNA 1: Nunca chegar m. 619 00:27:52,880 --> 00:27:55,880 Pero m é pasado, entón imos Considero un exemplo simple. 620 00:27:55,880 --> 00:27:58,510 Se m é pasado polo usuario como un negativo. 621 00:27:58,510 --> 00:28:00,059 Independentemente do principal. 622 00:28:00,059 --> 00:28:01,850 Iniciar nos protexe de iso tamén, entón eu son só 623 00:28:01,850 --> 00:28:04,680 sendo moi anal con sigma tamén asegurarse de 624 00:28:04,680 --> 00:28:06,540 que a entrada non pode ser negativa. 625 00:28:06,540 --> 00:28:10,130 Polo tanto, se m é negativa, algo así como un negativo. 626 00:28:10,130 --> 00:28:11,930 O que vai ocorrer? 627 00:28:11,930 --> 00:28:14,390 Ben, eu vai se inicializar con un, 628 00:28:14,390 --> 00:28:19,060 e entón eu será inferior ou igual a m? 629 00:28:19,060 --> 00:28:24,130 630 00:28:24,130 --> 00:28:24,765 >> Estar por. 631 00:28:24,765 --> 00:28:26,930 632 00:28:26,930 --> 00:28:29,370 Isto estava-- non imos, imos nix esta historia. 633 00:28:29,370 --> 00:28:32,780 Eu non pedín a esta pregunta, porque o risco que estou aludindo 634 00:28:32,780 --> 00:28:38,360 non vai ocorrer, porque é sempre será maior Aceptar than--, 635 00:28:38,360 --> 00:28:39,871 Eu retiro a esta pregunta. 636 00:28:39,871 --> 00:28:40,370 Está ben. 637 00:28:40,370 --> 00:28:42,030 Imos centrar só esta parte aquí. 638 00:28:42,030 --> 00:28:44,210 639 00:28:44,210 --> 00:28:48,830 Por que eu declarar algún fóra do loop? 640 00:28:48,830 --> 00:28:52,010 Aviso en liña 49 eu teño declarado i interior do lazo, 641 00:28:52,010 --> 00:28:54,950 pero en liña 48 eu teño declarou algúns fóra. 642 00:28:54,950 --> 00:28:55,695 Si. 643 00:28:55,695 --> 00:28:56,611 Audiencia: [inaudível]. 644 00:28:56,611 --> 00:28:58,734 645 00:28:58,734 --> 00:28:59,400 COLUMNA 1: Claro. 646 00:28:59,400 --> 00:29:03,360 Entón, en primeiro lugar, eu certamente non quero declarar e arrincar suma 647 00:29:03,360 --> 00:29:06,130 a cero no interior da circuíto en cada iteración, 648 00:29:06,130 --> 00:29:09,370 porque iso ía derrotar claramente a propósito de sumar os números. 649 00:29:09,370 --> 00:29:11,770 Quere estar cambiando o valor de volta a cero. 650 00:29:11,770 --> 00:29:17,992 E tamén, o que é outro máis arcanos razón para esa mesma decisión deseño? 651 00:29:17,992 --> 00:29:18,954 Si. 652 00:29:18,954 --> 00:29:20,279 >> Audiencia: [inaudível]. 653 00:29:20,279 --> 00:29:21,070 COLUMNA 1: Exactamente. 654 00:29:21,070 --> 00:29:24,060 Quero acceder a ela fóra do lazo tamén en que liña? 655 00:29:24,060 --> 00:29:25,390 656 00:29:25,390 --> 00:29:26,400 En 53. 657 00:29:26,400 --> 00:29:29,910 E en base a nosa regra de ouro dende un par de conferencias atrás, 658 00:29:29,910 --> 00:29:33,680 variables son alcance, realmente, ao claves que abranguen. 659 00:29:33,680 --> 00:29:38,190 Entón, se eu non declarar suma dentro desas claves externas, 660 00:29:38,190 --> 00:29:40,250 Eu non podo usalo na liña 53. 661 00:29:40,250 --> 00:29:43,160 Dito doutro xeito, se eu declarei suma aquí, ou incluso dentro do 662 00:29:43,160 --> 00:29:45,410 Para loop, eu non podía acceder a ela en 53. 663 00:29:45,410 --> 00:29:47,150 A variable que efectivamente desaparecido. 664 00:29:47,150 --> 00:29:48,579 Así, un par de razóns alí. 665 00:29:48,579 --> 00:29:50,370 Pero agora imos volver e ver que pasa. 666 00:29:50,370 --> 00:29:51,730 Entón sigma é chamada. 667 00:29:51,730 --> 00:29:55,640 Engade-se 1 máis 2 ou 1 máis 2 máis 3, e logo retorna o valor, 668 00:29:55,640 --> 00:29:59,660 almacena en resposta, e printf aquí É por iso que eu estou a ver na pantalla. 669 00:29:59,660 --> 00:30:03,079 Entón é iso que nós imos chamar unha iterativo visión, onde só iteración 670 00:30:03,079 --> 00:30:03,870 significa usar un loop. 671 00:30:03,870 --> 00:30:06,900 Un loop, un loop while, un Do While loop, só facendo algo de novo 672 00:30:06,900 --> 00:30:08,380 e de novo e de novo. 673 00:30:08,380 --> 00:30:13,505 >> Pero sigma é un tipo de función puro en que eu podería implementar lo de forma diferente. 674 00:30:13,505 --> 00:30:14,620 675 00:30:14,620 --> 00:30:19,120 E sobre iso, o que só para ser ben legal, 676 00:30:19,120 --> 00:30:21,880 déixeme realmente se librar dunha gran cantidade de distracción 677 00:30:21,880 --> 00:30:24,380 porque esta función É realmente moi simple. 678 00:30:24,380 --> 00:30:27,780 Imos tallar-lo só aos seus catro liñas centrais 679 00:30:27,780 --> 00:30:30,410 e se librar de toda a comentarios e chaves. 680 00:30:30,410 --> 00:30:34,334 Esta é unha especie de alucinante execución alternativa. 681 00:30:34,334 --> 00:30:37,250 Todo ben, quizais non alucinante, pero é o tipo de máis sexy, todo ben, 682 00:30:37,250 --> 00:30:39,920 de ollar para este moito máis sucinta. 683 00:30:39,920 --> 00:30:43,120 Con só catro liñas de código, A primeira vez que teño esa proba de sanidade. 684 00:30:43,120 --> 00:30:45,732 Se m é igual ou inferior a cero, sigma non ten sentido. 685 00:30:45,732 --> 00:30:48,190 É só debería estar en Neste caso, a números positivos, 686 00:30:48,190 --> 00:30:50,340 entón eu só vou volver cero arbitrariamente 687 00:30:50,340 --> 00:30:53,210 para que, polo menos, ter algúns chamados caso base. 688 00:30:53,210 --> 00:30:54,430 >> Pero aquí está a beleza. 689 00:30:54,430 --> 00:30:59,930 A totalidade desa idea, engadindo que o os números entre 1 e n, ou m, neste caso, 690 00:30:59,930 --> 00:31:02,630 se pode facer a través de pasar o balón. 691 00:31:02,630 --> 00:31:04,947 Ben, o que é a suma de 1 a m? 692 00:31:04,947 --> 00:31:05,780 Ben, vostede sabe o que? 693 00:31:05,780 --> 00:31:11,949 É o mesmo que a suma de m máis a suma de 1 a menos 1 m. 694 00:31:11,949 --> 00:31:12,740 Ben, vostede sabe o que? 695 00:31:12,740 --> 00:31:13,940 O que hai de sigma de m menos 1? 696 00:31:13,940 --> 00:31:17,860 Ben, se seguir este tipo de loxicamente, é o mesmo que m menos 1 697 00:31:17,860 --> 00:31:21,415 ademais de sigma de m menos 2. 698 00:31:21,415 --> 00:31:22,480 699 00:31:22,480 --> 00:31:26,012 Así, pode tipo de apenas-- isto é así, se está só 700 00:31:26,012 --> 00:31:28,220 intentando irritar correo e eles lle facer unha pregunta, 701 00:31:28,220 --> 00:31:31,344 vostede medio que responder con unha pregunta, pode tipo de manter pasar o balón. 702 00:31:31,344 --> 00:31:34,560 Pero o que é importante é que se continúa facer a pregunta menor e menor 703 00:31:34,560 --> 00:31:36,910 e menor, está non preguntar o que hai de sigma 704 00:31:36,910 --> 00:31:39,116 de n, o que é sigma de n, o que é sigma de n? 705 00:31:39,116 --> 00:31:40,990 Está facendo o que é sigma de n, o que é sigma 706 00:31:40,990 --> 00:31:42,839 de n menos 1, o que é sigma de n menos 2? 707 00:31:42,839 --> 00:31:44,880 Finalmente a súa pregunta vai chegar a ser o que? 708 00:31:44,880 --> 00:31:50,250 Que é de unha ou sigma cero, un valor moi pequeno, 709 00:31:50,250 --> 00:31:52,220 e así que conseguir isto, o seu amigo, 710 00:31:52,220 --> 00:31:54,350 non vai preguntar a mesma pregunta de novo, 711 00:31:54,350 --> 00:31:55,975 está indo só para dicir, ah, é cero. 712 00:31:55,975 --> 00:31:58,490 Somos feitos de xogar este tipo de xogo cíclico estúpido. 713 00:31:58,490 --> 00:32:02,950 >> Entón recursividade é o acto en programación dunha función que se autodenomina. 714 00:32:02,950 --> 00:32:06,630 Este programa, cando compilado e executado, é vai comportarse exactamente do mesmo xeito, 715 00:32:06,630 --> 00:32:09,620 pero o que é importante é que dentro dunha función chamada sigma, 716 00:32:09,620 --> 00:32:13,150 hai unha liña de código, en que estamos chamando a nós mesmos, 717 00:32:13,150 --> 00:32:14,980 que normalmente se mal. 718 00:32:14,980 --> 00:32:21,160 Por exemplo, se eu primeiro compilou este, así que sigma-- 719 00:32:21,160 --> 00:32:22,710 facer sigma 1 ./sigma-1. 720 00:32:22,710 --> 00:32:25,050 721 00:32:25,050 --> 00:32:27,690 Enteiro positivo, por favor, 50 1275. 722 00:32:27,690 --> 00:32:30,810 Entón, cal é a función parece ser, en base a unha proba, correcta. 723 00:32:30,810 --> 00:32:34,917 Pero e se eu ir un pouco perigoso e eliminar o chamado caso base, 724 00:32:34,917 --> 00:32:37,750 e dicir, ben, eu só estou facendo iso é máis complicado do que é. 725 00:32:37,750 --> 00:32:42,450 Imos calcular o sigma tomando m e, a continuación, engadindo 726 00:32:42,450 --> 00:32:44,564 en sigma m de menos un? 727 00:32:44,564 --> 00:32:45,980 Ben, o que vai pasar aquí? 728 00:32:45,980 --> 00:32:47,140 Imos diminuír o zoom. 729 00:32:47,140 --> 00:32:52,920 Imos recompilar o programa, salvalo, recompilar o programa, 730 00:32:52,920 --> 00:33:00,450 e entón preparado ./sigma-1 ampliar, entrar enteiro positivo, por favor, 50. 731 00:33:00,450 --> 00:33:02,180 732 00:33:02,180 --> 00:33:04,430 Cantos de vostedes están dispostos para confesar que ver iso? 733 00:33:04,430 --> 00:33:04,950 >> Está ben. 734 00:33:04,950 --> 00:33:06,690 Entón isto pode ocorrer por un certo número de razóns, 735 00:33:06,690 --> 00:33:09,148 e, a verdade, esta semana estamos a punto de darlle un deles. 736 00:33:09,148 --> 00:33:11,780 Pero, neste caso, proba razoar atrás 737 00:33:11,780 --> 00:33:14,430 o que podería acontecer aquí? 738 00:33:14,430 --> 00:33:17,400 Fallo de segmentación, que dixo no último tempo, refírese a un segmento de memoria. 739 00:33:17,400 --> 00:33:18,690 Algo malo ocorreu. 740 00:33:18,690 --> 00:33:21,550 Pero o que era mecánicamente que non deu correcto 741 00:33:21,550 --> 00:33:25,000 aquí por mor da miña retirada de que o chamado caso base, 742 00:33:25,000 --> 00:33:26,870 onde volvín un valor incorporado? 743 00:33:26,870 --> 00:33:28,970 744 00:33:28,970 --> 00:33:30,460 ¿Que pensas que deu mal? 745 00:33:30,460 --> 00:33:31,219 Si. 746 00:33:31,219 --> 00:33:32,135 >> Audiencia: [inaudível]. 747 00:33:32,135 --> 00:33:36,387 748 00:33:36,387 --> 00:33:36,970 COLUMNA 1: Ah. 749 00:33:36,970 --> 00:33:37,550 Boa pregunta. 750 00:33:37,550 --> 00:33:39,508 Así, o tamaño do número que eu estaba resumindo 751 00:33:39,508 --> 00:33:41,920 quedou tan grande que superou o tamaño do espazo de memoria. 752 00:33:41,920 --> 00:33:44,640 Boa idea, pero non fundamentalmente vai causar un accidente. 753 00:33:44,640 --> 00:33:48,230 Isto pode causar estourido de enteiros, onde os bits simplemente virar 754 00:33:48,230 --> 00:33:51,760 e logo, nos confundimos realmente un gran número de como un número negativo, 755 00:33:51,760 --> 00:33:53,260 pero iso en si non vai causar un accidente. 756 00:33:53,260 --> 00:33:55,509 Porque, ao final do día un int aínda é de 32 bits. 757 00:33:55,509 --> 00:33:57,640 Non vai accidentalmente roubar algo 33. 758 00:33:57,640 --> 00:33:58,431 Pero un bo pensamento. 759 00:33:58,431 --> 00:33:58,984 Si. 760 00:33:58,984 --> 00:33:59,900 >> Audiencia: [inaudível]. 761 00:33:59,900 --> 00:34:00,551 762 00:34:00,551 --> 00:34:02,300 COLUMNA 1: O método nunca deixa de funcionar, 763 00:34:02,300 --> 00:34:06,658 e, de feito, chámase a si mesmo de novo e de novo e de novo e de novo 764 00:34:06,658 --> 00:34:08,449 e unha vez máis, e ningunha as funcións de todos os tempos 765 00:34:08,449 --> 00:34:13,310 rematar, pois o seu único liña de código chama a si mesmos unha e outra vez 766 00:34:13,310 --> 00:34:14,219 e de novo. 767 00:34:14,219 --> 00:34:16,080 E o que é realmente pasando aquí, e agora nós 768 00:34:16,080 --> 00:34:18,100 pode tipo de deseñar ese pictoricamente. 769 00:34:18,100 --> 00:34:20,899 Deixade-me pasar un imaxe por só un momento. 770 00:34:20,899 --> 00:34:22,940 Esta é unha imaxe, que acabará por detallar 771 00:34:22,940 --> 00:34:26,336 con máis detalle, do que está a suceder dentro da memoria do seu ordenador. 772 00:34:26,336 --> 00:34:28,460 E verifícase que en a parte inferior da imaxe 773 00:34:28,460 --> 00:34:29,709 é algo chamado de pila. 774 00:34:29,709 --> 00:34:31,920 Este é un anaco de memoria, unha peza de memoria RAM, 775 00:34:31,920 --> 00:34:33,920 que só é usado en calquera momento unha función é chamada. 776 00:34:33,920 --> 00:34:36,239 Cada vez que, programador, chamar unha función, 777 00:34:36,239 --> 00:34:38,860 o sistema operativo, como Mac OS, Windows ou Linux, 778 00:34:38,860 --> 00:34:41,920 colle unha morea de bytes, quizais un poucos kilobytes, pode que algúns megabytes 779 00:34:41,920 --> 00:34:44,590 de memoria, os entrega para ti, e entón permite 780 00:34:44,590 --> 00:34:47,650 realizar a súa función a usar o que quere que as variables que necesitas. 781 00:34:47,650 --> 00:34:50,699 E se, a continuación, chamar outro función e outra función, 782 00:34:50,699 --> 00:34:53,590 comeza outra porción de memoria e outra porción de memoria. 783 00:34:53,590 --> 00:34:57,090 >> E, de feito, se estas bandexas verdes de Annenberg representan a memoria, 784 00:34:57,090 --> 00:34:59,870 aquí está o que acontece por primeira vez que chamar función sigma. 785 00:34:59,870 --> 00:35:04,510 É como poñer nunha bandexa como esta sobre o que é inicialmente unha pila baleira. 786 00:35:04,510 --> 00:35:07,142 Pero, entón, se esa bandexa chama-se, por así dicir, 787 00:35:07,142 --> 00:35:08,850 chamando outra instancia de sigma, que é 788 00:35:08,850 --> 00:35:11,640 como preguntar o sistema operativo, ooh, precisa un pouco máis de memoria, 789 00:35:11,640 --> 00:35:12,520 me que dar. 790 00:35:12,520 --> 00:35:14,840 E entón el fica amoreado en na parte superior. 791 00:35:14,840 --> 00:35:18,030 Pero o que é importante aquí é que a primeira bandexa aínda está alí, 792 00:35:18,030 --> 00:35:20,620 porque invocou esta segunda bandexa. 793 00:35:20,620 --> 00:35:23,500 Agora, con todo, chamar sigma sigma, Isto é como preguntar a máis memoria. 794 00:35:23,500 --> 00:35:25,830 Queda empilhado enriba aquí. 795 00:35:25,830 --> 00:35:29,350 sigma chamar sigma, que é outro bandexa que queda empilhado aquí. 796 00:35:29,350 --> 00:35:32,942 E se continúa facendo iso, finalmente, tipo de mapear este visual 797 00:35:32,942 --> 00:35:35,525 para este gráfico, o que vai pasar coa pila de bandexas? 798 00:35:35,525 --> 00:35:37,480 799 00:35:37,480 --> 00:35:41,160 Que vai ser superior o importe de memoria do ordenador. 800 00:35:41,160 --> 00:35:45,790 E así que esta bandexa verde supera a liña horizontal 801 00:35:45,790 --> 00:35:49,410 arriba pila e por riba desa palabra chea, que imos volver no futuro, 802 00:35:49,410 --> 00:35:50,410 que é unha cousa mala. 803 00:35:50,410 --> 00:35:52,810 A pila é un diferente segmento de memoria, 804 00:35:52,810 --> 00:35:55,190 e se deixar que estes bandexas de pila e pila en, 805 00:35:55,190 --> 00:35:57,800 vai superar seu propio segmento de memoria, 806 00:35:57,800 --> 00:36:00,420 e un programa é de feito vai fallar. 807 00:36:00,420 --> 00:36:02,930 >> Agora, como un aparte, esta idea de recursividade, polo tanto, 808 00:36:02,930 --> 00:36:06,500 pode claramente levar a problemas, pero non é necesariamente unha cousa mala. 809 00:36:06,500 --> 00:36:08,840 Por considerar, despois todo, e quizais how-- 810 00:36:08,840 --> 00:36:11,700 isto leva moito tempo para se acostumar • Como a elegante ou como simple 811 00:36:11,700 --> 00:36:14,890 que a posta en marcha do sigma foi. 812 00:36:14,890 --> 00:36:17,440 E nós non imos usar recursão moito nos CS50, 813 00:36:17,440 --> 00:36:20,780 pero en CS51, e realmente calquera clase onde manipular estruturas de datos 814 00:36:20,780 --> 00:36:23,640 como árbores ou árbores genealógicas, que teñen algunha xerarquía, 815 00:36:23,640 --> 00:36:26,000 el é super, super útil. 816 00:36:26,000 --> 00:36:29,750 Agora, como un aparte, para que como aspirantes a científicos da computación 817 00:36:29,750 --> 00:36:33,180 está familiarizado con algúns dos Google bromas, se vai a Google 818 00:36:33,180 --> 00:36:36,345 e mira para o que está a definición de, digamos, a recursão, escriba. 819 00:36:36,345 --> 00:36:40,208 820 00:36:40,208 --> 00:36:41,110 Uh-huh. 821 00:36:41,110 --> 00:36:42,670 Como un aparte, eu puxei un pouco. 822 00:36:42,670 --> 00:36:45,470 Iso foi como 10 minutos de procrastinação esta mañá. 823 00:36:45,470 --> 00:36:52,890 Se tamén Google "torto", previo inclinando a cabeza slightly-- 824 00:36:52,890 --> 00:36:55,120 e entón que é, se cadra, máis atroz de todos 825 00:36:55,120 --> 00:36:57,286 sempre que alguén pasou como seu día de aplicación do presente 826 00:36:57,286 --> 00:36:59,880 algúns anos ago-- imos. 827 00:36:59,880 --> 00:37:01,140 828 00:37:01,140 --> 00:37:04,540 Oh, wait-- iso é un erro. 829 00:37:04,540 --> 00:37:08,410 830 00:37:08,410 --> 00:37:11,410 >> Así sendo executado nun dos maiores sitios do mundo 831 00:37:11,410 --> 00:37:13,510 son eses ovos de Pascua estúpidos. 832 00:37:13,510 --> 00:37:16,690 Probablemente consumir unha número non trivial de liñas de código 833 00:37:16,690 --> 00:37:19,280 só para que poidamos ter pequenas cousas divertidas como esta. 834 00:37:19,280 --> 00:37:22,140 Pero polo menos agora comeza algunhas desas bromas. 835 00:37:22,140 --> 00:37:28,330 >> Agora imos dar un ollo a algunhas das branco mentiras que vimos dicir nos últimos tempos, 836 00:37:28,330 --> 00:37:30,707 e comezar a pelar algunhas capas tecnicamente 837 00:37:30,707 --> 00:37:32,790 de xeito que realmente entender o que está pasando 838 00:37:32,790 --> 00:37:34,860 e pode entender algunhas das ameazas, 839 00:37:34,860 --> 00:37:38,060 como Shellshock, que xa comezou a facer 840 00:37:38,060 --> 00:37:41,110 na vangarda de todo o mundo atención, polo menos nos medios de comunicación. 841 00:37:41,110 --> 00:37:45,810 Entón aquí está unha función moi sinxelo que retorna nada, baleiro. 842 00:37:45,810 --> 00:37:46,790 O seu nome é de intercambio. 843 00:37:46,790 --> 00:37:50,880 Leva en dúas variables e el retorna nada. 844 00:37:50,880 --> 00:37:52,260 Leva en ae b. 845 00:37:52,260 --> 00:37:53,337 Entón, unha rápida demostración. 846 00:37:53,337 --> 00:37:54,170 Trouxo estes anterior. 847 00:37:54,170 --> 00:37:56,100 Podemos moi ben ter un pouco romper aquí por só un momento 848 00:37:56,100 --> 00:37:57,250 e ter un pouco de algo para beber. 849 00:37:57,250 --> 00:38:00,120 Se alguén non lle importaría unirse me ata aquí só por un momento. 850 00:38:00,120 --> 00:38:01,830 E como a vostede coa camisa marrón? 851 00:38:01,830 --> 00:38:02,335 Imos cara arriba. 852 00:38:02,335 --> 00:38:04,060 853 00:38:04,060 --> 00:38:05,260 Só o de hoxe. 854 00:38:05,260 --> 00:38:06,251 Grazas, con todo. 855 00:38:06,251 --> 00:38:08,000 Todo ben, e temos chegando que aquí? 856 00:38:08,000 --> 00:38:08,660 Cal é o seu nome? 857 00:38:08,660 --> 00:38:09,360 >> COLUMNA 4: Laura. 858 00:38:09,360 --> 00:38:09,740 >> COLUMNA 1: Laura. 859 00:38:09,740 --> 00:38:10,370 Imos cara arriba. 860 00:38:10,370 --> 00:38:11,460 861 00:38:11,460 --> 00:38:13,850 Entón Laura, reto moi sinxelo hoxe. 862 00:38:13,850 --> 00:38:14,704 863 00:38:14,704 --> 00:38:15,370 Pracer en coñece-yo. 864 00:38:15,370 --> 00:38:16,410 865 00:38:16,410 --> 00:38:16,910 Todo correcto. 866 00:38:16,910 --> 00:38:21,179 Polo tanto, temos un pouco de leite ata aquí e temos un pouco de zume de laranxa aquí 867 00:38:21,179 --> 00:38:23,345 e algúns vasos que prestado de Annenberg hoxe. 868 00:38:23,345 --> 00:38:24,178 >> COLUMNA 4: prestado. 869 00:38:24,178 --> 00:38:27,240 COLUMNA 1: E indo para adiante e darlle a metade dun vaso de agasallo. 870 00:38:27,240 --> 00:38:28,250 871 00:38:28,250 --> 00:38:28,800 Todo correcto. 872 00:38:28,800 --> 00:38:30,750 E nós imos dar-lle a metade un vaso de leite. 873 00:38:30,750 --> 00:38:31,905 874 00:38:31,905 --> 00:38:35,890 Ah, e só para que poida lembre que este era como, 875 00:38:35,890 --> 00:38:38,860 Remember me de traer iso e hoxe. 876 00:38:38,860 --> 00:38:42,030 877 00:38:42,030 --> 00:38:42,530 Ok. 878 00:38:42,530 --> 00:38:45,470 Se non lle importa, imos ver, nós pode poñer-los sobre os seus propios lentes 879 00:38:45,470 --> 00:38:46,560 se quere. 880 00:38:46,560 --> 00:38:48,710 Este será o mundo de ollos de Laura. 881 00:38:48,710 --> 00:38:49,210 Todo correcto. 882 00:38:49,210 --> 00:38:53,820 Polo tanto, o seu obxectivo, dado dúas cuncas de líquido aquí, leite e zume de laranxa, 883 00:38:53,820 --> 00:38:58,370 é cambiar os dous contidos de xeito que a zume de laranxa vai á cunca de leite 884 00:38:58,370 --> 00:39:00,710 e leite pasa a o vaso de zume de laranxa. 885 00:39:00,710 --> 00:39:02,359 >> COLUMNA 4: Eu recibín outro vaso? 886 00:39:02,359 --> 00:39:05,650 COLUMNA 1: Estou tan feliz que preguntou, aínda que sería moito mellor rodaxe 887 00:39:05,650 --> 00:39:06,710 se non tivese pedido. 888 00:39:06,710 --> 00:39:10,620 Pero si, podemos ofrecer-lle un terceiro vaso que está baleiro, por suposto. 889 00:39:10,620 --> 00:39:11,120 Todo correcto. 890 00:39:11,120 --> 00:39:12,300 Entón cambiar o contido alí. 891 00:39:12,300 --> 00:39:16,100 892 00:39:16,100 --> 00:39:17,050 Moi bo. 893 00:39:17,050 --> 00:39:20,390 894 00:39:20,390 --> 00:39:21,305 Moi bo. 895 00:39:21,305 --> 00:39:23,121 896 00:39:23,121 --> 00:39:24,745 Está facendo iso moi coidado. 897 00:39:24,745 --> 00:39:26,970 898 00:39:26,970 --> 00:39:28,655 E o paso tres. 899 00:39:28,655 --> 00:39:30,390 900 00:39:30,390 --> 00:39:31,350 Todo correcto. 901 00:39:31,350 --> 00:39:31,930 Excelente. 902 00:39:31,930 --> 00:39:33,930 Un gran aplauso sería bo para Laura. 903 00:39:33,930 --> 00:39:36,500 904 00:39:36,500 --> 00:39:37,000 Todo correcto. 905 00:39:37,000 --> 00:39:40,790 Temos un pequeno agasallo de despedida para ti, pero deixe-me leva-los. 906 00:39:40,790 --> 00:39:42,620 Moitas grazas. 907 00:39:42,620 --> 00:39:46,170 Así, un exemplo simple, con todo, para demostrar que, se fai 908 00:39:46,170 --> 00:39:48,300 quere cambiar o contido de dous recipientes, 909 00:39:48,300 --> 00:39:52,360 ou imos chamalos de variables, precisa dalgún almacenamento temporal 910 00:39:52,360 --> 00:39:56,710 encenar un dos contidos en que realmente pode facer o intercambio. 911 00:39:56,710 --> 00:40:01,790 Entón, en realidade, este código fonte aquí en C é representativa de exactamente isto. 912 00:40:01,790 --> 00:40:06,340 Se o zume de laranxa era un eo leite era b, e queriamos cambiar os dous, 913 00:40:06,340 --> 00:40:08,990 podería tentar algo creativo vertendo-se unhas ás outras, 914 00:40:08,990 --> 00:40:11,031 pero que seguramente non acabar particularmente ben. 915 00:40:11,031 --> 00:40:15,260 E, así, usar un vaso terceira, chamada el tmp, T-M-P, por convención, 916 00:40:15,260 --> 00:40:19,370 e poñer o contido do DO en que, a continuación, cambiar un vaso, 917 00:40:19,370 --> 00:40:22,610 logo poñer o DO na vaso orixinais, así 918 00:40:22,610 --> 00:40:25,320 acadar, exactamente como Laura fixo, o intercambio. 919 00:40:25,320 --> 00:40:26,850 >> Entón, imos facer exactamente isto. 920 00:40:26,850 --> 00:40:30,110 Deixe-me ir adiante e abrir -se un exemplo de que é 921 00:40:30,110 --> 00:40:32,720 en realidade, chámase "non Intercambio ", porque este non é 922 00:40:32,720 --> 00:40:36,180 como simplemente feito como se podería pensar. 923 00:40:36,180 --> 00:40:41,190 Entón, neste programa, teña en conta que Está a usar stdio.h, o noso vello amigo. 924 00:40:41,190 --> 00:40:43,130 Eu teño o prototipo para cambiar alí enriba, o que 925 00:40:43,130 --> 00:40:45,450 significa a súa implementación probablemente a continuación, 926 00:40:45,450 --> 00:40:48,050 e imos ver o que este principal programa vai facer por min. 927 00:40:48,050 --> 00:40:52,020 A primeira vez que declarar int x recibe un, e int y recibe dous. 928 00:40:52,020 --> 00:40:54,930 Entón, creo que os que DO e leite, respectivamente. 929 00:40:54,930 --> 00:40:57,100 E entón eu só teño un printf dicindo x é este 930 00:40:57,100 --> 00:41:00,120 e y é iso, só para que eu poida visualmente ver o que está pasando. 931 00:41:00,120 --> 00:41:03,810 Así que printf reivindicando que estou cambiando os dous, 932 00:41:03,810 --> 00:41:07,100 e entón eu imprimir un afirman que son trocadas, 933 00:41:07,100 --> 00:41:09,300 e eu imprimir x e y de novo. 934 00:41:09,300 --> 00:41:13,010 Entón, aquí en intercambio é o que Laura fixo, 935 00:41:13,010 --> 00:41:16,240 e exactamente o que vimos en a pantalla dun momento atrás. 936 00:41:16,240 --> 00:41:19,380 >> Entón, imos adiante e unha gran desilusión. 937 00:41:19,380 --> 00:41:24,690 Non cambio, e non corre intercambio, zoom sobre a saída aquí. 938 00:41:24,690 --> 00:41:28,320 Escriba x é 1, y é 2, cambiando trocados. 939 00:41:28,320 --> 00:41:32,700 aínda x é 1, e y é aínda 2. 940 00:41:32,700 --> 00:41:37,630 Así, aínda que, a verdade, iso parece exactamente como, aínda máis tecnicamente, 941 00:41:37,630 --> 00:41:40,730 Laura o que fixo, non parece funcionar. 942 00:41:40,730 --> 00:41:42,130 Entón, por que isto? 943 00:41:42,130 --> 00:41:46,630 Ben, acontece que cando escribimos un programa como este 944 00:41:46,630 --> 00:41:51,590 que ten tanto principal, destacamos aquí, e logo, outra función, como intercambio, 945 00:41:51,590 --> 00:41:54,230 Destácanse aquí, que chama, o mundo 946 00:41:54,230 --> 00:41:57,030 parece un pouco algo como estas bandexas hai pouco. 947 00:41:57,030 --> 00:42:00,440 Cando principal en primeiro lugar se chama, Isto é como preguntar sistema operativo 948 00:42:00,440 --> 00:42:04,030 para un pouco de memoria para calquera lugar, variables como xe y que a principal ten, 949 00:42:04,030 --> 00:42:05,660 e eles acaban por aí. 950 00:42:05,660 --> 00:42:10,920 Pero, se as chamadas principais cambiar, e principal pasa para intercambiar dous argumentos, a e b, 951 00:42:10,920 --> 00:42:16,410 zume de laranxa e leite, non é como entregando o zume de laranxa eo leite 952 00:42:16,410 --> 00:42:17,500 para Laura. 953 00:42:17,500 --> 00:42:21,300 Que un ordenador fai, é pasa copias do zume de laranxa 954 00:42:21,300 --> 00:42:27,110 e copias do leite para Laura, de xeito que o que é, en definitiva neste bandexa 955 00:42:27,110 --> 00:42:32,510 é o valor dun e dous, ou DO e leite, pero copias dos mesmos, 956 00:42:32,510 --> 00:42:34,790 de xeito que, neste punto na historia, non 957 00:42:34,790 --> 00:42:36,930 é DO e leite en cada unha destas bandexas. 958 00:42:36,930 --> 00:42:39,260 Hai un un e dous en cada unha destas bandexas, 959 00:42:39,260 --> 00:42:41,720 ea función de intercambio é de feito a traballar. 960 00:42:41,720 --> 00:42:46,090 Está cambiando-os por dentro de bandexa o segundo máis alto, 961 00:42:46,090 --> 00:42:48,147 pero que a cambio non ten impacto. 962 00:42:48,147 --> 00:42:49,980 E en base a só algunhas principio básico temos 963 00:42:49,980 --> 00:42:52,970 falamos antes, e de feito a poucos minutos, o que 964 00:42:52,970 --> 00:42:58,770 podería explicar por que cambiar a eb dentro intercambio 965 00:42:58,770 --> 00:43:05,560 non ten efecto sobre xe y, aínda Pase xe y para a función de intercambio. 966 00:43:05,560 --> 00:43:08,750 Cal é a palabra clave aquí que pode simplista explicar? 967 00:43:08,750 --> 00:43:11,250 968 00:43:11,250 --> 00:43:12,627 Creo que oín-lo aquí? 969 00:43:12,627 --> 00:43:13,335 Audiencia: Return. 970 00:43:13,335 --> 00:43:14,085 COLUMNA 1: Retorno? 971 00:43:14,085 --> 00:43:14,590 Non volver. 972 00:43:14,590 --> 00:43:15,895 Imos con outro. 973 00:43:15,895 --> 00:43:16,395 ¿Que é iso? 974 00:43:16,395 --> 00:43:17,080 >> Audiencia: [inaudível]. 975 00:43:17,080 --> 00:43:20,000 >> COLUMNA 1: OK, entón return-- puidésemos facer o traballo de retorno na historia, 976 00:43:20,000 --> 00:43:21,914 pero hai unha explicación aínda máis simple. 977 00:43:21,914 --> 00:43:22,580 Audiencia: Scope. 978 00:43:22,580 --> 00:43:23,288 COLUMNA 1: Ámbito. 979 00:43:23,288 --> 00:43:24,300 Vou levar ámbito. 980 00:43:24,300 --> 00:43:27,290 Entón alcance, lembre que a x e y declarada. 981 00:43:27,290 --> 00:43:30,840 Están declaradas dentro de principal ata aquí. 982 00:43:30,840 --> 00:43:33,200 a eb, con todo, son efectivamente declarado 983 00:43:33,200 --> 00:43:35,930 dentro de intercambio, non exactamente as claves, pero aínda 984 00:43:35,930 --> 00:43:37,690 na área xeral de intercambio. 985 00:43:37,690 --> 00:43:40,560 E así, de feito, a e b só existen dentro desa bandexa 986 00:43:40,560 --> 00:43:44,850 de Annenberg, esta segunda parte do código. 987 00:43:44,850 --> 00:43:49,500 Entón, nós estamos cambiando a copia, pero iso non é realmente todo o que útil. 988 00:43:49,500 --> 00:43:52,190 >> Entón, imos dar un ollo este nivel un pouco inferior. 989 00:43:52,190 --> 00:43:55,430 Vou volver o directorio de orixe, 990 00:43:55,430 --> 00:43:58,330 e eu estou indo para a primeira zoom aquí, e só 991 00:43:58,330 --> 00:44:02,290 para confirmar que estou nesta fiestra de terminal grande, 992 00:44:02,290 --> 00:44:04,430 o programa aínda está comportándose así. 993 00:44:04,430 --> 00:44:06,840 Supoña agora que este non é intencional. 994 00:44:06,840 --> 00:44:10,090 Claramente eu quería intercambio para traballo, polo que se sente como un erro. 995 00:44:10,090 --> 00:44:12,780 Agora eu podería comezar a engadir un Moitas printf do para o meu código, 996 00:44:12,780 --> 00:44:16,010 imprimir x aquí, y sobre aquí, un alí, b aquí. 997 00:44:16,010 --> 00:44:18,220 Pero, francamente, iso é probablemente o que ten feito por un par de semanas 998 00:44:18,220 --> 00:44:20,190 agora, no horario de oficina e na casa cando se traballa 999 00:44:20,190 --> 00:44:22,150 en Serie de exercicios intentando atopar algúns erros. 1000 00:44:22,150 --> 00:44:25,560 Pero vai ver, se non ten, que conxunto de problemas presenta tres 1001 00:44:25,560 --> 00:44:31,630 para un comando chamado GDB, onde GDB, depurador GNU, 1002 00:44:31,630 --> 00:44:34,040 ten-se unha morea de recursos que poden, de feito, 1003 00:44:34,040 --> 00:44:38,160 imos entender situacións como este, pero máis convincente, 1004 00:44:38,160 --> 00:44:39,940 resolver problemas e atopar erros. 1005 00:44:39,940 --> 00:44:40,940 Entón, eu vou facer iso. 1006 00:44:40,940 --> 00:44:44,770 No canto de ./noswap, estou vez vai executar GDB ./noswap. 1007 00:44:44,770 --> 00:44:47,410 1008 00:44:47,410 --> 00:44:51,200 Noutras palabras, eu estou indo a executar o meu programa non en Bash, o noso novo amigo 1009 00:44:51,200 --> 00:44:51,850 hoxe. 1010 00:44:51,850 --> 00:44:53,970 Eu estou indo a executar o meu programa noswap dentro 1011 00:44:53,970 --> 00:44:56,900 deste outro programa chamado GDB, que é un depurador, que 1012 00:44:56,900 --> 00:45:01,035 é un programa que foi deseñado para axudar Vós, humanos, atopar e eliminar erros. 1013 00:45:01,035 --> 00:45:03,410 Entón, se eu bater correr aquí, hai unha cantidade atroz de texto 1014 00:45:03,410 --> 00:45:04,868 que realmente non ten que ler. 1015 00:45:04,868 --> 00:45:07,290 É esencialmente unha distracción a partir da liña, que 1016 00:45:07,290 --> 00:45:10,030 Vou bater Control-L para chegar ao cumio alí. 1017 00:45:10,030 --> 00:45:11,800 Este é o poder GDB. 1018 00:45:11,800 --> 00:45:15,550 Se eu queira executar este programa agora, como esta pequena folla de fraude en hoxe 1019 00:45:15,550 --> 00:45:21,860 diapositivas suxire, run é o primeiro ordena que pretendía introducir. 1020 00:45:21,860 --> 00:45:25,150 E eu estou indo só para escribir correr ata aquí dentro GDB, 1021 00:45:25,150 --> 00:45:26,811 e de feito el foi o meu programa. 1022 00:45:26,811 --> 00:45:29,310 Agora hai algún adicional saídas da pantalla como esta, 1023 00:45:29,310 --> 00:45:31,910 pero iso é GDB só sendo anal e nos dicir o que está a suceder. 1024 00:45:31,910 --> 00:45:34,451 Realmente non se preocupe sobre estes detalles agora mesmo. 1025 00:45:34,451 --> 00:45:36,890 Pero o que é realmente legal sobre GDB, se eu fai iso novamente-- 1026 00:45:36,890 --> 00:45:42,100 Control-L limpa o screen-- déixeme ir adiante e escriba "romper principal", así, 1027 00:45:42,100 --> 00:45:45,743 cando prema Intro, definindo o que é chamado un punto de ruptura na noswap.c, 1028 00:45:45,743 --> 00:45:51,270 liña 16, que é onde GDB descubrín o meu programa, en realidade, 1029 00:45:51,270 --> 00:45:53,070 é, a miña función é realmente. 1030 00:45:53,070 --> 00:45:55,070 Isto imos ignorar por agora pero ese é o enderezo 1031 00:45:55,070 --> 00:45:57,310 na memoria especificamente desta función. 1032 00:45:57,310 --> 00:46:00,240 Entón agora cando tecleo correr, entender o que é legal aquí. 1033 00:46:00,240 --> 00:46:05,650 O meu programa quebra na liña I dixo GDB para deter a execución en. 1034 00:46:05,650 --> 00:46:09,850 Entón eu non teño que cambiar agora meu código, engadir algúns printf de, recompilar, reprise 1035 00:46:09,850 --> 00:46:13,300 el, cambiar, engadir algúns printf do, salvalo, recompilar, executalo. 1036 00:46:13,300 --> 00:46:18,100 Só podo andar a través do meu programa paso a paso a paso na velocidade humana, 1037 00:46:18,100 --> 00:46:20,880 non no tipo Intel dentro da velocidade. 1038 00:46:20,880 --> 00:46:24,580 >> Entón agora entender esta liña aparece aquí, e se eu volver 1039 00:46:24,580 --> 00:46:27,800 ao meu programa no gedit, entender que iso é verdade 1040 00:46:27,800 --> 00:46:29,280 a primeira liña de código. 1041 00:46:29,280 --> 00:46:31,240 Hai liña 16 en gedit. 1042 00:46:31,240 --> 00:46:34,610 Hai liña 16 en GDB, e mesmo aínda que esta interface en branco e negro 1043 00:46:34,610 --> 00:46:37,760 non é tan usuario agradable, isto significa 1044 00:46:37,760 --> 00:46:41,680 que a liña 16 non foi executado aínda, pero que está a piques de ser. 1045 00:46:41,680 --> 00:46:46,220 Entón, en realidade, se eu escribir impresión x, non printf, só print x, 1046 00:46:46,220 --> 00:46:50,730 Recibo algún valor falso alí de cero, porque x aínda non foi inicializado. 1047 00:46:50,730 --> 00:46:54,760 Entón eu vou escribir a continuación, ou, se quere ser extravagante, só n para o próximo. 1048 00:46:54,760 --> 00:46:59,090 Pero cando eu tecleo seguinte entra agora ter en conta que se move sobre a liña 17. 1049 00:46:59,090 --> 00:47:02,840 Entón, loxicamente, se eu tivera executado liña 16 e agora estou a escribir print x, 1050 00:47:02,840 --> 00:47:03,640 o que debo ver? 1051 00:47:03,640 --> 00:47:04,970 1052 00:47:04,970 --> 00:47:05,520 Unha. 1053 00:47:05,520 --> 00:47:07,820 >> E agora ese é recoñecidamente confuso. 1054 00:47:07,820 --> 00:47:11,260 Dous dólares é só un xeito elegante de si quero referirse a ese valor máis tarde, 1055 00:47:11,260 --> 00:47:12,510 pode dicir "sinal de dólar dous." 1056 00:47:12,510 --> 00:47:13,480 É como unha referencia para atrás. 1057 00:47:13,480 --> 00:47:14,570 Pero, polo de agora, só ignore-lo. 1058 00:47:14,570 --> 00:47:17,070 O que é interesante é o que se á dereita do signo igual. 1059 00:47:17,070 --> 00:47:21,000 E agora si escribir seguinte novo e imprimir y, eu debería ver 2. 1060 00:47:21,000 --> 00:47:23,870 Eu tamén xa pode imprimir x de novo, e, francamente, 1061 00:47:23,870 --> 00:47:27,130 se eu estou quedando un pouco confuso en canto ao onde estou, podo tipo de lista para lista 1062 00:47:27,130 --> 00:47:30,590 e só ver algún contexto arredor o punto que eu estou realmente en. 1063 00:47:30,590 --> 00:47:35,180 E agora podo escribir xunto, e non é x 1. 1064 00:47:35,180 --> 00:47:36,300 Agora eu tecleo seguinte. 1065 00:47:36,300 --> 00:47:37,710 Oh, y é 2. 1066 00:47:37,710 --> 00:47:40,750 E unha vez máis, é confuso, porque a produción do GDB 1067 00:47:40,750 --> 00:47:43,044 está a ser mesturados coa miña propia saída. 1068 00:47:43,044 --> 00:47:45,710 Pero se manter presente, por mirando cara atrás e cara adiante no seu código 1069 00:47:45,710 --> 00:47:47,740 ou poñendo-o para fóra do lado a banda, quizais, vai 1070 00:47:47,740 --> 00:47:51,020 ver que realmente eu son só percorrendo o meu programa. 1071 00:47:51,020 --> 00:47:54,620 >> Pero teña en conta o que pasa a continuación, literalmente. 1072 00:47:54,620 --> 00:47:56,380 Aquí está a liña 22. 1073 00:47:56,380 --> 00:48:01,315 Déixeme ir sobre el, movendo-se, así, en a 23, e se eu imprimir x agora, aínda un. 1074 00:48:01,315 --> 00:48:03,890 E se eu imprimir y agora, aínda un. 1075 00:48:03,890 --> 00:48:05,820 Polo tanto, este non é un exercicio útil. 1076 00:48:05,820 --> 00:48:07,450 Entón, imos refacer iso. 1077 00:48:07,450 --> 00:48:10,069 Déixeme volver ata o tirada superior e tipo de novo. 1078 00:48:10,069 --> 00:48:12,110 E está dicindo o programa que está a ser depurado 1079 00:48:12,110 --> 00:48:14,109 xa comezou, iniciado a partir do inicio. 1080 00:48:14,109 --> 00:48:15,420 Si, imos facelo de novo. 1081 00:48:15,420 --> 00:48:22,000 E esta vez imos facer a continuación, next, next, next, next, 1082 00:48:22,000 --> 00:48:24,180 pero agora as cousas comezan a estar interesantes. 1083 00:48:24,180 --> 00:48:27,760 Agora quero entrar intercambio, entón eu non escribir a continuación. 1084 00:48:27,760 --> 00:48:34,380 Eu tecleo paso, e agora entende que me saltou a liña noswap.c 33. 1085 00:48:34,380 --> 00:48:37,240 Se eu atrás para o gedit, o que é liña 33? 1086 00:48:37,240 --> 00:48:40,500 Esta é a primeira real liña de código dentro intercambio. 1087 00:48:40,500 --> 00:48:44,150 O que é bo, porque agora podo tipo de fuçar e estar curioso 1088 00:48:44,150 --> 00:48:46,052 sobre o que está pasando realmente alí. 1089 00:48:46,052 --> 00:48:46,760 Déixeme imprimir tmp. 1090 00:48:46,760 --> 00:48:47,770 1091 00:48:47,770 --> 00:48:48,800 Whoa. 1092 00:48:48,800 --> 00:48:51,438 Por que ter algún tmp tolo, valor de lixo falso? 1093 00:48:51,438 --> 00:48:54,579 1094 00:48:54,579 --> 00:48:56,120 Audiencia: Non se inicializar. 1095 00:48:56,120 --> 00:48:57,150 COLUMNA 1: Non se inicializar. 1096 00:48:57,150 --> 00:49:00,270 E, de feito, cando executar un programa, está dado unha chea de memoria 1097 00:49:00,270 --> 00:49:03,392 polo sistema operativo, pero non inicializou calquera valores, 1098 00:49:03,392 --> 00:49:05,600 entón o que está bocados ver aquí, aínda que sexa 1099 00:49:05,600 --> 00:49:07,770 este gran negativo tolo número, significa só 1100 00:49:07,770 --> 00:49:10,750 que aqueles que son os restos algún uso anterior de que a memoria RAM, 1101 00:49:10,750 --> 00:49:13,050 a pesar de eu non ter eu precisaba diso aínda. 1102 00:49:13,050 --> 00:49:17,086 Entón agora eu estou indo a ir adiante e tipo seguinte, e se eu agora escriba impresión tmp, 1103 00:49:17,086 --> 00:49:17,835 o que debo ver? 1104 00:49:17,835 --> 00:49:19,570 1105 00:49:19,570 --> 00:49:23,360 Sexa cal sexa o valor de a foi, un é o primeiro argumento, só 1106 00:49:23,360 --> 00:49:25,550 como x foi a primeira que está a ser transmitido, 1107 00:49:25,550 --> 00:49:30,450 así un e x debe ser o mesmo, así imprimir tmp debe imprimir-me un. 1108 00:49:30,450 --> 00:49:36,360 >> Entón, o que podes ver no conxunto de problemas tres é un tutorial das sortes no GDB, 1109 00:49:36,360 --> 00:49:40,020 pero entende que este é o comezo de un ollo a unha ferramenta que vai realmente 1110 00:49:40,020 --> 00:49:42,774 axudar a resolver problemas forma moito máis eficaz. 1111 00:49:42,774 --> 00:49:44,690 O que estamos, en última instancia fará o mércores 1112 00:49:44,690 --> 00:49:48,180 é comezar a descascada algunhas capas e eliminar algunhas Rodas pequenas. 1113 00:49:48,180 --> 00:49:50,496 Esa cousa chamada cadea que temos utilizado durante algún tempo, 1114 00:49:50,496 --> 00:49:53,370 imos tomar lentamente que lonxe de ti e comezar a falar 1115 00:49:53,370 --> 00:49:55,725 algo máis esotericamente coñecido como char *, 1116 00:49:55,725 --> 00:49:59,550 pero imos facelo agradable e suavemente en primeiro lugar, aínda que os punteiros, 1117 00:49:59,550 --> 00:50:02,730 como son chamados, poden facer algunha cousas moi malas vítimas de abuso, 1118 00:50:02,730 --> 00:50:06,040 mirando un pouco de claymation noso amigo Nick parlante de Stanford 1119 00:50:06,040 --> 00:50:09,670 Universidade, profesor en ordenador ciencia que montar ese previsualización 1120 00:50:09,670 --> 00:50:11,075 do que está por vir este mércores. 1121 00:50:11,075 --> 00:50:12,196 1122 00:50:12,196 --> 00:50:13,400 >> [REPRODUCIÓN] 1123 00:50:13,400 --> 00:50:13,900 Ei, Binky. 1124 00:50:13,900 --> 00:50:14,930 1125 00:50:14,930 --> 00:50:15,780 Acorde. 1126 00:50:15,780 --> 00:50:17,240 É hora de diversión punteiro. 1127 00:50:17,240 --> 00:50:18,260 1128 00:50:18,260 --> 00:50:19,350 >> -Cal Que é iso? 1129 00:50:19,350 --> 00:50:21,150 Máis información sobre punteiros? 1130 00:50:21,150 --> 00:50:22,050 Ah, que bo! 1131 00:50:22,050 --> 00:50:22,897 1132 00:50:22,897 --> 00:50:23,730 [FIN REPRODUCIÓN DE VIDEO] 1133 00:50:23,730 --> 00:50:25,396 COLUMNA 1: Que espera por ti en mércores. 1134 00:50:25,396 --> 00:50:26,440 Imos velo axiña. 1135 00:50:26,440 --> 00:50:27,106 [REPRODUCIÓN] 1136 00:50:27,106 --> 00:50:30,420 -E Agora pensamentos profundos, por Daven Farnham. 1137 00:50:30,420 --> 00:50:33,980 1138 00:50:33,980 --> 00:50:35,900 >> Por que estamos aprendendo C? 1139 00:50:35,900 --> 00:50:36,785 Por que non a +? 1140 00:50:36,785 --> 00:50:38,550 1141 00:50:38,550 --> 00:50:40,910 >> [Risas] 1142 00:50:40,910 --> 00:50:42,160 >> [FIN REPRODUCIÓN DE VIDEO]