>> [MUZYKA GRA]
>> Głośnik 1: W porządku, to jest CS50, i jest rozpoczęcie od czwartego tygodnia
i jak może słyszeliście lub przeczytać, że świat został kończąc.
Dzieje na całym internecie został wiedzy i świadomości
błędu w programie, a język programowania zwany Bash.
Ten został cudownie markowe jak Shellshock lub drzwi Bash,
ale jak te artykuły nie były rzadkością.
I rzeczywiście, wiele z nich przyniesie wspomnienia Heartbleed,
które można zauważyć w wcisnąć z powrotem w ostatni wiosny, które
było podobnie dość dramatyczne.
Teraz z tych z was tutaj dzisiaj, jak wielu z was,
nawet jeśli nie rozumiem, co w tym wszystkim chodzi, słyszałem Shellshock?
Wszystko w porządku, i jak wielu z was mają komputery, które są narażone?
OK, nie powinno być dużo, dużo więcej rąk się w tej chwili, ze względu na to zobaczymy.
>> Rzućmy okiem na to, co jest dzieje się w mediach
a następnie wyjaśnić to trochę tutaj dla nas technicznie.
>> Głośnik 2: Eksperci mają ostrzegł, że poważna wada może
około wpływać setki miliony użytkowników na świecie sieci web.
Więc co dokładnie jest błąd, który był nazwany ShellShock i co to robi?
Cóż, ShellShock jest również znany jako Bash błąd, oprogramowanie to wykorzystuje.
Hakerzy wykorzystują wirusa skanowanie podatne Systemy działające Linux i UNIX
systemów operacyjnych, a następnie infekują je.
Bash jest powłoką linii poleceń.
Kwestia ta pozwala użytkownikom na polecenia uruchomienia Programy i funkcje oprogramowania
wpisując w tekście.
To zazwyczaj używane przez programistów, a nie powinien być otwarty na świat,
choć ShellShock zmienia to.
>> Cóż, worringly, niektórzy analitycy ostrzegam to może być większym zagrożeniem,
bo ShellShock umożliwia kompletne kontroli nad zainfekowanym komputerem,
natomiast Heartbleed tylko dozwolone hakerzy szpiegować komputery.
To jest tak poważna, że ​​to zostały ocenione na 10 z 10
do nasilenia przez Narodowy Vulnerability Database.
2/3 z wszystkich serwerów internetowych są ryzyka, w tym niektórych komputerach Mac.
Cóż, upewnij się, że łatać swoje systemy teraz.
Każdy, kto organizuje funkcjonowanie strony internetowej przez system
powinny podjąć działania jak najszybciej.
Każdy, kto może sobie pozwolić na to powinno wyglądać ich stosowania monitoringu i internetowej
zapory, aby zwrócić uwagę na wszelkie ataki.
GŁOŚNIK 3: Najgorsze że może się zdarzyć,
że ktoś mógłby napisać kod, który automatycznie go i skanować
Internet i wpłynęłoby Wszystkie z tych komputerów.
A raz tak, że dobrze, Najgorsze, co mogą zrobić,
jest po prostu usunąć wszystko, lub zamknij miejsc w dół.
Więc mogliśmy zobaczyć obrażenia z tego punktu widzenia,
gdzie mamy złośliwych ludzi którzy po prostu decydują się spowodować chaos
przez systemy obniżania lub usuwanie pliki i takie rzeczy.
Głośnik 2: Niektórzy mówią, że jest to jeden z najbardziej trudne do zmierzenia
błędy w latach, i to może potrwać kilka tygodni lub nawet
miesięcy, aby określić jego ostateczny wpływ.
>> Głośnik 1: Więc to wszystko jest prawdą, ale zabawne jest to, prawie wszystkie
z obrazami po prostu zobaczył, z wyjątkiem być może klawiatury
nie ma nic wspólnego z bug w ogóle.
Serwery i przewody i tak dalej, To coś w rodzaju stycznie związanych,
ale w centrum jest to faktycznie dość znać, co się tutaj dzieje.
W rzeczywistości, pozwól mi pójść do nasze urządzenie CS50.
Pozwólcie mi iść do przodu i zwiększyć okno terminalu tutaj.
A wy zostały z wykorzystaniem tego, lub jego wersję wbudowanego,
w gedit, aby pisać programy, typu polecenia, i tak dalej,
, a w rzeczywistości jest to, ma było na tydzień, Bash, B-A-S-H.
To Bourne-Again shell, który jest tylko fantazyjny sposób na powiedzenie,
to program, który jest miganie szybkie, skuteczne,
że siedzi tam czeka dla wejścia dla Ciebie.
I to jest polecenie Interfejs wiersza, za pomocą którego
wy zostały uruchomione polecenia i ostatecznie kompilacji i uruchamiania
programy.
>> Ale Bash jest także programowanie Język w następującym znaczeniu.
Wiesz, że istnieją komendy, takie jak cd i ls oraz brzękiem i inni,
ale można definiować własne komendy wdrażając je w bash.
Teraz nie będziemy bardzo szczegółowe
jak bash język programowania, ale wiadomo, na przykład, że w tym momencie,
nie ma polecenia o nazwie "cześć".
Więc można je znaleźć w jeden z tych pakietów.
To nie jest zainstalowany na moim komputerze.
Zapytaj administratora.
Ale jeśli chcę tam być program zwany "cześć" w bash lub w moim wierszu,
Faktycznie mogę użyć składni to zupełnie jak C. To nie jest to samo,
ale wygląda bardzo podobne do funkcja, choć brakuje kilku szczegółów.
Nic się nie dzieje, ale teraz, jeśli napiszę "witam"
rzeczywiście można napisać Program, a nie w C, a nie w Javie,
nie w innym programowania język, ale w samej Bash.
>> Teraz kluczem jest to, że napisałem wymienić chciałem dać to nowe polecenie,
i nawiasy są również symbolem tego jest funkcja.
Tak na marginesie, można też zrobić zabawy rzeczy, w rzeczywistości, nawet w systemie Mac OS,
to jest program o nazwie Terminal.
Chodzi ktoś jest wbudowany w Komputer, który ma Mac w tym pokoju,
i można zrobić podobnych rzeczy w Mac OS, ale można przejść więcej poza tym.
I to jest trochę styczna, ale jest to rodzaj zabawy.
Przypomniał mi dziś rano, kiedy myśli to przez,
mały gry grałem z jednym z byłych TF CS50 za
przy czym za każdym razem chciał odejść od Jego klawiatura z jego ekranie odblokowane,
Chciałbym wykonać polecenie jak to-- "przywitać".
I teraz za każdym razem wracał do jego Klawiatura po I wyczyszczone ekranu
i chciał usiąść, spróbuj popracować,
wyświetlić zawartość jego directory--
>> [AUDIO ODTWARZANIE]
>> Halo.
Witaj.
>> 1 głośnik: Tak, w sprawiedliwości, nie było w rzeczywistości "cześć".
To było coś, co zwykle bardziej podobny do that--
[AUDIO ODTWARZANIE]
-Beep.
Głośnik 1: czyli regulują I would-- byłoby więc jego komputer
Przysięgam na niego w każdej chwili, że faktycznie usiadła na jego klawiaturze.
I bardzo szybko zorientowali się, że aby nie pozostawić jego ekran odblokowany.
Ale to sugeruje rodzaj głupie zabawy, że ci
może mieć coś jak bash.
Ale to jest trochę więcej poważne, aby upewnić się, niż to.
I w rzeczywistości jest to jeden z Najbardziej niebezpieczne i długotrwałe błędy
że naprawdę hit świat globalnie.
Ten błąd jest już przez około 20 lat,
i będziesz po prostu uderzył w Moment jego względnej prostoty.
>> Więc to jest przedstawiciel dowodzić, że jeśli
właścicielem Mac, teraz dosłownie jeśli masz swój pokrywa otwarta,
można spróbować wpisując w które Program o nazwie Terminal.
Terminal znajduje się pod Aplikacje Utilities--
raz, użytkownicy systemu Windows nie trzeba martwić się o tego konkretnego threat--
ale ci z was, z komputerami Mac można wpisać to w oknie jak zrobię tutaj,
i jeśli nie wpisz że do tego programu
nazwie Terminal, jak zrobię teraz, jeśli widzisz słowo "narażone"
komputer jest podatne na eksploatację.
>> Teraz co to właściwie znaczy?
I to jest prawda niektóre całkiem szalony składnia,
ale niech przynajmniej wyciągnąć niektóre z interesujących aspektów.
Więc jest jakiś, który wygląda składnia mało znane, co najmniej od C
i programowania bardziej ogólnie.
Widzę kilka nawiasów, średniki, nawiasy klamrowe i takie,
ale okazuje się, że to głupota tutaj na żółto
jest zasadniczo funkcją że nic nie robi.
Środki okrężnicy nic nie robić, a średnik oznacza przestać robić nic.
Więc wewnątrz nich nawiasy klamrowe, fakt
że mam równe zaloguj się w lewo, to
jest zasadniczo stworzenie Polecenie albo zmienna
nazwie x, i przypisywanie że żółty fragment kodu nie.
To może być coś w stylu "echo hello "lub" mówią sygnał "czy coś
podobny do tego.
Nie zauważyć, jeśli twoje oczy dalej wędrować w prawo
nie więcej niż do tej linii tylko koniec tej średnikiem.
"Echo wrażliwe", a następnie poza tym jest jeszcze więcej.
Innym średnik, bash-c :.
>> Więc krótko mówiąc, ta linia kodu jest
wystarczające do zmuszenia Komputer, który jest
narażone na robienie czegoś , że chcesz to zrobić,
bo jest błąd w bash, zgodnie z którą chociaż Bash miał zatrzymać
czytanie wierszy prawo polecenia tam po żółtym tekstem,
dla 20-plus-letniego buga, Bash był faktycznie czytanie
poza tym średnikiem i ładna dużo robi to, co jej powiedział.
>> Więc co jest implikacja Z tego ostatecznie?
Powiedziałem tylko "echo Witaj" lub "echo wrażliwe"
Ale co, jeśli zrobił coś faktycznie złośliwy, jak rmdir *,
które może nie kiedykolwiek wpisane wcześniej,
i szczerze mówiąc, prawdopodobnie nie powinny zbyt szybko,
bo można zrobić Wiele szkód z niego.
Dlaczego?
rm co robi, oczywiście?
Usuwa.
* Oznacza co?
Wszystko.
Więc to tak zwany dzikie karty, więc oznacza to,
usunąć wszystko aktualny katalog.
-r dzieje oznacza rekurencyjne, co oznacza, że ​​jeśli to, czego usuwanie
jest katalogiem, a wewnątrz nie jest inne pliki i inne katalogi,
rekurencyjnie zanurzyć się tam i usuń wszystko.
A-f jest najgorszy z nich wszystkich.
Ktoś wie co -f oznacza tutaj?
Siła.
Tak więc siłę środka, nawet jeśli jest to zły pomysł,
zrobić bez pytania mnie do dalszego potwierdzenia.
Więc, wiesz, że śmiać się , ale szczerze mówiąc, prawdopodobnie
wpisz to wiele razy dzień, ponieważ rzeczywistości
Jest to najszybszy sposób na usunąć całą masę rzeczy.
Ale nawet zrobiłem trochę szkód.
>> Ale jeśli było oszukać komputer do definiowania trochę zmienną głupiego
lub funkcję x, a następnie oszukiwanie komputera do wykonywania
poza granice, które funkcja, poza tym średnikiem,
Rzeczywiście można oszukać komputer do wykonania coś rm -rf
E-mail lub polecenie lub polecenie Kopiuj.
Wszystko, co dosłownie można zrobić z komputer, czy to usuwanie plików,
tworzenia plików, spamuje kogoś, atakuje jakiś serwer zdalnie,
jeśli można to wyrazić z poleceniem, można
Można oszukać komputer do robienia tego.
>> Teraz to, co jest przykładem w jaki sposób można to zrobić?
Cóż, jest wiele komputerów na Bash Internet bieżącą.
Nas wszystkich użytkowników komputerów Mac są wśród nich.
Wiele serwerów Linux należą im, jak również i Unix.
System Windows ponownie dostaje stosunkowo od haka
chyba że masz zainstalowany specjalne oprogramowanie.
Teraz wiele serwerów, na instancji, działają serwery WWW,
i faktycznie Linux jest chyba najpopularniejszy system operacyjny
uruchomić na komputerach w internecie które służą do stron internetowych.
Teraz, jak zobaczymy później w semestrze, gdy
wysłać wniosek Twój browser-- Chrome
Internet Explorer, whatever-- do zdalnego serwera,
Okazuje się, że nawet jeśli po prostu wpisane www.example.com,
Twoja przeglądarka wysyła wiadomość to jest trochę bardziej ezoteryczne, jak ten.
>> Ale zauważysz coś dziwnego.
Pierwsze dwie linie Nigdy nie widziałem wcześniej,
ale nie wyglądają szczególnie groźne.
Ale zauważ, co ukradli dla trzeciej linii tutaj.
Jeśli zły był, aby wysłać wiadomość tak od swojego komputera
do trudnej Mac lub podatny serwer Linux,
Zabawne jest to, że Bash, że prosta szybka trochę poleceń,
jest wszechobecny i jest często używane na zasadzie wykonywania
Zawartość wiadomość, że odbiera.
I przez tę logikę, można oszukać serwer WWW, w związku z tym,
wysyłając coś User-Agent, który zazwyczaj
ma do powiedzenia Nazwa Twojej przeglądarce.
User-Agent Chrome, Internet User-Agent Explorer, Firefox User-Agent, w tym
jest tylko w Twojej przeglądarce Sposób identyfikowania się.
Ale jeśli facet bardzo zły sprytnie mówi, mm-mm, jestem
Nie powiem ci, co moja przeglądarka jest,
Ja zamiast zamiar wysłać ci to tajemniczo wyglądające rzeczy z -rf rm
* W nim można dosłownie oszukać podatny serwer WWW w Internecie
do wykonywania dokładnie, że w tam na usunięcie wszystkich plików.
I szczerze mówiąc, to nie jest nawet najgorsze.
Możesz zrobić wszystko.
Można zacząć dystrybuowane atak Denial of Service
jeśli wysłał tę wiadomość całe kiście serwerów internetowych
a następnie miał je wszystkie schodzą na instancji, na serwerach Harvard.edu,
i można sortować z hukiem do cholery z nimi
przez ruch w sieci, który był inaczej wywołane tym złym facetem.
>> Więc, krótko mówiąc, niemal wszyscy w tym pokoju, który jest właścicielem komputera Mac
jest podatny na to.
Wyszło, że chyba jesteś uruchomiony serwer WWW na komputerze przenośnym,
i chyba już właściwie skonfigurowane to, aby umożliwić coś SSH do niego,
jesteś rzeczywiście bezpieczne.
To wrażliwe, ale nie ma nic jeden próbuje dostać się do laptopa,
, dzięki czemu można mieć pewność, rodzaj.
Jednak, Apple wkrótce być aktualizacją poprawkę dla tego produktu.
Świat Linuksa już wydany liczba poprawek dla Fedory i Ubuntu
i inne wersje Linuksa, a nawet po uruchomieniu aktualizacji 50 w urządzeniu,
nawet, że zbyt będzie zaktualizowane i poprawione.
Ale to też nie ma naprawdę był podatny,
bo chyba masz majstrował urządzenia
i wykonany publicznie laptopa dostępne w Internecie, które nie jest
domyślnie masz rzeczywiście było w porządku, bo
z firewalla i innych technik.
>> Ale to skrajny przykład z błędem że mamy do mieszka dosłownie 20
lat, a kto wie, czy ktoś przez cały ten czas jest o niej wiadomo?
I w rzeczywistości jest to jeden z podstawowe wyzwania
że zobaczymy później w Semestr o bezpieczeństwo,
jest to, że tak jak w świecie rzeczywistym, dobrzy są w gorszej sytuacji.
Zachować złych facetów, musimy upewnić się, że wszystkie drzwi są zamknięte,
że każde okno jest bezpieczne, że każdy punkt wejścia do domu
jest bezpieczne utrzymanie złych facetów.
Ale to, co robi źle facet musiał zrobić, aby rzeczywiście zagrozić domu
i ukraść od Ciebie?
On lub ona po prostu musi znaleźć odblokowany drzwi, jedno okno przerwane, czy coś
w tym kierunku, i to samo w dziedzinie bezpieczeństwa komputerowego.
Możemy napisać miliony linii kodu programowania
i wydawać setki lub tysiące godzin próbuje uzyskać to prawidłowe,
ale jeśli tylko jeden błąd w poprawność,
można umieścić cały system i Rzeczywiście w tym przypadku, cały Internet
i świat na ryzyko.
>> Tak więc, jeśli chcesz dowiedzieć się więcej na ten temat, przejdź do tej zawartości tutaj.
Nie ma potrzeby do akcji dzisiaj, chyba że jesteś
wśród tych bardziej komfortowe, że prowadzimy własnej sieci
serwer, w którym to przypadku należy, w rzeczywistości, zaktualizować oprogramowanie.
>> I to też jest tytuł mowy, a teraz papier,
że mamy związane na strona Kursu na dziś.
To było przez kolegów nazwie Ken Thompson, który
przyjmowała bardzo znany Nagroda w dziedzinie informatyki,
i dał to przemówienie kilka lat temu, w zasadzie na tym samym temacie.
Prosząc ludzi pytanie, Należy naprawdę
Zaufanie, ostatecznie, oprogramowanie, które już zostały podane?
Na przykład, wszyscy mamy pisze programy,
i byliśmy kompilacji je z Clang.
I wiedzy, napisałeś wszelkie programy CS50, gdzie istnieje
Tylne drzwi z rodzaju, istnieje sposób, że zły facet, czy uruchomić program,
może przejąć kontrolę nad komputerem?
Chyba nie, prawda?
Mario i chciwi, i kredytowa.
To wszystko są bardzo małe programy.
Trzeba być dość źle, jeśli rzeczywiście
wykonany cały komputer podatny po napisaniu 10 lub 20 linii kodu,
lub co najmniej niektóre nieświadomy implikacji bezpieczeństwa.
Teraz mogę powiedzieć, że żartobliwie, ale mamy zamiar zobaczyć już dziś
i w tym tygodniu to faktycznie bardzo, bardzo łatwe
być źle i zrobić nawet krótkie programy narażone.
>> Ale teraz przynajmniej sobie że pytanie zadawane jest tutaj
jest o Clang w kompilator.
Dlaczego zostaliśmy ufając dzyń w ciągu ostatnich dwóch lub trzech tygodni?
Kto powiedział, że ten, kto napisał dzyń nie mają "jeśli" stan tam
że zasadniczo wstrzykuje kilka zer i te, do każdego programu kompiluje
że pozwolił mu dostęp komputer, gdy śpisz
i laptopa pokrywa jest otwarta i komputer działa?
Prawda?
Mamy tego rodzaju prawa cześć systemu Teraz, gdy mamy nadzieję, że Clang jest legalne.
Ufasz, że urządzenie jest legalne.
Ufasz, że dosłownie każdy program na komputerze Mac lub PC jest wiarygodne.
I jak sugeruje ten prosty błąd, nawet jeśli to nie jest złośliwy,
że nie jest to absolutnie może być prawdą.
>> Więc należy się bać jak cholera.
Szczerze mówiąc, to nie ma proste Rozwiązaniem tego inne
niż rodzaj świadomości społecznej z rosnącej złożoności
że budujemy na szczycie naszych systemów komputerowych,
i jak coraz bardziej podatne możemy być bardzo dobrze.
>> Teraz z tym powiedział, Breakout.
Breakout jest problemem tak ustawione trzy, a Breakout to gra z przeszłości
że może pamiętacie, ale dla nas problemu ustawić trzy,
pozwala nam na rzeczy z powrotem do nacięcia
tak, że kiedy piszemy programy, nawet w oknie terminala, jak ten,
może faktycznie działać, ostatecznie, nie programy graficzne
w przeciwieństwie do tych, mieliśmy Dostęp do w Scratch.
Więc to jest przez personel Realizacja Breakout,
Ten, który jest po prostu łamanie cegły gry, które można przenieść wiosła z powrotem
i do przodu, i uderzyć piłkę na tych kolorowych klocków w górę szczycie.
Więc to przynosi nam swego rodzaju powrotem do miejsca, gdzie
udało się bardzo szybko z początku, a teraz z C,
realizacji naszych własnych graficzne interfejsy użytkownika.
>> Ale to nie wszystko, to Problem stanowi zestaw pierwszy
, w którym dajemy Ci czek kodu.
A w rzeczywistości, wprowadzają wyraźne uwagę na to, ponieważ zwłaszcza
dla tych mniej wygodne, to ustaw błąd, przynajmniej na pierwszy rzut oka
będzie czuć się jak podjęliśmy go wycięcie.
Bo my wam, dla niektórych z wyszukiwania
i sortowania problemów w Pset, Pęczek kodu, które napisał,
i kilka uwag że powiedzieć "do zrobienia"
gdzie trzeba wypełnić formularz.
Więc nie zbyt straszne, ale jest to pierwszy raz,
mamy wręczając Ci kod, który trzeba najpierw przeczytać, zrozumieć, a następnie dodać do
i wypełnić go.
>> A następnie z Breakout, mamy zamiar zrobić to samo,
co daje kilkadziesiąt więcej linii kodu, który, szczerze mówiąc, daje
Wiele ram dla gra, ale zatrzymać się
wdrażania cegły i piłki i wiosło,
ale robimy realizacji innych funkcji.
A nawet, że na pierwszy rzut oka, znowu, szczególnie jeśli mniej wygodne,
może wydawać się szczególnie trudne i myślisz, że jest tak wiele nowych funkcji
trzeba owinąć swój umysł wokół, i to jest prawda.
Ale należy pamiętać, że to zupełnie jak nowa.
Kursy są nie użyłeś wszystkich kawałki układanki w Scratch.
Szanse są, że nie obchodzi mnie do zawijania twój umysł wokół nich wszystkich
bo wszystko było zajęło Szybki rzut oka, aby zrozumieć, o,
to jest to, co można zrobić, z tego kawałek układanki.
I rzeczywiście, w problemu ustawić 3 Spec, będziemy wskazywać
w dokumentacji, która będzie wprowadzenie do kilku nowych funkcji,
i ostatecznie programowania konstruuje używasz.
Warunki, pętle, zmienne i funkcje
będzie identyczna tego, co widzieliśmy do tej pory.
>> Tak naprawdę, co damy jesteś pewien, że przykładowy kod
pozwala utworzyć okno że nie wygląda inaczej niż ten,
i ostatecznie przekształcić go w coś całkiem tak.
Więc skorzystać z CS50, dyskutować godzinami pracy i więcej,
i ma komfort na tym, że ilość kodu trzeba napisać
w rzeczywistości nie jest aż tak dużo.
Pierwszym wyzwaniem jest po prostu przyzwyczaja sobie na jakiś kod pisaliśmy.
>> Wszelkie pytania dotyczące pset3, ShellShock, lub w inny sposób?
>> PUBLICZNOŚCI: Wydawało się, że przechodzi z Breakout
że kod jest prawie styl obiektowy,
ale myślałem, że C był obiektowego programu.
Głośnik 1: doskonałe pytanie.
Więc patrząc przez Kod dystrybucji kod
pisaliśmy o pset3, dla tych, którzy znają, to
Wygląda na to, że to trochę obiektowego.
Odpowiedź jest krótka, to jest.
To zbliżanie, w jaki sposób kod może zrobić za pomocą obiektowego
język C, ale jeszcze ostatecznie proceduralne.
Nie ma metody wewnątrz z zmienne, jak zobaczysz.
Ale przypomina, że.
I zobaczymy tę funkcję ponownie gdy mamy do PHP i JavaScript
pod koniec semestru.
Ale teraz, pomyśl o tym, jak podpowiedź, co nadejdzie.
Dobre pytanie.
Wszystko w porządku.
Więc merge sort był jak lewe rzeczy ostatnio.
I połączyć sortowania było fajne w Poczucie, że jest to o wiele szybciej,
co najmniej w oparciu o testy pobieżne zrobiliśmy w zeszłym tygodniu, niż, powiedzmy, bańki
sortowanie, wybór sortowania, wstawiania sortowania.
I to, co było po prostu zbyt schludny jak zwięźle i czysto
można je wyrazić.
A co możemy powiedzieć, to była górna zobowiązany na czas trwania do scalenia
sortować?
Tak?
>> PUBLICZNOŚCI: n log n?
>> Głośnik 1: n log n, w porządku. n log n.
I wrócimy do tego, co, że naprawdę oznacza i gdzie to pochodzi,
lecz była lepsza niż Czas
które widzieliśmy na bańce Wybór i wprowadzenie sortowania?
Więc n do kwadratu. n do kwadratu jest większe niż to,
i nawet jeśli nie jest to oczywiste, wiem, że log n jest mniejsza niż n,
więc jeśli n razy coś mniejszej niż n,
to będzie mniej niż n do kwadratu.
To trochę intuicji istnieje.
Ale zapłaciliśmy za to cenę.
To było szybciej, ale temat, który rozpoczął pojawiać się w zeszłym tygodniu był to kompromis.
Mam lepsze wyniki czas mądry, ale to, co
nie mam wydać na inne Natomiast w celu osiągnięcia tego?
>> PUBLICZNOŚCI: Pamięć.
Głośnik 1: Powiedz jeszcze raz?
PUBLICZNOŚCI: Pamięć.
Głośnik 1: Pamięć, lub miejsca bardziej ogólnie.
I to nie było super oczywiste z naszych ludzi,
ale pamiętam, że naszych wolontariuszy były krok do przodu i intensyfikacji
z powrotem, jakby tam tablica tu, a jakby nie
Drugi układ tutaj mogli korzystać, bo
Szacowany gdzieś połączyć tych ludzi.
Nie możemy po prostu wymienić je na miejscu.
Tak połączyć sortowania dźwigni jest więcej miejsca, które
nie muszą się inne algorytmy,
Plusem jest jednak, że jest to o wiele szybciej.
I szczerze mówiąc, w realnej przestrzeni świata te days-- RAM, dysk twardy space--
jest stosunkowo tanie, a więc to, niekoniecznie złe.
>> Więc rzućmy okiem, trochę bardziej metodycznie, na to, co zrobiliśmy
i dlatego powiedział, że n log n.
Więc tutaj są numery, a osiem ośmiu wolontariuszy mieliśmy ostatnio.
I pierwszą rzeczą, że Merge Sortuj kazał nam zrobić, to co?
PUBLICZNOŚCI: Podzielić na dwie części.
Głośnik 1: Powiedz jeszcze raz?
PUBLICZNOŚCI: Podzielić na dwie części.
Głośnik 1: Podział na dwie, prawda.
To bardzo przypomina książka telefoniczna, z podziałem
i podbić bardziej ogólnie.
Tak patrzyliśmy na lewej połowie.
A następnie raz mówiliśmy, sortowanie Lewa połowa elementów,
co my obok powiedzieć?
Sortować lewą połowę lewej połowa, co pozwoliło nam,
Po podzieleniu na dwie części, skupić się na czterech i dwóch.
>> Jak można sortować listy teraz, w żółty, wielkości dwóch, przy użyciu Merge Sortuj?
Oraz podzielić ją na pół, i uporządkować lewą połowę.
I to właśnie tam rzeczy mam trochę głupie krótko.
Jak można sortować listę, która jest z Rozmiar jeden, jak ten numer cztery tutaj?
To sortowane.
Gotowe.
>> Ale jak można sortować listę rozmiar jeden kiedy to numer dwa?
Cóż, to samo, ale teraz to, co było Trzeci i kluczowym krokiem w seryjnej Sortuj?
Trzeba było połączyć w lewo połowa i prawa połowa.
A kiedy już to zrobił, patrzyliśmy na czterech, w jaki patrzył na dwóch.
Zdecydowaliśmy wszelkie prawa, oczywiście dwa na pierwszym,
więc umieścić w jego dwóch miejsce, a następnie przez cztery.
A teraz trzeba trochę do tyłu, i to jest rodzaj charakterystyki
algorytmu jak Merge Sortuj, przewijanie w pamięci.
Jaka była następna linia z tej historii?
Co mam być skupienie się na następny?
Prawa połowa po lewej połowa, która jest sześć i osiem.
>> Pozwólcie mi przejść przez ten bez belaboring punkt za dużo.
Sześć i osiem, a sześć jest sortowane, osiem jest posortowana.
Połączyć je ze sobą tak, a teraz kolejny wielki krok
jest, oczywiście, rozwiązać z prawą połowę Pierwszym krokiem tego algorytmu.
Więc skupić się na jednym, trzy, siedem, pięć.
Następnie skupić się na lewej połowie.
Lewa połowa, że ​​prawa połowa to i następnie łączyć w jedną i trzy.
Następnie w prawo w połowie, a następnie w lewo w połowie z niej, a następnie prawa połowa.
Scalić je, a teraz co krok pozostaje?
Scalanie duży lewą połowę i duże prawa połowa, więc idzie tam,
Następnie dwa, a następnie trzy, cztery, a następnie, po czym pięć, potem sześć, potem siedem, potem osiem.
>> Więc teraz, dlaczego jest to ostatecznie ujawniając, zwłaszcza gdy n i logarytmy więcej
ogólnie raczej uciec, przynajmniej w ostatnich pamięci?
Cóż, zawiadomienia wysokość tej rzeczy.
Mieliśmy osiem elementów, a my podzielić je przez dwa, w dwóch o dwa.
Więc zalogować bazę dwa ośmiu daje nam trzy.
I uwierzcie mi, że jeśli trochę zamglone na tym.
Ale zalogować baza dwa ośmiu jest trzy, tak zrobiliśmy trzy warstwy łączenia.
A kiedy połączyły elementy, jak wiele elementów
nie patrzymy na każdy z tych wierszy?
Całkowita n, prawda?
Ponieważ połączyć górny wiersz, mimo, że zrobiliśmy to po kawałku,
my ostatecznie dotknął każdy numer raz.
I w drugim rzędzie, w celu scalić te wykazy wielkości dwóch,
musieliśmy dotknąć każdego elementu raz.
A następnie tutaj naprawdę wyraźnie w ostatnim wierszu
musieliśmy dotknąć każdego z tych Elementy raz, ale tylko raz
więc tu leży, to nasza n log n.
>> A teraz po prostu zrobić rzeczy trochę bardziej formalne na chwilę, gdy
były do ​​teraz analizować ten na jakimś wyższym poziomie
i starają się zdecydować, a jak Może go o wyrażanie
Czas pracy tego algorytmu po prostu patrząc na niego, a nie
stosując wymyślony przykład?
Cóż, ile czasu byś powiedział kroku jak ten w żółtym zajmie,
jeśli n <2 powrót?
To wielki O czym?
Więc widzę jeden, więc jeden krok, może dwa kroki, bo to, czy
a następnie wrócić, ale to stały czas, prawda?
Więc powiedzieliśmy O (1), a to jak ja wyrazić.
T, po prostu być razem z systemem.
n oznacza wielkość wejścia, więc T (n), po prostu fantazyjny sposób
mówić biegu Czas podany wejście wielkości n
będzie w porządku o stałym czasie, w O (1).
>> Ale poza tym, co z tego?
W jaki sposób można wyrazić czas tej żółtej linii działa?
T o co?
Niby można tu oszukać odpowiedzieć cyklicznie na moje pytanie.
Więc jeśli czas pracy w Ogólnie po prostu powiedzieć, to T (n).
A teraz trochę popływać tu i mówiąc, dobrze, tylko uporządkować lewą połowę,
a następnie posortować prawą połowę.
Jak możemy symbolicznie reprezentują Czas pracy tego żółtej linii?
T o co?
Co wielkość wejścia?
n nad nimi.
Dlaczego nie mogę po prostu powiedzieć, że?
A następnie jest inny T (n / 2), a następnie ponownie, jeśli połączyć dwie posortowane połówki,
ile elementów mam musiał dotknąć całości?
n.
Więc mogę wyrazić to, po prostu być rodzajem szczególnego,
jako czasu pracy w ogóle.
T (n) jest tylko czas przejścia T (n / 2), Plus T (n / 2), lewy i prawy połowę połowę,
Plus O (n), który jest prawdopodobnie n kroki , ale być może, jeśli używam dwa palce,
To dwa razy więcej kroki, ale liniowy.
To niektóre liczba kroków to współczynnik n,
tak możemy wyrazić to, jak ten.
I to, gdzie teraz będziemy punt do widok z naszego gimnazjum podręcznik matematyki
my, że nawrotu ostatecznie kończy się równa tej, n log n razy,
jeśli faktycznie się matematyka bardziej formalnie.
>> Więc to tylko dwie perspektywy.
Jednym z numerycznie zakodowane reprezentatywnego przykładu
za pomocą ośmiu cyfr, i więcej ogólne spojrzenie na to, jak tam dotarliśmy.
Ale to, co jest naprawdę interesujące tutaj jest, ponownie, to pojęcie z jazdy na rowerze.
Nie używam do pętli.
Jestem rodzaju definiowania chodzi o coś w sobie,
Nie tylko to funkcja matematyczna,
ale także pod względem tego pseudo kod.
Ten pseudo kod jest rekurencyjny , że dwa z jego liniami
zasadniczo mówi, aby przejść używać się rozwiązać mniejsze
Problem mniejszych rozmiarach a następnie wielokrotnie
i znowu, aż go zredukować aż do tak zwanego przypadku podstawowym.
>> Więc rzeczywiście wyciągnąć bardziej atrakcyjne wynos od tego w następujący sposób.
Pozwólcie mi iść do gedit i podjąć spojrzeć na niektóre z dzisiejszego kodu źródłowego,
w szczególności ten przykład tutaj.
Sigma 0, który najwyraźniej dodaje numery jeden do n.
Zobaczmy więc, co to zna i zna tutaj.
Po pierwsze mamy kilka obejmuje, więc nic nowego.
Prototyp.
Jestem trochę zamglony na to po kilku dniach,
Ale co powiedzieć Prototyp funkcji jest?
PUBLICZNOŚCI: [niesłyszalne].
Głośnik 1: Co to jest?
PUBLICZNOŚCI: Ogłaszamy go.
Głośnik 1: Ogłaszamy go.
Więc uczysz dzyń, hej, nie faktycznie realizacji tego jeszcze,
ale gdzieś w tym pliku, prawdopodobnie, będzie funkcja nazywa co?
Sigma.
I to jest właśnie obietnica, że to będzie wyglądać.
To zajmie liczbę całkowitą jako input-- i mogę być bardziej wyraźne
i powiedzieć, int n --and to zamierza powrócić int,
ale średnik oznacza, mm, będę się poruszać do realizacji w tym trochę później.
Ponownie, Clang jest głupi.
To będzie tylko wiedzieć, co poinformować go od góry do dołu,
więc musimy przynajmniej dać to wskazówka, co nadejdzie.
>> Teraz przyjrzyjmy się głównym tutaj.
Zróbmy tu i przewinąć w dół zobacz, co robi główny.
To nie tak, że długo z funkcji, a w rzeczywistości konstrukt tutaj zna.
Oświadczam zmiennej n, a następnie I znowu i znowu męczyć użytkownika
dla liczby naturalnej przy użyciu getInt, i jedyne wyjście z tej pętli
gdy użytkownik zastosował.
Do While, używaliśmy do męczyć użytkownika w ten sposób.
Teraz to jest interesujące.
Oświadczam, int o nazwie "odpowiedź".
Przypisać jej wartość zwracana z funkcji o nazwie "sigma".
Nie wiem jeszcze, co to robi, ale Pamiętam, deklarując ją przed chwilą.
A potem ja przekazując wartości, które użytkownik wpisał w, n,
a następnie zgłosić odpowiedź.
Dobrze niech przewijania na chwilę.
Idziemy do przodu do tego katalogu, aby sigma 0, i faktycznie uruchomić ten program
i zobaczyć co się dzieje.
Więc jeśli pójdę do przodu i bieg ten program, ./sigma-0,
i wpisz w pozytywny całkowitą jak dwóch, Sigma,
jak grecki symbol wskazuje, jest po prostu zamiar dodać do wszystkich numerów z
zero, do dwóch.
Tak 0 Plus 1 plus 2.
Więc mam nadzieję, że to powinno dać mi 3.
To wszystko robi.
I podobnie, jeśli uruchomię to znowu i nadać mu numer trzy,
to 3 plus 2, więc to 5 plus 1 powinien dać mi 6.
A potem, jeśli się naprawdę szalony i zacznij pisać w większych ilościach,
powinien dać mi coraz większe sumy.
Więc to wszystko.
>> Więc co sigma wygląda?
Cóż, to całkiem proste.
To jak może wdrożyliśmy to w ciągu ostatnich kilku tygodni.
"Int" będzie typ zwracany.
Sigma jest nazwa, a to trwa Zmienna m zamiast n.
Będę zmieni się góry.
To jest właśnie kontrola poprawności.
Zobaczymy, dlaczego w jednej chwili.
Teraz Oświadczam innej zmiennej, suma, zainicjować go do zera.
To mam to dla pętli iteracji, widocznie dla jasności,
od i = 1 do dnia an = m, który jest co użytkownik wpisze w, a potem
zwiększyć sumę takiego.
A następnie powrócić sumę.
>> Więc kilka pytań.
Jeden, mam prawo w moim komentarzu, że ta unika ryzyka nieskończoną pętlę.
Dlaczego przekazując liczby ujemnej wywoływać potencjalnie nieskończoną pętlę?
>> PUBLICZNOŚCI: Nigdy nie osiągnie m.
>> Głośnik 1: Nigdy nie osiągnie m.
Ale m przechodzi w, więc niech Rozważmy prosty przykład.
Jeśli m jest przekazywana przez użytkownika jako negatywny.
Niezależnie od głównego.
Głównym chroni nas przed to też, więc jestem
jest naprawdę analny z Sigma również upewnić się,
że wejście nie może być ujemna.
Tak więc, jeżeli m jest negatywna coś jak negatywny.
Co się stanie?
Cóż, będzie inicjalizacji jeden,
i wtedy będzie mniejsza lub równa m?
>> Stand by.
Że was-- niech nie, niech nix tę historię.
Nie pytałem na to pytanie, ponieważ ryzyko, że jestem nawiązując do
nie będzie się działo, bo to zawsze będzie większa niż: OK,
I wycofać to pytanie.
OK.
Skupmy się tylko na tej części tutaj.
Dlaczego Oświadczam, niektóre zewnątrz pętli?
Obwieszczenie w sprawie linii 49 mam oświadczył I wewnątrz pętli,
ale on-line 48 Mam oświadczył trochę poza.
Tak.
PUBLICZNOŚCI: [niesłyszalne].
Głośnik 1: Jasne.
Więc przede wszystkim na pewno nie Aby zadeklarować i zainicjować sumę
zero wewnątrz na każdej iteracji pętli,
bo to wyraźnie pokonać Celem sumowanie cyfr.
Ja ciągle się zmienia wartość z powrotem do zera.
A także, co jest inny, bardziej ezoteryczne Powodem tej samej decyzji projektowej?
Tak.
>> PUBLICZNOŚCI: [niesłyszalne].
Głośnik 1: Dokładnie.
Chcę przejść na zewnątrz pętli zbyt na jakiej linii?
Na 53.
Oraz w oparciu o nasze zasada od kilku wykładów temu
zmienne o zakresie, tak naprawdę, do nawiasy klamrowe, które je obejmujàcych.
Więc jeśli nie deklaruje sumę wewnątrz z tych zewnętrznych klamrach,
I nie można go używać w wierszu 53.
Innymi słowy, jeśli zadeklarowana Suma tutaj, lub nawet w obrębie
Pętli, nie mogłem do niego dostęp w 53.
Zmienna skutecznie zniknąć.
Więc kilka powodów tam.
Ale teraz wróćmy i zobaczyć co się dzieje.
Tak sigma zostanie wywołany.
Dodaje się 1 plus 2, lub 1 plus 2 Plus 3, a następnie zwraca wartość,
zapisuje go w odpowiedzi, a printf tutaj Dlatego widzę na ekranie.
Więc to jest to, co my nazywamy iteracyjny podejście, w którym powtórzenie tylko
Oznacza pomocą pętli.
Na pętli, pętla While, While pętla, tylko znowu robi coś
i znowu i znowu.
>> Ale sigma jest rodzaj funkcji w zgrabny że mogę go realizować w różny sposób.
Co to, co po prostu się trochę chłodno,
pozwól mi naprawdę pozbyć z wielu utrudnień
bo tej funkcji jest naprawdę bardzo proste.
Niech go po prostu zredukować do czterech głównych linii
i pozbyć się wszystkich Komentarze i nawiasy klamrowe.
To jest rodzaj oszałamiające Alternatywą wdrożenie.
W porządku, może nie oszałamiające, ale to trochę bardziej seksownego, dobrze,
spojrzeć na to o wiele więcej zwięźle.
Z zaledwie czterech linii kodu, I najpierw trzeba to testow.
Gdy m jest mniejsze niż lub równe zero, sigma nie ma sensu.
To ma być tylko tym przypadku liczb dodatnich
więc jestem po prostu będzie zwracają zero dowolnie
tak, że przynajmniej mają część tzw bazowym.
>> Ale tu jest piękno.
Całość tego pomysłu, dodając, liczby od 1 do n, lub, w tym przypadku,
Można to zrobić poprzez rodzaju przekazując złotówki.
Cóż, to, co jest sumą 1 do m?
Cóż, wiesz co?
To samo jak suma m plus suma 1 do m minus 1.
No wiesz co?
Co sigma m minus 1?
Cóż, jeśli to rodzaj postępować logicznie, to jest taka sama, jak m minus 1
Plus sigma m minus 2.
Więc można trochę tylko-- to jest jak, jeśli jesteś po prostu
próbując drażnić znajomego i zadać pytanie,
Ci niby odpowiedzieć na pytanie, można trochę zachować przekazując złotówki.
Ale co jest kluczowym jest, że jeśli trzymać czyni znak mniejsze
i mniejszy, jesteś nie pytając, co to sigma
n, co sigma n, co sigma n?
Pytasz, co jest sigma n, co sigma
n minus 1, co jest sigma n minus 2?
W końcu Twoje pytanie stanie się, co?
Co jest sigma jednym lub zero, niektóre bardzo małą wartość,
i jak najszybciej się, że Twój przyjaciel
nie zamierzasz zapytać samo pytanie jeszcze raz,
jesteś po prostu powiedzieć, oh to jest zero.
Skończyliśmy grać ten rodzaj z głupim cyklicznej gry.
>> Więc rekurencja jest aktem w programowaniu z funkcji nazywająca siebie.
Program ten, po opracowaniu i uruchomieniu, jest będzie zachowywać się dokładnie tak samo,
ale co to jest to, że wewnątrz klucz z funkcji o nazwie Sigma,
jest linia kodu w którym mamy nazywając siebie,
które normalnie byłoby złe.
Na przykład, co jeśli pierwszy skompilowane to, tak aby sigma--
Marka Sigma 1 ./sigma-1.
Dodatnia, proszę, 50 1275.
Więc to, co wydaje się funkcja być oparte na jednym z testów, prawidłowe.
Ale co, jeśli się trochę niebezpieczne i usunąć tzw sprawę podstawową,
i po prostu powiedzieć, a ja tylko co Ten bardziej skomplikowany niż jest.
Miejmy tylko obliczenia sigma biorąc m, a następnie dodanie
w sigma jednego m minus?
Cóż, co się będzie działo?
Miejmy pomniejszyć.
Miejmy rekompilacji programu, zapisać, ponownie skompilować program,
a następnie gotowe ./sigma-1 powiększanie, Proszę wprowadzić dodatnią liczbę całkowitą, 50.
Jak wielu z was są gotowi do przyzna się do oglądania, że?
>> OK.
Tak może się zdarzyć na wiele powodów,
i szczerze mówiąc w tym tygodniu, że jesteśmy o, aby dać Ci więcej z nich.
Ale w tym przypadku, spróbuj rozumować wstecz
Co by się stało tutaj?
Błąd segmentacji, powiedzieliśmy ostatniego Czas, odnosi się do segmentu pamięci.
Coś złego się stało.
Ale co to było mechanicznie, że wyszło
tutaj z powodu mojego usunięcia z tego tak zwanego przypadku bazowego,
gdzie wróciłem zakodowane wartości?
Co sądzisz poszło nie tak?
Tak.
>> PUBLICZNOŚCI: [niesłyszalne].
Głośnik 1: Ach.
Dobre pytanie.
Tak więc wielkość liczby że byłem podsumowując
ma tak duże, że przekroczone Wielkość wolnej przestrzeni pamięci.
Dobry pomysł, ale nie całkowicie będzie powodować awarię.
To może spowodować całkowitą przepełnienia, gdzie bity po prostu odwrócić
i wtedy pomylić naprawdę duży Numer do jak liczba ujemna,
lecz sam nie powoduje awarię.
Ponieważ na koniec dzień int jest nadal 32 bity.
Nie idziesz do przypadkowo ukraść 33-sza trochę.
Ale dobra myśl.
Tak.
>> PUBLICZNOŚCI: [niesłyszalne].
Głośnik 1: Metoda nigdy nie przestanie działać,
i rzeczywiście nazywa się ponownie i znowu i znowu i znowu
i znowu, i żaden z te funkcje w historii
zakończyć, ponieważ ich jedyny linii kod wywołuje same za siebie znowu i znowu
i znowu.
I co jest naprawdę dzieje się tu i teraz my
może zwrócić tego rodzaju obrazowo.
Pozwól mi przejść do obraz na chwilę.
To jest obraz, który w końcu ucieleśnić
bardziej szczegółowo, co się dzieje wewnątrz pamięci komputera.
I okazuje się, że na Dno tego obrazu
jest coś, co nazywa stos.
To jest fragment pamięci, fragment pamięci RAM,
że jest po prostu stosować w każdej chwili funkcja jest wywoływana.
Za każdym razem, programista, wywołania funkcji,
System operacyjny, jak Mac OS, Windows lub Linux,
chwyta kilka bajtów, może kilka kilobajtów, może kilka megabajtów
pamięci, wręcza je do Ciebie, a następnie pozwala
można uruchomić za pomocą funkcji bez względu na zmienne trzeba.
A jeśli to nazwać kolejnym Funkcja i innej funkcji,
masz kolejny kawałek pamięci i kolejny kawałek pamięci.
>> I rzeczywiście, jeśli te zielone tace z Annenberg reprezentowania tej pamięci,
Oto co się dzieje, pierwszy Czas wywołania funkcji sigma.
To jak wprowadzenie takiego zasobnika na co początkowo pusty stos.
Ale wtedy, jeżeli tacy domaga się, by tak rzec,
wzywając inne wystąpienie sigma, to
jak prosi system operacyjny, ooh, potrzebujemy trochę więcej pamięci,
daj mi to.
A potem robi się piętrzyły się na na szczycie.
Ale co tu jest klucz Pierwsza taca nadal istnieje,
bo wywołany ten drugi podajnik.
Teraz zaś, sigma zadzwonić Sigma, to jest jak z prośbą o więcej pamięci.
Zostanie ułożone na tutaj.
Sigma zadzwonić Sigma, to inna podajnik, który zostanie ułożone na tutaj.
A jeśli to robił, ostatecznie, rodzaj wizualnej mapie
na tym wykresie, co się dzieje na zdarzyć, ze stosem tac?
To będzie przekraczać kwoty pamięci w komputerze jest.
I tak szybko, jak to zielone tacy przekracza linię poziomą
powyżej stosu i sterty nad tym słowem, którego wrócimy w przyszłości,
to jest złe.
Kupa jest inna segment pamięci
i jeśli pozwoli to tace i stos na stos,
masz zamiar przekroczyć własny segment pamięci,
a program jest rzeczywiście zamiar upaść.
>> Teraz, jak na marginesie, ten pomysł rekursji Dlatego
może wyraźnie prowadzą do problemów, ale to nie jest koniecznie złą rzeczą.
Ponieważ uważają, po wszystkim how-- i może
ma to jakiś przyzwyczaić do --how elegancki lub jak proste
że realizacja sigma było.
I nie będziemy używać rekurencji aż tak dużo w CS50,
ale w CS51 i naprawdę każda klasa gdzie można manipulować struktury danych
jak drzewa lub drzew rodzinnych, , że mają jakąś hierarchię,
to jest bardzo, bardzo przydatna.
Teraz, jak na bok, tak, że jako początkujący informatyków
zna niektóre z Google'a wewnątrz żarty, jeśli pójdziesz do Google
i patrzeć, co jest Definicja, powiedzmy, rekurencja, wprowadź.
Aha.
Tak na marginesie, to zatrzymał się kilka.
To było jak 10 minutach kunktatorstwo rano.
Jeśli także Google "krzywo" informacja przechylając głowę slightly--
i ten jest prawdopodobnie najbardziej okropna wszystkim
ponieważ ktoś spędził jak wykonawczych to ich dzień
kilka lat ago-- chodź.
Och, wait--, że to błąd.
>> Tak działa na jednym z Największe strony świecie
są te głupie małe pisanki.
Prawdopodobnie zużywają Numer nieszablonowe linii kodu
po prostu tak, że możemy mieć trochę zabawy takie rzeczy.
Ale przynajmniej teraz masz niektóre z tych wewnątrz żartów.
>> Teraz rzućmy okiem na niektóre z White Lies, który został nam mówi późno,
i zacząć się łuszczyć powrotem niektóre warstwy technicznie
tak, że naprawdę można zrozumieć co się dzieje
i można zrozumieć, niektóre z zagrożeń,
jak Shellshock, że teraz zaczął się
na czele wszyscy na uwagę, przynajmniej w mediach.
Więc tutaj jest bardzo prosta funkcja że zwraca nic, nieważne.
Jego nazwa jest Swap.
To trwa w dwóch zmiennych i nic nie zwraca.
Staje się w A i B.
Tak szybkie demonstracji.
Przywieźliśmy je do góry.
Równie dobrze możemy wziąć trochę złamać się tu na chwilę
i mają coś do picia.
Jeśli ktoś nie miałby nic przeciwko łączenia ja się tu tylko na chwilę.
Jak o tobie w bordową koszulę?
Chodź na górę.
Wystarczy jeden dzisiaj.
Dziękuję, choć.
Wszystko w porządku, a my mamy wymyślanie kto tutaj?
Jak masz na imię?
>> GŁOŚNIK 4: Laura.
>> Głośnik 1: Laura.
Chodź na górę.
Więc Laura, bardzo proste wyzwanie dzisiaj.
Nice to meet yo.
Wszystko w porządku.
Tak więc mamy tu trochę mleka i mamy trochę soku pomarańczowego tutaj
i że niektóre kubki zapożyczone z Annenberg dziś.
>> GŁOŚNIK 4: Borrowed.
Głośnik 1: I będziemy iść do przodu i daje pół szklanki tego.
Wszystko w porządku.
I damy ci pół Szklanka mleka.
Aha, i tak, że można pamiętam, co to było jak,
Przypomniałem sobie, aby doprowadzić to się i dziś.
Ok.
Jeśli nie masz nic przeciwko, zobaczymy, że Można umieścić je na swoich własnych okularów
jeśli chcesz.
To będzie świat z oczu Laury.
Wszystko w porządku.
Więc twoim celem, biorąc pod uwagę dwie filiżanki ciecz tutaj, mleko i sok pomarańczowy,
jest zamiana obu zawartość żeby sok pomarańczowy przechodzi w kubku mleka
oraz mleko przechodzi szklanki soku pomarańczowego.
>> GŁOŚNIK 4: Czy dostanę kolejną filiżankę?
Głośnik 1: Cieszę się, że pytasz, choć byłoby znacznie lepiej filmy
jeśli nie poprosił.
Ale tak, możemy zaoferować Państwu trzeci puchar to pusty, oczywiście.
Wszystko w porządku.
Więc zamienić zawartość nie.
Bardzo ładne.
Bardzo dobre.
Robisz to niezwykle starannie.
I kroku trzeciego.
Wszystko w porządku.
Doskonałe.
Wielkie brawa byłoby to dobre dla Laury.
Wszystko w porządku.
Mamy mały prezent na pożegnanie dla Ciebie, ale pozwól mi wziąć te.
Dziękuję bardzo.
Tak więc prosty przykład, chociaż wykazać, że jeśli nie
chcesz zamienić zawartość z dwóch pojemników,
lub nazwijmy je zmienne, trzeba trochę tymczasowego magazynowania
do etapu jedną z zawartości w taki że można zrobić swap.
Tak naprawdę, to kod źródłowy tutaj w C to przedstawiciel dokładnie to.
Jeżeli sok pomarańczowy był i mleka był b, i chcieliśmy zamienić dwa,
możesz spróbować coś twórczego przez wylewanie się ze sobą,
ale to chyba nie byłoby kończy się szczególnie dobrze.
I tak używamy trzeci kubek, połączenie to tmp, T-M-P zgodnie z konwencją,
i umieścić zawartość L w, wtedy zamienić jedną filiżankę,
następnie umieścić w Dzienniku Urzędowym Oryginalny puchar, tym samym
osiągnięcia, dokładnie tak, jak Laura zrobiła, swap.
>> Więc zróbmy dokładnie to.
Pozwólcie mi iść do przodu i otworzyć się na przykład, że za
w rzeczywistości nazywa się "nie zamienić ", ponieważ nie jest to
tak po prostu zrobić jak mogłoby się wydawać.
Tak więc w tym programie, zauważysz, że Używam stdio.h, nasz stary przyjaciel.
Mam prototyp do wymiany tam, które
oznacza jego realizacja jest prawdopodobnie w dół poniżej,
i zobaczmy, co to główny Program zrobi dla mnie.
Pierwszy raz oświadczam, int x dostaje jeden, i int y dostaje dwa.
Więc myślę o tych, w Dzienniku Urzędowym mleko i, odpowiednio.
A potem po prostu printf mówiąc x to
i y jest to, tak mogę wizualnie zobaczyć, co się dzieje.
Wtedy mam printf twierdząc że jestem swapping dwa,
a potem wydrukować twierdzą, że są one zamienione,
i wydrukować x i y ponownie.
Więc tutaj w wymiany jest dokładnie to, co Laura zrobiła,
i dokładnie to, co widzieliśmy na Ekran chwilą.
>> Więc idź naprzód i być bardzo rozczarowany.
Dodać nie swap, i uruchomić bez swapa, powiększenie wyjścia tutaj.
Wprowadź x oznacza 1, y oznacza 2, zamiana zamienione.
X jeszcze 1 i y jest w dalszym ciągu 2.
Więc chociaż, szczerze mówiąc, to wygląda dokładnie jak, choć bardziej technicznie,
co Laura nie, nie wydaje się do pracy.
Więc dlaczego tak jest?
Cóż, okazuje się, że gdy możemy napisać program tak
który zarówno główny, podkreślił tutaj, a następnie innej funkcji, jak zamiana,
podświetlony tutaj, które wzywa świat
wygląda trochę coś jak te tace chwilą.
Po pierwsze jest wywoływana głównym, to jak pytanie system operacyjny
na trochę pamięci na każdy lokalny zmienne x i y, jak że głównym ma,
i kończy się tam.
Ale jeśli główne połączenia zamienić, a głównym przechodzi do wymiany dwa argumenty, A i B,
sok pomarańczowy i mleko, to nie jest tak, wręczając sok pomarańczowy i mleko
do Laury.
Co robi komputer, jest to przekazuje kopie soku pomarańczowego
i kopie mleka do Laury, tak że co ostatecznie wewnątrz tego podajnika
jest jedna wartość drugiego, lub L i mleko, ale ich kopie,
tak, że w tym momencie w historii, nie
to L i mleka w każdym z tych zasobników.
Nie jeden, a dwa W każdym z tych zasobników
i funkcja wymiany jest rzeczywiście pracuje.
To zamiana ich w środku z drugim najwyższym tacy,
Zamiana ale nie ma wpływu.
I opiera się tylko na niektórych Podstawową zasadą mamy
mówił o przed, a nawet zaledwie kilka minut temu, co
może wyjaśnić, dlaczego zmiany b wewnątrz swapu
ma wpływ na x i y, chociaż Zdałem x i y do funkcji swap.
Co znajduje się tutaj, że kluczowym słowem może uproszczeniu wyjaśnić?
Myślę, że słyszałem go tutaj?
PUBLICZNOŚCI: Powrót.
Głośnik 1: Powrót?
Nie powrócić.
Chodźmy z jednym innego.
Co to jest?
>> PUBLICZNOŚCI: [niesłyszalne].
>> Głośnik 1: OK, więc return-- mogliśmy uczynić pracę powrotu w historii,
ale jest jeszcze prostsze wyjaśnienie.
PUBLICZNOŚCI: Zakres.
Głośnik 1: Zakres.
Wezmę zakresu.
Tak więc zakres, pamiętam gdzie nasza x i y oświadczył.
Oni deklarowane wewnątrz z głównym aż tutaj.
i b, w międzyczasie, skutecznie oświadczył
wewnątrz swapu, nie całkiem w nawiasy klamrowe, ale nadal
w ogólnej powierzchni wymiany.
I tak naprawdę, i b tylko tacy istnieją w tym
z Annenberg, to Drugi fragment kodu.
Więc jesteśmy rzeczywiście zmiany kopię, ale to naprawdę nie wszystko, że pomocne.
>> Warto więc przyjrzeć się to trochę niższy poziom.
Mam zamiar wrócić do Źródło katalog,
i idę do pierwszego powiększyć tutaj, i tylko
aby potwierdzić, że jestem w tym większe okno terminala,
Program nadal zachowuje się tak.
Przypuśćmy teraz, że ten nie jest celowe.
Oczywiście chciałem swapa do praca, więc czuje się jak robaka.
Teraz mogę rozpocząć dodawanie Wiele printf do mojego kodu,
drukowanie X tutaj, y nad tutaj, tutaj, b tutaj.
Ale szczerze mówiąc, to chyba to, co robiłeś przez kilka tygodni
teraz, w godzinach pracy urzędu i podczas pracy w domu
na psets próbuje znaleźć kilka błędów.
Ale zobaczysz, jeśli nie masz, że problemem ustawić trzy wprowadza cię
do polecenia o nazwie GDB, gdzie GDB, GNU debugger,
ma sobie całą masę Cechy, które mogą rzeczywiście
pozwala zrozumieć sytuacje tak, ale nieodparcie,
rozwiązać problemy i znaleźć błędy.
Więc mam zamiar to zrobić.
Zamiast ./noswap, zamiast mnie zamierza uruchomić GDB ./noswap.
Innymi słowy, mam zamiar uruchomić mój Program nie w Bash, nasz nowy przyjaciel
dzisiaj.
Zamierzam uruchomić mój Program noswap wewnątrz
tego innego programu o nazwie GDB który debugera, które
to program, który jest zaprojektowany, aby pomóc Wy, ludzie, znaleźć i usunąć błędy.
Więc jeśli uderzę Uruchom tutaj, nie okropna ilość tekstu
że nigdy tak naprawdę nie trzeba czytać.
To w zasadzie rozproszenia z wiersza, który
Mam zamiar hit Control-L wstać o tam na górze.
To jest szybka GDB.
Jeśli chcę, aby uruchomić ten program teraz, w tej małej ściągawki na dzisiejszym
zjeżdżalnia sugeruje, Run to pierwszy Polecenia, które ma na celu wprowadzenie.
A ja po prostu się do typu uruchomić się tutaj wewnątrz GDB,
i rzeczywiście prowadził mój program.
Teraz jest jakaś dodatkowa Wyjścia ekranie, jak to
ale to GDB prostu analny i mówi nam, co się dzieje.
Tak naprawdę nie musisz się martwić o te szczegóły teraz.
Ale to, co jest naprawdę fajne o GDB, jeśli zrobić to again--
Control-L czyści screen-- pozwól mi odejść dalej i wpisz "złamać głównym," w ten sposób,
kiedy naciśnij Enter, co jest ustawienie zwany próg w noswap.c,
Linia 16, czyli tam, gdzie GDB zorientowali się mój program faktycznie
jest moja funkcja w rzeczywistości.
To my na razie zignorować ale to jest adres
pamięć specyficznie tej funkcji.
Więc teraz, kiedy typem uruchomienia, zauważyć, co jest cool tutaj.
Mój program przerywa na linii I powiedział GDB aby wstrzymać wykonanie na.
Więc nie mam do teraz zmiana kodu, dodać kilka printf, w przekompilować, powtórka
to, zmienić, dodać kilka printf, w zapisać, ponownie skompilować go, uruchom go.
Można po prostu przejść przez mój program krok po kroku po kroku w ludzkiej prędkości,
nie na Intel-wewnątrz rodzaju prędkości.
>> Więc teraz zauważyć tę linię pojawia się tutaj, a jeśli wrócę
do mojego programu w gedit, Zauważ, że to jest rzeczywiście
Pierwszy wiersz kodu.
Jest linia 16 w gedit.
Jest linia 16 w ciągu GDB, a nawet choć ten czarno-biały interfejs
nie jest tak użytkownik przyjazny, oznacza to,
że linia 16 nie został wykonany jeszcze, ale o to, aby być.
Tak naprawdę, jeśli polecenie print x, nie printf, tylko print x,
I trochę fałszywe wartości nie od zera, ponieważ x nie został jeszcze zainicjowany.
Więc mam zamiar wpisać obok, lub jeśli chcę być nadzwyczajnego, po prostu n dla następnego.
Ale kiedy typem obok wejść, teraz zauważyć, że porusza się na linii 17.
Tak logicznie, jeśli mam wykonywane Linia 16 i teraz wpisz Drukuj X,
co mam zobaczyć?
Jeden.
>> A teraz to jest prawda mylące.
$ 2 to tylko fantazyjny sposób, jeśli Ciebie Aby odnieść się do tej wartości później,
można powiedzieć "znak dolara dwóch."
To jak odniesienie tyłu.
Ale teraz, po prostu zignorować.
Co ciekawe jest to, co jest po prawej jednakowej znaku.
A teraz, jeśli napiszę następny raz i druk y, powinny widzę 2.
Teraz można również drukować x znowu, i szczerze mówiąc,
jeśli mam już trochę mylić, gdzie jestem, mogę pisać listy do listy
i po prostu zobaczyć jakiś kontekst wokół punkt w rzeczywistości jestem.
A teraz mogę pisać obok, a tam x 1.
Teraz wpisz obok.
Och, y 2.
I znowu, to jest mylące, bo wyjścia GDB za
jest zmieszane z własnej produkcji.
Ale jeśli pamiętać, by spoglądając w tę iz powrotem w kodzie
lub r to z boku przez strony, być może, będziesz
zobaczyć, że naprawdę jestem wzmocnienie przez mój program.
>> Nie zauważyć, co się dzieje obok, dosłownie.
Oto wiersz 22.
Pozwól mi przejść przez to, co porusza się na do 23, a jeśli mogę wydrukować x teraz, jeszcze jeden.
A jeśli mogę wydrukować y teraz, jeszcze jeden.
Więc to nie jest przydatne ćwiczenia.
Warto więc powtórzyć to.
Pozwól mi wrócić do góry i rodzaj uruchomić ponownie.
I to mówiąc, program debugowanym że jest
rozpoczęty już, rozpoczyna się od początku.
Tak, zróbmy to jeszcze raz.
I tym razem zróbmy następny, następny, następny, następny, następny,
ale teraz robi się ciekawie.
Teraz chcę, aby wejść do Swap, więc nie wpisz obok.
I typu krok, a teraz zauważyłem skoczył mnie do linii noswap.c 33.
Jeśli wrócę do gedit, co linia 33?
To pierwszy rzeczywisty linii kodu wewnątrz swap.
Co jest miłe, bo teraz mogę rodzaj grzebać i uzyskać ciekawy
co do tego, co się dzieje naprawdę tam jest.
Pozwól mi wydrukować tmp.
Wow.
Dlaczego niektórzy mają tmp szalony, fałszywe wartości śmieci?
PUBLICZNOŚCI: To nie został zainicjowany.
Głośnik 1: To nie został zainicjowany.
I rzeczywiście, po uruchomieniu programu, dostaniesz całą masę pamięci
przez system operacyjny, ale nie zainicjalizowany żadnych wartości,
więc cokolwiek bity jesteś widząc tutaj, nawet jeśli jest to
ten szalony duży negatywny liczba, oznacza po prostu
że są to pozostałości z Niektóre wcześniejsze korzystanie z tej pamięci RAM,
mimo, że nie mają ja potrzebowałem jeszcze.
Więc teraz mam zamiar iść do przodu i typ następny, i gdybym teraz wpisać druku tmp,
co mam zobaczyć?
Niezależnie wartość była jest pierwszym argumentem, tylko
jak x był pierwszy sprawa jest przekazywana w,
tak ix powinny być takie same, więc drukować tmp powinien wypisać mi jeden.
>> Więc to, co zobaczysz w zestawie problemu trzy to swego rodzaju samouczek na GDB,
ale uświadomić sobie, że to jest początek od spojrzenia na narzędzie, które rzeczywiście
pomoc w rozwiązaniu problemów o wiele bardziej skuteczne.
Co jesteśmy ostatecznie zamiar zrobić w środę
jest zacząć się łuszczyć powrotem kilka warstw i usunąć niektóre kółka.
To coś nazywa się ciąg znaków, który używaliśmy przez jakiś czas,
my jedziemy powoli zabieraj od Ciebie i zacząć mówić o
coś bardziej ezoterycznie znany jako char *,
ale mamy zamiar zrobić ładne i delikatnie pierwsze chociaż wskaźników,
jak nazywa się je, można zrobić kilka bardzo złe rzeczy, jeśli nadużywane,
patrząc na trochę od claymation nasz przyjaciel Nick Parlante Stanford
University, profesor w komputerze nauka, która ułożyła ten podgląd
z tego, co nadchodzi w środę.
>> [ODTWARZANIE]
Hej, Binky.
Obudź się.
To jest czas dla wskaźnika zabawy.
>> Co to jest?
Dowiedz się o wskazówki?
Och, cukierek!
[KONIEC ODTWARZANIE]
Głośnik 1: To czeka na Ciebie w środę.
Zobaczymy się potem.
[ODTWARZANIE]
-I teraz, Deep Thoughts, przez Daven Farnham.
>> Dlaczego uczymy C?
Dlaczego nie +?
>> [Śmiech]
>> [KONIEC ODTWARZANIE]