Во всех видео-лекциях есть оговорки. Я
знаю о них, но давайте я оставлю их выявление вам в качестве развлечения 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
Язык С. Время жизни и область
видимости переменных в языке С. Локальные и глобальные переменные. Модель
памяти языка С (стек, куча). Локальные автоматические массивы переменного
размера в языке 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. Простейшие преобразования изображений. Бинарный
ввод/вывод.
Порядковые статистики.
Простые алгоритмы поиска порядковой статистики.
Поиск порядковой статистики за линейное время в среднем.
Теорема о времени работы алгоритма.
Поиск порядковой статистики в общем случае с верхней оценкой
времени работы алгоритма Θ(n).
Поиск порядковой статистики последовательности целых чисел {ai} (i=1,…,n) за линейное время для случая ai=O(n).
Преобразование RGB-изображения в серое.