[Powered by Google Translate] [Тиждень 7] [David J. Малан - Гарвардський університет] [Це CS50. - CS50.TV] Добре. Ласкаво просимо назад. Це CS50, і це початок тижня 7. Два маленьких оголошення: Pset5 В даний час ведеться або скоро буде, і дозвольте мені сказати, чесно кажучи, це, як правило, серед більш складною завдання курсу наборів, тому дозвольте мені говорити про це зараз так що на цьому тижні більше, ніж коли-небудь ви не чекайте, поки, скажімо, в середу ввечері або в четвер вночі, щоб зануритися дюйма Це, безумовно, цікава PSET. Ми вважаємо, що це весело. Якщо ви дійсно отримаєте його повністю правильним і може кинути виклик так званого Великого ради, Ви будете мати можливість змагатися з деякими співробітниками курсу і деякі з ваших однокласників. Що Великої Ради є один раз у вас є для перевірки орфографії роботи, Ви будете в змозі піти в cs50.net після запуску команди, чисто відмовитися, і потім кількість часу і об'єм оперативної пам'яті і більш , Які ви використовували в своїй реалізації будуть виставлені тут, на домашній сторінці курсу. Ви помітите, що ціла купа цих людей тут вказані в якості співробітників так як в минулі вихідні, співробітники думали, що це було б цікаво прагнуть перевершити один одного. Так розумію, що мета тут не перевершити персоналу. Навіть я тільки тут, під номером 13. Чисто вибрати в, але це можливість побачити, як мало оперативної пам'яті і як мало процесора секунд ви можете використовувати VIS-A-VIS деякі з ваших однокласників. 

І я визнаю, що Kevin Michael Schmid, В даний час номер 1 позицію як одного з ТФ, Це реалізація, яку ми називаємо не представляється можливим враховуючи, що він використовує майже 0 оперативної пам'яті і майже 0 секунд для завантаження. Таким чином, ми будемо дбати про форум Кевін. [Сміх] Є певні навички, Кевін ставить на тест тут. Одна з речей, ми думали, що робити теж зараз CS50x є тижня в прогрес, і ви, хлопці, така ж частина цього експерименту, як ті студенти. Ми запитали їх, як частина їх pset0, який був так само представити проект до подряпин становлять інтерес для них - гра, інтерактивні твори мистецтва, анімації і т.п. - 1 - 2-хвилинне відео, якщо вони хотіли б, щоб привітатися зі світом і хто вони насправді. Я думав, що я поділюся з вами всього кілька відео, які були представлені досі тому що для нас, в штабі принаймні, це дійсно була захоплюючою і надихаючим, щоб побачити цих людей з усього світу - країн по всьому світу - налаштуванні на, всіх речей, на курс інформатики в Інтернеті, чи є це тому, що вони хочуть продовжити свою освіту, вони хочуть взяти свою кар'єру в новому напрямку, вони хочуть, щоб заповнити прогалини у своїх знаннях, тому деякі з тих же причин, що ви, хлопці, можливо, були тут. 

Тому я наведу вам один такий студент тут. Ви можете збільшити гучність тільки трохи. Ось один із 1-хвилинний наших студентів уявлень. Здрастуй, світ. Я студент промислового будівництва тут, в Малазі, Іспанія. Я дуже радий цій онлайн-курс, тому що я люблю інформатику, я справді роблю, і я дійсно ціную, що я отримую, щоб вивчити її. І те, що я можу навчитися же все ви, хлопці, але замість того, щоб в Гарварді я в Малазі, яким дивним є те, що? Ну, я Фернандо, і це CS50. Див вас, хлопці. [Сміх] Інший кліп нам особливо подобається, ви виявите, що англійське цього пана не так сильно. Схоже, він його машина переводиться, таким чином, переклади самі трохи недосконалим, але це було одним з наших улюблених досі, а також. [♪ ♪] Здрастуй, світ. [Говорить по-японськи] [Я повинен вітати на японській мові, тому що мій англійський дуже ненадійно.] [Я передав послання до вас з міста Гіфу, Японія.] [Я можу бути студентом в перший раз в 20 років, як це можна бачити.] [Я дуже вдячна Гарвардського університету, який дав мені цю можливість і EDX.] [Гольф-гітара і моя улюблена річ працює.] [Сміх] [♪ ♪] [Чому ви думаєте, що я намагався взяти участь в cs50x.] [Гарвардського університету, це моя туга.] [Особливо, якщо я далекого присутності жив у Японії.] [Я хотів спробувати відразу знають про існування таких EDX, коли.] [Чи не здається вам, щоб ви не пов'язане з віком навчання I.] [CS50 моя туга. Мене звати Kazu, і це CS50.] [♪ ♪] [оплески і крики] Інша улюблена наша була тут це подання від когось. [♪ ♪] [Малан] Google, якщо ви не знайомі з цим мемом. 

І тоді, нарешті, кілька інших, які отримали відповідав, що, можливо, виграти чарівні нагороду. [Студентів] Ой! >> [Малан] Ми повинні слухати. Це короткий, так що слухайте уважно. [Жінкою-спікером] Як тебе звуть? >> Луї. [Жінкою-спікером] Що це? >> [Сміх] CS50. [Сміх] [Малан] Він двох дублів, однак. Тут ми йдемо, останній. Мене звати Луї, і це CS50. [Сміється] У цьому і полягає CS50x. Спасибі всім тим з вас, слідуючи вздовж будинку , Які були причасті до цих пір. Сьогодні ми закінчуємо обговорення структур даних, принаймні деякі з найбільш фундаментальних, а потім ми продовжимо нашу розмову про HTML і веб-програмування. Дійсно, ми провели останні сім тижнів деякі, дивлячись на основи програмування - алгоритми, структури даних і т.п. - і C, як ви, можливо, випробували досі, не обов'язково є найбільш доступних мов з яким для реалізації деяких з цих ідей. І так починаючи з цього тижня і на наступному тижні, а потім наступний, ми, нарешті, бути в стані переходу від С, який, як відомо, досить низького рівня мови, до речей більш високого рівня, в тому числі PHP, JavaScript, тощо, що ми побачимо спиратися на ті ж уроки, що ми дізналися за останні кілька тижнів, але ви побачите, що оголошення речей, як масиви і хеш-таблиці та пошук і сортування стало набагато легше, тому що самі мови, ми почнемо використання буде ставати все більш потужними. Але, по-перше, застосування дерев. Це дуже часто в ці дні потрібно стиснути інформацію. В якому контексті ви хочете стиснути деякі види цифрової інформації? 

Так. >> [Студент] Якщо вам потрібно, щоб відправити його через Інтернет. Так, коли ви хочете відправити щось через Інтернет. Якщо ви хочете завантажити великий файл, він ідеально підходить, якщо хтось на іншому кінці стиснув, що файл, використовуючи формат ZIP або щось на зразок того так що ви посилаєте менше біт, ніж могли б бути передані. Отже, як ви стискати інформацію? Це все зводиться до використання меншої кількості бітів, ніж вимагається за замовчуванням. Але це начебто цікаво, тому що згадайте тижнів 0 і 1 коли ми говорили про ASCII і бінарні і ми говорили про ASCII, зокрема, як за допомогою 8 біт для представлення літери алфавіту так що буква представлена ​​65, нижній регістр число 97, і тим не менше ви уявляєте 65 або 97, ви використовуєте 7 або 8 біт. Але заковика в тому, що деякі букви в англійському алфавіті , Які не так популярні, як інші. Z не все, що популярно, Q не все, що популярно, але А і Е є супер популярним. І тим не менше за всі ці листи, за замовчуванням світі використовує таку ж кількість бітів, всього в 8. Таким чином, чи не було б розумніше, якби замість 8 біт для кожного листа, навіть самі рідко використовувані як Q і Z, що, якщо ми використали менше біт для А і Е і S і найпопулярніших літер і використовується більше бітів для менш популярних букви, Ідея в тому, оптимізувати давайте для загального випадку, , Яка є темою в області комп'ютерної науки в спробі оптимізувати те, що трапиться саме і витратити ще трохи часу, трохи більше простору на те, що, так, може відбутися але не обов'язково так часто. Отже, давайте розглянемо приклад. 

Припустимо, що ми хочемо, щоб кодувати інформацію досить ефективно. Ви, можливо, виросли знаючи дещо про азбуки Морзе, і цілком імовірно, ви не знаєте, фактичний код, але ви, можливо, пам'ятаєте, що це принаймні в цій серії точок і тире. Це досить ефективне кодування, і помітили, що найпопулярніші літери - наприклад, E - використовує найкоротші звукових сигналів. Азбука Морзе це все про біп-біп-біп-біп-біп-біп та проведення тонах або протягом короткого періоду часу або тривалих періодів часу. E, так як позначається крапкою, це супер короткий звуковий сигнал, тільки звуковий сигнал, і що буде представляти E. На відміну від T буде більше звуковий сигнал, як сигнал [подовжує звук] і що буде представляти T. Але це все ще досить короткою, тому що, навпаки, якщо ви подивитеся на Z, щоб висловити Z ви підете біп, біп [більше звуку], біп, біп [короткий звук]. Так що це більше, тому що це менш поширене. Але Гоча тут є те, що код Морзе трохи недоліків в тому, що це не відразу програватися. Наприклад, припустимо, що ви чуєте на деякі кінці дроту звуковий сигнал [короткий], звуковий сигнал [довго]. Яке повідомлення я тільки що отримав? Крапки і тире. Що це уявляєте? [Студент] A. >> [Малан] Може бути. Це також може бути E подальшим T. Іншими словами, азбука Морзе, хоча він використовує цей принцип оптимізації кута випадку, воно не піддається безпосередній декодіруемий. Тобто, людина, яка чує або отримання цих крапок і тире повинен якимось чином з'ясувати, де розриви між буквами, тому що, якщо ви не знаєте, де ці перерви, ви можете змішувати для ET або навпаки. 

Так що ж ви робите? В азбуці Морзе можна просто пауза між кожною з букв. Але зупиняючись це свого роду лічильник, щоб весь сенс прискорення речі. Так що, якщо замість цього ми придумали код, де не було цієї поганої ситуації де E є префіксом, наприклад, з - Іншими словами, якщо б ми могли переконатися, що моделі як і раніше короткі для популярної літери довго для менш популярних букв, але немає ніякої можливої ​​плутанини? Людина на ім'я Хаффман років тому придумали цю схему називають кодування Хаффмана що насправді використовує одну зі структур даних, ми провели трохи часу на розмови про Минулого тижня, що дерева, бінарні дерева конкретно - Сенс бінарне дерево, що воно має не більше 2 дітей. Вона, може бути, ліва дитини, може бути, прав дитини, от і все. Отже, нехай лише заради обговорення, що хтось хоче, щоб відправити повідомлення який виглядає наступним чином. Це повна маячня, але він складається з As, Bs, Cs, Ds, і Es. І якщо ви насправді підрахувати всі As, Bs, Cs, Ds, і Es , А потім розділити на загальну кількість літер, ця маленька графіка тут говориться, що 45% з букв Es, 20% As, 10% B, і так далі. Отже, іншими словами, припустимо, що лапки тут тільки деякі повідомлення, які ви хочете відправити. Це, виявляється, дурниця просто так ми можемо використовувати як кілька літер наскільки це можливо, але це дійсно так, що E залишається найпопулярнішим, і B і C є найменш популярними, принаймні, з цих 5 букв алфавіту. Так як ми можемо йти про придумують кодування, двійкового кодування, візерунок з 0 і 1 для кожного з цих букв таким чином, що E знаходиться в декількох хвилинах картини і, можливо, B і C є трохи більше моделей, Знову ж таки, ідея в тому, що ми хочемо використовувати меншу кількість біт більшу частину часу і більш біт тільки один раз в той час. За словами кодування Хаффмана, ви можете створити ліс дерев. Там начебто сюжетна лінія тут, що включає в себе дерева, а також процес побудови їх. Давайте почнемо. 

Я пропоную вам почати з цього лісу, так би мовити, з 5 дерев, кожен з яких є досить нерозумно дерева. Дерево складається з всього одного вузла, як представлено тут кругом. Таким чином, кожна з цих речей можуть бути структури C і всередині структури C може бути з плаваючою крапкою являють підрахунку частоти і тоді, можливо, символ являє листі. Так що думаю про цих вузлах, як тільки всі старі структури C, але, на даний момент, більш високий рівень. Це ліси з 5 дерев, кожне з яких є тільки один вузол. Що Хаффман пропонована в тому, що ми починаємо об'єднувати ці дерева , Які мають найменший розраховує частоту в трохи більше дерев , Поєднуючи їх із новим кореневим вузлом. Таким чином, серед букв тут, зверніть увагу, що для зручності я сортував їх зліва направо, хоча це не є строго обов'язковим, і зверніть увагу, що найменше вузлів В даний час 10% і 10%. Так Хаффман запропонував, щоб ми об'єднуємо ці 2 найменше вузлів в нове дерево шляхом введення нового батьківського вузла, а потім дати, що батьки дитини лівому і правому дитини де B довільно лівої і C довільно право. А потім Хаффман Крім того, пропонується Давайте просто думати про лівому дитини В одному з цих дерев завжди, як бути представленим на 0 і право дитини завжди, як бути представленим номером 1. 

Це не має значення, якщо ви переверніть їх так довго, як ви послідовні. Так що тепер у нас є чотири дерева в цьому лісі. І я кажу чотири, тому що зараз дерево зліва - і це не так багато дерева в тому сенсі, що він росте таким чином, це більше схоже на генеалогічне дерево, де зараз 0,2 є свого роду батько двох дітей - Відзначимо, що в батьківський що ми намалювали 0,2. Ми додали частоти відліків двох дітей і з урахуванням нових вузлів загальної суми. Так що тепер ми просто повторити цей процес. Знайти два найменших вузлів, а потім об'єднати їх в нове дерево , А потім повторити процес далі. Зараз у нас є кілька кандидатів, 20%, 15%, а ще 20%. У цьому випадку, ми повинні розірвати зв'язок. Ми можемо робити це довільно. Ми просто повинні робити це постійно. У цьому випадку, я буду йти з довільним один ліворуч, і я тепер об'єднати 20% і 15%, щоб дати мені нових батьків називають 35%, , Лівий дитина 0, чиє право дитини 1, і тепер у нас є тільки три дерева в лісі. Ви, можливо, може бачити, де це відбувається. Якщо ми повторимо це ще пару раз, ми збираємося мати лише одну більше дерев, , Всі ребра якого позначені 0 і 1. Давайте зробимо це знову. 35% кореня, дерева. 20% і 45%, так що ми збираємося об'єднати 35% і 20%. Тепер у нас є це дерево тут. Ми додаємо їх разом, у нас є 55%. Зараз є тільки два дерева в лісі. Ми робимо це в останній раз, і, сподіваюся, математично всі частоти складаються тому що вони повинні, так як ми вирахували їх з самого початку йти, щоб додати до 100%. І тепер у нас є одне дерево. Таким чином, це дерево Хаффмана. Це почасти знадобився час, щоб дістатися на словах, але насправді з циклу або за допомогою рекурсивної функції, можна побудувати цю річ досить швидко. Так що тепер у нас є один новий вузол, і всі ці внутрішні вузли були malloc'd, Імовірно, на цьому шляху. Так що тепер на вершині цього дерева ми маємо 100%, але тепер помічаю у нас є шлях З цього нового пра-пра-пра-прабатьків до всіх пра-пра-пра-внуки всю дорогу на дні, щоб все листя. 

Те, що ми збираємося зробити зараз, це запропонувати, що для того, щоб представляти букву Е, ми будемо просто використовувати номер 1. Чому? Тому що якщо ми пройдемо цей дерева від остаточного корінь вниз до листа відомий як E, ми слідуємо тільки один край, правий край, і це, звичайно, помічені в правому верхньому кутку 1. Таким чином, імплікація тут Хаффман, що кодування E в двійковому повинно бути просто 1. І це біса ефективно. Не можу отримати будь-яку менше, ніж це. З іншого боку, збирається бути представлені, якщо слідувати логіці, тим, що картина біт замість цього? 01. Таким чином, щоб добратися до, ми стартуємо з кореня і йдемо наліво, а потім ми йдемо направо, яка означає, що ми пішли 0, а потім 1. Таким чином, ми будемо представляти листи з малюнком 0 і 1. А тепер помічаю у нас вже є властивість безпосередній декодіруемий що ми не маємо в азбуці Морзе. Хоча обидві ці моделі є досить короткий - Е 1 біт, становить 2 біти - помітите, що вони не можуть бути сплутані одного чи з іншого боку, тому що, якщо ви бачите в 1 це повинно бути E, якщо ви бачите 0, то 1 він, очевидно, повинен бути A. Крім того, що D? 001. Що таке C? 0001. А що таке B? 0000. І знову, тому що всі листи, які ми дбаємо про знаходимося на листках і ніхто з них є свого роду посередниками на шляху від кореня до листа, немає ризику з'єднуючи різні кодування 2 букви " тому що всі ці бітів є детермінованими. 0000 завжди буде B. Там немає вузлів десь посередині, що ви могли сплутати одну літеру за одною. Так що ж мається на увазі тут? 

Найпопулярніший лист - в цьому випадку E - отримав найкоротші кодування, Отримав наступний найкоротший кодування, і B і C, які ми вже знали з самого початку йти було виду найменш популярним на 10% частоту кожного, вони отримали найдовший кодування. І що це означає тепер, що якщо ви хочете відправити повідомлення, яке стиснуте через Інтернет або по електронній пошті і т.п., а не за допомогою стандартного ASCII, ви можете відправити Хаффман закодоване повідомлення згідно з яким, якщо ви хочете відправити лист E, ви посилаєте тільки один біт. Якщо ви хочете відправити, ви посилаєте 2 бітами, 01, замість відправки 8 біт потім ще 8 бітів слідують ще 8 біт і так далі. Але є Гоча тут. Це не досить просто побудувати це дерево, а потім почати передачу від Аліси до Боба коротше бітів, рядок з ASCII, тому що Еліс також повинен повідомити про те, що Боб якщо Боб збирається бути в змозі прочитати її стисненим повідомлення? [Нерозбірливо відповідь студента] >> Що це таке? [Нерозбірливо відповідь студента] >> З чого дерево. Або навіть більш конкретно, то, що ці кодування, тим більше, що під час цієї історії ми прийняли рішення виклику в одній точці. Пам'ятайте, що ми повинні були вибрати довільно між 2 різними вузлами 20%? Так що це не той випадок, Боб, одержувач, може просто відновити дерево на своєму тому що, можливо, він буде створювати дерево трохи відрізняється від Аліси. Крім того, Боб навіть не знаю, що оригінальне повідомлення оскільки єдине, що Аліса посилає його, звичайно, є стислим повідомленні. 

Таким чином, вилов із стисненням, як це, що, так, Аліса може врятувати багато бітів шляхом відправлення 1 для E і 01 і так далі, але вона також повинна повідомити Бобу, що відображення між літерами і біти тому що вони не можуть чітко покладатися тільки на ASCII більше, якщо ми не використовуємо ASCII. Таким чином, вона може або відправити його деревом чи інакше - запишіть його, зберігати його у вигляді двійкових даних або щось подібне до цього - або просто послати йому трохи шпаргалку, файл Excel, який показує відображення. Таким чином, ефективність стиснення дійсно припускає, що повідомлення, які ви відправляєте досить великий, принаймні, середнього, тому що, якщо ви відправляєте супер коротке повідомлення, якщо ви просто хочете відправити повідомлення БАД, які, трапляється, слово, яке ми може означати тут, B-A-D, ви, ймовірно, будете використовувати меншу кількість біт, але заковика в тому, якщо ви також повинні повідомити Бобу, що дерево або те, що ці кодування, ви будете, ймовірно, переважують всі заощадження наявності стисненого речі з самого початку. Так що це дійсно може бути так, що якщо ви спробуєте стисненні навіть з чимось на зразок поштовий індекс або формати файлів ви можете бути знайомі з - досить невеликі файли, навіть порожні файли - Іноді ці файли можуть отримати більше і не менше. Але реально, що відбувається тільки для невеликих розмірів файлу, так що він не збирається робити гігабайт файлів складає 2 Гб; Ми дійсно говоримо байт або просто пару кілобайт. 

Деякі програми, як поштовий досить розумні, щоб розуміти, що, "Ви збираєтеся витратити більше бітів стиснення цього". "Нехай мене не турбують стискаючи його для вас на всіх". Так що це лише один із способів потім стиснути текстовий формат. Ми могли б реалізувати щось подібне в C. Наприклад, ось як ми могли б являти собою вузол в цьому дереві де у нас є символ на символ, плаваючі значення частоти, і, як ми бачили, з іншими нашими структурами даних, 2 покажчики, 1 вліво дитини, 1 вправо, кожний з яких може бути NULL, але якщо ні, це відноситься до лівих дитини та право дитини. Так що ж тоді кодування Хаффмана, і це один із способів, ви можете йти про стиснення інформації, і це, безумовно, одна з найбільш проста в реалізації в контексті, скажімо, дані минулого тижня структур, хоча навіть більш складні алгоритми існують що можна зробити ще більш складною мутації ваших даних. Будь-які питання, то на дерева, бінарні дерева, або стиснення тексту? [Студент] Є деяка двозначність, як якщо б [нерозбірливо] розділилася на 01, то 011 буде неоднозначним, так? [Нерозбірливо] >> Хороше питання. Неоднозначність. Дозвольте мені коротко, посилаючись на це фото тут. Тому що символи, які ви стискаєте, уявлення, за визначенням цього алгоритму завжди залишаються листя, Ви ніколи не будете випадково використовувати ту ж схему біта для префікса кілька букв. Отже, іншими словами, ви стурбовані, схоже, двозначності, що виникають яких 001 може бути початком B або C початку або щось на зразок цього. Але це не може бути так, бо помітили, що всі букви алфавіту ми кодують знаходяться на листі. 

Неоднозначність може виникнути тільки, як і у випадку з азбукою Морзе, Якщо, наприклад, C був десь на шляху від кореня до B. [Студент] Вірно. Так що в цьому випадку, скажімо, з 2 листками. >> Скажіть є - Скажи це ще раз. [Студент] Скажи має 2 листи, F і G, а потім G - >> Добре. Але вона не може. Сама по собі не може мати листя F і G, тому що ці літери F і G б самі бути залишає десь зліва від B або право E. Таким чином, за визначенням, вони повинні бути листям. В іншому випадку, ви абсолютно праві, ми не вирішили проблему, що код Морзе стикається. Хороше питання. Інші питання? Добре. Це поняття біта, виявляється, у нас були владі всі разом, що ми фактично не використовується коли мова йде про маніпулювання ці 0 і 1. Ми запитали про це на одній з перших наборів завдання: а саме, як ви йдете з приводу перетворення великих і малих літер, чи навпаки? Або, більш конкретно, один з тих перших psets запитав скільки біт ви насправді потрібно перевернути, щоб змінити в нижній регістр або навпаки? Ось коротке нагадування того, що 65 і 97 виглядати в двійковому вигляді. І навіть якщо це питання начебто був втрачений у вашій пам'яті, Ви можете побачити тут ще раз, що, скільки біт необхідно перевернути змінити капіталу в нижній регістр? Тільки один. 

Вони відрізняються лише в одному місці, третій біт зліва. У той час як є 010, мало має 011. Так чи інакше, ми повинні просто бути в змозі відобразити, що біт, і ми можемо капіталізувати чи малі літери. Ми зробили це в минулому, фактично використовуючи, якщо умови і перевірки, якщо лист між капіталом і капіталом Z, Потім виходу, як - + 26 або щось на зразок цього. Ви, напевно, зробив арифметичну зміни букви алфавіту. Але що, якщо ми могли б просто переверніть, що один біт? Як ви могли б іти про прийняття вартість одного байта біт, 8 біт, так як 01000001 01100001 і? Якщо у вас ці послідовності бітів, як ми можемо йти про зміну лише одного з них? Що, якщо ми введемо в жовтому ось це іншій структурі біта? Якщо я зроблю все жовті 0s рядки, за винятком одного біта, що я хочу змінити а потім ввести новий оператор відомий як оператор побітового - Побітова в тому сенсі, що вона діє на окремі біти, не на весь байт або чотири байти все відразу. Це вертикальна риса там, у жовтому припускає, що те, що якщо ми візьмемо уявлення капітал і побітове АБО його жовтою послідовність бітів? Іншими словами, думаю, повернемося до нашого обговоренню булевих виразів в подряпин, а потім в C. 

Роблячи логічний або означає, що, щоб бути правдою, або перше, що повинно бути істинним або друга річ повинна бути істинними або обидва вони мають, щоб бути правдою, , А потім отриманий результат є самою правдою. У цьому випадку тут, що ми отримаємо, якщо візьмемо 0 "або" е изд з 0? Помилкові чи ні? Він як і раніше помилковими, так рядкові залишається, як очікувалося. Що, якщо замість цього ми робимо 1 або 0? Це тепер залишається 1, але зауважив, що це має відбутися тут. Якщо ми почнемо з капіталом, і ми продовжуємо "або" її окремі біти, як ми робимо тут, 0 або жовтий дає нам, що тут, унизу? Це дає нам 1. У самому справі, припустимо, що ми не знали, що прописні версія мало насправді. Давайте робити це. Дозвольте мені рухатися назад це тут. Давайте зробимо це знову. 0 або 0 дає мені 0. 1 або 0 дає мені 1. 0 або 1 дає мені 1. 0 або 0 дає мені 0. Наступний 0, наступний дорівнює 0, наступна: 0. 1 або 0 дає мені 1. І тому, навіть якщо ми не знаємо заздалегідь, що нижній регістр був, просто "або" ІНГ з цієї картини біти, які ми представили тут, в жовтих, Ви можете нижній капіталу, клацаючи, що небагато. Ми використовували цей вираз тижнів тому: гортати небагато. Як ви насправді зробити це програмно? Ви можете використовувати те, що зазвичай називають маскою, послідовність бітів, що в цьому випадку відбувається просто так, аби подивитися, як цей номер тут, і тоді ви "або" це разом з використанням цього нового оператора C, Не | |, можна використовувати одне |, і ви б насправді отримати відповідь тут, бо навіщо? Це місце 1s, 2s місце, 4s, 8s, 16s, 32s. Ось і виходить, що якщо взяти великої літери і побітове АБО його з цілими 32, тому що цілими 32, коли ви дивитеся на це як на біти, виглядає так, це означає, що ви можете перевернути біт, що ви дійсно хочете. І точно так само - і ми будемо дивитися на код через хвилину - Припустимо, ми хочемо піти в іншому напрямку. 

Як ви йдете з нижнього регістра в столицю? Який біт необхідно змінити? Це та ж сама. Ми хочемо змінити це третій біт з 1 на 0. І як ми могли б йти про це? Як ми згортаємо трохи? З якою шаблон бітів ми могли вимкнути трохи? Що робити, якщо ми начебто інвертувати маску? Якщо раніше, ми зробили все жовті 0s маски за винятком одного біта ми хотіли включити, Що робити, якщо на цей раз, ми робимо все 1s маска, за винятком небагато, що ми хочемо, щоб вимкнути , А потім використовувати те, що оператор? Що, якщо ми "і" речі? Давайте подивимося. Якщо тепер клацнути на це, припустимо, що я знову створити маску, ось і все 1s за винятком одного біта, що я хочу, щоб вимкнути , А потім замість "або" білими цифрами нагорі з жовтими номерами тут, що, якщо я замість "і" їх разом? Це називається побітового і. Логічно, що це те ж саме, логічне і. Це дає мені 0 і 1 дорівнює 0. Таким чином, помилковою і дійсною є хибним. Правда, і правда, то правда. А ось магія: Справжні і помилкові зараз помилковим, тому ми вимкнений, що небагато. А тепер інша частина історії кілька простий. Тому що інша частина маски 1s, це не має значення те, що цифри в білому. Коли ви "і" щось з правдою, ви не збираєтеся, щоб змінити його значення. Якщо це правда, то залишиться вірним. Якби це була помилкова, вона буде залишатися помилковими. 

Але чарівництво відбувається, коли ви приймаєте те, що було істинним і ви тоді "і" його з помилковою. Це має ефект відключення, що небагато. Таким чином, трохи загадково там. Давайте реально дивитися на код, який може насправді виглядають ще більш загадковим, Але давайте подивимося ось на ToLower. Якщо я дивлюся на ToLower, що йдуть від столиці в нижній регістр, Давайте подивимося, як ми могли б реалізувати цю програму. Ось основні, і він не робить ніяких аргументів командного рядка. Я оголошенні характеру з для письма, які користувач збирається ввести дюйма Потім я використовую знайомі робити під час циклу просто переконайтеся, що користувач виразно дає мені капітал або B або C. .. Z, тому вони дають мені щось між А і Z. А тепер те, що я тут роблю? Я "або" ІНГ це з 0x20, але це насправді так само, як - і ми повернемося до цього в даний момент - 32. Отже, ще раз, 32 ця картина біти тут. Навіщо нам це знати? Просто згадайте тиждень 0. Це місце 1s, 2s місце, 4s, 8s, 16s, 32s місце. Таким чином, це жовтий номер, трапляється, 32. Потім я можу взяти з собою лист, як символ тут, побітове "або" вона буквально з числом 32, і що я повернуся? Рядкові версія, що символ. Хвилину тому, хоча, я висловив це в іншому записі бази. Що це уявляєте? >> [Студент] Шістнадцяткові. [Малан] Це відбувається представляють шістнадцяткові. Ми не говорили про шістнадцятковому все, що багато чого, але насправді це зручно у випадках, подібних до цього. 

Навіть якщо це виглядає більш складною і, хоча вона виглядає як 20, а не 32, Виявляється, що шістнадцяткові насправді супер зручні позначення тому що в шістнадцятковій кожної цифри після 0x - і це нічого не значить; це просто людське угоду, що говорить тут йде шістнадцяткове число - кожна з цих цифр, 2, а потім 0, самі по собі можуть бути представлені рівно з 4 біти. Так що, якщо ми зробимо це, дозвольте мені відкрити текстовий редактор тут - дивне автозаповнення - якщо ми трохи текстовий редактор тут, число 0x20 означає, що тут 4 біт, ось ще 4 біти. Давайте зробимо правий 4 біти в першу чергу. 0, коли представлені 4 біта це що? Супер просто. Просто всі 0s. Так що 4 біти, як 0s. Як ви уявляєте 2? Це був час, так як ми зробили це, але це 0100. Так що це 1s місце, це 2s місце, а потім це не має значення те, що інші місця. Іншими словами, в шістнадцятковому ви могли б сказати 0x20, Але якщо ви потім думати про те, що 2 і як воно представлене в двійковій, що таке 0 і як це представлено в двійковій, Відповіді на ці питання це і це, відповідно. Так відбувається, 0x20, щоб представити цю картину з 8 біт, який якраз і є маскою, яку ми хотіли. Так що це на даний момент просто інтелектуальна вправа, але насправді в коді це зазвичай частіше писати константи, як це в шістнадцятковому, тому що тоді програміст може відносно легко, навіть якщо це вимагає папір і олівець, з'ясувати, що це картина біт тому що ви не можете просто виражати 0 і 1 зазвичай в коді. Ви не можете піти 00010 і так далі. 

Ви повинні вибрати десятковій або шістнадцятковій або вісімковій або інші позначення. Більшість людей схильні вибирати шістнадцятковому просто так, щоб кожна цифра представляє 4 біти і ви можете зробити це швидко математики. І я махаю рукою у ToUpper, що майже те ж саме, він виглядає майже ідентично. ToUpper відбувається використовувати не чи оператор, а цей хлопець і DF. Що DF представляють? DF? Будь? >> [Студент] 255. 255? Не 255. Це було б і далі. Ми залишимо це одне, маленьке вправу. Але якщо ви йдете від 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, а потім те, що приходить після 9? Ми начебто з десяткових цифр, але в шістнадцятковому, що буде після 9? [Студент]. >> Так A, B, C, D. Ви можете з'ясувати звідти те, що картина біт D насправді являє. І якщо ми робимо математику, ми побачимо, що маски в кінцевому підсумку отримати назад ідентично цього. Це F, все 1s, і це р. Так DF заявляє, що маски. Добре. І, нарешті, не робити речей звук супер, супер технічних, але припустимо, що ми хотіли, щоб написати програму, яка це робить. Дозвольте мені піти далі і зробити бінарний, який являє собою програму у файлі з ім'ям binary.c. А тепер дозвольте мені запустити бінарний і дати мені невід'ємне ціле число. Давайте почнемо просто і тип 0. Це зараз це програма, яка виводить ціле число в двійковому представленні. Так що, якщо я граю в цю гру знову і ввести тільки 1, я повинен отримати 32-розрядне представлення 1. Якщо я зроблю це знову 2, я повинен отримати це. Якщо я роблю 7, я повинен отримати кілька 1s в кінці і так далі. Виявляється, я говорю про це, тому що з операції побітового ви реально можете зробити одну річ, як добре. Ви можете створити ці маски динамічно. Погляньте на цей останній приклад з участю бітових операцій. Ось перша частина коду, запитує в користувача число, і він наполягає на тому, що ви даєте мені невід'ємне ціле число. Так що це свого роду старе школи. Але ось те, що начебто цікавий. 

Як я можу йти про друк числа в двійковому? Я вперше ітерації від чого до чого? Який розмір Int зазвичай, принаймні в прилад? >> [Студент] 4. Це 4. Таким чином, 4 * 8 32 - 1, 31. Так що, якщо я починаю рахувати від 31, який представляє, виявляється, тільки концептуально, 31-розрядний або вищого порядку біт, що цей хлопець тут, в той час як це буде біт 0. Так що це біт 01 біт ... 31. Так що цей код робить? Зверніть увагу, це цикл, навіть якщо він виглядає загадковим, просто перебір з 31 до 0. Ось і все. Таким чином, сама цікава частина тепер повинна бути в цих 5 рядків тут. Зверніть увагу, що в цій лінії я оголошенні змінної маски у відповідність з нашою історією цих жовтих номерів. А те, що це робить? Це ще один оператор побітового ми не бачили раніше, швидше за все. Це оператор лівого зсуву. Цей оператор робить це. Ось номер 1, і якщо ви робите я залишив зрушення, зсув вліво, Що ви думаєте, що має ефект робить, щоб, що окремі 1? Буквально зміщення його. Таким чином, якщо число 1 є те, що у вас на лівому, і ви починаєте з ініціалізації я 31, Що це буде робити? Він збирається взяти цей номер 1 і перекласти її 31 місць тут. І тому, що тут немає інших цифр за нею, ті, за замовчуванням буде замінений 0s. Таким чином, ви починаєте з номером 1, який, звичайно, виглядає так - і дозвольте мені зробити це тут, в центрі. І те, як ви переносите речі зліва, цей хлопець по суті йде цим шляхом. Але як тільки ви це зробите, 0 отримує заповнені Якщо перевести його вдруге, він іде цим шляхом і інше 0 отримує заповнені 

Ви перекласти її знову, а потім ще 0 отримує заповнені Так що якщо ви це зробите з 1 << I 31 місць, у результаті ви отримуєте маску , Що становить 32 символів, лівий одним з яких є 1, Все інше з яких 0. А то виходить, як в сторону, переходячи число зліва, як це Також випадково, а іноді і зручно, має ефект робить те, що на цей номер? >> [Студент] Подвоєння його. Подвоєння це, тому що в кожному зі стовпців - 1s місце, 2s місце, 4s місце, 8s місце, 16s місці - вони всі подвоєння, як ви йдете наліво. Або, вірніше, коли ви переносите 1s ви будете в кінцевому підсумку подвоїти вартість номера. Ви можете в кінцевому підсумку робить цікаве перетворення цифр зрушуючи все більш подібним чином за ступенями 2. Так як же це працює? Це і дає мені маску, яка все 0s за винятком 1 в точності місці я хочу, а потім це вислів, який вкрали toupper.c, просто говорить, взяти число п, що користувач ввів в, »І« що з цією маскою, і що ви збираєтеся отримати? Ви збираєтеся отримати 1, якщо є 1 в масках, що місце, або ви збираєтеся отримати 0, якщо це не так. І так все це робить програма ефективно це має петлю, і це створює маску з 1 тут, то 1 тут, то 1 тут, і він використовує це побітове І трюк, щоб сказати, є 1 біт на вході користувачів тут? 

Є 1 біт на вході користувачів тут? І якщо це так, буквально друкувати 1, інакше друк 0. Ми робимо це з цілими тільки тому, що саме тому ми робимо 32 біт замість 8, але те, що ми ввели, то це побітове І це побітове АБО, і цей оператор лівого зсуву, який часто не дуже корисно, але виявляється, що вони можуть бути. У самому справі, якщо б ви були представляти собою щось на зразок масив логічних просто представляють істинне або помилкове, припустимо, ви хотіли, щоб відслідковувати чи ні кімнату, повну 300 студентів присутній, Ви можете оголосити масив розміром 300 типу BOOL, так що ви отримаєте 300 Bools, і ви можете налаштувати кожен істинно, якщо хтось тут і брехня в іншому випадку. Чому це подання в тому, що структура даних неефективна? Що поганого про дизайн, що структура даних, масив з 300 Bools? Що таке логічний, насправді, під капотом? Це, також, є те, що можуть бути не знайомі. Виявляється, немає BOOL. Пам'ятаєте, ми як би створили, що з cs50.h файл, яка сама по собі включає в себе стандартні BOOL. З видом німий, хоча, коли справа доходить до BOOL. Він використовує 8 біт для представлення кожен логічний, який повністю марнотратного тому що очевидно, скільки біт потрібно, щоб представляти логічне? Просто 1. Ось і виходить, що якщо зараз у вас є можливість з операторами побітового маніпулювати окремими бітами навіть в символ, навіть в один байт, Виявляється можна зменшити обсяг пам'яті, необхідний для подання дурість як, що відвідуваність стилі структуру даних в 8 разів. Замість того щоб використовувати вісім бітів являють істинне або помилкове, ви можете буквально використовувати один за допомогою одного байта на кожні вісім учнів у класі і перемикання від 0 до 1 окремі біти за допомогою цих видів низьким рівнем трюків. Це дійсно покласти край енергії. Чи є питання про бітові операції? 

Так. >> [Студент] Чи виняткові або оператор? Так. Існує виняткове або оператор, який виглядає так, ^, морква символ, , Що означає тільки перше або друге може бути 1 на виході буде 1. Існує також немає, ~, яка дозволить вам, щоб інвертувати 0 на 1 або навпаки, а також. І є також оператор зсуву вправо, >>, яка є протилежністю тієї, яку ми бачили. Добре. Давайте речі тепер на більш високий рівень. Ми почали говорити про текст, а потім стиснути його і представляє текст з меншою кількістю біт; Ми трохи поговорили про те, як ми можемо тепер почати маніпуляції речами на рівні Побітового. Давайте тепер масштаб до 10.000 футів, щоб подання більш складні речі, як графіка. Тут ми маємо прапором Німеччини, тут ми маємо одне з Франції. Вони можуть бути представлені у форматах, ви знаєте - GIF-файлів, наприклад. Якщо ви коли-небудь бачили зображення в Інтернеті, які закінчуються на. GIF, Це графічний формат обміну. Ці два прапори тут начебто піддаються стисненню за те, що, можливо, очевидних причин? >> [Нерозбірливо відповідь студента] Там дуже багато повторень, вірно? Для того, щоб відправити прапором Німеччини, думати про це як зображення на екрані назад в дні Scratch. Ви могли б пригадати, що є окремі точки, які складають зображення. 

Там цілий ряд чорних крапок і ще цілого ряду чорних крапок. Там купа рядків чорними крапками, які ми могли бачити, якщо ми дійсно збільшено, багато подобається, коли ми збільшено на обличчі Роба в Photoshop. Як тільки ми отримали все глибше і глибше і глибше в зображенні, Ви почали бачити пікселізация, всі квадрати, які складаються очі в цьому випадку. Те ж тут справа. Якщо ми збільшено зовсім небагато, ви б побачили окремих точок. Ну, це вид відходів біт. Якщо третина прапор чорного і третього прапора жовтий і так далі, чому ми не можемо якимось чином стиснути цей прапор? І навіть французький прапор може бути стиснута, хоча картина трохи інша. Виявляється форматі GIF файлів формат стиснення без втрат, яка означає, що ви можете робити знімки, як німецький прапор тут, Ви можете викинути багато з його бітів без шкоди для якості. Це на відміну від щось подібне JPEG, , З якої більшість з нас, ймовірно, більш знайомі. Facebook фото і Flickr фотографій і т.п. Майже завжди зберігаються як зображення у форматі JPEG, коли вони завантажені, але у форматі JPEG є втратами - втратами - формат якого ви викинули біти але ви також викидають якості. І тому, якщо ви стискати фотографії з Photoshop або завантажити їх на Facebook або взяти їх на дійсно дерьмово телефон, Ви знаєте, що картина починає одержувати дуже плямистим і нерівною, і це тому, що він стискається за допомогою комп'ютера або телефону буквально кидали інформація від готелю. Але GIF дивно в тому, що він може використовувати менше біт, ніж він може за замовчуванням без втрати інформації. 

І вона по суті робить це таким чином. Замість того, щоб зберігати у файлі, як BMP б RGB потрійний для чорного, чорного, чорного, чорного, чорний, чорний, чорний, чорний, чорний, чорний, чорний, чорний і так далі, Швидше за все, формат GIF збирається мовити, "Black" , А потім "Повторіть це 100 разів", або щось на зразок цього. "Чорний повторити це 100 разів, чорний, повторити це 100 разів ..." "Жовтий, повторити це 100 разів." І так він пам'ятає, по суті, ліве пікселів і потім кодує так чи інакше поняття повторював, що піксель знову і знову. Так GIF-файлів можна стиснути себе без втрати інформації. Але якщо у вас здогадатися, якщо це алгоритм, який ГІФС використання, який з цих прапорів, навіть якщо вони виглядають однаковими за розміром, буде менше, якщо зберігається на диску у форматі GIF? >> [Студент] Німеччина. Німеччина буде менше? Чому? [Студент] Оскільки Ви повторюєте це багато, багато разів горизонтально а потім повторити в інший раз. >> Саме так. Тому що люди, які винайшли GIF тільки почасти довільно вирішили , Що повторення будуть використані горизонтально, а не збоку. Там дуже багато більше повторень боків тут в німецький прапор, ніж у французький прапор. Таким чином, якщо ми насправді відкрити папку на жорсткому диску, який має ці GIF, Ви можете фактично бачити, що німецький прапор тут 2 кілобайт і французької становить 4 кілобайти. Це трапляється збіг, що один в два рази більше іншого, але це насправді так, що французький прапор набагато більше. 

Навіть якщо ми говоримо тут про графіку, ті ж ідеї можна застосувати до Не такі речі, як прапори, але образи, які є трохи більш складними. Якщо ви візьмете картину яблуко, безумовно, є багато дублювання там, , Щоб ми могли якось пам'ятати, що за замовчуванням фон синьо а не, як права картина припускає, повинні пам'ятати, колір кожного пікселя в цій картині. Таким чином, ми можемо кинути біт далеко тобто без втрати інформації. Яблуко як і раніше виглядає точно так само. У цьому прикладі, ви можете побачити, що відбувається у фільмі. Вони являють старої школи кінохроніки якого у верхньому зображенні є у вас є RV проїжджав повз будинок і дерево. А що ван проїжджає повз зліва направо, що, очевидно, не змінюється? Будинок нікуди не дінеться, і дерево нікуди не дінеться. Єдине, що рухається є ван в цьому випадку. Так як фон без змін передбачає, що ви можете зробити в кіно Аналогічно просто викинути інформацію, яка не змінюється між кадрами. Це, як правило, відомі як стиснення межкадрового згідно з яким, якщо цей кадр виглядає майже ідентично цього, давайте не будемо турбуватися збереження на диску будь-якого з ідентичною інформації на ці проміжні кадри, давайте використовувати тільки ключові кадри раз в той час що насправді зберігати цю інформацію надлишково так само, як трохи розсудливості перевірити. 

На відміну від інший підхід до стиснення відео в цьому другому і нижній приклад тут, , Де замість магазину 30 кадрів, чому б вам не просто зберігати 15 кадрів в секунду замість? Замість того, щоб фільм виду тече красиво, прекрасно, це може виглядати це заїкання трохи, трохи старої школи, але ефект буде використовувати набагато менше біт, ніж могло б бути необхідним. Так де ж це тоді нам залишається? Це було трохи в стороні від того, де ще ви можете піти зі стиском. Більш детальну інформацію про те, що взяти клас як CS175 тут. Ось ще один приклад в відео. Якщо бджола це єдине, що рухається, Ви дійсно можете викинути інформації в цих середніх кадрах тому що квітка і небо, і листя не змінюється. Але давайте тепер розглянемо одну річ. У наступні 5 хвилин ми залишимо позаду C вічно в лекції? Так. Не в psets, однак. Останній розповідь про С, а потім ми перейдемо до дуже сексуальним матеріалом за участю HTML і веб-і у-у-ух. Добре. Тут ми йдемо. Це мотивація. Виявляється, весь цей час, коли ми були написання програм ми запускаємо Clang. І Clang, ми говорили з першого тижня в значній мірі, бере вихідний код і перетворює його в об'єктний код. Це займе C і перетворює його в 0 і 1. Я начебто лежав до вас протягом декількох тижнів, тому що це не зовсім так просто. 

Там дуже багато більше відбувається під капотом, коли ви запускаєте програму, як Clang. У самому справі, процес компіляції програми дійсно може бути узагальнені, як ви, можливо, пам'ятаєте з відео Роба на компілятори, в ці 4 етапи: попередня обробка, складання себе, збирання та компонування. Але у нас в класі, і більшість людей у ​​світі зазвичай підсумувати всі ці кроки як тільки "компіляції". Але якщо ми почнемо з вихідного коду, як це, нагадаємо це, мабуть, найпростіша програма C ми написали досі, нагадаємо, що при компіляції він закінчується в такому вигляді. Але там насправді проміжний крок, і ці кроки полягають у наступному. По-перше, ця річ на самому верху цього, і більшість наших програм, # Включити <stdio.h> Що # включити зробити для нас? Це в значній мірі копіює і вставляє вміст stdio.h в моєму файлі, так що чому? Чому я дбаю про зміст stdio.h? Що там інтерес? Printf в декларації, його прототип, так що компілятор то знає, що я маю на увазі коли я згадую цю функцію Printf. Таким чином, крок 1 в зборі є попередньої обробки, в результаті чого програми, як Clang або деякі допоміжні програми, яка поставляється з Clang читає ваш код зверху вниз, Зліва направо, і в будь-який момент він бачить символ # слід ключове слово, як включати, він виконує цю операцію, копіювання і вставка в даному випадку stdio.h в ваш файл. Це крок 1. Тоді у вас є набагато більше C файл через величезну копіювати, вставити вакансії, просто так вийшло. 

Крок 2 Тепер це компіляція. Але, виявляється компіляція займає вихідний код, який виглядає наступним чином і перетворює його на щось, що виглядає так, що для тих, хто знайомий називається? >> [Студент] асамблеї. >> Асамблеї мовою. Насправді це щось, якщо ви берете CS61 ви будете занурюватися в більш докладно. Це майже так само близько, як ви можете отримати в письмовому 0 і 1 собі але писати речі таким чином, що все ще змушує принаймні трохи глузду. Ці машинні інструкції, і якщо ми Прокрутіть вниз до основною функцією тут, помітите, що цей поштовх інструкції, переміщати інструкції, відняти навчання, дзвоніть навчання, і так далі. Коли ви чуєте, що ваш комп'ютер Intel Inside, у вас процесор Intel в Mac або PC, що це значить? Процесор вбудований такими компаніями, як Intel розуміння певних інструкцій. Вони поняття не мають, що такі функції, як свопу або основний самі по собі, але вони знають, що дуже низькому рівні інструкцій, як додавання, віднімання, штовхати, перемістити, подзвонити, і так далі,. Таким чином, при компіляції C код на асемблері, ваша дуже зручний вид код перетвориться в щось, що виглядає так, , Що буквально рухається байта або 4 байти навколо в таких невеликих підрозділів і з CPU. Але, нарешті, коли Clang готовий прийняти це подання своєї програми в 0 і 1, то крок називається збірка відбувається, і це знову все відбувається в мить ока при запуску Clang. Ми починаємо тут, вона виводить файл, як це, а потім перетворить його в ці 0 і 1. І якщо ви хочете, щоб повернутися в якийсь момент і насправді побачити це в дії, якщо я йду в hello1.c--це одна з найперших програм, які ми подивилися на - Зазвичай ми будемо компілювати це з Clang hello1.c і це дасть нам a.out. Якщо на відміну від вас, а дати йому-S прапор, що ви отримаєте це hello1.s і ви насправді бачите на асемблері. 

Я роблю це для дуже короткої програми, але якщо ви повернетеся на Scramble або відновити або будь-яку програму, ви написали і просто з цікавості хочу подивитися, що це насправді схоже, що насправді годують в CPU, Ви можете використовувати це-S прапор з Clang. Але потім, нарешті, є ще один глюк. Тут 0 і 1, які представляють моєї реалізації Здрастуй, світ. Але я використовував чужу функцію в моїй програмі. Так що, хоча процес був я беру hello.c, він компілюється в код збірки, а потім вона буде збиратися в 0 і 1, тільки 0 і 1, які виводяться на даний момент ті, що в результаті мого коду. Але чоловік, який написав Printf, вони склали свій код 20 років тому і вона тепер встановлено десь на прилад, так що ми якимсь чином повинні об'єднати свої 0 і 1 з моїми 0 і 1, і це підводить нас до 4-ї і заключний етап компіляції, відомі як посилання. Таким чином, на лівій стороні у нас є точно така ж картина, як раніше: hello.c стає збірки коду стає 0 і 1. Але пам'ятайте, що я використовував стандартні бібліотеки вводу / виводу в мій код, і це означає, що десь на комп'ютері є файл під назвою stdio.c або принаймні скомпільовані версії їх тому, що хтось кілька років тому складений stdio.c в асемблерний код, а потім цілий букет з 0 і 1. Це те, що відомо як статична чи динамічна бібліотека. Це якийсь файл сидить десь в прилад. 

Але, нарешті, я повинен взяти мою 0 і 1, і що людина 0 і 1 і якимось чином зв'язати їх разом, буквально об'єднати ці 0 і 1 в єдиний файл з ім'ям a.out або hello1 або те, що я назвав свою програму так що кінцевий результат має всі 1 і 0, які повинні скласти свою програму. Так що весь цей час у цьому семестрі, коли ви використовуєте Clang і ще недавно запущених зробити для того, щоб запустити Clang, Всі ці кроки були відбувалося роду миттєво, а цілком свідомо. І тому, якщо ви продовжувати в інформатиці, а саме CS61, це шар, який ви будете продовжувати відігніть геть там говорити про ефективність, безпеку, наслідки, і як ці деталі нижнього рівня. Але разом з тим, ми збиралися йти C позаду. Давайте йти вперед і приймати наш 5-хвилинну перерву зараз, і коли ми повертаємося: в інтернеті. Добре. Ми повернулися. Зараз ми починаємо наш погляд не тільки на HTML, тому що, як ви побачите, HTML себе насправді досить проста але насправді на веб-програмування в цілому, мережі в цілому, і як всі ці технології об'єднуються щоб дозволити нам створювати більш складні програми поверх Інтернету ніж досі ми змогли в цих чорно-білих вікон. Дійсно, на даний момент в семестр, хоча ми будемо витрачати менше часу щодо на PHP, HTML, CSS, JavaScript, SQL і більше, більшість студентів роблять в кінцевому підсумку робить остаточні проекти, які веб- тому що, як ви побачите, фон тепер у вас є в C дуже застосовні до цих мов високого рівня. 

І, як ви починаєте думати про своє остаточне проекті, який, так само, як питання, поставлене 0, де ви були заохочені робити самому нічого цікавого для вас в Scratch, Остаточний проект це ваша можливість прийняти ваші нові знання і кмітливість з C або PHP або JavaScript, або як з за спин і створити свій власний шматок програмного забезпечення для світу, щоб бачити. І насіння вам ідеї, знайте, що ви можете очолити тут, projects.cs50.net. Кожен рік ми вимагати ідей від співробітників та викладачів і студентських груп на території кампуса просто представити свої ідеї для цікавих речей, які можуть бути вирішені за допомогою комп'ютерів, використання веб-сайтів, за допомогою програмного забезпечення. Так що, якщо ви боретеся, щоб придумати ідею самостійно, всіма засобами прокрутки ідеї є з цього року і останній. Це абсолютно нормально для вирішення проекту, які були вирішені раніше. Ми бачили багато додатків для бачивши стан пральні на території кампусу, багато додатків для навігації по меню їдальні, багато додатків для навігації по каталогу курсів тощо. І дійсно, в майбутньої лекції та семінари в майбутньому, Ми познайомимо вас з деякими загальнодоступних API, як комерційно доступні а також тут можна отримати CS50 на території кампусу, так що у вас є доступ до даних і може робити цікаві речі з ним. Так що більше на остаточне проекти в кілька днів, коли ми випускаємо специфікації, але зараз, знаю, що ви можете працювати поодинці або з одним або двома друзями на більшості проектів, що представляють інтерес для вас. Інтернет. Ви йдете вперед і витягніть ваш ноутбук, ви йдете в facebook.com вперше, те, що не увійшли останнім часом, і натисніть Enter. Що саме відбувається? 

Коли ви натиснете Enter на вашому комп'ютері, цілу купу кроків почати роду чарівним відбувається. Таким чином, ви тут, на лівому, веб-сервер, як Facebook тут справа, і якось ви використовуєте цю мову називається HTTP, протокол передачі гіпертексту. HTTP не є мовою програмування. Це скоріше протокол. Він являє собою набір конвенцій, веб-браузери і веб-сервери використовують, коли сполучені. А що це означає наступне. Багато чого, як в реальному світі, у нас є ці конвенції де, якщо ви зустрітися з деякими людини в перший раз, якщо ви не заперечуєте, посміюючись мене тут, Я міг би підійти до вас, кажете: "Привіт, мене звуть Девід». >> Привіт, Девід. Мене звати Семмі. "Привіт, Девід. Мене звати Семмі". Так що тепер ми тільки що займалися такого роду дурні людські протоколу де я ініціював протокол, Семмі відповів, Ми потиснув руку, і угода буде завершена. HTTP дуже схожі по духу. Коли ваші запити веб-браузера www.facebook.com, що ваш браузер насправді робить розширює свою руку, так би мовити, до сервера і посилає йому повідомлення. І це повідомлення, як правило, щось на зразок Get - що ви хочете отримати? - зрозумійте мене головна сторінка, яка звичайно позначається косою рисою в кінці URL-адреси. І тільки так ви знаєте на якій мові я говорю, я маю в браузері збираюся розповісти вам, що я говорю HTTP версії 1.1, А також для хорошої заходом, я збираюся розповісти вам, що господар, що я хочу на головну сторінку є facebook.com. Як правило, веб-браузер, непомітно для вас, людини, посилає це повідомлення в Інтернеті, коли ви просто вводите www.facebook.com, 

Вкажіть, у Вашому браузері. І що Facebook відповість? Він реагує з деякими подібний вид загадкові деталі, але і багато іншого. Дозвольте мені йти вперед на головну сторінку Facebook тут. Це екран, що більшість з нас, ймовірно, ніколи не побачити, якщо ви залишатися в системі весь час, але це дійсно їх домашню сторінку. Якщо ми зробимо це в Chrome, помітили, що ви можете підтягти ці маленькі контекстні меню. Використання Chrome, чи то на Mac OS, Windows, Linux і т.п., Якщо ви контролюєте миші або клацніть лівою кнопкою миші, як правило, можна підтягнути меню, яке виглядає так, де чекають кілька варіантів, один з яких є подання джерела сторінку. Ви також можете зазвичай отримують на ці речі, перейшовши в меню Вид і колупатися. Наприклад, тут, під View, розробника одне і те ж. Я збираюся йти вперед і дивитися на View Source сторінку. Те, що ви бачите, HTML, що Марк написав для представлення facebook.com. Це повний бардак, але ми побачимо, що це робить трохи більше сенсу незабаром. Але є деякі моделі тут. Дозвольте мені прокрутіть униз, щоб речі, як це. Це важко для людини, щоб читати, але зауважив, що є ця модель кутові дужки з ключовими словами, як варіант, ключові слова, як цінність, деякі лапках. Це де, коли ви зареєструвалися в перший раз, уточнив, що ваше народження році. Це випадаюче меню народження роки якось закодовані тут У цій мові називається HTML, мова гіпертекстової розмітки. Іншими словами, коли ваш браузер запитує веб-сторінку, вона говорить ця конвенція називається HTTP. Але що ж facebook.com відповісти на цей запит? 

Він реагує з деякими з цих загадкових повідомлень, як ми побачимо через мить. Але більшу частину своєї відповіді у вигляді HTML, мова гіпертекстової розмітки. Це фактично мову, на якому веб-сторінка написана. І те, що веб-браузер дійсно тобто, при отриманні щось на зразок цього, читає її зверху вниз, зліва направо, і в будь-який момент він бачить одну з цих кутових дужках слід ключове слово, як варіант, він показує, що мова розмітки відповідним чином. У цьому випадку він буде відображати меню, що випадає років. Але знову ж, це повний бардак на що подивитися. Це не тому, що розробники Facebook проявляються 0, 5 для стилю, наприклад. Це відбувається тому, що більша частина коду, що вони пишуть, насправді, написано гарно, добре прокоментований, красиво відступом, тощо, але, звичайно, машин, комп'ютерів, браузерів дійсно не наплювати Чи ваш код і стилі. І справді, це абсолютно марнотратно вдарив клавішу табуляції все ті часи і поставити коментарів протягом всього вашого коду і вибрати дійсно описові імена змінних тому що, якщо браузер не хвилює, все, що ви робите в кінці робочого дня витрачає байт. 

Ось і виходить, що більшість веб-сайтів зробити, це, навіть якщо вихідний код для facebook.com, для cs50.net і всі ці інші сайти в Інтернеті , Як правило, добре написана і добре прокоментований і приємно відступ і т.п., Зазвичай, перш ніж покласти сайт в Інтернет, код зменшена, якої HTML і CSS - щось ще, що ми скоро побачимо - Код JavaScript ми скоро побачимо стискається, якої довгих імен змінних стати X, У і Z, і все це прогалина, яка робить все виглядає так читається все це викидати, тому що, якщо ви думаєте про це так, Facebook отримує млрд звернень до сторінки на день - щось божевільний, як що - так що, якщо програміст просто бути анальний натисніть пробіл одне додаткове час, просто для відступу деякі рядки коду все настільки більше? Що мається на увазі якщо Facebook зберігається, що прогалини У всіх байтів вони відправляють назад в людей в Інтернеті? Натискання клавіші пробілу раз дає вам додатковий байт у файлі. І якщо мільярда чоловік потім перейти до завантаження домашньої сторінки в той день, наскільки більше даних ви передаються через Інтернет? Gigabyte без поважної причини. І експлуатацію, для багатьох веб-сайтах, це не така масштабованої питання, але для Facebook, для Google, для деяких з найбільш популярних веб-сайтів є великий стимул фінансово щоб зробити ваш код виглядає як безлад так що ви будете використовувати як кілька байт, як можливо у додаток до потім стиснути його використовуючи щось на зразок блискавки, алгоритм, званий GZIP, , Що браузер автоматично. Але це жахливо. Ми ніколи не дізнаємося нічого про сайтах інших людей, і, як проектувати веб-сторінок якщо ми повинні дивитися на це так. 

Так що, на щастя, браузери, такі як Chrome і IE і Firefox в ці дні як правило, мають вбудовані інструменти розробника. У самому справі, якщо я йду сюди, щоб огляд елементів або якщо я йду, щоб подивитися, розробників, і перейдіть до Інструменти розробника явно, це вікно в нижній частині екрана тепер моя спливає. Це трохи лякає спочатку, тому що там багато незнайомих вкладки тут, але якщо я натискаю на елементи на всьому шляху в лівому нижньому, Chrome, очевидно, дуже розумний. Він знає, як інтерпретувати весь цей код. І те, що Chrome робить це очищає всі HTML Facebook. Навіть якщо там не прогалини там, не відступу там, Зараз помічаю, що я можу почати навігацію цій веб-сторінці, тим більше ієрархічно. Виходить, що кожна веб-сторінка написана на мові називається HTML5 повинні почати з цього, ця декларація DOCTYPE, так би мовити: <! DOCTYPE HTML> Це свого роду світлом і сірий там, але це найперша рядок коду в цьому файлі, і що саме говорить браузеру, "Гей, ось деякі HTML5. от веб-сторінку". Перша відкрита дужка крім того, трапляється, ця річ, відкриває дужка HTML тегів, , А потім, якщо я пірнути в глибокі - ці стрілки абсолютно безглуздо; вони тільки заради презентації, вони не є насправді у файлі - помітите, що всередині HTML тега Facebook, все, що починається з відкриваючої дужки а потім слово називається міткою. Таким чином, усередині тега HTML-видимому, є тег голови і тіла тега. Усередині голови теги тепер весь безлад на Facebook тому що у них багато метадані та інші речі для маркетингу і реклами. 

Але якщо ми прокрутити вниз, вниз, вниз, вниз, давайте подивимося, де він знаходиться. Ось він. Це одна принаймні трохи знайомі. Назва головної сторінки Facebook, якщо ви подивитеся на вкладці в рядку заголовка, є Ласкаво просимо на Facebook - Увійдіть, Зареєструватися або дізнатися більше. Ось те, що ви бачите у заголовку Chrome, і ось як це представлено в коді. Якщо ми будемо ігнорувати все інше в голові, велика частина кишки веб-сторінка знаходиться в тілі, і виходить, що код Facebook, буде виглядати більш складними ніж більшість речей, які ми напишемо спочатку тільки тому, що вона була побудована на протязі багатьох років, але є багато сценаріїв теги, JavaScript код, , Що робить сайт дуже інтерактивним: бачачи поновлення статусу миттєво використанні мов, таких як JavaScript. Там-то називається справ, яка є підрозділом сторінку. Але перш ніж ми перейдемо до цього подробиці, давайте спробуємо, щоб зменшити масштаб і подивимося на просту версію Facebook 1.0, так би мовити. Ось Здрастуй, світ веб-сторінок. Він має, що DOCTYPE декларації на самому верху який трохи відрізняється від всього іншого. Нічого іншого ми пишемо на веб-сторінці буде починатися з <! винятком того, що лінія є і, за винятком так званих коментарі в HTML. Але по більшій частині, всі в веб-сторінка відкрита кронштейн, ключове слово, закриває дужка. 

У цьому випадку можна побачити найпростіші веб-сторінок можливо. HTML тегів містить головою теги і містить тіло тега, але зверніть увагу, що є таке поняття запуску і зупинки тегами. Це початок тега HTML, це закриває тег або закриває тега. Зверніть увагу, що вони начебто протилежності в тому сенсі, що закриває тег або закриваючий тег Чи має це косу риску всередині себе. Між тим, є відкриті теги голову тут і закриваючий тег голову тут. 

Там у відкриту назву і закриваючий тег назви тут. Той факт, що я поклав книгу на одній лінії, чисто умовно. Він просто дивився, як вона буде поміщається на одному рядку, тому я не став удару Введіть пару раз. Тим часом, тіло, я зробив відступ просто бути ніколи так ясно. Зверніть увагу, що HTML є досить дурним язиком. У самому справі, ще в день до появи WYSIWYG редакторів і Microsoft Word, де ви можете сказати: "Зробіть це сміливе, зробити це курсив," ви насправді введіть мало команд в нарисах 20 + років тому , В якому ви сказали б, "Почніть робити цього тексту напівжирним шрифтом. Припиніть робити цього тексту напівжирним". "Почніть робити цього тексту курсивом. Припиніть робити цього тексту курсивом". 

Це те, що HTML або будь-який інший мову розмітки. Це перший тег говорить: "Гей, браузером. Ось деякі HTML." Наступний тег говорить: "Гей, браузером. Ось голова, заголовок моєї веб-сторінки." "Гей, браузером. Ось титул". А потім сюди: "Ей, браузер. Ось саме за титул". Так що це, як браузер знає, більше не буде відображати більше символів, ніж Здрастуй, світ! У рядку заголовка. Між тим, ця говорить: "Ось і все на голову". Це каже: "Ось йде тіло Ось реальне тіло." - Буквально, слова Hello, World. І це говорить тут: "Ось це для тіла. Ось саме для HTML." Так браузерів досить безглуздо. Вони тільки що прочитали цей матеріал зверху вниз, зліва направо, і робити саме те, що вони говорять. Давайте насправді зробити невеличкий приклад. Дозвольте мені відкрити найпростіших програм на моєму Mac тут, а саме TextEdit. У Windows можна використовувати Notepad.exe. Але це все, що потрібно, щоб почати заробляти веб-сторінок. Я збираюся йти вперед і просто скопіювати і вставити цей код в цей файл. Я збираюся йти вперед і зберегти його на моєму робочому столі, і я хочу зберегти це як hello.html, і тепер файл з ім'ям hello.html. Ось він на моєму робочому столі. А тепер дозвольте мені перейти в браузері і перетягнути файл в браузері. І вуаля, ось мій найперший веб-сторінки. Зверніть увагу, що назви вкладки Привіт, світ в тег заголовка, і зауважте, що Здрастуй, світ є тіло моє веб-сторінки, і у-у-ух, я в Інтернеті. 

Я не дійсно, мають рацію, тому що цей файл не в інтернеті. Це трапляється, на мій локальний жорсткий диск в даний конкретний шлях. Але ідея та ж. Все, що нам зараз потрібно, це веб-сервер, до якого, щоб завантажити його. Але спочатку давайте насправді ввести трохи більш складний і трохи більше стилізації. Це просто, якщо нудно, веб-сторінки. Виявляється, є й інші типи теги ми можемо використовувати. Наприклад, тут, в жовтому Я представив 2 нових тегів. Ми не будемо грати багато з цим сьогодні, але зауважив, що посилання тега якось зовні відрізняється від всього іншого. Посилання теги бере те, що називають атрибутами, і атрибутом є те, що змінює поведінку тега. В даному випадку це не кращий вибір імен, посилання, тому що це частково безглуздо, але ця посилання тег говорить, по суті, включає файл під назвою styles.css всередині моєї веб-сторінці. Ви можете думати про це як аналогічний C # включає в директиві. Styles.css має на увазі іншої мови взагалі, що ми не будемо грати з сьогоднішнього дня, але це для естетики: розміри шрифту, кольори, відступи, відступи, поля і все таке докладніше естетики. Між тим, тег функціонально схожі, Але замість того, включають CSS, що мова, він включає в себе іншу мову, JavaScript. Отже, іншими словами, з цими 2 теги я в кінцевому підсумку буде можливість написати свою власну веб-сторінку але і тягнути в код, що я чи хтось інший написав так що ми можемо стояти на плечі інших людей, ми можемо практикувати хороший дизайн, винесення загального коду. Якщо у мене є 10 різних веб-сторінок, це означає, що деякі з моїх естетика можна винести, дуже схожий на № включають в окремий файл. Таким чином, ми як туди добратися. Але давайте насправді спочатку зробити щось більш цікаве з цим файлом. 

Знову ж таки, це тільки TextEdit. Я технічно не в Інтернеті, але ми доберемося туди. Я хотів би зробити Привіт, світ трохи сміливіше, ніж він є. Так що привіт, давай як завгодно говорити <b> для сміливих. Знову ж таки, історія та ж: Привіт, кома, почати робити це сміливий, тоді світ стає жирним шрифтом, а це значить зупинити друк цьому жирним шрифтом. Дозвольте мені йти вперед і зберегти свій файл, поверніться до Chrome, я буду збільшення саме так ми бачимо це краще, і перезавантажити, і ви побачите, що світ зараз жирним шрифтом. Веб це все про гіперпосилання, так що давайте йти вперед і робити це: мій улюблений сайт, скажімо, youtube.com. Зберегти, перезавантажити. Добре. Там є пара проблем в даний час, крім неподобства на сайті. 1, я впевнений, я вдарив Введіть тут. І я зробив. Я не тільки вдарив Enter, я також відступи, практикуючи те, що ми проповідували про стилі, але мої знаходиться поряд з миром. Так чому ж це? Браузери тільки те, що ви говорите їм зробити. Я не сказав браузера, "Break ліній тут. Вставте абзацу тут". Таким чином, браузер, це не має значення, якщо я вдарив Повернення в 30 разів, він як і раніше збирається поставити мою поруч зі світом. Що мені дійсно потрібно зробити, тут сказати щось подібне <br/>, вставити розрив рядка. 

А насправді, розрив рядка це свого роду дивні речі тому що ви не можете дійсно почати переїзд в інше лінії, то щось зробити, а потім зупинити перехід на новий рядок. Це свого роду атомарні операції. Ви або робити це чи ні. Ви потрапили Введіть чи ні. Так бр трохи інший тег, і тому мені потрібно розібратися як відкрити і закрити його все відразу. Синтаксис, що це. Технічно, ви могли б зробити щось на зразок цього в деяких версіях HTML, Але це просто нерозумно, тому що немає ніяких причин для запуску і зупинки щось якщо ви можете замість цього зробити все відразу. Зрозумійте, що HTML5 не строго вимагає цього чорта, так що ви побачите підручники та інтернет-ресурси, які не мають його, але для хорошої заходом давайте практикувати симетрії, які ми бачили дотепер. Це означає, що тег є як відкриваються і закриваються. Так що тепер дозвольте мені зберегти мою справу, повернутися сюди. Так, це починає виглядати краще, за винятком Web я знаю, це свого роду інтерактивним, і все ж YouTube тут, здається, не приведе ні до чого. Це тому, що, хоча вона виглядає як посилання, браузер не знає, що саме по собі, так що я повинен сказати браузеру, що це посилання. 

Способом зробити це є використання тега: <A HREF для гіпер посиланням, яка є старої школи говорити засланні, = "Http :/ / www.youtube.com"> і дозвольте мені перемістити це нова лінія просто так, це трохи більш читабельним, і я буду скорочувати розмір шрифту. Чи можу я зробити ще? Ні. Там збирається бути ця дихотомія. Цей тег, тег прив'язки, дійсно має атрибут, які змінюють його поведінку, і значення цього атрибута мабуть URL YouTube. Але зверніть увагу на те, що дихотомія тільки тому, що це URL ви збираєтеся, це не означає, що має бути слово, яке ви підкреслення і робить посилання. Швидше за все, що може бути щось на зразок цього. Таким чином, я повинен сказати, припинити це слово гіперпосилання за допомогою закриває тега якір. Зверніть увагу, що я не роблю цього. 1, це буде просто трата часу кожного, і в цьому немає необхідності. 

Щоб закрити тег, ви тільки згадати ім'я тега знову. Ви не говорячи вже про будь-якому з атрибутів. Так що давайте економити, що повернуся. Добре, вуаля, тепер це синій та гіперпосиланнями. Якщо я натискаю, я насправді піти в YouTube. Тому, навіть якщо мій веб-сторінки не в інтернеті, це принаймні HTML, і якщо ми дозволимо Інтернет наздоганяти, ми насправді в кінцевому підсумку тут на youtube.com. І я можу повернутися і ось мої веб-сторінки. Але зверніть увагу на це. Якщо ви коли-небудь отримав спам або фішинг-атакою, Тепер у вас є можливість уже через п'ять хвилин, щоб зробити те ж саме. Ми можемо піти сюди і зробити щось подібне www.badguy.com або що уривчасті сайт, а потім ви можете сказати підтвердити свій PayPal акаунт. [Сміється] І тепер це буде йти в badguy.com, який я не збираюся натиснути на тому що я поняття не маю, що призводить. [Сміх] 

Але тепер у нас є можливість насправді в кінцевому підсумку там. Таким чином, ми дійсно тільки починає дряпати поверхню. Ми не програмування як такого, ми пишемо мовою розмітки. Але як тільки ми округляємо нашу лексику в HTML, ми введемо PHP, фактично мова програмування , Що дозволить нам генерувати HTML автоматично генерувати CSS автоматично, так що ми можемо почати в середу для реалізації, скажімо, нашої власної пошукової системи і багато іншого. Але про це протягом декількох днів. Ми побачимося. 

[CS50.TV]