Критерии выставления оценки
на экзамене
Учитывается работа только за третий семестр.
За две контрольные = 2 балла (по 1 баллу за задачу).
Две задачи на структуры данных = 4 балла (0 до 2 за каждую
задачу в зависимости от сданного объема).
Вычислительная геометрия (Python /С++) = 2 балла (по 1 баллу
за задачу).
Коллоквиум = 2 балла (от 0 до 2 баллов).
Задача на экзамене = 4 балла.
Устная часть на экзамене (сюда же входят дополнительные
вопросы, обычно таких 2 шт.) = 6 баллов (от 0 до 6 баллов).
Итоговая оценка на экзамене = (К-воБаллов+5)/5
Во всех видео-лекциях есть оговорки. Я
знаю о них, но давайте я оставлю их выявление вам в качестве развлечения J . Можете даже
не сообщать мне о них.
Темы
реальных лекций курса Работы на ЭВМ
I семестр (весна)
12.02.20
1.
Представление чисел в ЭВМ. Стандартные представления (целое без знака, целое со
знаком, Currency).
19.02.20
2.
Вещественное с плавающей точкой. IEEE стандарт представления вещественных чисел
с плавающей точкой.
Точность представления вещественного числа. Какие числа можно точно представить
в виде вещественного числа с плавающей точкой.
Задача
о том, что можно ли представить точно в виде числа типа float все целые числа от 0 до
миллиона.
Нестандартные
представления чисел в ЭВМ. BCD. NUMBER из СУБД Oracle. Абс.и отн.ошибки.
26.02.20
3. Машинное
эпсилон (два определения). Связь машинного эпсилон с точностью представления
вещественных чисел с плавающей точкой. Решение модельной задачи
(квадратное уравнение).
04.03.20
4. Понятие алгоритма. Время работы алгоритма. Сведение задач и
алгоритмов.
Определения верхних и нижних оценок времени работы алгоритма.
Определения верхних и нижних оценок времени решения задачи. Теоремы о верхних и
нижних оценках при сведении задач.
11.03.20
5. Язык С. Время жизни и область видимости
переменных в языке С. Локальные и глобальные переменные. Модель памяти языка С
(стек, куча).
Цикл выполнения программы. Понятие ассемблерных
инструкций goto, call, rtn. Механизмы передачи параметров
в функции языка C через
стек и регистры. Принцип работы в языке C с функцией с переменным количеством параметров в
случае различных механизмов передачи параметров в функцию.
Язык Python3. Модель памяти языка Python (для
каждого объекта: идентификатор (id),
тип (type), значение). Смысл понятия
присваивания в Python. Простейшие программы.
18.03.20
6. Язык С. Структура
программы на языке С (С-файлы и include-файлы,
функции).
Язык Python3. Простейшие программы.
Арифметические операции. Логические операции. Ввод с клавиатуры. Циклы.
Структура программы на языке Python. Область видимости переменных. Локальные, глобальные (global)
и нелокальные (nonlocal)
переменные. Функции (return),
генераторы (yield),
модули.
Прожиточный минимум
для работы с последовательностями. Строки. Списки.
Кортежи. Исключения.
25.03.20
7. Сортировки.
Определение. Существование и единственность сортировки. Видео.
Достаточность использования (определения) одной
операции меньше для осуществления
сортировки. Видео.
Сортировка пузырьком.
Случай оптимальности сортировки пузырьком. Верхняя и нижняя оценки времени
решения задачи сортировки для случая, когда время сравнения элементов=0, время
обмена местами двух элементов=Θ(|i-j|). Директива препроцессора #define. Правила хорошего тона при
оформлении #define.
Видео.
Сортировки,
основанные на сравнениях. Дерево решения. Теорема о нижней оценке времени
решения задачи сортировки алгоритмами, основанными на сравнениях. Видео.
Сортировка слиянием с
рекурсией (видео).
01.04.20
8. Сортировки слиянием с рекурсией и без рекурсии.
Теоремы о нижних оценках времени решения задачи слияния массивов из n и n элементов и из n и n+1 элемента. Отличия ситуации, описанной в теореме, от запрограммированного
алгоритма Purge.
Попытка исправить ситуацию с помощью оператора switch. Особенности реализации оператора switch.
Видео.
Введение в OpenMP.
Распараллеливание сортировки слиянием с рекурсией. Распараллеливание секций. Видео.
Сортировки слиянием без рекурсии (видео).
Распараллеливание сортировки слиянием без
рекурсии. Распараллеливание циклов. Видео.
Теорема о времени работы алгоритма сортировки
слиянием и о количестве требуемой памяти.
QSort. Идея. Теорема о верхней
оценке времени работы алгоритма QSort.
Требования к памяти QSort.
Реализация QSort1. Видео.
08.04.20
9. Язык C. Работа со структурами.
Работа с составными объектами (объектами, включающими в себя разные типы
переменных) без структур. Работа с массивами структур. Работа с указателями на
массивы структур.
Реализация QSort2. Модификация
реализации для борьбы с однородно-неудобными исходными данными и для борьбы с
большой глубиной рекурсии. Видео.
15.04.20
10. Теорема о среднем времени работы алгоритма QSort2. Видео.
Алгоритм HeapSort. Теорема о
линейном времени работы алгоритма построения пирамиды. Видео.
Устойчивые сортировки. Сортировки со временем
работы O(n). Сортировка
подсчетом. Видео.
22.04.20
11. Цифровая
сортировка. Видео.
Вычислительная геометрия. Построение выпуклой
оболочки в лоб и с помощью обхода Грэхема.
Теоремы о верхней и нижней оценке решения задачи построения выпуклой оболочки в
R2
в рамках алгоритмов, основанных на сравнениях.
Видео.
Диаграмма Вороного.
Триангуляция Делоне. Видео.
29.04.20
12. Язык С. Типы
переменных. Спецификации формата функций printf()/scanf() (в том числе понятия точности, ширины полей, формат %[…]),
соответствующие типам переменных. Виды констант.
Видео.
06.05.20
13. Порядковые статистики. Простые алгоритмы поиска
порядковой статистики. Видео.
Поиск
порядковой статистики за линейное время в среднем. Теорема о времени работы
алгоритма. Видео.
Поиск
порядковой статистики в общем случае с верхней оценкой времени работы алгоритма
Θ(n). Видео.
Поиск
порядковой статистики последовательности целых чисел {ai} (i=1,…,n) за линейное время для случая ai<O(n). Видео.
Задача
поиска порядковой статистики в большой окрестности каждой точки серого
изображения. Отведение памяти под двумерный массив с помощью одной операции malloc().
13.05.20
14.
Язык С. Бинарный ввод/вывод. Просмотр бинарных файлов в Windows и
UNIX.
Работа
с изображениями. Различные виды представления изображений. Понятия палитры, битовых плоскостей,true color. BMP-формат
представления
изображения. Ввод/вывод 32-bpp, 24-bpp, 8-bpp изображений в формате BMP. Видео.
20.05.20
15. Краткий обзор работы в командной строке UNIX.
Регулярные
выражения UNIX.
bash.
Перенаправление потоков, конвейеры. Вставка результата стандартного потока
вывода в командную строку. Переменные (локальные и экспортируемые),
массивы. Циклы for (стандартный и C-подобный).
Арифметические выражения $[ ... ]. Логические выражения [[ ... ]]. Пример
программы сортировки в bash. Видео.
Поиск файлов (locate, updatedb, whereis, find). Видео.
Потоковые
редакторы grep, egrep, sed, awk. Видео.
II семестр (осень)
03.09.20
1. C++. Инкапсуляция. Полиморфизм. Понятие внутренних имен объектов C и С++. Простые (Видео: примеры комплексное
число и строка) и сложные классы.
Простые классы. Все необходимое для
понимания фразы a=b+c.
Переопределение операторов (в т.ч. переопределение операторов преобразования
типа). Конструкторы (в т.ч. конструктор копирования). Сложные неявные
преобразования типов в C++.
10.09.20
2.
Использование команды nm UNIX.
Сложные классы.
Сложные классы. Отведение памяти. Все
необходимое для понимания фразы a=b+c.
Переопределение
операторов. Видео.
Конструкторы
(в т.ч. конструктор копирования, конструкторы для OpenMP, вызов конструкторов для
переменных класса), деструкторы.
Параметры
по умолчанию. Исключения. Видео.
Коротко
про ввод/вывод в языке C++. Видео.
10.09.20
3. C++.
Дружественные функции/классы. С++03 (старый стандарт), С++11 (новый стандарт). Move-constructors,
move-assignment.
Видео.
Структуры данных.
Вектор. Реализация вектора неограниченной
длины на C++ (в том числе реализация разного поведения
оператора квадратные скобки слева и
справа от знака присваивания). Видео.
C++. Использование operator, на примере
конструкции CVector v=(CVector(),1,2,3,4,5); Видео.
17.09.20
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. Буду рад комментариям.
17.09.20
Семинар. Разбор
переопределения оператора new с параметрами (с
передачей имени текущего файла и номера текущей строки для написания
отладочного оператора new).
24.09.20
5. Стек. Различные реализации на С++. Видео.
Очередь. Реализация циклической очереди на С++. Видео.
Дек. Реализация на
С++. Видео.
Списки (однонаправленные, двунаправленные, циклические). Два
понимания понятия список: с текущим
элементом и текущим положением в списке. Ссылочная и бессылочная реализации на
С++. Бессылочная реализация
L2-списка с текущим положением. Видео.
24.09.20
6. Списки. Ссылочная реализация
L1-списка с фиктивным элементом. Видео.
Ссылочная реализация
L2-списка с текущим элементом. Видео.
Итераторы (в стиле STL). Реализация
итератора для шаблона L2-списка с текущим элементом. Видео.
01.10.20
7. Профессиональная реализация однонаправленного списка на языке
С++ (с собственным выделением памяти). Видео.
Язык С++. Исключения. Исключения Microsoft (SEH = Structured Exception Handling). Видео.
Взаимоотношения
между стандартными и структурированными исключениями Microsoft. Видео.
Возможность
продолжения работы программы при выбросе исключения с места выброса исключения.
Бинарные деревья. Деревья поиска.
Определение. Видео.
08.10.20
8. Бинарные деревья поиска.
Алгоритмы и реализация предписаний деревьев поиска на C++. Использование классов внутри
шаблона. Видео.
C++:
итератор для бинарного дерева поиска. Использование auto в C++11. Видео.
08.10.20
9. Сбалансированные (AVL), идеально
сбалансированные и идеально сбалансированные’ деревья. Определения. Взаимосвязи данных понятий.
Связь между высотой и количеством элементов в идеально-сбалансированном дереве.
Видео.
Связь между
высотой и количеством элементов в сбалансированном дереве.
Видео.
Добавление
элемента в сбалансированное дерево поиска. Удаление элемента из
сбалансированного дерева поиска. Видео.
15.10.20
10. Алгоритмы объединения и разбиения AVL-деревьев. Задача создания структуры данных для хранения множества
непересекающихся отрезков на числовой прямой. Видео.
Поиск элемента в AVL-дереве по его
индексу. Видео.
Красно-черные деревья.
Красно-черные’ деревья. Определения. Связь между высотой и количеством
элементов в красно-черных деревьях. Видео.
22.10.20
11. Красно-черные деревья. Добавление элемента в красно-черное дерево
за два прохода.
Добавление
элемента в красно-черное дерево за один проход (модификация дерева при поиске
листа таким образом, чтобы не требовался второй проход при добавлении элемента). Видео.
Удаление элемента
из красно-черного дерева. Видео.
Язык
Python3. Аналоги массивов. Списки (функции append, extend, insert, pop, remove, copy, sort; срезы; лямбда-функции). Внутренняя реализация
списков. Кортежи. Словари. Использование кортежей в словарях. Видео.
22.10.19
12. B-деревья. Связь высоты B-дерева с его количеством вершин. Видео.
Поиск элемента. Добавление элемента (за два прохода и за один
проход). Видео.
Удаление элемента (за один проход). Видео.
B+-деревья. Определение. Использование. Видео.
STL. Введение. Коротко о последовательных
контейнерах. Видео.
29.10.19
13. STL. Коротко о
списках и ассоциативных контейнерах. Видео.
Отступление к прошлой теме: Детали реализации B+
- деревьев применительно к файловым системам. C++: Шаблоны объединений,
структур, классов; initializer_list. Видео.
5.11.19
14. Грамотная
реализация realloc на С++11. Placement new. Явный вызов move-constructors и move-assignments. Видео.
STL. Векторы. Особенности
реализации на разных компиляторах. insert vs emplace. Видео.
STL. Итераторы. Итераторы ввода, вывода,
последовательные итераторы, двунаправленные итераторы, итераторы произвольного
доступа. Связь итераторов и потоков ввода/вывода. Обратные итераторы для
контейнеров STL. Видео.
5.11.19
15. STL. Особенности
реализации дека. Требования к реализации дека в STL. Когда лучше применять дек, а когда – вектор? Видео.
STL. Стек. Видео.
Очередь. Приоритетная очередь. Использование функциональных
объектов. Видео.
12.11.19
16. STL. Функциональные
объекты. Алгоритмы. Копирование объектов (copy, copy_if). Выполнение операции для группы (for_each). Работа с кучей (make_heap, push_heap). Видео.
Потоки ввода/вывода. Создание с помощью потоков ввода и файлового
ввода C++ криволинейного массива слов в строках. Вывод
данного массива с помощью потока вывода, привязанного к потоку cout. Видео.
Хеширование. Набор
предписаний для структуры данных, основанной на хешировании. Метод многих
списков. Оценки на максимальное и среднее время добавления, поиска, удаления
элементов в структуре данных на основе хеширования методом многих списков.
Стратегия работы с подобной структурой данных для обеспечения времени
выполнения основных операций = O(1). Видео.
19.11.19
17. Хеширование. Реализация
контейнера на основе хеширования методом многих списков с использованием STL со средним временем добавления элемента = O(1).
Метод
линейных проб.
Реализация метода на C++. Видео.
Оценка среднего времени выполнения неудачной операции
поиска (=добавления элемента). Видео.
26.11.19
18. Хеширование. Метод линейных
проб. Оценка среднего времени выполнения удачной
операции поиска. Видео.
Хэш-функции на основе деления
и умножения.
Метод линейных проб с
постоянным шагом.
26.11.19
19. Хеширование. Квадратичное хеширование.
CRC-алгоритм проверки целостности данных на основе
представления числа как многочлена с коэффициентами в поле вычетов по модулю 2.
Видео.
03.11.19
20. Графы. Определение. Ориентированные
и неориентированные графы. Инцидентность/смежность вершин/ребер. Нахождение
пути в графе от вершины к вершине с наименьшим количеством ребер (алгоритм
волны). Реализация алгоритма с помощью STL. Теорема о времени работы алгоритма
волны для случая графа без кратных ребер и петель. Видео.
Геометрическое
представление графа. Теорема о существовании геометрического представления
графа.
Планарные
графы. Плоская укладка планарного графа. Теорема о существовании плоской
укладки (без доказательства) (ошибка в
формулировке в видео!).
Деревья.
Листья ориентированных и неориентированных деревьев. Лемма о существовании
плоской укладки для конечного дерева.
Лемма
о приведении неориентированного дерева к ориентированному. Видео.
10.11.19
21. Теорема Эйлера.
Оценка количества ребер и граней конечного планарного графа через количество вершин.
Теорема о времени работы алгоритма волны для случая планарного графа. Видео.
Задача
о нахождении кратчайшего пути в графе. Алгоритм Дейкстры (простой и модифицированный). Видео.
10.11.19
22. Реализация простого алгоритма Дейкстры. Видео.
Алгоритм
Дейкстры для STL.
Видео (отличается от алгоритмов в
текстовых лекциях‼!).
Модифицированная
приоритетная очередь. Видео.