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

 

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

За две контрольные = 2 балла (по 1 баллу за задачу).

Задача на структуры данных = 4 балла (0 до 4 в зависимости от сданного объема).

Вычислительная геометрия (Python++) = 2 балла (по 1 баллу за задачу).

Коллоквиум = 2 балла (от 0 до 2 баллов).

Задача на экзамене = 4 балла.

Устная часть на экзамене (сюда же входят дополнительные вопросы, обычно таких 2 шт.) = 6 баллов (от 0 до 6 баллов).

 

Итоговая оценка на экзамене = (К-воБаллов+5)/5

 


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


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

 

09.02.19
1. Представление чисел в ЭВМ. Стандартные представления (целое без знака, целое со знаком, Currency, вещественное с плавающей точкой).

IEEE стандарт представления вещественных чисел с плавающей точкой без свойств.

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

Нестандартные представления чисел в ЭВМ. BCD. NUMBER из СУБД Oracle. Абс отн.ошибки.

02.03.19
3. Решение модельной задачи (квадратное уравнение). Понятие алгоритма. Время работы алгоритма. Сведение задач и алгоритмов.

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

 
09.03.19
4. Классический парадокс о том, что любое число можно задать алгоритмом, состоящим из не более, чем 40 словами русского языка.

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

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


16.03.19
5. Язык Python3. Простейшие программы. Арифметические операции. Логические операции. Ввод с клавиатуры. Циклы. Структура программы на языке
Python. Локальные и глобальные (global) переменные, функции, модули. Модель памяти языка Python (для каждого объекта: идентификатор (id), тип (type), значение). Смысл понятия присваивания в Python. Прожиточный минимум для работы с последовательностями. Строки. Списки. Кортежи. Исключения.


23.03.19
6. Постановка задачи сортировки. Теорема о существовании и единственности сортировки.

Дерево решения. Алгоритмы сортировки, основанные на операциях сравнения.

Сортировка пузырьком. Случай оптимальности сортировки пузырьком.

Теорема о нижней оценке времени решения задачи сортировки.


30.03.19
7. Сортировки слиянием с рекурсией и без рекурсии. Теоремы о нижних оценках времени решения задачи слияния массивов из
n и n элементов и из n и n+1 элемента.

Введение в OpenMP. Распараллеливание сортировок.

 

06.04.19
8. Ввод/вывод в языке С: текстовый и бинарный, буферный и прямой. Форматный вывод (форматы для типов
char, char*, short, int, long, long long, float, double; смысл числовых параметров в форматах; использование * в формате; формат %n). Пример составления таблицы при выводе. Запятая в языке С (в качестве оператора и в качестве разделителя).

 

13.04.19
9. Просмотр бинарных файлов в
DOS и UNIX (например, с помощью FAR и od).

Использование дескрипторов и потоков ввода/вывода. fdopen() / fileno(). Стандартные потоки ввода/вывода/вывода сообщений об ошибках. Дескрипторы ввода/вывода в Linux и в MSDOS. Перенаправление ввода/вывода в Linux и в MSDOS. Конвейеры в bash и MSDOS. Команды >, <, n>, n<, |, n&>m, &>, >>, &>>

Основные идеи программирования в bash. Переменные и циклы в bash.

 

20.04.19
10. QuickSort (первый алгоритм; псевдомедиана хранится в сортируемом массиве).

QuickSort (второй алгоритм; псевдомедиана хранится в отдельном элементе). Верхняя оценка времени работы алгоритма QuickSort. Верхняя оценка на количество дополнительной памяти, требуемой для работы различных версий алгоритма QuickSort.

 

27.04.19
11. Теорема о среднем времени работы алгоритма
QuickSort.

HeapSort. Теорема о верхней оценке времени построения пирамиды в рамках данного алгоритма.

 

04.05.19
12. Алгоритмы сортировки, имеющие верхнюю оценку времени работы
Θ(n). Устойчивые сортировки. Алгоритм сортировки подсчетом.

Примеры задач, к которым сводится задача сортировки: построение выпуклой оболочки в 2D. Теорема о виде выпуклой оболочки конечного множества точек. Критерий принадлежности отрезка с вершинами из заданного набора точек границе выпуклой оболочки. Простой алгоритм построения выпуклой оболочки.

 

11.05.19
13. Примеры задач, к которым сводится задача сортировки: построение выпуклой оболочки в 2
D. Теорема о нижней оценке времени решения задачи построения выпуклой оболочки в 2D. Метод обхода Грэхема. Модифицированный обход Грэхема. Метод обхода Джарвиса (для случая малого количества точек на выпуклой оболочке).

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

 

18.05.19
14. Теорема Делоне. Существование и единственность триангуляции Делоне.

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

Примеры задач, сводящихся к задаче сортировки (нахождение всех различных элементов множества; все ли элементы множества различны?;  совпадают ли два множества?).

Теорема о нижней оценке времени решения задачи на принятие решения через количество разделимых связных компонент множества W элементов пространства, на котором задача имеет ответ да. Теорема Бен-Ора.