CS50 на русском 2016 Основы программирования (часть 1)
Часть 1 - Часть 2
Неделя 0 курса Гарвардского университета по основам программирования CS50 2016 года на русском языке начинается с рассмотрения графического языка. Это язык Scratch (Скретч). Графический язык, который создан сотрудниками Массачусетского технологического института.
0:04:06 - двоичная система исчисления
0:10:01 - как перевести числа из десятичной в двоичную систему исчисления
0:12:24 - как компьютер запоминает буквы, цвета и изображения
0:16:12 - как в три действия сосчитать всех студентов в классе
0:22:11 - как в три действия найти человека в телефонной книге из 1000 страниц
0:30:50 - что нового в курсе CS50 2016 года
0:47:20 - графический язык Scratch (Скретч)
0:52:29 - играем в игру Oscartime
0:56:31 - создание первой программы в Scratch (Скретч)
Этот курс нацелен на тех, кто в раздумьях над тем с чего начать изучать программирование. Этот курс приобрел популярность во всем мире благодаря кропотливому и упорному труду команды CS50 Гарвардского университета. А это более, чем 100 человек во главе с талантливым оратором и преподавателем, профессором Дэвидом Мэлэном. Почему легко начать изучать программирование с курса CS50? Потому что вся информация преподается простым и понятным языком, а манера преподавания отличается от постсоветских ВУЗов настолько, что курс больше похож на тренинг, нежели на университетскую лекцию.
Почему Неделя 0?
Это старт курса Гарвардского университета по основам программирования CS50 на русском языке 2016 года. Почему неделя 0? - спросите вы меня. Все очень просто. Программисты начинают считать не с 1, как все остальные люди, а с 0. Именно поэтому курс CS50 начинается с недели 0. Если немного отклониться в сторону, то каждый человек начинает свой жизненный путь, свое дело, именно с 0, а не с единицы, так что начать изучать программирование предстоит именно с Недели 0.
На Неделе 0 вы узнаете чем отличается компьютер от человека, какую систему исчисления он использует и как ее преобразовать в десятичную систему исчисления, столь привычную для людей. Каким образом компьютеру удается представлять и запоминать не только цифры, но и буквы, цвета, изображения и даже видео.
Как быстро посчитать людей в большой аудитории и почему Scratch (Скретч)?
После этого Вас ждет разминка в виде задачки, в которой требуется найти в телефонном справочнике на 1000 страниц некого Майка Смитта. Но ценность задачи не просто в том, чтобы найти Майка Смитта, ведь все знают как это сделать, а в том, чтобы сделать это максимально быстро и эффективно. Профессор Дэвид Мэлэн расскажет Вам, как, используя простой алгоритм, другими словами, инструкцию, найти очень быстро человека в телефонной книге. Более того, алгоритм настолько универсальный, что позволяет быстро найти человека в телефонном справочнике, что даже справочник в 4 млрд страниц не является проблемой. Этот же алгоритм будет использован для подсчета количества людей в огромной аудитории.
Первым языком программирования, который Вы изучите в ходе курса, будет графический язык Scratch (Скретч). Он позволяет в буквальном смысле слова создать программу просто перетаскивая кусочки головоломки и объединяя их между собой. Это похоже больше на игру, нежели на программирование. Язык Scratch (Скретч) настолько разнообразен, что позволяет создать аналог популярной игры Pokemon GO, просто перетаскивая и объединяя блоки головоломки.
Простота и богатый функционал графического языка Scratch (Скретч) сделали его очень популярным не только среди детей и студентов, но и среди взрослых.
Логичным продолжением примеров, рассмотренных в ходе лекции Недели 0, является практическая часть, а точнее пошаговое руководство или уроки Scratch для начинающих. В практических уроках по Scratch сотрудники курса CS50 шаг за шагом расскажут о том, как работает программа от друзей из Массачусетского технологического института. Вы научитесь создавать свои собственные программы. Однако Вы не будете кодить, Вы будете просто перетаскивать соответствующие блоки, объединять их с другими блоками, использовать переменные, логические выражения, циклы и т.д.
Кроме того, существует также ресурс Code.org, который, подобно Scratch (Скретч), позволит в игровой манере постичь азы программирования. Преимуществом вышеуказанного ресурса является обучение не только на английском языке, но и возможность выбора русского языка в качестве основного.
Почему CS50?
Первая лекция курса очень многообещающая и абсолютно разрушает стереотип на счет сложности программирования. Все подается в игровой форме. Где бы Вас еще преподаватель попросил поиграть в свое первое домашнее задание? Согласитесь, это вызывает интерес и сводит на ноль фобию сложности программирования, ведь ключик именно в том, чтобы делать маленькие детские шажки, постепенно приближаясь к своей цели. Это можно сравнить с тем, как человек заходит в воду, шаг за шагом смачивая каждый миллиметр своего тела и в конце-концов получает удовольствие от полного погружения.
Практическая часть курса представляет собой практические занятия, так называемые Problem Sets, пошаговое руководство и «шоты» - коротенькие видеообзоры определенной узконаправленной темы. Практические занятия являются логичным дополнением курса лекций CS50 на русском, а конкретно этот пост относится к практическому занятию к лекции Недели 0, посвященной языку Scratch. Это своего рода уроки Scratch для начинающих.
Словарь практического занятия Scratch
Motion - движение
Look - вид
Sound - звук
Pen - ручка
Data - данные
Event - событие
Control - контроль
Sensing - ощущение
Operators - операторы
Costumes - костюмы
Sounds - звуки
to Move - двигаться
to Play - играть
to Change - менять
to Set - установить
Score - счет
Space - пробел
Key - клавиша
Forever - навсегда
Repeat - повтор
Until - до тех пор
Global - глобальный
Local - локальный
Behave - поведение
Receive - получать
Broadcast - трансляция
Edge - край
Bounce - отскок
Glide - скольжение
Touch - касание
Первые уроки Scratch для начинающих
Переходим по адресу https://scratch.mit.edu/ и мы попадаем на сайт. Для перехода непосредственно в интерфейс программы, мы можем нажать на оранжевого кота «попробовать». Кроме того, справа есть видео по работе со Scratch.
Итак, мы попадаем в интерфейс программы и видим слева рабочее пространство stage, о котором говорила Замайла в видео. Также мы видим наш первый спрайт оранжевого кота, который является спрайтом по умолчанию. При движении курсора мыши по рабочему пространству в нижнем правом углу меняются координаты x и y, что позволяет определить текущие координаты курсора мыши.
В центральной консоли расположены блоки. Блоки распределены по разделам:
* Движение
* Внешность
* Звук
* Перо
* Данные
* События
* Управление
* Сенсоры
* Операторы
* Другие блоки
Кроме того, на центральной консоли есть 3 вкладки: скрипты, костюмы, звуки.
Любая программа Scratch начинается с блока из раздела «События», который называется «когда щелкнут по зеленому флагу». Это строительный блок, который будет встречаться чаще всего в Ваших программах, так как без него не будет работать ни одна программа.
Среди основных блоков можно выделить блоки действий, блоки логических выражений, блоки условий, блоки циклов, блоки переменных, блоки событий.
Блоки действий
Блоки действий находятся в разделах «Движение», «Внешность», «Звук», «Перо».
Блоки условий и циклов
Находятся в разделе «События». Вы можете также обратить внимание, что некоторые блоки содержат заполнители такой же формы, как блоки, которые могут быть вставлены в них.
Наш первый урок Scratch.
Давайте сделаем нашу первую программу самостоятельно. Например, воспользуемся исходным спрайтом, изменим его костюм, чтобы он был в движении, а при наведении курсора мыши на кота, кот будет останавливаться. Когда вы убираете курсор мыши - кот продолжит движение. Итак, как же будет выглядеть наша первая программа? Какими строительными блоками мы воспользуемся? Попробуйте самостоятельно сделать эту программу.
Получилось? В качестве бонуса сыграйте в игру от Гарвардского университета.
https://scratch.mit.edu/projects/12352154/
На Неделе 1 профессор Дэвид Мэлэн проведет аналогию между графическим языком Scratch и низкоуровневым языком программирования C. Фактически все программы, реализованные на языке Scratch на Неделе 0, будут реализованы используя язык программирования C.
0:01:12 - графический язык Scratch и язык программирования C
0:14:10 - описание библиотеки CS50 IDE
0:16:39 - написание первой программы на языке С
0:28:50 - основные функции CS50 IDE
0:35:07 - какую стратегию следует использовать для поиска и устранения ошибок в коде
0:47:58 - как компьютеры округляют числа
0:54:49 - типы данных в языке С
0:55:51 - сколько памяти занимает каждый из типов данных
1:01:48 - какое максимальное число может представить компьютер
1:08:37 - ошибки в играх Lego Star Wars и Civilization
1:10:32 - ошибки в программном обеспечении самолетов Boeing
1:13:54 - как возникают ошибки из-за округления чисел компьютером
1:19:01 - взрыв ракеты Arian 5 и трагедия в Персидском заливе из-за ошибки в программном обеспечении ПВО Патриот
1:30:17 - написание программ на языке программирования С
Язык программирования C и «привет, мир»!
Фраза «Привет, мир!» без преувеличения является легендарной, ведь это первая фраза, с которой сталкивается практически каждый человек, желающий изучать программирование. Она стала настолько популярной, что используется практически в любом языке программирования. Это, по сути, первая программа, в которой рассматривается базовый синтаксис языка. Язык программирования C не является исключением, поэтому его рассмотрение начинается именно с этой фразы.
Поиск ошибки в коде или «детские» шаги?
Программирование неразрывно связано с наличием ошибок, так называемых «багов», которые постоянно приходится «фиксить» или устранять. Даже самая простая программа, состоящая всего из 6 строк кода может привести 10 строкам ошибок. Естественно, это вызывает разочарование у начинающего ай-тишника и может навсегда отбить охоту программировать. Но не все так страшно, потому что в терминале CS50 IDE будет подсказка, которая укажет номер строки и номер символа, вызвавшего ошибку. Идея в том, чтобы пойти в самое начало текста с ошибкой и вникнуть в эти первые строки, после чего исправить нужную строку кода. И в этот момент может произойти действительно чудо, когда все остальные ошибки пропадут. Это может быть связано с тем, что они были вызваны из-за каскадного эффекта. Такая ситуация возникает, когда программа не понимает одну строку, после чего не понимает следующие несколько строк. Но так бывает не всегда.
А теперь Вы узнаете самый главный секрет в написании кода - пишите код постепенно, делайте эти крошечные «детские» шаги, которые Вам понятны. Никогда не пишите большие куски кода целиком. Двигайтесь постепенно, от простого к более сложному. В таком случае Ваш код будет структурирован и понятен другим специалистам, а самое главное - он будет понятен Вам, когда вы откроете его через месяц, год или через 10 лет.
Стоит сказать, что этот подход можно использовать не только в программировании, но и в повседневной жизни, когда у Вас есть объемная задача, не так ли?
Помните! Залог успеха в маленьких «детских» шагах. Не менее важным является постоянство этих шагов. Выполнение сложной задачи маленькими кусочками изо дня в день даст Вам результат придаст уверенности в своих силах.
Постоянство «детских» шагов…
Даже самый мощный суперкомпьютер обладает ограниченными ресурсами
На неделе 1 курса приведено 2 примера, свидетельствующих о том, что в реальном мире компьютеры обладают ограниченными возможностями и не могут представить, например, число 1/3 как 0,333(3) и бесконечное количество троек, они обязательно округляют его.
Такие округления могут привести к тому, что после нескольких сотен часов непрерывной работы, может привести к появлению значительной погрешности, например, в счетчике времени.
Примером послужил фатальный случай, произошедший в 1991 году во время войны в Персидском заливе, когда ошибка в программном обеспечении привела к гибели американских солдат.
Этот случай послужил примером того, что любое программное обеспечение должно быть тщательно протестировано таким образом, чтобы учесть все возможные варианты развития событий.
Словарь:
Caeser - Цезарь
Ciphertext - зашифрованный текст
Plaintext - обычный текст
Encipher - зашифровать
Multiple - множественный
Same - одинаковый
Dog - собака
Correct - правильный
Usage - использование
Character - символ
Letter - буква
Alphabet - алфавит
На второй Неделе у Вас будет грандиозная возможность с головой окунуться в программирование на языке С, первое знакомство с которым произошло на Неделе 1, а также рассмотреть массивы.
00:00:00 - Обзор Недели 1
00:04:33 - Отладка программ
00:05:05 - buggy0
00:09:12 - buggy1
00:12:49 - buggy2
00:18:11 - buggy3
00:22:19 - debug50
00:29:04 - Отладка при помощи резиновой уточки
00:31:46 - Обзор практических занятий
00:35:18 - Академическая честность
00:39:07 - Щенки
00:39:58 - Криптография
00:41:00 - Ральфи
00:44:21 - Секретный ключ криптографии
00:46:18 - Строки
00:48:06 - string0
00:57:35 - string1
01:01:20 - Символы
01:02:39 - ascii0
01:06:19 - ascii1
01:09:04 - capitalize0
01:12:41 - capitalize2
01:13:47 - Руководство
01:16:31 - strlen
01:17:40 - Больше строк
01:22:49 - Больше о strlen
01:25:09 - Аргументы командной строки
01:26:53 - argv0
01:34:22 - argv1
01:36:35 - argv2
01:42:26 - exit
01:46:36 - Итоги
Инструменты для отладки программ
На первых этапах написания кода у новичков возникает масса синтаксических или логических ошибок. Такая ситуация, откровенно говоря, демотивирует, а иногда даже сводит с ума. В такие моменты хочется биться головой о стену, но приходится сдерживать свои эмоции, набраться терпения и искать «баги» или ошибки.
Именно по этой причине курс CS50 предлагает студентам ознакомиться с инструментами для отладки программы, а именно поиска и устранения ошибок. Одной из ключевых мыслей в этом разделе является исправление ошибок. Первым делом нужно взглянуть на самую первую ошибку, появившуюся в окне терминала . Там можно найти номер строки и символ, который привел к сбою в программе. Дэвид Мэлэн учит нас тому, что не стоит отчаиваться даже если количество строк с ошибками превышает количество строк программы. Это связано с тем, что одна ошибка может спровоцировать цепную реакцию и стать причиной возникновения нескольких ошибок друг за другом.
Стоит сосредоточиться на прочтении описания возникшей ошибки и, полагаясь на имеющиеся знания и опыт, опеределить причину ее возникновения. Кроме того, студентам курса CS50 может прийти в помощь help50, debug50 и как бы смешно и странно это не звучало - резиновая уточка. Интересно, не так ли? Тогда включайте видео на 29-й минуте и Вы увидите как пользоваться таким инструментом.
«Будь разумным»
Залогом качества обучения, спектра полученного опыта и навыков является самостоятельное выполение всех заданий. Это основной принцип курса CS50, о котором говорится практически на каждой неделе. Просто задайтесь вопросом: «Хотите ли Вы научиться программировать?!». Если ответ утвердительный, то в случае, когда у Вам возникают трудности Вы можете обратиться к своему товарищу, сокурснику, знакомому. Но ключевым здесь является то, что Вам нельзя смотреть на готовый код. Вы смело можете демонстрировать свой код и задавать различные вопросы. Вы не в коем случае не должны пользоваться чужим кодом или просить кого-то выполнить задание вместо Вас.
В CS50 существует целая процедура проверки работ на честность. Все работы должны быть выполнены индивидуально, поэтому работы сравнивают с работами всех студентов CS50, начиная с 2007 года. Более того, производится сравнение работы с работами на репозиторях, форумах, сайтах выполнения работ под заказ и так далее. Такой подход гарантирует качество полученных знаний и привавает студентам честность перед собой и перед окружающими.
Массивы
Главной темой Недели 2 курса CS50 Гарвардского университета являются массивы. Оказыватся, что любые слова или строки это массивы символов, которые следуют один за другим в памяти компьютера. Это связано с тем, что 1 бит памяти компьютера способен хранить 1 символ строки. Наборы этих символов, хранящихся в памяти компьютера, представляют собой строки, другими словами массивы символов. Более того, компьютер может представлять не только массивы символов, но и массивы строк. Но как же он понимает, где заканчивается одно слово и начинается другое, ведь его память это огромное количество ячеек? Оказывается, что существует специальный символ \0, который ставится вконце каждого слова в памяти компьютера и означает именно окончание слова.
Если вспомнить Неделю 1, а именно ASCII, то сразу становится понятно, что компьютер, понимающий только нули и единицы представляет в своей памяти буквы алфавита в виде цифр. Соответствие букв цифрам можно узнать из Интернета, посмотрев Неделю 2 курса CS50 на русском языке или, написав программу на языке С. На последнем варианте и будет сосредоточено внимание студентов на Неделе 2.
Шифрование данных
Неделя 2 курса CS50 Гарвардского университета привлекает к себе внимание тем, что здесь рассматриваются вопросы шифрования и расшифровки данных, другими словами понятия криптографии. Здесь нам поведают что же такое криптография, зачем она нужна и приведут пример, из которого станет понятно, что каждый из нас еще с детства занимался шифрованием и расшифровкой данных.
На Неделе 3 мы рассмотрим методы сортировки данных, их алгоритмы, а также узнаем какой метод самый эффективный и по традиции в самом начале Недели 3 будет краткий обзор массивов данных и материала с Недели 2.
00:00:00 - Обзор Недели 2
00:04:32 - Поиск числа 50
00:08:23 - Линейный поиск
00:11:56 - Бинарный поиск
00:15:18 - Память
00:19:13 - Сортировка синих книг
00:23:08 - Сортировка игральных карт
00:25:57 - Сортировка добровольцев с числами
00:28:31 - Сортировка выбором
00:31:58 - Пузырьковая сортировка
00:35:07 - Сортировка вставкой
00:37:30 - Псевдокод Пузырьковой сортировки
00:38:42 - Псевдокод сортировки Выбором
00:39:22 - Псевдокод сортировки Вставкой
00:40:19 - Алгоритмы и время их выполнения
00:45:11 - Обозначение большой О
00:51:10 - Обозначение большой Омега
00:56:33 - Обозначение большой Сэта
00:58:02 - Визуальная сортировка
01:02:00 - Рекурсия
01:03:04 - Сортировка объединением
01:17:23 - sigma0
01:19:15 - sigma1
01:22:58 - Интервью в Google
Сортировка данных и алгоритмы сортировок
В современном мире сортировка данных занимает место в жизни практически каждого человека. Вы сталкиваетесь с этим при игре в карты, при расстановке фигур на шахматной доске или при сортировке букв в алфавитном порядке. В контексте изучения программирования, сортировка является неотъемлемой его частью. Взять хотя бы iPhone или Android в Вашем кармане, телефонная книга которого содержит несколько десятков или сотен имен знакомых и родственников. Даже страшно представить сколько времени пришлось бы потратить, если бы фамилии и имена людей в телефонной книге не были отсортированы. Масштабируя и рассматривая этот вопрос в объеме данных интернета, становится понятно, что эффективный и быстрый поиск информации невозможен без сортировки данных. Именно сортировка данных и различные алгоритмы сортировок станут ключевыми на Неделе 3 курса Гарвардского университета по основам программирования CS50 2016.
На Неделе 4 мы рассмотрим память компьютера, а именно - взаимодействие кода программы и памяти компьютера. И по обычаю начало Недели 4 сопровождается кратким обзором материала алгоритмов сортировки данных с Недели 3.
00:00:00 - Обзор Недели 3
00:03:24 - Строки это вранье
00:04:20 - compare0
00:06:34 - copy0
00:10:05 - noswap
00:15:49 - Память программы
00:17:35 - Стэк (Stack)
00:22:15 - Подробное рассмотрение get_string()
00:31:05 - Пред просмотр мультипликации об указателях
00:31:29 - Удаление тренировочных колес
00:32:05 - compare1
00:32:39 - char *
00:34:45 - strcmp
00:36:42 - copy1
00:37:02 - malloc
00:45:07 - Рассмотрение указателей
00:49:27 - swap
00:55:04 - Память компьютера и профессор Мэлэн
00:56:05 - Арифметика указателей
00:56:18 - Указатели
01:03:06 - Игра указателей с Бинки
01:06:26 - Утечки памяти
01:07:02 - Отладка программы с помощью Valgrind
01:07:30 - memory
01:14:42 - Хип (Heap)
01:16:01 - Типы переполнений
01:17:26 - Переполнение буфера
01:21:20 - Подробное рассмотрение Стэк (Stack)
01:26:53 - Увеличение
01:28:38 - Изображения
01:31:04 - JPEG
01:32:11 - Шестнадцатиричная система исчисления
01:37:10 - BMP
01:40:24 - struct
01:42:19 - structs0
01:45:00 - structs1
01:47:55 - CSV
01:48:43 - Улучшение
Строки STRING и память компьютера
Почему курс СS50 Гарвардского университета по основам программирования приобрел столь широкую огласку и популярность? Мне кажется, что секретной формулой успеха являются детские шаги, о которых мы впервые узнали в самом начале курса на Неделе 0 при рассмотрении языка Scratch. Ведь все большие дела делаются маленькими шагами, не так ли?
Сначала мы рассматривали строки string в качестве данных, которые нам может ввести пользователь для дальнейшей работы с ними. После этого на Неделе 2 мы осознали, что строк, как таковых, не существует, вместо них есть массивы символов, другими словами, последовательность символов друг за другом. Все эти символы объединенные в строку. Но как компьютеру найти окончание той или иной строки? Для этого существует обратный слэш 0 (\0), который четко разграничивает в памяти окончание той или иной строки. На Неделе 4 пришло время сделать еще один маленький шаг, который позволит пополнить копилку наших знаний своего рода магической информацией.
Оказывается, что программа работает не со значениями или символами, которые ввел пользователь, будь-то слово Hello, Zamyla, David или любое другое слово. Программа работает с адресом символа в памяти компьютера, то есть с адресом первого символа строки, с которым мы выполняем операции в памяти.
Почему мы тогда рассматривали строки string на предыдущих занятиях, если их не существует? Все очень просто. Это сделано преднамеренно, для того, чтобы двигаться от общего к частному и не запутаться в самом начале изучения программирования в вопросах самого низкого уровня. Такое поэтапное движение дает четкое представление того, что же находится «под капотом» и каким образом устроена память компьютера.
Понимание принципов работы памяти компьютера на самом низком уровне позволяет избежать довольно распространенных ошибок. А именно связанных с ситуацией, когда память компьютера может оказаться переполненной или могут произойти утечками памяти. Знание «узких мест» позволяет защитить память своего компьютера от несанкционированного доступа злоумышленников.
Что нужно для того, чтобы стать файлом?
На Неделе 4 мы немного отвлечемся от рассмотрения как работает память компьютера и затронем определение файлов на примере изображений с расширением JPEG, которые все Вы видели у себя в компьютере, фотоаппарате или телефоне. Оказывается, что файл это все тот же набор нулей и единиц, однако компьютеру нужно как-то понимать отличие между изображениями и текстовыми документами Microsot Word или презентациями Power Point или другими файлами. Поэтому люди пришли к соглашению, что определенный набор цифр десятичной системы или двоичной системы, или шестнадцатиричной системы исчисления будет означать тот или другой тип файла. Так, например, изображения JPEG содержат цифры FF D8 FF в шестнадцатиричной системе исчисления, которые дают компьютеру понимание того, что это действительно изображение JPEG с большой долей вероятности. Давайте посмотрим, как будут выглядеть комбинации символов, представляющих изображение JPEG в различных системах исчисления:
1. Десятичная - decimal: 255, 216, 255.
2. Двоичная - binary: 1111 1111, 1101 1000, 1111 1111.
3. Шестнадцатиричная - hexadecimal: FF D8 FF.
Кстати, помните ли вы, как преобразовать число из десятичной системы исчисления в двоичную?
По итогу, хочется отметить, что четвертая Неделя курса CS50 2016 на русском является наиболее интересной неделей с точки зрения понимания вещей, которые происходят «под капотом» в памяти компьютера. Надеюсь, что Неделя 4 не оставит Вас равнодушными и пополнит Вашу копилку знаний, новым и интересным материалом.
На пятой Неделе мы изучим структуры данных, что позволит использовать память компьютера эффективнее. В начале Недели 5 вы увидите краткий обзор предыдущей Недели 4, в которой мы рассматривали память компьютера.
00:00:00 - Обзор Недели 4
00:07:22 - Ограничения в массивах
00:10:45 - Списки
00:13:11 - Узлы
00:15:10 - Связанные списки
00:20:39 - Список людей
00:26:52 - Список операций
00:28:14 - Реализация поиска
00:40:11 - Компромиссы в вязанных списках
00:41:26 - Стеки
00:43:57 - Реализация стека
00:47:30 - Очереди
00:49:43 - Реализация очереди
00:54:40 - Типы абстрактных данных
00:56:06 - Мультфильм о стеке и очереди
00:57:53 - Деревья
01:00:59 - Двоичное поисковое дерево
01:07:56 - Реализация дерева
01:14:26 - Код Хаффмана
01:28:42 - Хэш таблицы
01:30:37 - Ящики
01:33:31 - Линейное пробирование
01:36:21 - Отдельные цепочки
01:39:05 - Префиксное дерево
Словарь терминов и структуры данных
Во-первых, я хочу искренне поздравить Вас, дорогие друзья с тем, что Вы изучили 50% курса Гарвардского университета CS50 на русском 2016. Неделя 5 это середина курса и является последней Неделей, в которой рассматриваются основы того, что происходит в памяти компьютера, ведь во второй половине курса CS50 2016 мы сосредоточимся на таких темах, как протокол передачи данных HTTP, язык Python, SQL, Javascript и т.д.
Своеобразным ноу-хау Недели 5 является краткий словарь терминов, которые будут представлены под видео и в этой статье для лучшего понимания какие существуют структуры данных. Словарь Недели 5 выглядит следующим образом:
1. Список - list
2. Узел - node
3. Указатель - pointer
4. Очередь - queue
5. Дерево - tree
6. Префиксные деревья - tries
Это даст Вам возможность вдобавок изучить несколько английских слов или воспользоваться Википедией для того, чтобы более углубленно рассмотреть значения этих терминов. На этой лекции мы изучим такие структуры данных, как бинарное дерево, префиксное дерево, хеш-таблицы.
Динамическое выделение памяти
До этой Недели мы пользовались массивами для представления данных в памяти компьютера, но сложность состоит в том, что массивы хороши в том случае, когда Вы определенно знаете, какой размер Вашего массива и сколько свободных байтов необходимо попросить у компьютера. Однако в программировании часто возникает ситуация, когда Вы не можете знать заранее сколько памяти нужно попросить у компьютера, в таком случае нет смысла использовать массивы, обладающие фиксированными значениями.
Для этих целей в программировании существуют связанные списки, которые позволяют динамически получать или отдавать место в памяти компьютера, но, к сожалению, возникает еще одна проблема. Какая именно? Смотрите видео Недели 5 курса Гарвардского университета по основам программирования.
Как реализован стек или очередь queue?
На Неделе 5 курса CS50 на русском рассматривается интересный пример размещения информации в стек. Представьте стопку разносов в столовой или кафе. Идея заключается в том, что когда Вы кладёте разнос на стопку, а потом снова хотите взять разнос, Вы, как правило, берете верхний разнос, а все остальные разносы лежат, как и прежде. Это если бы Вы пришли купить новый iPhone в магазин Apple в первый же день начала продаж, простояли бы в очереди в ожидании открытия магазина и начала продаж, однако, получили бы свой новый iPhone не в порядке очереди, а после тех, кто пришел в магазин последним. С точки зрения логики, если Вы дадите товар сначала людям, которые ближе к выходу, эти люди выйдут из магазина первыми, в результате чего магазин будет постепенно опустошаться. Но вряд ли Вам понравится такой алгоритм продажи новых iPhone.
Такая же ситуация складывается и в стек, но для того, чтобы справедливость восторжествовала и первый элемент в очереди был использован в первую очередь существует такое понятие, как очередь queue.
Разницу между stack и queue можно легко понять, посмотрев короткометражный мультик на 56-й минуте Недели 5.
Код Хаффмана или азбука Морзе?
Скорее всего нет человека, который бы не знал что такое азбука Морзе. На Неделе 5 курса CS50 на русском 2016 проводится аналогия между азбукой Морзе и кодом Хаффмана. Так вот, интересным моментом азбуки Морзе является использование длинных или коротких сигналов для обозначения той или иной буквы. Основным является то, что самый короткий сигнал используется для буквы E. Все дело в том, что при создании своей азбуки, господин Морзе увидел, что некоторые буквы фигурируют в словах чаще других. Поэтому для того, чтобы сделать передачу информации максимально быстрой, было решено передавать самыми короткими сигналами те символы, которые используются чаще всего, а более длинными сигналами - буквы, которые реже всего используются.
Такой же принцип использует код Хаффмана, который служит для сжатия файлов. Принцип сжатия, например, файла Microsoft Word заключается в том, что для хранения в памяти букв, которые чаще всего используются, используется более короткий набор нулей и единиц. Более того, зная принцип работы кода Хаффмана, Вы можете закодировать информацию, а затем с легкостью расшифровать. Если Вы хотите узнать в каком случае сжатый файл может стать большего размера, нежели первоначальный - смотрите перевод на русский язык Недели 5 курса CS50 Гарвардского университета.
В заключении стоит отметить, что практически весь код программ на Неделе 5 сопровождается использованием рекурсии. Рекурсия является очень эффективным инструментом в плане скорости выполнения в случае, когда Вы выбрасываете половину проблемы прочь, как на Неделе 0 при поиске Майка Смитта.
На следующей Неделе мы рассмотрим протокол передачи данных HTTP.
Часть 1 - Часть 2
Смотрите также:
Весь гарвардский курс по основам программирования (CS50 2015 год)
Сайты для обучения программированию
11 ресурсов для бесплатного образования
15 образовательных YouTube каналов на русском языке
Лекции и уроки
Нейросеть сделала компьютерную игру
Игра «Маг кода» для изучения Python, JavaScript, анализа данных, машинного обучения и нейронных сетей
Click to viewНеделя 0 курса Гарвардского университета по основам программирования CS50 2016 года на русском языке начинается с рассмотрения графического языка. Это язык Scratch (Скретч). Графический язык, который создан сотрудниками Массачусетского технологического института.
0:04:06 - двоичная система исчисления
0:10:01 - как перевести числа из десятичной в двоичную систему исчисления
0:12:24 - как компьютер запоминает буквы, цвета и изображения
0:16:12 - как в три действия сосчитать всех студентов в классе
0:22:11 - как в три действия найти человека в телефонной книге из 1000 страниц
0:30:50 - что нового в курсе CS50 2016 года
0:47:20 - графический язык Scratch (Скретч)
0:52:29 - играем в игру Oscartime
0:56:31 - создание первой программы в Scratch (Скретч)
Этот курс нацелен на тех, кто в раздумьях над тем с чего начать изучать программирование. Этот курс приобрел популярность во всем мире благодаря кропотливому и упорному труду команды CS50 Гарвардского университета. А это более, чем 100 человек во главе с талантливым оратором и преподавателем, профессором Дэвидом Мэлэном. Почему легко начать изучать программирование с курса CS50? Потому что вся информация преподается простым и понятным языком, а манера преподавания отличается от постсоветских ВУЗов настолько, что курс больше похож на тренинг, нежели на университетскую лекцию.
Почему Неделя 0?
Это старт курса Гарвардского университета по основам программирования CS50 на русском языке 2016 года. Почему неделя 0? - спросите вы меня. Все очень просто. Программисты начинают считать не с 1, как все остальные люди, а с 0. Именно поэтому курс CS50 начинается с недели 0. Если немного отклониться в сторону, то каждый человек начинает свой жизненный путь, свое дело, именно с 0, а не с единицы, так что начать изучать программирование предстоит именно с Недели 0.
На Неделе 0 вы узнаете чем отличается компьютер от человека, какую систему исчисления он использует и как ее преобразовать в десятичную систему исчисления, столь привычную для людей. Каким образом компьютеру удается представлять и запоминать не только цифры, но и буквы, цвета, изображения и даже видео.
Как быстро посчитать людей в большой аудитории и почему Scratch (Скретч)?
После этого Вас ждет разминка в виде задачки, в которой требуется найти в телефонном справочнике на 1000 страниц некого Майка Смитта. Но ценность задачи не просто в том, чтобы найти Майка Смитта, ведь все знают как это сделать, а в том, чтобы сделать это максимально быстро и эффективно. Профессор Дэвид Мэлэн расскажет Вам, как, используя простой алгоритм, другими словами, инструкцию, найти очень быстро человека в телефонной книге. Более того, алгоритм настолько универсальный, что позволяет быстро найти человека в телефонном справочнике, что даже справочник в 4 млрд страниц не является проблемой. Этот же алгоритм будет использован для подсчета количества людей в огромной аудитории.
Первым языком программирования, который Вы изучите в ходе курса, будет графический язык Scratch (Скретч). Он позволяет в буквальном смысле слова создать программу просто перетаскивая кусочки головоломки и объединяя их между собой. Это похоже больше на игру, нежели на программирование. Язык Scratch (Скретч) настолько разнообразен, что позволяет создать аналог популярной игры Pokemon GO, просто перетаскивая и объединяя блоки головоломки.
Простота и богатый функционал графического языка Scratch (Скретч) сделали его очень популярным не только среди детей и студентов, но и среди взрослых.
Логичным продолжением примеров, рассмотренных в ходе лекции Недели 0, является практическая часть, а точнее пошаговое руководство или уроки Scratch для начинающих. В практических уроках по Scratch сотрудники курса CS50 шаг за шагом расскажут о том, как работает программа от друзей из Массачусетского технологического института. Вы научитесь создавать свои собственные программы. Однако Вы не будете кодить, Вы будете просто перетаскивать соответствующие блоки, объединять их с другими блоками, использовать переменные, логические выражения, циклы и т.д.
Кроме того, существует также ресурс Code.org, который, подобно Scratch (Скретч), позволит в игровой манере постичь азы программирования. Преимуществом вышеуказанного ресурса является обучение не только на английском языке, но и возможность выбора русского языка в качестве основного.
Почему CS50?
Первая лекция курса очень многообещающая и абсолютно разрушает стереотип на счет сложности программирования. Все подается в игровой форме. Где бы Вас еще преподаватель попросил поиграть в свое первое домашнее задание? Согласитесь, это вызывает интерес и сводит на ноль фобию сложности программирования, ведь ключик именно в том, чтобы делать маленькие детские шажки, постепенно приближаясь к своей цели. Это можно сравнить с тем, как человек заходит в воду, шаг за шагом смачивая каждый миллиметр своего тела и в конце-концов получает удовольствие от полного погружения.
Практическая часть курса представляет собой практические занятия, так называемые Problem Sets, пошаговое руководство и «шоты» - коротенькие видеообзоры определенной узконаправленной темы. Практические занятия являются логичным дополнением курса лекций CS50 на русском, а конкретно этот пост относится к практическому занятию к лекции Недели 0, посвященной языку Scratch. Это своего рода уроки Scratch для начинающих.
Словарь практического занятия Scratch
Motion - движение
Look - вид
Sound - звук
Pen - ручка
Data - данные
Event - событие
Control - контроль
Sensing - ощущение
Operators - операторы
Costumes - костюмы
Sounds - звуки
to Move - двигаться
to Play - играть
to Change - менять
to Set - установить
Score - счет
Space - пробел
Key - клавиша
Forever - навсегда
Repeat - повтор
Until - до тех пор
Global - глобальный
Local - локальный
Behave - поведение
Receive - получать
Broadcast - трансляция
Edge - край
Bounce - отскок
Glide - скольжение
Touch - касание
Первые уроки Scratch для начинающих
Переходим по адресу https://scratch.mit.edu/ и мы попадаем на сайт. Для перехода непосредственно в интерфейс программы, мы можем нажать на оранжевого кота «попробовать». Кроме того, справа есть видео по работе со Scratch.
Итак, мы попадаем в интерфейс программы и видим слева рабочее пространство stage, о котором говорила Замайла в видео. Также мы видим наш первый спрайт оранжевого кота, который является спрайтом по умолчанию. При движении курсора мыши по рабочему пространству в нижнем правом углу меняются координаты x и y, что позволяет определить текущие координаты курсора мыши.
В центральной консоли расположены блоки. Блоки распределены по разделам:
* Движение
* Внешность
* Звук
* Перо
* Данные
* События
* Управление
* Сенсоры
* Операторы
* Другие блоки
Кроме того, на центральной консоли есть 3 вкладки: скрипты, костюмы, звуки.
Любая программа Scratch начинается с блока из раздела «События», который называется «когда щелкнут по зеленому флагу». Это строительный блок, который будет встречаться чаще всего в Ваших программах, так как без него не будет работать ни одна программа.
Среди основных блоков можно выделить блоки действий, блоки логических выражений, блоки условий, блоки циклов, блоки переменных, блоки событий.
Блоки действий
Блоки действий находятся в разделах «Движение», «Внешность», «Звук», «Перо».
Блоки условий и циклов
Находятся в разделе «События». Вы можете также обратить внимание, что некоторые блоки содержат заполнители такой же формы, как блоки, которые могут быть вставлены в них.
Наш первый урок Scratch.
Давайте сделаем нашу первую программу самостоятельно. Например, воспользуемся исходным спрайтом, изменим его костюм, чтобы он был в движении, а при наведении курсора мыши на кота, кот будет останавливаться. Когда вы убираете курсор мыши - кот продолжит движение. Итак, как же будет выглядеть наша первая программа? Какими строительными блоками мы воспользуемся? Попробуйте самостоятельно сделать эту программу.
Получилось? В качестве бонуса сыграйте в игру от Гарвардского университета.
https://scratch.mit.edu/projects/12352154/
На Неделе 1 профессор Дэвид Мэлэн проведет аналогию между графическим языком Scratch и низкоуровневым языком программирования C. Фактически все программы, реализованные на языке Scratch на Неделе 0, будут реализованы используя язык программирования C.
0:01:12 - графический язык Scratch и язык программирования C
0:14:10 - описание библиотеки CS50 IDE
0:16:39 - написание первой программы на языке С
0:28:50 - основные функции CS50 IDE
0:35:07 - какую стратегию следует использовать для поиска и устранения ошибок в коде
0:47:58 - как компьютеры округляют числа
0:54:49 - типы данных в языке С
0:55:51 - сколько памяти занимает каждый из типов данных
1:01:48 - какое максимальное число может представить компьютер
1:08:37 - ошибки в играх Lego Star Wars и Civilization
1:10:32 - ошибки в программном обеспечении самолетов Boeing
1:13:54 - как возникают ошибки из-за округления чисел компьютером
1:19:01 - взрыв ракеты Arian 5 и трагедия в Персидском заливе из-за ошибки в программном обеспечении ПВО Патриот
1:30:17 - написание программ на языке программирования С
Язык программирования C и «привет, мир»!
Фраза «Привет, мир!» без преувеличения является легендарной, ведь это первая фраза, с которой сталкивается практически каждый человек, желающий изучать программирование. Она стала настолько популярной, что используется практически в любом языке программирования. Это, по сути, первая программа, в которой рассматривается базовый синтаксис языка. Язык программирования C не является исключением, поэтому его рассмотрение начинается именно с этой фразы.
Поиск ошибки в коде или «детские» шаги?
Программирование неразрывно связано с наличием ошибок, так называемых «багов», которые постоянно приходится «фиксить» или устранять. Даже самая простая программа, состоящая всего из 6 строк кода может привести 10 строкам ошибок. Естественно, это вызывает разочарование у начинающего ай-тишника и может навсегда отбить охоту программировать. Но не все так страшно, потому что в терминале CS50 IDE будет подсказка, которая укажет номер строки и номер символа, вызвавшего ошибку. Идея в том, чтобы пойти в самое начало текста с ошибкой и вникнуть в эти первые строки, после чего исправить нужную строку кода. И в этот момент может произойти действительно чудо, когда все остальные ошибки пропадут. Это может быть связано с тем, что они были вызваны из-за каскадного эффекта. Такая ситуация возникает, когда программа не понимает одну строку, после чего не понимает следующие несколько строк. Но так бывает не всегда.
А теперь Вы узнаете самый главный секрет в написании кода - пишите код постепенно, делайте эти крошечные «детские» шаги, которые Вам понятны. Никогда не пишите большие куски кода целиком. Двигайтесь постепенно, от простого к более сложному. В таком случае Ваш код будет структурирован и понятен другим специалистам, а самое главное - он будет понятен Вам, когда вы откроете его через месяц, год или через 10 лет.
Стоит сказать, что этот подход можно использовать не только в программировании, но и в повседневной жизни, когда у Вас есть объемная задача, не так ли?
Помните! Залог успеха в маленьких «детских» шагах. Не менее важным является постоянство этих шагов. Выполнение сложной задачи маленькими кусочками изо дня в день даст Вам результат придаст уверенности в своих силах.
Постоянство «детских» шагов…
Даже самый мощный суперкомпьютер обладает ограниченными ресурсами
На неделе 1 курса приведено 2 примера, свидетельствующих о том, что в реальном мире компьютеры обладают ограниченными возможностями и не могут представить, например, число 1/3 как 0,333(3) и бесконечное количество троек, они обязательно округляют его.
Такие округления могут привести к тому, что после нескольких сотен часов непрерывной работы, может привести к появлению значительной погрешности, например, в счетчике времени.
Примером послужил фатальный случай, произошедший в 1991 году во время войны в Персидском заливе, когда ошибка в программном обеспечении привела к гибели американских солдат.
Этот случай послужил примером того, что любое программное обеспечение должно быть тщательно протестировано таким образом, чтобы учесть все возможные варианты развития событий.
Словарь:
Caeser - Цезарь
Ciphertext - зашифрованный текст
Plaintext - обычный текст
Encipher - зашифровать
Multiple - множественный
Same - одинаковый
Dog - собака
Correct - правильный
Usage - использование
Character - символ
Letter - буква
Alphabet - алфавит
На второй Неделе у Вас будет грандиозная возможность с головой окунуться в программирование на языке С, первое знакомство с которым произошло на Неделе 1, а также рассмотреть массивы.
00:00:00 - Обзор Недели 1
00:04:33 - Отладка программ
00:05:05 - buggy0
00:09:12 - buggy1
00:12:49 - buggy2
00:18:11 - buggy3
00:22:19 - debug50
00:29:04 - Отладка при помощи резиновой уточки
00:31:46 - Обзор практических занятий
00:35:18 - Академическая честность
00:39:07 - Щенки
00:39:58 - Криптография
00:41:00 - Ральфи
00:44:21 - Секретный ключ криптографии
00:46:18 - Строки
00:48:06 - string0
00:57:35 - string1
01:01:20 - Символы
01:02:39 - ascii0
01:06:19 - ascii1
01:09:04 - capitalize0
01:12:41 - capitalize2
01:13:47 - Руководство
01:16:31 - strlen
01:17:40 - Больше строк
01:22:49 - Больше о strlen
01:25:09 - Аргументы командной строки
01:26:53 - argv0
01:34:22 - argv1
01:36:35 - argv2
01:42:26 - exit
01:46:36 - Итоги
Инструменты для отладки программ
На первых этапах написания кода у новичков возникает масса синтаксических или логических ошибок. Такая ситуация, откровенно говоря, демотивирует, а иногда даже сводит с ума. В такие моменты хочется биться головой о стену, но приходится сдерживать свои эмоции, набраться терпения и искать «баги» или ошибки.
Именно по этой причине курс CS50 предлагает студентам ознакомиться с инструментами для отладки программы, а именно поиска и устранения ошибок. Одной из ключевых мыслей в этом разделе является исправление ошибок. Первым делом нужно взглянуть на самую первую ошибку, появившуюся в окне терминала . Там можно найти номер строки и символ, который привел к сбою в программе. Дэвид Мэлэн учит нас тому, что не стоит отчаиваться даже если количество строк с ошибками превышает количество строк программы. Это связано с тем, что одна ошибка может спровоцировать цепную реакцию и стать причиной возникновения нескольких ошибок друг за другом.
Стоит сосредоточиться на прочтении описания возникшей ошибки и, полагаясь на имеющиеся знания и опыт, опеределить причину ее возникновения. Кроме того, студентам курса CS50 может прийти в помощь help50, debug50 и как бы смешно и странно это не звучало - резиновая уточка. Интересно, не так ли? Тогда включайте видео на 29-й минуте и Вы увидите как пользоваться таким инструментом.
«Будь разумным»
Залогом качества обучения, спектра полученного опыта и навыков является самостоятельное выполение всех заданий. Это основной принцип курса CS50, о котором говорится практически на каждой неделе. Просто задайтесь вопросом: «Хотите ли Вы научиться программировать?!». Если ответ утвердительный, то в случае, когда у Вам возникают трудности Вы можете обратиться к своему товарищу, сокурснику, знакомому. Но ключевым здесь является то, что Вам нельзя смотреть на готовый код. Вы смело можете демонстрировать свой код и задавать различные вопросы. Вы не в коем случае не должны пользоваться чужим кодом или просить кого-то выполнить задание вместо Вас.
В CS50 существует целая процедура проверки работ на честность. Все работы должны быть выполнены индивидуально, поэтому работы сравнивают с работами всех студентов CS50, начиная с 2007 года. Более того, производится сравнение работы с работами на репозиторях, форумах, сайтах выполнения работ под заказ и так далее. Такой подход гарантирует качество полученных знаний и привавает студентам честность перед собой и перед окружающими.
Массивы
Главной темой Недели 2 курса CS50 Гарвардского университета являются массивы. Оказыватся, что любые слова или строки это массивы символов, которые следуют один за другим в памяти компьютера. Это связано с тем, что 1 бит памяти компьютера способен хранить 1 символ строки. Наборы этих символов, хранящихся в памяти компьютера, представляют собой строки, другими словами массивы символов. Более того, компьютер может представлять не только массивы символов, но и массивы строк. Но как же он понимает, где заканчивается одно слово и начинается другое, ведь его память это огромное количество ячеек? Оказывается, что существует специальный символ \0, который ставится вконце каждого слова в памяти компьютера и означает именно окончание слова.
Если вспомнить Неделю 1, а именно ASCII, то сразу становится понятно, что компьютер, понимающий только нули и единицы представляет в своей памяти буквы алфавита в виде цифр. Соответствие букв цифрам можно узнать из Интернета, посмотрев Неделю 2 курса CS50 на русском языке или, написав программу на языке С. На последнем варианте и будет сосредоточено внимание студентов на Неделе 2.
Шифрование данных
Неделя 2 курса CS50 Гарвардского университета привлекает к себе внимание тем, что здесь рассматриваются вопросы шифрования и расшифровки данных, другими словами понятия криптографии. Здесь нам поведают что же такое криптография, зачем она нужна и приведут пример, из которого станет понятно, что каждый из нас еще с детства занимался шифрованием и расшифровкой данных.
На Неделе 3 мы рассмотрим методы сортировки данных, их алгоритмы, а также узнаем какой метод самый эффективный и по традиции в самом начале Недели 3 будет краткий обзор массивов данных и материала с Недели 2.
00:00:00 - Обзор Недели 2
00:04:32 - Поиск числа 50
00:08:23 - Линейный поиск
00:11:56 - Бинарный поиск
00:15:18 - Память
00:19:13 - Сортировка синих книг
00:23:08 - Сортировка игральных карт
00:25:57 - Сортировка добровольцев с числами
00:28:31 - Сортировка выбором
00:31:58 - Пузырьковая сортировка
00:35:07 - Сортировка вставкой
00:37:30 - Псевдокод Пузырьковой сортировки
00:38:42 - Псевдокод сортировки Выбором
00:39:22 - Псевдокод сортировки Вставкой
00:40:19 - Алгоритмы и время их выполнения
00:45:11 - Обозначение большой О
00:51:10 - Обозначение большой Омега
00:56:33 - Обозначение большой Сэта
00:58:02 - Визуальная сортировка
01:02:00 - Рекурсия
01:03:04 - Сортировка объединением
01:17:23 - sigma0
01:19:15 - sigma1
01:22:58 - Интервью в Google
Сортировка данных и алгоритмы сортировок
В современном мире сортировка данных занимает место в жизни практически каждого человека. Вы сталкиваетесь с этим при игре в карты, при расстановке фигур на шахматной доске или при сортировке букв в алфавитном порядке. В контексте изучения программирования, сортировка является неотъемлемой его частью. Взять хотя бы iPhone или Android в Вашем кармане, телефонная книга которого содержит несколько десятков или сотен имен знакомых и родственников. Даже страшно представить сколько времени пришлось бы потратить, если бы фамилии и имена людей в телефонной книге не были отсортированы. Масштабируя и рассматривая этот вопрос в объеме данных интернета, становится понятно, что эффективный и быстрый поиск информации невозможен без сортировки данных. Именно сортировка данных и различные алгоритмы сортировок станут ключевыми на Неделе 3 курса Гарвардского университета по основам программирования CS50 2016.
На Неделе 4 мы рассмотрим память компьютера, а именно - взаимодействие кода программы и памяти компьютера. И по обычаю начало Недели 4 сопровождается кратким обзором материала алгоритмов сортировки данных с Недели 3.
00:00:00 - Обзор Недели 3
00:03:24 - Строки это вранье
00:04:20 - compare0
00:06:34 - copy0
00:10:05 - noswap
00:15:49 - Память программы
00:17:35 - Стэк (Stack)
00:22:15 - Подробное рассмотрение get_string()
00:31:05 - Пред просмотр мультипликации об указателях
00:31:29 - Удаление тренировочных колес
00:32:05 - compare1
00:32:39 - char *
00:34:45 - strcmp
00:36:42 - copy1
00:37:02 - malloc
00:45:07 - Рассмотрение указателей
00:49:27 - swap
00:55:04 - Память компьютера и профессор Мэлэн
00:56:05 - Арифметика указателей
00:56:18 - Указатели
01:03:06 - Игра указателей с Бинки
01:06:26 - Утечки памяти
01:07:02 - Отладка программы с помощью Valgrind
01:07:30 - memory
01:14:42 - Хип (Heap)
01:16:01 - Типы переполнений
01:17:26 - Переполнение буфера
01:21:20 - Подробное рассмотрение Стэк (Stack)
01:26:53 - Увеличение
01:28:38 - Изображения
01:31:04 - JPEG
01:32:11 - Шестнадцатиричная система исчисления
01:37:10 - BMP
01:40:24 - struct
01:42:19 - structs0
01:45:00 - structs1
01:47:55 - CSV
01:48:43 - Улучшение
Строки STRING и память компьютера
Почему курс СS50 Гарвардского университета по основам программирования приобрел столь широкую огласку и популярность? Мне кажется, что секретной формулой успеха являются детские шаги, о которых мы впервые узнали в самом начале курса на Неделе 0 при рассмотрении языка Scratch. Ведь все большие дела делаются маленькими шагами, не так ли?
Сначала мы рассматривали строки string в качестве данных, которые нам может ввести пользователь для дальнейшей работы с ними. После этого на Неделе 2 мы осознали, что строк, как таковых, не существует, вместо них есть массивы символов, другими словами, последовательность символов друг за другом. Все эти символы объединенные в строку. Но как компьютеру найти окончание той или иной строки? Для этого существует обратный слэш 0 (\0), который четко разграничивает в памяти окончание той или иной строки. На Неделе 4 пришло время сделать еще один маленький шаг, который позволит пополнить копилку наших знаний своего рода магической информацией.
Оказывается, что программа работает не со значениями или символами, которые ввел пользователь, будь-то слово Hello, Zamyla, David или любое другое слово. Программа работает с адресом символа в памяти компьютера, то есть с адресом первого символа строки, с которым мы выполняем операции в памяти.
Почему мы тогда рассматривали строки string на предыдущих занятиях, если их не существует? Все очень просто. Это сделано преднамеренно, для того, чтобы двигаться от общего к частному и не запутаться в самом начале изучения программирования в вопросах самого низкого уровня. Такое поэтапное движение дает четкое представление того, что же находится «под капотом» и каким образом устроена память компьютера.
Понимание принципов работы памяти компьютера на самом низком уровне позволяет избежать довольно распространенных ошибок. А именно связанных с ситуацией, когда память компьютера может оказаться переполненной или могут произойти утечками памяти. Знание «узких мест» позволяет защитить память своего компьютера от несанкционированного доступа злоумышленников.
Что нужно для того, чтобы стать файлом?
На Неделе 4 мы немного отвлечемся от рассмотрения как работает память компьютера и затронем определение файлов на примере изображений с расширением JPEG, которые все Вы видели у себя в компьютере, фотоаппарате или телефоне. Оказывается, что файл это все тот же набор нулей и единиц, однако компьютеру нужно как-то понимать отличие между изображениями и текстовыми документами Microsot Word или презентациями Power Point или другими файлами. Поэтому люди пришли к соглашению, что определенный набор цифр десятичной системы или двоичной системы, или шестнадцатиричной системы исчисления будет означать тот или другой тип файла. Так, например, изображения JPEG содержат цифры FF D8 FF в шестнадцатиричной системе исчисления, которые дают компьютеру понимание того, что это действительно изображение JPEG с большой долей вероятности. Давайте посмотрим, как будут выглядеть комбинации символов, представляющих изображение JPEG в различных системах исчисления:
1. Десятичная - decimal: 255, 216, 255.
2. Двоичная - binary: 1111 1111, 1101 1000, 1111 1111.
3. Шестнадцатиричная - hexadecimal: FF D8 FF.
Кстати, помните ли вы, как преобразовать число из десятичной системы исчисления в двоичную?
По итогу, хочется отметить, что четвертая Неделя курса CS50 2016 на русском является наиболее интересной неделей с точки зрения понимания вещей, которые происходят «под капотом» в памяти компьютера. Надеюсь, что Неделя 4 не оставит Вас равнодушными и пополнит Вашу копилку знаний, новым и интересным материалом.
На пятой Неделе мы изучим структуры данных, что позволит использовать память компьютера эффективнее. В начале Недели 5 вы увидите краткий обзор предыдущей Недели 4, в которой мы рассматривали память компьютера.
00:00:00 - Обзор Недели 4
00:07:22 - Ограничения в массивах
00:10:45 - Списки
00:13:11 - Узлы
00:15:10 - Связанные списки
00:20:39 - Список людей
00:26:52 - Список операций
00:28:14 - Реализация поиска
00:40:11 - Компромиссы в вязанных списках
00:41:26 - Стеки
00:43:57 - Реализация стека
00:47:30 - Очереди
00:49:43 - Реализация очереди
00:54:40 - Типы абстрактных данных
00:56:06 - Мультфильм о стеке и очереди
00:57:53 - Деревья
01:00:59 - Двоичное поисковое дерево
01:07:56 - Реализация дерева
01:14:26 - Код Хаффмана
01:28:42 - Хэш таблицы
01:30:37 - Ящики
01:33:31 - Линейное пробирование
01:36:21 - Отдельные цепочки
01:39:05 - Префиксное дерево
Словарь терминов и структуры данных
Во-первых, я хочу искренне поздравить Вас, дорогие друзья с тем, что Вы изучили 50% курса Гарвардского университета CS50 на русском 2016. Неделя 5 это середина курса и является последней Неделей, в которой рассматриваются основы того, что происходит в памяти компьютера, ведь во второй половине курса CS50 2016 мы сосредоточимся на таких темах, как протокол передачи данных HTTP, язык Python, SQL, Javascript и т.д.
Своеобразным ноу-хау Недели 5 является краткий словарь терминов, которые будут представлены под видео и в этой статье для лучшего понимания какие существуют структуры данных. Словарь Недели 5 выглядит следующим образом:
1. Список - list
2. Узел - node
3. Указатель - pointer
4. Очередь - queue
5. Дерево - tree
6. Префиксные деревья - tries
Это даст Вам возможность вдобавок изучить несколько английских слов или воспользоваться Википедией для того, чтобы более углубленно рассмотреть значения этих терминов. На этой лекции мы изучим такие структуры данных, как бинарное дерево, префиксное дерево, хеш-таблицы.
Динамическое выделение памяти
До этой Недели мы пользовались массивами для представления данных в памяти компьютера, но сложность состоит в том, что массивы хороши в том случае, когда Вы определенно знаете, какой размер Вашего массива и сколько свободных байтов необходимо попросить у компьютера. Однако в программировании часто возникает ситуация, когда Вы не можете знать заранее сколько памяти нужно попросить у компьютера, в таком случае нет смысла использовать массивы, обладающие фиксированными значениями.
Для этих целей в программировании существуют связанные списки, которые позволяют динамически получать или отдавать место в памяти компьютера, но, к сожалению, возникает еще одна проблема. Какая именно? Смотрите видео Недели 5 курса Гарвардского университета по основам программирования.
Как реализован стек или очередь queue?
На Неделе 5 курса CS50 на русском рассматривается интересный пример размещения информации в стек. Представьте стопку разносов в столовой или кафе. Идея заключается в том, что когда Вы кладёте разнос на стопку, а потом снова хотите взять разнос, Вы, как правило, берете верхний разнос, а все остальные разносы лежат, как и прежде. Это если бы Вы пришли купить новый iPhone в магазин Apple в первый же день начала продаж, простояли бы в очереди в ожидании открытия магазина и начала продаж, однако, получили бы свой новый iPhone не в порядке очереди, а после тех, кто пришел в магазин последним. С точки зрения логики, если Вы дадите товар сначала людям, которые ближе к выходу, эти люди выйдут из магазина первыми, в результате чего магазин будет постепенно опустошаться. Но вряд ли Вам понравится такой алгоритм продажи новых iPhone.
Такая же ситуация складывается и в стек, но для того, чтобы справедливость восторжествовала и первый элемент в очереди был использован в первую очередь существует такое понятие, как очередь queue.
Разницу между stack и queue можно легко понять, посмотрев короткометражный мультик на 56-й минуте Недели 5.
Код Хаффмана или азбука Морзе?
Скорее всего нет человека, который бы не знал что такое азбука Морзе. На Неделе 5 курса CS50 на русском 2016 проводится аналогия между азбукой Морзе и кодом Хаффмана. Так вот, интересным моментом азбуки Морзе является использование длинных или коротких сигналов для обозначения той или иной буквы. Основным является то, что самый короткий сигнал используется для буквы E. Все дело в том, что при создании своей азбуки, господин Морзе увидел, что некоторые буквы фигурируют в словах чаще других. Поэтому для того, чтобы сделать передачу информации максимально быстрой, было решено передавать самыми короткими сигналами те символы, которые используются чаще всего, а более длинными сигналами - буквы, которые реже всего используются.
Такой же принцип использует код Хаффмана, который служит для сжатия файлов. Принцип сжатия, например, файла Microsoft Word заключается в том, что для хранения в памяти букв, которые чаще всего используются, используется более короткий набор нулей и единиц. Более того, зная принцип работы кода Хаффмана, Вы можете закодировать информацию, а затем с легкостью расшифровать. Если Вы хотите узнать в каком случае сжатый файл может стать большего размера, нежели первоначальный - смотрите перевод на русский язык Недели 5 курса CS50 Гарвардского университета.
В заключении стоит отметить, что практически весь код программ на Неделе 5 сопровождается использованием рекурсии. Рекурсия является очень эффективным инструментом в плане скорости выполнения в случае, когда Вы выбрасываете половину проблемы прочь, как на Неделе 0 при поиске Майка Смитта.
На следующей Неделе мы рассмотрим протокол передачи данных HTTP.
Часть 1 - Часть 2
Смотрите также:
Весь гарвардский курс по основам программирования (CS50 2015 год)
Сайты для обучения программированию
11 ресурсов для бесплатного образования
15 образовательных YouTube каналов на русском языке
Лекции и уроки
Нейросеть сделала компьютерную игру
Игра «Маг кода» для изучения Python, JavaScript, анализа данных, машинного обучения и нейронных сетей