1
00:00:00,000 --> 00:00:00,030

2
00:00:00,030 --> 00:00:00,460
>> DAVID MALAN: Très bien.

3
00:00:00,460 --> 00:00:01,094
Nous sommes de retour.

4
00:00:01,094 --> 00:00:04,260
Donc, dans ce segment sur la programmation ce
Je pensais que nous ferions est un mélange de choses.

5
00:00:04,260 --> 00:00:06,340
Un, faire un peu
de quelque chose pratique,

6
00:00:06,340 --> 00:00:08,690
mais en utilisant une plus ludique
environment-- de programmation

7
00:00:08,690 --> 00:00:11,620
celui qui est démonstratif
exactement le genre d'idées

8
00:00:11,620 --> 00:00:14,220
nous avons parlé,
mais un peu plus formelle.

9
00:00:14,220 --> 00:00:18,200
Deux, regardons quelques-uns des
les moyens plus techniques

10
00:00:18,200 --> 00:00:21,520
qu'un programmeur serait effectivement résoudre
des problèmes tels que le problème de recherche

11
00:00:21,520 --> 00:00:24,530
que nous avons examiné avant et
aussi plus fondamentalement

12
00:00:24,530 --> 00:00:26,020
problème intéressant de tri.

13
00:00:26,020 --> 00:00:28,840
>> Nous supposions dès le départ
que ce répertoire a été réglé,

14
00:00:28,840 --> 00:00:31,980
mais ce seul est en fait une sorte de
problème difficile avec de nombreuses façons différentes

15
00:00:31,980 --> 00:00:32,479
pour le résoudre.

16
00:00:32,479 --> 00:00:34,366
Donc, nous allons les utiliser comme
une classe de problèmes

17
00:00:34,366 --> 00:00:36,740
représentant des choses qui
pourraient être résolus en général.

18
00:00:36,740 --> 00:00:38,980
Et puis nous allons parler
environ en détail ce que

19
00:00:38,980 --> 00:00:42,360
sont appelées données structures--
façons fantaisistes comme les listes chaînées

20
00:00:42,360 --> 00:00:46,290
et des tables de hachage et des arbres qui
un programmeur serait effectivement

21
00:00:46,290 --> 00:00:48,890
utiliser et utilisent généralement
sur un tableau blanc à peindre

22
00:00:48,890 --> 00:00:51,840
une image de ce qu'il ou elle
envisage pour la mise en œuvre

23
00:00:51,840 --> 00:00:52,980
un morceau de logiciel.

24
00:00:52,980 --> 00:00:55,130
>> Alors, faisons les mains sur la première partie.

25
00:00:55,130 --> 00:01:00,090
Il suffit donc de vous salir les mains avec un
environnement appelé scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Ceci est un outil que nous utilisons
dans notre classe de premier cycle.

27
00:01:02,636 --> 00:01:04,510
Même si il est conçu
pour 12 ans et plus,

28
00:01:04,510 --> 00:01:07,570
nous l'utilisons pour le haut
une partie de ce tout à fait un peu

29
00:01:07,570 --> 00:01:10,020
car il est un beau, fun
manière graphique de l'apprentissage

30
00:01:10,020 --> 00:01:12,160
un petit quelque chose sur la programmation.

31
00:01:12,160 --> 00:01:17,600
Ainsi, la tête à cette URL, où vous
devrait voir une page tout à fait comme ça,

32
00:01:17,600 --> 00:01:23,330
et aller de l'avant et cliquez sur
Joignez-vous à Scratch en haut à droite

33
00:01:23,330 --> 00:01:28,300
et de choisir un nom d'utilisateur et un
mot de passe et, finalement, vous obtenez

34
00:01:28,300 --> 00:01:29,970
un scratch.mit.edu account--.

35
00:01:29,970 --> 00:01:32,165

36
00:01:32,165 --> 00:01:34,665
Je pensais l'utiliser comme un
première occasion de montrer cela.

37
00:01:34,665 --> 00:01:39,120
Une question a été soulevée pendant la pause
à propos de ce que le code ressemble réellement.

38
00:01:39,120 --> 00:01:41,315
Et nous parlions
pendant la pause à propos de C,

39
00:01:41,315 --> 00:01:45,060
en particulier un particular--
niveau inférieur dans une langue plus.

40
00:01:45,060 --> 00:01:47,750
Et je viens de faire un rapide
Google recherche pour trouver le code C

41
00:01:47,750 --> 00:01:51,574
pour la recherche binaire, l'algorithme que nous
utilisé pour la recherche que l'annuaire téléphonique plus tôt.

42
00:01:51,574 --> 00:01:54,240
Cet exemple particulier, bien sûr,
ne recherche pas un livre de téléphone.

43
00:01:54,240 --> 00:01:57,840
Il cherche simplement tout un tas de
les numéros dans la mémoire de l'ordinateur.

44
00:01:57,840 --> 00:02:01,000
Mais si vous souhaitez simplement obtenir un visuel
sens de ce qu'est une programmation effective

45
00:02:01,000 --> 00:02:05,370
la langue ressemble, il semble
un petit quelque chose comme ça.

46
00:02:05,370 --> 00:02:09,759
Il est donc environ 20 ans et plus,
30 ou si des lignes de code,

47
00:02:09,759 --> 00:02:12,640
mais la conversation que nous
ont été ayant pendant les vacances

48
00:02:12,640 --> 00:02:16,000
était sur la façon dont cette réalité
obtient transformé en zéros et des uns

49
00:02:16,000 --> 00:02:19,200
et si vous ne pouvez pas revenir que
traiter et aller de zéros et de uns

50
00:02:19,200 --> 00:02:20,210
revenir à code.

51
00:02:20,210 --> 00:02:22,620
>> Malheureusement, le processus
est si transformatrice

52
00:02:22,620 --> 00:02:24,890
qu'il est beaucoup plus facile à dire qu'à faire.

53
00:02:24,890 --> 00:02:29,400
Je suis allé de l'avant et effectivement tourné
ce programme, recherche binaire,

54
00:02:29,400 --> 00:02:32,700
en zéros et par l'intermédiaire d'un
Le programme appelé compilateur que je

55
00:02:32,700 --> 00:02:34,400
arrive d'avoir ici à droite sur mon Mac.

56
00:02:34,400 --> 00:02:37,850
Et si vous regardez l'écran
ici, en se concentrant spécifiquement

57
00:02:37,850 --> 00:02:43,520
sur ces six colonnes intermédiaires uniquement,
vous verrez que des zéros et des uns.

58
00:02:43,520 --> 00:02:48,290
Et ce sont les zéros et ceux qui
composer exactement ce programme de recherche.

59
00:02:48,290 --> 00:02:53,720
>> Et de sorte que chaque morceau de cinq bits,
chaque octet de zéros et de uns ici,

60
00:02:53,720 --> 00:02:57,310
représenter une certaine instruction
typiquement à l'intérieur d'un ordinateur.

61
00:02:57,310 --> 00:03:00,730
Et en fait, si vous avez entendu le
slogan "Intel inside" de marketing - que,

62
00:03:00,730 --> 00:03:04,610
bien sûr, signifie simplement que vous avez un
Intel CPU ou du cerveau à l'intérieur de l'ordinateur.

63
00:03:04,610 --> 00:03:08,000
Et ce que cela signifie d'être un CPU est
que vous avez un jeu d'instructions,

64
00:03:08,000 --> 00:03:08,840
pour ainsi dire.

65
00:03:08,840 --> 00:03:11,620
>> Chaque processeur dans le monde, dont beaucoup
les faites par Intel ces jours-ci,

66
00:03:11,620 --> 00:03:13,690
comprend un ensemble fini
nombre d'instructions.

67
00:03:13,690 --> 00:03:18,690
Et ces instructions sont si bas niveau
comme ajouter ces deux nombres,

68
00:03:18,690 --> 00:03:22,560
multiplier ces deux nombres,
déplacer ce morceau de données à partir d'ici

69
00:03:22,560 --> 00:03:27,340
ici en mémoire, enregistrez ce
l'information d'ici à là en mémoire,

70
00:03:27,340 --> 00:03:32,200
et ainsi forth-- donc très, très
bas niveau, les détails presque électroniques.

71
00:03:32,200 --> 00:03:34,780
Mais avec les mathématiques
opérations couplées

72
00:03:34,780 --> 00:03:37,410
avec ce que nous avons discuté plus tôt,
la représentation des données

73
00:03:37,410 --> 00:03:40,450
comme zéros et des uns, peut
vous construisez tout

74
00:03:40,450 --> 00:03:44,180
qu'un ordinateur peut faire aujourd'hui, que ce soit
il est textuel, graphique, musical,

75
00:03:44,180 --> 00:03:45,580
ou autrement.

76
00:03:45,580 --> 00:03:49,450
>> Donc, ce qui est très facile à obtenir
perdu dans les mauvaises herbes de rapidement.

77
00:03:49,450 --> 00:03:52,150
Et il y a beaucoup de
défis syntaxiques

78
00:03:52,150 --> 00:03:56,630
de sorte que si vous faites le plus simple,
plus stupide des fautes de frappe aucune du programme

79
00:03:56,630 --> 00:03:57,860
ne fonctionnera que ce soit.

80
00:03:57,860 --> 00:04:00,366
Et donc au lieu d'utiliser un
langage comme C ce matin,

81
00:04:00,366 --> 00:04:02,240
Je pensais que ce serait
plus de plaisir à faire réellement

82
00:04:02,240 --> 00:04:04,840
quelque chose de plus visuel, qui
tout en étant conçu pour les enfants

83
00:04:04,840 --> 00:04:08,079
est en fait une manifestation parfaite
d'une programmation effective

84
00:04:08,079 --> 00:04:10,370
language-- arrive juste à
utiliser des images au lieu de texte

85
00:04:10,370 --> 00:04:11,710
pour représenter ces idées.

86
00:04:11,710 --> 00:04:15,470
>> Donc, une fois que vous avez en effet un
compte scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
cliquez sur le bouton Créer
en haut à gauche du site.

88
00:04:21,070 --> 00:04:24,620
Et vous devriez voir un environnement comme
celui que je suis sur le point de voir sur mon écran

89
00:04:24,620 --> 00:04:26,310
ici.

90
00:04:26,310 --> 00:04:29,350
Et nous allons passer un peu
peu de temps à jouer ici.

91
00:04:29,350 --> 00:04:34,080
Voyons voir si nous ne pouvons pas tout résoudre certains
problèmes ensemble de la manière suivante.

92
00:04:34,080 --> 00:04:39,420
>> Donc, ce que vous verrez dans ce
environment-- et en fait juste laisser

93
00:04:39,420 --> 00:04:40,050
moi une pause.

94
00:04:40,050 --> 00:04:42,680
Quelqu'un est-il pas ici?

95
00:04:42,680 --> 00:04:45,070
Pas ici?

96
00:04:45,070 --> 00:04:45,800
D'ACCORD.

97
00:04:45,800 --> 00:04:49,030
Alors permettez-moi de souligner quelques-uns
caractéristiques de cet environnement.

98
00:04:49,030 --> 00:04:55,024
>> Donc, en haut à gauche de l'écran, nous
avoir la scène de Scratch, pour ainsi dire.

99
00:04:55,024 --> 00:04:57,440
Scratch est non seulement le nom
de ce langage de programmation;

100
00:04:57,440 --> 00:05:00,356
il est aussi le nom du chat qui
vous voyez par défaut, il en orange.

101
00:05:00,356 --> 00:05:02,160
Il est sur une scène, de sorte
un peu comme je l'ai décrit

102
00:05:02,160 --> 00:05:05,770
la tortue plus tôt comme étant dans un
environnement de tableau blanc rectangulaire.

103
00:05:05,770 --> 00:05:09,800
le monde Ce chat se limite entièrement
à ce rectangle en haut là.

104
00:05:09,800 --> 00:05:12,210
>> Pendant ce temps, sur la droite
côté ici, il est

105
00:05:12,210 --> 00:05:15,610
juste une zone de scripts, un
ardoise vierge si vous voulez.

106
00:05:15,610 --> 00:05:18,590
Voilà où nous allons écrire
nos programmes en un instant.

107
00:05:18,590 --> 00:05:22,935
Et les blocs de construction que nous
utiliser pour écrire cette program-- le puzzle

108
00:05:22,935 --> 00:05:25,310
morceaux, si vous êtes will--
ceux ici au milieu,

109
00:05:25,310 --> 00:05:27,500
et ils sont classés
par fonctionnalité.

110
00:05:27,500 --> 00:05:31,000
Ainsi, par exemple, je vais aller de l'avant
et de démontrer au moins un de ceux-ci.

111
00:05:31,000 --> 00:05:33,690
Je vais aller de l'avant et cliquez sur
la catégorie de contrôle en haut.

112
00:05:33,690 --> 00:05:35,720
>> Donc, ce sont les catégories en haut.

113
00:05:35,720 --> 00:05:39,410
Je vais cliquer sur la catégorie de contrôle.

114
00:05:39,410 --> 00:05:44,020
Au contraire, je vais cliquer sur les événements
catégorie, le tout premier en haut.

115
00:05:44,020 --> 00:05:47,790
Et si vous souhaitez suivre même
comme nous le faisons, vous avez tout à fait bienvenue à.

116
00:05:47,790 --> 00:05:52,180
Je vais cliquer et faire glisser ce
première, "lorsque le drapeau vert cliqué."

117
00:05:52,180 --> 00:05:58,410
Et puis je vais laisser tomber juste
à peu près au sommet de mes pages blanches.

118
00:05:58,410 --> 00:06:01,450
>> Et ce qui est agréable au sujet Scratch
est que cette pièce de puzzle, quand

119
00:06:01,450 --> 00:06:04,560
verrouillé avec un autre casse-tête
morceaux, va faire littéralement

120
00:06:04,560 --> 00:06:06,460
ce que ces pièces de puzzle disent de faire.

121
00:06:06,460 --> 00:06:09,710
Ainsi, par exemple, Scratch est juste
maintenant au milieu de son monde.

122
00:06:09,710 --> 00:06:14,660
Je vais aller de l'avant et de choisir
maintenant, disons, la catégorie de mouvement,

123
00:06:14,660 --> 00:06:18,000
si vous souhaitez faire de
same-- catégorie Motion.

124
00:06:18,000 --> 00:06:20,430
Et maintenant remarquer que j'ai un tout
tas de pièces de puzzle ici

125
00:06:20,430 --> 00:06:23,370
que, encore une fois, sorte de faire ce qu'ils disent.

126
00:06:23,370 --> 00:06:28,110
Et je vais aller de l'avant et faire glisser et
déposer le bloc de déplacement juste ici.

127
00:06:28,110 --> 00:06:31,860
>> Et remarquez que, dès que vous obtenez
à proximité du fond du «drapeau vert

128
00:06:31,860 --> 00:06:34,580
cliqué sur "bouton, avis
comment une ligne blanche apparaît,

129
00:06:34,580 --> 00:06:36,950
comme si elle est presque
magnétique, il veut y aller.

130
00:06:36,950 --> 00:06:43,070
Il suffit de laisser aller, et il se cassera
ensemble et les formes correspondront.

131
00:06:43,070 --> 00:06:46,620
Et maintenant, vous pouvez peut-être presque
deviner où nous allons avec cela.

132
00:06:46,620 --> 00:06:51,570
>> Si vous regardez la scène de Scratch
ici et regarder vers le haut de celui-ci,

133
00:06:51,570 --> 00:06:55,142
vous verrez une lumière rouge,
arrêtez le signe, et un drapeau vert.

134
00:06:55,142 --> 00:06:57,100
Et je vais aller de l'avant
et regarder mes screen--

135
00:06:57,100 --> 00:06:58,460
pour un instant, si vous le pouviez.

136
00:06:58,460 --> 00:07:01,960
Je vais cliquer sur le
drapeau vert en ce moment,

137
00:07:01,960 --> 00:07:07,850
et il a déménagé ce qui semble être 10 étapes
ou 10 pixels, 10 points, sur l'écran.

138
00:07:07,850 --> 00:07:13,390
>> Et donc pas excitant,
mais permettez-moi de proposer

139
00:07:13,390 --> 00:07:17,440
sans même enseigner cela, juste
en utilisant le propre de votre propre let intuition--

140
00:07:17,440 --> 00:07:22,560
me propose que vous comprendre comment
faire Scratch pied droit hors de la scène.

141
00:07:22,560 --> 00:07:28,700
Demandez-lui de faire place à la droite de
l'écran, tout le chemin vers la droite.

142
00:07:28,700 --> 00:07:32,200
Permettez-moi de vous donner un moment
ou alors à se débattre avec cela.

143
00:07:32,200 --> 00:07:37,681
Vous pouvez jeter un coup d'oeil
à d'autres catégories de blocs.

144
00:07:37,681 --> 00:07:38,180
D'accord.

145
00:07:38,180 --> 00:07:41,290
Donc, pour récapituler, lorsque nous avons
le drapeau vert cliqué ici

146
00:07:41,290 --> 00:07:44,850
et déplacer 10 étapes est la
seule instruction, chaque fois que je

147
00:07:44,850 --> 00:07:46,720
cliquez sur le drapeau vert, ce qui se passe?

148
00:07:46,720 --> 00:07:50,070
Eh bien, qui exécute mon programme.

149
00:07:50,070 --> 00:07:52,450
Donc, je pouvais le faire
peut-être 10 fois manuellement,

150
00:07:52,450 --> 00:07:55,130
mais cela se sent un peu
bit hackish, pour ainsi dire,

151
00:07:55,130 --> 00:07:57,480
de sorte que je ne suis pas vraiment
la résolution du problème.

152
00:07:57,480 --> 00:08:00,530
Je suis juste essayer encore et
Encore et encore et encore

153
00:08:00,530 --> 00:08:03,180
jusqu'à ce que je sorte de hasard
parvenir à la directive

154
00:08:03,180 --> 00:08:05,560
que je me suis mis à réaliser plus tôt.

155
00:08:05,560 --> 00:08:08,200
>> Mais nous savons de notre
pseudocode plus tôt qu'il ya

156
00:08:08,200 --> 00:08:11,870
cette notion dans la programmation de la boucle,
faire encore et encore quelque chose.

157
00:08:11,870 --> 00:08:14,888
Et je l'ai vu qu'un groupe de vous
atteint pour pièce ce puzzle?

158
00:08:14,888 --> 00:08:17,870

159
00:08:17,870 --> 00:08:18,730
Répétez jusqu'à ce que.

160
00:08:18,730 --> 00:08:21,400
Donc, nous pourrions faire quelque chose
comme répéter jusqu'à ce que.

161
00:08:21,400 --> 00:08:23,760
Et qu'est-ce que vous répétez jusqu'à ce exactement?

162
00:08:23,760 --> 00:08:27,720

163
00:08:27,720 --> 00:08:28,540
>> D'ACCORD.

164
00:08:28,540 --> 00:08:31,974
Et laissez-moi aller avec celui qui est
un peu plus simple pour un instant.

165
00:08:31,974 --> 00:08:33,140
Laissez-moi aller de l'avant et de faire cela.

166
00:08:33,140 --> 00:08:35,559
Notez que, comme vous pouvez avoir
découvert sous contrôle,

167
00:08:35,559 --> 00:08:38,409
il y a ce bloc de répétition, qui
ne regarde pas comme il est si grand.

168
00:08:38,409 --> 00:08:41,039
Il n'y a pas beaucoup de place dans
entre ces deux lignes jaunes.

169
00:08:41,039 --> 00:08:43,539
Mais comme certains d'entre vous pourraient avoir
remarqué, si vous faites glisser-déposer,

170
00:08:43,539 --> 00:08:45,150
remarquez comment il se développe pour remplir la forme.

171
00:08:45,150 --> 00:08:46,274
>> Et vous pouvez même entasser plus.

172
00:08:46,274 --> 00:08:48,670
Il va juste continuer de croître si
vous faites glisser et survolez.

173
00:08:48,670 --> 00:08:51,110
Et je ne sais pas ce qui est
mieux ici, alors laissez

174
00:08:51,110 --> 00:08:54,760
moi au moins répéter cinq fois, pour
par exemple, et ensuite revenir à l'étape

175
00:08:54,760 --> 00:08:56,720
et cliquez sur le drapeau vert.

176
00:08:56,720 --> 00:08:59,110
Et maintenant, remarquez qu'il est pas tout à fait là.

177
00:08:59,110 --> 00:09:02,400
>> Maintenant, certains d'entre vous ont proposé, comme
Victoria n'a tout simplement, répéter 10 fois.

178
00:09:02,400 --> 00:09:05,140
Et cela fait généralement
lui faire tout le chemin,

179
00:09:05,140 --> 00:09:10,510
mais ne serait pas y avoir une plus robuste
ainsi que de déterminer arbitrairement

180
00:09:10,510 --> 00:09:12,640
combien se déplace à faire?

181
00:09:12,640 --> 00:09:17,680
Quel pourrait être un meilleur bloc
que répéter 10 fois être?

182
00:09:17,680 --> 00:09:20,380
>> Ouais, alors pourquoi ne pas faire quelque chose pour toujours?

183
00:09:20,380 --> 00:09:24,390
Et maintenant, laissez-moi passer cette pièce de puzzle
à l'intérieur de là et se débarrasser de celui-ci.

184
00:09:24,390 --> 00:09:28,300
Maintenant, remarquez, peu importe où Scratch
commence, il va vers le bord.

185
00:09:28,300 --> 00:09:30,700
Et heureusement MIT,
qui fait Scratch, juste

186
00:09:30,700 --> 00:09:33,190
fait en sorte qu'il n'a jamais
disparaît complètement.

187
00:09:33,190 --> 00:09:35,360
Vous pouvez toujours saisir sa queue.

188
00:09:35,360 --> 00:09:37,680
>> Et intuitivement,
pourquoi at-il continuer à avancer?

189
00:09:37,680 --> 00:09:38,892
Qu'est-ce qui se passe ici?

190
00:09:38,892 --> 00:09:41,440

191
00:09:41,440 --> 00:09:43,824
Il semble s'être arrêté, mais
puis si je prends et faites glisser

192
00:09:43,824 --> 00:09:45,240
il continue à vouloir aller là-bas.

193
00:09:45,240 --> 00:09:46,123
Pourquoi donc?

194
00:09:46,123 --> 00:09:51,610

195
00:09:51,610 --> 00:09:54,360
Vraiment, un ordinateur est littéralement
allez faire ce que vous lui demandez de faire.

196
00:09:54,360 --> 00:09:58,380
Donc, si vous l'avez dit plus tôt faire la
suivant chose pour toujours, déplacer 10 étapes,

197
00:09:58,380 --> 00:10:01,860
il va continuer et aller
jusqu'à ce que je frappe le panneau d'arrêt rouge

198
00:10:01,860 --> 00:10:04,620
et arrêter complètement le programme.

199
00:10:04,620 --> 00:10:06,610
>> Donc, même si vous ne l'avez pas
faire, comment pourrais-je

200
00:10:06,610 --> 00:10:09,510
faire Scratch aller plus vite
à travers l'écran?

201
00:10:09,510 --> 00:10:12,060

202
00:10:12,060 --> 00:10:13,280
Plus de mesures, non?

203
00:10:13,280 --> 00:10:15,710
Ainsi, au lieu de faire 10
à un moment, pourquoi ne pas nous

204
00:10:15,710 --> 00:10:20,100
aller de l'avant et le changer to--
que feriez-vous propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Alors maintenant, je vais cliquer sur le vert
drapeau, et en effet, il va très vite.

206
00:10:24,410 --> 00:10:27,180
>> Et cela, bien sûr, est juste
une manifestation d'animation.

207
00:10:27,180 --> 00:10:28,060
Qu'est-ce que l'animation?

208
00:10:28,060 --> 00:10:33,090
Il est juste de vous montrer l'un humain
tas ensemble d'images fixes vraiment,

209
00:10:33,090 --> 00:10:34,160
vraiment, vraiment rapide.

210
00:10:34,160 --> 00:10:36,500
Et si nous sommes en train de dire
lui de se déplacer plusieurs étapes,

211
00:10:36,500 --> 00:10:39,750
nous juste avoir l'effet soit à
changement où il est à l'écran

212
00:10:39,750 --> 00:10:42,900
tout l'appareil plus rapidement par temps.

213
00:10:42,900 --> 00:10:46,454
>> Maintenant, le prochain défi que je proposais
devait avoir lui rebondir sur le bord.

214
00:10:46,454 --> 00:10:49,120
Et sans savoir ce casse-tête
morceaux parce qu'elle est réalisée: amende

215
00:10:49,120 --> 00:10:53,030
si vous ne recevez pas à la
étape du challenge-- ce

216
00:10:53,030 --> 00:10:54,280
voulez-vous faire intuitivement?

217
00:10:54,280 --> 00:10:58,030
Comment pourrions-nous le faire rebondir et
etc., entre la gauche et la droite?

218
00:10:58,030 --> 00:11:02,630

219
00:11:02,630 --> 00:11:03,810
>> Ouais.

220
00:11:03,810 --> 00:11:05,680
Nous avons donc besoin d'une sorte
de l'état, et nous

221
00:11:05,680 --> 00:11:09,710
semblent avoir conditionals, ainsi
dire, dans la catégorie de contrôle.

222
00:11:09,710 --> 00:11:14,110
Lequel de ces blocs
voulons-nous sans doute?

223
00:11:14,110 --> 00:11:15,200
Ouais, peut-être «si, alors."

224
00:11:15,200 --> 00:11:18,780
Donc remarquer que, parmi les blocs jaunes
nous avons ici, il y a ce "si"

225
00:11:18,780 --> 00:11:23,920
ou cette «if, else" bloc qui sera
nous permettent de prendre une décision pour ce faire

226
00:11:23,920 --> 00:11:25,000
ou de le faire.

227
00:11:25,000 --> 00:11:27,380
Et vous pouvez même imbriquer
à faire plusieurs choses.

228
00:11:27,380 --> 00:11:34,910
Ou si vous avez pas encore allé ici,
aller de l'avant à la catégorie Sensing

229
00:11:34,910 --> 00:11:39,612
et-- nous allons voir si elle est ici.

230
00:11:39,612 --> 00:11:43,050

231
00:11:43,050 --> 00:11:52,050
>> Donc, ce bloc peut être utile ici
pour détecter s'il est hors de la scène?

232
00:11:52,050 --> 00:11:56,740
Ouais, notez que certains de ces blocs
peuvent être paramétrées, pour ainsi dire.

233
00:11:56,740 --> 00:12:00,706
Ils peuvent être personnalisés en quelque sorte, pas
contrairement HTML hier avec des attributs,

234
00:12:00,706 --> 00:12:03,330
où ces attributs type de
personnaliser le comportement d'une balise.

235
00:12:03,330 --> 00:12:08,880
De même ici, je peux saisir cette touchante
bloc et le changement et poser la question,

236
00:12:08,880 --> 00:12:11,500
touchez-vous la souris
pointeur comme le curseur

237
00:12:11,500 --> 00:12:13,250
ou êtes-vous touchez le bord?

238
00:12:13,250 --> 00:12:15,210
>> Alors laissez-moi aller et le faire.

239
00:12:15,210 --> 00:12:18,130
Je vais faire un zoom arrière pour un moment.

240
00:12:18,130 --> 00:12:21,320
Permettez-moi de saisir cette pièce de puzzle
ici, ce puzzle morceau cela,

241
00:12:21,320 --> 00:12:24,570
et je vais pêle-mêle
les pour un moment.

242
00:12:24,570 --> 00:12:27,620
Je vais passer cela,
changer cette arête touchante,

243
00:12:27,620 --> 00:12:38,590
et je vais faire le mouvement.

244
00:12:38,590 --> 00:12:40,490
Alors, voici quelques ingrédients.

245
00:12:40,490 --> 00:12:42,570
Je pense avoir tout ce que je veux suis.

246
00:12:42,570 --> 00:12:47,710
>> Quelqu'un voudrait-il proposer comment je
peut se connecter ces peut-être haut en bas

247
00:12:47,710 --> 00:12:52,020
afin de résoudre le problème de devoir
Scratch mouvement de droite à gauche à droite pour

248
00:12:52,020 --> 00:12:57,020
de gauche à droite à gauche, chaque
temps juste rebondir sur le mur?

249
00:12:57,020 --> 00:12:58,050
Qu'est-ce que je veux faire?

250
00:12:58,050 --> 00:13:01,097
Quel bloc dois-je me connecter à
"Drapeau quand vert cliqué premier"?

251
00:13:01,097 --> 00:13:04,060

252
00:13:04,060 --> 00:13:06,200
>> OK, donc nous allons commencer avec le "pour toujours."

253
00:13:06,200 --> 00:13:07,170
Ce qui se passe à l'intérieur de la prochaine?

254
00:13:07,170 --> 00:13:10,290
Quelqu'un d'autre.

255
00:13:10,290 --> 00:13:11,850
OK, déplacer étapes.

256
00:13:11,850 --> 00:13:12,350
D'accord.

257
00:13:12,350 --> 00:13:14,470
Alors quoi?

258
00:13:14,470 --> 00:13:15,120
Alors le cas.

259
00:13:15,120 --> 00:13:17,720
Et remarquez, même si elle semble
pris en sandwich ensemble étroitement,

260
00:13:17,720 --> 00:13:19,500
il va juste pousser à remplir.

261
00:13:19,500 --> 00:13:21,500
Il va juste sauter dans où je veux.

262
00:13:21,500 --> 00:13:25,920
>> Et qu'est-ce que je mets entre
le cas et alors?

263
00:13:25,920 --> 00:13:27,180
Probablement "si touchant bord."

264
00:13:27,180 --> 00:13:31,800
Et remarquez, encore une fois, il est trop grand
pour elle, mais elle va croître à combler.

265
00:13:31,800 --> 00:13:35,002
Et puis tourner à 15 degrés?

266
00:13:35,002 --> 00:13:35,710
Combien de degrés?

267
00:13:35,710 --> 00:13:38,800

268
00:13:38,800 --> 00:13:41,196
Ouais, donc 180 va tourner
moi tout autour.

269
00:13:41,196 --> 00:13:42,570
Voyons donc si je suis ce droit.

270
00:13:42,570 --> 00:13:43,930
Permettez-moi de faire un zoom arrière.

271
00:13:43,930 --> 00:13:45,130
>> Permettez-moi de glisser Scratch up.

272
00:13:45,130 --> 00:13:50,030
Donc, il est un peu déformée
maintenant, mais ça va.

273
00:13:50,030 --> 00:13:52,231
Comment puis-je le réinitialiser facilement?

274
00:13:52,231 --> 00:13:59,879

275
00:13:59,879 --> 00:14:01,045
Je vais tricher un peu.

276
00:14:01,045 --> 00:14:04,074

277
00:14:04,074 --> 00:14:05,990
Je suis donc d'ajouter un autre
bloc, juste pour être clair.

278
00:14:05,990 --> 00:14:08,424
Je veux qu'il pointe à 90 degrés
à la droite par défaut,

279
00:14:08,424 --> 00:14:10,840
donc je vais juste lui dire
de le faire par programme.

280
00:14:10,840 --> 00:14:11,632
Et c'est reparti.

281
00:14:11,632 --> 00:14:14,740

282
00:14:14,740 --> 00:14:15,740
Nous semblons avoir fait.

283
00:14:15,740 --> 00:14:19,980
Il est un peu bizarre, parce que
il marche à l'envers.

284
00:14:19,980 --> 00:14:21,250
Appelons qu'un bug.

285
00:14:21,250 --> 00:14:22,120
C'est une erreur.

286
00:14:22,120 --> 00:14:27,320
Un bug est une erreur dans un programme, un
erreur logique que moi, l'être humain, fait.

287
00:14:27,320 --> 00:14:28,985
Pourquoi est-ce qu'il va à l'envers?

288
00:14:28,985 --> 00:14:33,560

289
00:14:33,560 --> 00:14:35,250
Est-ce que MIT bousiller ou ai-je?

290
00:14:35,250 --> 00:14:38,840

291
00:14:38,840 --> 00:14:42,550
>> Ouais, je veux dire, ce n'est pas MIT
faute. On m'a donné une pièce de puzzle

292
00:14:42,550 --> 00:14:44,970
qui dit tourner un certain nombre de degrés.

293
00:14:44,970 --> 00:14:47,672
Et à la suggestion de Victoria,
Je tourne à 180 degrés,

294
00:14:47,672 --> 00:14:48,880
qui est la bonne intuition.

295
00:14:48,880 --> 00:14:53,700
Mais tourner de 180 degrés littéralement
des moyens de rotation de 180 degrés,

296
00:14:53,700 --> 00:14:55,860
et ce n'est pas vraiment
ce que je veux, apparemment.

297
00:14:55,860 --> 00:14:58,026
Parce qu'au moins il est dans
ce monde à deux dimensions,

298
00:14:58,026 --> 00:15:00,740
alors tournant va vraiment
de lui retourner la tête en bas.

299
00:15:00,740 --> 00:15:04,030
>> Je veux probablement utiliser ce bloc
à la place, sur la base de ce que vous voyez ici?

300
00:15:04,030 --> 00:15:11,890

301
00:15:11,890 --> 00:15:14,790
Comment pourrions-nous résoudre ce problème?

302
00:15:14,790 --> 00:15:18,380
Ouais, donc nous pourrions pointer
dans la direction opposée.

303
00:15:18,380 --> 00:15:22,300
Et en fait même que ce
ne va pas être suffisant,

304
00:15:22,300 --> 00:15:26,410
parce que nous ne pouvons coder en dur
à pointer gauche ou à droite.

305
00:15:26,410 --> 00:15:27,920
>> Vous savez ce que nous pourrions faire?

306
00:15:27,920 --> 00:15:30,160
Il semble que nous avons un
bloc de commodité ici.

307
00:15:30,160 --> 00:15:32,987
Si je zoome, voir
quelque chose que nous aimons ici?

308
00:15:32,987 --> 00:15:36,120

309
00:15:36,120 --> 00:15:40,020
Donc, il semble que le MIT a un
abstraction construite ici.

310
00:15:40,020 --> 00:15:45,440
Ce bloc semble être équivalent
à laquelle d'autres blocs, pluriel?

311
00:15:45,440 --> 00:15:49,510
>> Celui-ci bloc semble être équivalent
à l'ensemble de ce trio de blocs

312
00:15:49,510 --> 00:15:50,880
que nous avons ici.

313
00:15:50,880 --> 00:15:54,670
Donc, il se trouve que je peux simplifier ma
programme en se débarrassant de tout cela

314
00:15:54,670 --> 00:15:58,270
et vient de mettre cela ici.

315
00:15:58,270 --> 00:16:01,620
Et maintenant, il est encore un peu
poussette, et c'est très bien pour le moment.

316
00:16:01,620 --> 00:16:03,370
Nous allons laisser ce soit.

317
00:16:03,370 --> 00:16:06,000
Mais mon programme est encore
plus simple, et cela, aussi,

318
00:16:06,000 --> 00:16:09,060
serait représentatif
d'un but dans programming--

319
00:16:09,060 --> 00:16:13,430
est de faire idéalement votre code comme
simple, aussi compact que possible,

320
00:16:13,430 --> 00:16:15,650
tout en étant aussi
lisible que possible.

321
00:16:15,650 --> 00:16:20,310
Vous ne voulez pas faire en sorte succincte
qu'il est difficile à comprendre.

322
00:16:20,310 --> 00:16:22,826
>> Mais notez que j'ai remplacé
trois blocs avec un,

323
00:16:22,826 --> 00:16:24,200
et c'est sans doute une bonne chose.

324
00:16:24,200 --> 00:16:27,280
Je suis loin de la notion abstraite
de vérifier si vous êtes

325
00:16:27,280 --> 00:16:29,120
sur le bord d'un seul bloc.

326
00:16:29,120 --> 00:16:31,520
Maintenant, nous pouvons nous amuser avec cela, en fait.

327
00:16:31,520 --> 00:16:35,790
Cela ne correspond pas tellement
valeur intellectuelle, mais la valeur ludique.

328
00:16:35,790 --> 00:16:39,730
Je vais aller de l'avant
et de saisir ce son ici.

329
00:16:39,730 --> 00:16:42,900

330
00:16:42,900 --> 00:16:46,420
Alors laissez-moi aller de l'avant, et laissez-moi
arrêter le programme pendant un moment.

331
00:16:46,420 --> 00:16:52,070
Je vais enregistrer ce qui suit,
permettant l'accès à mon micro.

332
00:16:52,070 --> 00:16:53,181
>> Et c'est parti.

333
00:16:53,181 --> 00:16:53,680
Aie.

334
00:16:53,680 --> 00:16:58,710

335
00:16:58,710 --> 00:17:01,140
Essayons encore une fois.

336
00:17:01,140 --> 00:17:02,279
Et c'est parti.

337
00:17:02,279 --> 00:17:03,570
OK, j'ai enregistré la mauvaise chose.

338
00:17:03,570 --> 00:17:04,580
Et c'est parti.

339
00:17:04,580 --> 00:17:05,080
Aie.

340
00:17:05,080 --> 00:17:07,910

341
00:17:07,910 --> 00:17:08,800
Aie.

342
00:17:08,800 --> 00:17:09,300
D'accord.

343
00:17:09,300 --> 00:17:10,791
Maintenant, je dois me débarrasser de cela.

344
00:17:10,791 --> 00:17:11,290
D'accord.

345
00:17:11,290 --> 00:17:13,950
>> Alors maintenant, je suis un
enregistrement de juste "ouch."

346
00:17:13,950 --> 00:17:18,040
Alors maintenant, je vais aller
avant et appeler cette "ouch."

347
00:17:18,040 --> 00:17:20,270
Je vais revenir en arrière
à mes scripts, et maintenant

348
00:17:20,270 --> 00:17:25,460
avis il y a ce bloc qui est appelé
jouer son "miaou" ou jouer son "ouch."

349
00:17:25,460 --> 00:17:28,920
Je vais faire traîner, et où
dois-je mettre ce pour un effet comique?

350
00:17:28,920 --> 00:17:31,740

351
00:17:31,740 --> 00:17:37,860
Ouais, alors maintenant il est une sorte de
poussette, parce que maintenant ce block--

352
00:17:37,860 --> 00:17:42,050
remarquez comment cette «si sur le bord,
rebond "est une sorte d'auto-contenue.

353
00:17:42,050 --> 00:17:43,704
Je dois donc résoudre ce problème.

354
00:17:43,704 --> 00:17:44,870
Laissez-moi aller de l'avant et de faire cela.

355
00:17:44,870 --> 00:17:48,630
Permettez-moi de me débarrasser de cela et revenir
à notre origine, plus délibérée

356
00:17:48,630 --> 00:17:49,870
la fonctionnalité.

357
00:17:49,870 --> 00:18:01,080
Donc, "si bord de toucher, puis" je veux
à tourner, que Victoria a proposé,

358
00:18:01,080 --> 00:18:02,480
180 degrés.

359
00:18:02,480 --> 00:18:05,497
Et ce que je veux jouer
le son "ouch" il?

360
00:18:05,497 --> 00:18:11,800

361
00:18:11,800 --> 00:18:15,580
>> Ouais, notez qu'il est à l'extérieur
ce bloc jaune.

362
00:18:15,580 --> 00:18:17,680
Donc, cela aussi serait un
bug, mais je l'ai remarqué.

363
00:18:17,680 --> 00:18:21,290
Donc, je vais le faire glisser ici,
et un avis maintenant il est à l'intérieur du «si».

364
00:18:21,290 --> 00:18:24,250
Ainsi, le «si» est ce genre
de comme blot en forme de bras

365
00:18:24,250 --> 00:18:26,260
que ça ne va
faire ce qui est à l'intérieur de celui-ci.

366
00:18:26,260 --> 00:18:30,216
Alors maintenant, si je zoome sur au
le risque de annoying--

367
00:18:30,216 --> 00:18:32,860

368
00:18:32,860 --> 00:18:36,470
>> COMPUTER: Aïe, aïe, aïe.

369
00:18:36,470 --> 00:18:39,910
>> DAVID MALAN: Et il
va juste durer éternellement.

370
00:18:39,910 --> 00:18:44,160
Maintenant, il suffit d'accélérer les choses
ici, laissez-moi aller de l'avant et d'ouvrir,

371
00:18:44,160 --> 00:18:50,460
nous allons say-- me laisser aller à quelques-uns
de ma propre substance de la classe.

372
00:18:50,460 --> 00:18:53,000

373
00:18:53,000 --> 00:19:00,220
Et laissez-moi ouvrir, disons, ce
celle faite par un de nos compagnons d'enseignement

374
00:19:00,220 --> 00:19:01,500
Il y a quelques années.

375
00:19:01,500 --> 00:19:04,732
Donc, certains d'entre vous rappeler
ce jeu d'antan,

376
00:19:04,732 --> 00:19:05,940
et il est en fait remarquable.

377
00:19:05,940 --> 00:19:08,190
Même si nous avons fait le
la plus simple des programmes en ce moment,

378
00:19:08,190 --> 00:19:09,980
nous allons examiner ce que cela
ressemble réellement.

379
00:19:09,980 --> 00:19:10,650
Permettez-moi de frapper le jeu.

380
00:19:10,650 --> 00:19:14,210

381
00:19:14,210 --> 00:19:18,980
>> Donc, dans ce jeu, nous avons un
grenouille, et en utilisant la flèche keys--

382
00:19:18,980 --> 00:19:23,340
il prend de plus grandes étapes que je remember--
Je contrôle sur cette grenouille.

383
00:19:23,340 --> 00:19:29,630
Et le but est d'obtenir à travers le occupés
route sans courir dans les voitures.

384
00:19:29,630 --> 00:19:34,735
Et soyons see-- si je vais ici, je
avoir à attendre un journal pour faire défiler par.

385
00:19:34,735 --> 00:19:38,130

386
00:19:38,130 --> 00:19:39,274
Cela se sent comme un bug.

387
00:19:39,274 --> 00:19:42,240

388
00:19:42,240 --> 00:19:43,495
Ceci est une sorte de bug.

389
00:19:43,495 --> 00:19:45,980

390
00:19:45,980 --> 00:19:46,480
D'accord.

391
00:19:46,480 --> 00:19:51,550
Je suis sur ce ici,
là, et puis vous continuez à

392
00:19:51,550 --> 00:19:54,100
jusqu'à ce que vous obtenez tous
les grenouilles aux nénuphars.

393
00:19:54,100 --> 00:19:55,920
Maintenant, cela pourrait ressembler
d'autant plus complexe,

394
00:19:55,920 --> 00:19:57,840
mais nous allons essayer de briser
cette mentalement

395
00:19:57,840 --> 00:20:00,040
et verbalement dans ses blocs de composants.

396
00:20:00,040 --> 00:20:03,910
Donc, il y a probablement un casse-tête
pièce que nous avons pas encore vu

397
00:20:03,910 --> 00:20:07,440
mais que cela répond à des frappes,
aux choses que je frappe sur le clavier.

398
00:20:07,440 --> 00:20:11,660
>> Donc, il y a probablement une sorte de
bloc qui dit, si la clé est égale up,

399
00:20:11,660 --> 00:20:15,965
puis faire quelque chose avec Scratch--
peut-être déplacer 10 étapes de cette façon.

400
00:20:15,965 --> 00:20:20,240
Si la touche vers le bas est enfoncé, déplacez 10 étapes
de cette façon, ou la touche gauche, déplacer 10 étapes

401
00:20:20,240 --> 00:20:21,710
De cette façon, 10 étapes que.

402
00:20:21,710 --> 00:20:23,644
J'ai clairement tourné le chat en grenouille.

403
00:20:23,644 --> 00:20:26,060
Voilà donc là où la
costume, comme des appels à gratter it-- nous

404
00:20:26,060 --> 00:20:28,440
juste importé une image de la grenouille.

405
00:20:28,440 --> 00:20:29,570
>> Mais qu'est-ce qui se passe?

406
00:20:29,570 --> 00:20:32,794
Quelles autres lignes de code,
ce que les autres pièces du puzzle

407
00:20:32,794 --> 00:20:35,460
Blake a fait, notre compagnon d'enseignement,
utiliser dans ce programme, apparemment?

408
00:20:35,460 --> 00:20:38,320

409
00:20:38,320 --> 00:20:42,730
Qu'est-ce tout faire move--
ce que la programmation construire?

410
00:20:42,730 --> 00:20:44,950
>> Mouvement, sure-- de sorte que le
déplacer le bloc, pour sûr.

411
00:20:44,950 --> 00:20:49,330
Et ce qui est de ce bloc de déplacement
intérieur, le plus probable?

412
00:20:49,330 --> 00:20:52,850
Oui, une sorte de boucle, peut-être un
jamais bloquer, peut-être une répétition block--

413
00:20:52,850 --> 00:20:54,070
répéter jusqu'à ce bloc.

414
00:20:54,070 --> 00:20:57,330
Et voilà ce qui rend les billes et
les nénuphars et tout mouvement d'autre

415
00:20:57,330 --> 00:20:57,990
d'avant en arrière.

416
00:20:57,990 --> 00:21:00,270
Il est juste passe sans cesse.

417
00:21:00,270 --> 00:21:03,180
>> Pourquoi certains sont des voitures
se déplaçant plus vite que les autres?

418
00:21:03,180 --> 00:21:06,607
Ce qui est différent au sujet de ces programmes?

419
00:21:06,607 --> 00:21:09,690
Oui, sans doute certains d'entre eux prennent
plusieurs étapes à la fois et certains d'entre eux

420
00:21:09,690 --> 00:21:10,690
moins d'étapes à la fois.

421
00:21:10,690 --> 00:21:14,670
Et l'effet visuel
est rapide par rapport lent.

422
00:21:14,670 --> 00:21:16,030
>> Que pensez-vous arrivé?

423
00:21:16,030 --> 00:21:19,700
Quand je suis arrivé ma grenouille tout le chemin
dans la rue et la rivière

424
00:21:19,700 --> 00:21:23,560
sur la feuille de nénuphar, quelque chose
remarquable est arrivé.

425
00:21:23,560 --> 00:21:26,540
Qu'est-il arrivé dès que je l'ai fait?

426
00:21:26,540 --> 00:21:27,210
Cela s'arrêta.

427
00:21:27,210 --> 00:21:29,680
Cette grenouille est arrêté, et
Je suis une seconde grenouille.

428
00:21:29,680 --> 00:21:33,155
Alors, que doit être construit
il utilisé, ce dispositif?

429
00:21:33,155 --> 00:21:36,020

430
00:21:36,020 --> 00:21:38,660
>> Ouais, donc il y a une sorte de
"Si" conditionner là-bas, aussi.

431
00:21:38,660 --> 00:21:41,909
Et il se out-- nous ne voyons pas this--
mais il y a d'autres blocs là que

432
00:21:41,909 --> 00:21:45,300
peut dire, si vous êtes toucher
une autre chose sur l'écran,

433
00:21:45,300 --> 00:21:47,720
si vous touchez le nénuphar », alors."

434
00:21:47,720 --> 00:21:50,810
Et puis c'est lorsque nous
faire la deuxième grenouille apparaît.

435
00:21:50,810 --> 00:21:54,969
Ainsi, même si ce jeu est certainement
très daté, même si, à première vue

436
00:21:54,969 --> 00:21:58,010
il y a tellement de choses on-- et Blake
n'a pas fouetter ce en deux minutes,

437
00:21:58,010 --> 00:22:00,390
il a probablement pris plusieurs lui
heures pour créer ce jeu

438
00:22:00,390 --> 00:22:03,850
sur la base de sa mémoire ou de vidéos
de la version d'antan de celui-ci.

439
00:22:03,850 --> 00:22:07,940
Mais toutes ces petites choses
aller sur l'écran dans l'isolement

440
00:22:07,940 --> 00:22:11,550
résument à ces très simple
mouvements ou déclarations constructs--

441
00:22:11,550 --> 00:22:15,519
comme nous en avons discuté, des boucles et des
conditions, et qui est à ce sujet.

442
00:22:15,519 --> 00:22:17,060
Il y a quelques autres fonctionnalités plus fantaisistes.

443
00:22:17,060 --> 00:22:19,130
Certains d'entre eux sont purement
esthétique ou acoustique,

444
00:22:19,130 --> 00:22:20,964
comme les sons que j'ai joué avec.

445
00:22:20,964 --> 00:22:23,380
Mais pour la plupart, vous
avoir dans cette langue, Scratch,

446
00:22:23,380 --> 00:22:25,350
tous les fondamentaux
blocs de construction que vous

447
00:22:25,350 --> 00:22:29,280
avoir en C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
et un certain nombre d'autres langues.

449
00:22:32,960 --> 00:22:36,720
Une question sur Scratch?

450
00:22:36,720 --> 00:22:37,220
D'accord.

451
00:22:37,220 --> 00:22:40,303
Donc, nous ne pourrons pas plonger plus profondément pour Scratch,
si vous êtes les bienvenus ce week-end,

452
00:22:40,303 --> 00:22:42,860
surtout si vous avez des enfants ou
neveux et nièces et autres,

453
00:22:42,860 --> 00:22:44,220
pour leur présenter Scratch.

454
00:22:44,220 --> 00:22:47,960
Il est en fait une merveille ludique
environnement avec, comme ses auteurs,

455
00:22:47,960 --> 00:22:49,120
très hauts plafonds.

456
00:22:49,120 --> 00:22:51,670
Même si nous avons commencé avec
mêmes les détails de bas niveau,

457
00:22:51,670 --> 00:22:54,890
vous pouvez vraiment faire un peu
avec elle, et cela est peut-être

458
00:22:54,890 --> 00:22:57,360
une démonstration de exactement cela.

459
00:22:57,360 --> 00:23:02,920
>> Mais nous allons transition maintenant un peu plus
problèmes sophistiqués, si vous voulez,

460
00:23:02,920 --> 00:23:05,870
connu sous le nom de «recherche» et
«Tri», plus généralement.

461
00:23:05,870 --> 00:23:09,500
Nous avons eu ce livre de téléphone, voici l'heure, à
un autre juste pour discussion--

462
00:23:09,500 --> 00:23:13,460
que nous étions en mesure de rechercher
de façon plus efficace, car

463
00:23:13,460 --> 00:23:15,270
d'une hypothèse importante.

464
00:23:15,270 --> 00:23:17,655
Et juste pour être clair, ce qui
hypothèse était je faire

465
00:23:17,655 --> 00:23:19,280
lors de la recherche à travers ce livre de téléphone?

466
00:23:19,280 --> 00:23:23,342

467
00:23:23,342 --> 00:23:25,300
Ce Mike Smith était en
le livre de téléphone, si je

468
00:23:25,300 --> 00:23:27,410
serait capable de gérer
le scénario sans lui

469
00:23:27,410 --> 00:23:30,720
là si je viens d'arrêter prématurément.

470
00:23:30,720 --> 00:23:31,806
Le livre est alphabétique.

471
00:23:31,806 --> 00:23:33,930
Et c'est un très généreux
hypothèse, parce que

472
00:23:33,930 --> 00:23:36,580
signifie someone-- Je suis un peu
de couper un coin,

473
00:23:36,580 --> 00:23:40,580
comme je suis plus rapide parce que quelqu'un
d'autre a fait beaucoup de travail difficile pour moi.

474
00:23:40,580 --> 00:23:43,120
>> Mais si le téléphone
livre ont été unsorted?

475
00:23:43,120 --> 00:23:47,050
Peut-être que Verizon a obtenu paresseux, juste jeté
Les noms et les numéros de chacun là-bas

476
00:23:47,050 --> 00:23:50,120
peut-être dans l'ordre dans lequel ils
signé pour le service téléphonique.

477
00:23:50,120 --> 00:23:54,570
Et combien de temps faut-il me prendre
de trouver quelqu'un comme Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1000 pages téléphone book-- combien
pages que je dois regarder à travers?

479
00:23:58,160 --> 00:23:58,905
>> Tous.

480
00:23:58,905 --> 00:24:00,030
Vous êtes en quelque sorte hors de la chance.

481
00:24:00,030 --> 00:24:03,420
Vous avez littéralement à regarder tous les
page si l'annuaire est juste

482
00:24:03,420 --> 00:24:04,450
triées aléatoirement.

483
00:24:04,450 --> 00:24:06,910
Vous pourriez avoir de la chance et trouver Mike
sur la première page, parce qu'il

484
00:24:06,910 --> 00:24:08,826
a été le premier client
de commander un service de téléphone.

485
00:24:08,826 --> 00:24:10,760
Mais il aurait pu être le dernier, aussi.

486
00:24:10,760 --> 00:24:12,500
>> Donc un ordre aléatoire est pas bon.

487
00:24:12,500 --> 00:24:16,750
Supposons donc que nous devons trier la
annuaire téléphonique ou dans les données générales de tri

488
00:24:16,750 --> 00:24:18,520
que nous avons reçu.

489
00:24:18,520 --> 00:24:19,440
Comment peut-on faire ça?

490
00:24:19,440 --> 00:24:21,360
>> Eh bien, laissez-moi juste essayer
un exemple simple ici.

491
00:24:21,360 --> 00:24:24,290
Laissez-moi aller de l'avant et de lancer une
Quelques chiffres sur la carte.

492
00:24:24,290 --> 00:24:35,480
Supposons que les chiffres que nous avons sont,
disons, quatre, deux, un, et trois.

493
00:24:35,480 --> 00:24:38,390
Et, Ben, trier ces chiffres pour nous.

494
00:24:38,390 --> 00:24:39,017
>> OK, bien.

495
00:24:39,017 --> 00:24:39,850
Comment as-tu fais ça?

496
00:24:39,850 --> 00:24:42,731

497
00:24:42,731 --> 00:24:43,230
D'accord.

498
00:24:43,230 --> 00:24:44,710
Donc, commencer par le plus petit
et la valeur la plus élevée,

499
00:24:44,710 --> 00:24:46,084
et c'est vraiment une bonne intuition.

500
00:24:46,084 --> 00:24:48,080
Et réaliser que nous
les humains sont en fait assez

501
00:24:48,080 --> 00:24:49,913
bon à la résolution de problèmes
comme celui-ci, au moins

502
00:24:49,913 --> 00:24:51,810
lorsque les données sont relativement faibles.

503
00:24:51,810 --> 00:24:54,860
Dès que vous commencez à avoir des centaines
des nombres, des milliers de numéros,

504
00:24:54,860 --> 00:24:58,440
des millions de numéros, Ben probablement
ne pouvait pas le faire tout à fait aussi vite,

505
00:24:58,440 --> 00:25:00,620
en supposant qu'il y avait
les lacunes dans les chiffres.

506
00:25:00,620 --> 00:25:03,450
Assez facile de compter jusqu'à un million
sinon, juste du temps.

507
00:25:03,450 --> 00:25:07,150
>> Donc, l'algorithme il sonne
comme Ben utilisé tout à l'heure

508
00:25:07,150 --> 00:25:08,930
était la recherche du plus petit nombre.

509
00:25:08,930 --> 00:25:12,900
Donc, même si nous, les humains peuvent prendre
dans un grand nombre d'informations visuelles,

510
00:25:12,900 --> 00:25:14,830
un ordinateur est en réalité
un peu plus limitée.

511
00:25:14,830 --> 00:25:17,560
L'ordinateur ne peut
regarder un octet à la fois

512
00:25:17,560 --> 00:25:20,770
ou peut-être quatre octets à time--
ces jours peut-être 8 octets à time--

513
00:25:20,770 --> 00:25:24,450
mais un très petit nombre
d'octets à un moment donné.

514
00:25:24,450 --> 00:25:28,480
>> Donc, étant donné que nous avons vraiment
quatre valeurs distinctes ici--

515
00:25:28,480 --> 00:25:32,440
et vous pouvez penser à Ben comme ayant
oeillères s'il était un ordinateur tel

516
00:25:32,440 --> 00:25:36,450
qu'il ne peut pas voir autre chose
d'un numéro à un time--

517
00:25:36,450 --> 00:25:39,720
donc nous supposerons généralement, comme dans
Anglais, nous allons lire de droite à gauche.

518
00:25:39,720 --> 00:25:42,870
Donc, le premier numéro Ben probablement regardé
à était quatre, puis très rapidement

519
00:25:42,870 --> 00:25:44,770
réalisé que c'est un assez grand
number-- permettez-moi de continuer à chercher.

520
00:25:44,770 --> 00:25:45,357
>> Il y a deux.

521
00:25:45,357 --> 00:25:45,940
Attends une minute.

522
00:25:45,940 --> 00:25:47,070
Deux est inférieur à quatre.

523
00:25:47,070 --> 00:25:47,986
Je vais vous rappeler.

524
00:25:47,986 --> 00:25:49,070
Deux est maintenant le plus petit.

525
00:25:49,070 --> 00:25:50,417
Maintenant One-- qui est encore mieux.

526
00:25:50,417 --> 00:25:51,250
C'est encore plus faible.

527
00:25:51,250 --> 00:25:54,000
Je vais oublier deux
et rappelez-vous juste un maintenant.

528
00:25:54,000 --> 00:25:56,550
>> Et pourrait-il arrêter de regarder?

529
00:25:56,550 --> 00:25:58,360
Eh bien, il pouvait base
cette information,

530
00:25:58,360 --> 00:26:00,477
mais il ferait mieux de recherche
le reste de la liste.

531
00:26:00,477 --> 00:26:02,060
Parce que si zéro étaient dans la liste?

532
00:26:02,060 --> 00:26:03,643
Que si négatif on était dans la liste?

533
00:26:03,643 --> 00:26:07,720
Il sait seulement que sa réponse
est correct s'il est exhaustive

534
00:26:07,720 --> 00:26:08,729
vérifier toute la liste.

535
00:26:08,729 --> 00:26:10,020
Donc, nous regardons le reste de cette.

536
00:26:10,020 --> 00:26:11,394
Three-- qui était une perte de temps.

537
00:26:11,394 --> 00:26:13,540
Got chance, mais j'étais
toujours correct de le faire.

538
00:26:13,540 --> 00:26:17,857
Et maintenant il vraisemblablement
choisi le plus petit nombre

539
00:26:17,857 --> 00:26:20,440
et vient de mettre au début
de la liste, comme je vais le faire ici.

540
00:26:20,440 --> 00:26:23,480
Maintenant, qu'avez-vous fait à côté, même si
vous ne pensez pas à ce sujet presque

541
00:26:23,480 --> 00:26:25,962
dans cette mesure?

542
00:26:25,962 --> 00:26:27,670
Répétez le processus,
donc une sorte de boucle.

543
00:26:27,670 --> 00:26:28,920
Il y a une idée familière.

544
00:26:28,920 --> 00:26:30,860
Voici donc quatre.

545
00:26:30,860 --> 00:26:32,110
C'est actuellement le plus petit.

546
00:26:32,110 --> 00:26:33,220
C'est un candidat.

547
00:26:33,220 --> 00:26:33,900
Plus maintenant.

548
00:26:33,900 --> 00:26:34,770
Maintenant, je l'ai vu deux.

549
00:26:34,770 --> 00:26:36,630
Voilà l'élément suivant le plus petit.

550
00:26:36,630 --> 00:26:40,800
Three-- ce n'est pas plus petit, de sorte
maintenant Ben peut arracher les deux.

551
00:26:40,800 --> 00:26:44,510
>> Et maintenant, nous répétons le processus et
des cours de trois obtient retirée suivant.

552
00:26:44,510 --> 00:26:45,420
Répétez le processus.

553
00:26:45,420 --> 00:26:46,990
Quatre obtient retirée.

554
00:26:46,990 --> 00:26:50,140
Et maintenant, nous sommes sur le nombre,
de sorte que la liste doit être triée.

555
00:26:50,140 --> 00:26:51,960
>> Et en effet, cela est un algorithme formel.

556
00:26:51,960 --> 00:26:56,610
Un informaticien serait
appeler cette "sorte de sélection,"

557
00:26:56,610 --> 00:27:00,880
l'idée étant un genre
liste iteratively-- nouveau

558
00:27:00,880 --> 00:27:03,807
et encore et encore la sélection
le plus petit nombre.

559
00:27:03,807 --> 00:27:06,140
Et ce qui est agréable à ce sujet est
il est tellement sacrément intuitive.

560
00:27:06,140 --> 00:27:07,470
Il est si simple.

561
00:27:07,470 --> 00:27:11,100
Et vous pouvez répéter la même
opération encore et encore.

562
00:27:11,100 --> 00:27:12,150
C'est simple.

563
00:27:12,150 --> 00:27:17,170
>> Dans ce cas, il a été rapide, mais
combien de temps faut-il réellement prendre?

564
00:27:17,170 --> 00:27:19,880
Faisons croire et
sentir un peu plus fastidieux.

565
00:27:19,880 --> 00:27:24,150
Donc, un, deux, trois, quatre, cinq six,
sept, huit, neuf, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- nombre arbitraire.

567
00:27:26,160 --> 00:27:28,780
Je voulais simplement plus ce
temps que juste quatre.

568
00:27:28,780 --> 00:27:30,780
Donc, si j'ai un ensemble
tas de chiffres maintenant-- il

569
00:27:30,780 --> 00:27:32,420
n'a même pas d'importance
ce qu'ils soient: LET

570
00:27:32,420 --> 00:27:34,380
penser à ce que cette
algorithme est vraiment.

571
00:27:34,380 --> 00:27:35,857
>> Supposons qu'il y ait un nombre là-bas.

572
00:27:35,857 --> 00:27:38,190
Encore une fois, n'a pas d'importance ce que
ils sont, mais ils sont aléatoires.

573
00:27:38,190 --> 00:27:39,679
Je demande l'algorithme de Ben.

574
00:27:39,679 --> 00:27:41,220
Je dois sélectionner le plus petit nombre.

575
00:27:41,220 --> 00:27:41,761
Que fais-je?

576
00:27:41,761 --> 00:27:44,240
Et je vais physiquement
faire cette fois-ci d'agir it out.

577
00:27:44,240 --> 00:27:46,099
Regarder, regarder,
à la recherche, à la recherche, à la recherche.

578
00:27:46,099 --> 00:27:48,140
Seulement le temps que je reçois à
la fin de la liste peut

579
00:27:48,140 --> 00:27:51,230
Je me rends compte le plus petit
nombre était deux cette fois.

580
00:27:51,230 --> 00:27:52,720
On est pas dans la liste.

581
00:27:52,720 --> 00:27:54,400
Donc, je pose deux.

582
00:27:54,400 --> 00:27:55,590
>> Je fais quoi ensuite?

583
00:27:55,590 --> 00:27:58,600
Regardant, regardant, regardant, regardant.

584
00:27:58,600 --> 00:28:02,250
Maintenant, je trouve le numéro sept, parce que
il y a des lacunes dans ces numbers--

585
00:28:02,250 --> 00:28:03,300
mais juste arbitraire.

586
00:28:03,300 --> 00:28:03,800
D'accord.

587
00:28:03,800 --> 00:28:06,030
Alors maintenant, je peux déposer sept.

588
00:28:06,030 --> 00:28:08,860
Regarder regarder, regarder.

589
00:28:08,860 --> 00:28:11,030
>> Maintenant, je suis en supposant,
bien sûr, que Ben ne

590
00:28:11,030 --> 00:28:14,780
avoir la RAM supplémentaire, en sus
la mémoire, parce que, bien sûr,

591
00:28:14,780 --> 00:28:16,080
Je regarde le même numéro.

592
00:28:16,080 --> 00:28:18,246
Certes, je pouvais me suis souvenu
tous ces chiffres,

593
00:28:18,246 --> 00:28:19,930
et c'est absolument vrai.

594
00:28:19,930 --> 00:28:22,610
Mais si Ben se souvient tous
des chiffres qu'il a vu,

595
00:28:22,610 --> 00:28:24,430
il n'a pas vraiment fait
progrès fondamentaux

596
00:28:24,430 --> 00:28:26,170
parce qu'il a déjà
la capacité de recherche

597
00:28:26,170 --> 00:28:27,540
à travers les numéros sur la carte.

598
00:28:27,540 --> 00:28:29,373
Se souvenant tous les
numéros n'aide pas,

599
00:28:29,373 --> 00:28:32,490
parce qu'il peut encore comme un ordinateur
seulement regarder, nous l'avons dit, un seul numéro

600
00:28:32,490 --> 00:28:33,080
à la fois.

601
00:28:33,080 --> 00:28:35,760
Donc, il n'y a aucune sorte de triche
là que vous pouvez tirer parti.

602
00:28:35,760 --> 00:28:39,170
>> Donc, en réalité, comme je
continuer à chercher la liste,

603
00:28:39,170 --> 00:28:44,200
Je dois littéralement juste continuer
avant et en arrière à travers elle, arrachant

604
00:28:44,200 --> 00:28:45,710
le prochain plus petit nombre.

605
00:28:45,710 --> 00:28:48,810
Et comme vous pouvez le genre d'inférer
de mes mouvements stupides,

606
00:28:48,810 --> 00:28:50,860
cela devient juste très
fastidieuse très rapidement,

607
00:28:50,860 --> 00:28:54,850
et il me semble être revenir en arrière et
avant, en arrière un peu.

608
00:28:54,850 --> 00:29:03,220
Maintenant, pour être honnête, je ne dois pas aller
tout aussi bien, disons see-- pour être juste,

609
00:29:03,220 --> 00:29:06,310
Je ne dois marcher tout à fait
autant d'étapes à chaque fois.

610
00:29:06,310 --> 00:29:09,200
Parce que, bien sûr, comme je
sélectionner les numéros de la liste,

611
00:29:09,200 --> 00:29:11,860
la liste restante devient plus courte.

612
00:29:11,860 --> 00:29:14,240
>> Et donc nous allons réfléchir à
combien d'étapes que je suis en fait

613
00:29:14,240 --> 00:29:16,010
traipsing à travers chaque fois.

614
00:29:16,010 --> 00:29:18,950
Dans le premier cas
nous avons eu 16 numéros,

615
00:29:18,950 --> 00:29:22,210
et ainsi maximally-- de simplement laisser
faire pour un discussion--

616
00:29:22,210 --> 00:29:25,640
Je devais regarder à travers 16
numéros pour trouver le plus petit.

617
00:29:25,640 --> 00:29:28,420
Mais une fois que je tirais sur
le plus petit nombre, comment

618
00:29:28,420 --> 00:29:30,590
longue est la liste restante, bien sûr?

619
00:29:30,590 --> 00:29:31,420
Juste 15.

620
00:29:31,420 --> 00:29:34,670
Alors, combien de numéros a fait Ben ou moi avons
de regarder à travers la deuxième fois?

621
00:29:34,670 --> 00:29:36,832
15, juste pour aller chercher le plus petit.

622
00:29:36,832 --> 00:29:39,540
Mais maintenant, bien sûr, la liste est,
aussi, inférieure à ce qu'elle était avant.

623
00:29:39,540 --> 00:29:42,540
Alors, comment de nombreuses étapes ai-je
prendre la prochaine fois?

624
00:29:42,540 --> 00:29:49,970
14 puis 13, puis 12, plus de points,
dot, dot, jusqu'à ce que je me retrouve avec un seul.

625
00:29:49,970 --> 00:29:53,146
Alors maintenant, un informaticien serait
demander, eh bien, qu'est-ce que tous égaux?

626
00:29:53,146 --> 00:29:55,770
Elle est égale à fait du béton
nombre que nous pourrions certainement

627
00:29:55,770 --> 00:30:00,490
faisons arithmétiquement, mais nous voulons parler
à propos de l'efficacité des algorithmes

628
00:30:00,490 --> 00:30:04,940
un peu plus formulaically,
indépendante de combien de temps la liste est.

629
00:30:04,940 --> 00:30:06,240
>> Et vous savez quoi?

630
00:30:06,240 --> 00:30:09,860
Ceci est 16, mais comme je l'ai dit avant,
disons simplement appeler la taille du problème

631
00:30:09,860 --> 00:30:10,970
n, où n est un nombre.

632
00:30:10,970 --> 00:30:13,220
Peut-être qu'il est 16, peut-être il est
trois, peut-être qu'il ya un million.

633
00:30:13,220 --> 00:30:13,761
Je ne sais pas.

634
00:30:13,761 --> 00:30:14,390
Je ne me soucie pas.

635
00:30:14,390 --> 00:30:16,520
Ce que je veux vraiment est
une formule que je peux

636
00:30:16,520 --> 00:30:19,420
utiliser pour comparer cet algorithme
contre d'autres algorithmes

637
00:30:19,420 --> 00:30:22,350
que quelqu'un pourrait prétendre
sont mieux ou pire.

638
00:30:22,350 --> 00:30:25,430
>> Donc, il se trouve, et je ne
le savoir de l'école primaire,

639
00:30:25,430 --> 00:30:34,790
que cela fonctionne réellement sur le même
chose que n sur n plus un sur deux.

640
00:30:34,790 --> 00:30:40,020
Et cela arrive à égaler, de
Bien sûr, n au carré plus n plus de deux.

641
00:30:40,020 --> 00:30:43,250
Donc, si je voulais une formule
pour combien d'étapes

642
00:30:43,250 --> 00:30:46,330
ont participé à la recherche du tout
de ces chiffres, encore et encore

643
00:30:46,330 --> 00:30:52,681
et encore et encore, je dirais
il est n au carré plus n plus de deux.

644
00:30:52,681 --> 00:30:53,430
Mais tu sais quoi?

645
00:30:53,430 --> 00:30:54,500
Cela semble juste en désordre.

646
00:30:54,500 --> 00:30:56,470
Je veux juste vraiment un
sens général des choses.

647
00:30:56,470 --> 00:30:58,810
Et vous souvenez peut-être de
lycée qu'il y

648
00:30:58,810 --> 00:31:00,660
est la notion de la plus haute expression de l'ordre.

649
00:31:00,660 --> 00:31:05,300
Lequel de ces termes, la n
carré, le n, ou de la moitié,

650
00:31:05,300 --> 00:31:07,550
a le plus d'impact au fil du temps?

651
00:31:07,550 --> 00:31:11,920
Le plus grand n obtient, qui
de ces questions le plus?

652
00:31:11,920 --> 00:31:15,560
>> En d'autres termes, si je branche
sur un million, n au carré

653
00:31:15,560 --> 00:31:17,900
va être le plus probable
le facteur dominant,

654
00:31:17,900 --> 00:31:21,670
parce que un million de fois
lui-même est beaucoup plus grand

655
00:31:21,670 --> 00:31:23,682
que plus un million supplémentaire.

656
00:31:23,682 --> 00:31:24,390
Donc, vous savez quoi?

657
00:31:24,390 --> 00:31:27,305
Ceci est un sacrément grand
numéro si vous conciliez un numéro.

658
00:31:27,305 --> 00:31:28,430
Cela n'a pas d'importance.

659
00:31:28,430 --> 00:31:30,596
Nous allons juste croix
oublier dehors et à ce sujet.

660
00:31:30,596 --> 00:31:34,250
Et un informaticien dirait
que l'efficacité de cet algorithme,

661
00:31:34,250 --> 00:31:37,850
est de l'ordre de n squared--
Je veux dire vraiment une approximation.

662
00:31:37,850 --> 00:31:40,810
Il est en quelque sorte à peu près n au carré.

663
00:31:40,810 --> 00:31:44,130
Au fil du temps, plus
et plus grand n obtient, cette

664
00:31:44,130 --> 00:31:47,610
est une bonne estimation de ce que le
l'efficacité ou le manque d'efficacité

665
00:31:47,610 --> 00:31:49,400
de cet algorithme est en réalité.

666
00:31:49,400 --> 00:31:52,040
Et je tire cela, bien sûr,
du fait de faire le calcul.

667
00:31:52,040 --> 00:31:54,040
Mais maintenant, je suis juste en agitant
mes mains, parce que je viens

668
00:31:54,040 --> 00:31:55,790
veulent un sens général de cet algorithme.

669
00:31:55,790 --> 00:31:58,850
>> Donc, en utilisant la même logique, quant à lui,
nous allons examiner un autre algorithme

670
00:31:58,850 --> 00:32:01,162
nous avons déjà regardé at-- recherche linéaire.

671
00:32:01,162 --> 00:32:02,870
Quand je cherchais
pour le téléphone book--

672
00:32:02,870 --> 00:32:05,980
pas trier, rechercher
par l'intermédiaire du téléphone book--

673
00:32:05,980 --> 00:32:09,197
nous avons continué en disant qu'il était
1000 marches, ou 500 étapes.

674
00:32:09,197 --> 00:32:10,280
Mais nous allons généraliser cela.

675
00:32:10,280 --> 00:32:12,860
S'il y a n pages
le livre de téléphone, ce qui est

676
00:32:12,860 --> 00:32:17,250
le temps d'exécution ou de la
efficacité de la recherche linéaire?

677
00:32:17,250 --> 00:32:19,750
Il est de l'ordre de
combien d'étapes pour trouver

678
00:32:19,750 --> 00:32:24,210
Mike Smith en utilisant la recherche linéaire, la
premier algorithme, ou même la deuxième?

679
00:32:24,210 --> 00:32:27,240

680
00:32:27,240 --> 00:32:31,710
>> Dans le pire des cas, Mike
est à la fin du livre.

681
00:32:31,710 --> 00:32:35,590
Donc, si le répertoire a 1.000 pages,
nous avons dit la dernière fois, dans le pire des cas,

682
00:32:35,590 --> 00:32:38,380
il pourrait prendre à peu près comment
beaucoup de pages pour trouver Mike?

683
00:32:38,380 --> 00:32:38,990
Comme 1000.

684
00:32:38,990 --> 00:32:39,830
Il est une limite supérieure.

685
00:32:39,830 --> 00:32:41,790
Il est une pire situation possible.

686
00:32:41,790 --> 00:32:44,410
Mais encore une fois, nous nous éloignons
à partir des chiffres comme 1000 maintenant.

687
00:32:44,410 --> 00:32:45,730
Il est juste n.

688
00:32:45,730 --> 00:32:47,470
>> Alors, quelle est la conclusion logique?

689
00:32:47,470 --> 00:32:50,210
Trouver Mike dans un téléphone
livre qui a n pages

690
00:32:50,210 --> 00:32:55,280
pourrait prendre, dans le pire des cas,
combien d'étapes de l'ordre de n?

691
00:32:55,280 --> 00:32:58,110
Et en effet, un ordinateur
scientifique dirait

692
00:32:58,110 --> 00:33:02,340
que le temps d'exécution, ou
le rendement ou l'efficacité

693
00:33:02,340 --> 00:33:07,470
ou l'inefficacité, d'un algorithme comme
une recherche linéaire est de l'ordre de n.

694
00:33:07,470 --> 00:33:10,010
Et nous pouvons appliquer le même
la logique de traverser quelque chose

695
00:33:10,010 --> 00:33:13,170
comme je viens à la seconde
algorithme que nous avions avec le livre de téléphone,

696
00:33:13,170 --> 00:33:16,040
où nous sommes allés deux pages à la fois.

697
00:33:16,040 --> 00:33:20,120
>> Donc 1000 pages annuaire pourrait
nous prendre 500 page se tourne, plus un

698
00:33:20,120 --> 00:33:21,910
si nous doublons un peu en arrière.

699
00:33:21,910 --> 00:33:26,590
Donc, si un livre de téléphone a n pages, mais
nous faisons deux pages à la fois,

700
00:33:26,590 --> 00:33:28,900
qui est plus ou moins quoi?

701
00:33:28,900 --> 00:33:33,190
N plus de deux, de sorte que est comme n sur deux.

702
00:33:33,190 --> 00:33:38,490
Mais j'ai fait la demande d'un
il y a instant que n sur two--

703
00:33:38,490 --> 00:33:41,060
qui est le genre de même que tout n.

704
00:33:41,060 --> 00:33:44,050
Il est juste un facteur constant,
les informaticiens diraient.

705
00:33:44,050 --> 00:33:45,970
Concentrons uniquement sur
les variables, really--

706
00:33:45,970 --> 00:33:47,780
les plus grandes variables de l'équation.

707
00:33:47,780 --> 00:33:52,530
>> recherche donc linéaire, se fait un
page à la fois ou deux pages à la fois,

708
00:33:52,530 --> 00:33:54,810
est une sorte de fondamentalement les mêmes.

709
00:33:54,810 --> 00:33:56,880
Il est encore de l'ordre de n.

710
00:33:56,880 --> 00:34:01,930
Mais je prétendais avec ma photo précédente
que le troisième algorithme n'a pas été

711
00:34:01,930 --> 00:34:02,480
linéaire.

712
00:34:02,480 --> 00:34:03,605
Ce ne fut pas une ligne droite.

713
00:34:03,605 --> 00:34:08,659
Il était cette ligne courbe, et
formule algébrique il y avait quoi?

714
00:34:08,659 --> 00:34:11,812
Connexion de n-- donc log base deux de n.

715
00:34:11,812 --> 00:34:14,520
Et nous ne devons pas aller trop
beaucoup de détails sur logarithmes aujourd'hui,

716
00:34:14,520 --> 00:34:17,394
mais la plupart des informaticiens ne serait pas
même vous dire ce que la base est.

717
00:34:17,394 --> 00:34:20,639
Parce qu'il est tout simplement
facteurs constants, pour ainsi dire,

718
00:34:20,639 --> 00:34:22,659
seulement de légères différences numériques.

719
00:34:22,659 --> 00:34:31,179
Et ce serait un très commun
façon pour ordinateur particulièrement formelle

720
00:34:31,179 --> 00:34:33,949
scientifiques à un conseil ou
programmeurs à un tableau blanc

721
00:34:33,949 --> 00:34:36,889
fait valoir que
algorithme qu'ils utiliseraient

722
00:34:36,889 --> 00:34:39,500
ou ce que l'efficacité
de leur algorithme est.

723
00:34:39,500 --> 00:34:42,960
>> Et ce ne sont pas nécessairement quelque chose
vous discutez dans le détail,

724
00:34:42,960 --> 00:34:47,889
mais un bon programmeur est quelqu'un
qui a un arrière-plan formel solide.

725
00:34:47,889 --> 00:34:50,120
Il est capable de parler
vous dans ce genre de façon

726
00:34:50,120 --> 00:34:53,350
et effectivement faire
arguments qualitatifs que

727
00:34:53,350 --> 00:34:56,870
les raisons pour lesquelles un algorithme ou
une pièce de logiciel

728
00:34:56,870 --> 00:35:00,165
est supérieure d'une certaine façon à l'autre.

729
00:35:00,165 --> 00:35:02,540
Parce que vous pourriez certainement
il suffit d'exécuter le programme d'une personne

730
00:35:02,540 --> 00:35:04,980
et compter le nombre de secondes
il faut trier certains numéros,

731
00:35:04,980 --> 00:35:06,710
et vous pouvez exécuter certains
Le programme d'une autre personne

732
00:35:06,710 --> 00:35:08,418
et compter le nombre
de secondes qu'il faut.

733
00:35:08,418 --> 00:35:12,840
Mais ceci est une façon plus générale que
vous pouvez utiliser pour analyser des algorithmes,

734
00:35:12,840 --> 00:35:15,520
si vous voulez, juste
papier ou tout simplement verbalement.

735
00:35:15,520 --> 00:35:18,430
Sans même en cours d'exécution, sans
même essayer des entrées d'échantillons,

736
00:35:18,430 --> 00:35:20,180
vous pouvez simplement raisonner à travers elle.

737
00:35:20,180 --> 00:35:24,670
Et ainsi, avec l'embauche d'un développeur ou si
qu'il y soit sorte d'argumenter pour vous

738
00:35:24,670 --> 00:35:28,460
pourquoi leur algorithme, leur secret
sauce pour la recherche des milliards

739
00:35:28,460 --> 00:35:30,580
des pages web pour votre
la société est mieux, ceux-ci

740
00:35:30,580 --> 00:35:33,302
sont les types d'arguments qu'ils
devrait idéalement être en mesure de faire.

741
00:35:33,302 --> 00:35:35,010
Ou du moins ce sont
le genre de choses

742
00:35:35,010 --> 00:35:40,211
qui viendrait en discussion, à
moins dans une discussion très formelle.

743
00:35:40,211 --> 00:35:40,710
D'accord.

744
00:35:40,710 --> 00:35:44,400
Donc, Ben a proposé quelque chose
appelé sélection tri.

745
00:35:44,400 --> 00:35:48,200
Mais je vais proposer qu'il ya
d'autres façons de le faire, aussi.

746
00:35:48,200 --> 00:35:50,400
Ce que je n'aime vraiment
à propos de l'algorithme de Ben

747
00:35:50,400 --> 00:35:54,400
est qu'il a continué à marcher, ou
ayant moi marcher, aller et retour

748
00:35:54,400 --> 00:35:56,930
et en arrière et en arrière.

749
00:35:56,930 --> 00:36:04,130
Et si au lieu que je devais faire
quelque chose comme ces chiffres ici

750
00:36:04,130 --> 00:36:08,200
et je devais traiter seulement avec chaque
nombre à son tour que je suis donnée?

751
00:36:08,200 --> 00:36:10,780
>> En d'autres mots, voici
ma liste de numéros.

752
00:36:10,780 --> 00:36:12,944
Quatre, une, trois, deux.

753
00:36:12,944 --> 00:36:14,360
Et je vais faire ce qui suit.

754
00:36:14,360 --> 00:36:17,230
Je vais insérer les numéros
où ils appartiennent plutôt

755
00:36:17,230 --> 00:36:18,980
que de les sélectionner un à la fois.

756
00:36:18,980 --> 00:36:20,820
En d'autres mots, voici le numéro quatre.

757
00:36:20,820 --> 00:36:22,430
>> Voici ma liste originale.

758
00:36:22,430 --> 00:36:25,290
Et je vais maintenir
essentiellement une nouvelle liste.

759
00:36:25,290 --> 00:36:26,710
Donc, c'est l'ancienne liste.

760
00:36:26,710 --> 00:36:28,560
Ceci est la nouvelle liste.

761
00:36:28,560 --> 00:36:30,220
Je vois le numéro quatre premiers.

762
00:36:30,220 --> 00:36:34,500
Ma nouvelle liste est initialement vide,
il est donc trivialement le cas

763
00:36:34,500 --> 00:36:36,410
que quatre est maintenant la liste assorties.

764
00:36:36,410 --> 00:36:39,560
Je prends juste le nombre que je me donne,
et je le mettre dans ma nouvelle liste.

765
00:36:39,560 --> 00:36:41,460
>> Est-ce que cette nouvelle liste triée?

766
00:36:41,460 --> 00:36:41,990
Ouais.

767
00:36:41,990 --> 00:36:45,090
Il est stupide parce qu'il n'y a qu'un seul
élément, mais il est absolument triée.

768
00:36:45,090 --> 00:36:46,390
Il n'y a rien hors de l'endroit.

769
00:36:46,390 --> 00:36:49,290
Il est plus intéressant, cet algorithme,
quand je passe à l'étape suivante.

770
00:36:49,290 --> 00:36:50,550
>> Maintenant, j'ai un.

771
00:36:50,550 --> 00:36:55,430
Donc, bien sûr, appartient à la
début ou la fin de cette nouvelle liste?

772
00:36:55,430 --> 00:36:56,360
Le début.

773
00:36:56,360 --> 00:36:58,530
Je dois donc faire un travail maintenant.

774
00:36:58,530 --> 00:37:01,410
Je prends un peu
libertés avec mon marqueur

775
00:37:01,410 --> 00:37:03,120
simplement en tirant les choses
où je les veux,

776
00:37:03,120 --> 00:37:05,320
mais ce n'est pas vraiment
précises dans un ordinateur.

777
00:37:05,320 --> 00:37:08,530
Un ordinateur, comme nous le savons, a
RAM ou Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
et c'est un octet et
un autre octet et un autre octet.

779
00:37:12,411 --> 00:37:14,910
Et si vous avez un gigaoctet de
RAM, vous avez un milliard d'octets,

780
00:37:14,910 --> 00:37:16,680
mais ils sont physiquement en un seul endroit.

781
00:37:16,680 --> 00:37:19,540
Vous ne pouvez pas déplacer des choses autour
en dessinant sur le tableau

782
00:37:19,540 --> 00:37:20,750
où tu veux.

783
00:37:20,750 --> 00:37:24,090
Donc, si ma nouvelle liste a
quatre emplacements en mémoire,

784
00:37:24,090 --> 00:37:27,480
malheureusement quatre est
déjà dans le mauvais endroit.

785
00:37:27,480 --> 00:37:30,410
>> Donc, pour insérer le numéro un
Je ne peux pas dessiner ici.

786
00:37:30,410 --> 00:37:31,901
n'existe pas cet emplacement mémoire.

787
00:37:31,901 --> 00:37:35,150
Ce serait tricher, et je l'ai été
tricherie imagée pendant quelques minutes,

788
00:37:35,150 --> 00:37:35,800
ici.

789
00:37:35,800 --> 00:37:40,950
Alors, vraiment, si je veux mettre un ici,
Je dois copier temporairement les quatre

790
00:37:40,950 --> 00:37:43,030
et puis mettre celui là.

791
00:37:43,030 --> 00:37:45,500
>> Ça va, c'est exact,
qui est techniquement possible,

792
00:37:45,500 --> 00:37:48,410
mais se rendent compte que ce travail supplémentaire.

793
00:37:48,410 --> 00:37:50,460
Je ne viens de mettre le numéro en place.

794
00:37:50,460 --> 00:37:53,026
Je devais d'abord déplacer un
numéro, puis le mettre en place,

795
00:37:53,026 --> 00:37:54,650
donc je sorte de doublé mon volume de travail.

796
00:37:54,650 --> 00:37:55,660
Alors garde cela en tête.

797
00:37:55,660 --> 00:37:57,120
>> Mais je suis maintenant fait avec cet élément.

798
00:37:57,120 --> 00:37:59,056
Maintenant, je veux saisir le numéro trois.

799
00:37:59,056 --> 00:38:00,430
Si, bien sûr, appartient-il?

800
00:38:00,430 --> 00:38:01,480
Entre.

801
00:38:01,480 --> 00:38:03,650
Je ne peux plus tricher
et juste le mettre là,

802
00:38:03,650 --> 00:38:06,770
parce que, encore une fois, cette mémoire
est dans des emplacements physiques.

803
00:38:06,770 --> 00:38:10,900
Je dois donc copier les quatre
et de mettre les trois ici.

804
00:38:10,900 --> 00:38:11,550
Pas un gros problème.

805
00:38:11,550 --> 00:38:14,610
Il est juste une étape supplémentaire
again-- sent très bon marché.

806
00:38:14,610 --> 00:38:16,445
>> Mais maintenant, je passe à deux.

807
00:38:16,445 --> 00:38:17,820
Les deux, bien sûr, appartient ici.

808
00:38:17,820 --> 00:38:20,990
Maintenant, vous commencez à voir comment
le travail peut accumuler.

809
00:38:20,990 --> 00:38:23,520
Maintenant, que dois-je faire?

810
00:38:23,520 --> 00:38:28,570
Ouais, je dois déplacer les quatre,
Je dois ensuite copier les trois,

811
00:38:28,570 --> 00:38:31,200
et maintenant je peux insérer les deux.

812
00:38:31,200 --> 00:38:34,460
Et la prise de cette
algorithme, il est intéressant,

813
00:38:34,460 --> 00:38:41,050
est que supposons que nous avons une plus grande
cas où il est, disons huit, sept,

814
00:38:41,050 --> 00:38:45,150
six, cinq, quatre, trois, deux, un.

815
00:38:45,150 --> 00:38:49,450
Ceci est, dans de nombreux contextes,
le pire des cas,

816
00:38:49,450 --> 00:38:51,570
parce que la chose sacrément
est littéralement en arrière.

817
00:38:51,570 --> 00:38:53,670
>> Il n'a pas vraiment
affecter l'algorithme de Ben,

818
00:38:53,670 --> 00:38:55,940
parce que, dans la sélection de Ben
sorte qu'il va garder

819
00:38:55,940 --> 00:38:58,359
des allers-retours dans la liste.

820
00:38:58,359 --> 00:39:01,150
Et parce qu'il était toujours à la recherche
à travers toute la liste restante,

821
00:39:01,150 --> 00:39:02,858
ça ne fait rien
où les éléments se trouvent.

822
00:39:02,858 --> 00:39:05,630
Mais dans ce cas avec mon insertion
approach-- nous allons essayer cela.

823
00:39:05,630 --> 00:39:08,616
>> Donc, une, deux, trois, quatre,
cinq, six, sept, huit.

824
00:39:08,616 --> 00:39:11,630
Un deux trois quatre,
cinq, six, sept, huit.

825
00:39:11,630 --> 00:39:14,320
Je vais prendre les huit,
et où dois-je le mettre?

826
00:39:14,320 --> 00:39:17,260
Eh bien, au début de ma liste,
parce que cette nouvelle liste est triée.

827
00:39:17,260 --> 00:39:18,760
Et je croise dehors.

828
00:39:18,760 --> 00:39:20,551
>> Où dois-je mettre les sept?

829
00:39:20,551 --> 00:39:21,050
Mince.

830
00:39:21,050 --> 00:39:23,174
Il faut y aller, donc
Je dois faire un peu de copie.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
Et maintenant sept va ici.

833
00:39:28,480 --> 00:39:29,860
Maintenant, je passe à six.

834
00:39:29,860 --> 00:39:30,980
Il est désormais encore plus de travail.

835
00:39:30,980 --> 00:39:32,570
>> Huit doit aller ici.

836
00:39:32,570 --> 00:39:33,920
Seven doit aller ici.

837
00:39:33,920 --> 00:39:35,450
Maintenant, les six peuvent aller ici.

838
00:39:35,450 --> 00:39:37,950
Je prends maintenant cinq.

839
00:39:37,950 --> 00:39:40,560
Maintenant, les huit doit aller
ici, sept doit aller ici,

840
00:39:40,560 --> 00:39:43,650
six doit aller ici, et
maintenant cinq et répéter.

841
00:39:43,650 --> 00:39:46,610
Et je suis à peu près
déplacer constamment.

842
00:39:46,610 --> 00:39:52,950
>> Donc, à la fin, ce algorithm-- nous allons
appeler insertion sort-- effectivement

843
00:39:52,950 --> 00:39:55,020
a beaucoup de travail, aussi.

844
00:39:55,020 --> 00:39:56,970
Il est juste différent
genre de travail que Ben.

845
00:39:56,970 --> 00:40:00,090
Le travail de Ben m'a aller
avant et en arrière tout le temps,

846
00:40:00,090 --> 00:40:03,510
sélection de la plus petite suivante
élément encore et encore.

847
00:40:03,510 --> 00:40:06,660
Il était donc ce genre très visuel de travail.

848
00:40:06,660 --> 00:40:10,600
>> Cet autre algorithme, qui est toujours
correct-- il va faire le travail done--

849
00:40:10,600 --> 00:40:12,800
modifie simplement la quantité de travail.

850
00:40:12,800 --> 00:40:15,420
On dirait que vous êtes d'abord
sauver, parce que vous êtes juste

851
00:40:15,420 --> 00:40:19,190
traiter chaque élément
à l'avant sans marcher tout

852
00:40:19,190 --> 00:40:20,930
le chemin à travers la liste comme Ben était.

853
00:40:20,930 --> 00:40:25,300
Mais le problème est, en particulier dans ces
cas fous où il est tout à l'envers,

854
00:40:25,300 --> 00:40:27,830
vous êtes juste un peu
retarder le travail acharné

855
00:40:27,830 --> 00:40:30,360
jusqu'à ce que vous devez corriger vos erreurs.

856
00:40:30,360 --> 00:40:33,919
>> Et donc si vous pouvez imaginer ce
huit et sept et six et cinq

857
00:40:33,919 --> 00:40:36,710
puis trois et quatre, et deux
déplacer leur chemin à travers la liste,

858
00:40:36,710 --> 00:40:39,060
nous venons tout juste changé le
type de travail que nous faisons.

859
00:40:39,060 --> 00:40:42,340
Au lieu de le faire à la
à partir de mon itération,

860
00:40:42,340 --> 00:40:45,250
Je suis juste le faire à la
la fin de chaque itération.

861
00:40:45,250 --> 00:40:50,550
Ainsi, il apparaît que cet algorithme,
trop, généralement appelé tri par insertion,

862
00:40:50,550 --> 00:40:52,190
est également de l'ordre de n au carré.

863
00:40:52,190 --> 00:40:56,480
Il est en fait pas mieux,
pas mieux du tout.

864
00:40:56,480 --> 00:41:00,810
>> Cependant, il y a une troisième approche
Je voudrais nous encourager à envisager,

865
00:41:00,810 --> 00:41:02,970
qui est-ce.

866
00:41:02,970 --> 00:41:07,850
Supposons donc que ma liste, pour la simplicité
encore, est de quatre, une, trois,

867
00:41:07,850 --> 00:41:11,080
two-- seulement quatre numéros.

868
00:41:11,080 --> 00:41:13,300
Ben avait une bonne intuition,
bonne intuition humaine

869
00:41:13,300 --> 00:41:16,340
avant, par lequel nous avons fixé l'ensemble
liste eventually-- tri par insertion.

870
00:41:16,340 --> 00:41:18,020
Je nous cajolé le long.

871
00:41:18,020 --> 00:41:22,530
Mais nous allons examiner la
manière la plus simple de fixer cette liste.

872
00:41:22,530 --> 00:41:24,110
>> Cette liste ne sont pas triées.

873
00:41:24,110 --> 00:41:26,130
Pourquoi?

874
00:41:26,130 --> 00:41:31,920
En anglais, expliquer pourquoi
il est pas réellement triée.

875
00:41:31,920 --> 00:41:33,400
Qu'est-ce que cela signifie de ne pas être triés?

876
00:41:33,400 --> 00:41:34,220
>> ÉTUDIANT: Il est pas séquentiel.

877
00:41:34,220 --> 00:41:34,990
>> DAVID MALAN: Non séquentiel.

878
00:41:34,990 --> 00:41:35,822
Donne moi un exemple.

879
00:41:35,822 --> 00:41:37,180
>> ÉTUDIANTS: Mettez-les dans l'ordre.

880
00:41:37,180 --> 00:41:37,440
>> DAVID MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Donnez-moi un exemple plus précis.

882
00:41:38,790 --> 00:41:39,832
>> ÉTUDIANTS: Ascendant.

883
00:41:39,832 --> 00:41:41,206
DAVID MALAN: Non ordre croissant.

884
00:41:41,206 --> 00:41:42,100
Soyez plus précis.

885
00:41:42,100 --> 00:41:45,190
Je ne sais pas ce que vous entendez par ordre croissant.

886
00:41:45,190 --> 00:41:47,150
Qu'est-ce qui ne va pas?

887
00:41:47,150 --> 00:41:49,930
>> ÉTUDIANTS: Le plus petit de la
les numéros ne sont pas dans le premier espace.

888
00:41:49,930 --> 00:41:51,140
>> DAVID MALAN: Le plus petit nombre de
pas dans le premier espace.

889
00:41:51,140 --> 00:41:52,120
Sois plus spécifique.

890
00:41:52,120 --> 00:41:55,000
Je commence à faire son chemin.

891
00:41:55,000 --> 00:41:59,470
Nous comptons, mais
ce qui est hors d'ici?

892
00:41:59,470 --> 00:42:00,707
>> ÉTUDIANTS: séquence numérique.

893
00:42:00,707 --> 00:42:02,040
DAVID MALAN: séquence numérique.

894
00:42:02,040 --> 00:42:04,248
le genre de tenue de tout le monde
il ici-- de très haut niveau.

895
00:42:04,248 --> 00:42:07,450
Dis-moi juste littéralement ce qui est
tort comme une puissance de cinq ans.

896
00:42:07,450 --> 00:42:08,310
>> ÉTUDIANTS: Plus un.

897
00:42:08,310 --> 00:42:08,750
>> DAVID MALAN: Qu'est-ce que?

898
00:42:08,750 --> 00:42:09,610
>> ÉTUDIANTS: Plus un.

899
00:42:09,610 --> 00:42:11,235
>> DAVID MALAN: Qu'entendez-vous plus un?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Donnez-moi un autre cinq ans.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Qu'est-ce qui ne va pas, maman?

904
00:42:18,330 --> 00:42:19,940
Qu'est-ce qui ne va pas, papa?

905
00:42:19,940 --> 00:42:22,808
Que voulez-vous dire ce ne sont pas triées?

906
00:42:22,808 --> 00:42:24,370
>> ÉTUDIANT: Il est pas le bon endroit.

907
00:42:24,370 --> 00:42:25,580
>> DAVID MALAN: Quelle est
pas à la bonne place?

908
00:42:25,580 --> 00:42:26,174
>> ÉTUDIANTS: Quatre.

909
00:42:26,174 --> 00:42:27,090
DAVID MALAN: OK, bon.

910
00:42:27,090 --> 00:42:29,110
Donc quatre est pas où il devrait être.

911
00:42:29,110 --> 00:42:30,590
En particulier, est-ce exact?

912
00:42:30,590 --> 00:42:33,000
Quatre et le premier
deux chiffres que je vois.

913
00:42:33,000 --> 00:42:34,930
Est-ce correct?

914
00:42:34,930 --> 00:42:36,427
Non, ils sont hors d'usage, non?

915
00:42:36,427 --> 00:42:38,135
En fait, maintenant penser
d'un ordinateur, aussi.

916
00:42:38,135 --> 00:42:40,824
Il ne peut que regarder peut-être un,
peut-être deux choses à once--

917
00:42:40,824 --> 00:42:43,240
et en fait une seule chose
à un moment, mais il peut au moins

918
00:42:43,240 --> 00:42:45,790
regarder une chose alors la
prochaine chose juste à côté.

919
00:42:45,790 --> 00:42:47,380
>> Ainsi sont-elles en ordre?

920
00:42:47,380 --> 00:42:48,032
Bien sûr que non.

921
00:42:48,032 --> 00:42:48,740
Donc, vous savez quoi?

922
00:42:48,740 --> 00:42:51,020
Pourquoi ne prenons pas de bébé
étapes de fixation de ce problème

923
00:42:51,020 --> 00:42:53,410
au lieu de faire ces fantaisie
des algorithmes comme Ben, où

924
00:42:53,410 --> 00:42:56,440
il est en quelque sorte de le fixer par
une boucle à travers la liste

925
00:42:56,440 --> 00:42:59,670
au lieu de faire ce que je faisais, où
Je viens de sorte de le fixe que nous allons?

926
00:42:59,670 --> 00:43:03,650
Disons simplement briser littéralement en bas de la
notion d'ordre numérique order--,

927
00:43:03,650 --> 00:43:06,990
appeler tout ce que vous want--
dans ces comparaisons par paires.

928
00:43:06,990 --> 00:43:07,590
>> Quatre et un.

929
00:43:07,590 --> 00:43:09,970
Est-ce le bon ordre?

930
00:43:09,970 --> 00:43:11,310
Donc, nous allons corriger cela.

931
00:43:11,310 --> 00:43:14,700
Un et quatre, puis
nous allons simplement copier cela.

932
00:43:14,700 --> 00:43:15,560
Bon, bon.

933
00:43:15,560 --> 00:43:17,022
Je fixe un et quatre.

934
00:43:17,022 --> 00:43:18,320
Trois et deux?

935
00:43:18,320 --> 00:43:18,820
Non.

936
00:43:18,820 --> 00:43:21,690
Que mes mots correspondent mes doigts.

937
00:43:21,690 --> 00:43:23,695
Quatre et trois?

938
00:43:23,695 --> 00:43:27,930
>> Il est pas dans l'ordre, alors je vais
de faire un, trois, quatre, deux.

939
00:43:27,930 --> 00:43:28,680
OK, bien.

940
00:43:28,680 --> 00:43:32,310
Maintenant, quatre et deux?

941
00:43:32,310 --> 00:43:33,370
Nous devons résoudre ce problème, aussi.

942
00:43:33,370 --> 00:43:36,700
Donc un, trois, deux, quatre.

943
00:43:36,700 --> 00:43:39,820
Ainsi est-il réglé?

944
00:43:39,820 --> 00:43:43,170
Non, mais est-il plus proche de tri?

945
00:43:43,170 --> 00:43:48,930
>> Il est, parce que nous avons fixé cette
erreur, nous avons corrigé cette erreur,

946
00:43:48,930 --> 00:43:50,370
et nous avons corrigé cette erreur.

947
00:43:50,370 --> 00:43:52,420
Donc, nous avons fixé trois erreurs sans doute.

948
00:43:52,420 --> 00:43:58,100
Encore ne pas vraiment regarder triée, mais
il est objectivement plus proche de tri

949
00:43:58,100 --> 00:44:00,080
parce que nous avons corrigé certaines de ces erreurs.

950
00:44:00,080 --> 00:44:02,047
>> Maintenant, que dois-je faire?

951
00:44:02,047 --> 00:44:03,630
Je genre de arrivé à la fin de la liste.

952
00:44:03,630 --> 00:44:05,680
Il me semblait avoir fixé
toutes les erreurs, mais non.

953
00:44:05,680 --> 00:44:08,510
Parce que dans ce cas, certains numéros
auraient pu barboter jusqu'à rapprocher

954
00:44:08,510 --> 00:44:10,410
d'autres numéros
sont encore hors d'usage.

955
00:44:10,410 --> 00:44:12,951
Donc, nous allons le faire à nouveau, et je vais
il suffit de faire en place cette fois.

956
00:44:12,951 --> 00:44:14,170
Une et trois?

957
00:44:14,170 --> 00:44:14,720
C'est bien.

958
00:44:14,720 --> 00:44:16,070
Trois et deux?

959
00:44:16,070 --> 00:44:17,560
Bien sûr pas, donc nous allons changer cela.

960
00:44:17,560 --> 00:44:19,160
Donc, deux, trois.

961
00:44:19,160 --> 00:44:21,340
Trois et quatre?

962
00:44:21,340 --> 00:44:24,370
Et maintenant, nous allons juste être
particulièrement pédant ici.

963
00:44:24,370 --> 00:44:26,350
Est-il réglé?

964
00:44:26,350 --> 00:44:29,280
Vous savez les humains est triée.

965
00:44:29,280 --> 00:44:30,400
>> Je devrais essayer à nouveau.

966
00:44:30,400 --> 00:44:31,900
Alors Olivia propose je tente à nouveau.

967
00:44:31,900 --> 00:44:32,530
Pourquoi?

968
00:44:32,530 --> 00:44:35,810
Parce qu'un ordinateur ne dispose pas
le luxe de nos yeux humains

969
00:44:35,810 --> 00:44:38,080
de simplement en regardant back-- OK, je suis fait.

970
00:44:38,080 --> 00:44:41,610
Comment l'ordinateur déterminer
que la liste est maintenant triée?

971
00:44:41,610 --> 00:44:44,590
Mécaniquement.

972
00:44:44,590 --> 00:44:47,650
>> Je devrais passer par
Encore une fois, et seulement si je

973
00:44:47,650 --> 00:44:51,190
ne pas faire / trouver toutes les erreurs que je peux
puis conclure que l'ordinateur, yep,

974
00:44:51,190 --> 00:44:51,980
nous sommes bons pour aller.

975
00:44:51,980 --> 00:44:54,850
Donc, un et deux, deux et
trois, trois et quatre.

976
00:44:54,850 --> 00:44:58,030
Maintenant, je peux définitivement dire que c'est
triés, parce que je fait aucun changement.

977
00:44:58,030 --> 00:45:01,940
Maintenant, ce serait un bug et juste
fou si je, l'ordinateur,

978
00:45:01,940 --> 00:45:05,640
demandé à nouveau ces mêmes questions
attend des réponses différentes.

979
00:45:05,640 --> 00:45:07,110
Ne devrait pas se produire.

980
00:45:07,110 --> 00:45:08,600
>> Et maintenant la liste est triée.

981
00:45:08,600 --> 00:45:12,630
Malheureusement, le temps de courir
cet algorithme est également n carré.

982
00:45:12,630 --> 00:45:13,130
Pourquoi?

983
00:45:13,130 --> 00:45:19,520
Parce que vous avez n nombres, et dans la
pire des cas, vous devez déplacer n nombres

984
00:45:19,520 --> 00:45:23,637
n fois parce que vous devez continuer
en arrière pour vérifier et éventuellement corriger

985
00:45:23,637 --> 00:45:24,220
ces chiffres.

986
00:45:24,220 --> 00:45:26,280
Et nous pouvons faire plus
analyse formelle, aussi.

987
00:45:26,280 --> 00:45:29,530
>> Donc, tout cela est de dire que nous avons pris
trois approches différentes, l'une

988
00:45:29,530 --> 00:45:32,210
d'entre eux immédiatement intuitive
le départ de Ben

989
00:45:32,210 --> 00:45:35,170
à mon insertion suggérée
sorte à celui-ci

990
00:45:35,170 --> 00:45:38,540
où vous sorte de perdre de vue
la forêt pour les arbres initialement.

991
00:45:38,540 --> 00:45:41,760
Mais alors, si vous prenez un peu de recul,
voila, nous avons fixé la notion de tri.

992
00:45:41,760 --> 00:45:43,824
Donc, cela est, ose dire,
un niveau inférieur peut-être

993
00:45:43,824 --> 00:45:45,740
que certains de ces autres
algorithmes, mais nous allons

994
00:45:45,740 --> 00:45:48,550
voir si nous ne pouvons pas visualiser
ceux-ci par le biais de cette.

995
00:45:48,550 --> 00:45:51,450
>> Donc, cela est un peu agréable
logiciel que quelqu'un

996
00:45:51,450 --> 00:45:56,110
écrit en utilisant des barres colorées qui est
va faire ce qui suit pour nous.

997
00:45:56,110 --> 00:45:57,736
Chacune de ces barres représente un nombre.

998
00:45:57,736 --> 00:46:00,026
Taller la barre, plus
le nombre, plus la barre,

999
00:46:00,026 --> 00:46:00,990
plus le nombre.

1000
00:46:00,990 --> 00:46:05,880
Donc, idéalement, nous voulons une pyramide belle
où il commence petit et obtient grand,

1001
00:46:05,880 --> 00:46:08,330
et cela signifierait que
ces barres sont triées.

1002
00:46:08,330 --> 00:46:11,200
Je vais donc aller de l'avant et de choisir,
par exemple, l'algorithme de Ben

1003
00:46:11,200 --> 00:46:13,990
first-- sorte de sélection.

1004
00:46:13,990 --> 00:46:16,220
>> Et remarquez ce qu'il fait.

1005
00:46:16,220 --> 00:46:18,670
La façon dont ils ont choisi de
visualiser cet algorithme

1006
00:46:18,670 --> 00:46:22,090
est que, tout comme moi
marchant dans ma liste,

1007
00:46:22,090 --> 00:46:24,710
ce programme marche
à travers sa liste de numéros,

1008
00:46:24,710 --> 00:46:28,160
soulignant en rose chaque
numéro qu'il regarde.

1009
00:46:28,160 --> 00:46:32,360
Et ce qui va se passer maintenant?

1010
00:46:32,360 --> 00:46:35,154
>> Le plus petit nombre qui
I ou Ben soudain trouvé

1011
00:46:35,154 --> 00:46:36,820
est déplacé vers le début de la liste.

1012
00:46:36,820 --> 00:46:40,037
Et ils l'ont fait expulser préavis
le nombre qui était là,

1013
00:46:40,037 --> 00:46:41,120
et c'est parfaitement bien.

1014
00:46:41,120 --> 00:46:42,600
Je ne suis pas entrer dans ce niveau de détail.

1015
00:46:42,600 --> 00:46:44,308
Mais nous avons besoin de mettre
ce nombre quelque part,

1016
00:46:44,308 --> 00:46:47,775
alors nous avons déménagé à la
endroit ouvert qui a été créé.

1017
00:46:47,775 --> 00:46:49,900
Donc, je vais accélérer ce
, parce que sinon il

1018
00:46:49,900 --> 00:46:51,871
devient très fastidieux rapidement.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animations speed-- nous y aller.

1021
00:46:58,600 --> 00:47:01,850
Alors maintenant, même principe
J'a été l'application, mais vous

1022
00:47:01,850 --> 00:47:06,540
peut commencer à se sentir l'algorithme, si vous
sera, ou voir un peu plus clair.

1023
00:47:06,540 --> 00:47:13,190
Et cet algorithme a pour effet de
la sélection du prochain élément le plus petit,

1024
00:47:13,190 --> 00:47:16,422
de sorte que vous allez commencer à
le voir monter en puissance sur la gauche.

1025
00:47:16,422 --> 00:47:19,130
Et à chaque itération, comme je
proposé, il fait un peu moins de travail.

1026
00:47:19,130 --> 00:47:21,921
Il n'a pas besoin d'aller tout le chemin
retour à l'extrémité gauche de la liste,

1027
00:47:21,921 --> 00:47:23,900
parce qu'il a déjà
connaît ceux qui sont triés.

1028
00:47:23,900 --> 00:47:28,129
Donc, ce genre de sent comme il est
accélère, même si chaque étape est

1029
00:47:28,129 --> 00:47:29,420
en prenant la même quantité de temps.

1030
00:47:29,420 --> 00:47:31,600
Il y a seulement moins d'étapes restantes.

1031
00:47:31,600 --> 00:47:35,240
Et maintenant, vous pouvez sorte de sentir la
algorithme de nettoyage à la fin de celui-ci,

1032
00:47:35,240 --> 00:47:37,040
et même maintenant il est trié.

1033
00:47:37,040 --> 00:47:41,620
>> Donc, le tri par insertion est tout fait.

1034
00:47:41,620 --> 00:47:43,600
Je dois re-randomiser le tableau.

1035
00:47:43,600 --> 00:47:45,940
Et remarquez que je peux juste
garder randomisation il,

1036
00:47:45,940 --> 00:47:50,630
et nous obtenons une approximation de
la même approche, le tri par insertion.

1037
00:47:50,630 --> 00:47:55,050
Permettez-moi de ralentir ici.

1038
00:47:55,050 --> 00:47:56,915
Commençons que plus.

1039
00:47:56,915 --> 00:47:57,414
Arrêtez.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Sautons quatre.

1042
00:48:02,410 --> 00:48:03,200
Nous y voilà.

1043
00:48:03,200 --> 00:48:04,190
Randomize ils tableau.

1044
00:48:04,190 --> 00:48:05,555
Et ici, nous go-- tri par insertion.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Jouer.

1047
00:48:12,800 --> 00:48:17,280
Notez qu'il a affaire à chaque
élément qu'il rencontre tout de suite,

1048
00:48:17,280 --> 00:48:20,282
mais si elle appartient à
le lieu préavis mal

1049
00:48:20,282 --> 00:48:21,740
tout le travail qui doit se produire.

1050
00:48:21,740 --> 00:48:24,700
Nous devons continuer à déplacer plus
et plus d'éléments pour faire de la place

1051
00:48:24,700 --> 00:48:27,340
pour celui que nous voulons mettre en place.

1052
00:48:27,340 --> 00:48:30,740
>> Nous sommes donc en se concentrant sur la
extrémité gauche de la liste seulement.

1053
00:48:30,740 --> 00:48:34,460
Notez que nous avons même pas regardé at-- nous
ne sont pas mis en évidence dans quoi que ce soit rose

1054
00:48:34,460 --> 00:48:35,610
à droite.

1055
00:48:35,610 --> 00:48:38,180
Nous sommes en train de traiter avec
les problèmes que nous allons,

1056
00:48:38,180 --> 00:48:40,430
mais nous créons beaucoup de
travailler pour nous-mêmes encore.

1057
00:48:40,430 --> 00:48:44,410
Et donc si nous accélérons cette place
maintenant aller à la fin,

1058
00:48:44,410 --> 00:48:46,210
il a une sensation différente à elle en effet.

1059
00:48:46,210 --> 00:48:50,150
Il est juste en se concentrant sur l'extrémité gauche, mais
faire un peu plus de travail que needed--

1060
00:48:50,150 --> 00:48:53,230
genre de choses de lissage
plus, réparer les choses,

1061
00:48:53,230 --> 00:48:58,350
mais en fin de compte traiter avec
chaque élément un à la fois

1062
00:48:58,350 --> 00:49:07,740
jusqu'à ce que nous arrivons à bien the--, nous
savons tous comment cela va se terminer,

1063
00:49:07,740 --> 00:49:09,700
il est donc un peu décevant peut-être.

1064
00:49:09,700 --> 00:49:12,830
>> Mais la liste dans le end--
spoiler-- va être triée.

1065
00:49:12,830 --> 00:49:15,300
Alors regardons un dernier.

1066
00:49:15,300 --> 00:49:16,840
Nous ne pouvons pas ignorer maintenant.

1067
00:49:16,840 --> 00:49:18,000
Nous y sommes presque.

1068
00:49:18,000 --> 00:49:19,980
Deux aller, un pour aller.

1069
00:49:19,980 --> 00:49:22,680
Et voila.

1070
00:49:22,680 --> 00:49:23,450
Excellent.

1071
00:49:23,450 --> 00:49:27,220
>> Alors maintenant, nous allons faire une dernière,
re-randomisation avec tri à bulles.

1072
00:49:27,220 --> 00:49:31,690
Et remarque ici, surtout si je ralentis il
vers le bas, cela ne tient élancées à travers.

1073
00:49:31,690 --> 00:49:36,830
Mais remarquez il est tout simplement pairwise
Tri comparisons-- de solutions locales.

1074
00:49:36,830 --> 00:49:39,050
Mais dès que nous arrivons à
la fin de la liste en rose,

1075
00:49:39,050 --> 00:49:40,690
ce qui va devoir se reproduire?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Ouais, il va devoir
recommencer, car il ne

1078
00:49:46,830 --> 00:49:49,870
erreurs appariées fixes.

1079
00:49:49,870 --> 00:49:53,120
Et qui aurait pu encore révélé d'autres.

1080
00:49:53,120 --> 00:49:58,950
Et donc si vous accélérez cette place, vous aurez
voir que, tout comme le nom l'indique,

1081
00:49:58,950 --> 00:50:01,870
la plus petite elements-- ou plutôt
les elements-- plus grandes commencent

1082
00:50:01,870 --> 00:50:03,740
bouillonner vers le haut, si vous voulez.

1083
00:50:03,740 --> 00:50:07,380
Et les plus petits éléments sont
commencer à faire des bulles vers le bas à gauche.

1084
00:50:07,380 --> 00:50:10,780
Et en effet, que ce genre de
l'effet visuel ainsi.

1085
00:50:10,780 --> 00:50:17,150
Et cela va finir par finir
d'une manière très similaire aussi.

1086
00:50:17,150 --> 00:50:19,160
>> Nous ne devons pas demeurer
sur celui-ci en particulier.

1087
00:50:19,160 --> 00:50:21,010
Permettez-moi d'ouvrir maintenant, aussi.

1088
00:50:21,010 --> 00:50:24,040
Il y a quelques autres algorithmes de tri
dans le monde, dont quelques-unes

1089
00:50:24,040 --> 00:50:25,580
sont capturés ici.

1090
00:50:25,580 --> 00:50:29,960
Et surtout pour les apprenants qui ne sont pas
forcément visuel ou mathématique,

1091
00:50:29,960 --> 00:50:31,930
comme nous l'avons fait avant, nous pouvons
aussi faire ce déficients auditifs

1092
00:50:31,930 --> 00:50:34,210
si nous associons un son avec cela.

1093
00:50:34,210 --> 00:50:36,990
Et juste pour le plaisir, voici un
quelques algorithmes différents,

1094
00:50:36,990 --> 00:50:40,950
et l'un d'eux en particulier que vous êtes
va à remarquer que l'on appelle «tri par fusion."

1095
00:50:40,950 --> 00:50:43,250
>> Il est en fait un fond
meilleur algorithme,

1096
00:50:43,250 --> 00:50:45,860
de telle sorte que le tri par fusion, l'un des
ceux que vous êtes sur le point de voir,

1097
00:50:45,860 --> 00:50:49,170
est pas l'ordre de n au carré.

1098
00:50:49,170 --> 00:50:57,280
Il est de l'ordre de n fois log de
n, ce qui est en fait plus petite et donc

1099
00:50:57,280 --> 00:50:58,940
plus rapidement que ceux des trois autres.

1100
00:50:58,940 --> 00:51:00,670
Et il y a un autre couple
les stupides que nous allons voir.

1101
00:51:00,670 --> 00:51:01,933
>> Alors on y va avec un certain bruit.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Ceci est le tri par insertion, de sorte à nouveau
il est juste traiter avec les éléments

1104
00:51:10,490 --> 00:51:13,420
comme ils viennent.

1105
00:51:13,420 --> 00:51:17,180
Ceci est tri à bulles, il est donc
les considérant paires à la fois.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
Et encore, les plus grands éléments
sont jaillissant vers le haut.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Ensuite sélection tri.

1110
00:51:41,710 --> 00:51:45,420
Ceci est l'algorithme de Ben, où
de nouveau, il est la sélection itérative

1111
00:51:45,420 --> 00:51:46,843
le prochain plus petit élément.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
Et encore une fois, vous pouvez maintenant vraiment entendre que
il est l'accélération, mais seulement dans la mesure où

1114
00:51:53,900 --> 00:51:58,230
comme il est fait de moins en moins
travailler à chaque itération.

1115
00:51:58,230 --> 00:52:04,170
Ceci est la plus rapide un, le tri par fusion,
qui est le tri des groupes de nombres

1116
00:52:04,170 --> 00:52:05,971
les combiner ensemble et ensuite.

1117
00:52:05,971 --> 00:52:07,720
Si la gauche look--
la moitié est déjà trié.

1118
00:52:07,720 --> 00:52:14,165
>> Maintenant, il est le tri de la moitié droite, et
maintenant il va les combiner en un seul.

1119
00:52:14,165 --> 00:52:19,160
Ceci est quelque chose appelé "Gnome genre."

1120
00:52:19,160 --> 00:52:23,460
Et vous pouvez sorte de voir que
ça va-et-vient,

1121
00:52:23,460 --> 00:52:27,950
fixant le travail un peu ici et
il avant qu'il ne procède à de nouveaux travaux.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
Et c'est tout.

1124
00:52:33,692 --> 00:52:36,400
Il y a une autre sorte, qui est
vraiment juste à des fins académiques,

1125
00:52:36,400 --> 00:52:40,980
appelé «sorte stupide» qui prend
vos données, trie au hasard,

1126
00:52:40,980 --> 00:52:43,350
et vérifie ensuite si elle est triée.

1127
00:52:43,350 --> 00:52:47,880
Et si ce n'est pas, il re-trie
au hasard, vérifie si elle est triée,

1128
00:52:47,880 --> 00:52:49,440
et sinon répète.

1129
00:52:49,440 --> 00:52:52,660
Et en théorie, probabilistically
cela va compléter,

1130
00:52:52,660 --> 00:52:54,140
mais après un peu de temps.

1131
00:52:54,140 --> 00:52:56,930
Il est pas le plus
efficace des algorithmes.

1132
00:52:56,930 --> 00:53:02,550
Donc, des questions sur les
algorithmes ou tout particulier

1133
00:53:02,550 --> 00:53:04,720
il lié aussi?

1134
00:53:04,720 --> 00:53:09,430
>> Eh bien, nous allons maintenant taquiner à part ce que tout
ces lignes sont que je dessine

1135
00:53:09,430 --> 00:53:15,090
et ce que je suis en supposant que l'ordinateur
peut faire sous le capot.

1136
00:53:15,090 --> 00:53:18,650
Je dirais que tous ces chiffres
Je garde drawing-- dont ils ont besoin pour obtenir

1137
00:53:18,650 --> 00:53:21,330
stockés quelque part dans la mémoire.

1138
00:53:21,330 --> 00:53:24,130
Nous allons nous débarrasser de ce gars maintenant, aussi.

1139
00:53:24,130 --> 00:53:30,110
>> Ainsi, une partie de mémoire dans un
computer-- donc RAM DIMM est

1140
00:53:30,110 --> 00:53:35,480
ce que nous avons cherché hier, double
inline memory module-- ressemble à ceci.

1141
00:53:35,480 --> 00:53:39,370
Et chacun de ces petits jetons noirs
est un certain nombre d'octets, typiquement.

1142
00:53:39,370 --> 00:53:44,380
Et puis les broches d'or sont comme le
fils qui se connectent à l'ordinateur,

1143
00:53:44,380 --> 00:53:47,521
et le conseil de silicium vert est juste
ce qui maintient tout tous ensemble.

1144
00:53:47,521 --> 00:53:48,770
Alors qu'est-ce que cela signifie vraiment?

1145
00:53:48,770 --> 00:53:53,180
Si je sorte de tire cette même image,
Supposons pour simplifier

1146
00:53:53,180 --> 00:53:55,280
que ce DIMM, dual
Module de mémoire en ligne,

1147
00:53:55,280 --> 00:54:00,530
est un gigaoctet de RAM, un gigaoctet de
la mémoire, ce qui est le nombre d'octets total?

1148
00:54:00,530 --> 00:54:02,100
Un gigaoctet est combien d'octets?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Plus que ça.

1151
00:54:06,030 --> 00:54:09,960
1124 est le kilo, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega est millions.

1153
00:54:11,730 --> 00:54:14,570
Giga est un milliard.

1154
00:54:14,570 --> 00:54:15,070
>> Suis-je mens?

1155
00:54:15,070 --> 00:54:16,670
Peut-on même lire l'étiquette?

1156
00:54:16,670 --> 00:54:19,920
Ceci est en fait 128
gigaoctets, il est donc plus.

1157
00:54:19,920 --> 00:54:22,130
Mais nous prétendons cette
est juste un gigaoctet.

1158
00:54:22,130 --> 00:54:25,640
Donc, cela signifie qu'il ya un milliard
octets de mémoire disponibles pour me

1159
00:54:25,640 --> 00:54:29,770
ou 8 milliards de bits, mais nous allons
pour parler en termes d'octets maintenant,

1160
00:54:29,770 --> 00:54:30,750
avancer.

1161
00:54:30,750 --> 00:54:36,330
>> Alors qu'est-ce que cela signifie est cela est
un octet, ceci est un autre octet,

1162
00:54:36,330 --> 00:54:38,680
ceci est un autre octet,
et si nous voulions vraiment

1163
00:54:38,680 --> 00:54:43,280
pour être précis, nous aurions à
tirer un milliard de petits carrés.

1164
00:54:43,280 --> 00:54:44,320
Mais qu'est ce que ça veut dire?

1165
00:54:44,320 --> 00:54:46,420
Eh bien, permettez-moi de zoom
sur cette photo.

1166
00:54:46,420 --> 00:54:50,900
Si je dois quelque chose qui ressemble
comme ça maintenant, c'est de quatre octets.

1167
00:54:50,900 --> 00:54:53,710
>> Et pour que je puisse mettre quatre chiffres ici.

1168
00:54:53,710 --> 00:54:54,990
Un deux trois quatre.

1169
00:54:54,990 --> 00:55:00,170
Ou je pourrais mettre quatre lettres ou des symboles.

1170
00:55:00,170 --> 00:55:02,620
"Hey!" pourrait aller là,
parce que chacune des lettres,

1171
00:55:02,620 --> 00:55:04,370
nous avons discuté plus tôt,
pourraient être représentés

1172
00:55:04,370 --> 00:55:06,650
avec huit bits ou ASCII ou un octet.

1173
00:55:06,650 --> 00:55:09,370
Donc, en d'autres termes, vous pouvez
mettre 8 milliards choses à l'intérieur

1174
00:55:09,370 --> 00:55:11,137
de celui-ci bâton de mémoire.

1175
00:55:11,137 --> 00:55:14,345
Maintenant, qu'est-ce que cela signifie pour remettre les choses
à dos à dos dans la mémoire comme ça?

1176
00:55:14,345 --> 00:55:17,330
Ceci est ce qu'un programmeur
appellerait un «tableau».

1177
00:55:17,330 --> 00:55:21,250
Dans un programme d'ordinateur, vous ne pensez pas
le matériel utilisé, en tant que tel.

1178
00:55:21,250 --> 00:55:24,427
Vous pensez juste de vous-même comme ayant
l'accès à un total milliard d'octets,

1179
00:55:24,427 --> 00:55:26,010
et vous pouvez tout ce que vous voulez avec elle.

1180
00:55:26,010 --> 00:55:27,880
Mais pour plus de commodité
il est généralement utile

1181
00:55:27,880 --> 00:55:31,202
pour garder votre droit de mémoire
à côté de l'autre comme ça.

1182
00:55:31,202 --> 00:55:33,660
Donc, si je zoome sur this--
parce que nous allons certainement pas

1183
00:55:33,660 --> 00:55:39,310
de tirer un milliard de petits squares--
supposons que ce conseil représente

1184
00:55:39,310 --> 00:55:40,610
ce bâton de mémoire maintenant.

1185
00:55:40,610 --> 00:55:43,800
Et je vais dessiner autant que mon
marqueur finit par me donner ici.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Nous avons donc maintenant un bâton
de mémoire sur la carte

1188
00:55:52,300 --> 00:55:56,400
qui a obtenu un, deux, trois, quatre, cinq,
six, un, deux, trois, quatre, cinq, six,

1189
00:55:56,400 --> 00:56:01,130
seven-- donc 42 octets de
mémoire sur le total de l'écran.

1190
00:56:01,130 --> 00:56:01,630
Je vous remercie.

1191
00:56:01,630 --> 00:56:02,838
Oui, a fait mon arithmétique droite.

1192
00:56:02,838 --> 00:56:05,120
Donc, 42 octets de mémoire ici.

1193
00:56:05,120 --> 00:56:06,660
Alors qu'est-ce que cela signifie réellement?

1194
00:56:06,660 --> 00:56:09,830
Eh bien, un programmeur informatique
serait en fait généralement

1195
00:56:09,830 --> 00:56:12,450
penser de cette mémoire adressable.

1196
00:56:12,450 --> 00:56:16,630
En d'autres termes, chacun de ceux-ci
emplacements en mémoire, dans le matériel,

1197
00:56:16,630 --> 00:56:18,030
a une adresse unique.

1198
00:56:18,030 --> 00:56:22,020
>> Il est pas aussi complexe que One Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Au lieu de cela, il est juste un nombre.

1200
00:56:23,830 --> 00:56:27,930
Ceci est l'octet numéro zéro, cela est
l'un, cela est deux, cela est trois,

1201
00:56:27,930 --> 00:56:30,327
et cela est 41.

1202
00:56:30,327 --> 00:56:30,910
Attends une minute.

1203
00:56:30,910 --> 00:56:32,510
Je pensais que je l'ai dit 42 il y a un instant.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Je commencé à compter à zéro,
de telle sorte que est en fait correcte.

1206
00:56:37,772 --> 00:56:40,980
Maintenant, nous ne devons pas réellement dessiner
comme une grille, et si vous dessinez comme une grille

1207
00:56:40,980 --> 00:56:43,520
Je pense que les choses effectivement
obtenir un peu trompeur.

1208
00:56:43,520 --> 00:56:46,650
Quel programmeur,
dans son propre esprit,

1209
00:56:46,650 --> 00:56:50,310
pense généralement de cette
mémoire est comme une bande,

1210
00:56:50,310 --> 00:56:53,340
comme un morceau de ruban adhésif de masquage
qui va juste encore et toujours

1211
00:56:53,340 --> 00:56:54,980
ou jusqu'à ce que vous manquez de mémoire.

1212
00:56:54,980 --> 00:56:59,200
Donc, d'une manière plus commune pour dessiner
et il suffit de penser la mémoire

1213
00:56:59,200 --> 00:57:03,710
serait que ce soit l'octet zéro, un,
deux, trois, puis dot, dot, dot.

1214
00:57:03,710 --> 00:57:07,650
Et vous avez 42 ces octets au total, même
bien physiquement, il pourrait effectivement

1215
00:57:07,650 --> 00:57:09,480
être quelque chose de plus comme ça.

1216
00:57:09,480 --> 00:57:12,850
>> Donc, si vous pensez maintenant de votre
mémoire comme cela, tout comme une bande,

1217
00:57:12,850 --> 00:57:17,640
c'est ce qu'un programmeur à nouveau
appellerait un tableau de mémoire.

1218
00:57:17,640 --> 00:57:20,660
Et quand vous voulez stocker effectivement
quelque chose dans la mémoire d'un ordinateur,

1219
00:57:20,660 --> 00:57:23,290
vous faites généralement les choses en magasin
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Donc, nous avons parlé de chiffres.

1221
00:57:25,010 --> 00:57:30,880
Et quand je voulais résoudre les problèmes
comme quatre, un, trois, deux,

1222
00:57:30,880 --> 00:57:33,820
même si je viens de dessiner
seul le nombre de quatre, un, trois,

1223
00:57:33,820 --> 00:57:39,490
deux sur le bord, l'ordinateur serait
vraiment avoir cette configuration en mémoire.

1224
00:57:39,490 --> 00:57:43,347
>> Et ce serait à côté de la
deux dans la mémoire de l'ordinateur?

1225
00:57:43,347 --> 00:57:44,680
Eh bien, il n'y a pas de réponse à cela.

1226
00:57:44,680 --> 00:57:45,770
Nous ne savons pas vraiment.

1227
00:57:45,770 --> 00:57:48,200
Et tant que le
ordinateur n'a pas besoin,

1228
00:57:48,200 --> 00:57:51,440
il n'a pas à prendre soin de ce qui est à côté
les chiffres, il se soucie.

1229
00:57:51,440 --> 00:57:55,130
Et quand je l'ai dit plus tôt qu'un ordinateur
peut seulement regarder une adresse à la fois,

1230
00:57:55,130 --> 00:57:56,170
c'est un peu pourquoi.

1231
00:57:56,170 --> 00:57:59,490
>> Pas contrairement à un record
joueur et une tête de lecture

1232
00:57:59,490 --> 00:58:03,030
seulement être capable de regarder à un certain
rainure dans un enregistrement physique de la vieille école

1233
00:58:03,030 --> 00:58:06,500
à la fois, de la même
peut un ordinateur grâce

1234
00:58:06,500 --> 00:58:09,810
à son processeur et sa
Intel jeu d'instructions,

1235
00:58:09,810 --> 00:58:12,480
parmi dont l'instruction
est lue dans la mémoire

1236
00:58:12,480 --> 00:58:15,590
ou enregistrer memory-- un
ordinateur ne peut que regarder

1237
00:58:15,590 --> 00:58:19,210
à un endroit à un time--
parfois une combinaison d'entre eux,

1238
00:58:19,210 --> 00:58:21,770
mais vraiment juste un endroit à la fois.

1239
00:58:21,770 --> 00:58:24,770
Alors, quand nous faisions
ces différents algorithmes,

1240
00:58:24,770 --> 00:58:28,110
Je ne suis pas en train d'écrire dans un
vacuum-- quatre, un, trois, deux.

1241
00:58:28,110 --> 00:58:30,849
Ces chiffres appartiennent effectivement
quelque part physique en mémoire.

1242
00:58:30,849 --> 00:58:32,890
Donc, il y a tout petit
transistors ou une sorte

1243
00:58:32,890 --> 00:58:35,840
de l'électronique sous le
hotte stocker ces valeurs.

1244
00:58:35,840 --> 00:58:40,460
>> Et au total, combien de bits sont
impliqué dès maintenant, juste pour être clair?

1245
00:58:40,460 --> 00:58:45,580
Voilà donc quatre octets, ou
il est maintenant de 32 bits au total.

1246
00:58:45,580 --> 00:58:49,280
Donc, il y a effectivement 32 zéros et
ceux qui composent ces quatre choses.

1247
00:58:49,280 --> 00:58:52,070
Il y a encore plus ici, mais
encore une fois nous ne nous soucions pas.

1248
00:58:52,070 --> 00:58:55,120
>> Alors maintenant, nous allons demander une autre
question en utilisant la mémoire,

1249
00:58:55,120 --> 00:58:57,519
parce que, à la fin
de la journée est la variance.

1250
00:58:57,519 --> 00:59:00,310
Peu importe ce que nous pourrions faire avec
l'ordinateur, à la fin de la journée

1251
00:59:00,310 --> 00:59:02,560
le matériel est toujours le
Même sous la hotte.

1252
00:59:02,560 --> 00:59:04,670
Comment pourrais-je stocker un mot ici?

1253
00:59:04,670 --> 00:59:09,710
Eh bien, un mot dans un ordinateur comme
"Hey!" seraient stockés comme ça.

1254
00:59:09,710 --> 00:59:12,300
Et si vous vouliez une plus
mot, vous pouvez simplement

1255
00:59:12,300 --> 00:59:19,120
écraser et dire quelque chose
comme "bonjour" et un magasin ici.

1256
00:59:19,120 --> 00:59:23,930
>> Et ici aussi, cette contiguïté
est en fait un avantage,

1257
00:59:23,930 --> 00:59:26,530
parce qu'un ordinateur peut simplement
lire de droite à gauche.

1258
00:59:26,530 --> 00:59:28,680
Mais voici une question.

1259
00:59:28,680 --> 00:59:33,480
Dans le cadre de ce mot,
h-e-l-l-o, point d'exclamation,

1260
00:59:33,480 --> 00:59:38,740
comment l'ordinateur peut savoir où le
mot commence et où le mot se termine?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
Dans le contexte de nombres,
comment fonctionne l'ordinateur

1263
00:59:43,800 --> 00:59:48,396
savoir combien de temps la séquence de
numéros est ou où il commence?

1264
00:59:48,396 --> 00:59:50,270
Eh bien, il se out--
et nous ne rentrerons pas trop

1265
00:59:50,270 --> 00:59:54,970
dans ce niveau de detail--
ordinateurs déplacent choses autour de la mémoire

1266
00:59:54,970 --> 00:59:57,800
littéralement par le biais de ces adresses.

1267
00:59:57,800 --> 01:00:02,080
Donc, dans un ordinateur, si vous êtes
écriture de code pour stocker les choses

1268
01:00:02,080 --> 01:00:05,800
comme des mots, ce que vous êtes
vraiment faire est de taper

1269
01:00:05,800 --> 01:00:11,320
expressions qui rappellent où, en
la mémoire de l'ordinateur sont ces mots.

1270
01:00:11,320 --> 01:00:14,370
Alors laissez-moi faire une très,
exemple très simple.

1271
01:00:14,370 --> 01:00:18,260
>> Je vais aller de l'avant et
ouvrir un programme de texte simple,

1272
01:00:18,260 --> 01:00:20,330
et je vais créer
un fichier appelé hello.c.

1273
01:00:20,330 --> 01:00:22,849
La plupart de ces informations, nous
ne va pas dans en détail,

1274
01:00:22,849 --> 01:00:25,140
mais je vais écrire un
programme dans cette même langue,

1275
01:00:25,140 --> 01:00:31,140
C. Ceci est beaucoup plus intimidant,
Je dirais, que Scratch,

1276
01:00:31,140 --> 01:00:32,490
mais il est très similaire dans l'esprit.

1277
01:00:32,490 --> 01:00:34,364
En fait, ces bouclés
braces-- vous pouvez sorte de

1278
01:00:34,364 --> 01:00:37,820
penser à ce que je viens de le faire comme cela.

1279
01:00:37,820 --> 01:00:39,240
>> Faisons cela, en fait.

1280
01:00:39,240 --> 01:00:45,100
Lorsque le drapeau vert cliqué,
procédez comme suit.

1281
01:00:45,100 --> 01:00:50,210
Je veux imprimer «bonjour».

1282
01:00:50,210 --> 01:00:51,500
Donc, cela est maintenant pseudocode.

1283
01:00:51,500 --> 01:00:53,000
Je suis une sorte de brouiller les lignes.

1284
01:00:53,000 --> 01:00:56,750
En C, cette langue je parle
à propos, cette ligne d'impression bonjour

1285
01:00:56,750 --> 01:01:01,940
devient réalité "printf" avec
des parenthèses et un point-virgule.

1286
01:01:01,940 --> 01:01:03,480
>> Mais il est la même idée exacte.

1287
01:01:03,480 --> 01:01:06,730
Et ce très convivial
"Lorsque le drapeau vert cliqué" devient

1288
01:01:06,730 --> 01:01:10,182
le plus mystérieux "void main int."

1289
01:01:10,182 --> 01:01:12,890
Et cela n'a vraiment aucune cartographie,
donc je vais juste l'ignorer.

1290
01:01:12,890 --> 01:01:17,210
Mais les accolades sont comme le
pièces de puzzle courbes comme celle-ci.

1291
01:01:17,210 --> 01:01:18,700
>> Ainsi, vous pouvez sorte de deviner.

1292
01:01:18,700 --> 01:01:22,357
Même si vous ne l'avez jamais programmé avant,
qu'est-ce que ce programme probablement faire?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
imprime Probablement bonjour
avec un point d'exclamation.

1295
01:01:28,000 --> 01:01:29,150
>> Essayons donc cela.

1296
01:01:29,150 --> 01:01:30,800
Je vais l'enregistrer.

1297
01:01:30,800 --> 01:01:34,000
Et cela est, encore une fois, une très
environnement old school.

1298
01:01:34,000 --> 01:01:35,420
Je ne peux pas cliquer, je ne peux pas glisser.

1299
01:01:35,420 --> 01:01:36,910
Je dois taper des commandes.

1300
01:01:36,910 --> 01:01:41,320
Donc, je veux courir mon programme, de sorte
Je pourrais le faire, comme hello.c.

1301
01:01:41,320 --> 01:01:42,292
C'est le fichier que je courais.

1302
01:01:42,292 --> 01:01:43,500
Mais attendez, je manque une étape.

1303
01:01:43,500 --> 01:01:46,470
Qu'est-ce que nous disons est une condition nécessaire
étape pour un langage comme C?

1304
01:01:46,470 --> 01:01:49,470
Je viens de source écrite
code, mais que dois-je?

1305
01:01:49,470 --> 01:01:50,670
Ouais, je besoin d'un compilateur.

1306
01:01:50,670 --> 01:01:57,670
Donc, sur mon Mac ici, j'ai un
programme appelé GCC, compilateur GNU C,

1307
01:01:57,670 --> 01:02:03,990
ce qui me permet de faire this-- tour
mon code source en, nous allons l'appeler,

1308
01:02:03,990 --> 01:02:04,930
langage machine.

1309
01:02:04,930 --> 01:02:10,180
>> Et je peux voir que,
encore une fois, comme suit, ceux-ci

1310
01:02:10,180 --> 01:02:14,090
sont les zéros et ceux que je viens
créé à partir de mon code source,

1311
01:02:14,090 --> 01:02:15,730
tous les zéros et des uns.

1312
01:02:15,730 --> 01:02:17,770
Et si je veux courir
mon program-- il arrive

1313
01:02:17,770 --> 01:02:23,010
d'être appelé a.out pour
reasons-- historique "bonjour."

1314
01:02:23,010 --> 01:02:24,070
Je peux courir à nouveau.

1315
01:02:24,070 --> 01:02:25,690
Bonjour bonjour bonjour.

1316
01:02:25,690 --> 01:02:27,430
Et il semble fonctionner.

1317
01:02:27,430 --> 01:02:31,000
>> Mais cela signifie que quelque part dans mon
la mémoire de l'ordinateur sont les mots

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, point d'exclamation.

1319
01:02:35,279 --> 01:02:38,070
Et il se trouve, tout comme un côté,
ce qu'un ordinateur serait généralement

1320
01:02:38,070 --> 01:02:40,550
faire ce qu'il sait où
les choses commencent et end-- il est

1321
01:02:40,550 --> 01:02:42,460
va mettre un symbole spécial ici.

1322
01:02:42,460 --> 01:02:46,064
Et la convention est de mettre la
Numéro de zéro à la fin d'un mot

1323
01:02:46,064 --> 01:02:48,230
de sorte que vous savez où il
se termine en fait, de sorte que vous

1324
01:02:48,230 --> 01:02:52,750
ne gardez pas l'impression de plus en plus
caractères que vous avez l'intention réellement.

1325
01:02:52,750 --> 01:02:55,400
>> Mais les plats à emporter ici, même
bien que ce soit assez obscur,

1326
01:02:55,400 --> 01:02:58,140
est qu'il est en fin de compte
relativement simple.

1327
01:02:58,140 --> 01:03:04,550
On vous a donné une sorte de bande, une ébauche
l'espace sur lequel vous pouvez écrire des lettres.

1328
01:03:04,550 --> 01:03:07,150
Vous devez simplement avoir un
symbole spécial, comme arbitraire

1329
01:03:07,150 --> 01:03:10,316
le nombre zéro, de mettre à la fin de
vos mots afin que l'ordinateur sait,

1330
01:03:10,316 --> 01:03:13,410
oh, je devrais arrêter l'impression après
Je vois le point d'exclamation.

1331
01:03:13,410 --> 01:03:16,090
Parce que la chose suivante, il y
est une valeur ASCII de zéro,

1332
01:03:16,090 --> 01:03:19,125
ou le caractère nul comme
quelqu'un l'appeler.

1333
01:03:19,125 --> 01:03:21,500
Mais il y a une sorte de problème
ici, et nous allons revenir

1334
01:03:21,500 --> 01:03:23,320
à des numéros pour un moment.

1335
01:03:23,320 --> 01:03:28,720
Supposons que je fais, en fait,
avoir un tableau de nombres,

1336
01:03:28,720 --> 01:03:30,730
et supposons que le
programme que je vous écris est

1337
01:03:30,730 --> 01:03:34,680
comme un carnet de notes pour un enseignant
et une salle de classe des enseignants.

1338
01:03:34,680 --> 01:03:38,720
Et ce programme lui permet
taper les scores de leurs élèves

1339
01:03:38,720 --> 01:03:39,960
sur des questionnaires.

1340
01:03:39,960 --> 01:03:43,750
Et supposons que l'étudiant obtient
100 sur leur premier jeu-questionnaire, peut-être

1341
01:03:43,750 --> 01:03:49,920
comme un 80 sur le prochain, puis un
75, puis un 90 sur le quatrième quiz.

1342
01:03:49,920 --> 01:03:54,150
>> Donc, à ce moment de l'histoire,
le tableau est de taille quatre.

1343
01:03:54,150 --> 01:03:58,470
Il n'y a absolument plus de mémoire dans le
ordinateur, mais le tableau, pour ainsi dire,

1344
01:03:58,470 --> 01:04:00,350
est de taille quatre.

1345
01:04:00,350 --> 01:04:06,060
Supposons maintenant que l'enseignant veut
d'attribuer un cinquième jeu-questionnaire à la classe.

1346
01:04:06,060 --> 01:04:08,510
Eh bien, l'une des choses qu'il
ou elle va avoir à faire

1347
01:04:08,510 --> 01:04:10,650
est maintenant stocker une valeur supplémentaire ici.

1348
01:04:10,650 --> 01:04:15,490
Mais si le tableau l'enseignant
créé dans ce programme est de taille pour,

1349
01:04:15,490 --> 01:04:22,440
l'un des problèmes avec un tableau est que
vous ne pouvez pas continuer à ajouter à la mémoire.

1350
01:04:22,440 --> 01:04:26,470
Parce que si une autre partie de la
programme a le mot "hey" juste là?

1351
01:04:26,470 --> 01:04:29,650
>> En d'autres termes, la mémoire peut être ma
utilisé pour quoi que ce soit dans un programme.

1352
01:04:29,650 --> 01:04:33,250
Et si à l'avance que je tapé, hey,
Je veux entrée quatre scores de quiz,

1353
01:04:33,250 --> 01:04:34,784
ils pourraient aller ici et ici.

1354
01:04:34,784 --> 01:04:37,700
Et si vous changez soudainement votre esprit
plus tard et dire que je veux un cinquième jeu-questionnaire

1355
01:04:37,700 --> 01:04:40,872
score, vous ne pouvez pas simplement
mettre où vous voulez,

1356
01:04:40,872 --> 01:04:42,580
parce que si cela
La mémoire est utilisée

1357
01:04:42,580 --> 01:04:45,990
pour quelque chose else-- un autre programme
ou une autre caractéristique du programme

1358
01:04:45,990 --> 01:04:46,910
que vous êtes en cours d'exécution?

1359
01:04:46,910 --> 01:04:50,650
Donc, vous devez penser à l'avance
comment vous souhaitez stocker vos données,

1360
01:04:50,650 --> 01:04:54,480
parce que maintenant vous avez peint
vous dans un coin numérique.

1361
01:04:54,480 --> 01:04:57,280
>> Ainsi, un enseignant pourrait à la place
dire lors de l'écriture d'un programme

1362
01:04:57,280 --> 01:04:59,360
pour stocker son
grades, vous savez quoi?

1363
01:04:59,360 --> 01:05:04,180
Je vais demander,
lors de l'écriture de mon programme,

1364
01:05:04,180 --> 01:05:12,070
que je veux zéro, un, deux, trois,
quatre, cinq, six, huit classes au total.

1365
01:05:12,070 --> 01:05:15,320
Donc, une, deux, trois, quatre,
cinq, six, sept, huit.

1366
01:05:15,320 --> 01:05:18,612
L'enseignant peut simplement trop affecter
la mémoire lors de l'écriture de son programme

1367
01:05:18,612 --> 01:05:19,570
et dire, vous savez quoi?

1368
01:05:19,570 --> 01:05:22,236
Je ne vais jamais affecter plus
de huit questionnaires en un semestre.

1369
01:05:22,236 --> 01:05:23,130
C'est tout simplement fou.

1370
01:05:23,130 --> 01:05:24,470
Je ne serai jamais allouer cela.

1371
01:05:24,470 --> 01:05:28,270
Alors que cette façon dont il ou elle a le
flexibilité aux scores magasin d'étudiants,

1372
01:05:28,270 --> 01:05:33,010
comme 75, 90, et peut-être un supplémentaire où
l'étudiant a obtenu un crédit supplémentaire, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Mais si l'enseignant ne
utilise ces trois espaces,

1374
01:05:36,130 --> 01:05:38,860
il y a une livraison intuitive ici.

1375
01:05:38,860 --> 01:05:41,410
Il ou elle est juste de gaspiller l'espace.

1376
01:05:41,410 --> 01:05:44,790
Donc, en d'autres termes, il y a cette
compromis commun dans la programmation

1377
01:05:44,790 --> 01:05:48,241
où vous pouvez allouer
exactement autant de mémoire que vous voulez,

1378
01:05:48,241 --> 01:05:51,490
la hausse qui est que vous êtes super
efficient-- vous n'êtes pas gaspiller

1379
01:05:51,490 --> 01:05:54,640
à tous-- mais l'inconvénient qui
est ce que si vous changez votre esprit lorsque

1380
01:05:54,640 --> 01:05:58,780
en utilisant le programme que vous souhaitez stocker
plus de données que vous avez initialement prévu.

1381
01:05:58,780 --> 01:06:03,030
>> Alors peut-être la solution, puis,
écrire vos programmes de manière

1382
01:06:03,030 --> 01:06:05,605
qu'ils utilisent plus de mémoire
que ce qu'ils ont réellement besoin.

1383
01:06:05,605 --> 01:06:07,730
De cette façon, tu ne vas pas
à courir dans ce problème,

1384
01:06:07,730 --> 01:06:09,730
mais vous êtes gaspiller.

1385
01:06:09,730 --> 01:06:12,960
Et plus la mémoire de votre programme utilise,
comme nous avons discuté hier, moins

1386
01:06:12,960 --> 01:06:15,410
la mémoire qui est disponible
pour d'autres programmes,

1387
01:06:15,410 --> 01:06:18,790
le plus tôt votre ordinateur peut ralentir
à cause de la mémoire virtuelle.

1388
01:06:18,790 --> 01:06:22,670
Et donc la solution idéale pourrait être quoi?

1389
01:06:22,670 --> 01:06:24,610
>> Sous-allocation semble mauvais.

1390
01:06:24,610 --> 01:06:27,030
Over-allocation semble mauvais.

1391
01:06:27,030 --> 01:06:31,120
Alors, que peut-être une meilleure solution?

1392
01:06:31,120 --> 01:06:32,390
Réaffectation.

1393
01:06:32,390 --> 01:06:33,590
Soyez plus dynamique.

1394
01:06:33,590 --> 01:06:37,520
Ne vous forcez pas à choisir un
priori, au début, ce que vous voulez.

1395
01:06:37,520 --> 01:06:41,370
Et certainement ne pas trop affecter,
de peur que vous être un gaspillage.

1396
01:06:41,370 --> 01:06:45,770
>> Et pour atteindre cet objectif, nous
besoin de jeter cette structure de données,

1397
01:06:45,770 --> 01:06:48,100
pour ainsi dire, loin.

1398
01:06:48,100 --> 01:06:51,080
Et qu'est-ce qu'un programmeur
utilisera habituellement

1399
01:06:51,080 --> 01:06:55,940
est ce qu'on appelle pas un
tableau, mais une liste liée.

1400
01:06:55,940 --> 01:07:00,860
En d'autres termes, il ou elle sera
commencer à penser à leur mémoire

1401
01:07:00,860 --> 01:07:05,280
comme étant une sorte de forme qu'ils
peut tirer de la manière suivante.

1402
01:07:05,280 --> 01:07:08,520
Si je veux mémoriser un numéro dans
un program-- il est donc Septembre,

1403
01:07:08,520 --> 01:07:12,600
J'ai donné à mes élèves un questionnaire; je veux
pour stocker premier quiz les étudiants,

1404
01:07:12,600 --> 01:07:16,220
et ils ont obtenu 100 sur it-- I
je vais demander à mon ordinateur,

1405
01:07:16,220 --> 01:07:19,540
par le biais du programme que j'ai
écrite, pour une partie de la mémoire.

1406
01:07:19,540 --> 01:07:22,570
Et je vais stocker le
numéro 100 en elle, et voilà.

1407
01:07:22,570 --> 01:07:24,820
>> Puis, quelques semaines plus tard
quand je reçois mon deuxième jeu-questionnaire,

1408
01:07:24,820 --> 01:07:27,890
et il est temps de taper
en ce que 90%, je vais

1409
01:07:27,890 --> 01:07:32,129
de demander à l'ordinateur, hé, ordinateur,
puis-je avoir un autre morceau de la mémoire?

1410
01:07:32,129 --> 01:07:34,170
Ça va me donner cette
morceau vide de la mémoire.

1411
01:07:34,170 --> 01:07:39,370
Je vais mettre dans le numéro 90,
mais dans mon programme d'une façon ou other--

1412
01:07:39,370 --> 01:07:42,100
et nous n'inquiéter
la syntaxe pour this-- je besoin

1413
01:07:42,100 --> 01:07:44,430
en quelque sorte enchaîner ces choses ensemble.

1414
01:07:44,430 --> 01:07:47,430
Et je vais les enchaîner avec
ce qui ressemble à une flèche ici.

1415
01:07:47,430 --> 01:07:50,050
>> Le troisième questionnaire qui se lève,
Je vais dire, hé, ordinateur,

1416
01:07:50,050 --> 01:07:51,680
me donner une autre partie de la mémoire.

1417
01:07:51,680 --> 01:07:54,660
Et je vais mettre bas
quoi qu'il en soit, comme 75,

1418
01:07:54,660 --> 01:07:56,920
et je dois chaîne cette
ensemble maintenant en quelque sorte.

1419
01:07:56,920 --> 01:08:00,290
Quatrième questionnaire vient le long, et peut-être
qui est à la fin du semestre.

1420
01:08:00,290 --> 01:08:03,140
Et en ce moment-là mon programme
pourrait être en utilisant la mémoire

1421
01:08:03,140 --> 01:08:05,540
partout, sur tout physiquement.

1422
01:08:05,540 --> 01:08:08,170
Et juste pour le plaisir, je suis
va tirer cette suite

1423
01:08:08,170 --> 01:08:11,260
quiz-- j'oublie ce qu'il était; je
pensez peut-être un 80 ou quelque chose--

1424
01:08:11,260 --> 01:08:12,500
venant ici.

1425
01:08:12,500 --> 01:08:15,920
>> Mais ça va, parce que picturalement
Je vais dessiner cette ligne.

1426
01:08:15,920 --> 01:08:19,063
En d'autres termes, dans la réalité,
dans le matériel de votre ordinateur,

1427
01:08:19,063 --> 01:08:20,979
le premier score pourrait
finir ici parce qu'il est

1428
01:08:20,979 --> 01:08:22,529
dès le début du semestre.

1429
01:08:22,529 --> 01:08:25,810
Le prochain pourrait finir ici
parce qu'un peu de temps a passé

1430
01:08:25,810 --> 01:08:27,210
et le programme continue à fonctionner.

1431
01:08:27,210 --> 01:08:30,060
La prochaine partition, qui était
75, peut-être ici.

1432
01:08:30,060 --> 01:08:33,420
Et le dernier résultat pourrait être
80, qui est ici.

1433
01:08:33,420 --> 01:08:38,729
>> Donc, en réalité, physiquement, cela pourrait être
ce que la mémoire de votre ordinateur ressemble.

1434
01:08:38,729 --> 01:08:41,569
Mais ce n'est pas un mental utile
paradigme pour un programmeur informatique.

1435
01:08:41,569 --> 01:08:44,649
Pourquoi devriez-vous prendre soin où le
heck vos données est de se retrouver?

1436
01:08:44,649 --> 01:08:46,200
Vous voulez juste pour stocker des données.

1437
01:08:46,200 --> 01:08:49,390
>> Ceci est un peu comme notre discussion
antérieure du dessin du cube.

1438
01:08:49,390 --> 01:08:52,200
Pourquoi tenez-vous ce
l'angle est du cube

1439
01:08:52,200 --> 01:08:53,740
et comment vous devez tourner à dessiner?

1440
01:08:53,740 --> 01:08:54,950
Vous voulez juste un cube.

1441
01:08:54,950 --> 01:08:57,359
De même ici, vous
je veux juste carnet de notes.

1442
01:08:57,359 --> 01:08:59,559
Vous voulez juste de penser à
ceci comme une liste de numéros.

1443
01:08:59,559 --> 01:09:01,350
Qui se soucie de la façon dont il est
mis en œuvre en matériel?

1444
01:09:01,350 --> 01:09:05,180
>> Donc, l'abstraction maintenant
est cette image ici.

1445
01:09:05,180 --> 01:09:07,580
Ceci est une liste liée, comme
un programmeur appellerait,

1446
01:09:07,580 --> 01:09:10,640
dans la mesure où vous avez un
liste, de toute évidence des nombres.

1447
01:09:10,640 --> 01:09:14,990
Mais il est lié picturalement
par l'intermédiaire de ces flèches,

1448
01:09:14,990 --> 01:09:18,510
et toutes ces flèches soient: sous
le capot, si vous êtes curieux,

1449
01:09:18,510 --> 01:09:23,210
rappeler que notre matériel physique a
adresses zéro, un, deux, trois, quatre.

1450
01:09:23,210 --> 01:09:28,465
Toutes ces flèches sont comme une carte est
ou directions, où si 90 est-- maintenant

1451
01:09:28,465 --> 01:09:29,090
Je dois compter.

1452
01:09:29,090 --> 01:09:31,750
>> Zéro, un, deux, trois,
quatre, cinq, six, sept.

1453
01:09:31,750 --> 01:09:35,640
Il semble que le 90 est à
adresse mémoire numéro sept.

1454
01:09:35,640 --> 01:09:38,460
Toutes ces flèches sont est
comme un petit morceau de papier

1455
01:09:38,460 --> 01:09:42,439
que cela donne des directives à la
programme qui dit suivre cette carte

1456
01:09:42,439 --> 01:09:43,880
pour se rendre à l'emplacement sept.

1457
01:09:43,880 --> 01:09:46,680
Et là, vous trouverez la
deuxième score du quiz de l'étudiant.

1458
01:09:46,680 --> 01:09:52,100
Pendant ce temps, le 75-- si je continue ce,
c'est de sept, huit, neuf, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Cette autre flèche représente juste
une carte à l'emplacement de mémoire 15.

1461
01:09:59,080 --> 01:10:02,550
Mais encore une fois, le programmeur le fait généralement
ne se soucient pas ce niveau de détail.

1462
01:10:02,550 --> 01:10:05,530
Et dans la plupart de chaque programmation
langue aujourd'hui, le programmeur

1463
01:10:05,530 --> 01:10:10,490
ne savent même pas où en mémoire
ces chiffres sont en réalité.

1464
01:10:10,490 --> 01:10:14,830
Tout ce qu'il ou elle doit prendre en compte est
qu'ils sont en quelque sorte liés ensemble

1465
01:10:14,830 --> 01:10:18,390
dans une structure de données comme celui-ci.

1466
01:10:18,390 --> 01:10:21,580
>> Mais il se trouve pas
pour obtenir trop technique.

1467
01:10:21,580 --> 01:10:27,430
Mais juste parce que nous pouvons peut-être
permettre d'avoir cette discussion ici,

1468
01:10:27,430 --> 01:10:33,630
supposons que nous revisitons
cette question ici d'une matrice.

1469
01:10:33,630 --> 01:10:35,780
Voyons voir si nous regrettons de venir ici.

1470
01:10:35,780 --> 01:10:42,950
Ceci est de 100, 90, 75 et 80.

1471
01:10:42,950 --> 01:10:44,980
>> Permettez-moi brièvement faire cette affirmation.

1472
01:10:44,980 --> 01:10:48,980
Ceci est un tableau, et encore une fois, la
caractéristique saillante d'un tableau

1473
01:10:48,980 --> 01:10:52,400
est que toutes vos données est de retour à
dos à dos dans memory-- littéralement

1474
01:10:52,400 --> 01:10:56,830
un octet ou peut-être quatre octets,
un nombre fixe d'octets loin.

1475
01:10:56,830 --> 01:11:00,710
Dans une liste liée, que nous pourrions tirer
comme celui-ci, sous le capot qui

1476
01:11:00,710 --> 01:11:02,000
sait où ce genre de choses est?

1477
01:11:02,000 --> 01:11:03,630
Il n'a même pas besoin de couler comme ça.

1478
01:11:03,630 --> 01:11:06,050
Certaines des données pourrait être
Retour à la gauche là-haut.

1479
01:11:06,050 --> 01:11:07,530
Vous ne savez même pas.

1480
01:11:07,530 --> 01:11:15,430
>> Et ainsi, avec un tableau, vous avez un
fonctionnalité appelée accès aléatoire.

1481
01:11:15,430 --> 01:11:20,570
Et quels moyens d'accès aléatoire est
que l'ordinateur peut sauter instantanément

1482
01:11:20,570 --> 01:11:22,730
à tout emplacement dans une matrice.

1483
01:11:22,730 --> 01:11:23,580
Pourquoi?

1484
01:11:23,580 --> 01:11:26,000
Parce que l'ordinateur sait
que le premier emplacement est

1485
01:11:26,000 --> 01:11:29,540
zéro, un, deux et trois.

1486
01:11:29,540 --> 01:11:33,890
>> Et donc si vous voulez aller de
cet élément à l'élément suivant,

1487
01:11:33,890 --> 01:11:36,099
vous littéralement, dans le
l'esprit de l'ordinateur, il suffit d'ajouter un.

1488
01:11:36,099 --> 01:11:39,140
Si vous voulez aller au troisième élément,
il suffit d'ajouter One-- élément suivant, juste

1489
01:11:39,140 --> 01:11:40,290
ajoute un.

1490
01:11:40,290 --> 01:11:42,980
Toutefois, dans cette version,
de l'histoire, supposons

1491
01:11:42,980 --> 01:11:46,080
l'ordinateur est actuellement à la recherche
à ou de traiter avec le numéro 100.

1492
01:11:46,080 --> 01:11:49,770
Comment obtenez-vous à la prochaine
grade dans le carnet de notes?

1493
01:11:49,770 --> 01:11:52,560
>> Vous devez prendre sept
étapes, qui est arbitraire.

1494
01:11:52,560 --> 01:11:58,120
Pour se rendre à la suivante, vous devez
prendre encore huit étapes pour arriver à 15.

1495
01:11:58,120 --> 01:12:02,250
En d'autres termes, il est pas un
écart constant entre les nombres,

1496
01:12:02,250 --> 01:12:04,857
et donc il faut juste le
ordinateur plus de temps est le point.

1497
01:12:04,857 --> 01:12:06,940
L'ordinateur doit rechercher
à travers la mémoire afin

1498
01:12:06,940 --> 01:12:08,990
pour trouver ce que vous cherchez.

1499
01:12:08,990 --> 01:12:14,260
>> Ainsi, alors que un tableau tend à être un
structure-- de données rapide parce que vous

1500
01:12:14,260 --> 01:12:17,610
peut littéralement faire des calculs simples
et obtenir où vous voulez en ajoutant un,

1501
01:12:17,610 --> 01:12:21,300
pour instance-- une liste liée,
vous sacrifiez cette fonctionnalité.

1502
01:12:21,300 --> 01:12:24,020
Vous ne pouvez pas simplement aller de la première
à la seconde au troisième à la quatrième.

1503
01:12:24,020 --> 01:12:25,240
Vous devez suivre la carte.

1504
01:12:25,240 --> 01:12:28,160
Vous devez prendre plusieurs étapes
pour arriver à ces valeurs, qui

1505
01:12:28,160 --> 01:12:30,230
semble être l'ajout d'un coût.

1506
01:12:30,230 --> 01:12:35,910
Donc, nous payons un prix, mais ce qui était
la fonctionnalité que Dan cherchait ici?

1507
01:12:35,910 --> 01:12:38,110
Qu'est-ce que une liste chaînée
apparemment nous permettent de faire,

1508
01:12:38,110 --> 01:12:40,240
qui était à l'origine de
cette histoire?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Exactement.

1511
01:12:43,830 --> 01:12:46,220
Une taille dynamique pour elle.

1512
01:12:46,220 --> 01:12:48,040
Nous pouvons ajouter à cette liste.

1513
01:12:48,040 --> 01:12:51,430
On peut même réduire la liste,
que nous sommes seulement en utilisant autant de mémoire

1514
01:12:51,430 --> 01:12:55,560
que nous voulons réellement et ainsi
nous ne sommes jamais trop allocation.

1515
01:12:55,560 --> 01:12:58,470
>> Maintenant, juste pour être vraiment tatillon,
il y a un coût caché.

1516
01:12:58,470 --> 01:13:01,980
Donc, vous ne devriez pas laisser juste me convaincre
vous que ceci est un compromis convaincant.

1517
01:13:01,980 --> 01:13:04,190
Il y a un autre coût caché ici.

1518
01:13:04,190 --> 01:13:06,550
L'avantage, pour être clair,
est que nous obtenons dynamisme.

1519
01:13:06,550 --> 01:13:10,359
Si je veux un autre élément, je peux juste
dessiner et de mettre un certain nombre là-bas.

1520
01:13:10,359 --> 01:13:12,150
Et puis je peux relier
avec une photo ici,

1521
01:13:12,150 --> 01:13:14,970
alors ici, encore une fois, si je l'ai
moi-même peint dans un coin,

1522
01:13:14,970 --> 01:13:19,410
si quelque chose est déjà utilisé
la mémoire ici, je suis hors de la chance.

1523
01:13:19,410 --> 01:13:21,700
Je me suis peint dans le coin.

1524
01:13:21,700 --> 01:13:24,390
>> Mais ce qui est caché
coût dans cette image?

1525
01:13:24,390 --> 01:13:27,690
Il n'y a pas que le montant
du temps qu'il faut

1526
01:13:27,690 --> 01:13:29,870
pour aller d'ici à là,
qui est sept étapes, puis

1527
01:13:29,870 --> 01:13:32,820
huit étapes, ce qui est plus d'un.

1528
01:13:32,820 --> 01:13:34,830
Quel est un autre coût caché?

1529
01:13:34,830 --> 01:13:35,440
Non seulement le temps.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Des informations supplémentaires sont
nécessaire pour atteindre cette image.

1532
01:13:49,940 --> 01:13:53,210
>> Oui, cette carte, ces petits bouts de
papier, que je garde les décrivant comme.

1533
01:13:53,210 --> 01:13:55,650
Ces arrows-- ceux qui ne sont pas libres.

1534
01:13:55,650 --> 01:13:57,660
A computer-- vous savez
ce qu'un ordinateur a.

1535
01:13:57,660 --> 01:13:58,790
Il a des zéros et des uns.

1536
01:13:58,790 --> 01:14:03,170
Si vous voulez représenter une flèche ou un
carte ou un numéro, vous avez besoin d'un peu de mémoire.

1537
01:14:03,170 --> 01:14:05,950
Donc, l'autre prix que vous
payer pour une liste liée,

1538
01:14:05,950 --> 01:14:09,070
une science informatique commun
ressources, est également l'espace.

1539
01:14:09,070 --> 01:14:11,710
>> Et en effet si, si souvent,
parmi les compromis

1540
01:14:11,710 --> 01:14:15,580
dans la conception de génie logiciel
systèmes est temps et space--

1541
01:14:15,580 --> 01:14:18,596
sont deux de vos ingrédients, deux
de vos ingrédients les plus coûteux.

1542
01:14:18,596 --> 01:14:21,220
Cela me coûte plus de temps
parce que je dois suivre ce plan,

1543
01:14:21,220 --> 01:14:25,730
mais il est aussi me coûte plus d'espace
parce que je dois garder cette carte autour.

1544
01:14:25,730 --> 01:14:28,730
Donc, l'espoir, comme nous l'avons sorte de
discuté plus hier et d'aujourd'hui,

1545
01:14:28,730 --> 01:14:31,720
est que les avantages
seront supérieurs aux coûts.

1546
01:14:31,720 --> 01:14:33,870
>> Mais il n'y a pas de solution évidente ici.

1547
01:14:33,870 --> 01:14:35,870
Peut-être est better--
a la rapide et sale,

1548
01:14:35,870 --> 01:14:38,660
Kareem a proposé l'heure, à
de jeter la mémoire au problème.

1549
01:14:38,660 --> 01:14:42,520
Il suffit d'acheter plus de mémoire, penser moins
difficile de résoudre le problème,

1550
01:14:42,520 --> 01:14:44,595
et de le résoudre d'une manière plus facile.

1551
01:14:44,595 --> 01:14:46,720
Et plus tôt en effet, quand
nous avons parlé de compromis,

1552
01:14:46,720 --> 01:14:49,190
il n'a pas été dans l'espace
l'ordinateur et le temps.

1553
01:14:49,190 --> 01:14:51,810
Il était temps de développeur, qui
est encore une autre ressource.

1554
01:14:51,810 --> 01:14:54,829
>> Encore une fois, il est cet équilibre
essayant de décider lequel de ces choses

1555
01:14:54,829 --> 01:14:55,870
êtes-vous prêt à dépenser?

1556
01:14:55,870 --> 01:14:57,380
Ce qui est le moins cher?

1557
01:14:57,380 --> 01:15:01,040
Ce qui donne les meilleurs résultats?

1558
01:15:01,040 --> 01:15:01,540
Ouais?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Effectivement.

1561
01:15:12,580 --> 01:15:15,970
Dans ce cas, si vous êtes
représentant des nombres dans le maps--

1562
01:15:15,970 --> 01:15:18,820
ceux-ci sont appelés dans de nombreuses langues
"pointeurs" ou "adresses" -

1563
01:15:18,820 --> 01:15:20,390
il est double de l'espace.

1564
01:15:20,390 --> 01:15:24,390
Cela n'a pas besoin d'être aussi mauvais que doubler si
en ce moment, nous sommes en train de stocker des numéros.

1565
01:15:24,390 --> 01:15:27,410
Supposons que nous stockons
les dossiers des patients dans un hospital--

1566
01:15:27,410 --> 01:15:30,870
donc les noms de Pierson, numéros de téléphone,
numéros de sécurité sociale, médecin

1567
01:15:30,870 --> 01:15:31,540
histoire.

1568
01:15:31,540 --> 01:15:34,160
Cette boîte peut être beaucoup,
beaucoup plus important, auquel cas

1569
01:15:34,160 --> 01:15:38,000
un tout petit pointeur, l'adresse de
la prochaine element-- ce n'est pas une grosse affaire.

1570
01:15:38,000 --> 01:15:40,620
Il est une telle frange
le coût n'a pas d'importance.

1571
01:15:40,620 --> 01:15:43,210
Mais dans ce cas, oui, il est un doublement.

1572
01:15:43,210 --> 01:15:45,290
Bonne question.

1573
01:15:45,290 --> 01:15:47,900
>> Parlons un temps
peu plus concrètement.

1574
01:15:47,900 --> 01:15:50,380
Quelle est la durée de fonctionnement
de la recherche de cette liste?

1575
01:15:50,380 --> 01:15:53,640
Supposons que je voulais chercher
à travers toutes les qualités »des élèves,

1576
01:15:53,640 --> 01:15:55,980
et il y a n grades
dans cette structure de données.

1577
01:15:55,980 --> 01:15:58,830
Ici aussi, nous pouvons emprunter
le vocabulaire plus tôt.

1578
01:15:58,830 --> 01:16:00,890
Ceci est une structure de données linéaire.

1579
01:16:00,890 --> 01:16:04,570
>> Big O n est ce qui est nécessaire pour obtenir
à la fin de cette structure de données,

1580
01:16:04,570 --> 01:16:08,410
whereas-- et nous avons pas vu
ce before-- un tableau vous donne

1581
01:16:08,410 --> 01:16:13,555
ce qu'on appelle la constante de temps, ce qui signifie
une étape ou deux étapes ou 10 steps--

1582
01:16:13,555 --> 01:16:14,180
n'a pas d'importance.

1583
01:16:14,180 --> 01:16:15,440
Il est un nombre fixe.

1584
01:16:15,440 --> 01:16:17,440
Cela n'a rien à voir avec
la taille de la matrice.

1585
01:16:17,440 --> 01:16:20,130
Et la raison de cela,
encore une fois, un accès aléatoire.

1586
01:16:20,130 --> 01:16:23,180
L'ordinateur peut tout de suite
sauter vers un autre emplacement,

1587
01:16:23,180 --> 01:16:27,770
parce qu'ils sont tous les mêmes
distance de tout le reste.

1588
01:16:27,770 --> 01:16:29,112
Il n'y a pas de pensée impliqué.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
D'accord.

1591
01:16:32,400 --> 01:16:39,230
Donc, si je peux, je vais essayer de
peindre deux images finales.

1592
01:16:39,230 --> 01:16:42,830
Un très commun connu sous le nom d'une table de hachage.

1593
01:16:42,830 --> 01:16:51,120
Donc, pour motiver cette discussion,
laissez-moi réfléchir sur la façon de le faire.

1594
01:16:51,120 --> 01:16:52,610
>> Alors, comment à ce sujet?

1595
01:16:52,610 --> 01:16:55,160
Supposons que le problème
nous voulons résoudre maintenant

1596
01:16:55,160 --> 01:16:58,360
est mise en œuvre dans un dictionary--
donc tout un tas de mots anglais

1597
01:16:58,360 --> 01:16:59,330
Ou peu importe.

1598
01:16:59,330 --> 01:17:02,724
Et l'objectif est d'être en mesure de répondre
les questions de la forme est-ce un mot?

1599
01:17:02,724 --> 01:17:04,640
Donc, vous voulez mettre en œuvre
un correcteur orthographique, juste

1600
01:17:04,640 --> 01:17:07,220
comme un dictionnaire physique
que vous pouvez regarder les choses dans.

1601
01:17:07,220 --> 01:17:10,490
Supposons que je devais le faire avec un tableau.

1602
01:17:10,490 --> 01:17:12,590
Je pourrais le faire.

1603
01:17:12,590 --> 01:17:20,756
>> Et supposons que les mots sont la pomme
et de la banane et le cantaloup.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
Et je ne peux pas penser de fruits
qui commencent par d, donc nous sommes juste

1606
01:17:26,465 --> 01:17:27,590
va avoir trois fruits.

1607
01:17:27,590 --> 01:17:31,510
Donc, c'est un tableau, et nous sommes
stocker tous ces mots

1608
01:17:31,510 --> 01:17:34,200
dans ce dictionnaire comme un tableau.

1609
01:17:34,200 --> 01:17:39,350
La question, alors, est de savoir comment les autres
pourriez-vous stocker cette information?

1610
01:17:39,350 --> 01:17:43,160
>> Eh bien, je suis une sorte de tricherie ici, parce que
chacune de ces lettres dans le mot

1611
01:17:43,160 --> 01:17:44,490
est vraiment un octet individuel.

1612
01:17:44,490 --> 01:17:46,740
Donc, si je voulais vraiment être
tatillon, je devrais vraiment

1613
01:17:46,740 --> 01:17:49,600
être divisant vers le haut dans beaucoup
petits morceaux de mémoire,

1614
01:17:49,600 --> 01:17:51,289
et nous pourrions faire exactement cela.

1615
01:17:51,289 --> 01:17:53,580
Mais nous allons courir dans
le même problème que précédemment.

1616
01:17:53,580 --> 01:17:56,674
Que faire si, comme Merriam Webster ou Oxford
fait chaque année-- ils ajoutent des mots

1617
01:17:56,674 --> 01:17:59,340
à la dictionary-- nous ne faisons pas
forcément envie de nous peindre

1618
01:17:59,340 --> 01:18:00,780
dans un coin avec un tableau?

1619
01:18:00,780 --> 01:18:05,710
>> Ainsi, au lieu, peut-être une approche plus intelligente
est de mettre la pomme dans son propre noeud ou une boîte,

1620
01:18:05,710 --> 01:18:11,190
comme nous dirions, la banane, et
puis nous avons ici le cantaloup.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
Et nous string ces choses ensemble.

1623
01:18:16,790 --> 01:18:19,980
Voici donc le tableau, et
voici la liste liée.

1624
01:18:19,980 --> 01:18:23,300
Si vous ne pouvez pas tout voir, juste
dit «tableau», et cela dit "liste."

1625
01:18:23,300 --> 01:18:25,780
>> Donc, nous avons le même
questions précises comme avant,

1626
01:18:25,780 --> 01:18:28,600
de sorte que nous avons maintenant
dynamisme dans notre liste liée.

1627
01:18:28,600 --> 01:18:31,090
Mais nous avons un dictionnaire assez lent.

1628
01:18:31,090 --> 01:18:32,870
Supposons que je veux chercher un mot.

1629
01:18:32,870 --> 01:18:35,430
Il pourrait me prendre grand O n
étapes, parce que le mot pourrait

1630
01:18:35,430 --> 01:18:37,840
soit tout le chemin à la fin de
la liste, comme le cantaloup.

1631
01:18:37,840 --> 01:18:40,600
Et il se trouve que
dans la programmation, le tri

1632
01:18:40,600 --> 01:18:42,700
du Saint-Graal des données
structures, est quelque chose

1633
01:18:42,700 --> 01:18:46,620
qui vous donne constante
temps comme un tableau

1634
01:18:46,620 --> 01:18:50,870
mais cela vous donne encore le dynamisme.

1635
01:18:50,870 --> 01:18:52,940
>> Ainsi pouvons-nous avoir le meilleur des deux mondes?

1636
01:18:52,940 --> 01:18:55,570
Et en effet, il y a quelque chose
appelé la table de hachage

1637
01:18:55,570 --> 01:18:59,320
qui vous permet de faire exactement
que, bien qu'approximative.

1638
01:18:59,320 --> 01:19:03,140
Une table de hachage est un amateur
Structure de données que nous

1639
01:19:03,140 --> 01:19:06,340
peut penser que le
Combinaison d'un array--

1640
01:19:06,340 --> 01:19:12,390
et je vais dessiner
comme this-- et listes chaînées

1641
01:19:12,390 --> 01:19:17,310
que je vais dessiner comme ça ici.

1642
01:19:17,310 --> 01:19:19,760
>> Et la façon dont cette chose
ouvrages est le suivant.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Si ce maintenant-- hachage table--
est ma troisième structure de données,

1645
01:19:29,540 --> 01:19:32,590
et je veux stocker
mots, je ne sais pas

1646
01:19:32,590 --> 01:19:35,440
veulent simplement stocker tous les
mots dos à dos à dos à dos.

1647
01:19:35,440 --> 01:19:37,430
Je veux tirer parti de certains
un bout d'information

1648
01:19:37,430 --> 01:19:40,330
sur les mots qui vous permettra de
moi obtenir là où il est plus rapide.

1649
01:19:40,330 --> 01:19:43,666
>> Donc, étant donné la pomme de mots
et de la banane et le cantaloup,

1650
01:19:43,666 --> 01:19:45,040
Je choisis délibérément ces mots.

1651
01:19:45,040 --> 01:19:45,340
Pourquoi?

1652
01:19:45,340 --> 01:19:47,631
Quelle est une sorte de fond
différent des trois?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Quel est l'évidence?

1655
01:19:51,484 --> 01:19:52,900
Ils commencent par des lettres différentes.

1656
01:19:52,900 --> 01:19:53,900
>> Donc, vous savez quoi?

1657
01:19:53,900 --> 01:19:57,120
Plutôt que de mettre tous mes mots
le même seau, pour ainsi dire,

1658
01:19:57,120 --> 01:20:00,390
comme dans une grande liste, pourquoi ne pas
Au moins je tente une optimisation

1659
01:20:00,390 --> 01:20:04,180
et de faire mes listes 1/26 aussi longtemps.

1660
01:20:04,180 --> 01:20:07,440
Une optimisation convaincante
peut-être pourquoi ne pas

1661
01:20:07,440 --> 01:20:10,650
Je-- lors de l'insertion d'un mot
dans cette structure de données,

1662
01:20:10,650 --> 01:20:14,300
dans la mémoire de l'ordinateur, pour laquelle
Je ne mets pas tous les «a» mots ici,

1663
01:20:14,300 --> 01:20:17,270
tous les mots 'b' ici,
et tous les 'c' mots ici?

1664
01:20:17,270 --> 01:20:24,610
Donc, cela finit par mettre une pomme
ici, banane ici, le cantaloup ici,

1665
01:20:24,610 --> 01:20:25,730
et ainsi de suite.

1666
01:20:25,730 --> 01:20:31,700
>> Et si je dois un montant supplémentaire
mot like-- ce qui est une autre?

1667
01:20:31,700 --> 01:20:36,640
Apple, banane, poire.

1668
01:20:36,640 --> 01:20:39,370
Toute personne pense à un fruit
qui commence par a, b, c?

1669
01:20:39,370 --> 01:20:40,570
parfait Blueberry--.

1670
01:20:40,570 --> 01:20:43,990
Cela va finir par ici.

1671
01:20:43,990 --> 01:20:47,530
Et donc nous semblent avoir un
légèrement meilleure solution,

1672
01:20:47,530 --> 01:20:50,820
parce que maintenant si je veux
à la recherche de la pomme, je

1673
01:20:50,820 --> 01:20:53,200
first-- Je ne suis pas simplement plongée
dans ma structure de données.

1674
01:20:53,200 --> 01:20:54,850
Je ne plonge pas dans la mémoire de mon ordinateur.

1675
01:20:54,850 --> 01:20:56,530
Je regarde d'abord à la première lettre.

1676
01:20:56,530 --> 01:20:58,610
>> Et voici ce qu'est un ordinateur
scientifique dirait.

1677
01:20:58,610 --> 01:21:00,760
Vous hachage dans votre structure de données.

1678
01:21:00,760 --> 01:21:04,100
Vous prenez votre entrée, qui
ce cas est un mot comme la pomme.

1679
01:21:04,100 --> 01:21:07,150
Vous analysez, en regardant
la première lettre dans ce cas,

1680
01:21:07,150 --> 01:21:08,340
le hachage de ce fait.

1681
01:21:08,340 --> 01:21:10,950
Hashage est un terme général dans lequel
vous prenez quelque chose comme entrée

1682
01:21:10,950 --> 01:21:12,116
et que vous produisez une certaine sortie.

1683
01:21:12,116 --> 01:21:15,090
Et la sortie en ce qu '
cas est l'emplacement

1684
01:21:15,090 --> 01:21:18,150
vous voulez rechercher, le premier
emplacement, deuxième emplacement, troisième.

1685
01:21:18,150 --> 01:21:22,160
Donc, l'entrée est la pomme,
la sortie est le premier.

1686
01:21:22,160 --> 01:21:25,054
L'entrée est la banane, la
sortie devrait être une seconde.

1687
01:21:25,054 --> 01:21:27,220
L'entrée est cantaloup,
la sortie devrait être troisième.

1688
01:21:27,220 --> 01:21:30,320
L'entrée est myrtille, la
sortie devrait être à nouveau deuxième.

1689
01:21:30,320 --> 01:21:34,010
Et c'est ce que vous aide à prendre
raccourcis à travers votre mémoire

1690
01:21:34,010 --> 01:21:39,050
afin d'obtenir des mots
ou des données de manière plus efficace.

1691
01:21:39,050 --> 01:21:43,330
>> Maintenant, cela réduit notre temps potentiellement
d'autant que l'un de 26,

1692
01:21:43,330 --> 01:21:45,850
parce que si vous supposez que vous
avoir autant de "a" mots comme "z"

1693
01:21:45,850 --> 01:21:48,080
mots comme mots «q», qui
est pas vraiment realistic--

1694
01:21:48,080 --> 01:21:50,830
vous allez avoir skew travers
certaines lettres de l'alphabet--

1695
01:21:50,830 --> 01:21:53,204
mais ce serait une incrémental
approche qui ne permet

1696
01:21:53,204 --> 01:21:55,930
vous obtenez des mots beaucoup plus rapidement.

1697
01:21:55,930 --> 01:21:59,660
Et en réalité, un système sophistiqué
programme, le Googles du monde,

1698
01:21:59,660 --> 01:22:02,180
le Facebooks du monde--
ils utilisent une table de hachage

1699
01:22:02,180 --> 01:22:03,740
pour beaucoup d'usages différents.

1700
01:22:03,740 --> 01:22:06,590
Mais ils ne seraient pas si naïf
juste regarder la première lettre

1701
01:22:06,590 --> 01:22:09,700
en pomme ou une banane ou
poire ou cantaloup,

1702
01:22:09,700 --> 01:22:13,420
parce que vous pouvez voir ces
listes pourraient encore être longue.

1703
01:22:13,420 --> 01:22:17,130
>> Et cela pourrait encore être une sorte
de linear-- donc sorte de lent,

1704
01:22:17,130 --> 01:22:19,980
comme avec le grand O n
que nous avons discuté plus tôt.

1705
01:22:19,980 --> 01:22:25,290
Alors qu'est-ce une vraie bonne table de hachage
do-- il aura un beaucoup plus grand tableau.

1706
01:22:25,290 --> 01:22:28,574
Et il utilisera beaucoup plus
fonction de hachage sophistiquée,

1707
01:22:28,574 --> 01:22:30,240
de sorte qu'il ne suffit de regarder le «a».

1708
01:22:30,240 --> 01:22:35,480
Peut-être qu'il regarde "a-p-p-l-e» et
convertit en quelque sorte ces cinq lettres

1709
01:22:35,480 --> 01:22:38,400
à l'endroit où
pomme doit être stocké.

1710
01:22:38,400 --> 01:22:42,660
Nous sommes juste naïvement en utilisant la lettre 'a'
seul, parce qu'il est simple et agréable.

1711
01:22:42,660 --> 01:22:44,600
>> Mais une table de hachage, dans
la fin, vous pouvez penser

1712
01:22:44,600 --> 01:22:47,270
comme une combinaison de
un tableau, dont chacune

1713
01:22:47,270 --> 01:22:51,700
a une liste liée qu'idéalement
doit être aussi courte que possible.

1714
01:22:51,700 --> 01:22:54,364
Et ce n'est pas une solution évidente.

1715
01:22:54,364 --> 01:22:57,280
En fait, une grande partie du réglage fin
ce qui se passe sous le capot lorsque

1716
01:22:57,280 --> 01:22:59,654
la mise en œuvre de ces types de
structures de données complexes

1717
01:22:59,654 --> 01:23:01,640
est ce qui est le droit
la longueur de la matrice?

1718
01:23:01,640 --> 01:23:03,250
Quelle est la fonction de hachage à droite?

1719
01:23:03,250 --> 01:23:04,830
Comment pensez-vous de stocker des choses en mémoire?

1720
01:23:04,830 --> 01:23:07,249
>> Mais se rendre compte de la rapidité
ce genre de discussion

1721
01:23:07,249 --> 01:23:10,540
escalade, soit si loin qu'il est le genre
de dessus de la tête à ce point, ce qui

1722
01:23:10,540 --> 01:23:11,360
c'est bien.

1723
01:23:11,360 --> 01:23:18,820
Mais nous avons commencé, le rappel, avec vraiment
bas niveau quelque chose et électronique.

1724
01:23:18,820 --> 01:23:20,819
Et cela est encore cette
thème de l'abstraction,

1725
01:23:20,819 --> 01:23:23,610
où une fois que vous commencez à prendre pour
accordée, OK, je l'ai it-- obtenu il y a

1726
01:23:23,610 --> 01:23:26,680
mémoire physique, OK, il a obtenu, chaque
emplacement physique a une adresse,

1727
01:23:26,680 --> 01:23:29,910
OK, je l'ai eu, je peux représenter
ces adresses comme arrows--

1728
01:23:29,910 --> 01:23:34,650
vous pouvez très rapidement commencer à avoir
conversations plus sophistiquées

1729
01:23:34,650 --> 01:23:38,360
à la fin semblent être nous permettant
pour résoudre des problèmes tels que la recherche

1730
01:23:38,360 --> 01:23:41,620
et trier plus efficacement.

1731
01:23:41,620 --> 01:23:44,190
Et rassurez-vous, too--
parce que je pense que ce

1732
01:23:44,190 --> 01:23:48,700
est le plus profond que nous sommes allés dans certains
de ces sujets CS proper-- nous avons

1733
01:23:48,700 --> 01:23:51,880
fait en un jour et demi à ce
pointez ce que vous pourriez normalement faire plus

1734
01:23:51,880 --> 01:23:55,520
au cours de huit semaines à un semestre.

1735
01:23:55,520 --> 01:23:59,670
>> Toute question sur ces?

1736
01:23:59,670 --> 01:24:01,100
Non?

1737
01:24:01,100 --> 01:24:01,940
D'accord.

1738
01:24:01,940 --> 01:24:05,610
Eh bien, pourquoi ne nous y arrêtons pas,
commencer à déjeuner quelques minutes plus tôt,

1739
01:24:05,610 --> 01:24:07,052
reprendre dans à peu près une heure?

1740
01:24:07,052 --> 01:24:08,760
Et je vais persister pendant
un peu avec des questions.

1741
01:24:08,760 --> 01:24:11,343
Ensuite, je vais devoir aller
prendre quelques appels si c'est OK.

1742
01:24:11,343 --> 01:24:15,000
Je cède la parole de la musique, dans l'intervalle,
mais le déjeuner devrait être dans le coin.

1743
01:24:15,000 --> 01:24:17,862