>> David J. MALAN: Dies ist CS50 und Dies ist der Beginn der vierten Woche.
Und, Junge, ist Volkswagen in Probleme alles wegen der Software.
Lassen Sie uns einen Blick.
[VIDEO PLAYBACK]
-Cars, Die intelligentesten Charaktere in den Fast and Furious Filme.
Diese Woche deutsche Auto Volkswagen fand sich
in der Mitte von einem Skandal potentiell kriminellen Proportionen.
>> -Volkswagen Wird Verstrebungen für Milliarden Geldstrafen, möglichen Strafanzeigen
für seine Führungskräfte, wie das Unternehmen entschuldigt sich
Rigging 11 Millionen Autos an helfen, sie zu schlagen Emissionsprüfungen.
>> -Bestimmte Dieselmodelle waren mit anspruchsvollen Software entwickelt,
dass benutzte Informationen, einschließlich der Position des Lenk- und Fahrzeug
Beschleunigung zu bestimmen, war das Auto unterziehen Abgasuntersuchung.
Unter diesen Umständen ist der Motor würden toxische Emissionen zu reduzieren.
Aber das Auto war in den Bypass-rigged dass, wenn es angetrieben wird.
Emissionen erhöht 10 bis 40 fach über akzeptable EPA Ebenen.
>> [END PLAYBACK]
>> David J. MALAN: Also lassen Sie uns Schau dir das an
und sehen Sie genau, wie diese umgesetzt werden könnten,
und wie könnte dies Auswirkungen auf so viele Autos wie diese.
Also in meiner Hand sind hier die Presse Mitteilung, wurde von der EPA-- ausgestellt
die Umwelt Schutzbehörde die
ist die Regulierungsbehörde uns, dass Griffe Umweltbedenken
und dann wird die tatsächliche Rechtlicher Hinweis, die war
Nachricht an die Volkswagen vor wenigen Tagen.
>> Also das EPA schreibt, und offenbart sich jetzt öffentlich, eine hoch entwickelte Software
Algorithmus zu bestimmten Volkswagen-Fahrzeuge erfasst
wenn das Auto unterziehen offizielle Abgasuntersuchung
und wendet sich voller Emissionen steuert nur während des Tests.
Die Wirksamkeit Diese Fahrzeuge Verschmutzung
Emissionssteuereinrichtungen ist deutlich während den normalen Fahrbetrieb reduziert
Situationen.
Dies führt zu Autos, die das erfüllen Standards im Labor oder Test
Station, aber im Normalbetrieb emittieren Stickstoff oxides-- oder NOx--
bis zu 40-fache der Standard.
Das von Volkswagen entwickelte Software ist ein Zitat unquote, Abschalteinrichtung,
wie von der Clean definiert Air Act in den USA.
>> Sie gehen zu sagen, dass die EPA und eine andere Agentur
deckt die Abschalteinrichtung Software nach der unabhängige Analyse
von Forschern an der West- Virginia University.
NOx Verschmutzung trägt zur Stickstoffdioxid, Ozon in Bodennähe,
und Feinstaub.
Exposition gegenüber diesen Schadstoffe verknüpft wurde
mit einem breiten Spektrum von schwerwiegende Auswirkungen auf die Gesundheit,
einschließlich der erhöhten Asthma- Angriffe und andere Atemwegs
Krankheiten, die schwerwiegend genug sein kann, um Menschen ins Krankenhaus zu schicken.
Die Exposition gegenüber Ozon und Feinstaub hat auch
wurde mit vorzeitiger zugeordnet Tod durch Atem verwandten
oder Herz-Kreislauf verbundenen Auswirkungen.
Kinder, ältere Menschen, Menschen mit vorbestehenden Atemwegserkrankungen
Besonders gefährdet sind für gesundheitlichen Auswirkungen dieser Schadstoffe.
>> Es genügt also, es ist ziemlich ernst.
Und lassen Sie uns weiter gehen zu lesen nur ein weiterer Auszug
und dann werden wir ein Blick in die zugrunde liegenden Auswirkungen
Dies im Zusammenhang mit einem Auto.
Insbesondere Volkswagen hergestellt und installiert
Software in der sogenannten elektronische Steuerung
module-- oder ECM-- von Diese Fahrzeuge, die spürte,
wenn das Fahrzeug wurde getestet Einhaltung der EPA-Emissionsstandards.
Basierend auf verschiedenen Eingaben einschließlich der Position des Lenkrads, Fahrzeug
Geschwindigkeit, die Dauer des Motors Betrieb und Luftdruck,
Diese Eingänge gerade verfolgt die Parameter
der für verwendet Federal Test Procedure Emissionsprüfung für EPA certification
Zwecke.
>> Während der Emissionsprüfung EPA, die Fahrzeuge ECM-Software
lief Software, die hergestellt konformen Emissionsergebnisse.
Zu allen anderen Zeiten, die Fahrzeug ECM-Software
lief eine separate Straße Kalibrierung, die reduziert
Die Wirksamkeit der Gesamtabgasreinigungsanlage,
insbesondere die selektive katalytische Reduzierung der Lean NOx trap--
was wir über gleich sehen.
Als Ergebnis der NOx-Emissionen um einen Faktor von 10 bis 40-fache
über den EPA-konform Ebenen abhängig von der Art des Fahrzyklus.
>> Also, was das wirklich bedeutet, und die Quellcode der Software Lauf
auf den Volkswagen hat nicht noch öffentlich bekannt war,
das heißt, effektiv, diese Äquivalent ist irgendwo im Inneren
der Volkswagen-Code.
Wenn Sie werden derzeit getestet, und wenn das Auto erkennt bestimmte Umweltfaktoren
wie der Lenkrad Position oder der Bewegung
oder deren Fehlen des Autos oder eine beliebige Anzahl von anderen Faktoren,
die derzeit die Hypothese aufgestellt werden Teil dieser Formel,
wenden sie sich einfach an Voll Emissionen zu kontrollieren.
Mit anderen Worten, beginnen sie emittierende weniger der Schadstoffe.
>> Else, in jeder anderen Situation, wenn es nicht als nachgewiesen
im Labor, sie einfach nicht.
Und so können Sie dies in mehr vereinfachen Betonpseudocode mit etwas,
so was.
Wenn die Räder drehen, aber die Lenkrad nicht, suggestive
dass der Wagen auf einigen Art von rotierenden Zylinder
aber in einer Art Lager getestet wird,
dann als verhalten EPA möchte, dass Sie.
Sonst nicht.
Werfen wir also einen Blick in einem kurzen Video,
wirft einen Blick auf das, was die Auswirkungen sind dies tatsächlich mechanisch.
>> [VIDEO PLAYBACK]
>> -In Den letzten Freitag das EPA angekündigt, dass einige Volkswagen Audi Autos zwischen 2009 gemacht
und in diesem Jahr wurden unter Verwendung von eine sogenannte Abschalteinrichtung
zu umgehen Emissionsgesetze entworfen, um die Luft sauber zu halten.
Aber was bedeutet das genau?
>> Nun, moderne Autos haben Dutzende von Computern in ihnen.
Und einige von diesen Computern zur Koordinierung der Funktionen
des Motors für eine optimale Leistung gleichzeitig dafür,
daß es nicht zu viel Müll die aus dem Abgasrohr.
Sie haben tatsächlich gearbeitet auf diese Weise seit Jahrzehnten.
Grundsätzlich jeder Teil eines modernen Automotor
einen Sensor oder Controller auf sie, und diese Computer
werden im Daten tausende Lesen mal pro Sekunde Anpassungen
wie das Verhältnis von Brennstoff zu Luft das wird in die Zylinder.
>> Diese betrügen Volkswagen und Audi-Modelle sind Diesel,
und Dieselmotoren noch eine weitere wirklich wichtigen Computer
gesteuerten Parameter, das ist die Menge an unverbranntem Kraftstoff gehen
in dem Abgas.
Nun, das klingt schlecht.
Klingt nicht wie Sie wollen unverbrannter Kraftstoff in den Auspuff gehen.
Aber im Fall von a Diesel, etwas, müssen Sie
genannt NOx-Falle, die ein Gerät ist, dass absorbiert und Fallen für Stickoxide
dass Schadstoffe Das wäre ansonsten in die Atmosphäre gehen.
Und die Wirkung des NOx-Fallen mit unverbrannten Kraftstoffs verbessert.
So Abschalteinrichtung ist ein spezielles Programm innerhalb dieser Computer, die es schaffen kann
schauen, wie das Auto trifft Emissions Standards, auch wenn es nicht tut.
Volkswagen hatte ein Problem auf seinen Händen.
Sein Dieselmotoren bekannt waren für immer große Kraftstoffverbrauch,
aber die NOx-Falle funktioniert nur gut wenn mehr Kraftstoff verwendet wird.
So würde das Auto zu erfassen, mit diesen Abschalteinrichtung,
wenn es wurde ein Emissions Test, wäre es mehr Kraftstoff zu verwenden,
gut machen den NOx-Speicher-Arbeit, Emissionen wäre in Ordnung.
Aber dann sind Sie auf dem Weg zu bekommen, das Gerät erlischt, bist du brenn weniger Kraftstoff
aber du bist so viel wie 40-mal setzen mehr Schadstoffe in die Atmosphäre.
Aber wie zum Teufel tat das Fahrzeug, dass es
wobei für die Einhaltung der Emissionsgrenzwerte untersucht?
Die EPA sagt, es war ein ausgeklügeltes System, das die Dinge überprüft
wie Lenkradstellung, Geschwindigkeit, wie lange der Motor eingeschaltet war,
und auch der Atmosphärendruck.
In anderen Worten, es war keine Möglichkeit, dies war ein versehentliches
weil die Software war sehr sorgfältig konzipiert, um zu erfassen
eine offizielle Abgasuntersuchung.
Das ist einige ziemlich ernst Täuschung und das ist,
warum Volkswagen ist in wie ernsthaften Schwierigkeiten.
In der Tat, deren CEO, Martin Winterkorn, nur trat.
>> Also, was passiert als nächstes?
Nun, wenn Sie eine der halbe Million sind Diesel Jettas, Beatles, spielt Golf, Passat,
oder Audi A3s erfolgt, die gute Nachricht ist, ist
dass Ihr Auto ist immer noch sicher zu fahren.
Sie müssen nicht, sie wegräumen bis Volkswagen gibt einen Rückruf.
Aber irgendwann sind sie wahrscheinlich gehen zu müssen,
um die Software in Ihrem Auto zu aktualisieren.
Wenn das passiert, die Dir vielleicht erhalten weniger Meilen pro Tank.
Rechtsanwälte sind bereits Getriebe für Sammelklagen
so Besitzer könnten ausgeglichen bekommen irgendwann einmal.
Aber das ist nicht zu gehen jederzeit geschehen bald.
>> [END PLAYBACK]
David J. MALAN: Also eigentlich wirft ein interessantes Gesamtbild Frage
als zu vertrauen.
Recht?
Alle von uns haben iPhones oder Androids oder etwas in der Tasche am ehesten
in diesen Tagen, oder Laptops auf den Schoß, die sind
Ausführen von Software gemacht von Apple und Microsoft
und Trauben von anderen Unternehmen.
Aber wie wir wissen, dass das tun, was Diese Softwareprodukte tun
ist eigentlich, was diese Unternehmen sagen, sie tun?
>> Zum Beispiel, wer ist zu sagen, dass jedes Mal, wenn Sie
einen Anruf tätigen auf Ihrem iPhone oder Android-Handy oder dergleichen,
dass diese Telefonnummer ist auch nicht an Server irgendeines Unternehmens hochgeladen
weil einige Programm, das Sie haben geschrieben, ob es sich um das Betriebs
System selbst wie iOS oder Android, oder weil Sie heruntergeladen haben
einige Dritten App dass irgendwie hört
für alles, was Sie mit der Eingabe in bist, oder alles, was Sie eigentlich sagen.
Woher wissen Sie, dass, wenn Sie Kerle laufen Clang
Oder zum Kompilieren Ihrer eigene Software in CS50, wie
Sie arbeiten Mitarbeiter, die CS50 ist, über die CS50-Bibliothek,
war nicht die Protokollierung jedes Zeichenfolge, die Sie je bekommen habe
oder jeder Zoll Sie je bekommen haben?
Nun, man könnte sicherlich freuen auf den Quellcode für etwas
wie der CS50-Bibliothek, die Sie könnte auf den Quellcode schauen
für Linux-Betriebssystem am CS50 IDE ausgeführt.
Aber eine erstaunliche Präsentation wurde im Jahr 1984 gegeben
Der Erhalt eines Turing Award durch eine sehr berühmter Informatiker bekannt
as-- namens Ken Thompson, die erhielt den Turing Award die
ist eine Art von Computer-Wissenschaft Nobelpreis, wenn man so will,
für seine Arbeiten über eine Betriebssystem aufgerufen
Unix, die sehr ähnlich ist Geist, was wir verwenden, was Linux.
Und die Frage im fragte er seine Dankesrede im wesentlichen
zur Festlegung des Rahmens für die Jahre und Jahre der Diskussion
um Vertrauen und Sicherheit, das war.
In welchem ​​Umfang sollte man Vertrauen ein Aussage, dass eine program-- ein Stück
von software-- frei von Trojanern?
Vielleicht ist es wichtiger, zu vertrauen die Menschen, die die Software schrieb.
>> Und in der Tat, wir verknüpft haben um dem Gerede, dass er
hat bei der Annahme dieser Auszeichnung in den 80er Jahren am CS50-Website
unter der Seite Vorlesungen für heute.
Denn das, was Sie sehen, ist, dass er tatsächlich gibt
ein relativ einfaches Beispiel, wie auch ein Compiler Clang wie oder was auch immer
Compiler andere haben in Vergangenheit, was ist, wenn in den Compiler wir eingebettet
uns verwenden ist ein wenig, wenn Bedingung, die im wesentlichen sagt,
wenn Sie feststellen, dass dieser Code wird mit die GetString-Funktion oder die getint
Funktion, gehen Sie vor und stecken eine Hintertür oder ein Trojaner
derart, dass das Programm Jetzt hat ein paar Nullen
und diejenigen, die etwas bösartiges zu tun.
Anmeldung alle Ihre Tastatureingaben, das Hochladen, dass Daten
bis zu einem gewissen Server oder wirklich etwas.
>> Und was Ken Thompson fährt fort, in seinem Vortrag zu tun
ist es, dass zu demonstrieren, auch wenn Sie Zugriff auf die Quelle haben
Code eines Compiler, böswillig sein könnte, dies zu tun,
es nicht, weil Rolle spielt gibt es dieses Huhn und das Ei
Realität der Vergangenheit viele Jahre, wobei Compilern
werden verwendet, um sich selbst zu kompilieren.
Mit anderen Worten, Weg zurück, wenn jemand hatte, und der erste Compiler geschrieben.
Und danach jedes Mal, wenn sie aktualisiert haben ein Compiler durch eine Änderung seiner Source-Code,
Hinzufügen von Funktionen und neu zu kompilieren für Leute wie uns zu bedienen, gut,
sie sind mit den alten Compilerversion
die neue zu kompilieren Compilerversion.
Und wenn Sie einen Blick zu nehmen im Gespräch, das er gab,
Sie, denn da zu sehen dieser Zirkularität
können Sie sogar Bugs oder Trojanische Pferde in der Software eingebettet
wir verwenden.
Und selbst wenn Sie bei der Suche Quellcode für die Programme,
es vielleicht nicht einmal klar sein, weil der Betrug ist eigentlich
in einigen älteren Version eines Compiler, der seitdem gewesen
Einspritzen der Bedrohung in unsere Software.
>> Das ist nur zu sagen, wir kann es wirklich nicht und sollte nicht
Vertrauen Software auf unseren Laptops mit oder Telefone oder eine beliebige Anzahl von Stellen.
Und in der Tat, später in diesem Semester, wenn wir anfangen, über Web-Programmierung im Gespräch
und tatsächlich mit dem Bau Web-Anwendungen selbst,
wir werden über diese zu sprechen Bedrohungen und andere.
Jetzt könnten Sie fragte mich, und bemerkt, , dass es einen kleinen kleinen Darth
Vader in die Clips, die The Verge war es, die
über Volkswagen. Wenn Sie noch nie gesehen, ich
dachten wir aufhellen sollte die Stimmung, denn das ist alles,
sehr bedrückend und beängstigend.
Ich werde zurückblicken Super Bowl 2011
wenn ein Spot von Volkswagen-- und dies
fast macht sie sympathisch again-- zum ersten Mal im Fernsehen ausgestrahlt.
Es ist die 60-Sekunden-Clip dass ich denke, Sie genießen.
[VIDEO PLAYBACK]
[MUSIC - Thema aus "Star Wars"]
[Hund bellt]
[Auto beginnt]
[END PLAYBACK]
David J. MALAN: Ja.
Ich war nur die Überprüfung.
Das Auto ist auf der Liste der Verstöße.
Gut.
Also schauen wir uns einige Pseudocode einen Moment vor.
Und hier ist ein größeres Ausschnitt aus Pseudocode
dass wir ein paar Mal bisher gesehen.
Und lassen Sie verwenden dies ist eine Gelegenheit nun auf eine neue Programmiersprache vorstellen
Technik, die wir getan haben siehe algorithmisch
letzte Woche, als wir blickte merge sort.
Aber lassen Sie uns zu formalisieren und sehen, wie wir sie im eigentlichen Code verwenden könnte,
und dann werden wir diese verwenden Technik auf dem Weg die meisten
wahrscheinlich einige andere Probleme zu lösen.
>> So war eines der ersten Programme wir je geschrieben hat, wenn auch in Pseudocode.
Und was dieses Programm konnten wir natürlich tun
war es Mike Smith in einem Telefonbuch zu finden.
Insbesondere Linien acht merken und 11, die diese Sprunganweisung hatten.
Und in der Tat gewisse Sprachen, darunter C,
tatsächlich haben ein Anweisung, die buchstäblich ist
gehen Sie zu, dass ermöglicht es Ihnen, Sprung zu einer bestimmten Zeile.
Es ist in der Regel auf, weil runzelte die Stirn es sehr leicht missbraucht werden können
und schon können Sie Ihre springen Programm ganz über dem Platz, im Gegensatz
unter Verwendung der Art von Logik und der Steuerfluss
dass wir bisher mit nur verwendet, Schleifen und Bedingungen und dergleichen.
>> Aber wir können diesen Algorithmus zu vereinfachen in Pseudocode wie folgt.
Anstelle dieses iterative oder Looping Ansatz
wo wir immer wieder zurück und hin und zurück in die Linie drei,
warum machen wir nicht nur irgendwie Punt und mehr in der Regel sagen, im Einklang sieben und 10,
nur diese beiden zu ersetzen Leitungspaare mit,
else if Smith früher in dem Buch wir werden
Suche nach Mike in der linke Hälfte des Buches.
Else, wenn Smith wird später im Buch, suchen Sie nach Mike in die richtige
die Hälfte des Buches.
Und bemerken bereits die Rundheit.
Recht?
Ich suche Mike in das Telefonbuch und dann
Ich schließlich traf vielleicht Linie sieben oder vielleicht Linie 10
und meine Anweisung, mich ist Suche Mike in die Hälfte des Telefonbuchs.
Nun, wie kann ich für Mike zu suchen?
Ich bin in der Mitte Suche nach Mike, warum
Sie Art von Zusendung im Kreis?
Aber das ist in Ordnung, denn was ist geschieht auf die Größe des Problems
wie in Zeile 7 und 10 geschrieben?
Wir sind nicht einfach nur sagen Suche Mike, suchen Sie nach Mike.
Wir sagen, was gesagt?
Suchen Sie nach ihm in der linken Hälfte des die rechte Hälfte, die wirksam ist,
die Hälfte der Größe des Problems.
So ist es OK, dass wir Art sind ihre Beteiligung an dieser Rund,
Diese Zirkelschluss, weil zumindest sind wir
wodurch das Problem geringer.
Und schließlich werden wir zu erreichen dass so genannte Basis Fall,
wir müssen nur eine Seite left-- wie unsere freiwilligen letzte Woche
did-- wir hatten eine Seite nach links und dann tun wir nicht
muss sich immer auf der Suche nach Mike Smith weil er entweder auf dieser Seite
oder ist er nicht.
>> Wie können wir diese Idee umzusetzen, die diese Art von Rundheit im eigentlichen Code?
Nun, wir können eine Technik nutzen das ist in der Regel als Rekursion bekannt.
Und wir dies in die gesehen haben Pseudocode für Mergesort letzte Woche.
Daran erinnert, daß dies das Pseudocode für merge sort.
Es ist wohl noch einfacher als Blase oder Auswahl oder Insertion Sort
nur in Bezug auf die Einfachheit mit dem man es ausdrücken.
>> Aber das ist, weil wir sind eine Art kreis
sagen, die Suche nach etwas, bei der Suche nach es wieder.
Aber wir sind auf der Suche entweder die linke Hälfte und die rechte Hälfte
und dann schließlich sind wir Zusammenführen in diesem Fall.
Aber auch hier, mit diese beiden Sortierlinien,
haben wir wieder diese Idee der Rekursion.
Und konkret, was das bedeutet, im Zusammenhang mit einem Algorithmus,
ist, dass ein Algorithmus ist rekursiv wenn es verwendet oder nennt sich.
>> Oder in Form von C, ist eine Funktion, recursive-- eine Funktion namens
foo ist rekursiv, wenn foo, irgendwo in den Quellcode,
ruft die Funktion foo selber.
Und das ist schlimm, wenn alle foo immer tut ist nennen sich immer wieder.
Es ist in Ordnung, wenn foo schließlich nicht mehr, ebenso wie merge sort, indem er sagte, warten Sie eine Minute,
wenn dieses Problem ist super klein ist, zum Beispiel,
oder fand ich, den ich Suche nur zurück.
Nicht rekursiv, nicht selbst zyklisch erneut aufrufen.
>> Und so lassen Sie uns einen Blick auf wie dies funktionieren könnte tatsächlich funktionieren.
Also werde ich nach vorne und öffnen gehen zwei Quellcode-Beispiele hier.
Einer davon wird als Sigma-0.
Und dies ist nicht überhaupt rekursiv, aber lassen Sie uns
einen Blick auf, was das Programm macht.
Ich habe alle abgestreift Kommentare von ihm aber alle
des Quellcodes auf der CS50 Webseite Kommentare, wenn Sie
möchte es später noch einmal durchlesen.
Und lassen Sie uns ein paar der Vernunft prüft hier.
>> So dass am Anfang der Code, haben wir gehören CS50.h.
Was bedeutet dies?
Warum ist es hier?
In Bezug auf die angemessene Laien.
Was tut es?
Ja.
>> ZIELGRUPPE: Damit getint Funktion arbeitet.
>> David J. MALAN: Damit die getint Funktion arbeitet.
Weil Innere dieser Datei CS50.h, die
wir werden schon bald in zu sehen Bezug auf den Quellcode,
hat eine Reihe von Funktionen declared-- getint, GetString,
und eine Reihe von Andere-- und es sei denn, haben wir eigentlich, dass Zeile enthalten,
der Compiler Clang nicht geht, zu wissen, daß es existiert.
Und Gleiches gilt für Linie zwei, wo int definiert
printf, die eine Funktion ist Wir halten mit ziemlich viel.
Nun Reihenvier scheint ein wenig flippig denn es ist nur ein Motto.
Es hat ein Semikolon, keine geschweiften Hosenträger, kein Code darin.
Aber was haben wir als dieses Ding in Wochen Vergangenheit?
Ja.
So ein Prototyp.
Und warum haben wir ein Prototyp, der scheint,
ein wenig redundant in der Regel, weil wir in der Regel
siehe die Funktion erneut später in der Datei, nicht wahr?
Also, warum wir have-- Sie gerade sind Kopf kratzen, aber ich nehme es.
Ja.
>> ZIELGRUPPE: [unverständlich] Funktion nach der Haupt.
David J. MALAN: Genau.
Damit der Compiler weiß, dass Sie wird schließlich zu definieren oder zu implementieren
dass nach der Hauptfunktion, vermutlich.
So Clang und die meisten Compiler sind Art von dumm
und sie werden nur wissen, was Sie ihnen sagen.
Und wenn Sie verwenden möchten, eine Funktion namens Sigma,
Sie den Compiler besser lehren dass es existiert im Voraus.
>> Jetzt, Haupt selbst, auch obwohl es eine Reihe von Linien,
ist ziemlich hoffentlich kennen mittlerweile.
Es ist ein Do While-Schleife bekam , deren Zweck im Leben
hier offenbar um eine zu bekommen positive ganze Zahl von dem Benutzer.
Und nur halten ihn belästigen oder sie, bis sie zusammenarbeiten.
Dann in Zeile 16 Ich habe eine interessante Anruf.
IntAnswer.
Die auf der linken Seiten gibt mir eine Int
genannt store-- können Answer-- die gehen, um zu speichern ist, offenbar,
der Rückgabewert von Sigma.
So Sigma ist nur ein beliebige, aber aussagekräftigen Namen
dass ich auf eine Funktion gegeben , deren Zweck im Leben
ist es, einen argument-- nehmen wir werden es in diesem Fall-- nennen N
und nur um den Betrag dieser Zahl zu nehmen Plus jede positive Zahl, das ist
kleiner, als es.
>> Also, wenn ich übergeben Sie die Nummer 2 auf sigma, möchte ich hinzufügen 2 plus 1
zzgl 0-- nicht 0--, so dass gibt mir 3.
Wenn ich pass in 3 bis sigma, Ich möchte haben 3 plus 2 plus 1, das gibt mir 6.
Und so weiter.
So fügt es gerade alle Zahlen, die kleiner als oder gleich ist.
>> Nun, hier unten Ich werde einfach zum Ausdrucken die Antwort.
So als eine schnelle Plausibilitätsprüfung, lassen Sie uns machen Sigma 0-- dot Strich Sigma 0--
und lassen Sie mich in 2 geben.
Und ich in der Tat erhalten 3.
Lassen Sie mich geben 3.
Ich in der Tat erhalten 6.
Und wenn jemand die Mathematik schnell tun können, wenn ich 50 was soll ich bekommen?
>> ZIELGRUPPE: [unverständlich].
David J. MALAN: Nun, nein.
Aber 1275, das ist ziemlich nahe.
Also das ist das Ergebnis von 50 zu tun Plus 49 Plus 48 sowie 47 und 46
bis hinunter auf 1.
Also das ist alles, Sigma tut.
Aber mal sehen, wie wir implementiert es jetzt.
So ist hier unten die Funktion selbst.
Und dies scheint nicht zu haben etwas mit Rekursion noch zu tun.
In der Tat, verwenden wir ein alte Schule-Technik.
Ich Initialisierung einer Variable Summe Null ist, dann habe ich eine foreloop hier,
und ich erklärte ein Int genannt I, Gleichsetzen 1--
aber ich konnte es gleich eingestellt Null, aber da ich tue hinaus
wen kümmert das, wenn es null oder eins.
Es wird keine Wirkung haben.
>> So bin ich, so lange ich es Iteration weniger als oder gleich m, die
ist das Argument, die übergeben wurde.
Und dann habe ich einfach weiter Erhöhen I. und Einsicht
der Schleife alles, was ich tue, ist Summe tut zzgl gleich I. Und das ist Absicht.
Ich will nicht zu tun, in diesem Fall wie Summe plus plus.
Ich möchte eigentlich hinzuzufügen der aktuelle Wert des I
die wird immer größer und größer und größer auf die Lauf tally.
>> Und dann habe ich Summe zurück.
Und so Antwort bekommt die Wertsumme.
Und dann habe ich auch ausdrucken.
So gibt es eine Gelegenheit, hier, obwohl, um Art zu vereinfachen
dieser Code konzeptionell und die Art der Schlag einer ist
dagegen in Bezug auf die Einfachheit, auch wenn es
dauert eine Weile, um zu sortieren der zu schätzen wissen, warum dies
ist mächtig in diesen kleinen Beispielen.
Hier ist sigma one-- so der zweite Version dieses Codes.
Alles bis oben ist identisch, so dass gleiche Geschichte gilt nach wie vor.
Aber jetzt einen Blick auf die lassen Umsetzung der Sigma die
Ich habe auf nur diese schnitzte lines-- vier Zeilen Code, wirklich,
plus einige geschweiften Klammern und Leerzeichen.
>> Aber was mache ich?
Wenn m kleiner als oder gleich ist Null, muss ich Art von hand
dass Super einfachen Fall.
Und wenn du mich übergeben null oder nichts Negativ, das nur komisch ist,
Ich werde einfach beliebig aber beständig zurück Null.
Ich will nicht, diese Sache zu erhalten in einige seltsame unendlichen
Schleife aufgrund eines negativen Wert.
Also ich bin einfach nur sagen, wenn Sie mir geben Null oder weniger, ich bin der Rückkehr Null.
>> Aber das ist gut so, denn das ist, dass einzelne Seite des Telefonbuchs
, was übrig bleibt.
Ich Abbeißen ein sehr spezifisches Problem und nicht etwas, rekursiv aufrufen.
Aber in der Leitung 31, was ich scheinen zu tun?
Die Klammern sind nur halten Dinge hoffentlich ein wenig klarer.
Aber alles, was ich tue, ist, ich bin Rückkehr M-- unabhängig
Sie mich- und der Hand Wert M-- sorry,
plus dem Wert der Sigma-m minus 1.
Also, was bedeutet das?
Wenn Sie mir die Nummer 3 als Eingang zu geben, die Antwort Ich möchte schließlich erhalten
6, weil 3 plus 2 plus 1 gibt mir 6.
Aber wie kann ich darüber nachdenken, wie dieser Code ausgeführt wird?
Das erste Mal, ich nenne Sigma und ich übergeben Sie den Wert 3,
das ist, wie gesagt, auf einem Stück Papier, hier ist der Wert 3
und ich habe dies als sigma verabschiedet.
3 ist natürlich nicht kleiner als 0, so die IF-Bedingung gilt nicht.
Die anderen nicht.
Also, was soll ich tun?
Ich möchte m zurück, das ist, 3 plus Sigma von m minus 1.
Also lassen Sie mich verfolgen, diese zu halten.
Ich werde diese setzen Stück Papier nach unten.
Und welchen Wert, zu sein klar, werde ich weitergeben
in Sigma an diesem Punkt in der Geschichte?
Welche Nummer?
2, oder?
3 minus 1 ist 2.
Also brauche ich nur ein wenig Zettel hier.
So, jetzt Sigma wird immer wieder genannt.
Und ich absichtlich gesetzt haben Diese nach unten, weil es
eine Art, wie Pausieren dass Version der Geschichte
denn jetzt bin ich fokussierten auf Signal m minus 1.
So war m 3, m minus 1 ist 2.
So, hier ist 2, die ich geführt worden.
2 ist offensichtlich nicht weniger als 0, so daß Fall keine Anwendung findet.
Else Ich kehre m, was das ist Sache, zzgl Sigma von welchen Wert?
Also, wenn der Sigma-1--, weil m jetzt 2 so 2 minus 1 ist 1.
So, jetzt muss ich nur den Wert 1.
Ich bin vorbei nur die Anzahl 1 an den Funktions sigma--
oder mich hier-- so 1 ist natürlich nicht kleiner als Null ist, noch nicht anwendbar ist.
>> Else Rückkehr 1 plus Sigma von was?
0.
Also lassen Sie mich nur daran erinnern, dass.
Ich komme, um zu bekommen, dass später.
Jetzt werde ich voran und jot gehen unten die Nummer 0, weil das ist,
mein Argument bzw. Parameter.
Ich bin die Nummer 0 übergeben und schließlich dieser Prozess
der gerade wiederhole mich ad nauseum nicht aufhören, weil das, was
ich sofort tun, wenn ich sehe, dieses 0?
Ich kehre Null.
So, jetzt haben Sie, um die Geschichte zurückzuspulen.
>> Wenn ich nun rückwärts in der Zeit, was war die letzte Sache,
Ich tat, wenn Sie buchstäblich waren Zurückspulen eines Videos?
Ich werde zu holen die jüngsten 1 und das gibt mir 1 plus 0 1.
Wenn ich halten das Zurückspulen Geschichte, das wird mir zu geben
2 plus das Laufwert, der 1 ist.
Also das ist, 3.
Und dann werde ich Zurückspulen halten.
Als ich das erste legte die Zahl 3-- so 3 plus 3 gibt mir 6.
>> Und jetzt, wenn Sie zurückgespult habe das Video bis zu diesem Zeitpunkt,
Das war die sehr erste Frage, fragte ich.
Wenn verfehlt 3, was Sigma von 3?
Es ist in der Tat 6, die Summe aus Alle diese Zettel.
Also, wenn das dauert eine Weile, um Wendet euer Gehirn um, das ist in Ordnung.
Aber bedenken Sie, es war ein little-- es war sehr bewusste, dass ich gestapelt
diese Zahlen auf der jeweils anderen Seite.
Es ist ein bisschen wie mit einem memory-- einen Rekord in der Zeit,
wie ein Gaswäscher in einem Video, dass ich in der Tat in zurückspulen.
Und wir werden zurückkommen daß Metapher in nur ein wenig.
>> Zunächst aber es stellt sich heraus, dass es eine Menge von Geeks und lustigen Menschen,
Ich schätze, bei Google.
Würde jemand, der sehr ist gut googeln Geist
kommen nur für einen Augenblick und mir helfen, etwas zu suchen?
Sehr, sehr zurückhaltend.
Jemand, der noch nie ist kommen vor, vielleicht.
OK.
Ja?
Komm schon.
Komm runter.
Wie heißen Sie?
>> SAM: Sam.
>> David J. MALAN: Sam, komm nach unten.
Dies ist Same.
Nett, dich zu treffen.
Hallo.
Komm rüber.
Also alles, was ich brauche, was Sie tun, wenn Sie könnte, Sam, hier ist Google.
Können Sie nach dem Begriff Rekursion zu suchen?
Verderben Sie nicht.
>> Und jetzt let's-- ja.
OK Klicken Sie auf, dass.
Bessere klicken, dass.
Ahh, get it.
Nein?
OK.
Lassen Sie uns so tun, ein paar andere.
Nicht so sehr damit verbundenen akademisch hier aus haben Sie aber
immer gesucht Google für Anagramm?
>> SAM: Nein
>> David J. MALAN: OK.
Suchen Sie nach Anagramm statt Rekursion.
Wie wäre es schief.
Sie jemals schief gesucht?
Jetzt ist dieses ein wenig schwer zu sehen aber hoffentlich everything's-- OK.
Es ist nur du und ich genießen dieses.
OK.
>> So endlich, diese one's-- es ist ein wenig schief.
Jetzt tun Sie eine Fass-Rolle.
Wunderbar.
Gut.
Großes Dankeschön an Sam.
Bitte schön.
Vielen Dank.
>> Also, was los ist in allen dieser dumme Beispiele?
Also wirklich, unter der Haube des Millionen von Zeilen Code von Google
anscheinend ein paar dumme IF Bedingungen, die im wesentlichen
Überprüfen, ob der Benutzer in diesem Ausdruck eingegeben haben,
tun etwas, das fand wahrscheinlich eine nichttriviale Menge an Zeit
um nur zu implementieren amüsant auf diese Weise.
Aber das ist alles, es kocht bis auf unter der Haube.
Aber natürlich Rekursion ist der geekier
B. unter den besonderen Tricks.
Und sicherlich gibt es andere gibt, als auch, dass wir vielleicht noch nicht einmal
nur noch nicht entdeckt.
>> Also werfen Sie einen Blick, oder zu prüfen, jetzt das folgende Programm,
und sicherlich packen jede von diesen auf dem Weg nach draußen.
Ich werde weitermachen und öffnen, ein Programm, das ist
werde versuchen, zwei Werte zu tauschen.
Aber bevor wir dorthin gehen, lassen Sie uns dies tun.
Könnten wir bekommen einen weiteren Ehrenamtliche Arbeit, ich denke?
Möchten Sie freiwillig?
Nein?
Komm auf.
Gut.
Also Ihr Name ist was?
>> LAUREN: Lauren.
>> David J. MALAN: Lauren.
Kommen Sie auf, Lauren.
So Lauren wird wie folgt hier in Frage gestellt.
Nett, dich zu treffen.
So Lauren hat sich hier vor ihre beiden leeren Becher.
Und wir haben einige Orangen Saft und etwas Milch
und wir werden zu gehen die folgende voran und tun.
Wir sind gerade dabei, diese zu füllen.
Ein paar Unzen Milch her und lassen Sie uns füllen Sie ein wenig Orangensaft hier.
>> Und vor allem der diese Zuschauer,
tauschen Sie die beiden Werte dieser Becher.
Setzen Sie den O-Saft in der Milchschale und die Milch in der Tasse Orangensaft.
Wie würden Sie das tun, wenn man sich gab Haus und hatte Zugang zu anderen Lieferungen?
LAUREN: Legen Sie es in eine Tasse.
David J. MALAN: OK.
Lassen Sie uns also eine temporäre Variable, wenn wir wollen.
Und gehen Sie jetzt und umzusetzen Diese gleichen Swapping Verfahren.
So gut.
Wir haben OJ in den temporären setzen variable, Milch in die ABl variable,
und nun der temporären Variablen in den Milch variabel.
OK.
Also sehr gut bisher.
So stellt sich out-- halten, dass dachte für einen Moment.
Hier, um nur Aussenseiter es ein wenig, diese würde die entsprechende C-Code sein
dass wir einfach implementiert.
Wir hatten zwei Eingänge a und b, die beide welche wir einfach sagen, der Einfachheit halber sind
int ist.
Und hier bemerken, wenn ich will, um zu tauschen die Werte von zwei Variablen a und b,
wir in der Tat brauchen einen Mittelsmann, ein Zwischenvariable, eine temporäre Tasse,
in die das Gießen einer der Werte so dass wir einen Platzhalter für sie.
Aber der Code ist genau das, wie Lauren hier implementiert.
>> Nun, nur um einen zu bekommen wenig verrückter, stellt sich heraus,
dass Sie dies tun, ohne eine temporäre Variable ist.
Um dies richtig zu machen, aber wir gehen zu haben, um mit einigen der Chemie zu betrügen.
Wir haben einige Extrabecher hier.
So ist die nächste Sache, die aussieht wie Milch und Wasser perhaps--
oder Milch und OJ-- ist, wir haben einige Wasser, so dass wir diesen einen tanken
mit ein paar Unzen klares Wasser.
Das ist wahrscheinlich zu viel.
Ja.
Das ist definitiv zu viel.
Warte eine Sekunde.
>> Und jetzt haben wir Öl, das, soweit ich mich erinnere von der Mittelschule der Chemie-Klasse,
hoffentlich ist es nicht mit Wasser mischen.
Aber es ist irgendwie eine Art sieht aus wie Milch und ABl.
So, jetzt, ohne Verwendung eine temporäre Variable ist,
können Sie diese zwei Werte zu tauschen?
So Öle geht in die Wasserschale, Wasser geht in die Ölschale.
LAUREN: Keine anderen Cups?
David J. MALAN: Keine anderen Cups.
Und ich habe nicht wirklich getestet bevor dieses Jahres
so dass ich weiß nicht, ob dies tatsächlich funktionieren chemisch.
Das sollte eigentlich nicht passieren.
Funktioniert es?
Gut.
So trennen?
Gut.
Jetzt haben wir, um das zu bekommen Wasser in den anderen Becher.
Smarter Chemie Konzentratoren könnten wahrscheinlich tun dies besser als ich.
>> LAUREN: Das Wasser ist auf der Unterseite.
>> David J. MALAN: Die water--, das war was ist Schlüssel wir das letzte Mal tat dies.
Sie haben es in der richtigen Reihenfolge zu tun.
Ja.
Das ist ok.
Jetzt haben wir also zwei Tassen Öl.
OK.
Das ist ok.
Aber wenn diese chemisch bearbeitet als I--
>> LAUREN: Dies ist Wasser.
>> David J. MALAN: Das ist vor allem Wasser.
Gut.
Aber das ist immer noch die gleiche Tasse wie zuvor.
So gießen es-- probieren Sie es dort.
OK.
Dies ist eine gute Nutzung der Unterrichtszeit heute.
OK.
So wir-- jetzt schön.
Art.
Gut.
Also sehr gut.
Vielen Dank an Lauren.
Sehr gut gemacht.
>> Also, nur um deinen Verstand zu blasen, und das ist vielleicht etwas
mit, wenn Sie in CS50 ID gerne spielen, Sie können in der Tat, tauschen zwei Variablen
ohne Verwendung eines temporären Integer.
Und das ist das entsprechende C-Code.
Und wenn Sie von den letzten erinnern Mittwoch, haben wir, wenn auch nur kurz,
einige neue Operatoren in C. Und tut jemand daran erinnern, was die kleine Karotte
Symbol ist, das kleine dreieckige Symbol auf der Tastatur darstellt?
Was bitweisen Operator?
>> ZIELGRUPPE: EXOR.
>> David J. MALAN: EXOR.
Exclusive Or.
Also, wenn Sie wollen, nur so zum Spaß an zu Hause, um eine und b zwei beliebige geben
Werte wie jede eight-- und ich würde ein Acht-Bit-Wert zu wählen.
Wenn Sie dies mit 32 Bit zu tun, Sie werden sehr schnell langweilen.
Aber gerade geben ein ein Acht-Bit Wert, der ist, was auch immer, ein oder zwei,
und geben Sie b einen ähnlichen Wert.
Und dann unter Verwendung der Definition von XOR vom vergangenen Mittwoch,
anzuwenden, die Stück für Stück, jede diese acht Bits in jedem der a und b,
und dann tun Sie es genau pro diesem Code.
Und es ist nicht eine falsche welche Sie sehen, hier auf dem Bildschirm.
Es läuft darauf hinaus tatsächlich nach unten zu drei XOR-Operationen
und irgendwie magisch ein und b werden Positionen austauschen
ohne Informationen zu verlieren.
>> Also das Öl und Wasser Trick ist, die am nächsten realen Inkarnation
I zu imitieren denken konnte.
Aber es ist sicherlich einfacher, eine temporäre Variable,
wie in diesem Fall hier.
Und auch dies ist eine Gelegenheit, zu sagen, Auch diese Art von Mikro Optimierung,
als Informatiker sagen würde, während Art von Spaß
darüber nachdenken, wie Sie tat dies, ohne zu prahlen wie das Makeln mit einem zusätzlichen variablen,
es ist gar nicht so überzeugend.
Weil auf 32 Bit, wie zu sparen im Fall eines tatsächlichen int,
ist gar nicht so überzeugend auf einem System
Sie könnten mit zig Megabyte oder noch mehr solcher Speicher in diesen Tagen.
Und in der Tat, wenn wir zu einem späteren Problem Set
und Sie Rechtschreib umsetzen checker und du wirst
fordert, dies mit zu tun Diese so wenig RAM und so wenig
Zeit wie möglich auf die computer-- Sie noch
haben eine Woche zu implementieren es-- Du have-- werden Sie sein
herausgefordert, diese Ressourcen zu minimieren.
Und das ist wirklich das einzige veran diesem Semester
wo Sie aufgefordert werden, sich zu rasieren off sogar die beste Leistung
kostet nichts anderes.
>> So what-- wie können wir Dies in eigentlichen Code?
Lassen Sie mich gehen Sie jetzt und öffnen Sie ein Beispiel
dass gezielt aufgerufen Kein Tausch, weil es nicht der Fall ist
Tatsächlich tauschen die Variablen wie Sie eigentlich erwarten könnte.
Werfen wir also einen Blick.
Hier ist ein Programm, das keine CS50 hat Bibliothek los, nur Standard-I / O.
Jetzt haben wir einen Prototyp für Swap-up top, die gerade
bedeutet, es muss später festgelegt werden.
Und hier ist Haupt.
>> I willkürlich zugeordnet x und y, jeweils die Werte eins und zwei
nur weil sie klein sind und einfach zu denken.
Und dann habe ich nur ein paar printfs wo ich eine Plausibilitätsprüfung. x gleich 1 ist
und y 2 ist vermutlich was diese printfs werden sagen.
Also keine magische bisher.
>> Dann werde ich mit Anspruch drucken def, Swapping dot dot dot.
Ich werde die Swap nennen Funktion, vorbei in x und y.
Und lassen Sie uns für jetzt davon ausgehen, dass Swap exakt umgesetzt
wie es war vor einem Augenblick mit einer temporären Variablen.
Und so behaupte ich kühn, getauscht.
x ist jetzt dies und y ist jetzt, dass.
Aber die Datei natürlich heißt ohne Swap.
Lassen Sie uns also tatsächlich sehen, was passiert.
Wenn ich keine Swap und kompilieren do ./noswap, x 1 ist, y 2.
Dem Wechsel getauscht.
x 1 ist, y 2 ist.
So dass es scheint tatsächlich sogar fehlerhaft sein obwohl swap-- die nach unten scrollen now-- lassen
ist genau das umgesetzt pro Code, den ich vorgeschlagen, vor einem Augenblick.
So werden wir nicht hübsch machen mit der XOR-Sachen für jetzt.
Auch dies sollte nur Arbeit wie mit der Milch und Orangensaft,
aber es scheint nicht zu funktionieren.
>> Lassen Sie uns also wieder tun.
Vielleicht nur ich war nicht richtig auszuführen.
Also lassen Sie laufen keine Swap erneut.
Vielleicht I-- nicht.
So ist es einfach nicht funktioniert.
Lassen Sie uns also ein wenig Plausibilitätsprüfung.
Lassen Sie mich gehen Sie hier in Swap und fügen Sie einfach, warten Sie eine Minute,
a ist% i / n und lassen Sie uns Plug-in den Wert a.
Weil ich wirklich wollen, um zu sehen, was los ist.
Und in der Tat ist dies ein Debugging-Technik
dass Sie verwenden möglicherweise in Öffnungszeiten oder an schon nach Hause,
ähnlich der ersten Hälfte des Dan Armendariz Video in PSET3
wobei wir uns vorgestellt Druck def als eine empfohlene Technik zumindest
für einfache Fälle.
Lassen Sie mich gehen Sie vor und laufen zu lassen kein Swap wieder ./noswap.
>> Interessante.
So bemerken, was scheint, um wahr zu sein. x 1 ist, y 2, sondern eine 2 ist, wenn b 1 ist.
Also die beiden irgendwie bekam getauscht aber x und y sind nicht immer vertauscht.
So klar zu sein, was passiert, ist, hier oben habe ich x und y
und das sind lokale Variablen in der Umfang der wichtigsten, ich bin in x- und y-Weitergabe
vertauschen.
Nun, tauschen, als separate Funktion, ist frei, um ihre Argumente nennen
oder seine Parameter alles, was es will.
Foo oder Bar oder x oder y oder a oder b.
Nur um klar zu machen, dass sie nicht identisch mit X und Y per se,
Ich sagte, a und b haben.
Aber wir konnten sie alles, was wir wollen, rufen.
>> Und so sieht es aus wie Swap übergeben wird
x-- Alias ​​a-- und es ist übergeben Y- Alias ​​b.
Irgendwie diese drei Linien Swapping diese Werte genau
wie Lauren tat mit der Milch und ABl.
Aber wenn wir ausdrucken Die Werte a und b
sind in der Tat zu tauschen, aber x und y keine Änderung zu ihnen.
Daran erinnern, dass x und y sind hier oben.
>> So können wir dies über sehen Eine andere Technik auch.
Und auch dies ist eine Technik, in Problem eingebetteten Satz drei.
Lassen Sie uns weitermachen und tun dies in CS50-ID, wenn Sie nicht bereits haben.
Auf der rechten Seite haben wir haben diese Debugger Registerkarte.
Und wenn Sie diese öffnen, es gibt einige arkane Informationen
das ist bei Ihnen zunächst geworfen.
Aber lassen Sie uns necken dieses Apart wirklich schnell.
>> Eines finden Sie lokale Variablen.
Es stellte sich heraus, dass in CS50 IDE zu bauen, und eine Menge von Programmierumgebungen mehr
Im Allgemeinen wird ein Debugger.
Ein Werkzeug, das Ihnen, zu sehen, ermöglicht was los ist im Inneren Ihres Programms
ohne auf Hinzufügen greifen printfs und Kompilieren und Ausführen
und das Hinzufügen von printf und die Zusammenstellung und läuft, die bereits in der Bürozeiten
oder zu Hause, ist wahrscheinlich immer ziemlich langweilig.
>> So, hier, in nur einem Augenblick sind wir gehen, um in Echtzeit zu sehen,
die Werte unserer lokalen Variablen.
Wir werden auch in der Lage sein festgelegt sein, was sind Haltepunkte aufgerufen,
es Möglichkeiten in meinem Programm zu pausieren Bearbeitung an bestimmter Codezeile
dass ich bin neugierig.
Recht?
Diese Programme laufen in Sekundenbruchteilen.
Es ist ganz nett für uns langsameren Menschen in der Lage sein anzuhalten, einen Moment Zeit nehmen, siehe
was los ist in der Umgebung eine bestimmte Codezeile
ohne das Programm Pflügen durch ihn und Finishing ganz.
So ein Haltepunkte wird uns, damit brechen und Pause an einem bestimmten Punkt.
>> Call-Stack ist eine andere Art zu sagen, was Funktionen sind derzeit
im Moment bezeichnet.
Haupt wird immer zuerst genannt.
Aber wenn Haupt ruft ein Swap-Funktion aufgerufen,
wir eigentlich vor sich geht, das zu sehen Turm von Funktionen, die gewesen sein
in umgekehrter chronologischer Reihenfolge aufgerufen.
Also mal sehen, dass.
>> Ich werde zu verkleinern.
Ich werde wieder in meinem Code zu gehen.
Und gerade weil ich will, hier pedantisch zu sein,
Ich werde weitermachen und klicken Sie auf nur links von der Linie fünf.
Und das schafft einen roten Punkt.
Und auf der rechten Seite merken dass der Debugger weiß, hey,
Ich sagte nur ein Haltepunkt an noswap.c Linie fünf, und zwar
bei dieser Codezeile.
So dass der Debugger weiß, daß ich , dass das nächste Mal, wenn die angeforderte
Ich betreibe mein Programm ist Pause Ausführung gibt und nicht nur
läuft die ganze Sache super schnell.
>> So, jetzt werde ich die Debug klicken Taste an der Spitze der IDE
und das wird die folgende zu tun.
Es wird ein zunächst etwas öffnen unheimlich aussehende zweiten Anschluss window--
Remote-Debugging von Wirt, und such--
und wir werden zurückkommen, was alles, was bedeutet, es dauerte nicht lange.
Aber was wichtig ist für jetzt ist, dass die red dot getroffen wurde,
Der Debugger hat absichtlich Pause execution--
nicht auf dieser Linie an sich, sondern in der ersten Linie der eigentliche Code in dieser Funktion.
Und deshalb Linie sieben ist nun gelb markiert.
>> Und jetzt wir einen Blick lassen an der rechten Seite.
Es sieht aus wie in der Standardeinstellung schön genug ist, hat x, was Wert?
0.
Und y, was Wert?
Null.
Und das ist in dem Sinne zu erwarten daß x und Y-, dass gelbe line-- hat
noch nicht ausgeführt.
So x sollten nicht den Wert 1 haben.
Es könnte einen anderen Wert haben, eine so genannte Garbage-Wert.
Und wir haben das Glück, dass es Null an dieser Stelle, im Wesentlichen.
>> So, jetzt gibt es nur noch wenige Tasten wir brauchen, um Pflege
etwa bei der Fehlersuche in dieser Weise.
Beachten Sie, hier haben wir eine Play-Taste.
Und wenn wir spielen, oder drücken wieder aufzunehmen, das ist nur
gehen zu durchlaufen der Rest des Programms
oder bis er auf einen weiteren Haltepunkt.
Aber ich habe keine andere gesetzt Haltepunkte so ist es nur
gehen, um bis zum Ende ausgeführt.
Diese Art von Niederlagen der Zweck stochern.
>> Anstatt also, sorge ich mich über Diese Symbole auf der rechten Seite.
Und wenn ich den Mauszeiger über ihnen, wie Sie sollten auch
Du kleine tips-- Tooltips angezeigt.
Dieser ist Schritt über.
Nun bedeutet das nicht, skip Die folgende Codezeile.
Das bedeutet nur, ausführen und zum nächsten, um zum nächsten,
zum nächsten.
Mit anderen Worten, über dass Taste kann ich zu Fuß
durch meinen Code einen Schritt zu einer Zeit.
Zeile für Zeile, buchstäblich.
Nun auf der rechten daß, da liegt noch eine
dass wir in nur einem Augenblick zu sehen.
Dies ist die sogenannte Step Into Symbol, das ist
werde mir gestatten Tauch in einer anderen Funktion.
Aber lassen Sie uns das sehen in nur einem Augenblick.
So werde ich Sie auf Schritt über.
Und jetzt bemerken, wie ich klicken diese Taste oben rechts,
halten Sie die Augen etwa unter Local Variablen und sehen, was passiert, um x.
x 1 ist jetzt, da die gelbe Linie ist nun durchgeführt
und wir sind auf die Linie 8 verschoben haben.
Und in nur einem Augenblick y Machen hoffentlich 2.
>> Nun, nichts, was interessant passiert, für ein bisschen.
All dies ist printf.
Und beachten Sie, in meinem sekundären Anschluss Fenster, sehe ich die Ausgabe des Druck def.
Und jetzt habe ich eine machen Entscheidung, den Programmierer.
Ich kann über diese Leitung der Schritt Code, führt es aber nicht
immer neugierig, was drin ist.
Oder ich kann tatsächlich in sie Schritt und im Inneren des Swap selbst zu gehen.
Lassen Sie uns so tun, das letztere.
>> Lassen Sie mich gehen Sie vor und klicken Sie auf nicht vorbei, aber Schritt Step Into.
Unsere, auf einmal die Fensteränderungen
um die erste markieren Codezeile im Swap.
Das ist die Leitung 21.
Und nun, was ist eine Art von funky ist, dass, wenn Sie sich hier über Aussehen, wie erwartet,
ein Komma b 1 bzw. 2.
Warum ist Temp 32.767?
Hinweis darauf, dass Temperatur, ähnlich wie die leere Tasse vor einem Augenblick,
Hier wird in Zeile 21 deklariert.
Warum 32,000- Ich meine, warum ist es ist nur einige seltsame Wert?
Ja?
>> ZIELGRUPPE: Es ist nicht initialisiert.
>> David J. MALAN: Es ist nicht initialisiert.
Also unsere Computer immer hat physischen Speicher.
Es hat immer physischen RAM.
Und es gibt immer Nullen und man ist da drin, oder?
Weil wir mit unseren Computer den ganzen Tag lang,
Sie mit dem CS50 IDE sind oder die Server, den ganzen Tag lang.
So dass RAM entweder hat einige Nullen oder jemand oder einige Nullen und Einsen.
Egal, ob nicht Sie mit ihnen.
Sie können nicht nur blank Räume, in denen Sie Bits möchten.
Sie sind entweder Nullen und Einsen.
>> So stellt sich heraus, dass die Temperatur, weil wir haben es noch nicht initialisiert,
Wir haben diese 32 Bit aber nicht haben beliebigen bekannten Werten initialisiert.
So was auch immer sie waren die meisten kürzlich for-- jene 32 bits-- verwendet
wir sind nur zu sehen, die Artefakte von einigen vorherige Verwendung von diesen besonderen 32
Bit.
Sobald ich auf Step Over obwohl, Puh, wird Temp gehen, um den Wert 1 zu bekommen.
Und wenn ich es wieder tun, a gehen, um den Wert 2 gegeben werden
und dann b Nahmen den Wert 1 angegeben werden.
>> Und was ist schön, jetzt an dieser Punkt in der Geschichte
ist, dass der Debugger zeigt mir, super langsam
in meinem eigenen Tempo, was der Zustand der Swap ist.
Aber beachten Sie an der Spitze hier, Ankündigung dass der Aufruf-Liste tatsächlich
zwei Schichten darauf.
Jetzt ist die eine, die so markiert ist Swap, wenn ich auf der Main klicken Sie stattdessen,
beachten Sie, wie die lokalen Variablen ändern da der Entwickler nur Hop kann
um und in jedem anderen Bereich zu gehen.
Also auch wenn wir tun, all dies arbeiten und richtig Swapping a und b,
wenn ich gehe hin und her zwischen Swap wobei a 2 ist und b 1 und Main,
hat Haupthaupt betroffen?
Nein.
Also, was ist das Mitnehmen hier?
Nun stellt sich heraus, dass jederzeit Aufruf einer Funktion wie Swap,
und Sie Argumente übergeben, was Sie an den Swap-Funktion vorbei sind
in diesem Fall ist eine Kopie dieser Argumente.
So dass, wenn x und y sind jeweils 32 Bits, welche Swap bekommen wird
zwei neue lokale Variablen oder Argumente,
genannt und b-- aber die willkürlich sind Namen colliders-- aber das Muster von Nullen
und Einsen Innenseite a und b aufgereiht identisch mit x und y zu sein
aber sie nicht das sind, Gleiche wie x und y.
>> Es ist, als ob Main hat auf seiner Stück Papier für die Zahl 1 und 2 für X und Y,
und dann, wenn es reicht, dass Stück Papier zu tauschen,
Swap sehr schnell bekommt seine eigene Feder, schreibt
1 und 2 auf einem eigenen Blatt Papier, Hände wieder die ursprüngliche xy zum Haupt
und dann macht seinen eigenen Sache mit a und b.
Und das ist jetzt super wichtig, weil dies hat Auswirkungen nicht-triviale
zum eigentlichen Schreiben richtigen Code weil es scheint, wir nicht tauschen können
zwei Variablen.
>> Ich habe eine richtige Swap Funktion geschrieben.
Wir haben es mit Lauren implementiert eine korrekte Swap-Funktion in der Realität,
aber anscheinend nichts davon Fragen, wenn Sie können nicht wirklich
Swap zwei Werte dauerhaft.
Also müssen wir einen anderen Weg um tatsächlich an dieses zu erhalten,
und wir müssen in der Lage zu sein, tatsächlich dieses Problem zu lösen.
Und es stellt sich out-- und wir kommen zurück zu diesem Bild
vor long-- dies ist eine Art und Weise, Sie können den Arbeitsspeicher Ihres Computers ziehen.
Es ist nur ein Rechteck.
Sie konnten es nicht ziehen Anzahl von Wegen, aber es ist
bequem, es als ein Unentschieden Rechteck aus dem folgenden Grund.
>> Wir werden heute beginnen und darüber hinaus reden über die sogenannten Stack.
Und der Stapel ist nur ein Stück von RAM-- ein Stück memory--
dass die Funktionen zugreifen um, wenn sie genannt werden.
Und so stellt sich heraus, dass bei Ganz unten in diesem Stapel
ist, wo alle Haupt die lokalen Variablen und org C org V und all das Zeug
gehen, um standardmäßig zu gehen. Und wenn Haupt ruft eine andere Funktion wie Swap,
Nun, das ist Swap gehen zum anderen zu gelangen Schicht der Speicher bis darüber.
>> Und so, nur um Ihnen eine schnelle oberflächliche geben Bild von diesem, wenn ich über hier--
und lassen Sie mich spiegeln dies auf die Overhead als well-- was wirklich ich habe,
wenn wir uns nur für die unten von diesem Bild für den Moment,
ist, dass, wenn ich ein Programm und Main aufgerufen wird,
Main liegt ein Stück gegeben RAM in meinen Computer, der ist
am Ende der sogenannten Stack.
Und ich werde, es zu zeichnen bewusst als Quadrat.
So ist es wie 32 Bits oder vier Bytes.
Und wenn dieser Hauptfunktion eine Variable x mit einem Wert von 1
und es eine Variable namens hat y den Wert von 2, das ist
wie wenn man diese Splitter der Erinnerung, die Haupt wurde von dem Betriebs gegeben
System und Dividieren es so einrichten, dass die erste lokale Variable geht hier,
die zweite geht man hier, und das ist es.
>> Als Haupt ruft Swap, Swap erhält eine eigene Scheibe Speicher
dass wir wie folgt zu zeichnen von dem Betriebssystem,
und es ist zu haben, ihre eigenen lokalen Variablen auf der Grundlage
auf unserer Umsetzung früher mit lokalen Variablen ein
und b, die ursprünglich erhalten Sie die Werte 1 und 2.
Aber dann, sobald der Swap-Code ausführt,
und Lauren tatsächlich vertauscht die Orangensaft und Milch, was passiert?
Nun, dieses 2 wird zu einem 1, dieses 1 wird zu einem 2 und, nebenbei bemerkt,
gibt es eine temporäre Variable, die Befinden verwendet diese ganze Zeit, die schließlich
geht weg.
Aber es spielt keine Rolle, wie viel Arbeit Sie tun,
In dieser Zeile von-- in diesem Speicherraum, x und y sind völlig unberührt.
>> Also müssen wir einen Weg geben Swap und Funktionen, wie es
Geheimzugang, wenn Sie so wollen, um Funktionen like-- zum Gedächtnis wie x und y.
Werfen wir also einen Blick auf ein Beispiel, das hilft,
wir sehen, genau das, was ist schon geht dieser ganzen Zeit.
Ich werde weitermachen und eröffnen Vergleichen Null.
Und ich werde, um zu schließen unsere Debugger, ich werde
, diese unheimlich aussehende Meldung zu schließen der sagt nur, warten Sie eine Minute,
du bist in der Mitte Debugging.
Ich werde diese Registerkarte, hier verstecken nur um wieder zur Einfachheit zu gehen.
Also keine Sorge, wenn GDB wird getötet.
Das bedeutet nur, dass das Programm wurden zu verlassen, gezielt in diesem Fall,
von mir.
>> Und jetzt vergleichen Null tut dies.
Ich bin mit dem CS50 Bibliothek im Standard-I / O.
Ich habe eine Hauptfunktion, die zum ersten Mal sagt, etwas sagen, und bekommt einen String.
Sagt, dass es dann wieder und bekommt eine andere Zeichenfolge.
Und beachten Sie, dass diese beiden Saiten werden als S und T verbunden.
Und jetzt das Programm vergleichen Zero, ihren Zweck im Leben,
es soll mir sagen, habe ich die gleiche Sache geben?
Und so bin ich zurück gehen, um eine Woche.
Ich bin mit meiner equal equal Betreiber was die Qualität des Bedieners.
Nicht der Zuweisungsoperator, der Gleichheitsoperator.
Ich bin einfach nur den Vergleich s und t.
>> Lassen Sie uns also tatsächlich gehen Sie vor und tun dies.
Und ich werde weitermachen und stellen Sie die Vergleichs Null.
Ich werde ./comparezero zu tun.
Und ich werde gehen voraus und etwas sagen
wie, machen wir mom in Kleinbuchstaben und wie über mom in Großbuchstaben.
Und natürlich habe ich geben verschiedene Dinge.
Gut.
Das ist zu erwarten.
>> Lassen Sie führen Sie es erneut.
Beide Male tun, Kleinbuchstaben, Kleinbuchstaben.
Das sieht super gleich zu mir.
Enter.
OK.
Vielleicht ist es nur komisch, weil es ist nicht zu mögen meine Grammatik.
Also lassen Sie uns einen Kapital MOM, Kapital MOM, identisch.
Verschiedene Dinge.
>> Also, warum ist das so?
Na ja, was eigentlich vor sich geht auf unter der Haube hier?
Also lassen Sie uns gehen Sie zurück über hier für einen Moment
und überlegen, was GetString ist tatsächlich tun.
Wenn Sie GetString aufrufen, das ist eine Funktion, die wir
selbst geschrieben und es irgendwie bekommt ein Folge von Zeichen von dem Benutzer.
Und lassen Sie uns davon ausgehen, dass die erste Zeit, die ich nennen GetString, gibt mir, dass
ein Teil des Speichers, der so aussieht.
Und wenn ich in Kleinbuchstaben eingegeben m-o-M- und was danach geht es?
Nur eine schnelle Plausibilitätsprüfung.
>> Backslash Null.
Wir wissen das.
Und daran erinnern, dass wir spielten rund mit Zamila Name
und ein paar andere Namen Wenn Rob war hier auf der Suche
auf, was los ist in der Erinnerung.
Also diese Geschichte ist genau das gleiche.
Dies ist, was GetString ist zu mir zurückkehren.
Nun, mein Code vor einem Augenblick gespeichert der Rückgabewert der GetString
in einer Variablen namens s.
Und dann das zweite Mal, dass ich es nannte, es in einer Variablen namens t gespeichert.
>> Also, wenn ich hier übergehen, ich brauche um diese lokalen'variable zeichnen
und ich bin in der Regel werde zeichnen Sie eine Zeichenfolge als just-- wir werden
nennen es S- als kleinen Platz hier.
Und nun, somehow-- wie funktioniert mom gehen innerhalb dieser Variable s?
Nun, wir müssen zurück zu gehen In den ersten Prinzipien hier.
Was GetString tatsächlich zurückkehrt?
>> So stellt sich heraus, dass M-O-M Backslash Null, und eine beliebige Anzahl
von anderen Saiten im Gedächtnis wie Zamila und Rob oder Andy oder irgendwelche andere,
Natürlich sind in unserer RAM oder Speicher Computers.
Und Ihre RAM verfügt like-- Sie ein Gig RAM, zwei GB RAM,
oder eine Milliarde oder zwei Milliarde Byte, oder vielleicht noch mehr in diesen Tagen.
Nehmen wir also an, für die heutigen Zwecke, , dass es keine Rolle spielt, wie wir die Nummer
sie, aber wir können jede Nummer von denen Milliarden oder zwei Milliarden
oder vier Milliarde Byte.
>> Und lassen Sie uns einfach sagen, dass beliebig dies ist der erste Biss, zweiten Bissen,
dritte, vierte.
Ich bin bewusst nicht mit Null heute aber wir werden darauf zurückkommen.
Also mit anderen Worten, wenn dies der allererste Mal, dass ich mit dem Programm,
Ich bin gerade erst das Glück und die erste Biss ist an der Stelle ein, dann zwei
dann drei als vier.
Und wenn ich immer zeichnen, Box-Nummer zwei Milliarden würde Weg hierher sein.
>> So was denken Sie dann, GetString tatsächlich zurückkehrt?
Es ist nicht der Rückkehr M-O-M umgekehrten Schrägstrich Null an sich, weil das deutlich
passen nicht in die Box, die ich gezogen habe.
So was könnte tatsächlich GetString zurückkehren all diese Wochen?
Die Antwort ist auf die Pension hier irgendwo.
Sie können nicht passt M-O-M umgekehrten Schrägstrich Null, so was könnte sinnvoll, anstatt zu machen?
Wenn Sie musste super klug, setzen auf der sogenannten Ingenieur Hut,
was können Sie zurückkehren?
Was ist die geringste Menge an Informationen Sie konnte das immer noch zurückkehren würde
Lassen Sie M-O-M im Speicher?
Ja?
>> ZIELGRUPPE: One.
>> David J. MALAN: One.
Und warum man?
ZIELGRUPPE: Weil es würde sagen, Sie, wo zu gehen [unverständlich].
David J. MALAN: Genau.
Ich bin gerade dabei, die Adresse zurück der Saite, die ich bekommen.
Die Adresse in diesem Fall ist die Lage ein.
Also, was wirklich wird in S- gespeichert und jeder String-Variable so far--
hat gerade die Adresse dieser Zeichenfolge.
>> Inzwischen, wenn ich rufe GetString ein zweites Mal und ich
Geben Sie in wahrsten Sinne des Wortes die gleiche thing-- M-O-M mit lowercase-- M-O-M
und ein weiterer umgekehrter Schrägstrich Null, und jetzt vielleicht meine Programms
seit einiger Zeit läuft so vielleicht dieses 10 ist, ist diese Position 11, 12 ist,
das ist 13.
Die Computer mit einer anderen Speicher welchem ​​Grund auch immer.
Was geht jetzt in meinem zweiten Variable in meinem Programm t?
10.
Genau.
>> Und so, wenn wir auf die Source-Code des Programms
wo ich einfach versuchen, um die beiden Werte zu vergleichen,
ist s gleich gleich t, ​​was ist die offensichtliche Menschen Antwort?
Nur weil kein 1 nicht gleich 10.
Und so liegt hierin ein Gelegenheit für uns, wirklich
um nur wieder auf, gehen Sie wieder zuerst Prinzipien und darüber nachdenken, nun ja,
was los ist unter der Haube?
Wir haben darüber gesprochen, Bits und Bytes und Gedächtnis,
aber es ist wirklich nützlich, um zu verstehen, denn wenn man GetString aufrufen,
auch wenn wir denken, es ist von Rückkehr M-O-M oder String mom
oder Andy oder Zamila oder dergleichen, technisch
es ist nur die Adresse der Rückkehr dieser Teil des Speichers.
>> Aber das ist OK.
Denn wie weiß ich, wo der String endet?
Wenn ich nur den Anfang gegeben?
Nun, der Backslash Null, oder?
Nur in linearer Zeit, ich kann Drucken Sie mit Print def M-O-M.
Und sobald ich umgekehrten Schrägstrich Null ist, ist mir egal, wo ich angefangen habe,
Ich weiß schon implizit wo ich brauche, um zu beenden.
>> Und so markiert heute die beginning-- und lassen Sie mich dies dramatisch, weil wir
ging durch eine Menge Ärger zu Holen Sie sich diese hier trainiert wheels--
so heute die Stützräder beginnen sich lösen und wir enthüllen least--
>> [Applaus]
>> Das war auch eine Reise wert heute morgen Ziel, ja?
So now-- ist, stellt sich aus, nicht so etwas wie String.
String ist nicht vorhanden.
Es ist ein Synonym, das wir je hatten Innenseite der CS50-Bibliothek.
Von nun an werden wir lostelefonieren s und t nicht Strings aber char Sternen.
Und die char star wir werden necken neben dauerte nicht lange.
Aber dies bedeutet, dass, selbst wenn wir auch weiterhin
mit GetString für jetzt, technisch, ich sollte
sagen char Sterne und Saibling Sterne.
>> Und es stellt sich heraus, was den Stern wird zu bezeichnen ist etwas,
genannt ein Zeiger oder eine Adresse.
Und in der Tat eine teaser für das, was vor uns liegt,
ist dies 20 Sekunden Clip aus unserem Freund Nick Parlante in Stanford
, die, vor einiger Zeit, verbringen eine lächerliche Menge an Zeit,
so gut ich kann sagen, sein Küche oder seinem Keller,
machen claymation Einführung in die Welt
ein Charakter namens Binky mit denen wir
beim nächsten Mal, um Zeiger eingeführt werden.
So, hier ist eine Vorschau von dem, was noch kommen wird.
>> [VIDEO PLAYBACK]
>> -Hey, Binky.
Aufwachen.
Es ist Zeit für Zeiger Spaß.
>> -Was ist das?
Erfahren Sie mehr über Zeiger?
Oh, gute sachen.
>> [END PLAYBACK]
David J. MALAN: Und in diesem Sinne, werden wir Sie am Mittwoch zu sehen.
Gut.
Wer ist Tanz?
Komm schon.
Wer ist Tanz?
Soll ich es angefangen?
Ich werde es begann.
Woooo!
>> LAUREN: süß fancy Moses.