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

 

Правила выставления оценки на экзамене:

 

Оценкаа_Семестр – от 2 до 5

Оценкаа_Задачу (на экзамене) – от 0 до 2 (если Оценка_За_Семестр=5, то Оценка_За_Задачу=2 без написания задачи)

Количество_Отвеченных_Вопросов – от 0 до 10

 

Итоговая оценка на экзамене = [(Оценкаа_Семестр  +  Оценка_За_Задачу + Количество_Отвеченных_Вопросов/2 + 2)/2]

 

Здесь [] обозначают целую часть. Например, при несделанной задаче на экзамене и оценке за семестр = 4 для получения отлично на экзамене необходимо правильно ответить не менее чем на 8 вопросов из билета.

 


Темы реальных лекций курса Алгоритмы и алгоритмические языки

 

 

09.09.20
1. Язык С. Описание связки FAR+gcc.

Модель памяти языка С (стек, куча).

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

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

Простейшая программа на языке С.

Видео.

 

16.09.20
2. Просьба вместе с решением задач присылать формулировки постановок задач в кванторах.

Вещественные числа с фиксированной и плавающей точкой. Представление вещественных чисел по IEEE-стандарту.

Видео.

 

23.09.20
3. Точность представления вещественных чисел в виде числа с плавающей точкой. Машинное эпсилон. Как проверять равенство чисел с плавающей точкой. Что значит, что одно число много меньше другого. Абсолютная и относительная ошибки. Теоремы о поведении ошибок при сложении, вычитании, умножении, делении чисел. Решение модельной задачи (решение квадратного уравнения). Понятие некорректных задач.

Видео.

 

 

30.09.20
4. Представления целых чисел со знаком (прямой код, обратный код, дополнительный код). Обоснование разумности дополнительного кода. Точное представление целых чисел в виде вещественных чисел с плавающей точкой.

Базовые типы переменных в языке С. Видео.

 

 

07.10.20
5. Время жизни и область видимости переменных в языке С. Локальные и глобальные переменные.

Общая структура С-программы. Всё необходимое для работы с последовательностями.

 Видео.

 

14.10.20
6. Механизмы передачи параметров в функции языка C через стек и регистры. Принцип работы в языке C функций с переменным количеством параметров в случае различных механизмов передачи параметров в функцию.

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

Видео.

 

21.10.20

7. Парадокс о том, что бесконечно количество натуральных n может быть получено с помощью алгоритма, состоящего из не более чем 50 слов русского языка.

Верхние и нижние оценки времени решения задачи и времени работы алгоритма. Теоремы о получении верхних и нижних оценок времени решения задачи при сведении задач.

Видео.

 

28.10.20

8. Разбор старых проблем. Сортировки. Определение. Существование.

Видео.

Следующую лекцию я выкладываю перед официальным временем лекции. Ее надо посмотреть, осознать и приготовить вопросы. Собственно, на лекции я буду только отвечать на вопросы.

 

04.11.20

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

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

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

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

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

Обсуждение темы на лекции.

 

11.11.20

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

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

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

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

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

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

 

11.11.20

11. CISC- и RISC-идеологии. Необходимость распараллеливания программ. Сложности, связанные с распараллеливанием программ. Понятие критических секций. Компиляция программ под OpenMP. Проблемы при распространении программ, написанных с использованием OpenMP. Отладка программ с помощью gdb. Видео.

 

18.11.20

12. Язык C. Работа со структурами. Работа с составными объектами (объектами, включающими в себя разные типы переменных) без структур. Работа с массивами структур. Работа с указателями на массивы структур.

Реализация QSort2. Модификация реализации для борьбы с однородно-неудобными исходными данными и для борьбы с большой глубиной рекурсии. Видео.

 

18.11.20

13. Язык C. Работа со строками.

 

25.11.20

14. Теорема о среднем времени работы алгоритма QSort2. Видео.

Алгоритм HeapSort. Теорема о линейном времени работы алгоритма построения пирамиды. Видео.

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

 

25.11.20

15. Разбор первого алгоритма QSort и его реализации. Теорема о верхней оценке времени работы данного алгоритма и о верхней оценке объема требуемой алгоритмом дополнительной памяти. Объяснение непригодности данного алгоритма для рабочего использования.

 

 

02.12.20

16. Цифровая сортировка. Видео.

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

Поиск порядковой статистики за линейное время в среднем. Теорема о времени работы алгоритма. Видео.

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

 

02.12.20

17. Структуры/объединения. Совместное использование структур/объединений. Битовые поля в структурах. Бинарный ввод/вывод. Сортировка пузырьком на диске с помощью бинарного ввода/вывода.

Работа со строками. Ввод/вывод строк. Использование формата %n для разбора строки. Работа с двумерными массивами. Видео.

 

09.12.20

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

Задача поиска порядковой статистики в большой окрестности каждой точки серого изображения. Отведение памяти под двумерный массив с помощью одной операции malloc().

Язык С. Бинарный ввод/вывод. Просмотр бинарных файлов в Windows и UNIX.

Работа с изображениями. Различные виды представления изображений. Понятия палитры, битовых плоскостей,true color. BMP-формат представления изображения. Ввод/вывод 32-bpp, 24-bpp, 8-bpp изображений в формате BMP.    Видео.

 

09.12.20

19. Общие идеи форматов изображений со сжатием с потерей/без потери информации. JPEG. Фрактальное сжатие. Выделение границы областей на растровом изображении и сохранение в 1-бит-на-пиксельное изображение. Видео.

 

16.12.20

20. C++. Инкапсуляция. Полиморфизм. Наследование. Создание простого класса.  Видео.

 

13.01.21

21. C++. Работа с простыми классами. Преобразования типов. Сложные преобразования типов. Исключения.   Видео.

 

20.01.21

22. C++. Работа со сложными классами. Идеология SetZero/Clean/CopyOnly. Все, что нужно для реализации выражения a=b+c. Move-constructors, Move-assignment.  Видео.