[Musik zu spielen] Sprecher 1: Alles klar, das ist CS50, und dies ist der Beginn der vierten Woche, Und wie Sie vielleicht gehört haben oder zu lesen, hat sich die Welt wurde zu Ende. Gehen rund um das Internet wurde Wissen und Bewusstsein eines Fehlers in einem Programm, ein Programmiersprache namens Bash. Dies wurde wunderbar Marken wie Shellshock oder der Bash-Tür, aber Artikel wie diese waren nicht selten. Und in der Tat sind viele von ihnen bringen Erinnerungen an Heartbleed, die Sie in die bemerkt haben drücken Sie wieder im vergangenen Frühjahr, die war ebenfalls ziemlich dramatisch. Nun die von Ihnen hier heute, wie viele von Ihnen haben, auch wenn Sie nicht verstehen, was es ist alles über, von Shellshock gehört? Alles klar, und wie viele von euch haben Computer, die anfällig sind? OK, sollte es viel, viel mehr Hände sein bis jetzt, aus Gründen, die wir sehen werden. Lassen Sie uns einen Blick an, was nun schon in den Medien und dann erklären, es ein bisschen hier für uns technisch. Sprecher 2: Sicherheitsexperten haben warnte davor, dass ein schwerwiegender Fehler könnte etwa, um Hunderte von Einfluss Millionen der weltweit Surfer. Also, was genau ist der Fehler, der gewesen ist Shellshock genannt, und was tut sie? Nun, Shellshock ist auch bekannt als die Bash Fehler, die Software nutzt es. Hacker nutzen das Virus zu scannen anfällig Systeme mit Linux und Unix Betriebssysteme und dann zu infizieren. Bash ist ein Kommandozeilen-Shell. Dadurch können Benutzer Befehle an starten Programme und Funktionen in Software durch Eingabe von Text. Es ist in der Regel von Programmierern verwendet, und sollten nicht geöffnet werden, um den Rest der Welt, obwohl Shellshock ändert, dass. Nun, worringly einige Analysten warnen, es könnte ein größere Bedrohung sein, weil Shellshock ermöglicht die vollständige Steuerung von einer infizierten Maschine, wohingegen Heartbleed nur erlaubt, Hacker auf Computer auszuspionieren. Es ist so ernst, es ist wurde eine 10 bewertet von 10 für die Schwere von der National Vulnerability Database. 3.2 aller Web-Server sind bei Risiko, darunter auch einige Mac-Computern. Nun, stellen Sie sicher, Ihre Systeme zu patchen jetzt. Jeder Hosting einer Website läuft die betroffenen Betriebssysteme sollten Maßnahmen so bald wie möglich erfolgen. Wer es sich leisten kann sollte es aussehen zu deren Überwachung und Web-Anwendung Firewalls, um für etwaige Angriffe achten. SPRECHER 3: Das Schlimmste passieren könnte ist, dass jemand Code schreiben, dass würde automatisch gehen und scannen das Internet und beeinflussen würden alle Rechner. Und wenn sie das tun, gut, das Schlimmste, was sie tun könnten, ist einfach alles zu löschen, oder herunter die Seiten nach unten. So konnten wir sehen, Schaden von diesem Punkt aus gesehen, wo wir böswillige Menschen haben , die nur entscheiden, um Chaos verursachen indem Systeme nach unten oder Löschen Dateien und solche Dinge. Sprecher 2: Einige sagen, das ist eine der am schwierigsten zu mess Fehler in Jahren, und es kann Wochen dauern oder sogar Monate, um festzustellen, seine endgültige Wirkung. Sprecher 1: Also all das ist wahr, aber der Spass an der Sache ist, die fast alle der Bilder die Sie gerade gesehen haben, außer vielleicht der Tastatur, hat nichts damit zu tun, der Fehler auch immer. Server und Leitungen usw., Es ist eine Art tangential bezogen, aber im Kern ist es eigentlich ziemlich vertraut, was ist denn hier los. In der Tat, lassen Sie mich in zu gehen unsere CS50-Appliance. Lassen Sie mich gehen Sie vor und maximieren das Terminal-Fenster hier. Und euch habe mit diesem, oder die Embedded-Version davon, in gedit, um Programme zu schreiben, Befehle eingeben kann, und so weiter, und dies ist tatsächlich, und hat seit Wochen, Bash, B-A-S-H. Dies ist die Bourne-again shell, Das ist nur eine andere Art zu sagen, Dies ist ein Programm, das eine hat blinkt Aufforderung effektiv, dass sitzt da und wartet für die Eingabe für Sie. Und es ist der Befehl Zeilenschnittstelle, über die Sie Jungs haben läuft Befehle und schließlich der Zusammenstellung und dann läuft Programme. Aber ist auch ein Bash-Programmierung Sprache im folgenden Sinn. Sie wissen, dass es Befehle wie cd und ls und auch klirren und andere, aber Sie können Ihre eigene Befehle definieren durch Umsetzung in Bash. Jetzt sind wir es nicht gewohnt, gehen sehr ins Detail um die Programmiersprache Bash, aber weiß zum Beispiel, dass in dem Moment, es gibt keinen Befehl namens "Hallo." So kann gefunden werden, eines dieser Pakete. Es ist nicht auf meinem Computer installiert. Fragen Sie Ihren Administrator. Aber wenn ich es, ein Programm zu sein, als "Hallo" in der Bash oder auf meine Aufforderung, Ich kann tatsächlich nutzen Syntax Das ist ganz wie C. Es ist nicht ganz das gleiche, aber es ist ziemlich ähnlich sieht ein Funktion, wenn auch einige Details fehlen. Nichts scheint zu geschehen, aber jetzt, wenn ich schreibe "Hallo" Sie können tatsächlich schreib eine Programm, nicht in C, nicht in Java, nicht in einer anderen Programmiersprache Sprache, aber in der Bash selbst. Jetzt ist hier der Schlüssel, dass ich schrieb der Name, den ich wollte diesen neuen Befehl zu geben, und die Klammern sind auch Symbolisch dafür eine Funktion. Nebenbei können Sie auch Spaß machen Dinge, und in der Tat, auch auf Mac OS, Dies ist ein Programm namens Klemme. Es kommt in jeder der integrierten Computer, der einen Mac in diesem Raum hat, und Sie ähnliche Dinge in Mac tun können OS, aber Sie können mehr darüber hinausgehen. Und das ist ein wenig tangential, aber es ist eine Art von Spaß. Ich wurde heute Morgen daran erinnert, wenn man dies durch, von einem kleinen Spiel, das ich verwendet, um zu spielen mit einem der CS50 ehemaligen TFs wobei jede Mal, wenn er weg von zu Fuß würde seine Tastatur mit seinem Bildschirm entsperrt, Ich würde einen Befehl auszuführen wie this-- "Hallo sagen." Und jetzt keine Zeit, kam er zurück sein Tastatur, nachdem ich den Bildschirm gelöscht und er würde sich hinsetzen, versuchen, einige Arbeit zu tun, Liste den Inhalt seiner directory-- [AUDIO PLAYBACK] -hello. Hallo. Sprecher 1: Also, in Fairness, es war nicht wirklich "Hallo." Es war in der Regel etwas verwandter dass-- [AUDIO PLAYBACK] -Beep. Sprecher 1: --that ich would-- so würde seinen Computer schwören auf ihn jederzeit er tatsächlich saß an seiner Tastatur nach unten. Und sehr schnell dachte er nicht zu verlassen, seinen Bildschirm entsperrt. Dies weist jedoch den Sortier dummer Spaß, dass Sie kann mit so etwas wie Bash haben. Aber es ist ein wenig mehr ernst, um sicher zu sein, als die. Und in der Tat ist eine der diese gefährlichsten und lang anhaltende Bugs das hat wirklich die Welt global getroffen. Dieser Bug herum gewesen seit rund 20 Jahren und Sie werden in nur getroffen werden, Moment durch seine relative Einfachheit. Das ist also ein Vertreter befehlen, dass, wenn Sie besitzen einen Mac, wörtlich jetzt wenn Sie Ihre Deckel geöffnet haben, Sie können versuchen, die Eingabe in das Programm namens Terminal entfernt. Terminal ist unter Anwendungen Utilities-- Für einmal haben Windows-Benutzer nicht Sorgen über diese besondere threat-- aber diejenigen von Ihnen mit Macs kann schreiben dies in einem Fenster wie ich hier zu tun, und wenn Sie geben dass in das Programm genannt Klemme, so wie ich jetzt tun werde, wenn Sie das Wort "verwundbar" Ihr Computer anfällig für Ausbeutung. Nun, was bedeutet das eigentlich? Und das ist zugegebenermaßen einige ziemlich verrückte Syntax, aber lassen Sie uns wenigstens ziehen einige der interessanten Aspekte. Also, es gibt einige, die Syntax sieht ein wenig vertraut ist, zumindest aus C und Programmierung im Allgemeinen. Ich sehe einige Klammern, Semikolons, geschweiften Klammern, und solche, aber es stellt sich heraus, dass diese dumme Sache hier in gelb ist im Wesentlichen eine Funktion das macht nichts. Der Doppelpunkt Mittel nichts tun, und die Semikolon bedeutet aufhören, nichts zu tun. Also innerhalb von diesen geschweiften Klammern, die Tatsache, dass ich eine gleich Zeichen links, diese ist im Wesentlichen die Schaffung ein Befehl oder eine Variable, x bezeichnet, zugeordnet wird dass gelb Stück Code gibt. Das könnte so etwas wie "Echo sein hallo "oder" sagen Piepton "oder etwas die derjenigen. Beachten Sie aber, wenn Sie Ihre Augen wandern weiter nach rechts, es gibt mehr zu dieser Linie als nur das Ende dieser Semikolon. "Echo anfällig", und dann darüber hinaus gibt es noch mehr. Ein weiteres Semikolon, bash-c :. So lange Rede kurzer Sinn, Diese Codezeile ist ausreichend für überzeugende ein Computer, ist anfällig für etwas zu tun dass Sie es tun wollen, denn es ist ein Bug in der Bash, wobei obwohl Bash sollte aufhören Lesen Linien Befehl rechts es nach dem gelben Text, für eine 20-plus-jährigen Bug, Bash wurde tatsächlich lesen darüber hinaus Semikolon und hübsch viel zu tun, was ihm gesagt wird. Also, was ist die Implikation der, dass letztlich? Ich sagte nur: "echo hallo" oder "echo anfällig", aber was, wenn Sie etwas getan tatsächlich bösartig, wie rm-rf *, die Sie vielleicht nicht je zuvor eingegeben haben, und ehrlich gesagt werden Sie wahrscheinlich sollte nicht zu früh, weil Sie ein tun können Menge Schaden mit sich. Warum? rm tut, was natürlich? Entfernt. * Bedeutet was? Alle. Es ist also eine so genannte Joker, so bedeutet alles löschen in das aktuelle Verzeichnis. r geschieht, bedeutet rekursiv, was bedeutet, wenn das, was Sie löschen ist ein Verzeichnis, und im Inneren von dort ist andere Dateien und andere Verzeichnisse, rekursiv tauchen ein in es und löschen Sie das alles. Und f ist die schlimmste von allen. Wer weiß, was f bedeutet hier? Kraft. So zwingen Mittel, auch ob dies eine schlechte Idee, tun es ohne mich aufgefordert für eine weitere Bestätigung. Also, wissen Sie, lachen wir über , aber ehrlich gesagt, hätte ich wahrscheinlich Geben Sie diese mehrfach am Tag, weil die Realität ist, es ist der schnellste Weg, löschen Sie eine ganze Reihe von Sachen. Aber auch ich habe einige Schäden getan. Aber wenn Sie einen Computer auszutricksen waren in der Definition einige dumme Variable oder Funktion namens x, aber dann trickst den Computer in der Ausführung jenseits der Grenzen, dass Funktion, darüber hinaus Semikolon, Sie könnte in der Tat verleiten einen Computer Ausführung in etwas wie rm-rf oder die E-Mail-Befehl oder den Befehl Kopieren. Alles, was Sie mit dem buchstäblich tun können Computer, ob es sich um das Löschen von Dateien, Erstellen von Dateien, Spamming jemand, Angriff auf einige Server remote, wenn man es so ausdrücken mit einem Befehl, können Sie können einen Computer in das Tun, dass Trick. Nun, was ist ein Beispiel für wie Sie dies tun? Nun, es gibt eine Menge von Computern im Internet läuft Bash. Alle von uns Mac-Anwender sind unter ihnen. Viele Linux-Server sind unter sie als gut und Unix-Servern. Fenster wieder bekommt relativ aus dem Schneider es sei denn, Sie installiert haben spezielle Software. Jetzt eine Menge von Servern, für So laufen Web-Server, und in der Tat Linux ist vielleicht beliebteste Betriebssystem auf den Computern im Internet laufen , das im Dienste werden Web-Seiten. Nun, wie wir später sehen in dem Semester, wenn Sie senden eine Anfrage von Ihre browser-- Chrome, Internet Explorer, whatever-- auf einem Remote-Server, es stellt sich heraus, dass, obwohl Sie gerade eingegeben www.example.com, Ihr Browser das Senden einer Nachricht das ist ein wenig mehr geheimnisvoll, wie diese. Beachten Sie aber, ein wenig etwas seltsam. Die ersten beiden Zeilen Ich habe noch nie gesehen, aber sie sehen nicht besonders bedrohlich. Beachten Sie aber, was ich gestohlen für die dritte Zeile hier. Wenn ein Angreifer waren, um eine Nachricht zu senden wie dies von seinem Computer zu einer gefährdeten Mac oder ein anfällig Linux-Server Die lustige Sache ist, dass Bash, dass kleine, einfache Eingabeaufforderung ist allgegenwärtig und oft gebrauchte wesentlichen ausführen Die Inhalte eines Nachricht, die er empfängt. Und von dieser Logik, können Sie Trick einen Web-Server, damit durch etwas wie das Senden User-Agent, die in der Regel soll das sagen nennen Ihres Browsers. User-Agent Chrome, User-Agent-Internet Explorer, Firefox User-Agent, diese ist nur Ihre Browser- Verfahren zur Identifizierung selber. Aber wenn ein schlechter Kerl sehr Geschickt sagt, mm-mm, bin ich nicht, Ihnen zu sagen was mein Browser ist, Ich werde Ihnen stattdessen diese senden kryptisch aussehendes Ding mit einem rm-rf * In ihm, können Sie buchstäblich ein Trick anfällig Webserver im Internet in genau diese Ausführung in es zum Löschen aller Dateien. Und ehrlich gesagt, das ist nicht sogar das Schlimmste. Sie können nichts tun. Sie könnten beginnen eine verteilte Denial-of-Service-Angriff Wenn Sie diese Nachricht gesendet Ganze Trauben von Web-Servern und hatte dann steigen sie alle, für beispielsweise auf Harvard.edu Servern und Sie können von Bang sortieren das Heck aus ihnen durch einen Netzwerkverkehr, war sonst durch diese Bösewicht ausgelöst. Also, lange Rede kurzer Sinn, fast jeder in diesem Raum, die einen Mac besitzt ist anfällig für diese. Der Silberstreif am Horizont ist, dass es sei denn, du bist einen Web-Server auf Ihrem Laptop, und wenn Sie tatsächlich konfiguriert haben es so etwas wie SSH in sie zu ermöglichen, Sie sind wirklich sicher. Es ist verletzlich, aber es gibt keine ein Versuch, in den Laptop zu bekommen, so können Sie sicher sein, Art. Allerdings wird Apple bald erneuern, ein Update für das. Die Welt von Linux bereits freigegeben hat eine Reihe von Updates für Fedora und Ubuntu und anderen Versionen von Linux, und in der Tat Wenn Sie Update 50 in das Gerät laufen, sogar, dass auch sein aktualisiert und korrigiert. Aber auch das hat nicht wirklich gefährdet gewesen, weil, wenn du hast mit dem Gerät gebastelt und machte Ihren Laptop öffentlich über das Internet, die nicht zugänglich ist standardmäßig, Sie haben eigentlich schon in Ordnung, weil der Firewall und andere Techniken. Aber es ist ein extremes Beispiel für einen Fehler dass wir für für buchstäblich 20 gelebt haben Jahre, und wer weiß, wenn jemand all dieser Zeit hat es gewusst? Und in der Tat ist einer dieser die grundlegenden Herausforderungen dass wir in der später sehen Semester über Sicherheit, ist, dass genau wie in der realen Welt, die Guten sind in der Nachteil. Um die bösen Jungs draußen zu halten, müssen wir stellen Sie sicher, dass jede Tür abgeschlossen ist, dass jedes Fenster ist sicher, dass jeder Punkt der Einreise in ein Heim sicher ist, die bösen Jungs draußen zu halten. Aber was hat der Bösewicht muss tun, um tatsächlich Kompromisse zu Hause und stehlen von Ihnen? Er oder sie muss nur einen entsperrten finden Tür, ein zerbrochenes Fenster, oder etwas in diese Richtung, und es ist das elbe in Computer-Sicherheit. Wir können Millionen von schreiben Zeilen Programmcode und verbringen Hunderte oder Tausende von Stunden damit es richtig zu bekommen, aber wenn man nur eine machen Fehler in der Korrektheit, Sie können das gesamte System setzen und in der Tat in diesem Fall das gesamte Internet und Welt in Gefahr. Also, wenn Sie möchten, um mehr zu erfahren über diese, zu dieser URL finden Sie hier. Es gibt keine Notwendigkeit für Maßnahmen heute Abend, es sei denn du bist unter denen, mehr Komfort, dass wurden Ihre eigenen Bahnlauf Server, in diesem Fall sollten Sie, in der Tat, aktualisieren Sie Ihre Software. Und auch dies ist der Titel des eine Rede, und jetzt ein Papier, dass wir auf dem verknüpft haben Website natürlich für heute. Es war von einem anderen namens Ken Thompson, der wurde die Annahme einer sehr berühmt Auszeichnung in der Informatik, und er gab diese Rede einige Jahre vor, im Wesentlichen auf dem gleichen Thema. Fragen die Leute die Frage, Sollten Sie wirklich Vertrauen, letztlich die Software Sie schon gegeben? Zum Beispiel, wir haben alle wurden Programme schreiben, und wir haben die Erstellung sie mit Clang. Und Ihr Wissen haben Sie geschrieben alle Programme für CS50, wo es eine Hintertür der Art, ist auch ein Weg dass ein schlechter Kerl, wenn Ihr Programm, könnte über Ihren Computer übernehmen? Wahrscheinlich nicht, oder? Mario, und gierig, und Credit. Diese sind alle ziemlich kleine Programme. Sie müssten schön sein schlecht, wenn Sie tatsächlich machte den ganzen Computer anfällig nach dem Schreiben 10 oder 20 Zeilen Code, oder zumindest nicht bewusst einige der Auswirkungen auf die Sicherheit. Jetzt sage ich, dass scherzhaft, aber wir werden heute zu sehen und in dieser Woche ist es eigentlich wirklich, wirklich einfach schlecht zu sein und auch Kurzprogramme anfällig. Aber für jetzt, zumindest, erkennen , dass die Frage, die hier gefragt Clang ist etwa in einem Compiler. Warum haben wir vertrauensvolle Clang für die letzten zwei oder drei Wochen? Wer zu sagen, dass wer auch immer schrieb Clang ist nicht eine "if" Bedingung dort haben dass im Wesentlichen injiziert einige Nullen und Einsen in jedem Programm kompiliert das würde lassen ihn oder sie Zugang Ihren Computer, wenn Sie schlafen und Ihr Laptop-Deckel ist geöffnet und Ihr Computer läuft? Oder? Wir haben diese Art von Ehre-System rechts Jetzt, wo wir vertrauen darauf, dass Clang ist echt. Sie vertrauen darauf, dass das Gerät echt. Sie vertrauen darauf, dass buchstäblich jedes Programm auf Ihrem Mac oder PC vertrauenswürdig ist. Und als diese einfache Fehler vermuten lässt, auch wenn es nicht bösartig, Das ist absolut nicht wahrscheinlich der Fall sein wird. So sollten Sie Angst, wie die Hölle sein. Ehrlich gesagt, gibt es keine einfache Lösung für dieses andere als eine Art gesellschaftliche Bewusstsein der zunehmenden Komplexität dass wir auf den Bau unsere EDV-Systeme, und wie immer anfälliger wir könnten sehr gut sein. Jetzt mit dieser sagte, Breakout. Breakout ist so eingestellt Problem drei, und Breakout ist ein Spiel von gestern dass Sie sich vielleicht erinnern, aber für uns in Frage stellte drei, es erlaubt uns, nehmen die Dinge wieder eine Kerbe so dass, wenn wir Programme schreiben, auch in einem Terminal-Fenster wie dieses, wir tatsächlich laufen letztlich grafische Programme nicht anders als die, die wir hatten Zugriff auf die im Scratch. Das ist also der Mitarbeiter Umsetzung der Breakout, Das ist gerade das Mauerbruch Spiel, dass Sie Ihr Paddel wieder bewegen und her, und du den Ball zu schlagen gegen die bunten Steine ​​bis oben. Also das bringt uns Art zurück, wo Wir waren in der Lage, sehr schnell mit Scratch, und jetzt mit C, die Umsetzung unserer eigenen grafische Benutzeroberflächen. Aber mehr als das, diese Problem stellt der erste Satz , in dem wir geben Sie sind ein Haufen von Code. Und in der Tat, ich bringe explizite die Aufmerksamkeit auf das, weil vor allem für die weniger komfortabel, diese Problem eingestellt, zumindest auf den ersten Blick wird sich wie fühlen wir eine Kerbe genommen haben oben. Weil wir euch gegeben, Für einige der Such und Sortierprobleme in der pSoll, ein Haufen von Code, den wir geschrieben, und ein paar Kommentare sagen "zu tun" wo man bis in die Lücken zu füllen. Also nicht zu gruselig, aber es ist das erste Mal, wir Gabe Sie Code, den Sie brauchen zuerst lesen, zu verstehen und dann zu addieren und füllen Sie es. Und dann mit Breakout, wir werden das gleiche tun, geben Sie ein paar Dutzend mehr Linien Code, der, ehrlich gesagt, geben Sie eine Menge von dem Rahmen für das Spiel, aber halt der Umsetzung der Steine und die Kugel und die Paddel, aber wir haben einige andere Features zu implementieren. Und auch, dass auf den ersten Blick wieder vor allem, wenn weniger komfortabel, vielleicht besonders entmutigend und Sie denken, es gibt so viele neue Funktionen Sie, Ihre Meinung zu wickeln müssen um, und das ist wahr. Aber bedenken Sie, es ist ganz wie Scratch. Chancen sind Sie nicht alle verwenden die Puzzleteile in Scratch. Chancen sind Sie nicht darauf zu wickeln Ihre Meinung rund um alle von ihnen weil alle dauerte es war ein schnellen Blick zu verstehen, oh, das ist, was ich tun kann mit diesem Puzzle-Stück. Und in der Tat, in Problem eingestellt 3 spec, werden wir Sie darauf hinweisen bei der Dokumentation, dass Will stellen Ihnen einige neue Funktionen, und schließlich die Programmier Konstrukte, die Sie verwenden. Bedingungen, Schleifen, Variablen und Funktionen identisch zu sein, was wir bisher gesehen. Also in der Tat, was wir geben Sie einige Beispiel-Code ist, dass lässt Sie ein Fenster erstellen das sieht nicht anders als diese, und schließlich machen es zu etwas ganz wie diese. So profitieren Sie von CS50, diskutieren Bürozeiten und mehr, und Trost in der Tatsache, dass die Menge an Code, den Sie haben, zu schreiben ist eigentlich gar nicht so viel. Die erste Herausforderung ist nur zu akklimatisieren Sie sich eine Code haben wir geschrieben. Sie haben Fragen zu pset3, Shellshock, oder anders? ZIELGRUPPE: Es schien, als durch mit Breakout dass der Code fast eine objektorientierte Stil, aber ich dachte, war ein C objektorientierten Programms. Sprecher 1: Eine ausgezeichnete Frage. So in der Suche durch die Verteilung Code, der Code wir pset3 schrieb, für diejenigen, vertraut, es sieht aus wie es ist ein wenig objektorientiert. Kurze Antwort ist, es ist. Es ist eine Annäherung, wie Sie möglicherweise mit objektorientierten Code zu tun eine Sprache wie C, aber es ist noch letztlich Verfahrens. Es sind keine Methoden innerhalb der die Variablen, wie Sie sehen werden. Es ist aber erinnert, daß. Und wir werden diese Funktion wieder zu sehen wenn wir in PHP und JavaScript zu erhalten gegen Ende des Semesters. Aber jetzt halten sie für ein Hauch von dem, was noch kommen wird. Gute Frage. In Ordnung. So verschmelzen Art war, wie wir links die Dinge beim letzten Mal. Und verschmelzen Art war kühl in der Sinn, dass es so viel schneller, zumindest an den flüchtigen Tests wir haben in der vergangenen Woche, als, sagen wir, Blase Sortieren, Auswahl Art, Insertion Sort. Und was war ordentlich zu ist nur wie prägnant und sauber Sie können es zum Ausdruck bringen. Und was haben wir sagen, es war ein oberer von der Laufzeit der Zusammenführungs gebunden sortieren? Ja? ZIELGRUPPE: n log n? Sprecher 1: n log n, richtig. n log n. Und wir werden wieder zu dem, was kommen, dass wirklich bedeutet oder woher das kommt, aber das war besser als das, was Laufzeit dass wir für die Blasen sah Auswahl und Insertion Sort? So n quadriert. n im Quadrat größer ist als diese, und selbst wenn es nicht ganz offensichtlich ist, wissen, dass log n kleiner als n ist, Wenn Sie also n-mal tun etwas kleiner als n ist, es geht um weniger als n quadriert werden. Es ist ein bisschen der Intuition gibt. Aber wir einen Preis bezahlt für diese. Es war schneller, aber ein Thema, das gestartet letzte Woche war dieser Kompromiss entstehen. Ich habe eine bessere Leistung Zeit weise, aber was musste ich auf der anderen verbringen Seits wird, um zu erreichen, dass? ZIELGRUPPE: Speicher. Sprecher 1: noch einmal sagen? ZIELGRUPPE: Speicher. Sprecher 1: Speicher oder Raum im Allgemeinen. Und es war nicht super mit unseren Menschen offensichtlich, aber daran erinnern, dass unsere Freiwilligen freuten Schritt und Schritt zurück, als ob es ein Array hier, und als ob es ein zweites Feld, dass hier sie nutzen könnten, weil wir benötigte irgendwo, diese Leute zusammenzuführen. Wir konnten nicht einfach tauschen sie an Ort und Stelle. So verschmelzen Art Hebelwirkung ist mehr Platz, die wir haben nicht mit Notwendigkeit die anderen Algorithmen, aber der Vorteil ist, dass es viel schneller. Und ehrlich gesagt, in der realen Welt Raum diese days-- RAM, Festplatte space-- ist relativ billig, und so ist das nicht unbedingt eine schlechte Sache. Werfen wir also einen kurzen Blick, ein wenig mehr methodisch, was wir getan haben und warum wir sagten, dass sie n log n. Also hier sind die acht Zahlen und die acht Freiwilligen hatten wir beim letzten Mal. Und das erste, was Merge Sortieren sagte uns zu tun war, was? ZIELGRUPPE: Teilen in zwei. Sprecher 1: noch einmal sagen? ZIELGRUPPE: Teilen in zwei. Sprecher 1: Teilen Sie in zwei, rechts. Dies erinnert sehr an das Telefonbuch, der Kluft und erobern im Allgemeinen. Also haben wir uns mit der linken Hälfte. Und dann, sobald wir gesagt, sortieren Die linke Hälfte der Elemente, Was haben wir als nächstes sagen? Sortieren Sie die linke Hälfte des linken Hälfte, die es uns ermöglicht,, nach der Teilung in zwei, konzentrieren sich auf vier und zwei. Wie sehen Sie jetzt eine Liste zu sortieren, in gelb, zwei von der Größe, mit Merge Sort? Nun teilen sie in zwei Hälften, und sortieren die linke Hälfte. Und das war, wo die Dinge habe ein wenig dumm kurz. Wie sehen Sie eine Liste, die ist eine Art von Größe ein, wie dieser hier, Nummer vier? Es ist sortiert. Sie sind fertig. Aber dann, wie Sie eine Liste sortieren Größe ein, wenn es die Nummer zwei? Nun, dasselbe, aber jetzt, was war das dritten und der entscheidende Schritt in Merge Sort? Sie musste die linke verschmelzen Hälfte und die rechte Hälfte. Und wenn wir das täten, haben wir uns an vier, haben wir uns zwei. Wir entschieden uns alle Rechte, offensichtlich zwei kommt zuerst, Also haben wir zwei in der Platz, gefolgt von vier. Und jetzt haben Sie, um Art von Rücklauf, und dies ist eine Art von charakteristischen eines Algorithmus wie Merge Sortieren, zurückspulen im Speicher. Was war die nächste Zeile von der Geschichte? Was sollte ich auf die sich weiter? Die rechte Hälfte des linken Hälfte, die sechs und acht. Also lassen Sie mich nur durch diesen Schritt ohne darauf herumzureiten, den Punkt zu viel. Sechs und acht, dann sechs ist sortiert, acht sortiert ist. Verschmelzen sie zusammen wie das, und jetzt der nächste große Schritt ist natürlich sortieren die rechte Hälfte aus der erste Schritt des Algorithmus. Also konzentrieren wir uns auf ein, drei, sieben, fünf. Wir konzentrieren uns dann auf der linken Hälfte. Die linke Hälfte, dass die rechte Hälfte des dass dann in einem und drei verschmelzen. Dann die rechte Hälfte, dann links die Hälfte davon, dann die rechte Hälfte. Verschmelzen sie in, und was nun Schritt bleibt? Zusammenführen der großen linken Hälfte und die große rechte Hälfte, so geht man dort unten, dann zwei, dann drei, dann vier, anschließend fünf, dann sechs, dann sieben, dann acht. So, jetzt, warum ist dies letztlich offenbart, vor allem, wenn n und Logarithmen mehr generell eher entkommen Sie, zumindest in der jüngsten Vergangenheit? Nun, beachten Sie die Höhe dieser Sache. Wir hatten acht Elemente, und wir geteilt durch zwei, durch zwei, durch zwei. So melden Sie sich zwei von acht Basis gibt uns drei. Und glauben Sie mir, dass, wenn ein wenig verschwommen auf die. Aber anmelden Basis zwei von acht ist drei, so haben wir drei Schichten der Zusammenführung getan. Und wenn wir zusammengeführt Elemente, wie viele Elemente haben wir uns auf jede dieser Zeilen? Insgesamt n, oder? Da die obere Reihe zusammenzuführen, auch wenn wir es Stück für Stück, wir letztlich berührt jede Zahl einmal. Und in der zweiten Reihe, um mischen Sie die Listen der Größe zwei, wir mussten jedes Element einmal zu berühren. Und dann ist hier wirklich eindeutig in der letzten Reihe, wir hatten für jeden der zu berühren Elemente einmal, sondern nur einmal, so liegt hierin also, unsere n log n. Und jetzt, nur um die Dinge ein wenig zu machen mehr formale nur für einen Moment, wenn Sie waren jetzt analysieren diese bei einer Art von höherem Niveau und versuchen, zu entscheiden, wie gut können Sie über das Ausdrücken gehen die Laufzeit des Algorithmus einfach durch einen Blick auf sie und nicht durch die Verwendung eines konstruiertes Beispiel? Nun, wie viel Zeit würden Sie sagen, ein Schritt, wie dies in gelb nehmen würde, wenn n <2 zurück? Das ist ein großes O, was? Also ich sehe ein, so einen Schritt, vielleicht zwei Schritte, weil es, wenn und dann wieder, aber es ist konstante Zeit, oder? Also sagten wir O (1), und das ist , wie ich dies zum Ausdruck bringen. T, nur Laufzeit sein. N die Größe des Eingangs, so T (n), nur eine andere Art zu sagen, die Lauf Zeit gegebene Eingabe der Größe n wird sich in der Größenordnung sein konstanter Zeit in O (1). Aber sonst, was ist das? Wie würden Sie das zum Ausdruck bringen Laufzeit dieser gelben Linie? T von was? Sie können hier Art betrügen und meine Frage beantworten zyklisch. Also, wenn die Laufzeit in wir generell nur sagen, ist T (n). Und jetzt sind Sie Art von Tochern hier und sagen, gut, nur die linke Hälfte zu sortieren, und dann sortieren, die rechte Hälfte. Wie können wir symbolisch die Laufzeit dieser gelben Linie? T von was? Was ist die Größe des Eingangs? n mehr als zwei. Warum ich nicht einfach sagen Sie das? Und dies ist ein weiterer T (n / 2) und dann wieder, wenn ich Zusammenführen von zwei sortierten Hälften, wie viele Elemente werde ich zu haben, um zu berühren insgesamt? n. So kann ich das zum Ausdruck bringen, nur um Art von Phantasie, als die Laufzeit im Allgemeinen. T (n) ist nur die Laufzeit T (n / 2), und T (n / 2), linke Hälfte und eine rechte Hälfte, und O (n), das ist wahrscheinlich n Schritten, aber vielleicht, wenn ich mit zwei Fingern, es doppelt so viele Schritte, aber es ist linear. Es ist eine Reihe von Schritten das ist ein Faktor von n, so könnten wir dies als dies zum Ausdruck bringen. Und das ist, wo wir jetzt zu Punt Rückseite unseres Hochschulmathematiklehrbuch wir sind schließlich, dass Rezidiv endet diese gleich, n-mal log n, wenn Sie tatsächlich tun out die Mathematik mehr formal. Also das ist nur zwei Perspektiven. Eine zahlenmäßig mit einem hartcodierte repräsentatives Beispiel mit acht Zahlen und eine weitere allgemeinen Blick auf, wie wir dort ankamen. Aber was ist wirklich interessant hier ist wieder dieser Begriff des Radsports. Ich bin nicht mit for-Schleifen. Ich bin eine Art der Definition etwas in Bezug auf sich selbst, nicht nur mit diesem mathematische Funktion, sondern auch in Bezug auf dieses Pseudo-Code. Diese Pseudo-Code ist rekursiv daß zwei der Linien wird im Wesentlichen sagen sie zu gehen verwenden selbst zu lösen eine kleinere Problem der kleineren Größe, und dann wieder und wieder und wieder, bis wir es Whittle bis zu diesem so genannten Basisfall. Lassen Sie uns also tatsächlich zeichnen Sie eine überzeugende Mitnehmen von dieser wie folgt. Lassen Sie mich in gedit gehen und ein Blick auf einige der heutigen Quellcode, insbesondere dieses Beispiel hier. Sigma 0, die offenbar fügt die Zahlen eins bis n. Also mal sehen, was ist vertraut und ungewohnt hier. Zuerst müssen wir ein paar enthält, also nichts Neues. Prototyp. Ich bin ein wenig dunstig auf das nach einigen Tagen, aber was wir sagen, ein Prototyp einer Funktion? ZIELGRUPPE: [unverständlich]. Sprecher 1: Was ist das? ZIELGRUPPE: Wir verkünden es. Sprecher 1: Wir verkünden es. So können Sie unterrichten Clang, hey, nicht die tatsächliche Umsetzung dieser noch aber irgendwo in dieser Datei, vermutlich, sein wird eine Funktion aufgerufen, was? Sigma. Und das ist nur ein Versprechen, das es wird so aussehen. Es geht um eine ganze Zahl als nehmen input-- und ich kann mehr explizit sein und sagen, int n --und es ist werde ein int zurück, aber Semikolon Mittel, mm, ich werde umgehen zur Umsetzung dieses ein wenig später. Auch hier ist Clang dumm. Es ist nur zu wissen, was Sie sagen, es von oben nach unten, so müssen wir zumindest geben es ist ein Hinweis darauf, was noch kommen wird. Jetzt schauen wir uns hier Haupt. Lassen Sie nach unten scrollen und hier sehen, welche Haupt tut. Es ist nicht so lange von einer Funktion und in der Tat das Konstrukt ist hier vertraut. Ich erkläre, eine Variable n und dann Ich die Benutzer zu belästigen immer wieder für eine positive ganze Zahl mit getInt, und einzige Ausgang aus dieser Schleife sobald der Benutzer erfüllt werden. Tun, während wir verwendet haben belästigen die Benutzer auf diese Weise. Nun ist dies interessant. Ich erkläre, einen int als "Antwort". Ich, es ist der Rückgabewert zuweisen einer Funktion namens "Sigma". Ich weiß nicht, was das noch tut, aber Ich erinnere mich noch vor einem Moment erklärt. Und dann bin ich in die Weitergabe Wert, den der Benutzer eingegeben in, n, und dann melde ich die Antwort. Nun lassen Sie blättern zurück nur für einen Moment. Lassen Sie uns gehen Sie in dieses Verzeichnis, machen Sigma 0, und tatsächlich dieses Programm ausführen und sehen, was passiert. Also, wenn ich voran gehen und laufen Dieses Programm, ./sigma-0, und ich tippe auf eine positive integer wie zwei, Sigma, wie die griechische Symbol bedeutet, ist nur gehen, um von summieren sich alle Zahlen Null bis zu zwei. Also 0 plus 1 plus 2. So sollte dies hoffentlich geben Sie mir 3. Das ist alles, es tut. Und ähnlich, wenn ich dies wieder und ich gebe sie die Nummer drei, das ist 3 plus 2, das ist also 5, plus 1 sollte mir 6. Und dann, wenn ich wirklich verrückt und Anfang, der in größeren Zahlen, sollte es mir geben größer und größer Summen. Also das ist alles. Also, was hat Sigma aus? Nun, es ist ziemlich einfach. Es ist, wie wir umgesetzt haben, könnte dies für die letzten paar Wochen. "Int" wird sich der Rückgabetyp sein. Sigma ist der Name, und es dauert eine Variable m statt n. Ich werde das ändern, bis oben. Dann ist dies nur eine Plausibilitätsprüfung. Wir werden gleich sehen, warum. Jetzt erkläre ich eine weitere Variable, Summe, initialisieren Sie ihn auf Null. Dann habe ich diese For-Schleife Iterieren offenbar zur Klarheit von i = 1 auf bis zu einem = m, das ist, was auch immer der Benutzer eingegeben wird, und dann habe ich erhöhen die Summe wie diese. Und dann die Summe zurück. So ein paar Fragen. Eins, behaupte ich in meinem Kommentar, dass dies vermeidet Risiko einer Endlosschleife. Warum sollte in einer negativen Zahl vorbei induziert werden, eine Endlos-Schleife? ZIELGRUPPE: Du wirst nie m zu erreichen. Sprecher 1: m erreichen Nie. Aber m übergeben wird, so lassen Sie uns ein einfaches Beispiel. Wenn m in den durchlaufenen Benutzer als negative. Unabhängig von Haupt. Haupt schützt uns vor dies zu, so bin ich nur als wirklich anal mit Sigma, um auch sicherstellen, dass daß die Eingabe nicht negativ sein. Also, wenn m negativ ist, so etwas wie negative. Was wird passieren? Nun, ich werde einem initialisiert, und dann habe ich sein wird weniger als oder gleich m? Stehen zu. Dass was-- die nicht zulassen, Lassen Sie uns diese Geschichte nix. Ich habe nicht diese Frage stellen, denn das Risiko, dass ich in Anspielung auf wird nicht passieren, weil ich es immer werde größer sein than-- OK, Ich zurückziehen, dass die Frage. Ok. Konzentrieren wir uns nur auf diesen Teil hier. Warum habe ich einige erklären außerhalb der Schleife? Bekanntmachung über die Linie 49 habe ich Innenseite der Schleife deklariert i, aber ich habe 48 Online- erklärt etwas außerhalb. Ja. ZIELGRUPPE: [unverständlich]. Sprecher 1: Sicher. Also in erster Linie ich sicher nicht wollen, zu erklären und zu initialisieren Summe Null innerhalb des Schleife bei jeder Iteration, denn dies würde klar die Niederlage der Zweck der Addition der Zahlen. Ich würde ständig ändern der Wert auf Null zurück. Und auch, was ist eine andere, geheimnisvollen Grund für den gleichen Design-Entscheidung? Ja. ZIELGRUPPE: [unverständlich]. Sprecher 1: Genau. Ich will es außerhalb zugreifen der Schleife zu, auf welcher Linie? 53. Und auf unserer Faustregel auf der Basis von ein paar Vorlesungen vor, Variablen sind Bereiche, und wirklich, um die geschweiften Klammern, die sie umfassen. Also, wenn ich nicht innerhalb erklären Summe dieser äußeren geschweiften Klammern, Ich kann ihn nicht in Zeile 53. Anders gesagt, wenn ich erklärte, Summe hier, oder sogar innerhalb der For-Schleife, konnte ich nicht darauf zugreifen in 53. Die Variable würde effektiv verschwunden sein. So ein paar Gründe gibt. Aber jetzt zurück gehen lassen und sehen, was passiert. So Sigma aufgerufen wird. Es summiert sich 1 sowie 2, oder 1 plus 2 plus 3, und gibt dann den Wert, speichert es in der Antwort, und hier printf Deshalb habe ich sehe auf dem Bildschirm. Also das ist, was wir nennen eine iterative Ansatz, bei dem nur Iteration bedeutet, mit einer Schleife. Eine For-Schleife, einer While-Schleife, ein Do While Schleife, nur etwas wieder zu tun und immer wieder. Aber Sigma ist eine Art ordentlich Funktion in dass ich es anders umzusetzen. Was ist dieses, das nur um irgendwie cool, lassen Sie mich wirklich loswerden eine Menge Ablenkung Da diese Funktion ist eigentlich ganz einfach. Lassen Sie es nach unten schnitzen nur zu den vier Kernlinien und loszuwerden alle Kommentare und geschweiften Klammern. Dies ist eine Art Geist weht alternative Implementierung. Alles klar, vielleicht nichts dagegen weht, aber es ist irgendwie sexy, alles in Ordnung, auf diese so viel mehr kurz und bündig zu suchen. Mit nur vier Zeilen Code, Ich habe zuerst diese Plausibilitätsprüfung. Wenn m kleiner als oder gleich ist Null, macht Sigma keinen Sinn. Es ist nur angeblich in sein dieser Fall für positive Zahlen, so bin ich gerade dabei, Null zurück willkürlich so dass man zumindest einige so genannte Basisfall. Aber hier ist die Schönheit. Die Gesamtheit dieser Idee, indem die Zahlen von 1 bis n oder m in diesem Fall kann durch Art von den schwarzen Peter zuschieben geführt werden. Nun, was ist die Summe von 1 bis m? Nun, wissen Sie was? Es ist die gleiche wie die Summe von m und die Summe von 1 bis M minus 1 ist. Nun wissen Sie was? Was ist der Sigma-m minus 1? Nun, wenn Sie diese Art von folgen logisch, es ist das gleiche wie m minus 1 Plus Sigma von minus 2 m. Können Sie so freundlich von just-- das ist wie, wenn Sie gerade sind versucht, einen Freund zu ärgern und sie dir eine Frage stellen, Sie Art reagieren mit einer Frage, Sie können Art halten den schwarzen Peter zuschieben. Aber was ist Schlüssel ist, dass, wenn Sie zu halten macht die Frage immer kleiner und kleiner, sind Sie nicht zu fragen, was ist Sigma n, was ist der Sigma- n, was ist sigma n? Sie fragen, was ist Sigma-n, was ist Sigma n minus 1, was ist sigma n minus 2? Schließlich Ihre Frage wird, was zu werden? Was Sigma eines oder Null, einige sehr kleinen Wert, und sobald Sie bekommen, dass, Ihr Freund, Sie sind nicht zu fragen die gleiche Frage wieder, Sie gerade gehen zu sagen, oh, es ist null. Wir sind fertig spielen diese Art dumme zyklischen Spiel. So Rekursion ist die Handlung in der Programmierung einer Funktion, die sich selbst. Dieses Programm, wenn kompiliert und ausgeführt wird, ist gehen, genau die gleiche Art und Weise zu verhalten, aber was ist Schlüssel ist, dass im Inneren einer Funktion namens Sigma, gibt es eine Code-Zeile bei wir uns selbst fordern, die normalerweise schlecht sein würde. Zum Beispiel, was ist, wenn ich zum ersten Mal Diese zusammengestellt, so stellen sigma-- machen Sigma-1-./sigma-1. Positive ganze Zahl, bitte, 50 1275. Also, was die Funktion scheint , bezogen auf einen Test korrigieren. Aber was, wenn ich ein wenig gefährlich und die so genannte Basisfall zu löschen, und einfach sagen, auch ich mache nur dies komplizierter als es ist. Lassen Sie uns einfach berechnen die Sigma- indem m und dann die Zugabe Sigma in der m minus eins? Nun, was ist hier geschehen? Lassen Sie uns zu verkleinern. Lassen Sie das Programm neu zu kompilieren, speichern, kompilieren Sie das Programm, und dann bereit ./sigma-1 Zoomen, Geben Sie bitte positive ganze Zahl, 50. Wie viele von Ihnen bereit sind um zu sehen, erzähl ihm, dass? Ok. So kann dies für passieren eine Reihe von Gründen, und ehrlich gesagt in dieser Woche sind wir über Sie mehr von ihnen zu geben. Aber in diesem Fall versuchen rückwärts Vernunft was könnte hier passiert sein? Segmentation fault, sagten wir zuletzt Zeit bezieht sich auf ein Segment des Speichers. Etwas Schlimmes passiert. Aber was war es mechanisch, die schief ging hier wegen meiner Entfernung dieser so genannten Basisfall, wo ich wieder einen hart codierten Wert? Was denken Sie, ist schief gelaufen? Ja. ZIELGRUPPE: [unverständlich]. Sprecher 1: Ah. Gute Frage. So dass die Größe der Zahl dass ich der Zusammenfassung war so groß, dass es überschritten die Größe des Speicherplatzes. Gute Idee, aber nicht grundlegend gehen zu einem Absturz führen. Das könnte dazu führen, Integer-Überlauf, wo die Bits nur umdrehen und dann Fehler, den wir eine wirklich große Nummer wie eine negative Zahl, aber, dass selbst führt nicht zu einem Absturz. Da am Ende der Tag ein int ist immer noch 32 Bit. Sie sind nicht zu gehen versehentlich stehlen ein 33. Bit. Aber ein guter Gedanke. Ja. ZIELGRUPPE: [unverständlich]. Sprecher 1: Die Methode nie mehr läuft, und in der Tat selbst nennt es wieder und wieder und wieder und wieder wieder, und keiner diese Funktionen je beenden, weil ihre einzige Zeile Code ruft them wieder und wieder und wieder. Und was ist wirklich geschieht hier, und jetzt sind wir kann diese Art von bildhaft zu zeichnen. Lassen Sie mich gehen über eine Bild für einen Moment. Dies ist ein Bild, dass schließlich Fleisch aus genauer, was los ist innerhalb des Arbeitsspeichers Ihres Computers. Und es stellt sich heraus, dass auf die Unterseite des Bildes ist etwas, genannt Stack. Dies ist ein Stück Erinnerung, ein Stück von RAM, das ist nur jederzeit benutzt eine Funktion aufgerufen wird. Jedes Mal, wenn ein Programmierer, eine Funktion aufrufen, das Betriebssystem, wie Mac OS, Windows oder Linux, greift ein Bündel von Bytes, vielleicht ein wenige Kilobyte, vielleicht paar Megabyte Speicher, gibt sie für Sie, und dann lässt Sie Ihre Funktion mit laufen was auch immer Sie brauchen, Variablen. Und wenn Sie dann rufen Sie eine andere Funktion und eine andere Funktion, Sie noch ein Stück Erinnerung erhalten und ein weiteres Stück der Erinnerung. Und in der Tat, wenn dieser grünen Schalen von Annenberg vertreten, dass der Speicher, hier ist was passiert, die erste Zeit, die Sie Funktion Sigma nennen. Es ist wie wenn man ein Fach wie dieses auf, was zunächst ein leerer Stapel. Aber dann, wenn das Fach nennt sich, so zu sprechen, Aufruf einer anderen Instanz Sigma, das wie zu fragen, das Betriebssystem, ooh, brauchen ein wenig mehr Speicher, geben mir das. Und dann wird es auf auf der Oberseite aufgetürmt. Aber was ist der Schlüssel hier ist, dass die erste Schale ist noch da, weil er aufgerufen diese zweite Fach. Jetzt inzwischen Sigma Sigma nennen, das ist wie zu fragen, für mehr Speicher. Wird auf hier aufgetürmt. Sigma Sigma nennen, das ist eine andere Fach, das hier aufgetürmt wird. Und wenn Sie dies tun, immer, schließlich, Art der Karte dieses visuelle auf diese Karte, ist was zu gehen passieren den Stapel von Ablagen? Es geht um den Betrag übersteigen Speicher auf Ihrem Computer. Und sobald dieser grünen Schale die horizontale Linie überschreitet Stapel oben und über diesem Wort Haufen, die wir wieder in der Zukunft kommen, das ist eine schlechte Sache. Der Haufen ist eine andere Speichersegment, und wenn Sie diese lassen Tabletts Stapel und Haufen auf, Sie gehen zu übersteigen sind Ihre eigenen Speichersegment, und ein Programm ist in der Tat werde abstürzen. Jetzt als beiseite, dieser Idee Rekursion daher Deutlich zu Problemen führen, aber es ist nicht unbedingt eine schlechte Sache. Da betrachten, nach alle, und vielleicht how-- Dies dauert einige gewöhnungs zu --Wie elegant oder wie einfach dass die Umsetzung des Sigma war. Und wir sind nicht zu verwenden, Rekursion, dass alle viel in CS50, aber in CS51, und wirklich jede Klasse wo man Datenstrukturen manipulieren wie Bäume oder Familienstammbäume, dass eine gewisse Hierarchie, es ist super, super nützlich. Jetzt, als zur Seite, so dass Sie als angehende Informatiker sind mit einigen von Google vertraut Insider-Witze, wenn Sie zu Google und Sie sehen, was ist der Definition von, sagen wir, Rekursion, geben. Uh-huh. Nebenbei, zog ich ein paar. Das war wie 10 Minuten Zaudern an diesem Morgen. Wenn Sie auch Google "schief", Bekanntmachung durch Neigen Sie Ihren Kopf slightly-- und dann ist dies eine vielleicht grausamsten aller da jemand wie verbrachte ihren Tag der Umsetzung dieser einige Jahre ago-- kommen. Oh, das ist wait-- ein Fehler. Also auf einen der Lauf größten Websites weltweit sind diese dummen kleinen Ostereier. Sie verbrauchen wahrscheinlich ein triviale Anzahl von Codezeilen gerade so, dass wir haben können wenig Spaß Dinge. Aber zumindest jetzt erhalten Sie einige dieser Insider-Witze. Werfen wir nun einen Blick auf einige der White Lies haben wir in der letzten Zeit erzählt wurde, und beginnen zu schälen zurück einige Schichten technisch so dass Sie wirklich verstehen, was los war und Sie verstehen können einige der Bedrohungen, wie Shellshock, dass haben nun begonnen, sich an der Spitze der jeder Aufmerksamkeit, zumindest in den Medien. So, hier ist eine sehr einfache Funktion dass nichts zurückgibt, ungültig. Sein Name ist Swap. Es dauert in zwei Variablen und es gibt nichts zurück. Nimmt in a und b. So eine schnelle Demonstration. Wir brachten diese auf. Wir könnten genauso gut ein wenig dauern brechen hier für einen Moment und haben ein wenig etwas zu trinken. Wenn jemand hätte nichts dagegen Beitritt mich hier nur für einen Moment. Wie über Sie in der kastanienbraunen T-Shirt? Komm auf. Nur die ein heute. Vielen Dank, dass Sie, wenn. Alles in Ordnung, und wir haben kommen, die hier? Wie heißen Sie? Lautsprecher 4: Laura. Sprecher 1: Laura. Komm auf. So Laura, sehr einfache Herausforderung heute. Schön, yo erfüllen. In Ordnung. Also haben wir etwas Milch über hier und wir haben etwas Orangensaft hier und einige Tassen, die wir von Annenberg ausgeliehen heute. Lautsprecher 4: entlehnt. Sprecher 1: Und er ging voran gehen und geben Sie ein halbes Glas davon. In Ordnung. Und wir werden Sie die Hälfte geben ein Glas Milch. Ach ja, und nur so, dass man daran erinnern, was das war, wie, Ich erinnerte mich an zu bringen, Diese und heute. Okay. Wenn Sie nichts dagegen hätte, mal sehen, wir können sie über die eigene Brille aufsetzen falls Sie es wollen. Das wird die Welt von Lauras Augen sein. In Ordnung. Ihr Ziel so, da zwei Tassen Hier Flüssigkeit, Milch und Orangensaft, wird die beiden Inhalte zu tauschen, so dass die Orangensaft geht in die Milch Tasse und die Milch geht in der Orangensaft Tasse. Lautsprecher 4: Bekomme ich noch eine Tasse? Sprecher 1: Ich bin so froh, dass du gefragt, wenn auch es wäre viel besser Material haben wenn du nicht gefragt. Aber ja, wir bieten Ihnen eine dritte Tasse, die leer ist, natürlich. In Ordnung. So tauschen Sie die Inhalte dort. Sehr schön. Sehr gut. Sie tun dies bemerkenswert sorgfältig. Und Schritt drei. In Ordnung. Ausgezeichnet. Ein großer Applaus wäre gut für Laura. In Ordnung. Wir haben ein kleines Abschiedsgeschenk für Sie, aber lassen Sie mich diese zu nehmen. Vielen Dank. So ein einfaches Beispiel, obwohl, zu zeigen, dass, wenn Sie tun möchten den Inhalt tauschen aus zwei Behältnissen, oder nennen wir sie Variablen, Sie einige Zwischenlagerung müssen einem der Inhalt so Bühne dass Sie tatsächlich die Swap. Also in der Tat, diese Quellcode hier in C ist repräsentativ für genau dies. Wenn der Orangensaft war und die Milch war b, und wir, die beiden tauschen wollte, Sie könnten versuchen, etwas Kreatives durch Gießen einen in die andere, Aber das wäre wohl nicht Ende besonders gut. Und so nutzen wir eine dritte Tasse, Call es tmp, T-M-P durch Konvention, und legte den Inhalt der OJ in das, dann tauschen Sie eine Tasse, dann die in der OJ Original Tasse, wodurch erreichen, genau so, wie Laura hat, die Swap. Lassen Sie uns also genau das zu tun. Lassen Sie mich gehen Sie vor und öffnen bis ein Beispiel, das ist eigentlich "nicht tauschen ", denn dies ist nicht so einfach getan, wie Sie vielleicht denken. Also in diesem Programm, feststellen, dass Ich bin mit stdio.h, unser alter Freund. Ich habe den Prototyp für Swap da oben, die bedeutet, ihm die Umsetzung wahrscheinlich unten, und lassen Sie uns sehen, was das Haupt Programm geht für mich zu tun. Ich zuerst erklären, int x bekommt eine, und int y bekommt zwei. Also denken Sie an jene, die als OJ und Milch sind. Und dann habe ich nur eine printf sagen x ist dies und y ist das, nur so kann ich visuell zu sehen, was los ist. Dann habe ich printf behauptet dass ich Vertauschen der beiden, und dann habe ich ein ausdrucken behaupten, dass sie ausgelagert sind, und ich ausdrucken x und y wieder. Also hier unten in Swap ist genau das, was Laura tat, und genau das, was wir auf sah der Bildschirm vor einem Augenblick. Also lassen Sie uns weitermachen und bitter enttäuscht sein. Machen Sie keinen Tausch, und führen Sie keine Swap, Zoom auf den Ausgang hier. Eingabe x 1 ist, y 2 ist, Austauschen vertauscht. x ist immer noch 1 ist, und y 2 noch. Also auch wenn, ehrlich gesagt, das sieht Genau wie, wenn auch technisch, Laura, was getan hat, nicht zu funktionieren scheint. Also, warum ist das so? Nun stellt sich heraus, dass, wenn schreiben wir ein Programm wie dieses das hat sowohl Haupt, betonte hier, und dann eine andere Funktion, wie Swap, hier hervorgehoben, die es nennt, die Welt sieht ein wenig so etwas wie Diese Schalen vor einem Augenblick. Wenn der Haupt ersten aufgerufen wird, das ist als würde man fragen Betriebssystem für ein wenig Speicher für jede lokale Variablen wie x und y, die Haupt hat, und sie am Ende recht. Aber wenn Haupt Anrufen zu wechseln, und die Haupt geht auf zwei Argumente A und B zu tauschen, Orangensaft und Milch, es ist nicht wie Übergabe der Orangensaft und die Milch Laura. Was ein Computer tut, ist es gibt Kopien der Orangensaft und Kopien der Milch an Laura, so dass was letztlich innerhalb dieses Fach ist der Wert eins und zwei, oder OJ und Milch, aber Kopien davon, so dass an dieser Stelle in der Geschichte, gibt OJ und Milch in jedem dieser Fächer. Es gibt eine und eine zwei In jedem dieser Fächer, und die Swap-Funktion ist in der Tat funktioniert. Es ist ihnen in Austausch der zweiten obersten Fach, aber das Swapping hat keine Auswirkungen. Und auf der Basis nur einige Grundprinzip haben wir sprach über vor, und zwar gerade vor ein paar Minuten, was könnte erklären, warum ändern a und b innerhalb der Swap- keine Wirkung auf x und y, obwohl Ich ging x und y auf die Swap-Funktion. Was ist hier das Schlüsselwort, dass könnte vereinfachend zu erklären? Ich glaube, ich habe es hier? ZIELGRUPPE: Rückkehr. Sprecher 1: Zurück? Nicht zurück. Lassen Sie uns mit einem anderen zu gehen. Was ist das? ZIELGRUPPE: [unverständlich]. Sprecher 1: OK, also wir konnten return-- Rückkehr machen Arbeit in der Geschichte, aber es gibt eine noch einfachere Erklärung. ZIELGRUPPE: Scope. Sprecher 1: Scope. Ich werde Umfang zu nehmen. So Umfang, daran erinnern, wo unsere x und y erklärt. Sie sind im Inneren erklärt Haupt bis hier. A und B sind unterdessen wirksam erklärt innerhalb von Swap, nicht ganz in Die geschweiften Klammern, aber immer noch in den allgemeinen Bereich der Swap. Und zwar so, a und b nur in diesem Fach gibt es von Annenberg, diese zweiten Teil des Codes. So sind wir in der Tat die Änderung der Kopie, sondern das ist gar nicht so hilfreich. Werfen wir also einen Blick auf dies ein wenig niedrigeren Niveau. Ich werde wieder in gehen Das Quellverzeichnis, und ich werde zum ersten Vergrößern hier, und nur , um zu bestätigen, dass ich in dieser größere Terminal-Fenster, das Programm ist immer noch verhalten wie die. Nehmen wir nun an, dass diese ist nicht beabsichtigt. Klar wollte ich Swap Arbeit, so fühlt es sich wie ein Bug. Jetzt konnte ich ein Start-Zugabe viel printf auf meine Code, Ausdrucken x hier, y über hier, ein hier, b hier. Aber ehrlich gesagt, ist wahrscheinlich, was das Sie haben für ein paar Wochen getan Jetzt, in der Bürozeiten und zu Hause bei der Arbeit auf psets versuchen, einige Fehler zu finden. Aber Sie werden sehen, wenn Sie nicht bereits haben, dass Problem stellte drei führt Sie auf einen Befehl namens GDB, wo GDB, der GNU Debugger, hat sich eine ganze Reihe von Funktionen, die eigentlich kann lassen uns verstehen, Situationen wie diese, aber mehr zwingend, Probleme zu lösen und Fehler finden. Also werde ich, dies zu tun. Statt der ./noswap, ich bin statt werde GDB ./noswap laufen. Mit anderen Worten, ich werde laufen meine Programm nicht in Bash, unser neuer Freund heute. Ich werde laufen meine Programm NOSWAP innen dieses andere Programm namens GDB, die ein Debugger, der ist ein Programm, das entworfen, um zu helfen Sie finden Menschen und Bugs zu entfernen. Also, wenn ich getroffen Führen Sie hier, gibt es ein grausames Textmenge dass Sie wirklich nie zu lesen. Es ist im Wesentlichen eine Ablenkung von der Eingabeaufforderung, die Ich werde Strg-L getroffen aufstehen an der Spitze gibt. Dies ist der GDB Aufforderung. Wenn ich dieses Programm jetzt laufen, als dieser kleinen Spickzettel auf dem heutigen Rutsche schon sagt, ist der erste Run Befehle, die wir einführen soll. Und ich werde einfach geben laufen hier innerhalb der GDB, und in der Tat lief es mein Programm. Jetzt gibt es einige zusätzliche Ausgänge der Bildschirm wie diese, aber das ist einfach nur anal GDB und sagen uns, was los ist. Sie haben nicht wirklich Sorgen zu machen über diese Details jetzt. Aber was ist wirklich cool GDB, diese again-- wenn ich Strg-L löscht die screen-- mich gehen lassen vor und geben Sie "brechen Haupt," damit, wenn ich drücken Sie die Eingabetaste, Einstellung, was rief ein Haltepunkt an noswap.c, Linie 16, die GDB ist, wo heraus mein Programm eigentlich ist, eigentlich ist meine Funktion. Dies werden wir jetzt ignorieren aber das ist die Adresse im Speicher speziell dieser Funktion. So, jetzt, wenn ich tippen, bemerken, was ist cool hier. Mein Programm bricht an der Linie, die ich sagte GDB, um die Ausführung zu unterbrechen. So dass ich nicht haben, um jetzt meinen Code zu ändern, fügen Sie einige printf ist, neu kompilieren, Wiederholung es, zu ändern, fügen Sie einige printf ist, speichern, neu kompilieren, führen Sie es. Ich kann einfach durch mein Programm laufen Schritt für Schritt für Schritt an die menschliche Geschwindigkeit, nicht bei Intel-inside Art von Geschwindigkeit. So, jetzt feststellen, diese Zeile erscheint hier, und wenn ich zurückgehen mein Programm in gedit, feststellen, dass das ist eigentlich die erste Zeile Code. Es gibt Linie 16 in gedit. Es gibt Linie 16 in GDB, und selbst Obwohl diese Schwarz-Weiß-Schnittstelle ist nicht annähernd so benutzer freundlich, bedeutet dies, diese Linie 16 wurde nicht ausgeführt noch nicht, aber es geht darum, zu sein. Also in der Tat, wenn ich schreibe Druck x, nicht printf, nur print x, Ich einige gefälschte Wert von Null dorthin zu gelangen, weil x ist noch nicht initialisiert. So werde ich zum nächsten geben, oder, wenn man wollen kunstvoll zu sein, nur N für nächste. Aber wenn ich schreibe nächste geben, jetzt merken es bewegt sich auf der Linie 17. So logisch, wenn ich ausgeführt habe Zeile 16 und ich jetzt geben print x, Was muss ich sehen? One. Und jetzt ist dies zwar verwirrend. $ 2 ist nur eine andere Art zu, wenn Sie wollen auf diesen Wert später beziehen, Sie sagen: "Dollar-Zeichen zwei." Es ist wie ein Rückverweis. Aber jetzt, einfach ignorieren. Was interessant ist, was ist auf der rechten Seite des Gleichheitszeichens. Und jetzt, wenn ich als nächstes schreiben wieder und Druck y, sollte ich sehen 2. Ich kann auch jetzt drucken x wieder, und ehrlich gesagt, wenn ich immer ein wenig verwirrt, wo ich bin, kann ich Liste für Liste geben und nur sehen, um einige Kontext der Punkt bin ich tatsächlich an. Und jetzt habe ich geben kann Weiter, und gibt x 1 ist. Jetzt tippe ich auf Weiter. Oh, das ist y 2. Und wieder ist es verwirrend, weil GDB Ausgangs wird mit eigenen Ausgang vermischt. Aber wenn man bedenkt, von Blick hin und her auf den Code oder aus über IT-Seite einander vielleicht, werden Sie sehen, dass wirklich, ich bin nur Schreiten durch mein Programm. Beachten Sie aber, was als nächstes passiert, buchstäblich. Hier ist Zeile 22. Lassen Sie mich über sie gehen und bewegt dadurch auf bis 23, und wenn ich drucken X jetzt, immer noch einer. Und wenn ich drucken y jetzt, immer noch einer. Das ist also nicht eine nützliche Übung. Also lassen Sie uns dies wiederholen. Lassen Sie mich zurückgehen bis zu der Top-und Typ Lauf erneut. Und es sagt, das Programm das ist gedebuggt hat bereits begonnen, vom Beginn gestartet. Ja, machen wir das wieder. Und dieses Mal wollen wir als nächstes tun, Als nächstes nächstes nächstes nächstes aber jetzt die Dinge interessant. Jetzt möchte ich in den Schritt Swap, so dass ich nicht neben geben. Ich tippe Schritt, und jetzt merkt es hat mich zu noswap.c Linie 33 gesprungen. Wenn ich wieder zu gedit, was ist Zeile 33? Das ist der erste tatsächliche Codezeile innerhalb Swap. Das ist schön, denn jetzt kann ich Art schnüffeln und neugierig , was los ist wirklich drin. Lassen Sie mich tmp drucken. Whoa. Warum hat tmp einige haben verrückt, gefälschte Müll Wert? ZIELGRUPPE: Es wurde nicht initialisiert. Sprecher 1: Es wurde nicht initialisiert. Und in der Tat, wenn Sie ein Programm ausführen, Sie eine ganze Reihe von Speicher gegeben durch das Betriebssystem, aber sie nicht initialisiert alle Werte, so was auch immer du bist Bits hier sehen, auch wenn es diese verrückte großen negativen Nummer, bedeutet nur, dass diejenigen, die Reste von sind einige vorherige Nutzung dieser RAM, auch wenn ich nicht mich brauchte es noch nicht. So, jetzt werde ich weiter und Art gehen nächsten, und wenn ich jetzt Typ Druck tmp, Was muss ich sehen? Was auch immer der Wert von a war, a ist das erste Argument, nur wie x war die erste Ding, das übergeben wird, so a und x gleich sein sollten, so drucken tmp sollte mir ein drucken. Also, was Sie in Problem-Set zu sehen drei ist ein Tutorial von Arten auf GDB, aber erkennen, dass dies der Anfang von einem Blick auf ein Tool, das tatsächlich Ihnen helfen, Probleme zu lösen so viel effektiver. Was wir letztlich werde am Mittwoch zu tun wird beginnen, ein paar Schichten wieder ablösen und entfernen Sie einige Stützräder. Das Ding namens String, wir für einige Zeit verwendet haben, wir werden langsam wegnehmen von Ihnen und sprechen über etwas esoterisch als char * bekannt, aber wir werden dieses schöne tun und zuerst sanft, obwohl Zeiger, wie sie genannt werden, können einige tun sehr schlimme Dinge, wenn missbraucht, durch Blick auf ein wenig claymation aus unser Freund Nick Parlante von der Stanford Universität, Professor in Computer Wissenschaft, die zusammen diese Vorschau setzen von dem, was auf diesem Mittwoch kommen. [VIDEO PLAYBACK] -Hey, Binky. Aufwachen. Es ist Zeit für Zeiger Spaß. -Was Ist das? Erfahren Sie mehr über Zeiger? Oh, gute sachen! [END VIDEO PLAYBACK] Sprecher 1: Das erwartet Sie am Mittwoch. Wir sehen uns dann. [VIDEO PLAYBACK] -Und Jetzt, Deep Thoughts, Daven von Farnham. -Warum Lernen wir C? Warum nicht A +? [Gelächter] [END VIDEO PLAYBACK]