Лекции

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение модельной задачи на ЭВМ: нахождение корней квадратного уравнения.

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

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

12.03.22

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

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

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

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

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

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

19.03.22

6. Навёрстываем то, что не успел рассказать на предыдущих лекциях…

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

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

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

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

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

26.03.22

7. Понятия O, o, Θ, Ω.

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

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

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

02.04.22

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

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

09.04.22

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

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

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

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

16.04.22

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

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

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

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

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

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

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

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

23.04.22

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

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

Реализация QSort2. Модификация реализации для борьбы с однородно-неудобными исходными данными и для борьбы с большой глубиной рекурсии. Видео.

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

30.04.22

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

Язык C. Работа со структурами. Работа с составными объектами (объектами, включающими в себя разные типы переменных) без структур. Работа с массивами структур. Работа с указателями на массивы структур.

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

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

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

07.05.22

13. Алгоритм HeapSort. Теорема о линейном времени работы алгоритма построения пирамиды. Видео.

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

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

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

Дополнительная лекция.

Вычислительная геометрия. Построение выпуклой оболочки в лоб и с помощью обхода Грэхема. Теоремы о верхней и нижней оценке решения задачи построения выпуклой оболочки в R² в рамках алгоритмов, основанных на сравнениях. Видео.

Диаграмма Вороного. Триангуляция Делоне. Видео.

14.05.22

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

Поиск порядковой статистики за линейное время в среднем. Теорема о времени работы алгоритма. Видео.

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

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

Задача поиска порядковой статистики в большой окрестности каждой точки серого изображения. Отведение памяти под двумерный массив с помощью одной операции malloc().

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

21.05.22

15. Язык С. Бинарный ввод/вывод. Просмотр бинарных файлов в Windows и UNIX.

Работа с изображениями. Различные виды представления изображений. Понятия палитры, битовых плоскостей,true color. BMP-формат представления изображения. Ввод/вывод 32-bpp, 24-bpp, 8-bpp изображений в формате BMP. Видео.

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

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

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

0) правила нуля, трех, пяти;

1) семантика перемещения и rvalue-ссылки;

2) лямбда-функции;

3) "умные" указатели;

4) range-based циклы + initializer_list;

5) default, delete;

6) auto, decltype;

7) nullptr;

8) static_assert.

03.09.22

1. C++. Инкапсуляция. Полиморфизм. Понятие внутренних имен объектов C и С++. Использование программ nm либо cc /FAS . Простые (Видео: примеры комплексное число и строка) и сложные классы.

Простые классы. Переопределение операторов (в т.ч. переопределение операторов преобразования типа). Сложные неявные преобразования типов в C++.

Коротко про ввод/вывод в языке C++. Видео.

09.09.22

2. Использование команды nm UNIX. Сложные классы.

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

Переопределение операторов. Видео.

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

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

Параметры по умолчанию. Исключения. Видео.

C++. Дружественные функции/классы. С++03 (старый стандарт), С++11 (новый стандарт). Move-constructors, move-assignment. Правило пяти. Видео.

10.09.22

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

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

Дружественные функции/классы.

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

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

Правило нуля.

17.09.22

4. Умные указатели. uniq_ptr, shared_ptr.

C++. Casts (static_cast, const_cast, reinterpret_cast). Примеры использования. Видео.

С++. Шаблоны (templates). Типовые и целые параметры шаблонов. Видео.

23.09.22

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

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

C++. Использование operator, в рамках С++03 на примере конструкции CVector v=(CVector(),1,2,3,4,5); (в C++11 для этих целей используется initializer_list) Видео.

Вынесение определения шаблона в отдельный cpp-файл.

Реализация вектора в виде шаблона. Видео.

24.09.22

6. Почему приведенная реализация вектора быстрая, но плохая?

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

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

l-value, r-value. lvalue references, rvalue references. Идеальная передача ссылок. Видео.

Вопрос на понимание последней темы: какое понятие рассказано принципиально неправильно?

01.10.22

7. Очередь. Реализация циклической очереди на С++. Видео.

Дек. Реализация на С++. Видео.

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

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

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

07.10.22

8. Итераторы, reverse итераторы, constant итераторы (в стиле STL). Реализация итератора для шаблона L2-списка с текущим элементом. Видео.

Ссылочная реализация L1-списка с фиктивным элементом. Видео.

Циклические списки.

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

08.10.22

9. Язык С++. Исключения. Исключения Microsoft (SEH = Structured Exception Handling). Видео.

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

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

15.10.22

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

21.10.22

11. Деревья поиска. Объединение/разбиение деревьев. Поиск элемента в модифицированном дереве поиска по порядковому номеру.

Сбалансированные, идеально сбалансированные, идеально сбалансированные’ деревья.

22.10.22

12. C++. decltype, auto.

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

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

Оператор ≔

29.10.22

13. Сбалансированные (AVL), идеально сбалансированные и идеально сбалансированные’ деревья. Определения. Взаимосвязи данных понятий. Связь между высотой и количеством элементов в идеально-сбалансированном дереве. Видео.

Связь между высотой и количеством элементов в сбалансированном дереве. Видео.

Добавление элемента в сбалансированное дерево поиска. Удаление элемента из сбалансированного дерева поиска. Видео.

Алгоритмы объединения и разбиения AVL-деревьев. Задача создания структуры данных для хранения множества непересекающихся отрезков на числовой прямой. Видео.

Поиск элемента в AVL-дереве по его индексу. Видео.

05.11.22

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

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

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

12.11.22

15. Удаление элемента из красно-черного дерева. Видео.

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

Язык C. Стандартные функций сортировки и поиска элемента и их использование для работы с вершиной B-дерева.

Язык C++. Использование простейшего варианта лямбда-функции для работы с вершиной B-дерева.

18.11.22

16. Язык C. Указатели на функции.

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

B-деревья. Связь высоты B-дерева с его количеством вершин. Видео.

Поиск элемента. Добавление элемента (за один и два прохода). Видео.

Удаление элемента (за один проход). Видео.

19.11.22

17. B⁺-деревья. Определение. Использование. Видео.

C++. Универсальный синтаксис инициализации, braced-init-list, initializer_list. Полезная ссылка.

26.11.22

18. C++. Инициализация агрегатных типов. Range-based for.

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

Детали реализации B⁺ - деревьев применительно к файловым системам. C++: Шаблоны объединений, структур, классов. Видео.

02.12.22

C++. static_assert.

Грамотная реализация realloc на С++11. Placement new. Явный вызов move-constructors и move-assignments. Видео.

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

Коротко о списках и ассоциативных контейнерах. Использование mutable в приоритетной очереди и ассоциативных контейнерах. Видео (лекция 02.12.2022).

03.12.22

STL. Итераторы. Итераторы ввода, вывода, последовательные итераторы, двунаправленные итераторы, итераторы произвольного доступа. Связь итераторов и потоков ввода/вывода. Видео.

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

Итераторы вставки. Видео.

STL. Обратные и const итераторы. Их использование для контейнеров STL.

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

10.12.22

STL. Функциональные объекты. Алгоритмы. Копирование объектов (copy, copy_if). Алгоритмы (sort, unique, reverse, find, binary_search, lower_bound). Выполнение операции для группы (for_each). Работа с кучей (make_heap, push_heap). Видео.

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

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

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

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

Лемма о приведении неориентированного дерева к ориентированному. Видео.

16.12.22

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

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

Реализация простого алгоритма Дейкстры. Видео.

Алгоритм Дейкстры для STL. Видео (отличается от алгоритмов в текстовых лекциях‼!).

Модифицированная приоритетная очередь. Видео.