>> [За възпроизвеждане на музика]
>> SPEAKER 1: Добре, това е CS50, и това е началото на четири седмици,
и както може би сте чували или прочетете, светът е бил край.
Отивате всички из интернет е бил на познанията и информираността
на бъг в една програма, език за програмиране, наречен Bash.
Това е чудесно маркови като Shellshock, или вратата на Bash,
но статии като тези не са били рядкост.
И в действителност, много от тях донесе обратно спомени от Heartbleed,
които може би сте забелязали в натиснете отново тази пролет, което
беше по същия начин доста драматично.
Сега на тези от вас, тук днес, колко от вас имат,
дори и да не разбирам какво всичко е въпрос, чувал Shellshock?
Добре, а колко от вас има компютри, които са в уязвимо положение?
OK, трябва да има много, много повече ръце точно сега, по причини, ще видим.
>> Нека хвърлим един поглед към това, което е продължава в медиите
и след това да го обясня малко тук за нас е технически.
>> SPEAKER 2: Експерти по сигурността са предупреди, че сериозен недостатък може
да за да засегне стотици милиони потребители на интернет в света.
И така, какво точно е бъг, който е бил наречен Shellshock, и какво прави той?
Е, Shellshock е известен също като Баш бъг, софтуерът го експлоатира.
Хакерите използват вируса да сканира уязвими системи, работещи под Linux и Unix
операционни системи и след това да ги заразят.
Bash е обвивка на командния ред.
Това позволява издаване потребители заповядва да започне програми и функции в рамките на софтуер
чрез въвеждане на текст.
Това обикновено се използва от програмистите, и не трябва да бъдат отворени към широкия свят,
макар Shellshock променя това.
>> Е, worringly, някои анализатори предупреждават, че то би могло да бъде по-голяма заплаха,
защото Shellshock позволява пълна контрол на заразената машина,
като има предвид, Heartbleed разрешено само хакери, за да шпионира компютри.
Това е толкова сериозна, че е е класиран на 10 място от 10
за тежест от Националната Уязвимост Database.
2.3 на всички уеб сървъри са най- риск, включително и някои Mac компютри.
Е, не забравяйте да закърпи вашите системи сега.
Всеки хостинг уебсайт бягане засегнатите операционни системи
трябва да предприемат действия възможно най-скоро.
Всеки, който може да си позволи това трябва да изглежда за прилагането им наблюдение и уеб
защитни стени, за да се грижа за някакви атаки.
SPEAKER 3: Най-лошото нещо, че може да се случи е
че някой би могъл да напише код, който автоматично ще отида и да сканирате
интернет и това би засегнало Всички тези компютри.
И след като го правят, добре, най-лошото нещо, което можеше да направи
е просто да изтриете всичко, или затвори обектите надолу.
Така че ние може да видите щети от тази гледна точка,
където ще имаме злонамерени хора който току-що реши да предизвика хаос
като приведе системи надолу или изтриване файлове, и такива неща.
SPEAKER 2: Някои казват, че това е един от най-трудно да се измери
бъгове в година, и го може да отнеме седмици или дори
месеца, за да определят крайната му въздействие.
>> SPEAKER 1: Така че всичко това е вярно, но смешното е, че почти всички
на образността току-що видяхте, с изключение може би на клавиатурата,
няма нищо общо с бъг, каквато.
Сървъри и кабели и така нататък, Това е нещо тангенциално, свързани,
но в основата е всъщност доста запознати какво става тук.
Всъщност, нека да отидат в нашата CS50 уред.
Нека да вървим напред и да се максимизира терминален прозорец тук.
А вие момчета са използвали това, или вградения версия от него,
в Gedit, за да пишат програми, въведете команди, и така нататък,
и това е действително, и има бил в продължение на седмици, Bash, B-A-S-H.
Това е най-Борн отново Shell, който е само един луксозен начин на казвайки:
това е програма, която има мига бързо, ефективно,
който седи там и те чака за вход за вас.
И това е командата линия интерфейс, чрез който
момчета са били работещи команди и в крайна сметка съставянето и след това работи
програми.
>> Но Bash е и програмиране език в следния смисъл.
Вие знаете, че има команди като CD и LS, а също и звъня и други,
но можете да зададете вашите собствени команди от прилагането им в Bash.
Сега ние няма да навлиза в големи подробности
за да Баш на езика за програмиране, но Знам, например, че в момента,
там не е команда, наречена "здравей".
Така че може да се намери в един от тези пакети.
Това не е инсталиран на компютъра ми.
Помолете вашия администратор.
Но ако искам да има една програма наречен "здравей" в Bash или в моя ред
Аз всъщност може да се използва синтаксис, който е съвсем като C. Това не е съвсем същото,
но тя изглежда доста сходен с функция, макар и липсват някои подробности.
Сякаш нищо не може да се случи, но сега, ако напишете "здравей"
всъщност можете да напишете програма, а не в C не, в Java,
не в друг програмиране език, но сам по себе си Bash.
>> Сега ключът тук е, че аз написах назовем Исках да дам тази нова команда,
и скобите също са символ на това е функция.
Като настрана, вие също може да направи забавно неща, а в действителност, дори и за Mac OS,
това е програма, наречена терминал.
Той идва вграден в ничии компютър, който има Mac в тази стая,
и можете да направите подобни неща в Mac OS, но можете да отидете по-далеч.
И това е малко по допирателна, но това е вид забавление.
Тази сутрин ми напомни, когато мисля това чрез,
на малка игра Използвах да играе с един от бившите TFS CS50 е
при което всеки път, когато той ще си тръгне от клавиатурата си с екранния си отключена,
Бих изпълни команда като това-- "казват здравей".
И сега всеки път, когато той се върна, за да му клавиатура, след като изчисти екрана
и той ще седне, Опитвам се да направя някаква работа,
списък на съдържанието на неговата directory--
>> [AUDIO PLAYBACK]
>> Здравейте.
Здравейте.
>> SPEAKER 1: Така че, в справедливост, това не е всъщност "здравей".
Той обикновено е нещо, по-близко до че--
[AUDIO PLAYBACK]
-Beep.
SPEAKER 1: --that I would-- така че компютърът му ще
Кълна се в него всеки път, когато той действително седна на клавиатурата си.
И много бързо той измисли да не напускат екрана си отключена.
Но това предполага вид глупаво забавно, че
може да има с нещо като Bash.
Но това е малко по- сериозна, за да бъде сигурен, от това.
И в действителност, това е един от най- Най-опасното и дълго-трайни бъгове
че е наистина хит на света в глобален мащаб.
Този бъг е бил около за около 20 години,
и ще бъде постигнат само с момент от относителната му простота.
>> Така че това е представител заповядай ако
притежавате Mac, буквално точно сега когато имате капак си отворени,
можете да се опитате да пишете в тази програма, наречена Terminal.
Терминал е под Заявленията Utilities--
за пръв път, потребителите на Windows, не трябва да притеснявате за този конкретен threat--
но тези от вас, с Mac-ове може да въведете това в един прозорец като аз ще направя тук,
и ако се объркате че в тази програма
наречена Terminal, като аз ще направя сега, Ако видите думата "уязвим"
компютърът ви е уязвими към експлоатация.
>> Сега какво означава това всъщност означава?
И това е наистина някои доста луд синтаксис,
но нека поне да очертае някои интересни аспекти.
Така че има някакъв синтаксис, който изглежда малко запознати, най-малко от C
и програмирането като цяло.
Виждам някои скоби, точка и запетая, фигурни скоби, както и такива,
но се оказва, че този глупаво нещо тук в жълто
е основно функция който не прави нищо.
Средствата за дебелото черво не правят нищо, и запетая означава да спрем да правим нищо.
Така вътре на тези фигурни скоби, фактът,
че имам равен подпише наляво, това
е по същество създаване команда или променлива,
наречена X, и да го възлагане че жълто малко код там.
Това може да бъде нещо като "ехо здравей "или" казват звуков сигнал "или нещо
близко до това.
Но забележете, ако очите ви скитат допълнително надясно,
има още за тази линия от само до края на тази точка и запетая.
"Ехо уязвими", а след това отвъд това има още повече.
Друга точка и запетая, Баш -c :.
>> Така че, дълга история кратко, тази линия на код е
достатъчни за убедителна компютър, на който е
уязвими към правя нещо че вие ​​искате да направите,
защото има бъг в Bash, при която макар Bash е трябвало да спре
нощни линии на команда полето там след жълт текст
за 20-те години стар бъг, Всъщност Bash е бил четене
отвъд тази точка и запетая и доста много прави това, което е казал.
>> И така, какво е отражението от които в крайна сметка?
Току-що каза, че "ехо здравей" или "ехо-уязвими",
Но какво, ако си направил нещо всъщност злонамерени, като RM-RF *
които може да не някога сте написали преди,
и честно казано, най-вероятно не трябва да е твърде скоро,
защото можете да направите много на увреждане с него.
Защо?
RM прави това, което, разбира се?
Премахва.
* И какво означава това?
All.
Така че това е така наречената див карта, така че това означава
изтриете всичко в текущата директория.
-r случва да означава рекурсивно, което означава, че ако това, което изтриване
е директория, а вътре от там е други файлове и други директории,
рекурсивно потопите в там и да изтриете всичко това.
И -f е най-лошото от всички тях.
Някой знае ли какво означава -f тук?
Force.
Така принуди средства, дори ако това е лоша идея,
го направя, без да ме накара за по-нататъшно потвърждение.
Така че, знаете ли, ние се смеят това, но честно казано, аз вероятно
тип, това няколко пъти на ден, защото реалността
е, че е най-бързият начин да се изтриете цял куп неща.
Но дори и аз направих някои щети.
>> Но ако ви се налага да подвежда компютър в определянето на някаква глупава променлива
или функция, наречена X, но тогава разиграва компютъра в изпълняващата
извън границите на тази функция, след тази точка и запетая,
бихте могли наистина трик компютър в изпълнение на нещо като RM-RF
или командата Email или командата Copy.
Всичко, буквално можеш да направиш с компютър, независимо дали това е изтриване на файлове,
създаване на файлове, спам някой, атакува някои сървър от разстояние,
ако можете да го изразя с команда, можете
може да подвежда компютър в правиш това.
>> Сега това, което е пример за как можете да направите това?
Е, има много компютри на интернет бягане Баш.
Всички потребители нас Mac са сред тях.
Много от Linux сървъри са сред тях, както и Unix сървъри.
Windows отново получава относително разстояние от куката
освен ако не сте инсталирали специален софтуер.
Сега много от сървъри, за Например, работят уеб сървъри,
и в действителност Linux е може би най- най-популярната операционна система
да работи на компютри в интернет които са генерирането на уеб страници.
Сега, както ще видим по-късно в семестъра, когато
ви изпрати искане от Вашата browser-- Chrome,
Internet Explorer, whatever-- към отдалечен сървър,
Оказва се, че въпреки че просто написали www.example.com,
Вашия браузър е изпращане на съобщение това е малко по-тайнствена, като този.
>> Но забележите нещо странно.
Първите два реда Никога не съм виждал преди,
но те не изглеждат особено заплашително.
Но забележете какво съм откраднал за третия ред тук.
Ако лош човек е трябвало да изпрати съобщение като това от своя компютър
към уязвима Mac или уязвима Linux сървър,
Най-смешното е, че Bash, че просто малко командния ред,
е вездесъщ и често е употребяван по същество изпълни
съдържанието на съобщение, което го получава.
И от тази логика, може да трик уеб сървър, следователно,
чрез изпращане на нещо подобно User-Agent, който обикновено
е трябвало да се каже, името на вашия браузър.
User-Agent Chrome, User-Agent интернет Explorer, User-Agent Firefox, тази
е само на вашия браузър начин на самия идентифициране.
Но ако лош човек много умело казва, mm-mm, аз съм
Няма да ви кажа, какво ми браузър е,
Аз, вместо да ти изпратя това загадъчен изглеждащи нещо с RM-RF
* В нея, вие можете буквално да измамят уязвими уеб сървър в интернет
в изпълнение на точно това в има за изтриване на всички файлове.
И честно казано, това не е дори и най-лошото от него.
Можете да направите нищо.
Можете да започнете разпределена отказ на услуга атака
ако ви изпрати това съобщение до цели букети от уеб сървъри
и след това трябваше всички тях се спускат, за Например, на Harvard.edu сървъри,
и можете да сортирате от взрив по дяволите от тях
от трафика в мрежата, че е задейства по друг начин от този лош човек.
>> Така че, дълга история кратко, почти всички в тази зала, който е собственик на Mac
е уязвима за това.
Сребърната облицовка е, че освен ако не сте работещ уеб сървър на вашия лаптоп,
и освен ако не сте в действителност конфигуриран да позволи нещо подобно SSH в нея,
вие сте всъщност безопасно.
Тя е уязвима, но няма едно се опитва да получите във вашия лаптоп,
така че можете да бъдете сигурни, някак.
Въпреки това, Apple скоро ще бъде актуализиране на решение за това.
В света на Linux вече е освободен редица поправки за Fedora и Ubuntu
и други версии на Linux, и наистина ако ви свършат актуализация 50 в уреда,
дори и това също ще бъде актуализирани и коригирани.
Но това също не е наистина е уязвима,
защото освен ако не сте поиграл с уреда
и да направи своя лаптоп публично достъпни в интернет, което не е
по подразбиране, вие сте всъщност е добре, защото
на защитни стени и други техники.
>> Но това е краен пример за бъг че сме живели в продължение на буквално 20
години, и кой знае, ако някой през цялото това време е известно за него?
И в действителност, това е една от основните предизвикателства
че ние ще видим по-късно в семестър за сигурността,
е, че точно както в реалния свят, добрите момчета са в неизгодно положение.
За да се запази на лошите момчета, ние трябва да уверете се, че всяка врата е заключена,
че всеки прозорец е сигурна, че всяка точка на влизане в дома
е сигурен, за да запази лошите момчета.
Но това, което прави лош човек трябва да направя, за да всъщност компрометира вашия дом
и да открадне от вас?
Той или тя просто трябва да се намери един отключен врата, един счупен прозорец, или нещо
по тези линии, и това е най- едно и също нещо в компютърната сигурност.
Можем да напишем милиони линии на програмния код
и прекарват стотици или хиляди на час, които се опитват да го правилно,
но ако се направи само едно грешка в коректност,
можете да поставите цялата система и Наистина в този случай, целият интернет
и световно застрашени.
>> Така че, ако искате да научите повече за това, отидете на този адрес тук.
Няма нужда за действие тази вечер, освен ако не сте
сред тези, по-удобно, че са Стартирането на собствен уеб
сървър, в който случай трябва, В действителност, да се актуализира софтуера си.
>> И това също е заглавието на реч, а сега и на хартия,
че сме свързани въз уебсайт курс за днес.
Това беше от колега на име Кен Томпсън, който
приемаше много известен награда в областта на компютърните науки,
и той е дал тази реч от няколко години Преди, по същество на същата тази тема.
Питам хора на въпроса, трябва ли наистина
доверие, в крайна сметка, на софтуер, който ми е даден?
Например, всички ние имаме писането на програми,
и ние сме били съставяне тях с звъня.
И за да ви е известно, си написал всички програми за CS50, където има
с гръб към вратата на видове, има и начин , че е лош човек, ако използвате вашата програма,
може да поеме вашия компютър?
Вероятно не, нали?
Марио и алчни, и Credit.
Това са всички доста малки програми.
Вие ще трябва да бъде доста лошо, ако действително
направи целия си компютър уязвими след писмено 10 или 20 реда код,
или най-малко знае на някои на последиците за сигурността.
Сега мога да кажа, че шеговито, но ние отиваме да се види днес
и тази седмица това е всъщност наистина, много лесно
да бъде лошо и да направи дори кратки програми уязвими.
>> Но за сега, най-малко, да разбере, че въпросът се иска тук
е около звъня в компилатор.
Защо сме били доверявайки звъня за последните две или три седмици?
Кой е казал, че всеки, който пише звъня не разполага с "ако" състояние там
която по същество се инжектира някои нули и такива във всяка програма го компилира
че ще позволи на него или нея достъп вашия компютър, когато сте заспали
и вашия лаптоп капак е отворен и компютърът ви работи?
Така ли е?
Ние имаме този вид на полето чест система Сега, когато ние вярваме, че звъня е легален.
Вярваш ли, че уредът е легален.
Вярваш ли, че буквално всяка програма на вашия Mac или PC е надежден.
И тъй като тази проста бъг предполага, дори ако това не е злонамерен,
че абсолютно не е вероятно да се случи.
>> Така че трябва да се плаши като ада.
Честно казано, няма прост разтвор на другия
от един вид на информираност на обществото на нарастващата сложност
че ние строим на върха на нашите компютърни системи,
и как все по-уязвими ние може да бъде много добре.
>> Сега с това каза, Breakout.
Така Breakout е проблем постави три, и Breakout е игра от недалечното минало
, че може да си припомни, но за нас в проблем зададете три,
тя ни позволява да предприемем нещата обратно с една степен
така че когато пишем програми, дори в терминален прозорец, подобен на този,
всъщност ние може да работи, в крайна сметка, графични програми не
за разлика от тези, които имахме достъп в Scratch.
Така че това е те години на персонала изпълнение на Breakout,
който е само на тази тухла-чупене игра, която се движите гребло обратно
и т.н., и те удари топката срещу тези цветни тухли до върха.
Така че това ни доставят нещо обратно до мястото, където
ние бяхме в състояние да бъде много бързо със Scratch, а сега с C,
прилагане на собствената ни графични потребителски интерфейси.
>> Нещо повече, този проблем набор представлява първия
в която ние даваме ви куп код.
И в действителност, аз донесе изрична внимание на това, тъй като особено
за тези, които по-малко удобни, тази проблем настроен, поне на пръв поглед,
ще се чувстват като сме го вземе с една степен.
Защото ние сме ви дали, за някои от търсенето
и сортиране проблеми в pset, куп код, който ние написахме,
и няколко коментари които казват "да направя",
където ще трябва да попълнят празните места.
Така че не е твърде страшно, но това е първият път,
ние ви раздава код, който трябва да първо четене, разбиране, и след това се добавят към
и го завърши.
>> И след това с Breakout, отиваме да направят същото,
който ви дава няколко десетки повече линии на код, който, честно казано, да ви даде
много на рамката за игра, но спрете кратко
на прилагането на тухли и топката и гребло,
но правим изпълнява някои други функции.
И въпреки че на пръв поглед, отново, особено ако по-малко удобни,
може да изглежда особено трудна и ли, че има толкова много нови функции
, което трябва да приключи ума си наоколо, и това е вярно.
Но имайте предвид, че е съвсем като Scratch.
Коефициентите са, че не се е възползвал от всички пъзел парчета в Scratch.
Коефициентите са, че не се грижи за увиване ума си около всички от тях
защото всичко, което се е бърз поглед да се разбере, о,
това е, което мога да направя с това парче пъзел.
И наистина, в проблем зададете 3 спекулация, ние ще ви насочи
в документацията, която ще ви запозная с някои нови функции,
и в крайна сметка на програмирането изгражда, който използвате.
Условия, шлейфове, променливи и функции
ще бъде идентично това, което сме виждали до този момент.
>> Така че, наистина, какво ще даде ви е някакъв код проба, която
ви позволява да създадете прозорец че не изглежда за разлика от това,
и в крайна сметка да го превърне в нещо доста подобно.
Така че да се възползват от CS50, обсъдят работно време и повече,
и спокоен, в това, че размера на код, който трябва да напишете
всъщност не е чак толкова много.
Първото предизвикателство е само за да се аклиматизира себе си до известна код сме написали.
>> Всякакви въпроси относно pset3, Shellshock, или по друг начин?
>> АУДИТОРИЯ: Той изглеждаше като преживява с Breakout
че кодът е почти обектно-ориентиран стил,
но мислех, че C е обектно-ориентирана програма.
SPEAKER 1: Един отличен въпрос.
Така че в гледа през код разпределение, кодът
писахме за pset3, за тези, запознати, тя
Изглежда, че това е малко обектно-ориентиран.
Краткият отговор е, че това е така.
Това е сближаване на начина, по който може да направи обектно-ориентиран код, като използвате
език като С, но е все пак в крайна сметка процедурно.
Все още няма методи вътре в променливи, както ще видите.
Но това е напомнящ за това.
И ние ще видим, че черта отново когато стигнем до PHP и JavaScript
към края на семестъра.
Но за сега, мисля за него като намек за това какво е да дойде.
Добър въпрос.
Добре.
Така се сливат вид е как ние леви неща за последен път.
И се сливат вид е готино в смисъл, че е много по-бързо,
най-малко на базата на повърхностни тестове направихме миналата седмица, отколкото, да речем, балон
вид, подбор на сортиране, вмъкване вид.
И това, което е чист прекалено е просто как сбито и чисто
можете да го изразя.
А какво да кажем, че е горна граница на времето за работа на сливане
сортирате?
Да?
>> АУДИТОРИЯ: N влезете п?
>> SPEAKER 1: N влезете N, нали. п влезете п.
И ние ще се върнем към това, че всъщност означава или, когато това идва от,
но това е по-добре от това време на работа
че видяхме за балон подбор и вмъкване вид?
Така н квадрат. N на квадрат е по-голям от този,
и дори и да не е съвсем очевидно, Знам, че дневник н е по-малък от N,
така че ако направя N пъти нещо по-малко от N,
тя ще бъде по-малко от N на квадрат.
Това е малко на интуиция там.
Но ние платихме цената за това.
Тя е по-бързо, но една тема, която започна да се появи миналата седмица беше този компромис.
Имам по-добра производителност време мъдър, но какво
ми трябваше да се харчат за другия ръка, за да се постигне това?
>> АУДИТОРИЯ: Memory.
SPEAKER 1: Кажи го отново?
АУДИТОРИЯ: Memory.
SPEAKER 1: Памет, или пространство като цяло.
И това не е супер очевидно с нашите хора,
но припомни, че нашите доброволци бяха пристъпи напред и засилването
назад, като че ли има един масив тук, и като че ли е
втори масив тук, че те биха могли да използват, защото ние
необходима някъде да се слеят тези хора.
Ние не може просто да ги сменяте на място.
Така се сливат вид ливъридж е по-голямо пространство, което
ние не трябва с други алгоритми
но главата е, че е много по-бързо.
И честно казано, в реалния свят пространство тези days-- RAM, твърд диск Космосът
е сравнително евтин и затова, че е не е непременно нещо лошо.
>> Така че нека хвърлим един бърз поглед, малко по-методично, в това, което сме направили
и защо каза, че е п влезете п.
Така че тук са осем номера, както и осем доброволци, които имахме за последен път.
И първото нещо, което Merge Sort ни каза да направя, е какво?
АУДИТОРИЯ: Разделя се на две.
SPEAKER 1: Кажи го отново?
АУДИТОРИЯ: Разделя се на две.
SPEAKER 1: Разделя се на две, нали.
Това е много напомня на телефонния указател, разделяй
и да завладее по-общо.
Така че ние погледна към лявата половина.
И тогава, след като ние казахме, нещо лявата половина на елементите,
Какво сме следващия кажа?
Подреди лявата половина на ляво половина, което ни позволи да,
След като се разделят на две, съсредоточи върху четири и две.
>> Как да сортирате списък сега, в жълто, с размер на две, като се използва Merge Sort?
Ами тя се разделя на две, и сортиране на лявата половина.
И това е мястото, където нещата имам малко глупаво за кратко.
Как да сортирате списък, който е на размер един, като този номер четири тук?
Това е сортиран.
Вие сте готови.
>> Но тогава как да сортирате списък на размер един, когато това е номер две?
Е, едно и също нещо, но сега какво е трето и ключовата стъпка в Merge Sort?
Вие трябваше да се слеят в ляво половина и дясната половина.
И след като направихме това, ние погледна на четири, разгледахме две.
Решихме наред, Очевидно две идва на първо място,
така ще се постави две в своята място, последвано от четири.
И сега ще трябва да вид назад, и това е нещо характерно
на алгоритъм като Merge Sort, назад в паметта.
Каква е следващата линия на историята?
Какво трябва да се фокусира върху следващия?
В дясната половина на ляво половина, което е шест и осем.
>> Така че нека просто да преминете през този без belaboring точката прекалено много.
Шест и осем, а след това шест е подредени, осем се сортира.
Да ги обедините заедно по този начин, и сега следващата голяма стъпка
е, разбира се, сортирате дясната половина от най-първата стъпка на този алгоритъм.
Така че ние се фокусираме върху една, три, седем, пет.
Ние след това се съсредоточи върху лявата половина.
Лявата половина на тази, дясната половина на че и след това се сливат в едно и три.
Тогава дясната половина, след което се оставя половин на него, след това дясната половина от него.
Това Merge в, и сега какво стъпка остава?
Обединяване на големия лявата половина и големите дясната половина, така че човек отива там,
след две, след това три, след това четири, тогава пет, след шест, след седем, след осем.
>> Така че сега, защо е това в крайна сметка разкрива, особено ако п и логаритми повече
като цяло по-скоро да ви избяга, поне в близкото минало?
Е, забележите, че височината на това нещо.
Имахме осем елемента, и ние това разделени на две, като две от две.
Така че влезте база две от осемте ни дава три.
И повярвай ми, че ако малко неясен за това.
Но влезте база две от осем е три, така че ние сме направили три слоя на сливане.
И когато ние се сляха елементи, колко много елементи
го гледаме на всеки един от тези редове?
Общо N, нали?
Защото, за да се слеят най-горния ред, въпреки че ние го направихме на парче,
ние в крайна сметка докосна всеки брой веднъж.
И във втория ред, за обедините тези списъци с размер два,
ние трябваше да се докосне всеки елемент веднъж.
И след това тук наистина ясно в последния ред
ние трябваше да се докоснат всяка от тези елементи веднъж, но само веднъж,
така че тук се крие, а след това, нашата п дневник п.
>> А сега, само за да направи нещата малко по- по-официално само за миг, ако сте
бяха до сега да анализираме този в един вид на по-високо ниво
и се опитват да решат, и как може да отидеш за изразяване
времето за работа на този алгоритъм само като погледнете в него и да не
чрез използване на скалъпен например?
Е, колко време ще ви кажа стъпка като тази в жълто ще отнеме,
ако N <2 замяна?
Това е голяма O на какво?
Така че аз виждам едно, така че една стъпка, може би две стъпки, защото това е, ако
и след това се върнете, но това е константно време, нали?
Така че ние казахме O (1), и това е как аз ще изразя това.
T, просто да бъде времето за работа.
N е размерът на вложените материали, така че T (п), само един луксозен начин
Споменаването на протичане време на подадената от размера н
ще бъде от порядъка на постоянно време, в Н (1).
>> А иначе, какво ще кажеш за това?
Как бихте се изрази времето за работа на тази жълта линия?
T на какво?
Можете да вид мамят тук и отговори на въпроса ми циклично.
Така че, ако времето за работа в цяло можем да кажем, е T (N).
И сега си вид Punting тук и казва, добре, просто сортирате лявата половина,
и след това се справи дясната половина.
Как може ние символично представлява времето за работа на тази жълта линия?
T на какво?
Какъв е размерът на входа?
N над две.
Защо не мога просто да кажа, че?
И след това е друг T (N / 2) и след това отново, ако се слеят две сортираните половинки,
колко елемента отивам трябва да се докоснат общо?
п.
Така че мога да изразя това, само за да бъде вид фантазия,
като времето за работа като цяло.
Т (п) е само на времето за работа на T (N / 2), плюс T (N / 2), лявата половина и дясната половина,
плюс О (N), който е вероятно N стъпки но може би, ако аз съм с два пръста,
това е два пъти повече стъпки, но това е линейна.
Това е някакъв номер от стъпки това е фактор от N,
така че можем да изразим това, тъй като това.
И това е мястото, където сега ние ще шута към обратно на нашия учебник по математика в гимназията
сме, че повторение в крайна сметка завършва равняващо това, N пъти вляза N,
ако действително направим навън по математика по-официално.
>> Така че това е само на две гледни точки.
Един числено с трудно кодирани представителен пример
с помощта на осем цифри и повече общ поглед към това как сме се озовали там.
Но това, което е наистина интересно тук е, отново, това понятие за колоездене.
Аз не съм с помощта на примки.
Аз съм един вид на определяне нещо по отношение на себе си,
не само с този математическа функция,
но също така и по отношение на тази псевдо-код.
Този псевдо код е рекурсивно в който двама от неговите линии
по същество той казва да отидете Самата използват за решаване на по-малък
проблем с по-малък размер, и след това отново и отново
и отново, докато не го омаловажавам до този така наречен базов модел.
>> Така че нека всъщност направи по-убедителна взема-далеч от това, както следва.
Позволете ми да отида в Gedit и да вземе разгледаме някои от днес изходния код,
по-специално този пример тук.
Sigma 0, което очевидно добавя цифрите един чрез п.
Така че нека да видим какво е запознат и непознати тук.
Първо имаме няколко включва, така че нищо ново там.
Prototype.
Аз съм малко неясен за това след няколко дни,
Но какво да кажем за прототип на функция е?
АУДИТОРИЯ: [недоловим].
SPEAKER 1: Какво е това?
АУДИТОРИЯ: Ние го обявим.
SPEAKER 1: Ние го обявим.
Значи вие преподавате звъня, хей, не действително прилагане на настоящия все пак,
но някъде в този файл, вероятно, ще бъде функция, наречена какво?
Sigma.
И това е само обещание, че тя ще изглежда по този начин.
Това ще отнеме цяло число, както е input-- и мога да бъда по-ясен
и да кажа, вътр н --and това е ще се върне на ПНА,
но на точка и запетайка средства, mm, ще получават около прилагането на този малко по-късно.
Отново звъня е тъпо.
Това е само да знаем какво ти го кажа горе до долу,
така че ние трябва да даде най-малко това намек за това какво е да дойде.
>> Сега нека да разгледаме основната тук.
Нека да превъртите надолу тук и вижте какво главния прави.
Това не е толкова дълго на функция, и в действителност конструкцията тук е запознат.
Декларирам променлива N, и след това I досаждам потребителят отново и отново
за положително число използвайки getInt, и само изход от този цикъл
След като потребителят се е съобразил.
Направете Докато сме се използва за досаждам на потребителя по този начин.
Сега това е интересно.
Декларирам, едно цяло число, наречено "отговор."
Аз го върнатата стойност зададете на функция, наречена "сигма".
Аз не знам какво още, но Спомням си, че се обявява преди малко.
И тогава аз съм преминаване в стойност, която потребителят въведена, N,
и след това да съобщя отговора.
Ами нека да превъртите обратно само за миг.
Нека вървим напред в тази директория, уверете сигма 0, и всъщност стартирате тази програма
и да видим какво ще стане.
Така че, ако отидете напред и да тичам тази програма, ./sigma-0,
и аз въведете в положителна число като две, Sigma,
като гръцкия символ предполага, е само щеше да добавите до всички номера от
нула до два.
Така че 0 плюс 1 плюс 2.
Така че това трябва да се надяваме да ми даде 3.
Това е всичко, което прави.
И по същия начин, ако аз тичам отново и аз я давам на номер три,
това е три плюс две, така че това е 5, плюс един трябва да ми даде 6.
И тогава, ако получа наистина луд и започнете да пишете в по-големи номера,
той трябва да ми даде по-големи и по-големи суми.
Така че това е всичко.
>> Е, какво значи сигма изглежда?
Е, това е доста ясен.
Това е начина, по който може да са приложени това за последните няколко седмици.
"INT" ще бъде типа замяна.
Sigma е името, и това отнема променлива m вместо п.
Ще променим това до върха.
Тогава това е просто проверка на здрав разум.
Ще видим защо в един миг.
Сега аз декларирам друга променлива, Накратко, това се инициализира на нула.
Тогава аз имам този за Контур итерации, очевидно за по-голяма яснота,
от I = 1 на до един = m, което е независимо от потребителя написали в, а след това
нарастване на сумата по този начин.
И след това се върнете сумата.
>> Така няколко въпроса.
One, аз твърдя, в моя коментар, че това избягва риск от безкраен цикъл.
Защо ще преминава в отрицателно число предизвиквайте, потенциално, един безкраен цикъл?
>> Публика: Ти никога няма да достигне m.
>> SPEAKER 1: Никога не достигне m.
Но m е преминал в, така че нека да помисли за един прост пример.
Ако m е преминал в от потребител като отрицателен.
Независимо от основната.
Основна ни предпазва от това също, така че аз съм просто
е наистина анален с сигма също да се уверите,
че входът не може да бъде отрицателна.
Така че, ако m е отрицателна, нещо като отрицателен.
Какво ще се случи?
Е, аз ще се се инициализира с един,
и тогава аз ще бъде по-малко от или равно на М?
>> Изчакайте.
Това беше-- оставим не, нека никс тази история.
Не съм искал на този въпрос, защото рискът, че съм визирайки
няма да се случи, защото аз е винаги ще бъде по-голяма отколкото-- OK,
I прибере този въпрос.
OK.
Нека да се съсредоточи само върху тази част тук.
Защо Декларирам, някои извън линия?
Известие по линия 49 Нямам обявен аз вътре на цикъла,
но 48 онлайн Нямам обявиха някои отвън.
Да.
АУДИТОРИЯ: [недоловим].
SPEAKER 1: Разбира се.
Така че на първо място и преди всичко аз със сигурност не го правят искат да декларира и инициализира сума
до нула вътрешността на контур на всяка итерация,
тъй като това очевидно ще победят Цел на сумиране на номерата.
Бих продължава да се променя стойността обратно до нула.
И също така, каква е друг, по-тайнствена причина за това същото решение дизайн?
Да.
>> АУДИТОРИЯ: [недоловим].
SPEAKER 1: Точно така.
Искам да го достъп извън на цикъла прекалено върху това, което линия?
На 53.
И въз основа на нашето правило на палеца от преди няколко лекции,
променливи са обхванати, наистина, към фигурни скоби, които ги обхващат.
Така че, ако не се декларира сума вътре от тези външните фигурни скоби,
Не мога да го използвам в съответствие 53.
Казано по друг начин, ако декларираната сума в тук, или дори в рамките на
За контур, аз не можех да го отворите в 53.
Променливата ефективно ще бъдат унищожени.
Така няколко причини там.
Но сега нека се върнем и да видим какво ще стане.
Така че сигма получава обади.
Тя добавя, до 1 плюс 2, или 1 плюс 2 плюс 3, и след това се връща на стойността,
го съхранява в отговор, и ФОРМАТ тук Ето защо аз се виждам на екрана.
Така че това е, което ние ще се обадя на един повтарящ се подход, при повторение само
означава използване на една линия.
A За контур, а Докато контур, а Do Докато контур, просто правиш нещо отново
и отново и отново.
>> Но сигма е вид чист функция в че мога да го приложи по различен начин.
Какво ще кажете за това, което само за да бъде нещо страхотно,
нека наистина да се отървете на много отвличане на вниманието
защото тази функция всъщност е доста прост.
Нека да омаловажавам това надолу просто на своите четири основни линии
и да се отървете от всички коментари и фигурни скоби.
Това е вид на ум-разпенващ алтернативно изпълнение.
Добре, може би не е умопомрачаващо, но това е нещо по-секси, добре,
да погледнем в това, така много по-сбито.
Със само четири реда код, За първи път имаме тази проверка здрав разум.
Ако m е по-малко от или равно на нула, сигма няма смисъл.
Той е трябвало само да бъде в този случай за положителни числа,
така че аз съм просто ще върнете нула произволно
така че да можем поне да има някои така наречения базов модел.
>> Но тук е красотата.
Същността на тази идея, като се добавят номера от 1 до N, или м в този случай,
може да се направи по вид на преминаване отмятат.
Е, каква е сумата от 1 до m?
Ами, знаете ли какво?
Това е същото като сумата от т плюс сумата от 1 до m минус 1.
Ами знаеш ли какво?
Какво е сигма на m минус 1?
Е, ако сте вид следват тази Логично, това е същото като m минус 1
плюс Sigma М минус 2.
Така че можете да вид просто-- това е като, ако сте просто
се опитва да дразни приятел и те да ви задам един въпрос,
някак си отговори с въпрос, можете да вид запази прехвърляха отмятат.
Но това, което е ключ е, че ако продължаваш вземане на въпрос по-малък и по-малък
и по-малък, вие сте Не питам какво е сигма
на N, което е сигма на н, какъв е сигма на п?
Питате какво е сигма на N, което е сигма
п минус 1, какво е сигма на п минус 2?
В крайна сметка вашия въпрос ще стане това?
Какво е сигма на една или нула, някои много малка стойност,
и веднага след като си се, че си приятел,
вие няма да питам същия въпрос отново,
вие просто ще кажа, о, това е нула.
Ние сме готови да играете този вид глупаво циклична игра.
>> Така рекурсия е акт по програмиране на функция, наричаща себе си.
Тази програма, когато са съставени и тичам, е ще се държат точно по същия начин,
но това, което е ключ е, че вътре на функция, наречена Sigma,
има една линия на код, където ние сме се обажда,
което нормално би било лошо.
Например, какво ще стане ако аз първи компилиран това, така че се уверете sigma--
направи сигма 1 ./sigma-1.
Положително число, моля, 50 1275.
Така че това, което функцията изглежда да, въз основа на един тест, вярна.
Но какво, ако получа малко опасно и изтриване на така наречената база случая,
и просто да кажа, ами аз съм просто направи това по-сложно, отколкото е то.
Нека просто да се изчисли сигма , като m и след това прибавяне
в сигма на m минус едно?
Е, какво ще се случи тук?
Да намалите.
Нека да компилирате програмата, го спаси, компилирате програмата,
и след това е готов ./sigma-1 мащабиране в, въведете положително число, моля, 50.
Колко от вас са готови до Фес до виждайки, че?
>> OK.
Така че това може да се случи редица причини,
и честно казано тази седмица сме за да ви даде повече от тях.
Но в този случай, опитайте да се разсъждава назад
какво може да се случи тук?
Сегментация вина, казахме последно време, се отнася до сегмент на паметта.
Нещо лошо се е случило.
Но това, което беше механично, че отиде проваля
тук, защото на моето отстраняване на тази т.нар базов модел,
когато се върнах трудно кодирани стойност?
Какво мислиш, че се е объркало?
Да.
>> АУДИТОРИЯ: [недоловим].
SPEAKER 1: Ah.
Добър въпрос.
Така размерът на броя че бях обобщавайки
имам толкова голям, че тя е превишила размера на пространството памет.
Добра идея, но не фундаментално ще доведе до катастрофа.
Това може да доведе до цяло число преливник, където битовете просто обърнете
и тогава ние бъркаме наистина голям номер за като отрицателна стойност,
но себе си не ще доведе до катастрофа.
Защото в края на ден пад все още е 32 бита.
Вие не започваш да се случайно открадне 33тата малко.
Но една добра мисъл.
Да.
>> АУДИТОРИЯ: [недоловим].
SPEAKER 1: Методът никога не спира да работи,
и наистина отново нарича себе си и отново и отново и отново
и отново, и нито един от тези функции всякога
довърши, защото тяхната единствена линия на код themself призовава отново и отново
и отново.
И това, което е наистина се случва тук и сега
може да се направи този вид картинно.
Нека да преминем към по- снимка само за момент.
Това е снимка, че в крайна сметка ще плът
по-подробно за това какво се случва вътре в паметта на компютъра си.
И се оказва, че на дъното на тази снимка
е нещо, наречено стека.
Това е парче памет, парче от RAM,
това е просто използва по всяко време функция се нарича.
Всеки ли време, програмист, наричаме функция,
операционната система, като Mac OS, Windows или Linux,
грабва куп байта, може би няколко килобайта, може би няколко мегабайта
на паметта, да ги раздава за вас, а след това ви позволява
стартирате функцията си, използвайки каквото и променливи, което трябва.
И ако тогава се обади друг функция и друга функция,
можете да получите друго парче на паметта и друго парче от памет.
>> И наистина, ако тези зелени тави от Annenberg декларирате, че паметта,
ето какво се случва на първия време ти се обадя функция сигма.
Това е като да сложиш на поднос като този върху това, което е първоначално празен стак.
Но след това, ако тази тава нарича себе си, така да се каже,
призовава друга инстанция на сигма, че е
като иска от операционната система, ох, трябва малко повече памет,
Дай ми това.
И тогава той се струпват на върха.
Но това, което е ключът тук е, че първата тава е все още там,
защото той позоваване на тази втора тава.
Сега Междувременно сигма наричат ​​сигма, това е все едно да питаме за повече памет.
Взима се струпват тук.
сигма сигма наричаме, това е друга тава, която получава прибрана тук.
И ако продължаваш да правиш това, в крайна сметка, вид на картата този визуален
към тази диаграма, какво ще се се случи с топчето тави?
Това се случва, да надвиши размера на паметта на компютъра ви има.
И веднага след като тази зелена тава надвишава хоризонталната линия
горе стак и над тази дума грамада които ще се върнем в бъдещето,
че е нещо лошо.
Купчината е различен сегмент на памет,
и ако искаш да те тави купчина и купчина,
ти започваш да надвишава свой собствен сегмент от паметта,
и програма е наистина ще се разбие.
>> Сега като настрана, тази идея на рекурсия, следователно,
може ясно да доведе до проблеми, но това не е непременно нещо лошо.
Тъй като разгледа, след всички, how-- и може би
това отнема известно привикване да --how елегантен или колко е лесно
че изпълнението на сигма беше.
И ние няма да използвате рекурсия чак толкова много в CS50,
но в CS51, и наистина всеки клас където ви манипулират структури от данни
като дървета, или семейни дървета, че има някаква йерархия,
това е супер, супер полезно.
Сега, като настрана, така че да можете като се стремят компютърни учени
са запознати с някои от на Google вътре вицове, ако отидете на Google
и погледнете нагоре, което е определение на, да речем, рекурсия, влиза.
Аха.
Като настрана, аз спря няколко.
Това е като 10 минути отлагането тази сутрин.
Ако вие също Google "накриво" известие като наклоните главата си slightly--
и след това е може би най-жестокото от всички
тъй като някой, прекарал като ден им прилагане на настоящия
няколко години ago-- хайде.
О, Чакай, че е бъг.
>> Така че работи на един от най- най-големите сайтове в света
са тези глупави малки великденски яйца.
Те вероятно консумират нетривиални брой редове код
просто така, че ние можем да имаме малки забавни неща.
Но поне сега ще получите някои от тези вътре шеги.
>> Сега нека да разгледаме някои от най- бяла лежи ние сме били казвам напоследък,
и да започне да се бели обратно някои слоеве технически
така че да можете наистина да разберем какво става на
и можете да разберете някои от заплахите,
като Shellshock, че вече са започнали да се превърне
на преден план на всеки внимание, поне в медиите.
Така че тук е много проста функция който се връща нищо, за невалидни.
Името му е суап.
Това отнема в две променливи и го връща нищо.
Счита в а и б.
Така бързо демонстрация.
Донесохме тези нагоре.
Ние може и да отнеме малко пробие тук само за миг
и да има нещо за пиене.
Ако някой не би имал нищо против присъединяването ми до тук само за миг.
Какво ще кажете за вас в кестеняво риза?
Хайде нагоре.
Само една днес.
Благодаря ви, все пак.
Добре, и ние имаме идва, който тук?
Как ти е името?
>> SPEAKER 4: Лора.
>> SPEAKER 1: Лора.
Хайде нагоре.
Така Лора, много проста предизвикателство днес.
Приятно ми е да се срещне йо.
Добре.
Така че ние имаме малко мляко тук и имаме някои портокалов сок тук
и някои чаши, които ние назаем от Annenberg днес.
>> SPEAKER 4: назаем.
SPEAKER 1: И ще вървим напред и ще ви даде половин чаша от това.
Добре.
И ние ще ви дам половината чаша мляко.
О, и просто така, че можете да Спомням си какво беше като,
Спомних си, за да донесе това и днес.
Добре.
Ако не би имал нищо против, нека да видим, ние може да ги постави над вашите собствени очила
ако искаш.
Това ще бъде в света от очите на Лора.
Добре.
Така че вашата цел, като се има предвид две чаши течност тук, мляко и портокалов сок,
се разменят двата съдържанието, така че портокалов сок отива в чашата на млякото
и отива в млякото чашата портокалов сок.
>> SPEAKER 4: Обичате ли да получа още една чаша?
SPEAKER 1: Аз съм толкова се радвам, че попита, макар че би било много по-добре кадри
ако не беше поискал.
Но да, ние можем да Ви предложим една трета чаша, че е празна, разбира се.
Добре.
Така че сменяте съдържанието там.
Много хубаво.
Много добре.
Правиш това забележително внимателно.
И стъпка три.
Добре.
Отлично.
A голям кръг от аплодисменти би било добре за Лора.
Добре.
Имаме малък прощален подарък за вас, но нека ми отнеме това.
Благодаря ви толкова много.
Така че един прост пример, все пак, да докаже, че ако го направите
искате да сменяте съдържанието на два контейнера,
или нека ги наречем променливи, имате нужда от временно складиране
да организира един от съдържанието на така че всъщност можете да направите на суапа.
Така че наистина, това изходния код тук в C е представител на точно това.
Ако портокалов сок е и млякото е б, и ние искахме да сменяте два,
бихте могли да опитате нещо творческо чрез изливане една в друга,
но това вероятно няма да края особено добре.
И така, ние използваме една трета чаша, повикване тя TMP, T-M-P от конвенция,
и пуснати на съдържанието на ОВ в това, тогава сменяте една чаша,
след това пуснати на ОВ в оригиналната чаша, като по този начин
постигане, точно както Лора направи, суапа.
>> Така че нека да направим точно това.
Нека да вървим напред и да се отвори до един пример, който е
всъщност се нарича "не суап ", защото това не е
като просто направи колкото може би си мислите.
Така че в тази програма, да забележите, че Аз съм с stdio.h, нашият стар приятел.
Имам прототип за суап там, които
означава прилагането му е вероятно по-долу,
и нека видим какво тази основна програма ще направите за мен.
За първи път декларира INT х получава една и INT г. получава две.
Така че мисля, че на тези, като ОВ и мляко, съответно.
И тогава аз просто имат ФОРМАТ казва х е това
и Y е това, само за да мога да визуално да видим какво става.
Тогава съм ФОРМАТ твърдейки че аз съм смяна на две,
и тогава аз отпечатате твърдят, че те са разменени,
и аз отново разпечатате х и у.
Така че тук надолу в суап е точно това, което Лора направи,
и точно това, което видяхме на екрана преди малко.
>> Така че нека да вървим напред и да бъде крайно разочарован.
Не се суап, и тичам не суап, мащабиране на изхода тук.
Въведете х е 1, Y е 2, размяна разменят.
X е все още 1, и Y е все още 2.
Така че, въпреки че, честно казано, това изглежда точно харесва, макар и по-технически,
какво Laura направил, не изглежда да работи.
Така че, защо е това?
Е, оказва се, че когато пишем програма като тази
, която има основна, подчертано тук, и после още една функция, като суап,
подчертани тук, който го нарича, светът
изглежда малко нещо като тези тави преди малко.
Когато основната първо получава нарича, това е като да питаш операционна система
за малко памет за всеки местен променливи, като X и Y, че основното е,
и те в крайна сметка точно там.
Но ако основните разговори разменят, и основната минава да сменяте два аргумента, а и б,
портокалов сок и мляко, не е като да подавайки портокалов сок и млякото
Лора.
Какъв компютър прави, е, че преминава копия от портокалов сок
и копия на млякото да Laura, така че какво е в крайна сметка вътре в тази тава
е една стойност и две, или ОВ и мляко, а копия от него,
така че в тази точка в историята, има
е ОВ и мляко във всяка от тези тави.
Има едно и две във всяка от тези тави,
и функцията за суап се наистина работи.
Той ги е смяна вътре на втория горната тава
но че смяна не оказва влияние.
И въз основа на само някои основен принцип сме
говорихме и преди, и наистина Само преди няколко минути, какво
може да обясни защо се променя А и В в на размяна
няма ефект на X и Y, макар Минах х и у на функцията суап.
Каква е ключовата дума тук, че може опростенчески обясни?
Мисля, че го чух тук?
АУДИТОРИЯ: Завръщането.
SPEAKER 1: замяна?
Не се върне.
Нека да отидем с един друг.
Какво е това?
>> АУДИТОРИЯ: [недоловим].
>> SPEAKER 1: ОК, така return-- можехме направи завръщане на работа в историята,
но там е още по-просто обяснение.
АУДИТОРИЯ: Приложно поле.
SPEAKER 1: Обхват.
Ще взема обхват.
Така обхват, не забравяйте, когато нашата х и у декларирани.
Те са обявени за вътре на главния чак тук.
А и Б, междувременно, са ефективно обявена
вътре на суап, не съвсем в фигурните скоби, но все още
в широката зона на суап.
И така, наистина, а и б съществува само в рамките на тази тава
от Аненберг, този второ парче код.
Така че ние сме наистина промяна на копието, но това не е наистина всичко, което е полезно.
>> Така че нека да разгледаме най- това е малко по-ниско ниво.
Отивам да се върне в Директория източник
и аз отивам към първия увеличите тук, а просто
, за да потвърдите, че аз съм в тази голяма терминален прозорец,
Програмата все още се държи по този начин.
Да предположим сега, че това не е умишлено.
Ясно е, че искам да суап работа, така че тя се чувства като буболечка.
Сега може да започне добавяне на много ФОРМАТ е на моя код,
отпечатване х тук, у над Тук, тук, б тук.
Но честно казано, това е може би това, което сте били прави в продължение на няколко седмици
сега, в работно време и у дома, когато се работи
на psets опитват да намерят някои бъгове.
Но вие ще видите, ако вече не сте, този проблем определя три ви запознава
на команда, наречена GDB, където GDB, GNU дебъгер,
Самата има цял куп функции, които могат действително
нека разберем ситуации по този начин, но по-интригуващи,
решаване на проблеми и да намерят грешки.
Така че аз отивам да правя това.
Вместо ./noswap, аз вместо съм ще избяга GDB ./noswap.
С други думи, аз отивам да тичам ми програма не в Bash, нашият нов приятел
днес.
Отивам да тече ми програма noswap вътре
на тази друга програма, наречена GDB, което е корекция на грешки, която
е програма, която е предназначена да помогне на вие хората намиране и премахване на бъгове.
Така че, ако се удари Пусни тук, има отвратителен размер на текста
че наистина никога не трябва да се чете.
Това е по същество една разсейване от командния ред, който
Отивам да се удари Control-L да се изправи на върха там.
Това е ред GDB.
Ако искате да стартирате тази програма сега, тъй като това малко мамят лист на днешния
слайд показва, Run е първият команди, които ние за цел да въведе.
И аз съм просто ще да въведете тичам тук вътре в GDB,
и наистина се завтече моята програма.
Сега има някои допълнителни изходи на екран като този,
но това е GDB просто е анален и ни казва какво става.
Вие наистина не трябва да се притеснявате за тези детайли точно сега.
Но това, което е наистина страхотно за GDB, ако направя това again--
Control-L изчиства screen-- ме пусна напред и тип "пробие основната," по този начин,
когато ударих Enter, за определяне какво е нарича точка почивка в noswap.c,
линия 16, което е мястото, където GDB измисли моята програма всъщност
е, моята функция в действителност.
Това ще игнорира за сега но това е адреса
в памет специално на тази функция.
Така че сега, когато пиша тичам, Забележете какво е готино тук.
Моята програма разбива в съответствие I каза GDB за пауза при изпълнение.
Така че аз не трябва да се променят кода си, добавите някои ФОРМАТ, той прекомпилирате, повторение
това, да се промени, добави някои ФОРМАТ е, го спаси, да го компилирате, пуснете го.
Мога само да минеш през моята програма стъпка по стъпка по стъпка в човешката скорост,
не на Intel-вътре вид на скорост.
>> Така че сега забележите тази линия се появява тук, и ако се върна
към програмата ми в Gedit, се отбележи, че това е действително
най-първата линия на код.
Има линия 16 в Gedit.
Има линия 16 в GDB, и дори че този черен и бял интерфейс
не е почти като потребител приятелски, това означава,
тази линия 16 не е била изпълнена все още, но това е на път да бъде.
Така че наистина, ако напишете печат X, не ФОРМАТ, просто печат X,
Получа някои фалшив стойност там на нула, защото X все още не е инициализиран.
Така че аз отивам да въведете следващия, или, ако сте Искам да се фантазия, просто N за следващия.
Но когато пиша следващия влиза, сега забележите, че се движи по линията 17.
Така че, логично, ако съм изпълнен линия 16 и сега напишете печат X,
какво трябва да видим?
One.
>> И сега това е наистина объркващо.
$две Е само един луксозен начин на това, ако сте Искам да се позове на тази стойност по-късно,
може да се каже "долар подпише две."
Това е като препратка назад.
Но за сега, просто го игнорира.
Какво е интересно е това, което е относно правото на знака за равенство.
И сега, ако пиша следващия път и печат Y, аз трябва да видите 2.
Също така мога да се отпечата X отново, и честно казано,
ако аз съм се малко объркан, че да къде съм, не мога да въведете списък за списък
и просто да видя някакъв контекст около точката, аз съм всъщност в.
И сега мога да напишете На следващо място, и там х е 1.
Сега пиша следващия.
О, Y е 2.
И отново, това е объркващо, защото изход GDB е
се смесват с моя собствена продукция.
Но ако продължаваш да се има предвид, от поглеждайки назад и напред в кода си,
или да го регламентираща страна от страна може би, вие ще
се види, че наистина съм просто засилване чрез моята програма.
>> Забележете какво се случва след това, буквално.
Тук е ред 22.
Позволете ми да отида над него, като по този начин се движат по до 23, и ако аз отпечатате х сега, все едно.
И ако аз сега отпечатате г., все още е един.
Така че това не е полезно упражнение.
Така че нека да ремонтирам тази.
Позволете ми да се върна до отгоре и тип се кандидатира отново.
И тя казва програмата че е се дебъгва
е започнала вече, започна от самото начало.
Да, нека да го направим отново.
И този път да го направим следващия, следващото, следващото, следващото, следващото,
но сега нещата стават интересни.
Сега искам да се оттегли в суап, така че аз не напишете следващата.
I тип стъпка, а сега го забележите ми скочи до noswap.c ред 33.
Ако се върна към Gedit, какво е ред 33?
Това е първата действително ред код във вътрешността на суап.
Което е хубаво, защото сега мога да вид мушкам наоколо и да получите любопитна
за това какво се случва наистина там.
Позволете ми да отпечатате ПТУ.
Уау.
Защо ПТУ има някои луд, фалшива стойност боклук?
АУДИТОРИЯ: Това не е инициализиран.
SPEAKER 1: Той не е инициализиран.
И наистина, когато стартирате програмата, Вие сте даде цял куп памет
от операционната система, но не са инициализира всички стойности,
така че каквото и бита си виждате тук, въпреки че е
този луд голям отрицателен номер, просто означава,
че това са останките от някои предишни използване на тази RAM,
въпреки че не съм самият той все още е необходимо.
Така че сега аз отивам да вървим напред и тип На следващо място, и ако сега пиша печат ПТУ,
какво трябва да видим?
Каквато и да е стойност на А е, а е първият аргумент, просто
като X е първият нещо, което се предава в,
така че и X трябва да бъдат еднакви, така отпечатате ПТУ трябва да ми отпечата един.
>> Така че това, което ще видите в проблем набор три е урок на видове на GDB,
но осъзнавам, че това е началото на поглед към един инструмент, който действително ще
да ви помогне да решаване на проблеми толкова по-ефективно.
Това, което ние сме в крайна сметка ще направи в сряда
се започне да се бели обратно няколко слоя и премахване на някои помощни колела.
Това нещо, наречено низ сме използвали за известно време,
отиваме да се вземат бавно, че далеч от вас и започнем да говорим за
нещо по-езотерично известен като знак *
но ние ще направим това хубаво и внимателно в началото, въпреки че указатели,
тъй като те се наричат, може да се направят някои много лоши неща, ако се злоупотребява,
, като погледнете в малко claymation от нашият приятел Ник Parlante от Stanford
Университет, професор по компютърни науката, които, взети заедно този преглед
за това какво е да дойде тази сряда.
>> [VIDEO PLAYBACK]
Хей, Бинки.
Събуди се.
Това е време, за показалка забавно.
>> Какво е това?
Научете повече за указатели?
О, лакомство!
[END възпроизвеждане на видео]
SPEAKER 1: Това ви очаква в сряда.
Ще се видим тогава.
[VIDEO PLAYBACK]
-А Сега, Deep Thoughts, от Дейвън Farnham.
>> Защо са ни учи C?
Защо не A +?
>> [СМЯХ]
>> [END възпроизвеждане на видео]