Во всех видео-лекциях есть оговорки. Я знаю о них, но давайте я оставлю их выявление вам в качестве развлечения 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. Цифровая сортировка. Видео.

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

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