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


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


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

 

10.02.24
1. Понятие виртуальной памяти. Основы реализации.

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

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

 

17.02.24
 2. Вещественные числа с фиксированной точкой. Currency.

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

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

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

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

 Видео.

 

24.02.24

3. Написание примеров программ на тему битового представления вещественных чисел.

Пример решения квадратного уравнения.

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

 Видео.

 

02.03.24

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

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

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

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

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

 Видео.

 

09.03.24

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

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

Отведение памяти в куче (malloc,…) и в стеке (alloca). _malloca()/_freea().

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

Отладка программ в Linux с помощью valgrind.

 Видео.

 

16.03.24

6. Отладка программ в Linux с помощью valgrind и gdb.

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

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

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

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

 Видео.

 

23.03.24

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

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

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

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

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

Видео.

 

30.03.24

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

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

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

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

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

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

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

Видео.

 

06.04.24

9. Язык C. Работа со структурами. Работа с массивами структур. Работа с указателями на массивы структур.

Вопрос на понимание: какие ошибки присутствуют в функции ввода структур из файла и к каким последствиям приведут эти ошибки?

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

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

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

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

Видео.

 

13.04.24

10. C++. Оператор преобразования типа. Кратко про использование ввода/вывода в языке C++. Сложные преобразования типа. Конструктор копирования.

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

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

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

Видео.

 

20.04.24

11. Алгоритм HeapSort. Теорема о времени приведения массива к*-упорядоченному состоянию (к пирамиде).

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

Видео.

 

30.04.24

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

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

Цифровая сортировка.

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

Видео.

 

04.05.24

13. Ввод/вывод BMP. Простейшие преобразования изображений. Бинарный ввод/вывод.

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

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

Поиск порядковой статистики за линейное время в среднем (алгоритм QStat1).

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

Видео.

 

11.05.24

14. Порядковые статистики.

Теоремы о времени работы алгоритмов Stat0, CStat, QStat.Теорема о времени работы в среднем алгоритма QStat.

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

Фильтрация серых изображений. Медианная фильтрация. Теоремы о времени работы алгоритмов медианной фильтрации (med_filter и med_filter_q).

Видео.

 

 

18.05.24

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

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

Видео.