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


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

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

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

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

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

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


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

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

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

Язык Python3. Простейшие программы. Структура программы на языке Python (локальные и глобальные переменные, функции, модули). Модель памяти языка Python (для каждого объекта: идентификатор (id), тип (type), значение; смысл понятия присваивания в Python).

 

10.03.18
5. Простейшая программа на
Python. Прожиточный минимум для работы с последовательностями. Строки. Списки. Кортежи. Исключения.

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

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

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

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

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

 

17.03.18
6. Сортировки слиянием с рекурсией и без рекурсии. Ввод/вывод в языке С: текстовый и бинарный, буферный и прямой.

 

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

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

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

 

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

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

 

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

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

 

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

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

Язык C. Структуры. Объединения.

Цифровой алгоритм сортировки.

Замечания о зависимости времени работы сортировок слиянием и подсчетом от вида входных данных.

 

21.04.18
11. Язык
C. Директива препроцессора #define (без параметра; с параметрами; использование ##). Динамический вектор в идеологии языка C (DVECTOR(int,xx); SET_INDEX(int,xx,99); for(i=0;i<LVECTOR(xx);i++)xx[i]=i;).

HeapSort (пирамидальная сортировка). Теорема о времени построения пирамиды.

 

30.04.18

12. Об ошибке в реализации алгоритма быстрой сортировки QSort2().

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

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

Задача поиска порядковой статистики в большой окрестности каждой точки серого изображения.

 

05.05.18

13. Язык С. Типы переменных. Спецификации формата функций printf()/scanf() (в том числе понятия точности, ширины полей, формат %[…]), соответствующие типам переменных. Виды констант.

Структуры данных. Стек. Различные реализации.

 

12.05.18

14. Структуры данных. Стек. Очередь. Дек. Различные реализации.

Списки (однонаправленные, двунаправленные, циклические). Ссылочная и бессылочная реализации.

 

19.05.18

15. Структуры данных. Списки (однонаправленные, двунаправленные, циклические). Реализация списка с самостоятельным выделением памяти.