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

 

Учитывается работа только за третий семестр.

За две контрольные = 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. Понятие алгоритма. Время работы алгоритма.

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

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

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

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

Язык С. Время жизни и область видимости переменных в языке С. Локальные и глобальные переменные. Модель памяти языка С (стек, куча). Локальные автоматические массивы переменного размера в языке 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.    Видео.

Текст, записанный на лекции .