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