CS50 на русском | Гарвард, Основы программирования

Знакомство с курсом.

родной язык компьютеров — двоичная система счисления
• ASCII — как записываются символы
• как алгоритмизировать задачи — на живых примерах. Очень живых=)
• почему Дэвид разорвал телефонный справочник или что такое двоичный поиск
• сложность алгоритма — что, как и почему
• о том, что такое циклы, расскажет никто иной, как Марк Цукерберг, основатель Facebook
• …а еще вы увидите его же в 2005 году, в качестве приглашенного гостя CS50. Хм… судя по аудитории, интерес к технологиям вырос в десятки раз!

Студенты этого представителя «Лиги плюща» с энтузиазмом приняли гарвардскую команду, и узнали много нового из лекции, а именно:

Что такое алгоритмы. Казалось бы, такое простое понятие, но на самом деле алгоритмизовать даже столь элементарный процесс, как намазывание арахисового масла на тост совсем не просто. Ребята вам это покажут на практике=). Как эффективно посчитать количество людей в аудитории? У нас есть такой алгоритм. Есть такое английское выражение “From Scratch”. Переводится оно как «С самого начала». Но можно также перевести как «Начиная со Scratch», если слово Scratch понимать как специальный учебный язык программирования. Так вот, вас познакомят со Scratch — замечательной разработкой Массачусетского технологического университета и покажут, как писать с её помощью программки.

Язык программирования C. На примере простейшей программы Дэвид растолкует основные конструкции языка, пользуясь аналогиями с изученными на нулевой неделе «пазлами» Scratch; Облачная IDE, в которой мы будем писать программы на C и не только; Вот такие штуки: jharvard@ide50:~/workspace $ make hello. Выглядит как заклинание? К концу лекции станет понятно, что к чему. Это одна из команд Linux. Выучим еще парочку необходимых для запуска приложений из командной строки. И немного интересных фактов о первом программируемом американском компьютере (из тех, что целую комнату занимают), а также о первом обнаруженном баге=).

Гарвардский курс по основам программирования CS50: лекция #4: углубляемся в C и делаем первые задания

В четвертой лекции мы углубимся в язык С и изучим всё необходимое для выполнения первых трех серьезных заданий по программированию. Это циклы, условия, типы данных, переменные и функции.

Задания, к слову весьма разнообразные, совсем не скучные. Выполнив их, вы отточите использование библиотек, ввод/вывод и циклы вместе со знаменитым водопроводчиком Super Mario, посчитаете, сколько воды вы расходуете во время душа и запрограммируете первый относительно серьезный алгоритм для вычисления минимального количества монеток для выдачи сдачи.

Задания не слишком сложные, но требуют от новичков задействовать всё, что было выучено на третьей и четвертой лекции, плюс немного подумать. Смело к работе, а если что-то не получается, задавайте вопросы, мы будем рады помочь=).

- Баги. Без этих верных спутников разработчиков никуда не деться, нужно научиться их выискивать. Дэвид расскажет о некоторых типах багов. Начнет с тех, которые сложнее выцепить: логических;

- Откровение: бесконечный цикл на самом деле не такой уж и бесконечный;
- Функциональная декомпозиция: прием для повышения читаемости кода и удобства кодирования;
- Знай свои фигурные скобки: область действия переменных;
- Объявление функций до реализации: специально для C;
- Строки и как с ними работать;
- Что такое ошибка сегментации;
- Милые щеночки! В стриме. Не пропустите=).
- Как едят шоколадки и M&M’s в Гарварде. Наглядное пособие.

Каждый раз, когда вы ловите себя на том, что копируете и вставляете куски кода, спрашивайте себя: а нет ли другого способа? В шестой лекции Гарвардского курса по основам программирования CS50 будет много полезного для нахождения «других способов», но и веселья хватит сполна.

Кстати, её будет вести молодой лектор Роб Боуден. Но Дэвид Малан также вертикально поприсутствует=). Что значит «вертикально»? Узнаете в начале лекции.

Ну а потом начнется серьезная работа:

Роб объяснит, что такое массивы, одномерные и многомерные; • что такое аргументы командной строки, какова их связь с элементами массивов и как их использовать непосредственно в программах; • Немного приоткроет завесу тайны над тем, что такое криптография (но подробнее о шифрах узнаете из дополнительных материалов).

Смотрите лекцию, читайте о шифрах, и… не забывайте решать побольше задач!

Помните разорванный телефонный справочник из самой первой лекции CS50? В седьмой лекции он возвращается! Возвращается, чтобы сделать фразу «эффективность алгоритмов» не пустым звуком, а пояснить на примере. Все программисты думают о скорости работы программы и о том, сколько памяти она при этом «съест». На учебных задачках это не так очевидно, но когда мы работаем с большими массивами данных (как почти везде в «Энтерпрайзе»), эти вопросы становятся первоочередными.

Представьте себе, что данные в телефонном справочнике не отсортированы по алфавиту. Представляете, сколько времени у нас бы ушло на то, чтобы его там найти? С учётом того, что в телефонном справочнике нет человека с таким именем, пришлось бы перебирать все строчки подряд — и всё впустую! Но есть выход: данные всегда можно отсортировать.

И в седьмой лекции Дэвид Малан расскажет об известных алгоритмах сортировки — пузырьковой, вставки и выбора. Эффективны ли они? Подсказка: не слишком, в чем это проявляется — узнаете из лекции. Но почему они в таком случае знамениты и зачем их изучать? Дело в том, что они довольно просты в реализации, а на их основе можно создавать уже более продвинутые алгоритмы сортировки.

А еще, вы услышите, как звучат алгоритмы сортировки. Незабываемая музыка программирования уже доступна в переводе седьмой лекции.

Восьмая лекция Гарвардского курса по основам программирования CS50 пройдет в необычной обстановке: Дэвид Малан окажется в окружении зелёных стен библиотеки Вайднера. И пускай они выглядят не так эффектно, как полюбившийся студентам театр Сандерса (та самая огромная торжественная аудитория, в которой обычно проходят занятия), это никак не повлияло на увлекательность лекции! В этот раз мы:

Узнаем, может ли рекурсия помочь нам в поисках Майка Смита. И вообще, узнаем, что это за загадочный инструмент такой — рекурсия — и как её применять. Разберемся, с понятием сортировки слиянием, и поймем, как можно её реализовать с помощью рекурсии. Снова разделяем и властвуем, уже практически по привычке. Станем на шаг ближе к пониманию загадочного компилятора Clang и его работе. Продолжим разбираться с тем, что находится «под капотом» программы и оценим путь от исходного кода через ассемблерный к объектному. Столкнемся с такими вот знаками: & | ^ ~. Это— не «птичий язык», а побитовые операторы, они позволяют добраться до отдельных битов данных. Для расшифровки каждого из них Дэвид воспользуется весьма необычным инструментом — доской и маркерами! Даже такое «ретро» изредка проскакивает на CS50 =). А еще Дэвид приоткроет завесу тайны: в практическом задании вам предстоит вспомнить детство и поиграть в «пятнашки». Только в этот раз они будут написаны на Си. Наконец, вы увидите милую беседу Эрика Шмидта из Google и одного бывшего сенатора с каким-то знакомым лицом по имени Барак. Эрик попросил Барака предложить самый эффективный способ отсортировать миллион 32-битных целых чисел. Ответ нынешнего президента США вы узнаете из лекции.

Гарвардский курс, основы программирования CS50, лекция 9: обман с помощью программирования, рекурсия, указатели и отладка приложений

Девятая лекция CS50 получилась очень интересной и разнообразной по содержанию. В ней задействованы даже автомобили VW =). Конечно, не непосредственно, но в качестве весьма удачного примера того, как с помощью простых программных команд можно написать сложную программу и обмануть профессиональную комиссию, проверяющую систему контроля выхлопа. Да, руководствуясь некоторыми параметрами приложение может понять, что его подопечную машинку сейчас тестирует и выдаст нужный ревизорам результат.

Примерно так же работает и вредоносное ПО, запуская незаметных «троянских коней» в системы. На занятии Дэвид расскажет общие принципы работы такого ПО, почему, даже досконально изучив код приложения, нельзя быть уверенным в его честности и какова роль «протокомпилляторов» в этом процессе.

Кроме этого:

Дэвид подробнее расскажет о рекурсии и сравнит циклический и рекурсивный алгоритмы для одной и той же задачи. Научит, как менять переменные местами с помощью дополнительного параметра, без него, а также с применением загадочного оператора XOR. Продемонстрирует, как нужно отлаживать программку на примере CS50 IDE. Отладка — полезна, она действительно ускоряет процессы разработки в разы, так что это важное умение и в каждой среде разработки его следует усвоить чтобы повысить собственную продуктивность. • Вы получите ещё немного полезной информации о стеке памяти и локальных переменных. Указатели или как в Си напрямую общаться с памятью! Вот мы дошли и до них. Сила и слабость Си, мощнейший инструмент, который в руках новичка или злоумышленника может превратиться в ядерную бомбу.

Гарвардский курс по основам программирования CS50, 10 лекция, конец 4 недели

В шпионских (или любых других) боевиках, вы, наверное, замечали такую штуку: хакер сидит в темной комнате, весь такой загадочный, подсвеченный монитором своего компьютера и всякими цветными диодами непонятного происхождения. На мониторе — не менее загадочные буковки, обычно зелёные с курсором-нижнее-подчеркивание и малюсенькая карта, на которой где-то в дебрях спрятан интересующий спецслужбы объект. Приходит команда «увеличь этот участок изображения», дабы обнаружить, скажем, номер автомобиля, отражённый в чьем-нибудь глазу… И специалист бесконечно масштабирует картинку, пока отражение не станет ясным и четким…

Вам нравятся такие сцены? Если да, спешим вас огорчить: после 10 лекции CS50 вы уже не будете смотреть их прежними глазами, понимая всю их несуразицу и преувеличение. Впрочем, будущему программисту это необходимо сделать. Это как рано или поздно все узнают правду о Санта Клаусе. С другой стороны, если в мире будет все больше и больше грамотных с точки зрения IT людей, Голливуду придется повысить качество подобных сцен, не лепя случайные наборы терминов куда ни попадя.

А всё дело в том, что фотографии состоят из пикселей (или точек), и когда мы увеличиваем фотографию, рано или поздно мы дойдем до одного пикселя и как бы мы дальше ни увеличивали изображение, дополнительной глубины не появится, перед нами — конечное количество битов. «Это цифра, детка!».

После четвертой лекции вы сможете приступить к задачнику CS50 для четвертой недели. Он позволит вам прикоснуться к миру графики и криминальной экспертизы: вы напишете коды для восстановления утраченных изображений и изменения масштаба картинок.

Итого, из лекции вы узнаете:

Как кодируется изображение. Слово bitmap станет родным и понятным. Вы узнаете, как понять (с точки зрения компьютера), что перед вами именно JPEG-файл и какую роль в этом играет комбинация битов 244 216 255. Вспомните (или изучите) 16-ричные числа. Запись 0хff станет столь же очевидной, как 255 а десятичной системе. Что такое struct в Си? Собственные типы данных в Си. Сравнение содержимого строк в Си (strcmp) и другие средства работы со строками. Адресная арифметика. char* t = malloc((strlen(s) + 1) * sizeof(char)) — как вам такая строчка кода? После лекции вы будете понимать, что к чему, и сами сможете писать нечто подобное =) Немного синтаксического сахара =) Как писать swap с указателями и зачем

Ну и, чтобы расслабиться, напоследок вы посмотрите пластилиновый мультфильм. Не просто мультфильм, но мультфильм про указатели. А если после этого произведения искусства вы только напряжётесь, DJ к вашим услугам.