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

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

За три контрольные = 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 . Можете даже не сообщать мне о них.

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

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

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

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

Представление чисел в ЭВМ. Целое со знаком (прямой, обратный, дополнительный код). Видео.

17.02.24
 2. Вещественные числа с фиксированной точкой. Currency.

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

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

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

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

Видео.

24.02.24

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

Пример решения квадратного уравнения.

Нестандартные представления чисел в ЭВМ.

Видео.

02.03.24

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

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

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

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

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

Видео.

09.03.24

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

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

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

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

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

Видео.

16.03.24

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

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

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

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

Язык Python3. Модель памяти языка Python (для каждого объекта: идентификатор (id), тип (type), значение). Смысл понятия присваивания в Python. Простейшие программы. Все, необходимое для работы с последовательностями.

Видео.

23.03.24

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

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

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

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

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

Видео.

30.03.24

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

Сортировки слиянием с рекурсией и без рекурсии. Теоремы о нижних оценках времени решения задачи слияния массивов из n и n элементов и из n и n+1 элемента. Отличия ситуации, описанной в теореме, от запрограммированного алгоритма Merge. Попытка исправить ситуацию с помощью оператора switch. Особенности реализации оператора switch.

Использование #define для автоматизации отведения/очистки памяти.

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

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

Программа для написания функции Merge без использования циклов.

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

Видео.

06.04.24

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

Вопрос на понимание: какие ошибки присутствуют в функции ввода структур из файла и к каким последствиям приведут эти ошибки?

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

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

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

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

Видео.

13.04.24

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

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

Отведение памяти

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

Видео.

20.04.24

11. Алгоритм HeapSort. Теорема о времени приведения массива к*-упорядоченному состоянию (к пирамиде).

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

Видео.

30.04.24

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

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

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

Понятие растрового изображения. TrueColor, изображения с палитрой, серые изображения. BMP. Бинарный ввод/вывод.

Видео.

04.05.24

13. Ввод/вывод BMP. Простейшие преобразования изображений. Бинарный ввод/вывод.

Преобразование RGB-изображения и изображения с палитрой в серое.

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

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

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

Видео.

11.05.24

14. Порядковые статистики.

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

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

Фильтрация серых изображений. Медианная фильтрация. Теоремы о времени работы алгоритмов медианной фильтрации (med_filter и med_filter_q).

Видео.

18.05.24

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.24

16. Язык C++. Структуры данных. Хеширование. Метод линейных проб. Хеш-функция на основе деления.

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

07.09.24

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

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

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

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

14.09.24

18. C++. friend.

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

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

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

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

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

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

Видео.

16.09.24

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

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

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

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

Видео.

21.09.24

20. Умные указатели. unique_ptr. Возвращение к однонаправленным спискам. Что не так?

shared_ptr.

Видео.

28.09.24

21. shared_ptr.

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

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

Структуры данных. Вектор. Реализация вектора неограниченной длины на C++ (в том числе реализация разного поведения оператора квадратные скобки слева и справа от знака присваивания).

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

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

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

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

Видео.

30.09.24 Standard Template Library

22. Итераторы, reverse итераторы, constant итераторы (в стиле STL). Использование typename, auto, decltype.

Переопределение операторов new/delete.

Видео.

05.10.24

23. Создание отладочных версий операторов new/delete.

STL. Коротко о последовательных и ассоциативных контейнерах.

Структура данных Стек. Различные реализации на С++.

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

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

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

Видео.

12.10.24

24. Структуры данных. Очередь. Реализация циклической очереди на С++. STL. Контейнер queue.

Структуры данных. Дек. Реализация на С++. STL. Контейнер deque.

initializer_list. Range-based for.

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

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

Видео.

14.10.24

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

STL. Списки. Итераторы, reverse итераторы, constant итераторы.

Понятия итераторов ввода и вывода. Последовательные итераторы. Двунаправленные итераторы. Итераторы произвольного доступа.

insert_iterator, front_insert_iterator, back_insert_iterator, inserter, front_inserter, back_inserter.

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

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

Видео.

19.10.24

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

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

Проверка очистки памяти с использованием функции atexit().

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

Видео.

26.10.24

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

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

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

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

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

Видео.

28.10.24

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

C++. Реализация шаблона бинарного дерева поиска. Определение статических элементов шаблонов. Использование шаблона pair (в том числе, если элемент пары является шаблоном внутри шаблона) при реализации добавления элемента в дерево.

Видео.

02.11.24

29. C++. Реализация шаблона бинарного дерева поиска. Использование создания локальной переменной в условии if. Скрытое преобразование к логическому типу.

Удаление элемента из дерева.

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

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

Видео.

09.11.24

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

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

Создание своего класса, который можно использовать в собственной реализации дерева и в контейнере set.

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

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

Видео.

11.11.24

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

Видео.

16.11.24

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

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

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

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

Видео.

23.11.24

33. Красно-черные деревья. Добавление элемента в красно-черное дерево за один проход (модификация дерева при поиске листа таким образом, чтобы не требовался второй проход при добавлении элемента).

Язык Python3. Аналоги массивов. Списки (функции append, extend, insert, pop, remove, copy, sort; срезы; лямбда-функции). Внутренняя реализация списков. Кортежи. Словари. Использование кортежей в словарях.

Все что нужно для вывода форматированной таблицы двумерного массива чисел, представляющего собой словарь на основе кортежей.

Видео.

25.11.24

34. Python. Создание классов. Определение операций +, -, *, / для созданного класса. Определение инициализирующей класс функции и функции преобразования содержимого класса в строку. Пример класса рациональной дроби.

Решение системы линейных уравнений в дробях и в обычных вещественных числах (реализация на Python). Пример матрицы Гильберта.

Оператор ≔

Язык C++. Лямбда-функции без захвата и с захватом vs указатели на функции vs лямбда-функции Python.

Видео.

30.11.24

35. C++. Лямбда-функции с захватом.

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

Алгоритм lower_bound. Шаблон функции, параметром которой является класс, являющийся подклассом шаблона класса (например BTree<…>∷Node).

Видео.

07.12.24

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

B+ - деревья. Вариант реализации файловой системы в памяти на основе B+ - деревьев.

STL. Перечисление всех основных контейнеров.

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

Увы, запись видео закончилась неудачей ☹

09.12.24

37. Нахождение пути в графе от вершины к вершине с наименьшим количеством ребер (алгоритм волны). Реализация алгоритма с помощью STL. Теорема о времени работы алгоритма волны для случая графа без кратных ребер и петель.

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

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

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

Лемма о приведении неориентированного дерева к ориентированному. Теорема Эйлера.

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

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