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

 

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

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

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

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

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

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

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

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

 

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

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

 

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


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


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

 

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

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

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

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

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

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

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

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

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

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

13.03.21

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

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

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

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

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

20.03.21

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

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

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

27.03.21

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

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

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

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

Полное видео лекции (изложение сильно сжато).

 

03.04.21

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

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

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

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

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

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

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

Краткий пересказ лекции с некоторыми отклонениями в сторону. Пара слов о multithreading.

 

10.04.21

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

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

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

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

17.04.21

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

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

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

Основные утверждения лекции с некоторыми отклонениями в сторону.

 

24.04.21

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

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

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

 

08.05.21

12. Язык С. Типы переменных. Спецификации формата функций printf()/scanf() (в том числе понятия точности, ширины полей, формат %[…]), соответствующие типам переменных. Виды констант. Видео.

 

15.05.21

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

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

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

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

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

 

22.05.21

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

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

 

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

 

03.09.21

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

Простые классы. Все необходимое для понимания фразы a=b+c. Переопределение операторов (в т.ч. переопределение операторов преобразования типа). Конструкторы (в т.ч. конструктор копирования). Сложные неявные преобразования типов в C++.

 

09.09.21

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

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

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

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

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

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

 

10.09.21

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

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

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

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

 

17.09.21

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

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

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

Замечание: если в последнем приведенном примере заменить определение шаблона

…ostream &operator<<(ostream &cout, const CVector<T> &s)…

на

template<class T> ostream &operator<<(ostream &cout, const CVector<T> &s){for(int i=0;i<s.n;i++)cout<<s.s[i]<<" ";return cout;}

то это будет работать в Microsoft C++, но не будет в gcc. Буду рад комментариям.

 

23.09.21

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

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

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

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

 

24.09.21

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

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

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

 

01.10.21

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

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

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

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

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

 

07.10.21

8. Бинарные деревья поиска. Алгоритмы и реализация предписаний деревьев поиска на C++. Использование классов внутри шаблона. Видео.

C++: итератор для бинарного дерева поиска. Использование auto в C++11. Видео.

 

08.10.21

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

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

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

 

15.10.21

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

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

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

 

21.10.21

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

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

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

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

 

22.10.21

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

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

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

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

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

 

29.10.21

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

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

initializer_list. Range-based for. Forwarding references (rvalue references). Использование auto. Запись с семинара 29.10.2021:  Видео.

 

12.11.21

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

STL. Векторы. Особенности реализации на разных компиляторах. insert vs emplace.  Видео.

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

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

 

 

18.11.21

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

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

STL. Особенности реализации дека. Требования к реализации дека в STL. Когда лучше применять дек, а когда – вектор?   Видео.

STL. Стек.  Видео.

Очередь. Приоритетная очередь. Использование функциональных объектов.  Видео.

 

19.11.21

16.  new/delete определяемые пользователем.

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

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

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

 

26.11.21

17.  Хеширование. Реализация контейнера на основе хеширования методом многих списков с использованием STL со средним временем добавления элемента = O(1).

 Видео.

Метод линейных проб. Реализация метода на C++. Видео.

Мои извинения: в прочитанной online-лекции в функции bad() сравнение j<=h(v[j]) надо заменить на j<h(v[j]).

 

02.12.21

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

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

Хэш-функции на основе деления и умножения.

Метод линейных проб с постоянным шагом.

Двойное хеширование.

 

03.12.21

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

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

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

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

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

 

10.12.21

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

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

 

14.12.21

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

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

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