Гарвардский курс «Основы программирования CS50»

Вторая часть легендарного курса «Основы программирования CS50» Гарвардского университета, который теперь стал доступен на русском языке. Курс появился еще в 80-е годы прошлого столетия, однако он до сих пор считается самым популярным курсом по программированию как в родном Гарварде, так и в некоторых других университетах Лиги Плюща.

Успех CS50 — во многом заслуга его основателя: профессор компьютерных наук Дэвид Малан является блестящим оратором и не оставляет равнодушным ни одного своего слушателя. Курс будет невероятно интересен и полезен всем тем, кто уже начал (или только решается начать) изучать программирование, идеально подойдет для старшеклассников и студентов.

Описание лекций:

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

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

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

• Узнаем, может ли рекурсия помочь нам в поисках Майка Смита. И вообще, узнаем, что это за загадочный инструмент такой — рекурсия — и как её применять.

• Разберемся, с понятием сортировки слиянием, и поймем, как можно её реализовать с помощью рекурсии. Снова разделяем и властвуем, уже практически по привычке.

• Станем на шаг ближе к пониманию загадочного компилятора Clang и его работе. Продолжим разбираться с тем, что находится «под капотом» программы и оценим путь от исходного кода через ассемблерный к объектному.

• Столкнемся с такими вот знаками: & | ^ ~. Это— не «птичий язык», а побитовые операторы, они позволяют добраться до отдельных битов данных. Для расшифровки каждого из них Дэвид воспользуется весьма необычным инструментом — доской и маркерами! Даже такое «ретро» изредка проскакивает на CS50 =).

• А еще Дэвид приоткроет завесу тайны: в практическом задании вам предстоит вспомнить детство и поиграть в «пятнашки». Только в этот раз они будут написаны на Си.

• Наконец, вы увидите милую беседу Эрика Шмидта из Google и одного бывшего сенатора с каким-то знакомым лицом по имени Барак. Эрик попросил Барака предложить самый эффективный способ отсортировать миллион 32-битных целых чисел. Ответ нынешнего президента США вы узнаете из лекции.

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

Кроме этого:

• Дэвид подробнее расскажет о рекурсии и сравнит циклический и рекурсивный алгоритмы для одной и той же задачи.

• Научит, как менять переменные местами с помощью дополнительного параметра, без него, а также с применением загадочного оператора XOR.

• Продемонстрирует, как нужно отлаживать программку на примере CS50 IDE. Отладка — полезна, она действительно ускоряет процессы разработки в разы, так что это важное умение и в каждой среде разработки его следует усвоить чтобы повысить собственную продуктивность.

• Вы получите ещё немного полезной информации о стеке памяти и локальных переменных.

• Указатели или как в Си напрямую общаться с памятью! Вот мы дошли и до них. Сила и слабость Си, мощнейший инструмент, который в руках новичка или злоумышленника может превратиться в ядерную бомбу.

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

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

• Как кодируется изображение. Слово bitmap станет родным и понятным.

• Вы узнаете, как понять (с точки зрения компьютера), что перед вами именно JPEG-файл и какую роль в этом играет комбинация битов 244 216 255.

• Вспомните (или изучите) 16-ричные числа. Запись 0хff станет столь же очевидной, как 255 а десятичной системе.

• Что такое struct в Си? Собственные типы данных в Си.

• Сравнение содержимого строк в Си (strcmp) и другие средства работы со строками.

• Адресная арифметика.

• char* t = malloc((strlen(s) + 1) * sizeof(char)) — как вам такая строчка кода? После лекции вы будете понимать, что к чему, и сами сможете писать нечто подобное =)

• Немного синтаксического сахара =)

• Как писать swap с указателями и зачем

— Лекция Работа с памятью и указателями, пожалуй, — один из самых сложных моментов CS50. Даже опытные программисты часто ошибаются и заваливают систему из-за утечек памяти, чего уж тут говорить о новичках. Но нам повезло: CS50 — отличный курс, поэтому нам нечего бояться. В 11 лекции мы кое-что изучим, а кое-что повторим вот о чем:

• Почему не стоит ждать ничего хорошего от разыменовывания «мусорных» значений или недействующих указателей.

• scanf(“%i”, &x) — что значит & в этой записи

• char* и string — что между ними общего?

• Как правильно выделять память, чтобы не было ошибки сегментации

• Изучаем работу с памятью на примере функций библиотеки CS50 и… постепенно отказываемся от неё, как от ходунков.

• Valgrind – мощный инструмент для поиска утечек памяти, начинаем с ним работать.

• Связные списки Linkedlist в Си: как с ними работать, чем они лучше массивов, а чем — хуже.

• Что общего у стека и стопки подносов в столовой?

— Лекция Середина курса по основам программирования CS50... Еще остались те, кто считал, что в курсе слишком мало сути и много воды? Очень в этом сомневаемся: последние лекции три-четыре темы вполне себе "взрослые".

Судите сами:

• Эффективная работа со связными списками

• Канонические операции delete, search и insert. Как пройтись по списку, и найти в нем элемент (а также добавить и удалить)

• Манипуляции со стеками и очередями

• Под капотом: как программа распределяется в памяти

• Как с помощью адресов, указателей, связных последовательностей попасть в царство эффективности?

• Бинарные деревья

• Как бы вы сжимали немецкий флаг? Учим алгоритм Хаффмана.

• Хэш-таблицы и мгновенный доступ к данным

... А также глубокие мысли Д.Ф. (об этом в конце лекции).

Впечатляет? Нас тоже. Тем не менее, переживать не стоит: профессионалы Гарварда помогут понять даже такие непростые для начинающих темы.

Комментарии: