>> [МУЗЫКА ИГРАЕТ]
>> СПИКЕР 1: Хорошо, это CS50, и это начало четвертой неделе,
и как вы, возможно, слышали или читать, мир был конец.
Идущий все вокруг интернета была знаний и осведомленности
за ошибки в программу, Язык программирования называется Bash.
Это было чудесно фирменных как Shellshock, или Баш двери,
но такие статьи, как это не были редкостью.
И в самом деле, многие из них приносят воспоминания о Heartbleed,
которые вы, возможно, заметили в нажмите назад весной этого года, которая
было так же довольно драматично.
Теперь из тех из вас, здесь сегодня, как многие из вас,
даже если вы не понимаете, что это все о, слышали о Shellshock?
Ладно, и как многие из вас есть компьютеры, которые уязвимы?
ОК, не должно быть гораздо, гораздо больше рук прямо сейчас, по причинам, мы увидим.
>> Давайте взглянем на то, что что происходит в средствах массовой информации
а затем объяснить его немного здесь для нас технически.
>> СПИКЕР 2: Эксперты по безопасности имеют предупредил, что серьезный недостаток мог
около повлиять сотни миллионы пользователей в мире веб.
Так что же такое ошибка, было название Shellshock, и для чего это нужно?
Ну, Shellshock также известен как Bash ошибка, программное обеспечение она использует.
Хакеры используют вирус для сканирования уязвимы системы, работающие Linux и Unix
операционных систем, а затем заразить их.
Bash является оболочкой командной строки.
Это позволяет команд вопрос пользователям запустить программы и функций в рамках программного обеспечения
набрав в тексте.
Это, как правило, используется программистами, и не должны быть открыты для более широкого мира,
хотя Shellshock изменяет, что.
>> Ну, worringly, некоторые аналитики предупредить это может быть большая угроза,
потому Shellshock позволяет полное контроль зараженной машины,
в то время как Heartbleed допускается только хакеры, чтобы шпионить за компьютерами.
Это настолько серьезно, что это был оценен в 10 из 10
для тяжести Национальным Уязвимость База данных.
2/3 из всех веб-серверов, по крайней риск, в том числе некоторых компьютерах Mac.
Ну, убедитесь, что вы залатать свои системы сейчас.
Любой хостинг веб-сайт работает пострадавшие операционные системы
следует принять меры как можно скорее.
Любой, кто может позволить себе это должно выглядеть к их применению мониторинга и веб-
брандмауэры, чтобы высматривать любых атак.
СПИКЕР 3: Худшая вещь что может случиться,
что кто бы написать код, который будет автоматически идти и сканирование
Интернет и повлияет все эти компьютеры.
И как только они делают, что, ну, самое худшее, что они могли сделать
просто удалить все, или закрыть сайты вниз.
Таким образом, мы могли видеть повреждения с этой точки зрения,
где мы должны были бы злоумышленникам которые просто решили вызвать хаос
путем привлечения системы вниз или удаление файлы, и тому подобные вещи.
СПИКЕР 2: Некоторые говорят, что это один из самых трудно измерить
ошибки в годы, и это может занять несколько недель или даже
месяцев, чтобы определить его конечное воздействие.
>> СПИКЕР 1: Так все это правда, но самое смешное, почти все
из образов вы только что видели, для возможно клавиатуре исключением,
не имеет ничего общего с ошибка вообще.
Серверы и провода и так далее, она как бы косвенное отношение,
но в основном это на самом деле довольно знакомы, что происходит здесь.
На самом деле, меня отпустили в наша CS50 прибор.
Позвольте мне идти вперед и максимально окно терминала здесь.
И вы, ребята уже используют это, или встроенного их версии,
в Gedit для того, чтобы писать программы, вводить команды, и так далее,
и это на самом деле, и имеет был в течение многих недель, Bash B-A-S-H.
Это Bourne-Again Shell, , который является просто причудливый способ сказать,
это программа, которая имеет мигать быстро, эффективно,
что сидит там ждет для ввода для Вас.
И это команда линейный интерфейс, через который
вы, ребята, были выполнения команд и в конечном счете, компиляции и затем работает
программы.
>> Но Bash также программирование язык в следующем смысле.
Вы знаете, что есть команды, как кд и Ls, а также лязг и другие,
но вы можете определить свои собственные команды путем внедрения их в Bash.
Теперь мы не собираемся вдаваться в подробности
как колотить язык программирования, но знаем, например, что на данный момент,
нет команды называется "привет".
Таким образом, можно найти в один из этих пакетов.
Это не установлен на моем компьютере.
Попросите администратора.
Но если я хочу, чтобы программа называется "привет" в Bash или в моем приглашении,
Я могу на самом деле использовать синтаксис вот совсем как C. Это не совсем то же самое,
но это выглядит очень похоже на Функция, хотя отсутствуют некоторые детали.
Ничто, кажется, произойдет, но теперь, если я печатаю "привет",
Вы можете на самом деле писать Программа, не в C, не в Java,
не в другом программирования язык, но и в самой Bash.
>> Теперь Ключевым моментом здесь является, что я написал назвать я хотел дать этот новый команду,
и скобки также Символично это является функцией.
Как в стороне, вы также можете сделать удовольствие вещи, и на самом деле, даже на Mac OS,
это программа под названием Terminal.
Он поставляется встроенная в ничьи компьютер, который имеет Mac в этой комнате,
и вы можете сделать то же самое в Mac ОС, но вы можете пойти более за что.
И это немного по касательной, но это забавно.
Мне напомнили сегодня утром, когда думая, что это через,
маленькой игре я играл с одним из бывших TFs CS50 в
причем в любое время он будет ходить от его клавиатура с его экрана разблокирован,
Я исполняю бы команду как это-- "поздороваться".
И теперь в любое время он вернулся к своему Клавиатура после того как я очистил экран
и он садился, попробуйте сделать некоторую работу,
список содержимого его directory--
>> [АУДИО ВОСПРОИЗВЕДЕНИЕ]
>> -Здравствуйте.
Здравствуйте.
>> СПИКЕР 1: Так, справедливости ради, это не было на самом деле "привет".
Это, как правило, было нечто больше похоже на that--
[АУДИО ВОСПРОИЗВЕДЕНИЕ]
-Beep.
СПИКЕР 1: --that я would-- так что его компьютер будет
изругаю любое время он фактически сел за клавиатуру.
И очень быстро он понял, не оставлять его экран разблокирован.
Но это говорит о то глупого веселья, что вам
может иметь что-то вроде Bash.
Но это немного больше серьезно, чтобы быть уверенным, чем это.
И в самом деле, это один из большинство опасные и длительные ошибки
что действительно попал в мир во всем мире.
Эта ошибка была вокруг около 20 лет,
и вы будете поражены в просто момент по своей относительной простоте.
>> Так что это представитель командовать, что если вас
владеть Mac, буквально прямо сейчас когда у вас есть крышка открыта,
Вы можете попробовать ввести в том, что Программа называется Терминал.
Терминал находится под Приложения Utilities--
на этот раз, пользователи Windows, не должны беспокоиться о данном threat--
но те из вас с Macs можете ввести это в окно, как я сделаю здесь,
и если вы введите что в эту программу
называется Терминал, как я сделаю сейчас, если вы видите слово "уязвимыми"
Ваш компьютер уязвимыми для эксплуатации.
>> Теперь что же это на самом деле означает?
И это правда, некоторые довольно сумасшедшим синтаксис,
но давайте хотя бы вытянуть некоторые интересные аспекты.
Таким образом, есть некоторые синтаксис, который выглядит немного знакомы, по крайней мере, от C
и программирования в целом.
Я вижу некоторые скобки, запятой, фигурные скобки, и такие,
но оказывается, что это глупо здесь в желтый
, по существу, является функцией что ничего не делает.
Средства толстой кишки ничего не делать, а Точка с запятой означает остановить, ничего не делая.
Так внутри них Фигурные скобки, тот факт,
что у меня есть равна подписать влево, это
является по существу создавая Команда, или переменная,
называется х, и присваиваем его что желтый кусок кода там.
Это может быть что-то вроде "эхо привет "или" сказать сигнал "или что-то
сродни тому, что.
Но обратите внимание, если ваши глаза бродить дальше вправо,
есть больше к этой линии, чем просто конец этой запятой.
"Эхо уязвимы", а затем кроме того, есть еще больше.
Другой запятой, Баш -c :.
>> Так короче говоря, эта строка кода является
достаточно для убедительных Компьютер это
уязвимы для делать что-то что вы от него хотите,
потому что есть ошибка в Bash которой хотя Bash должен был остановить
Чтение строк из командной права там после желтым текстом,
для 20-плюс-летнего ошибки, Bash фактически читал
за пределами этого запятой и довольно много делает то, что он сказал.
>> Так в чем же подтекст того, что в конечном итоге?
Я просто сказал, что "эхо привет" или "эхо уязвимы,"
но то, что если вы сделали нечто на самом деле злой, как РМ-РФ *,
которые вы не могли бы когда-либо ввели раньше,
и, честно говоря, вы, вероятно, не должны слишком рано,
потому что вы можете сделать Большой ущерб с ним.
Почему?
гт делает что, конечно?
Удаляет.
* Означает, что?
Все.
Так что это так называемый дикая карта, так это означает,
удалить все, что в текущий каталог.
-r происходит с виду рекурсивный, что означает, если то, что вы удаляете
является каталогом, и внутри есть является другие файлы и другие каталоги,
рекурсивно погрузиться в там и удалить все, что.
И -f является худшим из всех.
Каждый знает, что -f означает здесь?
Force.
Так заставить средства, даже если это плохая идея,
сделать это, не спрашивая меня для дальнейшего подтверждения.
Итак, вы знаете, мы смеемся над это, но, честно говоря, я, вероятно,
введите это несколько раз в день, так как в действительности
это самый быстрый способ, чтобы удалить целую кучу вещей.
Но даже я сделал некоторые повреждения.
>> Но если бы вы были, чтобы обмануть компьютер в определении некоторое глупое переменную
или функция называется х, но тогда обманывая компьютер в выполнении
за пределы, что Функция, за этой точкой с запятой,
Вы действительно может обмануть компьютер в выполнении то как РМ-РФ
или команда E-mail или команда Копировать.
Все, что буквально можно сделать с компьютер, будь то удаление файлов,
создание файлов, спам кого, удаленно атаковать некоторые сервера,
если вы можете выразить это с командой, вы
может обмануть компьютер в это делать.
>> Теперь то, что пример как вы могли бы это сделать?
Ну, есть много компьютеров на интернет проточной Bash.
Все пользователи нам Mac среди них.
Много серверов Linux являются одними им также, и серверы Unix.
Окна снова получает относительно крючка
если вы не установлен специальное программное обеспечение.
Сейчас много серверов, для Экземпляр, работают веб-серверы,
а на самом деле Linux является, пожалуй, самая популярная операционная система
для работы на компьютерах в Интернете которые обслуживанию веб-страниц.
Теперь, как мы увидим позже в семестр, когда
Вы отправляете запрос от Ваш browser-- Chrome,
Internet Explorer, whatever-- на удаленный сервер,
получается, что даже при том, Вы только что ввели www.example.com,
ваш браузер посылает сообщение это немного более тайной, как это.
>> Но обратите внимание, немного нечто странное.
Первые две строки Я никогда не видел прежде,
но они не выглядят особенно угрожающим.
Но обратите внимание, что я украл для третьей линии здесь.
Если плохой парень были отправить сообщение как это от своего компьютера
к уязвимой Mac или уязвимы сервер Linux,
Самое смешное, что Bash, что просто немного командной строки,
вездесущ и часто привык к существу выполнить
содержание сообщение, что он получает.
И по этой логике, можно обмануть веб-сервер, поэтому,
отправив то как User-Agent, который, как правило,
Предполагается сказать Имя Вашего браузера.
User-Agent Chrome, User-Agent Интернет Проводник, User-Agent Firefox, это
просто вашего браузера способ идентификации себя.
Но если плохой парень очень умно говорит, мм-мм, я
не собираюсь говорить вам, что мой браузер,
Я вместо пошлю тебе это загадочный вид вещь с РМ-РФ
* В нем, вы можете буквально обмануть уязвимыми веб-сервер в Интернете
в выполнении именно, что в есть для удаления всех файлов.
И, честно говоря, это не даже самое худшее.
Вы можете делать что угодно.
Вы можете начать распространяться отказ в обслуживании нападения
если вы отправили это сообщение целые гроздья веб-серверов
а затем были они все происходят, для Экземпляр, на серверах Harvard.edu,
и вы можете сортировать Банг черт из них
сетевым трафиком, который был в противном случае вызывается этого плохого парня.
>> Так, короче говоря, почти все в этой комнате, кто владеет Mac
уязвим для этого.
Луч надежды в том, что, если вы не работает веб-сервер на вашем ноутбуке,
и если вы не на самом деле настроен это чтобы что-то вроде SSH в него,
вы на самом деле безопасно.
Это не уязвимы, но нет никакого один, пытаясь попасть в вашем ноутбуке,
так что вы можете рода уверены.
Однако Apple скоро быть обновление починку для этого.
Мир Linux уже выпустила ряд исправлений для Fedora и Ubuntu
и другие версии Linux, и в самом деле если вы запустите обновление 50 в приборе,
даже, что тоже будет обновляются и корректируются.
Но это тоже не имеет действительно были уязвимы,
потому что, если ты не имеешь возился с машиной
и сделал свой ноутбук публично доступны в Интернете, который не
по умолчанию, вы, на самом деле был прекрасен, потому что
из межсетевого экрана и других методов.
>> Но это крайний пример ошибки что мы жили буквально за 20
лет, и кто знает, если кто все это время знал об этом?
И в самом деле, это один из фундаментальные проблемы
что мы увидим позже в семестр о безопасности,
является то, что, как и в реальном мире, хорошие парни находятся в невыгодном положении.
Чтобы держать плохих парней, мы должны убедиться, что каждый дверь заперта,
что каждое окно находится в безопасности, что каждая точка входа в дом
является безопасным держать плохих парней из.
Но то, что делает плохой парень должен сделать, чтобы на самом деле компромисс ваш дом
и украсть у вас?
Он или она просто имеет, чтобы найти один разблокированный дверь, один разбитое окно, или что-то
вдоль этих линий, и это То же самое в области компьютерной безопасности.
Мы можем написать миллионы линии программного кода
и тратить сотни или тысячи из часов, пытаясь заставить его правильно,
но если вы делаете только один ошибка в правильности,
Вы можете поместить всю систему и Действительно, в этом случае весь интернет
и мир в опасности.
>> Так что если вы хотели бы узнать больше об этом, по следующему адресу здесь.
Там нет необходимости в действии сегодня, если вы не
среди тех, удобнее, что были запустить собственный веб
сервер, в этом случае вы должны, на самом деле, обновлять программное обеспечение.
>> И это тоже название речь, и теперь бумаги,
что мы связаны на Сайт курсы для начинающих на сегодняшний день.
Это было парень по по имени Кен Томпсон, который
принимал очень известный Премия в области компьютерных наук,
и он дал эту речь несколько лет назад, по существу, на этой же теме.
Запрашиваемая людей вопрос, должны вы действительно
доверие, в конечном счете, программное обеспечение вы получили?
Например, у всех нас есть писал программы,
и мы были компиляции им с Clang.
И вашим знаниям, вы написали любые программы для CS50, где есть
задняя дверь сортов, есть способ что плохой парень, если выполнение вашей программы,
может принять ваш компьютер?
Наверное, нет, не так ли?
Марио, и Жадные и Кредит.
Это все довольно небольшие программы.
Вы должны были бы быть довольно плохо, если вы на самом деле
сделает весь ваш компьютер уязвимым после написания 10 или 20 строк кода,
или, по крайней мере, не знают о некоторых о последствиях безопасности.
Теперь я говорю, что в шутку, но мы собираемся, чтобы увидеть сегодня
и на этой неделе это на самом деле действительно, очень легко
быть плохим и сделать еще короткие программы уязвимые.
>> Но сейчас, как минимум, понять, что вопрос поставлен здесь
о Clang в компилятор.
Почему нас доверяя Clang в течение последних двух-трех недель?
Кто может сказать, что тот, кто писал Clang не было "если" условие в там
что существенно вводят некоторое количество нулей и те, в каждую программу он компилирует
что позволит ему или ей доступ компьютер, когда вы спите
и ваш крышка ноутбука открыта и ваш компьютер работает?
Верно?
Мы имеем такую ​​системы честь справа Теперь, когда мы верим, что Clang является законным.
Вы уверены, что прибор является законным.
Вы уверены, что буквально каждая программа на вашем Mac или PC заслуживает доверия.
И как видно из этого простого ошибка, даже если это не злой,
что абсолютно не скорее всего, будет так.
>> Таким образом, вы должны быть страшно, как ад.
Честно говоря, нет простой Решение этой друга
чем своего рода общественной осведомленности из усложнением
что мы строим на вершине из наших компьютерных систем,
и как все более уязвимыми мы вполне может быть.
>> Теперь с этим сказал, Breakout.
Так Breakout является проблема установить три, и Breakout это игра от прошлого
что вы, возможно, помните, но для нас в проблему установить три,
это позволяет нам принимать вещи обратно на ступеньку выше
так что, когда мы пишем программы, даже в терминальном окне, как это,
мы можем реально работать, в итоге, графические программы не
в отличие от тех, кого мы имели доступ в пустом.
Так что это сотрудники отеля Реализация Breakout,
который является только этот кирпич-нарушение игра, что вы переместить весло обратно
и вперед, и вы попали против тех цветного кирпича до верхней.
Так что это приносит нам рода туда, где
мы смогли бы очень быстро с нуля, и теперь с C,
реализации нашей собственной графические интерфейсы пользователя.
>> Но более того, это Проблема набор представляет первый
, в котором мы даем Вы куча кода.
И в самом деле, я приношу явное внимание на это, потому что особенно
для тех, меньше знакомы, это Проблема установить, по крайней мере, на первый взгляд,
будет чувствовать себя, как мы взяли его на ступеньку выше.
Потому что мы дали вам, для некоторых из поиска
и сортировки проблемы в PSET, куча кода, который мы написали,
и несколько комментариев что сказать "делать",
где вы должны заполнить пробелы.
Так что не слишком страшно, но это в первый раз
мы вручить вам код, который вы должны впервые прочитал, понимаю, а затем добавить в
и завершить его.
>> А потом с Breakout, мы собираемся сделать то же самое,
давая вам несколько десятков больше линий кода, который, честно говоря, дать вам
много рамок для игра, но остановится
реализации кирпичи и мяч и весло,
но мы делаем реализовать некоторые другие функции.
И даже то, что на первый взгляд, опять же, особенно если менее комфортно,
может показаться особенно сложной и Вы думаете, что есть так много новых функций
вам нужно обернуть свой ум вокруг, и это правда.
Но имейте в виду, что это совсем как нуля.
Скорее всего вы не использовали все части головоломки в пустом месте.
Скорее всего вы не заботитесь, чтобы обернуть ваш ум вокруг все из них
потому все, что потребовалось было Быстрый взгляд, чтобы понять, о,
это то, что я могу сделать, с этой паззл.
И действительно, в задачи установить 3 спецификации, мы будем указывать вам
на документации, что будет познакомить вас с некоторыми новыми функциями,
и в конечном счете программирование строит использовании.
Условия, петли, переменные и функции
будут идентичны что мы видели до сих пор.
>> Так действительно, что мы дадим Вы пример кода, что
позволяет создавать окно что выглядит не в отличие от этого,
и в конечном итоге превратить его в нечто совсем так.
Так воспользоваться CS50, обсудить рабочие часы и многое другое,
и утешение в том, что объем кода вы должны написать
на самом деле не так уж и много.
Первая задача просто, чтобы акклиматизироваться себе некоторый код мы написали.
>> Любые вопросы по pset3, Контузия, или иначе?
>> АУДИТОРИЯ: Казалось, идти до конца с Breakout
что код почти объектно-ориентированный стиль,
но я думал, C был Объектно-ориентированный программы.
СПИКЕР 1: Отличный вопрос.
Таким образом, в просматривал Код распределения, код
мы писали для pset3, для тех, кто знаком, его
Похоже, что это немного объектно-ориентированный.
Короткий ответ, это.
Это приближение, как вы может сделать объектно-ориентированный код, используя
язык, как C, но это конечном счете, все процедурный.
Там не существует методов внутри переменные, как вы увидите.
Но это напоминает, что.
И мы увидим эту функцию снова когда мы доберемся до PHP и JavaScript
к концу семестра.
Но сейчас, думаю о нем, как намек на то, что будет дальше.
Хороший вопрос.
Хорошо.
Так сортировки слиянием был, как мы левые вещи в последний раз.
И сортировка слиянием было прохладно ощущение, что это было намного быстрее,
по крайней мере, на основе испытаний беглыми мы сделали на прошлой неделе, чем, скажем, пузырь
сортировать, выбор рода, сортировка вставками.
И то, что было опрятно слишком просто как лаконично и чисто
Вы можете выразить это.
И что же мы говорим, это было верхняя ограничение на времени работы слиянии
сортировать?
Да?
>> АУДИТОРИЯ: н § п?
>> СПИКЕР 1: п войти н, право. н войти н.
И мы вернемся к тому, что, что на самом деле означает или где что происходит от,
но это было лучше, чем то, что времени работы
что мы видели в течение пузырь Выбор и сортировка вставками?
Так н квадрат. н квадрат больше, чем это,
и даже если это не совсем очевидно, знаю, что журнал н меньше п,
так что если вы п раз то меньше, чем п,
это будет меньше п квадрат.
Это немного интуиции есть.
Но мы заплатили цену за это.
Это было быстрее, но тема, которая началась появляться на прошлой неделе был этот компромисс.
Я получил лучшую производительность Время мудро, но то, что
я должен потратить на другой рука, для того, чтобы достичь этого?
>> АУДИТОРИЯ: Память.
СПИКЕР 1: Скажите еще раз?
АУДИТОРИЯ: Память.
СПИКЕР 1: память, или пространство в целом.
И это не было супер Очевидно, с нашими людьми,
но напомним, что наших волонтеров ступали вперед и шагать
назад, как будто есть массив здесь, и как бы есть
Второй массив здесь они могли бы использовать, потому что мы
нуждались где-нибудь, чтобы объединить тех людей.
Мы не могли просто поменять их на месте.
Так сливаются сортировки рычаги больше места, которые
мы не должны с другие алгоритмы,
но вверх, что это намного быстрее.
И, честно говоря, в реальном мировом пространстве это days-- RAM, жесткий диск space--
является относительно дешевой, и так вот не обязательно плохо.
>> Итак, давайте бросим быстрый взгляд, немного более методично, на то, что мы сделали
и почему мы сказали, что это был п § п.
Так вот это восемь цифр и восемь добровольцев у нас был последний раз.
И первое, что Merge Сортировать сказал нам делать было что?
АУДИТОРИЯ: Разделить на две части.
СПИКЕР 1: Скажите еще раз?
АУДИТОРИЯ: Разделить на две части.
СПИКЕР 1: Разделить на две части, прямо.
Это очень напоминает телефонная книга, из пропасти
и властвуй в целом.
Таким образом, мы смотрели на левой половине.
А потом, как только мы сказали, вроде левая половина элементов,
Что же мы в следующий раз сказать?
Сортировать левую половину слева половина, который позволил нам,
после деления на две части, сосредоточиться на четырех и двух.
>> Как вы отсортировать список теперь, в желтый, размер два, используя Слияние Сортировать?
Ну разделить его пополам, и сортировать левую половину.
И это было, где вещи есть немного глупый кратко.
Как вы отсортировать список Вот из Размер один, как этот номер четыре здесь?
Это сортируются.
Вы сделали.
>> Но тогда, как же отсортировать список Размер один, когда это номер два?
Ну, то же самое, но теперь то, что было Третий и ключевой шаг в Merge Сортировать?
Вы должны были объединить левый половина и правая половина.
И как только мы это сделали, мы смотрели в четыре, мы смотрели на два.
Мы решили все в порядке, очевидно, два на первом месте,
поэтому мы помещаем два в его место, следуют четыре.
И теперь у вас есть, чтобы отчасти назад, и это является своего рода характеристикой
алгоритма, как Merge Сортировать, перемотка в памяти.
То, что было на следующий линия рассказа?
Что я должен концентрироваться на следующий?
Правая половина слева половина, что в шесть и восемь.
>> Итак, позвольте мне просто шаг через это без разговоре точку слишком много.
Шесть и восемь, то шесть является сортируются, восемь сортируется.
Слияние их вместе, как, что, и теперь следующий большой шаг
есть, конечно, сортировать правую половину от Самый первый шаг этого алгоритма.
Таким образом, мы сосредоточиться на одном, трех, семи, пяти.
Мы затем сосредоточиться на левой половине.
Левая половина, что, правая половина что, а затем объединить в одном и три.
Тогда правая половина, то левая половина из него, то правая половина его.
Слияние это, и сейчас то, что шаг остается?
Слияние большой левую половину и большой Правая половина, так что идет туда,
затем два, затем три, затем четыре, затем пять, то шесть, то семь, то восемь.
>> Так что теперь, почему этот в конечном счете, выявления, особенно если н и логарифмы больше
как правило, довольно бежать тебе, по крайней мере, в последнее время?
Ну, обратите внимание на высоту этой вещи.
У нас было восемь элементов, и мы разделить его на два, на два, на два.
Так войти базу два из восьми дает нам три.
И поверьте мне на том, что если немного туманно на что.
Но войти база два из восьми в три, таким образом, мы сделали три слоя слияния.
И когда мы объединены элементы, как многие элементы
же мы посмотрим на на каждой из этих строк?
В общей сложности п, не так ли?
Потому что, чтобы объединить верхнюю строку, хотя мы сделали это по частям,
мы в конечном счете коснулся каждое число раз.
И во втором ряду, чтобы объединить эти списки размера два,
мы должны были коснуться каждого элемента один раз.
А потом здесь действительно ясно в последнем ряду,
мы должны были коснуться каждого из тех, элементы сразу, а только один раз,
так в этом и заключается, то, наша н лог н.
>> И теперь только, чтобы сделать вещи немного более формальный на мгновение, если вам
были теперь анализировать этот в своего рода более высоком уровне
и попытаться решить, а как может вы идти о выражении
время работы этого алгоритма просто взглянув на него, а не
с помощью надуманный пример?
Ну, сколько времени вы можете сказать шаг, как это в желтый возьмет,
если п <2 возвращение?
Это большая O чего?
Так я вижу один, поэтому один шаг, может быть, два шага, потому что это, если
, а затем вернуться, но это Постоянная времени, не так ли?
Поэтому мы сказали O (1), и это как я буду выражать это.
T, просто время работы.
N является размер входа, так Т (п), только причудливый способ
сказать бег Время дано вход объема п
будет порядка постоянной времени, в O (1).
>> Но в противном случае, то, что об этом?
Как бы вы выразить время работы этого желтой линии?
T чего?
Вы можете рода обмануть здесь и ответить на мой вопрос циклически.
Так что, если время работы в Вообще мы просто сказать, Т (п).
А теперь ты рода понтировавшего здесь и говоря, ну просто отсортировать левую половину,
а затем отсортировать правую половину.
Как мы можем символически представляют время работы этой желтой линии?
T чего?
Что размер входа?
п над ними.
Почему бы мне просто не сказать, что?
И тогда это еще один Т (N / 2), а затем снова, если я объединить два отсортированных половинки,
сколько элементов я собираюсь иметь коснуться всего?
н.
Так что я могу выразить это, просто чтобы быть своего рода фантазии,
как времени работы в целом.
Т (п) является только время работы Т (п / 2), плюс Т (п / 2), оставил половину и правую половину,
плюс O (п), что, вероятно, п шагов, но может быть, если я использую два пальца,
это в два раза больше шаги, но это линейная.
Это некоторое количество шагов вот фактор п,
таким образом, мы могли бы выразить это, как это.
И это, где сейчас мы Пунт, чтобы назад из нашей средней школы по математике учебника
мы, что рецидива в конечном счете, заканчивается сравнявшись это, п раз войти н,
если вы на самом деле из математика более формально.
>> Так вот всего два перспективы.
Один численно с жестко типичный пример
с использованием восьми цифр и больше Общий взгляд на то, как мы добрались там.
Но что действительно интересно здесь , опять же, это понятие на велосипеде.
Я не использую для петель.
Я вроде определения то с точки зрения само по себе,
не только с этим Математическая функция,
но и с точки зрения этой псевдо-код.
Это псевдо-код рекурсивен в этом двух своих линий
по существу говорю это, чтобы пойти использовать себя решить меньше
Проблема меньшего размера, а затем снова и снова
и не раз, пока мы свести его до этого так называемого базового варианта.
>> Так что давайте на самом деле сделать более привлекательным вынос из этого следующим образом.
Позвольте мне идти в Gedit и принять посмотрим на некоторые из сегодняшней исходного кода,
В частности, этот пример здесь.
Sigma 0, по-видимому, добавляет номера с первого по п.
Итак, давайте посмотрим, что знакомы и незнакомым здесь.
Впервые у нас есть пару включает в себя, так что ничего нового там.
Прототип.
Я немного туманно на это после нескольких дней,
но то, что мы говорили Прототип функции?
АУДИТОРИЯ: [неразборчиво].
СПИКЕР 1: Что это?
АУДИТОРИЯ: Мы объявляем его.
СПИКЕР 1: Мы объявляем его.
Таким образом, вы учите Clang, эй, фактически не осуществляет это еще,
а где в этом файле, по-видимому, собирается быть функция называется то, что?
Sigma.
И это только обещание, что это будет выглядеть следующим образом.
Это собирается занять целое, как input-- и я могу быть более явным
и сказать Int N --И это собирается вернуть Int,
но точка с запятой означает, мм, я обойти в реализации этого чуть позже.
Опять же, Clang является немым.
Это только собирается знать, что Вы говорите это сверху вниз,
так что мы должны по крайней мере дать это намек на то, что будет дальше.
>> Теперь давайте посмотрим на главный здесь.
Давайте прокрутите вниз здесь и видеть то, что главный делает.
Это не так долго функции, и на самом деле конструкция здесь знаком.
Я объявить переменную п, а затем Я приставать пользователю снова и снова
для целого положительного числа, используя GetInt, и единственный выход из этой петли
как только пользователь выполнил.
Делать во время, мы использовали, чтобы приставать к пользователю таким образом.
Теперь это интересно.
Я объявить Int под названием "Ответ".
Поручаю это возвращаемое значение функции под названием "сигма".
Я не знаю, что это делает еще, но Я помню, объявив ее минуту назад.
И тогда я передаю в значение, которое пользователь вводит в N,
и тогда я сообщить ответ.
Ну давайте прокрутки назад на мгновение.
Давайте пойдем дальше в этот каталог, сделать сигма 0, а на самом деле запустить эту программу
и посмотреть, что происходит.
Так что, если я иду вперед и бежать эта программа, ./sigma-0,
и я печатаю в положительном целое, как два, Sigma,
как греческий символ означает, это просто собирается сложить все числа от
нулю на до двух.
Так 0 плюс 1 плюс 2.
Так что это, будем надеяться, дать мне 3.
Вот и все, что он делает.
И точно так же, если я запускаю это снова и я даю ему число три,
вот 3 плюс 2, так что это 5, плюс 1 должен дать мне 6.
И потом, если я получаю действительно сумасшедший и наберите текст в больших количествах,
он должен дать мне все больше и больше суммы.
Так вот и все.
>> Итак, что же сигма выглядеть?
Ну, это довольно просто.
Это то, как мы могли бы осуществляться это за последние пару недель.
"Int" будет тип возвращаемого.
Сигма это имя, и он принимает переменная м вместо п.
Я изменю, что до лучших.
Тогда это просто санитарная проверка.
Мы увидим, почему в данный момент.
Теперь я заявляю еще одну переменную, сумма, инициализировать его к нулю.
Тогда у меня есть этот цикл итерации, по-видимому, для ясности,
от я = 1 на до = т, что является что пользователь ввел в, а затем я
увеличить сумму, как это.
А потом возвратить сумму.
>> Так пару вопросов.
Один, я утверждаю, на мой комментарий, который это избегает риска бесконечный цикл.
Почему передавая бы в негативном числа побуждать, потенциально, в бесконечный цикл?
>> АУДИТОРИЯ: Вы никогда не будете достигать м.
>> СПИКЕР 1: Никогда не лезьте м.
Но м передается в, так что давайте Рассмотрим простой пример.
Если м передается в по Пользователь, как отрицательного.
Независимо от основной.
Главная защищает нас от это тоже, так что я просто
будучи действительно анал с сигма также убедиться,
что вход не может быть отрицательным.
Таким образом, если отрицательна м, то как отрицательного.
Что произойдет?
Ну, я собирается инициализируются один,
и тогда я будет меньше или равно т?
>> Ожидание.
Это was-- давайте не, давайте Никс эту историю.
Я не задать этот вопрос, потому что риск того, что я, намекая на
не произойдет, потому что я это всегда будет быть больше than-- ОК,
Я отрекаюсь этот вопрос.
Хорошо.
Давайте сосредоточимся только на этой части здесь.
Почему я заявляю некоторые вне цикла?
Уведомление на линии 49 У меня объявлены I внутри петли,
но на сайте 48 У меня заявил некоторое пределами.
Да.
АУДИТОРИЯ: [неразборчиво].
СПИКЕР 1: Конечно.
Так, прежде всего, я, конечно, не хочу объявить и инициализировать сумму
с нулевой внутренней петля на каждой итерации,
потому что это будет ясно победить Цель подведения номера.
Я хотел бы сохранить изменения значение на ноль.
А также, что еще один более тайной Причина тому же дизайнерское решение?
Да.
>> АУДИТОРИЯ: [неразборчиво].
СПИКЕР 1: Точно.
Я хочу получить доступ к нему вне петли тоже на какой линии?
На 53.
И на основе нашего правило от пару лекций назад,
переменные области видимости, действительно, в Фигурные скобки, которые охватывают их.
Так что, если я не объявить сумму внутри из этих внешних фигурные скобки,
Я не могу использовать его в линии 53.
Иными словами, если я объявил сумма в здесь, или даже в течение
Для цикла, я не мог получить доступ к нему в 53.
Переменная бы эффективно не будет.
Так несколько причин там.
Но теперь давайте вернемся и посмотреть, что происходит.
Так сигма вызывается.
Он добавляет, 1 плюс 2, или 1 плюс 2 плюс 3, а затем возвращает значение,
сохраняет его в ответ, и Е здесь Поэтому я вижу на экране.
Так это то, что мы называем повторяющийся Подход, в котором итерации только
означает использование петлю.
Для цикла, в то время как цикл, Do Хотя цикл, а просто делаю то снова
и снова и снова.
>> Но сигма вид аккуратный функции в что я мог реализовать его по-разному.
Что по этому поводу, которые просто чтобы быть круто,
дайте мне действительно избавиться из большого отвлечения
потому этой функции действительно очень просто.
Давайте свести его только чтобы ее четырех основных линий
и избавиться от всех комментарии и фигурные скобки.
Это своего рода умопомрачительных Альтернативная реализация.
Ладно, может быть, не умопомрачительных, но это отчасти сексуальнее, все в порядке,
смотреть на это так много более лаконично.
С помощью всего лишь четыре строки кода, Я сначала это здравомыслие проверку.
Если т меньше или равна нулю, сигма не имеет смысла.
Это только должно быть в этот случай для положительных чисел,
так что я просто хочу, чтобы возвратить нуль произвольно
так что мы по крайней мере, некоторые так называемые базовый вариант.
>> Но здесь-то и прелесть.
Совокупность этой идеи, добавляя числа от 1 до п, или м в этом случае,
может быть сделано по видам перекладывания ответственности.
Ну, то, что является суммой 1 до т?
Ну, вы знаете, что?
Это то же самое как сумма м плюс сумма 1 до т минус 1.
Ну вы знаете, что?
Что сигма м минус 1?
Ну, если вы вроде следовать этому логически, это то же самое, как м минус 1
плюс сигма м минус 2.
Таким образом, вы можете рода просто-- это как, если вы просто
пытается досадить другу и они задать вам вопрос,
вы вроде ответить на вопрос, Вы можете отчасти держать перекладывания ответственности.
Но то, что ключевым является то, если вы держите что делает этот вопрос все меньше и меньше
и меньше, вы не спрашивая, что это сигма
п, что сигма п, что сигма п?
Ты просишь что сигма п, что сигма
н минус 1, что сигма н минус 2?
В конце концов ваш вопрос собирается стать что?
Что Sigma из одного или нулю, некоторые очень малое значение,
и как только вы получить, что, ваш друг,
Вы не собираетесь спросить тот же вопрос снова,
вы только собираетесь сказать, О, это ноль.
Мы закончили играть этот вид тупой циклического игры.
>> Так рекурсия акт в программировании функции, называющая себя.
Эта программа, при компиляции и запуска, является собирается вести себя точно так же,
но то, что ключ, что внутри функции под названием Sigma,
есть строка кода отличающийся тем, мы называем себя,
которые, как правило, плохо.
Например, что, если я первый составлен этот, так что sigma--
сделать сигма 1 ./sigma-1.
Положительное целое, пожалуйста, 50 1275.
Так что видимо функция бы, на основе одного теста, правильной.
Но что, если я немного опасно и удаление так называемого базового варианта,
и просто сказать, а я просто сделать это сложнее, чем это.
Давайте просто вычислить сигма принимая м с последующим добавлением
в сигма м минус один?
Ну, то, что произойдет здесь?
Давайте уменьшения масштаба.
Давайте перекомпилировать программу, сохранить его, перекомпилировать программу,
а затем готов ./sigma-1 масштабирования, введите положительное целое число пожалуйста, 50.
Как многие из вас готовы признаться до видя, что?
>> Хорошо.
Так что это может произойти в течение целый ряд причин,
и откровенно на этой неделе мы о, чтобы дать вам несколько из них.
Но в этом случае, попробуйте рассуждать в обратном направлении
Что могло бы произойти здесь?
Ошибка сегментации, мы сказали в прошлом Время, относится к сегменту памяти.
Что-то плохое случилось.
Но что же это было механически, что пошло не так
здесь из моего удаления из этой так называемой базовой случае,
где я вернулся жестко запрограммированный значение?
Что вы думаете пошло не так?
Да.
>> АУДИТОРИЯ: [неразборчиво].
СПИКЕР 1: Ах.
Хороший вопрос.
Так размера числа что я подведения
получил настолько большой, что он превысил размер памяти.
Хорошая идея, но не принципиально собирается вызвать сбой.
Это может привести к целочисленное переполнение, где биты просто перевернуть
и тогда мы ошибочно действительно большой номер для как отрицательное число,
но, что само по себе не приведет к аварии.
Потому что в конце день Int еще 32 бита.
Вы не собираетесь случайно украсть 33-е немного.
Но хорошая мысль.
Да.
>> АУДИТОРИЯ: [неразборчиво].
СПИКЕР 1: Метод никогда не прекращает работать,
и это действительно так называет себя снова и снова и снова и снова
и снова, и ни один из эти функции когда-либо
закончить, потому что их единственной линии код вызывает сам себе снова и снова
и снова.
И то, что на самом деле что здесь происходит, и теперь мы
может отчасти обратить на это графически.
Позвольте мне перейти к картина на мгновение.
Это картина, что в конечном итоге будет конкретизировать
более подробно, что происходит на внутри памяти компьютера.
И получается, что на Дно этой картинке
то, что называется стек.
Это кусок памяти, кусок памяти,
вот только использоваться в любое время функция вызывается.
Каждый раз, когда вы, программист, вызвать функцию,
операционная система, как Mac OS, Windows, или Linux,
хватает куча байтов, может быть, несколько килобайт, может быть, несколько мегабайт
памяти, передает их Вам, а затем позволяет
вы ведете свой функцию с помощью все переменные вам нужно.
И если вы затем вызвать другой Функция и другая функция,
вы получите еще один кусочек памяти и еще кусочек памяти.
>> И в самом деле, если этих зеленых лотков от Анненберг представляют эту память,
вот что происходит первым вызове функции сигма.
Это как положить поднос, как это на том, что изначально пустой стек.
Но тогда, если этот лоток называет себя, так сказать,
вызов в другой экземпляр сигма, это
как просить операционную систему, ох, нужно немного больше памяти,
дай мне это.
И тогда он получает свалили на поверх.
Но то, что ключевым здесь является то, что первый лоток по-прежнему существует,
потому что он вызывается этот второй лоток.
Теперь между тем, сигма называют сигма, вот как просить больше памяти.
Получает свалили на здесь.
сигма называют сигма, это уже совсем другая лоток, который получает свалили на здесь.
И если вы продолжаете делать это, в конце концов, своего рода карту этого визуального
в той диаграмме, что происходит в случиться со стеком лотков?
Это будет превышать сумму памяти компьютера имеет.
И как только этот зеленый лоток превышает горизонтальную линию
выше стека и выше, что слово кучи, которые мы еще вернемся в будущем,
что это плохо.
Куча отличается сегмент памяти,
и если вы позволите это Лотки куча и куча на,
вы собираетесь превышать самостоятельно сегмент памяти,
и программа действительно врежется.
>> Теперь как в сторону, этой идеи рекурсии, поэтому,
может четко привести к проблемам, но это не обязательно плохо.
Потому что считаю, после все, how-- и, возможно,
это требует некоторого привыкания чтобы --Как элегантный или как просто
что реализация сигма был.
И мы не собираемся использовать рекурсия все, что многое в CS50,
но в CS51, и действительно любой класс где вы манипулировать структуры данных
как деревья, или семейных деревьев, что есть иерархия,
это супер, супер полезно.
Теперь, как в сторону, так, чтобы вас как стремящихся компьютерных ученых
знакомы с некоторыми из Google, внутри анекдоты, если вы идете в Google
и вы посмотрите, что является определение, скажем, рекурсия, введите.
Угу.
Как в стороне, я подъехал немногие.
Это было, как 10 минут промедление сегодня утром.
Если вам также Google "криво", уведомление наклоняя голову slightly--
и то это одно, пожалуй, Наиболее жестокие всего
так как кто провел как их день реализации этого
несколько лет ago-- давай.
О, wait-- это ошибка.
>> Так работает на одном из Крупнейшие сайты мире
эти глупые маленькие пасхальные яйца.
Они, вероятно, потреблять нетривиальное количество строк кода
просто так, что мы можем иметь маленькие забавные вещи, как, что.
Но по крайней мере теперь вы получаете некоторые из этих внутренних шуток.
>> Теперь давайте взглянем на некоторые из белый лежит мы говорили в последнее время,
и начинают отогните некоторые слои технически
так что вы действительно понимаете, что происходило на
и вы можете понять, некоторые из угроз,
как Shellshock, что уже начали, чтобы стать
на переднем крае каждого внимание, по крайней мере, в средствах массовой информации.
Так вот это очень простая функция что ничего не возвращает, недействительными.
Его зовут подкачки.
Это занимает от двух переменных и это ничего не возвращает.
Принимает в а и б.
Так короткий ролик, демонстрирующий.
Мы принесли эти вверх.
Мы могли бы также взять немного разбить здесь на мгновение
и есть немного то, чтобы пить.
Если кто был бы не против присоединения мне здесь на мгновение.
Как о вас в темно-бордовый рубашку?
Поднимайтесь.
Только один сегодня.
Спасибо, хотя.
Ладно, и у нас есть придумывать, кто здесь?
Как тебя зовут?
>> СПИКЕР 4: Лаура.
>> СПИКЕР 1: Лора.
Поднимайтесь.
Так Лора, очень простой задачей сегодня.
Приятно познакомиться йо.
Хорошо.
Поэтому у нас есть немного молока сюда и у нас есть немного апельсинового сока здесь
и некоторые чашки, которые мы заимствованы из Анненберг сегодня.
>> СПИКЕР 4: Заемные.
СПИКЕР 1: И собираюсь идти вперед и дать вам полстакана этого.
Хорошо.
И мы дадим вам половину стакан молока.
О, и просто так, что вы можете помню, что это было, как,
Я забыл приносить это и сегодня.
Хорошо.
Если вы не возражаете, давайте посмотрим, что мы может поставить их на Ваших очков
если ты хочешь.
Это будет мир от глаз Лоры.
Хорошо.
Так ваша цель, учитывая две чашки жидкость здесь, молоко и апельсиновый сок,
будет поменять местами два содержимое таким образом, что апельсиновый сок идет в чашку молока
и переходит в молоко чашка апельсинового сока.
>> СПИКЕР 4: Могу ли я получить еще одну чашку?
СПИКЕР 1: Я так рада, что вы спросили, хотя это было бы намного лучше, кадры
если бы вы не спросили.
Но да, мы можем предложить вам третий чашка, что там пусто, конечно.
Хорошо.
Так своп содержимое там.
Очень мило.
Очень хорошо.
Вы делаете это удивительно тщательно.
И третьему шагу.
Хорошо.
Отлично.
Большой взрыв аплодисментов было бы хорошо для Лауры.
Хорошо.
У нас есть небольшой прощальный подарок для вас, но позвольте мне взять это.
Спасибо большое.
Таким образом, простой пример, тем не менее, чтобы продемонстрировать, что если вы делаете
хотите поменять содержимое из двух контейнеров,
или назовем их переменными, Вы нуждаетесь в некотором временное хранение
на сцене одного из содержания в так что вы реально можете сделать своп.
Так действительно, это исходный код здесь, в C является представителем именно это.
Если апельсиновый сок был и молоко было б, и мы хотели, чтобы поменять их местами,
Вы можете попробовать то творческое путем заливки друг в друга,
но, что, вероятно, не будет в конечном особенно хорошо.
И поэтому мы используем третий стакан, звоните это TMP, T-M-P по соглашению,
и поместить содержимое OJ в том, что, то поменять одну чашку,
затем положить OJ в Оригинальный кубок, тем самым
достижения, так же, как Лаура сделал, своп.
>> Так что давайте делать именно это.
Позвольте мне идти вперед и открыть до примера, это
на самом деле называется "нет обменять, "потому что это не
как просто сделать, как вы думаете.
Таким образом, в этой программе, заметили, что Я использую stdio.h, наш старый друг.
У меня есть прототип для подкачки там, которые
означает его реализация сайт вероятно, внизу,
и давайте посмотрим, что это главное Программа будет делать для меня.
Я сначала объявить Int х получает один, и десятичного у получает два.
Так думать о тех, как OJ и молоко, соответственно.
А потом я просто есть Е говоря х это
и у это, только так я могу наглядно увидеть, что происходит.
Тогда я PRINTF утверждая что я перекачки два,
и тогда я распечатать утверждают, что они поменялись,
и я распечатать х и у вновь.
Так здесь, в своп именно то, что сделал Лаура,
и именно то, что мы видели на экран минуту назад.
>> Так что давайте идти вперед и очень разочарованы.
Не делайте своп, и не создает никаких проблем своп, масштабирования на выходе здесь.
Введите х 1, у 2, перекачки местами.
х по-прежнему 1, а у еще 2.
Таким образом, даже при том, что, откровенно говоря, это выглядит точно как, хотя и более технически,
что сделал Лаура, не похоже на работу.
Так почему же?
Ну, получается, что, когда мы пишем программу, как это
что оба главный, здесь освещены, а затем еще одна функция, как своп,
Показанные здесь, которые он вызывает, мир
выглядит немного нечто подобное эти лотки момент назад.
Когда основная первый вызывается, что все равно что просить операционную систему
для немного памяти для любой местный переменные, такие как х и у, что основная имеет,
и они в конечном итоге прямо там.
Но если основные вызовы поменять, а главное проходит поменять два аргумента, а и б,
апельсиновый сок и молоко, это не так вручая апельсиновый сок и молоко
Лоре.
Что делает компьютер, является его проходит копии апельсинового сока
и копии молока к Лауре, так что что в конечном итоге внутри этого лотка
это одно значение, и два или OJ и молоко, но их копии,
так что на данный момент в истории, есть
это OJ и молоко в каждом из этих лотков.
Там в один и два в каждом из этих лотков,
и функция подкачки действительно работает.
Это поменяв их внутри из второго верхнего лотка,
но, что замена не влияет.
И на основе лишь некоторые Основной принцип мы в
говорили раньше, и в самом деле всего несколько минут назад, что
может объяснить, почему изменения и б внутри свопа
не имеет никакого влияния на х и у, хотя Я прошел х и у функции подкачки.
Что здесь ключевым словом, что может упрощенно объяснить?
Я думаю, что я слышал его здесь?
АУДИТОРИЯ: Return.
СПИКЕР 1: Возвращение?
Не вернуться.
Пойдем с одним другим.
Что это?
>> АУДИТОРИЯ: [неразборчиво].
>> СПИКЕР 1: Итак, return-- мы могли сделать обратный работу в этой истории,
но есть еще более простое объяснение.
АУДИТОРИЯ: Сфера.
СПИКЕР 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, чтобы приостановить выполнение в.
Так что я не должен теперь изменить свой код, добавить PRINTF-х, пересобрать их повтор
его, изменить, добавить некоторые PRINTF-х, сохранить его, перекомпилировать его, запустить его.
Я могу просто ходить по моей программе шаг за шагом за шагом в человеческой скоростью,
не на Intel-внутри вида скорости.
>> Так что теперь заметить эту линию появляется здесь, и если я вернусь
в моей программе в Gedit, заметить, что это на самом деле
Самая первая строка кода.
Там в линии 16 в Gedit.
Там в линии 16 в GDB, и даже хотя этого черно-белого интерфейса
не почти как пользователь дружелюбный, это означает,
что линия 16 не был выполнен пока нет, но это собирается быть.
Так ведь если я типа печати х, не Е, просто распечатать х,
Я получаю некоторые фиктивные значения там нуля, потому х не был инициализирован еще.
Так что я собираюсь ввести следующий, или, если вам хочу быть необычный, просто п на следующий.
Но когда я печатаю следующий введите, теперь заметите, что он переходит к строке 17.
Так логично, если я выполняется строка 16 и теперь я печатаю Print X,
что я должен увидеть?
Один.
>> А теперь это, по общему признанию в заблуждение.
$ 2 это просто причудливый способ, если вам хочу обратиться к этому значению позже,
Вы можете сказать: "знак доллара два."
Это как обратной ссылки.
Но сейчас, просто игнорировать его.
Что интересно, в чем справа от знака равенства.
И теперь, если я печатаю следующий раз и печать у, я должен видеть 2.
Я также могу сейчас печатать х снова, и, честно говоря,
если я получаю немного запутался, где я нахожусь, я могу список для списка введите
и просто посмотреть, некоторый контекст вокруг точка на самом деле я в.
И теперь я могу типа Следующий, и там х 1.
Теперь я печатаю следующий.
О, у есть 2.
И снова, это сбивает с толку, потому выход GDB в
будет смешиваться с моей собственной продукции.
Но если вы держите в уме, по поглядывая назад и вперед на ваш код
или укладки его сторону бок, возможно, вы будете
видеть, что на самом деле я просто пошагового моей программе.
>> Но обратите внимание, что произойдет дальше, буквально.
Вот строки 22.
Отпусти меня над ним, тем самым перемещая на до 23, а если я печатаю х сейчас, еще один.
И если я печатаю у теперь, еще один.
Так что это не полезное упражнение.
Итак, давайте заново это.
Позвольте мне вернуться до сверху и тип запуска снова.
И это говорит программу который отлаживается
уже началась, начали с самого начала.
Да, давайте сделаем это снова.
И на этот раз давайте делать дальше, Далее, следующий, следующий, следующий,
но теперь начинается самое интересное.
Теперь я хочу, чтобы ступить в своп, так что я не вводите следующий.
Я печатаю шаг, и теперь замечают подскочила меня noswap.c линии 33.
Если я возвращаюсь в Gedit, что линия 33?
Это первое фактическое строка кода внутри свопа.
Что приятно, потому что теперь я могу вид копаться и получить любопытно
относительно того, что происходит действительно там.
Позвольте мне печатать TMP.
Вау.
Почему TMP есть некоторые с ума, поддельным значение мусор?
АУДИТОРИЯ: Это не был инициализирован.
СПИКЕР 1: Это не был инициализирован.
И действительно, когда вы запускаете программу, Вам дают целый букет памяти
операционной системой, но вы не инициализируется любые значения,
так что биты вы видим здесь, хотя это
этот сумасшедший большой негатив число, просто означает,
что те остатки от некоторые предыдущие использование этой памяти,
хотя у меня не я нуждался в нем еще.
Так что теперь я собираюсь идти вперед и тип Следующий, и, если я теперь типа печати TMP,
что я должен увидеть?
Какой бы ни была стоимость была, первый аргумент, только
как х был первым вещь передается в,
так и х должны быть такими же, так печатать TMP должны напечатать мне один.
>> Так что вы увидите в проблемной набора три учебник рода на GDB,
но понимаю, что это начало из взгляда на инструмент, который будет на самом деле
помочь вам решить проблемы таким образом, гораздо более эффективно.
Что мы, в конечном счете собираюсь сделать в среду
это начать отогните несколько слоев и удалить некоторые дополнительные колеса.
Это, что называется строка, мы использовали в течение некоторого времени,
мы собираемся медленно отнять от вас и начать говорить о
то более эзотерически известен как символ *,
но мы собираемся сделать это красиво и сначала нежно, хотя указателей,
как они называются, можно сделать некоторые очень плохие вещи, если злоупотреблять,
глядя на небольшой Claymation от наш друг Ник Parlante из Стэнфорда
Университет, профессор в компьютере наука, кто собрал эту превью
того, что должно прийти в эту среду.
>> [ВИДЕОВОСПРОИЗВЕДЕНИЕ]
Эй, Бинки.
Просыпайся.
Это время для указателя веселья.
>> -Что Что?
Узнайте о указателей?
О, положительный герой!
[END ВИДЕОВОСПРОИЗВЕДЕНИЕ]
СПИКЕР 1: Это ждет вас в среду.
Увидимся тогда.
[ВИДЕОВОСПРОИЗВЕДЕНИЕ]
-И Сейчас, Deep Thoughts, по Daven Фарнэме.
>> Почему мы изучаем C?
Почему бы не +?
>> [Смех]
>> [END ВИДЕОВОСПРОИЗВЕДЕНИЕ]