Вопрос №1 (теория)

 

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

2.      Машинное эпсилон. Точность представления вещественного числа. Какие числа можно точно представить в виде вещественного числа с плавающей точкой. Нестандартные представления чисел в ЭВМ. BCD. NUMBER из Oracle. Абсолютные и относительные ошибки.

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

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

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

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

7.      Сортировка алгоритмом QuickSort. Теорема о среднем времени работы алгоритма QuickSort.

8.      Сортировка алгоритмом HeapSort или сортировка с помощью пирамиды.

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

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

11.   Алгоритмы сортировки за время O(N). Сортировка подсчетом. Цифровая сортировка.

12.   Структуры данных. Определения. Различные реализации. Вектор. Стек.

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

14.   Структуры данных. Определения. Различные реализации. L1- и L2-cписки.

15.   Бинарные деревья поиска. Поиск, добавление, удаление элемента.

16.   Бинарные деревья поиска. Поиск минимального и максимального элемента в дереве. Поиск следующего/предыдущего элемента в дереве.

17.   Сбалансированные, идеально сбалансированные и идеально сбалансированные’ деревья. Определения. Взаимосвязи данных понятий.  Высота сбалансированного и идеально сбалансированного бинарного деревьев в зависимости от количества элементов в дереве.

18.   Сбалансированные бинарные деревья поиска. Поиск, добавление, удаление элемента.

19.   Сбалансированные бинарные деревья поиска. Поиск минимального и максимального элемента в дереве. Поиск следующего/предыдущего элемента в дереве.

20.   Сбалансированные бинарные деревья поиска. Слияние двух деревьев. Разбиение дерева по разбивающему элементу.

21.   Красно-черные деревья. Определение. Красно-черное’ дерево. Оценка высоты красно-черного дерева через количество элементов в дереве. Добавление элемента в красно-черное дерево за два прохода (поиск с проходом сверху вниз + добавление с проходом снизу вверх).

22.   Красно-черные деревья. Удаление элемента из красно-черного дерева. Добавление элемента в красно-черное дерево за один проход (с модификацией дерева при поиске элемента, после которого вставляется новый элемент).

23.   B-деревья. Добавление и удаление элементов.

24.   B+-деревья. Их использование при моделировании файловой системы. Пример добавления 15 элементов в B+-дерево, предназначенное для моделирования файловой системы.

25.   Графы. Определение. Ориентированные и неориентированные графы. Инцидентность/смежность вершин/ребер. Нахождение пути в графе от вершины к вершине с наименьшим количеством ребер (алгоритм волны). Теорема о времени работы алгоритма волны для случая графа без кратных ребер и петель. Теорема о времени работы алгоритма волны для случая графа с плоской укладкой.

26.   Нахождение кратчайшего пути в графе. Алгоритм Дейкстры. Простой алгоритм Дейкстры. Теорема о времени работы простого алгоритма Дейкстры.

27.   Нахождение кратчайшего пути в графе. Алгоритм Дейкстры. Модифицированный алгоритм Дейкстры на основе STL. Теорема о времени работы модифицированного алгоритма Дейкстры.

 

Вопрос №2 (по языку)

 

1.      Общая структура С-программы.

2.      Язык С. Типы базовых переменных. Их описание, определение, инициализация.

3.      Язык С. Константы (целые, вещественные, строковые, символьные).

4.      Язык С. Структуры и объединения. Описания и определения.

5.      Язык С. Арифметические операции `+’, `-’, `*’, `/’, `+=’, `-=’, `*=’, `/=’, `++’,   `--’.

6.      Язык С. Логические операции `&&’, `||’, `!’.

7.      Язык С. Указатели. Указатели на функции.

8.      Язык С. Область видимости переменных и время жизни переменных.

9.      Язык С. Описание и определение функций.

10.   Язык С. Операторы цикла.

11.   Язык С. Условные операторы. Оператор перехода.

12.   Строки в языке С. Функции работы со строками.

13.   Язык С. Потоковый ввод/вывод для текстовых файлов. Открытие файла, ввод/вывод с помощью функций fprintf/fscanf/fgets/fputs, закрытие файла.

14.   Язык С. Потоковый ввод/вывод для бинарных файлов. Открытие файла, ввод/вывод с помощью функций fread/fwrite, закрытие файла.

15.   Язык С. Отведение/очистка памяти с помощью функций malloc/realloc/free.

16.   OpenMP. Использование OpenMP в сортировках.

17.   Язык С++. Конструкторы, деструкторы. Отведение памяти. Ввод/вывод с клавиатуры/на экран (cin/cout) и в файл (fstream).

18.   Язык С++. Инкапсуляция. Полиморфизм. Создание простых классов. Выделить, какие методы для простых классов  можно не создавать. Все необходимое для понимания фразы a=b+c для простых классов.

19.   Язык С++. Инкапсуляция. Полиморфизм. Создание сложных классов. Идеология SetZero/Clean/CopyOnly. Все необходимое для понимания фразы a=b+c для сложных классов.

20.   Язык С++. Правило трех. Правило пяти.

21.   Язык С++. Переопределение операторов, в том числе, переопределение операторов преобразования типа.

22.   Язык С++. Дружественные функции/классы. С++03 (старый стандарт), С++11 (новый стандарт). Move-constructors.

23.   Язык С++. Умные указатели. Правило нуля.

24.   STL. Последовательные контейнеры. Итераторы для них.

25.   STL. Ассоциативные контейнеры. Итераторы для них.

26.   Язык С++. Range-based for. Что надо определить в классе, чтобы к нему был применим range-based for ?

27.   Язык С++. Initializer list и его использование в собственных классах.

28.   Язык С++. Лямбда-функции (с захватом и без захвата). Примеры их использования в STL.

29.   Python. Арифметические и логические операции.

30.   Python. Циклы. Условные операторы.

31.   Python. Функции. Модули. Стандартные модули. Создание и использование собственных модулей.

32.   Python. Списки. Кортежи. Работа со списками и кортежами. Основные методы списков и кортежей.

33.   Python. Словари. Работа со словарями. Основные методы словарей.

34.   Python. Строки. Работа со строками. Основные методы строк. Ввод строк (в том числе слов) из файла.

35.   Python. Исключения.