>> [МУЗИКА ГРАЄ]
>> СПІКЕР 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 відеовідтворення]