[MUSIQUE LECTURE] 

ENCEINTE 1: Très bien, c'est CS50, et c'est le début de la quatrième semaine, et comme vous avez pu entendre ou lire, le monde a été à sa fin. Aller tout autour de l'Internet a été la connaissance et de la sensibilisation d'un bogue dans un programme, un langage de programmation appelé Bash. Cela a été merveilleux de marque comme Shellshock, ou la porte de Bash, mais des articles comme ceux-ci n'ont pas été rares. Et en fait, beaucoup d'entre eux apportent souvenirs de retour de Heartbleed, que vous avez peut-être remarqué dans le refouler le printemps dernier, qui était de même assez dramatique. Maintenant, ceux d'entre vous ici aujourd'hui, combien d'entre vous ont, même si vous ne comprenez pas ce il est tout au sujet, entendu parler de Shellshock? Très bien, et combien d'entre vous avoir des ordinateurs qui sont vulnérables? OK, il devrait y avoir beaucoup, beaucoup plus de mains jusqu'à ce moment, pour des raisons que nous verrons. 

Jetons un oeil à ce qui est se passe dans les médias puis l'expliquer un peu ici pour nous sur le plan technique. 

ENCEINTE 2: Les experts en sécurité ont averti qu'une grave lacune pourrait être sur le point de toucher des centaines de millions d'utilisateurs d'Internet dans le monde. Alors, quel est exactement le bug qui a été surnommé Shellshock, et que fait-il? Eh bien, Shellshock est également connu comme l' bug de Bash, le logiciel qu'il exploite. Les pirates utilisent le virus pour scanner vulnérables systèmes fonctionnant sous Linux et Unix les systèmes d'exploitation et les infecter. Bash est un shell en ligne de commande. Cela permet aux utilisateurs de question de lancer des commandes programmes et fonctionnalités dans le logiciel par la saisie de texte. Il est généralement utilisé par les programmeurs, et ne devrait pas être ouvert au reste du monde, si Shellshock change cela. 

Eh bien, worringly, certains analystes avertir qu'il pourrait être une plus grande menace, parce Shellshock permet complète le contrôle d'une machine infectée, alors que Heartbleed seulement permis les pirates pour espionner les ordinateurs. C'est tellement grave, c'est été évalué à 10 sur 10 de la gravité par le National Base de données de vulnérabilité. 2/3 de tous les serveurs Web sont à risque, y compris des ordinateurs Mac. Eh bien, assurez-vous patcher votre système maintenant. N'importe qui héberge un site Internet marche les systèmes d'exploitation affectés devraient prendre des mesures dès que possible. N'importe qui peut se permettre il devrait ressembler à leur application de surveillance et web pare-feu à regarder dehors pour toutes les attaques. ENCEINTE 3: Le pire qui pourrait arriver, c'est que quelqu'un écrire du code qui serait automatiquement aller et numériser Internet et affecterait l'ensemble de ces ordinateurs. Et une fois qu'ils le font, bien, la pire chose qu'ils pouvaient faire est il suffit de supprimer tout ou fermer les sites potentiels. Donc, nous pourrions voir des dommages de ce point de vue, où nous aurions des personnes mal intentionnées qui décident juste de causer des ravages en amenant vers le bas ou la suppression des systèmes fichiers, et des choses comme ça. ENCEINTE 2: Certains disent que c'est un des plus difficiles à mesurer bogues dans les années, et il peut prendre des semaines ou même mois afin de déterminer son impact final. 

ENCEINTE 1: Donc tout cela est vrai, mais le plus drôle est, la quasi-totalité de l'imagerie vous venez de voir, sauf peut-être le clavier, n'a rien à voir avec le bug que ce soit. Les serveurs et les fils et ainsi de suite, C'est une sorte de qu'accessoirement, mais à la base, il est en fait assez familier ce qui se passe ici. En fait, laissez-moi aller dans notre appareil de CS50. Permettez-moi aller de l'avant et de maximiser la fenêtre de terminal ici. Et vous les gars ont eu recours à cela, ou la version embarquée de celui-ci, dans gedit pour écrire des programmes, entrer des commandes, et ainsi de suite, et c'est effectivement, et a été pendant des semaines, Bash, B-A-S-H. Il s'agit de la Bourne again shell, qui est juste une façon élégante de dire, il s'agit d'un programme qui a un clignotement rapide, efficace, qui est assis là à attendre pour l'entrée pour vous. Et c'est la commande interface de ligne par l'intermédiaire duquel vous les gars ont été l'exécution de commandes et finalement, la compilation et l'exécution programmes. 

Mais Bash est également une programmation langue dans le sens suivant. Vous savez qu'il ya des commandes comme cd et ls et aussi clang et autres, mais vous pouvez définir vos propres commandes par leur mise en œuvre dans Bash. Maintenant, nous n'allons pas entrer dans les détails à bash le langage de programmation, mais savoir, par exemple, que pour le moment, il n'y a pas de commande appelé «bonjour». Donc, il peut être trouvé dans un de ces paquets. Il n'est pas installé sur mon ordinateur. Demandez à votre administrateur. Mais si je veux qu'il y ait un programme appelé «bonjour» en Bash ou à mon invite, Je peux effectivement utiliser la syntaxe c'est tout à fait comme C. Ce n'est pas tout à fait la même, mais il semble assez similaire à un fonction, mais manque quelques détails. Rien ne semble se passer, mais maintenant, si je tape "bonjour" vous pouvez réellement écrire un programme, pas en C, pas en Java, pas dans une autre programmation langue, mais en Bash lui-même. 

Maintenant, la clé ici est que j'ai écrit l' nom que je voulais donner à cette nouvelle commande, et les parenthèses sont également symbolique de ce qui est une fonction. En passant, vous pouvez également faire plaisir choses, et en fait, même sur Mac OS, il s'agit d'un programme appelé Terminal. Il est livré intégré dans n'importe qui ordinateur équipé d'un Mac dans cette salle, et vous pouvez faire des choses similaires à Mac OS, mais vous pouvez aller plus loin. Et c'est un peu tangent, mais c'est le genre de plaisir. Je me suis rappelé ce matin, en pensant ce travers, d'un petit jeu que j'ai l'habitude de jouer avec l'un des anciens de FO CS50 lequel tout moment il quitterait son clavier avec son écran déverrouillé, Je voudrais exécuter une commande comme this-- "dire bonjour." Et maintenant, chaque fois qu'il est revenu à son clavier après j'ai effacé l'écran et il s'asseyait, essayer de faire un peu de travail, lister le contenu de son directory-- 

[LECTURE AUDIO] 

-Hello. Bonjour. 

ENCEINTE 1: Donc, en toute équité, il n'a pas été fait "bonjour." Il était généralement quelque chose plus proche de that-- [LECTURE AUDIO] -Beep. ENCEINTE 1: --que je would-- si son ordinateur serait jure à lui chaque fois qu'il fait assis à son clavier. Et très vite, il a compris de ne pas laisser son écran déverrouillé. Mais cela suggère le genre de plaisir stupide que vous peut avoir avec quelque chose comme Bash. Mais il est un peu plus grave, bien sûr, que cela. Et en fait, c'est l'un des la plupart des bogues dangereux et durables qui a vraiment touché le monde entier dans le monde. Ce bug a été autour depuis 20 ans, et vous serez frappé en seulement instant de sa relative simplicité. 

Il s'agit donc d'un représentant commander que si vous posséder un Mac, littéralement dès maintenant quand vous avez votre couvercle ouvert, vous pouvez essayer de taper dans cette programme appelé Terminal. Terminal est en cours Applications Utilities-- pour une fois, les utilisateurs de Windows n'ont pas à s'inquiéter à ce sujet threat-- particulier mais ceux d'entre vous avec les Mac peut taper ce dans une fenêtre comme je vais le faire ici, et si vous ne tapez que dans ce programme, appelé Terminal, comme je vais le faire maintenant, si vous voyez le mot «vulnérable» votre ordinateur est vulnérables à l'exploitation. 

Maintenant, qu'est-ce que signifie réellement? Et ce n'est certes une syntaxe assez fou, mais nous allons au moins tirer certains des aspects intéressants. Donc, il ya une syntaxe qui ressemble un peu familier, au moins à partir de C et la programmation en général. Je vois des parenthèses, des points-virgules, des accolades, et comme, mais il se trouve que ce stupide ici en jaune est essentiellement une fonction qui ne fait rien. Les moyens du côlon ne font rien, et la virgule signifie arrêter de ne rien faire. Ainsi, à l'intérieur de ceux-ci accolades, le fait que j'ai un pied d'égalité signer vers la gauche, ce est essentiellement la création d' une commande ou une variable, appelé x, et en lui attribuant que peu jaune de code là. Cela pourrait être quelque chose comme "écho bonjour »ou« dire bip "ou quelque chose semblable à celle. Mais remarquez si vos yeux promener un peu plus vers la droite, il ya plus à cette ligne de juste à la fin de ce point-virgule. "Echo vulnérables», puis au-delà il ya encore plus. Un autre point-virgule, bash-c :. 

Donc, longue histoire courte, cette ligne de code est suffisante pour contraindre un ordinateur qui est vulnérables à faire quelque chose que vous voulez qu'il fasse, parce qu'il ya un bug dans lequel Bash même si Bash était censé arrêter lecture des lignes de commande à droite il après le texte jaune, un de plus de 20 ans bug, Bash a été effectivement lecture au-delà point-virgule et jolie beaucoup faire ce qu'on lui dit. 

Alors, quelle est l'implication en fin de compte que de? Je viens de dire "echo bonjour" ou "echo vulnérables», mais que faire si vous avez fait quelque chose effectivement malveillant, comme rm-rf *, qui vous ne pourriez pas ont déjà tapé avant, et franchement vous avez probablement ne devrait pas trop tôt, parce que vous pouvez faire beaucoup de dégâts avec elle. Pourquoi? rm fait quoi, bien sûr? Supprime. * Signifie quoi? Tous. C'est donc un soi-disant wild card, donc cela signifie supprimer tout le répertoire courant. r arrive à signifier récursive, qui signifie que si ce que vous la suppression est un répertoire, et à l'intérieur de là est d'autres fichiers et d'autres répertoires, plonger de manière récursive en y et supprimer tout cela. Et f est le pire de tous. Quelqu'un sait ce que signifie ici f? Vigueur. Donc forcer les moyens, même si c'est une mauvaise idée, le faire sans me demandant pour confirmation. Donc, vous le savez, nous rions , mais franchement, je doute Ce type plusieurs fois un jour, parce que la réalité c'est que c'est le meilleur moyen de supprimer tout un tas de choses. Mais même j'ai fait quelques dégâts. 

Mais si vous étiez à tromper un ordinateur en définissant une variable stupide ou fonction appelée x, mais incitant l'ordinateur en exécutant au-delà des limites de cette fonction, au-delà de ce point-virgule, vous pouvez en effet tromper un ordinateur dans l'exécution de quelque chose comme rm-rf ou la commande Email ou la commande Copier. Tout littéralement vous pouvez faire avec la ordinateur, qu'il s'agisse de la suppression de fichiers, la création de fichiers, spamming de quelqu'un, attaquer un serveur à distance, si vous pouvez l'exprimer avec une commande, vous peut tromper un ordinateur en faisant cela. 

Maintenant, ce qui est un exemple de comment vous pouvez faire cela? Eh bien, il ya beaucoup d'ordinateurs sur le Bash internet en cours d'exécution. Tous les utilisateurs de Mac nous sont parmi eux. Un grand nombre de serveurs Linux sont parmi eux aussi, et les serveurs Unix. Fenêtres obtient à nouveau relativement décroché sauf si vous avez installé logiciel spécial. Maintenant, beaucoup de serveurs, pour exemple, les serveurs Web gérés, et en fait, Linux est peut-être le plus le système d'exploitation populaire pour fonctionner sur des ordinateurs sur l'Internet qui purgent des pages web. Maintenant, comme nous le verrons plus tard au cours du semestre, quand vous envoyez une demande de votre browser-- Chrome, Internet Explorer, whatever-- à un serveur distant, il s'avère que, même si vous venez de taper www.example.com, votre navigateur envoie un message c'est un peu plus mystérieux, comme ça. 

Mais remarquez un peu quelque chose d'étrange. Les deux premières lignes Je n'ai jamais vu avant, mais ils ne semblent pas particulièrement menaçant. Mais remarque ce que je t'ai volé pour la troisième ligne ici. Si un mauvais gars devait envoyer un message comme cela de son ordinateur à un Mac ou un vulnérables serveur Linux vulnérables, le plus drôle, c'est que Bash, aussi simple que rapide peu de commande, est omniprésent et est souvent Utilisé pour exécuter l'essentiel le contenu d'un un message qu'il reçoit. Et cette logique, vous pouvez piéger un serveur web, donc, en envoyant quelque chose comme User-Agent, qui, généralement, est censé dire la Nom de votre navigateur. User-Agent Chrome, User-Agent Internet Explorer, Firefox User-Agent, ce est juste le navigateur de votre façon de s'identifier. Mais si un méchant très dit habilement, mm-mm, je suis ne vais pas vous dire ce que mon navigateur est, Je place va vous envoyer ce chose cryptique vers l'avenir avec un rm -rf * En elle, vous pouvez littéralement tromper un le serveur web vulnérable sur Internet dans l'exécution exactement que dans y pour la suppression de tous les fichiers. Et franchement, ce n'est pas même le pire. Vous pouvez faire n'importe quoi. Vous pouvez commencer une distribués déni de service si vous avez envoyé ce message grappes entières de serveurs web puis avaient tous descendent, pour exemple, sur les serveurs Harvard.edu, et vous pouvez trier de coup le diable hors de leur par un trafic de réseau qui était déclenché contraire de ce méchant. 

Alors, longue histoire courte, presque tout le monde dans cette salle qui possède un Mac est vulnérable à cela. La doublure d'argent est que si vous êtes l'exécution d'un serveur Web sur votre ordinateur portable, et si vous avez réellement configuré à permettre quelque chose comme SSH en elle, vous êtes réellement sans danger. Il est vulnérable, mais il n'y a pas celle qui tente de pénétrer dans votre ordinateur portable, de sorte que vous pouvez sorte de tranquille. Toutefois, Apple va bientôt être mise à jour d'un correctif pour cela. Le monde de Linux a déjà publié un certain nombre de correctifs pour Fedora et Ubuntu et d'autres versions de Linux, et en effet si vous exécutez la mise à jour 50 dans l'appareil, même qui trop être mise à jour et corrigée. Mais cela n'a pas trop vraiment été vulnérables, parce que si vous avez bricolé avec l'appareil et fait de votre ordinateur portable publiquement accessible sur Internet, qui n'est pas par défaut, vous avez effectivement été bien parce que de pare-feu et d'autres techniques. 

Mais c'est un exemple extrême d'un bug que nous avons vécu pour pour littéralement 20 ans, et qui sait si quelqu'un tout ce temps a connu à ce sujet? Et en fait, c'est l'un des les défis fondamentaux que nous verrons plus tard dans la semestre sur la sécurité, est que, tout comme dans le monde réel, les bons sont à l'inconvénient. Pour garder les méchants, nous devons s'assurer que chaque porte est verrouillée, que chaque fenêtre est sécurisé, que chaque point d'entrée dans une maison est sûr de garder les méchants. Mais qu'est-ce que le méchant doivent faire réellement compromettre votre maison et vous voler? Il ou elle a juste besoin de trouver un déverrouillé porte, une fenêtre cassée, ou quelque chose le long de ces lignes, et c'est la même chose dans la sécurité informatique. Nous pouvons écrire des millions de lignes de code de programmation et dépenser des centaines ou des milliers des heures à essayer de l'obtenir correcte, Mais si vous faites juste un erreur dans l'exactitude, vous pouvez mettre l'ensemble du système et en effet, dans ce cas, tout l'Internet et dans le monde en danger. 

Donc, si vous souhaitez en savoir plus à ce sujet, allez à cette adresse ici. Il n'y a pas nécessité d'une action ce soir, sauf si vous êtes parmi ceux plus à l'aise que ont été la gestion de votre propre site web serveur, auquel cas vous devriez, en fait, de mettre à jour votre logiciel. 

Et c'est aussi le titre de un discours, et maintenant un document, que nous avons relié à la le site Web de cours pour aujourd'hui. C'était par un collègue nommé Ken Thompson, qui a été d'accepter un très célèbre prix en informatique, et il a donné ce discours quelques années Il ya, essentiellement sur le même sujet. Les gens se poser la question, devriez-vous vraiment confiance, en fin de compte, la logiciel que vous avez reçu? Par exemple, nous avons tous été l'écriture de programmes, et nous avons compilons eux avec Clang. Et à votre connaissance, avez-vous écrit des programmes pour CS50 où il ya une porte arrière de toutes sortes, il ya une façon que un mauvais gars, si vous exécutez votre programme, pourrait prendre contrôle de votre ordinateur? Probablement pas, non? Mario et gourmand, et crédit. Ce sont tous très petits programmes. Vous devriez être assez mauvais si vous avez réellement fait toute votre ordinateur vulnérable après avoir écrit 10 ou 20 lignes de code, ou au moins pas au courant de certaines des implications de sécurité. Maintenant, je dis que la blague, mais nous allons voir aujourd'hui et cette semaine, il s'agit en fait d' vraiment, vraiment facile être mauvais et de faire encore programmes courts vulnérables. 

Mais pour l'instant, au moins, réaliser que la question qui se pose ici est d'environ Clang dans un compilateur. Pourquoi avons-nous fait confiance à Clang pour les deux ou trois dernières semaines? Qui est-à-dire que celui qui a écrit Clang ne pas avoir un "si" condition il que des zéros essentiellement injecté et ceux dans chaque programme, il compile cela laissez-lui l'accès votre ordinateur lorsque vous êtes endormi et le couvercle de votre ordinateur portable est ouvert et votre ordinateur est en marche? Droite? Nous avons cette sorte de droit de système d'honneur maintenant où nous espérons que Clang est légitime. Vous faites confiance que l'appareil est légitime. Vous faites confiance que littéralement chaque programme sur votre Mac ou PC est digne de confiance. Et comme cette simple bug suggère, même si ce n'est pas malveillant, qui n'est absolument pas susceptible d'être le cas. 

Donc, vous devriez avoir peur comme l'enfer. Franchement, il n'y a pas de simples solution à cet autre qu'une sorte de conscience sociale de la complexité croissante que nous construisons sur le dessus de nos systèmes informatiques, et comment de plus en plus vulnérables nous pourrions très bien être. 

Maintenant, avec cela dit, Breakout. Donc Breakout est le problème réglé trois, et Breakout est un jeu d'antan que vous vous en souvenez, mais pour nous problème posé trois, il nous permet de prendre les choses d'un cran de sorte que lorsque nous écrivons des programmes, même dans une fenêtre de terminal comme cela, nous pouvons réellement fonctionner, en fin de compte, programmes graphiques non contrairement à ceux que nous avions l'accès au Scratch. Donc, c'est le personnel de la mise en œuvre de Breakout, qui est juste de ce casse-briques jeu, que vous déplacez votre pagaie retour et-vient, et vous frappez la balle contre ces briques de couleur en haut. Donc, cela nous apporte sorte de retour à l'endroit où nous avons pu être très rapidement avec Scratch, et maintenant avec C, mise en œuvre de notre propre des interfaces utilisateur graphiques. 

Mais plus que cela, ce ensemble de problème représente la première dans laquelle nous donnons vous un tas de code. Et en fait, je vous apporte explicite attention à cela, car en particulier pour ceux qui sont moins à l'aise, ce problème réglé, au moins à première vue, va se sentir comme nous avons pris un cran. Parce que nous vous avons donné, pour une partie de la recherche et le tri des problèmes dans le jeu de processeurs, un tas de code que nous avons écrit, et un couple de commentaires que dire «à faire», où vous devez remplir les blancs. Donc, pas trop effrayant, mais c'est la première fois nous vous remettre le code que vous devez d'abord lire, comprendre, et puis ajouter au et le compléter. 

Et puis avec Breakout, nous allons faire la même chose, vous donnant quelques dizaines de plusieurs lignes de code qui, franchement, vous donner une grande partie du cadre de le jeu, mais s'arrêter de mise en œuvre des briques et la balle et la raquette, mais nous faisons la mise en œuvre d'autres fonctionnalités. Et même que, à première vue, encore une fois, en particulier si elle est inférieure à l'aise, peut sembler particulièrement difficile et vous pensez qu'il ya tellement de nouvelles fonctions vous avez besoin d'envelopper votre esprit autour, et c'est vrai. Mais gardez à l'esprit, il est tout à fait comme Scratch. Les chances sont que vous n'avez pas utilisé tous les pièces du puzzle à zéro. Les chances sont que vous n'avez pas soin d'envelopper votre esprit autour de tous les car il a suffi d'un coup d'oeil rapide à comprendre, oh, c'est ce que je peux faire avec ce morceau de puzzle. Et en effet, en problème posé 3 spec, nous vous indiquerons à la documentation qui sera vous présenter quelques nouvelles fonctions, et, finalement, la programmation constructions que vous utilisez. Conditions, boucles, variables et fonctions sera identique à ce que nous avons vu jusqu'à présent. 

Donc, en effet, ce que nous allons donner vous est un exemple de code qui vous permet de créer une fenêtre qui ressemble un peu comme cela, et, finalement, de le transformer en quelque chose de tout à fait comme ça. Alors, profitez de CS50, discuter des heures de bureau et plus, et réconfort dans le fait que la quantité de code que vous devez écrire est en fait pas tant que ça. Le premier défi est juste à s'acclimater vous un peu de code que nous avons écrit. 

Des questions sur pset3, Shellshock, ou autrement? 

PUBLIC: Il semblait en passant par des petits groupes que le code est presque un style orienté objet, mais je pensais que c'était un C orientée objet programme. ENCEINTE 1: Une excellente question. Donc, en regardant à travers la le code de répartition, le code nous avons écrit pour pset3, pour ceux qui connaissent, il On dirait que c'est un peu orienté objet. Réponse courte est, il est. C'est une approximation de la façon dont vous pourrait faire du code orienté objet à l'aide un langage comme C, mais il est toujours en fin de compte de la procédure. Il n'y a pas de méthodes à l'intérieur de les variables, comme vous le verrez. Mais il rappelle que. Et nous verrons cette fonction à nouveau quand nous arrivons à PHP et JavaScript vers la fin du semestre. Mais pour l'instant, penser que c'est un soupçon de ce qui est à venir. Bonne question. Bien. Donc, le tri par fusion était de savoir comment nous laissé les choses la dernière fois. Et le tri par fusion était cool dans le sens où il était beaucoup plus rapide, au moins sur la base des essais sommaires nous l'avons fait la semaine dernière, que, par exemple, bulle sorte, la sélection sorte, le tri par insertion. Et ce qui était soigné est trop juste comment succinctement et propre vous pouvez exprimer. Et qu'avons-nous dire que c'était un supérieur lié à la durée de fusion trier? Ouais? 

PUBLIC: n log n? 

ENCEINTE 1: n log n, à droite. n log n. Et nous allons revenir à ce que signifie vraiment ou d'où ça vient, mais c'était mieux que ce temps de marche que nous avons vu pour la bulle la sélection et le tri par insertion? Alors n carré. n carré est plus grande que cela, et même si ce n'est pas tout à fait évident, savoir que log n est plus petit que n, donc si vous faites n fois quelque chose plus petit que n, ça va être inférieure à n carré. C'est un peu de l'intuition il. Mais nous avons payé un prix pour cela. Il a été plus rapide, mais un thème qui a commencé de sortir la semaine dernière était ce compromis. J'ai eu une meilleure performance temps sage, mais ce ai-je eu à passer de l'autre main, afin de parvenir à cela? 

PUBLIC: Mémoire. ENCEINTE 1: Dites à nouveau? PUBLIC: Mémoire. ENCEINTE 1: mémoire, ou plus d'espace en général. Et c'était pas super évident avec les êtres humains, mais rappeler que nos bénévoles ont été un pas en avant et pas à pas dos comme s'il y avait un tableau ici, et comme s'il y avait un second réseau ici que qu'ils pourraient utiliser, parce que nous quelque part nécessaires pour fusionner ces gens. Nous ne pouvions pas les échanger en place. Donc, le tri par fusion levier plus d'espace, ce qui nous n'avons pas besoin de les autres algorithmes, mais l'avantage est que c'est beaucoup plus rapide. Et franchement, dans l'espace du monde réel ces RAM days--, disque dur space-- est relativement pas cher, et c'est donc pas nécessairement une mauvaise chose. 

Donc, nous allons jeter un coup d'œil, un peu plus méthodiquement, à ce que nous avons fait et pourquoi nous l'avons dit, il a été n log n. Voici donc les huit numéros et le huit bénévoles, nous avons eu la dernière fois. Et la première chose que Merge Trier nous a dit de faire, c'était quoi? PUBLIC: Diviser en deux. ENCEINTE 1: Dites à nouveau? PUBLIC: Diviser en deux. ENCEINTE 1: Diviser en deux, à droite. Cela rappelle de le livre de téléphone, de fracture et de conquérir plus généralement. Nous avons donc examiné la moitié gauche. Et puis une fois que nous avons dit, en quelque sorte la moitié gauche des éléments, qu'est-ce que nous disons prochaine? Trier la moitié gauche de la gauche moitié, ce qui nous a permis d', après avoir divisé en deux, se concentrer sur quatre et deux. 

Comment vous triez-vous une liste maintenant, dans jaune, de taille deux, en utilisant le tri par fusion? Eh bien diviser en deux, et trier la moitié gauche. Et c'est là que les choses Vous avez un petit brièvement stupide. Comment vous triez-vous une liste qui est de taille un, comme ce nombre quatre ici? Il est triée. Vous avez terminé. 

Mais alors comment voulez-vous trier une liste de taille un quand il est le numéro deux? Eh bien, la même chose, mais maintenant ce qui était la troisième et l'étape clé dans la fusion Trier? Vous avez eu à fusionner la gauche la moitié et la moitié droite. Et une fois que nous l'avons fait, nous avons examiné à quatre heures, nous avons examiné deux. Nous avons décidé de tout droit, de toute évidence deux vient en premier, nous avons donc mis deux dans son place, suivi par quatre. Et maintenant que vous avez à type de rembobinage, et c'est une sorte de caractéristique d'un algorithme comme Merge Trier, revenir en arrière dans la mémoire. Quelle était la ligne suivante de l'histoire? Que dois-je concentrerai sur la prochaine? La moitié droite de la gauche la moitié, qui est six et huit. 

Permettez-moi donc de suivre cet sans belaboring point trop. Six et huit ans, puis six est triés, huit sont triés. Les fusionner comme ça, et maintenant la prochaine grande étape est, bien sûr, trier la moitié droite de la première étape de cet algorithme. Donc, nous nous concentrons sur un, trois, sept, cinq. Nous nous concentrons alors sur la moitié gauche. La moitié gauche de ce que la moitié droite de que, puis fusionnent en un et trois. Ensuite, la moitié droite, puis à gauche la moitié de celui-ci, puis la moitié droite de celui-ci. Fusionner dans, et maintenant ce que l'étape reste? Fusionner la grande moitié gauche et la grande moitié droite, donc on va là-bas, puis deux, puis trois, puis quatre, puis cinq, puis six, puis sept, puis huit. 

Alors maintenant, pourquoi est-ce finalement révélateur, en particulier si n et logarithmes plus généralement assez vous échapper, au moins dans la mémoire récente? Eh bien, vous remarquerez la hauteur de cette chose. Nous avons eu huit éléments, et nous divisé par deux, par deux, par deux. Alors connectez base deux de huit nous donne trois. Et croyez-moi sur que si un peu brumeux sur ce point. Mais log base deux de huit est trois, de sorte que nous avons fait de trois couches de fusion. Et quand nous avons fusionné éléments, le nombre des éléments n'avons nous regardons sur chacune de ces lignes? Un total de n, non? Parce que de fusionner la rangée du haut, même si nous l'avons fait au coup par coup, nous avons finalement abordé chaque numéro une fois. Et dans la deuxième rangée, à fusionner les listes de taille deux, nous avons eu à toucher chaque élément une fois. Et puis ici vraiment clairement dans la dernière rangée, nous avons eu à toucher chacun de ces éléments une fois, mais une seule fois, si se trouve ici, alors, notre n log n. 

Et maintenant, juste pour rendre les choses un peu plus formel pour un instant, si vous étaient d'analyser maintenant ce à une sorte de niveau supérieur et essayer de décider, bien comment pourriez-vous aller à exprimer le temps d'exécution de cet algorithme juste en regardant et ne pas l'aide d'un exemple artificiel? Eh bien, combien de temps voulez-vous dire un étape de ce type en jaune faudrait, si n <2 retour? C'est un grand O de quoi? Donc, je vois un, donc une seule étape, peut-être à deux pas parce que c'est si puis revenir, mais c'est constante de temps, non? Alors nous avons dit O (1), et c'est comment je vais exprimer cela. T, soit juste le temps courir. n est la taille de l'entrée, si T (n), juste une façon élégante de dire le fonctionnement temps entrée donnée de taille n va être de l'ordre de la constante de temps, en O (1). 

Mais sinon, ce à ce sujet? Comment voulez-vous exprimer la temps de cette ligne jaune en cours d'exécution? T de quoi? Vous pouvez sorte de tricher ici et répondre à ma question de manière cyclique. Donc, si le temps d'exécution dans général, nous disons juste est T (n). Et maintenant, vous êtes sorte de barque ici et dire, eh bien, en quelque sorte la moitié gauche, puis trier la moitié droite. Comment pourrions-nous représenter symboliquement le temps d'exécution de cette ligne jaune? T de quoi? Quelle est la taille de l'entrée? n sur deux. Pourquoi dois-je vous dire que pas? Et alors c'est un autre T (n / 2), puis encore une fois, si je fusionne deux moitiés triées, le nombre d'éléments que je vais avoir à toucher au total? n. Donc, je peux exprimer ce, juste pour être une sorte de fantaisie, comme le temps d'exécution en général. T (n) est juste le temps d'exécution de T (n / 2), ainsi que T (n / 2), moitié gauche et la moitié droite, en plus O (n), qui est probablement n étapes, mais peut-être, si je suis en utilisant deux doigts, c'est deux fois plus nombreux étapes, mais il est linéaire. C'est un certain nombre de mesures c'est un facteur de n, afin que nous puissions exprimer ce que cela. Et c'est là que nous allons maintenant botté de dégagement à l' arrière de notre manuel de mathématiques de lycée nous sommes en fin de compte que la récurrence finit par égaler ce, n log n fois, si vous faites réellement sur les mathématiques de façon plus formelle. 

C'est donc seulement deux points de vue. Une numériquement avec un codé en dur exemple représentatif l'aide de huit chiffres, et un plus aperçu général de la façon dont nous y sommes arrivés. Mais ce qui est vraiment intéressant ici est, de nouveau, cette notion de cyclisme. Je n'utilise pas de boucles. Je suis une sorte de définition quelque chose en termes de lui-même, non seulement avec ce fonction mathématique, mais aussi en termes de ce code pseudo. Ce pseudo-code est récursive en ce que deux de ses lignes est essentiellement lui disant d'aller utiliser elle-même pour résoudre un petit problème de plus petite taille, et puis encore et encore et encore jusqu'à ce que nous rogner il jusqu'à ce que l'on appelle cas de base. 

Donc, nous allons effectivement tirer un plus convaincant à emporter de cette manière suivante. Laissez-moi aller dans gedit et prends un examiner certaines de code source d'aujourd'hui, en particulier cet exemple ici. Sigma 0, ce qui ajoute apparemment les numéros un à n. Voyons donc ce qui est familier et inconnu ici. D'abord, nous avons un couple de comprend, donc rien de nouveau. Prototype. Je suis un peu brumeux sur ce après quelques jours, mais qu'est-ce que nous disons une prototype d'une fonction est? PUBLIC: [inaudible]. ENCEINTE 1: Qu'est-ce que c'est? PUBLIC: Nous annonçons. ENCEINTE 1: Nous annonçons. Donc, vous enseignez Clang, hé, pas réellement mise en œuvre de cette encore, mais quelque part dans ce dossier, sans doute, va être une fonction appelée quoi? Sigma. Et ce n'est que la promesse que ça va ressembler à ceci. Il va prendre un entier comme input-- et je peux être plus explicite et dire int n --et c'est va retourner un int, mais les moyens virgules, mm, je vais contourner à la mise en œuvre un peu plus tard. Encore une fois, Clang est muet. Il va seulement de savoir ce que vous lui dites de haut en bas, Nous devons donc donner au moins un soupçon de ce qui est à venir. 

Maintenant regardons principal ici. Disons faites défiler ici et voir ce principal est fait. C'est pas si longtemps d'une fonction, et en fait, la construction ici est familier. Je déclare une variable n, puis Je harceler l'utilisateur encore et encore pour un nombre entier positif en utilisant getInt, et que la sortie de cette boucle fois que l'utilisateur s'est conformé. Alors que faire, nous avons utilisé pour harceler l'utilisateur de cette façon. Maintenant, ce qui est intéressant. Je déclare un int appelé «réponse». Je lui attribuer la valeur de retour d'une fonction appelée «sigma». Je ne sais pas ce que cela fait encore, mais Je me souviens de déclarer il ya un instant. Et puis je suis de passage dans la valeur que l'utilisateur a tapé dans, n, puis-je signaler la réponse. Eh bien nous allons revenir en arrière pour un instant. Allons de l'avant dans ce répertoire, assurez- sigma 0, et fait exécuter ce programme et voir ce qui se passe. Donc, si je vais de l'avant et l'exécution ce programme, ./sigma-0, et je tape dans un esprit positif entier comme deux, Sigma, comme le symbole grec l'indique, est juste aller à additionner tous les nombres de zéro à un maximum de deux. Donc 0 plus 1 plus 2. Ce qui devrait, espérons-donnez-moi 3. C'est tout ce qu'il fait. Et de même, si je lance ce message et je lui donne le numéro trois, c'est 3 plus 2, de sorte que c'est 5, plus 1 devrait me donner 6. Et puis si je suis vraiment fou et commencez à taper en plus grand nombre, il devrait me donner sommes de plus en plus grandes. Donc, c'est tout. 

Alors qu'est-ce sigma ressemble? Eh bien, c'est assez simple. C'est la façon dont nous pourrions avons mis en place ce pour les deux dernières semaines. "Int" va être le type de retour. Sigma est le nom, et il faut une variable m au lieu de n. Je vais changer que là-haut. Ensuite, c'est juste un test de cohérence. Nous verrons pourquoi dans un instant. Maintenant, je déclare une autre variable, somme, l'initialiser à zéro. Puis j'ai cette boucle For itération, apparemment pour plus de clarté, de i = 1 sur un maximum de un = m, ce qui est quel que soit l'utilisateur a tapé dans, et puis je incrémenter la somme comme ça. Et puis retourner la somme. 

Alors quelques questions. Un, je demander à mon commentaire que ce évite le risque d'une boucle infinie. Pourquoi les passant dans un nombre négatif induire, potentiellement, une boucle infinie? 

PUBLIC: Vous ne serez jamais atteindre m. 

ENCEINTE 1: Ne jamais atteindre m. Mais m est passé, donc nous allons Prenons un exemple simple. Si m est transmise par la utilisateur comme un négatif. Indépendamment du principal. Principal nous protège des ce trop, donc je suis juste être vraiment anal avec sigma aussi s'assurer que l'entrée ne peut pas être négatif. Donc, si m est négatif, quelque chose comme un négatif. Qu'est-ce qui va se passer? Eh bien, je va s'initialiser à un, et puis je va être inférieur ou égal à m? 

Etre prêt. C'est était-- de laissez pas, nous allons Nix cette histoire. Je n'ai pas posé cette question, parce que le risque que je fais allusion à ne va pas se produire parce que i est va toujours être plus grande OK than--, Je retire cette question. Dáccord. Concentrons-nous uniquement sur cette partie ici. Pourquoi ai-je déclare une certaine à l'extérieur de la boucle? Avis sur la ligne 49, je n'ai i déclaré à l'intérieur de la boucle, mais en ligne 48 j'ai déclaré un peu en dehors. Ouais. PUBLIC: [inaudible]. ENCEINTE 1: Bien sûr. Alors d'abord et avant tout, je n'ai certainement pas vouloir déclarer et initialiser somme de zéro à l'intérieur de la à chaque itération de boucle, parce que ce serait contraire clairement la but de résumer les chiffres. Je voudrais continuer à changer la valeur à zéro. Et aussi, ce qui est une autre plus mystérieux raison de cette même décision de conception? Ouais. 

PUBLIC: [inaudible]. ENCEINTE 1: Exactement. Je veux accéder à l'extérieur de la boucle trop sur quelle ligne? Sur 53. Et sur la base de notre règle d'or il ya un couple de conférences, les variables ont une portée limitée, vraiment, à la accolades qui les englobent. Donc, si je ne déclare pas la somme à l'intérieur de ces accolades extérieures, Je ne peux pas l'utiliser dans la ligne 53. En d'autres termes, si je déclarais somme ici, ou même au sein de la Pour la boucle, je ne pouvais pas accéder à 53. La variable serait effectivement disparu. Ainsi, un certain nombre de raisons là. Mais maintenant revenons et voir ce qui se passe. Donc sigma est appelé. Il ajoute une plus 2 ou 1 + 2 plus 3, puis renvoie la valeur, stocke dans la réponse, et printf ici C'est pourquoi je vois sur l'écran. Donc, c'est ce que nous appellerons un processus itératif approche, où itération juste des moyens à l'aide d'une boucle. Une boucle For, une boucle While, un Do While boucle, juste faire quelque chose de nouveau et encore et encore. 

Mais sigma est une sorte de fonction propre dans que je pouvais mettre en œuvre différemment. Que dire de ce qui juste pour être plutôt cool, permettez-moi de me débarrasser vraiment de beaucoup de distraction parce que cette fonction est vraiment très simple. Passons en rogner le bas juste à ses quatre principaux et se débarrasser de tous les commentaires et accolades. C'est en quelque sorte d'un époustouflant mise en œuvre alternative. D'accord, peut-être pas vous tourner la tête, mais c'est le genre de sexy, tout droit, regarder cette tellement plus succinctement. Avec seulement quatre lignes de code, Je dois d'abord ce test de cohérence. Si m est inférieur ou égal à zéro, sigma n'a pas de sens. C'est seulement censé être en ce cas pour les nombres positifs, donc je vais juste retourner zéro arbitraire de sorte que nous avons au moins certains soi-disant cas de base. 

Mais voici la beauté. L'intégralité de cette idée, en ajoutant le nombres de 1 à n, m ou, dans ce cas, peut être fait par type de renvoyer la balle. Eh bien, ce qui est la somme de 1 à m? Eh bien, vous savez quoi? C'est la même que la somme de m plus la somme de 1 et m ± 1. Eh bien, vous savez quoi? Quel est le sigma m moins 1? Eh bien, si vous suivez ce genre de logiquement, c'est le même que m moins 1 ainsi sigma m moins 2. Ainsi, vous pouvez sorte de just-- c'est comme, si vous êtes juste essayer de déranger un ami et ils vous posent une question, vous sorte de répondre à une question, vous pouvez sorte de garder renvoyer la balle. Mais ce qui est essentiel, c'est que si vous continuez à faire la question plus en plus petits et plus petit, vous êtes ne demande pas ce qui est sigma de n, ce qui est le sigma n, ce qui est de sigma n? Vous vous demandez ce qui est sigma de n, ce qui est sigma de n moins 1, ce qui est le sigma n moins 2? Finalement, votre question va devenir quoi? Qu'est-ce que sigma d'un ou zéro, de très faible valeur, et dès que vous obtenir, votre ami, vous n'allez pas demander la même question, vous allez juste de dire, oh c'est zéro. Nous avons terminé la lecture de ce type de jeu cyclique stupide. 

Donc, la récursivité est l'acte dans la programmation d'une fonction qui se fait appeler. Ce programme, lorsqu'il est compilé et exécuté, est va se comporter exactement de la même manière, mais ce qui est important est que l'intérieur d'une fonction appelée sigma, il ya une ligne de code dans laquelle nous nous appeler, qui devrait normalement être mauvais. Par exemple, si j'ai compilé ce, alors assurez-sigma-- faire sigma 1 ./sigma-1. Entier positif, s'il vous plaît, 50 1275. Alors quelle est la fonction semble être, basée sur un test, correct. Mais que faire si je suis un peu dangereux et supprimer l'affaire dite de base, et je dis juste, eh bien je fais juste ce plus compliqué que ça. Disons simplement calculer la sigma m et en prenant ensuite l'ajout d' dans sigma m moins un? Eh bien, qu'est-ce qui va se passer ici? Voyons un zoom arrière. Disons recompiler le programme, enregistrer, recompiler le programme, et alors prêt ./sigma-1 zoom avant, entrer entier positif s'il vous plaît, 50. Combien d'entre vous sont prêts à coupé sur place de voir ça? 

Dáccord. Donc cela peut se produire pour un certain nombre de raisons, et franchement cette semaine, nous sommes sur le point de vous donner plus d'eux. Mais dans ce cas, essayez de raisonner à l'envers ce qui serait arrivé ici? Segmentation fault, nous dit la dernière temps, se réfère à un segment de mémoire. Quelque chose de mauvais s'est passé. Mais ce qui était il mécanique qui a mal tourné ici en raison de mon déménagement de cette affaire dite de base, où je suis retourné une valeur codée en dur? Que pensez-vous allé mal? Ouais. 

PUBLIC: [inaudible]. ENCEINTE 1: Ah. Bonne question. Ainsi, la taille du nombre que je résumant devenu si grand qu'il dépasse la taille de l'espace de mémoire. Bonne idée, mais pas fondamentalement va causer un accident. Cela pourrait provoquer un débordement entier, où les bits seulement se renversent puis nous prenons un très gros nombre de comme un nombre négatif, mais que lui-même ne sera pas causer un accident. Parce que, à la fin de l' jour un int est toujours de 32 bits. Vous n'allez pas accidentellement voler un peu 33e. Mais une bonne pensée. Ouais. 

PUBLIC: [inaudible]. ENCEINTE 1: La méthode ne cesse de courir, et en effet il se dit à nouveau et encore et encore et encore et encore une fois, et aucun des ces fonctions jamais terminer parce que leur seule ligne de code appelle encore et encore themself et de nouveau. Et ce qui est vraiment se passe ici, et maintenant nous peut sorte de tirer cette imagée. Permettez-moi de passer à un image pour un instant. Il s'agit d'une image, que finira étoffer plus en détail, de ce qui se passe l'intérieur de la mémoire de votre ordinateur. Et il se trouve que sur le fond de cette image est quelque chose qui s'appelle la pile. Il s'agit d'un morceau de mémoire, un morceau de RAM, c'est juste utilisé tout moment une fonction est appelée. Chaque fois que vous, un programmeur, appeler une fonction, le système d'exploitation, comme Mac OS, Windows ou Linux, attrape un tas d'octets, peut-être un quelques kilo-octets, peut-être quelques mégaoctets de la mémoire, les remet à vous, et vous permet alors vous exécutez votre fonction à l'aide que les variables qui vous avez besoin. Et si vous établissez une autre fonction et une autre fonction, vous obtenez une autre tranche de mémoire et une autre tranche de mémoire. 

Et en effet, si ces plateaux verts de Annenberg représenter que la mémoire, voici ce qui arrive le premier fois que vous appelez la fonction sigma. C'est comme mettre un plateau comme celui-ci sur ce qui est d'abord une pile vide. Mais alors, si ce bac appelle lui-même, pour ainsi dire, appeler un autre exemple de sigma, c'est comme demander au système d'exploitation, ooh, besoin d'un peu plus de mémoire, donnez-moi cela. Et puis il se empilés sur le dessus. Mais ce qui est important ici est que le premier plateau est toujours là, car il a invoqué ce deuxième plateau. Maintenant, quant à lui, appellent sigma sigma, c'est comme demander plus de mémoire. Obtient empilés sur ici. sigma appeler sigma, c'est une autre plateau qui obtient empilés sur ici. Et si vous continuez à faire cela, éventuellement, type de carte ce visuel à ce tableau, ce qui se passe à produire avec la pile de plateaux? Il va dépasser le montant de la mémoire de votre ordinateur a. Et dès que ce bac vert dépasse la ligne horizontale ci-dessus et ci-dessus pile ce mot tas, qui nous y reviendrons à l'avenir, c'est une mauvaise chose. Le tas est un autre le segment de mémoire, et si vous laissez ce plateaux pile et pile sur, vous allez dépasser votre propre segment de mémoire, et un programme est en effet va s'écraser. 

Maintenant, en passant, cette idée de récurrence, par conséquent, peut clairement entraîner des problèmes, mais ce n'est pas nécessairement une mauvaise chose. Parce envisager, après tout, et peut-être how-- cela prend un certain temps pour s'y habituer à --Comment élégante ou la simplicité que la mise en œuvre de sigma était. Et nous n'allons pas utiliser récursion tant que ça en CS50, mais dans CS51, et vraiment toute catégorie où vous manipuler des structures de données comme des arbres ou des arbres de la famille, qui ont une certaine hiérarchie, c'est super, super utile. Maintenant, en passant, de sorte que vous comme aspirant des informaticiens sont familiers avec certains de Google l'intérieur des blagues, si vous allez sur Google et vous regardez ce qui est le définition de, disons, la récursivité, entrez. Uh-huh. En passant, je me suis arrêtée un peu. Ce fut comme 10 minutes de procrastination ce matin. Si vous aussi vous Google "de travers" avis en inclinant votre tête slightly-- puis celui-ci est peut-être plus atroce de tous puisque quelqu'un a passé comme leur journée la mise en œuvre de cette ago-- quelques années à venir. Oh, wait-- c'est un bug. 

Ainsi, en cours d'exécution sur l'un des plus grands sites mondiaux sont ces stupides petits œufs de Pâques. Ils consomment probablement une nombre non négligeable de lignes de code juste pour que nous puissions avoir petites choses amusantes comme ça. Mais au moins maintenant vous avez certaines de ces blagues. 

Maintenant, nous allons jeter un oeil à quelques-uns des White Lies nous avons dit à la fin, et commencer à décoller certaines couches techniquement afin que vous compreniez vraiment ce qui se passe et vous pouvez comprendre certaines des menaces, comme Shellshock, que ont maintenant commencé à devenir à la pointe de tout le monde est attention, au moins dans les médias. Voici donc une fonction très simple qui renvoie rien, vide. Son nom est swap. Il faut à deux variables et il ne renvoie rien. Prend en a et b. Donc, une démonstration rapide. Nous avons fait cela en compte. Nous pourrions aussi bien prendre un peu de briser ici pendant un moment et avoir un petit quelque chose à boire. Si quelqu'un ne me dérangerait pas de rejoindre moi ici pendant un moment. Que diriez-vous de la chemise marron? Venez sur place. Juste celle d'aujourd'hui. Merci, cependant. Très bien, et nous avons venir qui ici? Quel est votre nom? 

ENCEINTE 4: Laura. 

ENCEINTE 1: Laura. Venez sur place. Donc, Laura, très simple défi aujourd'hui. Nice yo répondre. Bien. Donc, nous avons un peu de lait ici et nous avons un peu de jus d'orange ici et des tasses qu'on emprunté à Annenberg aujourd'hui. 

ENCEINTE 4: Borrowed. ENCEINTE 1: Et aller de l'avant et vous donner un demi-verre de ce. Bien. Et nous allons vous donner la moitié un verre de lait. Oh, et juste afin que vous puissiez rappelez-vous ce que c'était, Je me suis souvenu d'apporter cette place et aujourd'hui. Bien. Si vous le voulez bien, nous allons voir, nous peut les mettre sur vos propres lunettes si vous voulez. Ce sera le monde dans les yeux de Laura. Bien. Donc, votre objectif, étant donné deux tasses de liquide ici, le lait et le jus d'orange, est permuter les deux contenus de sorte que la jus d'orange va dans la tasse de lait et le lait va dans la coupe du jus d'orange. 

ENCEINTE 4: Est-ce que je reçois une autre tasse? ENCEINTE 1: Je suis tellement content que vous posiez, si il aurait été beaucoup mieux de vidéos si vous n'aviez pas demandé. Mais oui, nous pouvons vous offrir un troisième tasse qui est vide, bien sûr. Bien. Donc échange de contenu là-bas. Très agréable. Très bon. Vous faites cela remarquablement bien. Et la troisième étape. Bien. Excellente. Une salve d'applaudissements serait bon pour Laura. Bien. Nous avons un petit cadeau d'adieu pour vous, mais permettez-moi de prendre ces. Merci beaucoup. Ainsi, un exemple simple, si, de démontrer que si vous faites vouloir échanger le contenu de deux récipients, ou appelons-les les variables, vous avez besoin de stockage temporaire de mettre en scène l'un des contenus dans la que vous pouvez réellement faire l'échange. Donc, en effet, le code source de ici en C est représentatif de exactement cela. Si le jus d'orange a une et le lait était b, et nous voulions échanger les deux, vous pouvez essayer quelque chose de créatif en versant une dans l'autre, mais qui ne serait pas probablement fin particulièrement bien. Et si nous utilisons une tasse troisième appel il tmp, T-M-P, par convention, et mettre le contenu de la JO de cela, alors échanger une tasse, puis mettez le dans le JO tasse d'origine, ainsi la réalisation, exactement comme Laura fait, le swap. 

Donc, nous allons faire exactement cela. Permettez-moi d'aller de l'avant et ouvrir jusqu'à un exemple qui est réellement appelé «non échanger, "parce que ce n'est pas comme un simple fait que vous pourriez penser. Donc, dans ce programme, vous remarquerez que J'utilise stdio.h, notre vieil ami. J'ai le prototype pour le swap là-haut, qui des moyens de sa mise en œuvre probablement vers le bas ci-dessous, et voyons ce que ce principal programme va faire pour moi. J'ai d'abord déclare int x obtient un, et int y obtient deux. Alors, pensez à ceux que JO et du lait, respectivement. Et puis j'ai juste un printf dire x est ce et y est présent, juste pour que je puisse voir visuellement ce qui se passe. Puis j'ai printf prétendant que je échangeant les deux, puis-je imprimer une affirment qu'ils sont échangés, et j'imprime x et y de nouveau. Donc, ici, dans swap est exactement ce que Laura a fait, et exactement ce que nous avons vu sur l'écran il ya un instant. 

Donc, nous allons aller de l'avant et être cruellement déçus. Ne faites pas d'échange, et de fonctionner sans swap, zoom sur la sortie ici. Entrez x est 1, y est 2, l'échange échangé. x est toujours 1, et y est toujours 2. Ainsi, même si, franchement, cela ressemble voulez exactement, mais techniquement plus, ce Laura fait, ne semble pas fonctionner. Alors, pourquoi est-ce? Eh bien, il s'avère que lorsque nous écrivons un programme comme celui-ci qui a à la fois principal, mis en évidence ici, puis une autre fonction, comme swap, mis en évidence ici, qui il appelle, le monde regarde un petit quelque chose comme ces plateaux il ya un moment. Lorsque principale première est appelée, c'est comme si on demandait système d'exploitation pour un peu de mémoire pour toute locale variables telles que x et y qui a principale, et ils finissent là. Mais si les appels principaux échanger, et principal passe à échanger deux arguments, a et b, jus d'orange et le lait, ce n'est pas comme remettre le jus d'orange et le lait à Laura. Quel ordinateur fait, est-il transmet des copies du jus d'orange et des copies de lait de Laura, de sorte que ce qui est en fin de compte à l'intérieur de ce bac est celui de la valeur et de deux, ou JO et le lait, mais des copies de celui-ci, de sorte que, à ce stade dans l'histoire, il est JO et le lait dans chacun de ces plateaux. Il ya un et un deux dans chacun de ces bacs, et la fonction de permutation travaille en effet. C'est les échanger à l'intérieur du second plateau le plus élevé, mais que la permutation n'a pas d'impact. Et sur la base de quelques-uns principe de base que nous avons parlé avant, et même il ya quelques minutes, ce qui pourrait expliquer pourquoi le changement a et b à l'intérieur de swaps n'a pas d'effet sur x et y, alors que Je passai x et y à la fonction d'échange. Quel est le mot clé ici que pourrait expliquer simpliste? Je pense que je l'ai entendu ici? PUBLIC: Retour. ENCEINTE 1: Retour? Ne reviendra pas. Allons avec une autre. Qu'est ce que c'est? 

PUBLIC: [inaudible]. 

ENCEINTE 1: OK, donc nous avons pu return-- rendre le travail de retour dans l'histoire, mais il ya une explication encore plus simple. PUBLIC: Champ d'application. ENCEINTE 1: Champ d'application. Je prends portée. Donc portée, se rappeler où notre x et y déclarés. Ils sont déclarées à l'intérieur de principal droit ici. a et b, en attendant, sont effectivement déclarée l'intérieur de swap, pas tout à fait les accolades, mais encore dans le domaine général de swap. Et en effet, a et b exister que dans ce bac de Annenberg, ce deuxième morceau de code. Donc, nous sommes en effet modifier la copie, mais ce n'est pas vraiment tout ce qui utile. 

Donc, nous allons jeter un oeil à ce niveau un peu plus bas. Je vais retourner dans le répertoire source, et je vais d'abord agrandir ici, et juste pour confirmer que je suis dans ce plus grande fenêtre de terminal, le programme est toujours comporter comme ça. Supposons maintenant que cette n'est pas intentionnelle. Il est clair que je voulais échange de travail, il se sent comme un bug. Maintenant, je pourrais commencer à ajouter un beaucoup de printf du à mon code, imprimer x ici, y sur ici, un ici, b ici. Mais franchement, c'est probablement ce que vous avez fait pour un couple de semaines maintenant, aux heures de bureau et à la maison lorsque vous travaillez sur psets essayer de trouver quelques bugs. Mais vous verrez, si vous n'avez pas déjà, ce problème réglé trois vous présente à une commande appelée GDB, où GDB, GNU débogueur, lui-même a tout un tas de caractéristiques qui peuvent effectivement laissez-nous comprendre les situations comme ça, mais plus convaincante, résoudre les problèmes et trouver des bogues. Donc, je vais le faire. Au lieu de ./noswap, je suis à la place va courir GDB ./noswap. En d'autres termes, je vais courir ma programme pas dans Bash, notre nouvel ami aujourd'hui. Je vais courir mon programme NOSWAP l'intérieur de cet autre programme appelé GDB, un débogueur, qui est un programme qui est conçu pour aider Vous les humains trouver et supprimer les bugs. Donc, si je frappe exécuter ici, il n'y a un montant atroce de texte que vous avez vraiment jamais à lire. Il s'agit essentiellement d'une distraction partir de l'invite, qui Je vais frapper Control-L pour obtenir au sommet il. C'est l'invite GDB. Si je veux exécuter ce programme maintenant, comme ce petit aide-mémoire sur aujourd'hui diapositive indique, Run est le premier commandes que nous voulions présenter. Et je vais juste à taper courir ici à l'intérieur de GDB, et en effet il a couru mon programme. Maintenant, il ya un certain supplémentaires sorties de l'écran comme celui-ci, mais c'est juste GDB étant anal et nous dire ce qui se passe. Vous n'avez pas vraiment à vous soucier sur ces détails pour le moment. Mais ce qui est vraiment cool GDB, si je fais ce again-- Control-L efface le screen-- Let Me Go de l'avant et de type "briser principal," ce qui, lorsque je tape sur Entrée, ce qui est la mise en appelé point à noswap.c de pause, ligne 16, qui est l'endroit où GDB compris mon programme fait est, ma fonction est en réalité. C'est ce que nous allons ignorer pour l'instant mais c'est l'adresse dans la mémoire de cette fonction spécifique. Alors maintenant, quand je saisir run, remarquer ce qui est cool ici. Mon programme se brise sur la ligne I dit GDB à suspendre l'exécution à. Donc, je n'ai pas à changer maintenant mon code, ajouter des printf de, recompiler, reprise il, changer, ajouter des printf de, enregistrer, recompiler, exécutez-le. Je peux encore marcher dans mon programme étape par étape par étape à vitesse humaine, pas au type Intel à l'intérieur de la vitesse. 

Alors maintenant remarquer cette ligne apparaît ici, et si je reviens à mon programme dans gedit, Remarquons que c'est fait la première ligne de code. Il ya la ligne 16 de gedit. Il ya la ligne 16 dans GDB, et même si cette interface en noir et blanc est loin d'être aussi utilisateur amical, cela signifie que la ligne 16 n'a pas été exécutée encore, mais il est sur le point de l'être. Donc, en effet, si je tape impression x, pas printf, juste print x, Je reçois une certaine valeur faux il de zéro, car x n'a pas encore été initialisé. Donc, je vais taper à côté, ou, si vous vouloir être de fantaisie, juste pour N prochaine. Mais quand je tape suivante entrer, maintenant remarque il passe à la ligne 17. Donc, logiquement, si j'ai exécuté ligne 16 et je tape maintenant print x, que dois-je voir? One. 

Et maintenant, ce n'est certes déroutant. $ 2 est juste une façon élégante de, si vous vous référer à cette valeur plus tard, vous pouvez dire «dollar signer deux." C'est comme une référence arrière. Mais pour l'instant, juste l'ignorer. Ce qui est intéressant est ce qui est sur la droite du signe égal. Et maintenant, si je tape prochaine fois et print y, je devrais voir 2. Je peux aussi maintenant imprimer x fois, et franchement, si je suis un peu confus quant à où je suis, je peux liste pour le type de liste et juste voir un peu de contexte autour le point que je suis en fait à. Et maintenant, je peux taper suivante, et x est égal à 1. Maintenant je tape suivante. Oh, y est 2. Et encore une fois, il est source de confusion, car la sortie de GDB est mélangé avec ma propre production. Mais si vous gardez à l'esprit, par en regardant en arrière à votre code ou posant sur côté de l'autre peut-être, vous aurez vois que vraiment je suis juste pas à pas dans mon programme. 

Mais remarquez ce qui se passe à côté, littéralement. Voici la ligne 22. Laissez-moi aller sur elle, déplaçant ainsi sur à 23, et si j'imprime x maintenant, encore un. Et si je y imprimer maintenant, encore un. Ce n'est donc pas un exercice utile. Donc, nous allons refaire cela. Permettez-moi de revenir à la dessus et tapez run nouveau. Et c'est dire le programme que cela en cours de débogage a déjà commencé, commencé dès le début. Oui, nous allons le faire à nouveau. Et cette fois, nous allons faire ensuite, Suivant, Suivant, Suivant, Suivant, mais maintenant les choses deviennent intéressantes. Maintenant, je veux entrer dans swap, donc je ne tape pas à côté. Je tape pas, et maintenant le remarquer m'a sauté à la ligne de noswap.c 33. Si je reviens à gedit, ce qui est la ligne 33? C'est la première réelle ligne de code à l'intérieur de swap. Ce qui est bien, parce que maintenant je peux type de fouiller et obtenir curieux à ce qui se passe vraiment là-dedans. Permettez-moi imprimer tmp. Whoa. Pourquoi ne tmp ont une certaine fou, la valeur des ordures faux? PUBLIC: Il n'a pas été initialisé. ENCEINTE 1: Il n'a pas été initialisé. Et en effet, lorsque vous exécutez un programme, vous êtes donné tout un tas de mémoire par le système d'exploitation, mais vous n'ont pas initialisé toutes les valeurs, donc tout ce que vous êtes morceaux voir ici, même si c'est ce grand point négatif fou nombre, signifie simplement que ce sont les restes de certains usages précédente de cette RAM, même si je n'ai pas me faut il encore. Alors maintenant, je vais aller de l'avant et le type prochaine, et si je tape maintenant imprimer tmp, que dois-je voir? Quelle que soit la valeur d'un été, un est le premier argument, juste comme x a été le premier chose qui est transmis, si a et x doivent être les mêmes, donc imprimer tmp devrait me imprimer un. 

Donc, ce que vous verrez dans le jeu de problème trois est un tutoriel de toutes sortes sur GDB, mais se rendent compte que c'est le début d'un coup d'œil à un outil qui sera effectivement vous aider à résoudre les problèmes de manière beaucoup plus efficace. Ce que nous sommes en fin de compte va faire le mercredi est de commencer à éplucher quelques couches et enlever des roues de formation. Cette chose appelée chaîne nous avons utilisé pendant un certain temps, nous allons prendre lentement que l'écart de vous et de commencer à parler de quelque chose de plus ésotérique connu en tant que char *, mais nous allons faire cette belle et d'abord doucement, même si des pointeurs, comme on les appelle, peuvent faire des très mauvaises choses si on en abuse, en regardant un peu de pâte à modeler de notre ami Nick Parlante de Stanford Université, un professeur en informatique la science qui mis ensemble cet aperçu de ce qui est à venir ce mercredi. 

[VIDEO LECTURE] Hé, Binky. Réveillez-vous. Il est temps pour pointeur plaisir. 

-Quel Ce que c'est? En savoir plus sur les pointeurs? Oh, Goody! [FIN LECTURE VIDÉO] ENCEINTE 1: ce qui vous attend le mercredi. Nous vous verrons alors. [VIDEO LECTURE] -Et Maintenant, pensées profondes, par Daven Farnham. 

-Pourquoi Nous apprennent C? Pourquoi ne pas A +? 

[Rires] 

[FIN LECTURE VIDÉO]