Во всех видео-лекциях есть оговорки. Я знаю о них, но давайте я оставлю их выявление вам в качестве развлечения J . Можете даже не сообщать мне о них.


Темы реальных лекций курса Работы на ЭВМ. Мехмат МГУ. 2026 г.

I семестр (весна)

Текст, написанный на лекциях.

 

07.02.26
1. Понятие виртуальной памяти. Основы реализации.

Представление чисел в ЭВМ. Стандартные представления (целое без знака).

Видео.

 

14.02.26
2. Little/big-endian. Целое со знаком (прямой, обратный, дополнительный код). Вещественные числа с фиксированной точкой. Currency.

Вещественные числа с плавающей точкой: нормализованное и ненормализованное представления. Язык C: union. assert.

 Видео.

 

21.02.26

21.02.26
3. Вещественные числа с плавающей точкой. IEEE стандарт представления. Не числа.

Точность представления вещественного числа.

Машинное эпсилон (два определения). Связь машинного эпсилон с точностью представления вещественных чисел с плавающей точкой.

Абсолютные и относительные ошибки. Теоремы об ошибках сложения/вычитания/умножения/деления.

Написание примеров программ на тему битового представления вещественных чисел.

Какие числа можно точно представить в виде вещественного числа с плавающей точкой.

Задача о том, что можно ли представить точно в виде числа типа float все целые числа от 0 до миллиона.

Задача о нахождении корней уравнения ax2+bx+c=0.

Видео.

 

28.02.26

4. Задача о нахождении корней уравнения ax2+bx+c=0. Понятия корректных и некорректных задач.

Нестандартные представления чисел в ЭВМ. Number из СУБД Oracle.

Язык C. Что больше: минус два или два? Чему равно минус два поделить на два? Чему равно минус два умножить на два? Чему равно ((char)50)*((char)50) ?

Типы переменных в языке С, в том числе size_t, структуры, объединения. Соответствующие форматы для работы с функциями ввода/вывода и литералы, соответствующие типам переменных. Константы. Макроопределения.

Видео.

 

07.03.26

5. Понятие алгоритма. Время работы алгоритма.

Сведение задач и алгоритмов.

Определения верхних и нижних оценок времени работы алгоритма. 

Теоремы о верхних и нижних оценках при сведении задач.

Понятие сложности (по времени выполнения и по памяти) /средней сложности/амортизационной сложности алгоритма.

Понятия O, o, Θ, Ω.

Видео.

 

 

14.03.26

6. Сортировки. Определение. Существование и единственность сортировки.

Достаточность использования (определения) одной операции меньше для осуществления сортировки.

Сортировка пузырьком. Случай оптимальности сортировки пузырьком. Верхняя и нижняя оценки времени решения задачи сортировки для случая, когда время сравнения элементов=0, время обмена местами двух элементов=Θ(|i-j|). Директива препроцессора #define. Правила хорошего тона при оформлении #define. 

Сортировка слиянием с рекурсией.

Видео.

 

 

21.03.26

7. Сортировки, основанные на сравнениях. Дерево решения. Теорема о нижней оценке времени решения задачи сортировки алгоритмами, основанными на сравнениях.

Введение в OpenMP. Распараллеливание сортировки слиянием с рекурсией. Распараллеливание секций.  

Сортировка слиянием без рекурсии.

Распараллеливание сортировки слиянием без рекурсии. Распараллеливание циклов.  Теоремы о времени работы алгоритмов сортировки слиянием с рекурсией и без рекурсии и о количестве требуемой памяти.

Сортировка в языке C стандартной функцией qsort().

Видео.

 

Дополнительная полезная лекция с семинара: всё, что нужно знать про язык С++ в этом семестре.

 

28.03.26

8. Написание кода функции HeapSort. Теорема о времени приведения массива к *-упорядоченному состоянию (к пирамиде). Теорема о времени работы алгоритма HeapSort и требованиях к дополнительной памяти.

QSort. Идея. Теорема о верхней оценке времени работы алгоритма QSort. Требования к памяти QSort.

Реализация QSort.

Видео.

 

04.04.26

9. Теорема об оценке времени работы алгоритма QSort в среднем.

Цикл выполнения команды. Возможные различия реализации if/else if и switch. goto/call/rtn в терминах регистра с адресом текущей команды и регистра стека. Команды на компьютере, выходящие за рамки элементарных операций в рамках алгоритмов, основанных на сравнениях.

Устойчивые сортировки. Сортировки с временем работы O(n). Сортировка подсчетом.

Видео.

 

 

11.04.26

10. Цифровая сортировка.

Поиск элемента в отсортированном массиве. Понятие структур данных. Плоские множества. Понятие  lower_bound, upper_bound. Почему и когда left+(right-left)/2 лучше, чем (left+right)/2 ?

Язык С: Статические, динамические, автоматические переменные. Время жизни и область видимости переменных в языке С.

Отведение памяти в куче (malloc,…) и в стеке (alloca). _malloca()/_freea().

Видео.

 

Лекции с семинарских занятий.

Первая дополнительная лекция по работе с изображениями BMP (общие понятия + работа BMP в формате TrueColor).

Вторая дополнительная лекция по работе с изображениями BMP (формат с палитрой).

 

 

18.04.26

11. Связь автоматических переменных с системным стеком. Немного про ассемблер. Расшифровка ассемблерного кода простейшей функции.

Локальные автоматические массивы переменного размера в языке C. VLA. Преобразование типов с использованием VLA.

Механизмы передачи параметров в функции языка C через стек и регистры.

Принцип работы в языке C функций с переменным количеством параметров в случае различных механизмов передачи параметров в функцию. Пример аналога printf() (с использованием стандартных макросов va_list, va_start, va_arg, va_end) с несколькими форматными строками.

Видео.

 

25.04.26

12. Язык C. Работа со структурами. Работа с массивами структур. Работа с массивами указателей на структуры. Работа с объектами, содержащими подобъекты различной природы, без структур.

Полезно зайти в семинарские видео I-го курса и посмотреть видео с написанием примера списка студентов.

Плавный переход на C++. Простые классы. Инкапсуляция. Полиморфизм. Отведение памяти (создание объектов). Конструкторы. [Деструкторы]. Inline-функции.

Задание функций вне класса.

Видео.

 

02.05.26

13. C++. Переопределение операторов. Методы по умолчанию (=default). Параметры по умолчанию. Ссылки (&). const. Сложные преобразования типа. Конструктор копирования. Создание временных объектов в формулах.

Конструктор копирования. Задание функций вне класса. Создание временных объектов в формулах.

Оператор преобразования типа. Кратко про использование ввода/вывода в языке C++.

istream/ostream , “iostream”, cin, cout, fstream

Очень коротко про шаблоны.

Несколько слов про алгоритмы. Очень коротко про простейшие лямбда-функции.

Видео.

 

 

16.05.26

14. Порядковые статистики. Простой алгоритм поиска порядковой статистики (алгоритм Stat0).

Поиск порядковой статистики за линейное время в среднем (алгоритм QStat1).

Поиск порядковой статистики последовательности целых чисел {ai} (i=1,…,n) за линейное время для случая ai=O(n) (алгоритм CStat).

Теоремы о времени работы алгоритмов Stat0, CStat, QStat.Теорема о времени работы в среднем алгоритма QStat.

Поиск порядковой статистики в общем случае с верхней оценкой времени работы алгоритма Θ(n). Доказательство оценки.

Медианная фильтрация изображений.

Видео.

 

 

23.05.26

15. Язык C++. Структуры данных. Работа со списками. Однонаправленный список с фиктивным элементом.

Хеширование. Метод многих списков (закрытая адресация?). Оценки на максимальное и среднее время добавления, поиска, удаления элементов в структуре данных на основе хеширования методом многих списков. Стратегия работы с подобной структурой данных для обеспечения среднего времени выполнения основных операций за время = O(1).

Видео.

 

II семестр (осень)

К концу семестра студенты должны уметь пользоваться следующими понятиями языка С++ (ver.11):

0) правила трех, пяти, нуля (это основа!);

1) семантика перемещения и rvalue-ссылки (зачем числу 5 может понадобиться что-то присваивать?);

2) лямбда-функции (двух типов);

3) "умные" указатели (например, надо знать, как их использовать в списках, и почему это делать нельзя);

4) range-based циклы + initializer_list (уметь делать свои классы доступными для range-based циклов);

5) default, delete;

6) auto, decltype;

7) nullptr;

8) static_assert.

 

 

02.09.26

16. Хеширование. Открытая адресация. Добавление, удаление, поиск элемента в стандартном хеш-множестве с открытой адресацией. Реализация хеш-множества с заглушками для удаляемых элементов. Модификация перебора элементов в хеш-множестве, реализованном в Python. Хеш-функция на основе деления для строк.

Видео.

05.09.26

17. Простые классы. Исключения. Всё что нужно для понимания простых классов (=написания первой контрольной работы). Неименованные переменные.

 Сложные классы. Отведение памяти. Все необходимое для понимания фразы a=b+c.

Правило трех.

Видео.

 

12.09.26

18. Стандартное и нестандартное поведение C++ в компиляторе gcc.

Касты: static-cast, const-cast, reinterpret-cast. volatile.

C++. friend.

Конструкторы (в т.ч. конструктор копирования), деструкторы.

Move-constructors, move-assignment. Правило пяти.  

Определение структуры данных вектор.

L-value. Понятие identity.

R-value. Понятия литералов, временных переменных, неименованных переменных. R-value и L-value ссылки.

Видео.

 

16.09.26

19. L-value. Понятие identity. R-value. Понятие материализации для prvalue в C++17. Стандартная классификация объектов C++.

Явный вызов move-операций.

Как использовать ссылки на возвращаемое из функции значение?

Конструкторы (в т.ч. конструктор копирования, конструкторы для OpenMP, вызов конструкторов для переменных класса). Порядок инициализации объектов класса.

Что делать при разных расстановках скобок в формуле a=b+c+d+e ? Как интерпретируется *this в плане r-value/l-value ссылок? Куда приписать битовые поля и строковые константы?

Видео.

 

19.09.26

20. Что делают компилятор и линковщик (сборщик)? Внутренние имена переменных. Архитектура x86-64: Понятия таблицы релокаций и таблицы символов. Модели памяти: small/medium/large. Статическое vs динамическое выделение памяти для больших массивов.

Видео.

 

26.09.26

21. Использование программ nm либо cc /FAs . static и inline функции. inline методы в классах. Проблемы, связанные с inline-функциями.

С++. Шаблоны (templates). Типовые и целые параметры шаблонов. Определение функций шаблона в отдельном cpp-файле.

Видео.

 

30.09.26

22. Понятие функциональных объектов. Возвращение к сортировке. Упоминание алгоритмов STL. Range-based for.

Умные указатели. unique_ptr.

Видео.

 

03.10.26

23. Структуры данных. Списки. Однонаправленные списки. Реализация однонаправленных списков с помощью умных указателей. static и inline static (С++17) переменные в классах. Использование nullptr, nullptr_t.

Что не так?

shared_ptr. Работа с классами, элементами которых являются только полноценные (сложные) классы/объекты. Правило нуля.

Видео.

 

10.10.26

24. Реализация вектора бесконечной длины.

Реализация вектора (a’la Python) на основе умных указателей.

Структуры данных. Вектор.

Александр Степанов. Менг Ли. Руководство по стандартной библиотеке шаблонов (STL).      

Мэтью Уилсон. Расширение библиотеки STL для С++. Наборы и итераторы.        

STL. Понятия контейнеров, алгоритмов, функциональных элементов, работы с потоками.

STL. Контейнер vector.

Итераторы, reverse итераторы, constant итераторы (в стиле STL).