Основы программирования — зимний семестр 2026/27

Первый семестр курса «Основы программирования» (СПбГУ). Здесь публикуются конспекты занятий: их можно читать до занятия как подготовку или после — как справочник при выполнении домашнего задания.

Как устроен курс

Занятия чередуются между двумя линиями:

• Линия языка — C и C++ (нечётные занятия, лекции с практикой): сборка, типы, функции, классы и ООП, строки, умные указатели, STL, move-семантика, шаблоны. Местами Python — для контраста и прототипов.
• Линия алгоритмов (чётные занятия, семинары): сложность и O-символика, рекуррентные соотношения, структуры данных, двоичный поиск, сортировки, амортизационный анализ.

Контроль: домашние задания после семинаров (сдача через Git + контест на HackerRank) · два рубежных контроля · зачёт с оценкой.

Инструменты: компилятор (GCC/Clang/MSVC) + редактор, Git для сдачи заданий, санитайзеры, Compiler Explorer. Всё настраивается на первом занятии.

Конспекты

Конспект каждого занятия открывается в день самого занятия — список пополняется по ходу семестра.

• Занятие 0. Вступление: от перфокарт до LLM

  история разработки, хронология стандартов C++ и эпоха LLM-ассистентов.

• Занятие 1. Сборка C++: от кода до .exe

  конвейер сборки, заголовочные файлы, include guards, окружение под три ОС.

• Занятие 2. Анализ сложности алгоритмов

  Фибоначчи четырьмя способами, O-символика, иерархия скоростей роста.

• Занятие 3. Типы данных: во что упаковываем данные?

  биты и байты, IEEE 754, массивы, указатели и ссылки, size_t.

• Занятие 4. Элементарная арифметика

  длинные числа, умножение Карацубы, первые шаги в Git.

• Занятие 5. Управление программой: функции и потоки выполнения

  стек вызовов, перегрузка, ветвления, циклы и их ловушки.

• Занятие 6. Рекуррентные соотношения

  дерево рекурсии, основная теорема с доказательством, формула Бине.

• Занятие 7. Классы и ООП: основа основ

  инкапсуляция, RAII, правила трёх/пяти/нуля, полиморфизм и vtable.

• Занятие 8. Базовые структуры данных

  массив против списка и кэш, динамический массив, стек, очередь, дек.

• Занятие 9. Строки: от C-стиля до modern C++

  C-строки, std::string и SSO, string_view, UTF-8 по байтам.

• Занятие 10. Амортизационный анализ и динамические структуры

  методы усреднения и монеток, MinStack, очередь на двух стеках.

• Занятие 11. Ключевые слова: волшебные слова C++

  const и семья, три смысла static, this, new/delete, auto, enum class.

• Занятие 12. Двоичный поиск

  инвариант, границы вхождений, поиск по ответу, вещественный поиск, два указателя.

• Занятие 13. Рубежный контроль № 1

  формат, критерии, карта тем и тренировочный вариант с разбором.

• Занятие 14. Умные указатели, функции и лямбды

  unique_ptr и владение как тип, shared/weak и циклы, лямбды против qsort.

• Занятие 15. Префиксные суммы и RMQ

  предпосчёт как инвестиция, разностный массив, 2D префиксы, Sparse Table за O(1).

• Занятие 16. std::vector, std::chrono, std::thread

  устройство vector и инвалидация, честные замеры, потоки и гонка данных, операторы.

• Занятие 17. Контейнеры и алгоритмы STL

  карта контейнеров с ценами, категории итераторов, ловушки алгоритмов, компараторы. {class=“children children-type-tree children-sort-weight”}