Критерии выставления оценки
на экзамене
Учитывается работа только за третий семестр.
За две контрольные = 2 балла (по 1 баллу за задачу).
Две задачи на структуры данных = 4 балла (0 до 2 за каждую
задачу в зависимости от сданного объема).
Три задачи на массивы Python = 3 балла (1 балл за каждую
задачу).
Вычислительная геометрия (Python /С++) = 2 балла (по 1 баллу за задачу).
Коллоквиум = 2 балла (от 0 до 2 баллов).
Задача на экзамене = 4 балла.
Устная часть на экзамене (сюда же входят дополнительные
вопросы, обычно таких 2 шт.) = 6 баллов (от 0 до 6 баллов).
Итоговая оценка на экзамене = [(К-воБаллов+5)/5]
здесь [x]=целая
часть от x.
Во всех видео-лекциях есть оговорки. Я
знаю о них, но давайте я оставлю их выявление вам в качестве развлечения J
. Можете даже не сообщать мне
о них.
Темы
реальных лекций курса Работы на ЭВМ
I
семестр (весна)
12.02.22
1.
Представление чисел в ЭВМ. Стандартные представления (целое без знака). Видео.
19.02.22
2.
Представление чисел в ЭВМ. Целое со знаком (прямой,
обратный, дополнительный код), Currency.
Вещественное с
плавающей точкой. IEEE стандарт представления вещественных чисел с плавающей
точкой. Видео.
26.02.22
3.Точность
представления вещественного числа. Какие числа можно точно представить в виде
вещественного числа с плавающей точкой.
Задача о том, что можно ли представить точно в
виде числа типа float все целые числа от 0 до миллиона.
Абсолютные и относительные ошибки. Машинное
эпсилон (два определения). Связь машинного эпсилон с точностью представления
вещественных чисел с плавающей точкой.
Нестандартные представления чисел в ЭВМ. Видео.
Текст, записываемый на
лекции .
Абсолютные и относительные ошибки. Машинное
эпсилон (два определения). Связь машинного эпсилон с точностью представления вещественных
чисел с плавающей точкой.
Нестандартные
представления чисел в ЭВМ. Видео.
07.03.22
4.
Абсолютные и относительные ошибки. Машинное эпсилон (два определения).
Связь машинного эпсилон с точностью представления вещественных чисел с
плавающей точкой.
Нестандартные представления чисел в ЭВМ. NUMBER
из СУБД Oracle.
Решение модельной задачи на ЭВМ: нахождение
корней квадратного уравнения.
Понятие
алгоритма. Время работы алгоритма. Видео.
Текст, записанный на
последней лекции .
12.03.22
5. Понятие алгоритма. Время работы алгоритма.
Сведение задач и алгоритмов.
Определения
верхних и нижних оценок времени работы алгоритма.
Теоремы о верхних и нижних оценках при сведении
задач.
Язык
С. Время жизни и область видимости переменных в языке С. Локальные и глобальные
переменные. Модель памяти языка С (стек, куча). Локальные автоматические
массивы переменного размера в языке C. Видео.
19.03.22
6. Навёрстываем то, что не
успел рассказать на предыдущих лекциях…
Понятие алгоритма. Время работы алгоритма.
Сведение задач и алгоритмов.
Определения
верхних и нижних оценок времени работы алгоритма.
Теоремы о верхних и нижних оценках при сведении
задач.
Текст, записанный на
последней лекции .
26.03.22
7. Понятия O, o, Θ, Ω.
Язык
С. Время жизни и область видимости переменных в языке С. Локальные и глобальные
переменные. Модель памяти языка С (стек, куча). Локальные автоматические
массивы переменного размера в языке C.
Отведение памяти в куче (malloc,…) и в стеке (alloca). _malloca()/_freea().
Цикл выполнения программы. Понятие ассемблерных
инструкций goto, call, rtn.
Механизмы
передачи параметров в функции языка C через стек и регистры.
Текст, записанный на
последней лекции .
02.04.22
8. Принцип работы в языке C
функций с переменным количеством параметров в случае
различных механизмов передачи параметров в функцию. Примеры аналога printf() (с использованием и без использования
стандартных макросов va_list, va_start, va_list, va_end) с несколькими форматными
строками (см. запись этой конкретной
лекции).
Язык
Python3. Модель памяти языка Python (для каждого
объекта: идентификатор (id),
тип (type),
значение). Смысл понятия присваивания в Python.
Простейшие программы. Все, необходимое для работы с последовательностями. Видео.
09.04.22
9. Сортировки.
Определение. Существование и единственность сортировки. Видео.
Достаточность использования
(определения) одной операции меньше
для осуществления сортировки. Видео.
Сортировка
пузырьком. Случай оптимальности сортировки пузырьком. Верхняя и нижняя
оценки времени решения задачи сортировки для случая, когда время сравнения
элементов=0, время обмена местами двух элементов=Θ(|i-j|). Директива препроцессора #define.
Правила хорошего тона при оформлении #define.
Видео.
Сортировки,
основанные на сравнениях. Дерево решения. Теорема о нижней оценке времени
решения задачи сортировки алгоритмами, основанными на сравнениях. Видео.
16.04.22
10. Сортировка
слиянием с рекурсией (видео).
Сортировки слиянием с рекурсией и без рекурсии.
Теоремы о нижних оценках времени решения задачи слияния массивов из n и n элементов и из n и n+1 элемента. Отличия ситуации, описанной в теореме, от запрограммированного
алгоритма Murge. Попытка исправить ситуацию с помощью оператора switch. Особенности реализации оператора switch.
Видео.
Использование #define для автоматизации отведения/очистки памяти (см. запись этой конкретной лекции).
Введение в OpenMP. Распараллеливание сортировки слиянием с рекурсией. Распараллеливание
секций. Видео.
Сортировки слиянием без рекурсии (видео).
Распараллеливание сортировки
слиянием без рекурсии. Распараллеливание циклов. Видео.
Теорема о времени работы алгоритма
сортировки слиянием с рекурсией и о количестве требуемой памяти.
Текст, записанный на
последних лекциях .
23.04.22
11. QSort.
Идея. Теорема о верхней оценке времени работы алгоритма QSort.
Требования к памяти QSort. Реализация QSort1. Видео.
Теорема о времени работы
алгоритма сортировки слиянием без рекурсии и о количестве требуемой памяти.
Реализация
QSort2.
Модификация реализации для борьбы с однородно-неудобными исходными данными и
для борьбы с большой глубиной рекурсии. Видео.
30.04.22
12. Теорема о среднем времени
работы алгоритма QSort2.
Видео.
Язык C. Работа со структурами.
Работа с составными объектами (объектами, включающими в себя разные типы
переменных) без структур. Работа с массивами структур. Работа с указателями на
массивы структур.
Полезно зайти в семинарские
видео I-го
курса и посмотреть видео
с написанием примера списка студентов.
Дополнение о работе с
массивом объектов различной природы (работа со структурами и объединениями, в
том числе, неименованными).
07.05.22
13. Алгоритм HeapSort. Теорема о линейном
времени работы алгоритма построения пирамиды. Видео.
Устойчивые сортировки.
Сортировки со временем работы O(n). Сортировка
подсчетом. Видео.
Дополнительная
лекция.
Вычислительная геометрия.
Построение выпуклой оболочки в лоб и с помощью обхода
Грэхема. Теоремы о верхней и нижней оценке решения задачи построения
выпуклой оболочки в R2
в рамках алгоритмов, основанных на сравнениях.
Видео.
Диаграмма
Вороного. Триангуляция Делоне. Видео.
14.05.22
14. Порядковые статистики.
Простые алгоритмы поиска порядковой статистики. Видео.
Поиск порядковой статистики за линейное время в среднем.
Теорема о времени работы алгоритма. Видео.
Поиск порядковой статистики в общем случае с верхней оценкой
времени работы алгоритма Θ(n). Видео.
Поиск порядковой статистики последовательности целых чисел {ai} (i=1,…,n) за линейное время для случая ai<O(n). Видео.
Задача поиска порядковой статистики в большой окрестности каждой
точки серого изображения. Отведение памяти под двумерный массив с помощью одной
операции malloc().
21.05.22
15. Язык С. Бинарный ввод/вывод. Просмотр бинарных файлов в Windows
и UNIX.
Работа
с изображениями. Различные виды представления изображений. Понятия палитры, битовых плоскостей,true color. BMP-формат представления изображения. Ввод/вывод 32-bpp, 24-bpp, 8-bpp изображений
в формате BMP. Видео.