show time!
13-я лекция Гарвардского курса по основам программирования CS50 (введение в программирование).
В этой лекции мы с вами займемся веб-программированием и познакомимся с интернет-технологиями. Мы перейдем от командных строк в C к программированию на PHP, JavaScript, познакомимся с Html, CSS, SQL и многим другим.
Середина курса по основам программирования CS50… Еще остались те, кто считал, что в курсе слишком мало сути и много воды? Очень в этом сомневаемся: последние лекции три-четыре темы вполне себе «взрослые».
Судите сами:
— Эффективная работа со связными списками
— канонические операции delete, search и insert. Как пройтись по списку, и найти в нем элемент (а также добавить и удалить)
— манипуляции со стеками и очередями
— под капотом: как программа распределяется в памяти
— как с помощью адресов, указателей, связных последовательностей попасть в царство эффективности?
— бинарные деревья
— как бы вы сжимали немецкий флаг? Учим алгоритм Хаффмана.
— хэш-таблицы и мгновенный доступ к данным
… А также глубокие мысли Д.Ф. (об этом в конце лекции).
Работа с памятью и указателями, пожалуй, — один из самых сложных моментов CS50. Даже опытные программисты часто ошибаются и заваливают систему из-за утечек памяти, чего уж тут говорить о новичках. Но нам повезло: CS50 — отличный курс, поэтому нам нечего бояться. В 11 лекции мы кое-что изучим, а кое-что повторим вот о чем:
• Почему не стоит ждать ничего хорошего от разыменовывания «мусорных» значений или недействующих указателей.
• scanf(“%i”, &x) — что значит & в этой записи
• char* и string — что между ними общего?
• Как правильно выделять память, чтобы не было ошибки сегментации
• Изучаем работу с памятью на примере функций библиотеки CS50 и… постепенно отказываемся от неё, как от ходунков.
• Valgrind – мощный инструмент для поиска утечек памяти, начинаем с ним работать.
• Связные списки Linkedlist в Си: как с ними работать, чем они лучше массивов, а чем — хуже.
• Что общего у стека и стопки подносов в столовой?
В шпионских (или любых других) боевиках, вы, наверное, замечали такую штуку: хакер сидит в темной комнате, весь такой загадочный, подсвеченный монитором своего компьютера и всякими цветными диодами непонятного происхождения. На мониторе — не менее загадочные буковки, обычно зелёные с курсором-нижнее-подчеркивание и малюсенькая карта, на которой где-то в дебрях спрятан интересующий спецслужбы объект. Приходит команда «увеличь этот участок изображения», дабы обнаружить, скажем, номер автомобиля, отражённый в чьем-нибудь глазу… И специалист бесконечно масштабирует картинку, пока отражение не станет ясным и четким…
Вам нравятся такие сцены? Если да, спешим вас огорчить: после 10 лекции CS50 вы уже не будете смотреть их прежними глазами, понимая всю их несуразицу и преувеличение. Впрочем, будущему программисту это необходимо сделать. Это как рано или поздно все узнают правду о Санта Клаусе. С другой стороны, если в мире будет все больше и больше грамотных с точки зрения IT людей, Голливуду придется повысить качество подобных сцен, не лепя случайные наборы терминов куда ни попадя.
А всё дело в том, что фотографии состоят из пикселей (или точек), и когда мы увеличиваем фотографию, рано или поздно мы дойдем до одного пикселя и как бы мы дальше ни увеличивали изображение, дополнительной глубины не появится, перед нами — конечное количество битов. «Это цифра, детка!».
Игра начинается! Настало время поиграть! Большинство людей знакомы с головоломкой «Пятнашки». Если формализовать, «Пятнашки» — это двумерное поле 4х4, в этом поле расположены не 16, а 15 квадратиков, то есть один слот остается пустым. Каждый из квадратиков пронумерован и может двигаться внутри поля по горизонтали или вертикали (если, конечно, есть куда двигаться). Цель — расположить …
Подготовка Прежде, чем браться за задачи, посмотрите лекции 7-8, прочитайте и вникните в «Дополнительные материалы третьей недели». Они посвящены алгоритмам поиска (линейному и бинарному), сортировки (много их!), а также работе дебаггера (умение работать с дебаггером для отладки программ — чрезвычайно важный навык!). Если с лекциями и теорией все пошло, как надо, вы без труда ответите …
Асимптотическая нотация Измерить скорость алгоритма реальным временем — секундами и минутами — непросто. Одна программа может работать медленнее другой не из-за собственной неэффективности, а по причине медлительности операционной системы, несовместимости с оборудованием, занятости памяти компьютера другими процессами… Чтобы измерять эффективность алгоритмов придумали универсальные концепции вне зависимости от среды, в которой запущена программа. Измерение ассимптотической сложности …
Восьмая лекция Гарвардского курса по основам программирования CS50 пройдет в необычной обстановке: Дэвид Малан окажется в окружении зелёных стен библиотеки Вайднера. И пускай они выглядят не так эффектно, как полюбившийся студентам театр Сандерса (та самая огромная торжественная аудитория, в которой обычно проходят занятия), это никак не повлияло на увлекательность лекции!
В седьмой лекции Дэвид Малан расскажет об известных алгоритмах сортировки — пузырьковой, вставки и выбора. Эффективны ли они? Подсказка: не слишком, в чем это проявляется — узнаете из лекции. Но почему они в таком случае знамениты и зачем их изучать? Дело в том, что они довольно просты в реализации, а на их основе можно создавать уже более продвинутые алгоритмы сортировки.
Лекции CS50 лежат здесь: http://samantos.ru/tag/cs50/. В этом материале — 3 задания, теоретические сведения к ним и руководство к действию. Цели • Углубиться в функции и библиотеки • Познакомиться с криптографией, реализовать пару простых шифров Дополнительные материалы reference.cs50.net/ — разъяснение функций библиотек, используемых во время обучения. На английском. http://computer.howstuffworks.com/c.htm стр. 11 – 14 и 39 Подготовка …