Критерии выставления оценки на экзамене.

Учитывается работа только за третий семестр.

За три контрольные = 3 балла (по 1 баллу за задачу).

Две задачи на структуры данных = 4 балла (0 до 2 за каждую задачу в зависимости от сданного объема).

Три задачи на массивы Python = 3 балла (1 балл за каждую задачу).

Вычислительная геометрия или хеш-множества (Python /С++) = 2 балла (по 1 баллу за задачу).

Коллоквиум = 2 балла (от 0 до 2 баллов).

Задача на экзамене = 4 балла.

Устная часть на экзамене (сюда же входят дополнительные вопросы, обычно таких 2 шт.) = 6 баллов (от 0 до 6 баллов).

b=1 если сделана задача на BMP в прошлом семестре, иначе = 0

Итоговая оценка на экзамене = [(К-воБаллов+5+b)/5]

здесь [x]=целая часть от x.

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

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

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

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

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

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

Представление чисел в ЭВМ. Видео.

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

Вещественное с плавающей точкой.  Видео.

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

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

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

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

Видео не удалось записать. Доступны видео предыдущего года, где, в том числе, описаны данные темы: Видео1 и Видео2.

01.03.25

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

IEEE стандарт представления вещественных чисел с плавающей точкой.  Объединения и структуры для работы с битовым представлением числа. Нормализованное и денормализованное представление вещественных чисел.

Вещественные числа с плавающей точкой: понятия underflow и overflow. +/- 0; понятия нечисла и +/- бесконечности.  Видео.

15.03.25

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

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

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

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

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

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

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

Видео.

22.03.25

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

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

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

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

Видео.

29.03.25

7. Язык С: Динамические переменные. Интересная ссылка, в которой описывается понятие системного стека в разных системах. Немного про ассемблер. Расшифровка ассемблерного кода простейшей функции.

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

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

Цикл выполнения команды в терминах счетчика команда и регистра стека. Понятие ассемблерных инструкций goto, call, ret.

Видео.

05.04.25

8. Модель памяти языка С (стек, куча) vs модель памяти языка Python (для каждого объекта: идентификатор (id), тип (type), указатель на значение). Смысл понятия присваивания в Python.

Отладка программ в Linux с помощью valgrind и gdb.

Отладочные функции работы с памятью в Microsoft C (<crtdbg.h>, _malloc_dbg(), _calloc_dbg(), компиляция с ключами /MDd, /MTd, функции _CrtCheckMemory() и _CrtDumpMemoryLeaks(), использование ключа /CRT1).

Видео.

12.04.25

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

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

Язык Python3. Простейшие программы. Все, необходимое для работы с последовательностями.

Видео.

19.04.25

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

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

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

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

Видео.

26.04.25

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

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

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

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

Видео.

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

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

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

03.05.25

12. Язык C. Работа со структурами. Работа с массивами структур. Работа с указателями на массивы структур.

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

Дополнение о работе с массивом объектов различной природы (работа со структурами и объединениями, в том числе, qнеименованными).

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

Указатели на функции. Сортировка массивов с помощью стандартной функции языка C qsort.

Видео.

10.05.25

13. C++. Простые классы. Полиморфизм. Переопределение операторов. Ссылки (&). const.

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

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

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

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

Сортировки (С++). Алгоритм HeapSort. Теорема о времени работы алгоритма HeapSort.

Видео.

17.05.25

14. Написание кода функции HeapSort. Теорема о времени приведения массива к *-упорядоченному состоянию (к пирамиде).

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

Видео.

24.05.25

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

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

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

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

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.

01.09.25

16. C++. Предельный минимум для определения простого класса вектор. Исключения. Создание своих типов для исключений. Определение бинарных операторов и операторов преобразования типа. Упоминание о сложных преобразованиях типов. Видео.

06.09.25

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

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

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

Касты: static-cast, const-cast, reinterpret-cast. Видео.

volatile Видео (взято с предыдущего года).

13.09.25

18. C++. friend.

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

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

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

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

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

15.09.25

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

Параметры по умолчанию.

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

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

Что делают компилятор и линковщик (сборщик)? Внутренние имена переменных. Использование программ nm либо cc /FAS . (посмотрите также лекцию №7).

static и inline функции. inline методы в классах. Проблемы, связанные с inline-функциями. Видео (с великолепной ненайденной ошибкой).

20.09.25

20. static и inline функции. inline методы в классах. Проблемы, связанные с inline-функциями. Разбор ошибки предыдущей лекции.

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

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

27.09.25

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

Определение полноценной структуры данных вектор. Задание шаблона дружественной функции внутри шаблона класса.

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

Видео.

29.09.25

22. Структуры данных. Списки. Однонаправленные списки. Реализация однонаправленных списков с помощью умных указателей. Что не так?

Видео.

04.10.25

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

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

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

Видео.

11.10.25

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

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

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

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

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

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

Range-based for. Range-based for для новых классов.

Видео.

13.10.25

25. Необходимость определений для итераторов:

using iterator_category = std::forward_iterator_tag;// std::random_access_iterator_tag;

using difference_type = std::ptrdiff_t;

using value_type = T;

using pointer = value_type*;

using reference = value_type&;

Поиск элементов в контейнере.

Использование typename, auto, decltype.

Переопределение операторов new/delete. Короткая реализация для gcc.

Видео.

18.10.25

26. Переопределение операторов new/delete. Исправление недочетов; реализация для Microsoft C++.

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

Реализация стека на С++ на базе вектора.

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

Существенные различия в STL в реализации стека (как адаптера дека) и вектора.

Структура данных Очередь.

STL. Контейнеры queue и priority_queue.

Видео.

24.10.25

27. Переопределение операторов new/delete. Запоминание места отведения памяти.

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

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

initializer_list.

Структуры данных. Списки (однонаправленные, двунаправленные, циклические). Два понимания понятия список: с текущим элементом и текущим положением в списке. Ссылочная и бессылочная реализации на С++.

Бессылочная реализация L2-списка с текущим положением.

STL. Контейнер list. Итераторы вставки. insert_iterator, front_insert_iterator, back_insert_iterator, inserter, front_inserter, back_inserter.

Видео.

26.10.25

28. Ссылочная реализация L2-списка с текущим элементом.

Использование using и value_type. Использование typename.

Использование итераторов вставки: insert_iterator, front_insert_iterator, back_insert_iterator, inserter, front_inserter, back_inserter для собственного списка.

Циклические списки. Итераторы для циклических списков.

Алгоритмы for_each и copy.

Профессиональная реализация однонаправленного списка на языке С++ (с собственным выделением памяти).

Видео.

31.10.25

29. Циклические списки. Итераторы для циклических списков.

Профессиональная реализация однонаправленного списка на языке С++ (с собственным выделением памяти).

Реализация L2-списка с помощью умных указателей. weak_ptr.

Язык С++. Исключения. Исключения Microsoft (SEH = Structured Exception Handling). Как посчитать гармоническое среднее без использования оператора if ? (Microsoft C).

__try, __except, __finally, __leave, GetExceptionCode().

Взаимоотношения между стандартными и структурированными исключениями Microsoft.

Видео.

08.11.25

30. Бинарные деревья. Деревья поиска. Определение. Основные операции.

C++. Реализация шаблона бинарного дерева поиска по аналогии с контейнером set. Определение статических элементов шаблонов. Использование typename.

Видео.

10.11.25

31. Использование шаблона pair (в том числе, если элемент пары является шаблоном внутри шаблона для случая определения шаблона метода вне шаблона класса) при реализации добавления элемента в дерево по аналогии с контейнером set.

insert() / erase().

Использование создания локальной переменной в условии if.

Определение универсальной инициализации переменной вида Tree<int> t=v .

Видео.

15.11.25

32. Скрытое преобразование к логическому типу.

Поиск элемента дерева поиска по порядковому номеру. Коррекция методов удаления и вставки элемента для обеспечения возможности поиска элемента по порядковому номеру.

Объединение и разбиение деревьев.

Сбалансированные, идеально сбалансированные, идеально сбалансированные’ деревья. Определения. Теоремы о вложении определений. Теорема о связи высоты идеально сбалансированного дерева и количества его вершин. Построение идеально сбалансированного и идеально сбалансированного’ деревьев.

Оценка высоты сбалансированного дерева через количество элементов в сбалансированном дереве.

Видео.

22.11.25

33. Сбалансированные деревья. Вставка элемента. Удаление элемента. Объединение и разбиение сбалансированных деревьев.

Задача создания структуры данных для хранения множества непересекающихся отрезков на числовой прямой.

Видео.

24.11.25

34. Красно-черные деревья. Красно-черные’ деревья. Определения. Связь между высотой и количеством элементов в красно-черных деревьях.

Добавление элемента в красно-черное дерево за два прохода. Модификация алгоритма для однопроходного добавления элемента в красно-черное дерево.

Удаление элемента из красно-черного дерева (за два прохода).

Видео.

29.11.25

35. Задача создания структуры данных для хранения множества непересекающихся отрезков на числовой прямой.

C++. Лямбда-функции без захвата и с захватом. STL. Контейнеры set, multiset, map, multimap. Задача нахождения K самых больших [различных] чисел среди элементов последовательности по модулю M.

B-деревья. Определение.

Видео.

06.12.25

36. Оценка высоты B-дерева через количество элементов в нем.

Алгоритмы однопроходного и двухпроходного добавления элемента в B-дереве.

Алгоритм удаления элемента в B-дереве.

Два определения B-дерева (B / B’ деревья).

2-3-Дерево.

B⁺-Дерево.

Видео.

08.12.25

37. 2-3-Дерево. Алгоритм удаления элемента.

STL. Работа с кучей (make_heap, push_heap, pop_heap).

Графы. Поиск пути в графе с наименьшим количеством шагов. Алгоритм волны.

Видео.

13.12.25

38. Оценки времени работы алгоритма волны.

Геометрическое представление графа. Теорема о существовании геометрического представления графа.

Планарные графы. Плоская укладка планарного графа. Теорема о существовании плоской укладки (без доказательства).

Деревья. Листья ориентированных и неориентированных деревьев. Лемма о существовании плоской укладки для конечного дерева.

Лемма о приведении неориентированного дерева к ориентированному. Теорема Эйлера. Лемма о связи в графе количества вершин, ребер и связных компонент.

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

Задача о нахождении кратчайшего пути в графе. Алгоритм Дейкстры (простой и STL-модифицированный).

Видео.