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

За три контрольные = 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 семестр (весна)

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

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

18.02.23

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

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

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

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

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

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

25.02.23

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

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

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

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

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

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

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

04.03.23

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

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

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

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

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

11.03.23

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

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

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

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

Запись данной лекции с сортировкой слиянием с рекурсией.

18.03.23

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

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

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

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

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

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

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

Видео.

25.03.23

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

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

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

01.04.23

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

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

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

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

08.04.23

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

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

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

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

Видео лекции.

15.04.23

10. Алгоритм HeapSort.

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

Запись лекции.

22.04.23

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

Язык C++. Структуры данных. Работа со списками.

Звук при записи видео не записался L

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

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

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

29.04.23

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

06.05.23

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

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

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

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

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

Видео.

13.05.23

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

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

Записать лекцию не получилось. В лекциях прошлого года есть первая тема, но хэширования нет L, но я рассказывал это в позапрошлом году. Хотя, я рассказывал это в другое время и на основе того, что вы еще будете проходить L.

Если кто, вдруг, случайно, записал лекцию, то пришлите, пожалуйста. Буду благодарен!

20.05.23

15. Структуры данных. Хеширование. Метод многих списков. Оценки на максимальное и среднее время добавления, поиска, удаления элементов в структуре данных на основе хеширования методом многих списков. Стратегия работы с подобной структурой данных для обеспечения среднего времени выполнения основных операций за время = 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.23

16. Хэширование. Метод линейных проб. Оценка среднего времени выполнения удачной операции поиска=среднее время неудачного добавления элемента. Видео.

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

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

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

09.09.23

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

Создание своих типов для исключений. Видео.

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

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

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

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

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

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

13.09.23

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

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

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

Умные указатели. unique_ptr, shared_ptr. Понятие функциональных объектов. Видео.

16.09.23

19. Умные указатели. unique_ptr, shared_ptr. Понятие функциональных объектов.

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

23.09.23

20. Реализация вектора на основе умных указателей.

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

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

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

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

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

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

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

Видео.

27.09.23

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

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

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

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

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

Видео.

30.09.23

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

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

initializer_list. Range-based for.

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

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

07.10.23

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

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

Понятия итераторов ввода и вывода.

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

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

Видео.

11.10.23

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

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

Проверка очистки памяти с помощью функций, написанных на 21 лекции. Функия atexit(). Директива препроцессора __GNUC__.

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

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

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

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

Видео.

14.10.23

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

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

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

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

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

C++. Определение статических элементов темплейтов.

Видео.

21.10.23

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

C++. Использование создания локальной переменной в условии if. Скрытое преобразование к логическому типу. Определение универсальной инициализации переменной вида Tree<int> t=v; .

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

Видео.

25.10.23

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

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

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

Видео.

28.10.23

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

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

Видео.

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

8.11.23

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

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

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

Оператор ≔

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

Видео.

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

11.11.23

30. Язык Python3. Решение системы линейных уравнений в дробях и в обычных вещественных числах.

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

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

Видео.

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

18.11.23

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

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

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

Видео.

Архив с программой для работы с деревьями и файлом с исходными данными, используемый на лекции для операций добавления элемента в дерево за один проход (коррекция дерева при поиске элемета) и архив с программой для удаления элемента.

22.11.23

32. Язык C++. STL. Алгоритмы. Использование лямбда-функций для работы с вершиной B-дерева. Лямбда-функции без захвата и с захватом vs указатели на функции. Задание шаблона для оператора, работающего с подклассом класса, заданного шаблоном J .

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

Видео.

Архив с программой для работы с деревьями и файлом с исходными данными, используемый на лекции для тестирвоания элементарных операция, Архив с программой с данными по обычному B-дереву степени 3.

25.11.23

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

C++. static_assert.

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

Алгоритмы. Работа с кучей (make_heap, push_heap).

Видео.

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

02.12.23

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

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

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

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

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

Дополнение к теме хеширования. Хеш-функция на основе деления.

Видео лекции.

Видео короткого куска, дописанного после лекции.

06.12.23

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

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

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

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

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

Видео лекции.

09.12.23

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

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

Видео.