Во всех видео-лекциях есть оговорки. Я знаю о них, но давайте я оставлю их выявление вам в качестве развлечения 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 до миллиона.

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

Видео.

28.02.26

4. Задача о нахождении корней уравнения ax²+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).

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

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

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

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

Видео.

23.05.26

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

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

Видео.

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

Хеширование. Открытая адресация.