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