Что означает f(n) = O(g(n))?
Варианты ответа:
1) Для любого C, найдется N, что для любого n > N справедливо f(n) < C*g(n)
2) Найдется константа C, что для любого n, начиная с некоторого n0, справедливо f(n) > C*g(n)
3) Для любого C, найдется N, что для любого n > N справедливо f(n) > C*g(n)
4) Найдется константа C, что для любого n, начиная с некоторого n0, справедливо f(n) < C*g(n)
Что означает f(n) = O(g(n))?
Варианты ответа:
1) Для любого C, найдется N, что для любого n > N справедливо f(n) < C*g(n)
2) Найдется константа C, что для любого n, начиная с некоторого n0, справедливо f(n) > C*g(n)
3) Для любого C, найдется N, что для любого n > N справедливо f(n) > C*g(n)
4) Найдется константа C, что для любого n, начиная с некоторого n0, справедливо f(n) < C*g(n)
Начинающий программист реализовал сортировку выбором и пузырьковую сортировку. Обе они использовали одну функцию обмена элементов массива с помощью промежуточной переменной:
void swap(int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
} //swap
Обе сортировки работают правильно (хотя пузырьковая раза в два медленнее).
Потом он узнал что обмен можно произвести без промежуточной переменной, с помощью операции побитового "исключающего или" и исправил функцию:
void swap(int i, int j) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
} //swap
Однако теперь он обнаружил что:
Начинающий программист реализовал сортировку выбором и пузырьковую сортировку. Обе они использовали одну функцию обмена элементов массива с помощью промежуточной переменной:
void swap(int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
} //swap
Обе сортировки работают правильно (хотя пузырьковая раза в два медленнее).
Потом он узнал что обмен можно произвести без промежуточной переменной, с помощью операции побитового "исключающего или" и исправил функцию:
void swap(int i, int j) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
} //swap
Однако теперь он обнаружил что:
Какие утверждения справедливы для последовательности чисел, генерируемых следующим алгоритмом?
for i = 0..2^k-1
output (i ^ (i >> 1))
Где ^ --- операция побитового xor-а, а >> --- сдвиг на один бит вправо:
Варианты ответа:
1) Битовое представление следующего числа отличается от предыдущего только в одном бите
2) Без первого элемента последовательность совпадает со следующей: seq(2^k)
seq(2^k) = seq(2^{k-1}) 2^k seq(2^{k-1})
seq(1) = 1
3) i-ый бит следующего числа хранит сумму по модулю два всех битов предыдущего числа, номера чьих позиций меньше либо равны i
b_i = (\sum_{j=0}^{i} a_i) % 2
4) Следующее число всегда больше предыдущего
Какие утверждения справедливы для последовательности чисел, генерируемых следующим алгоритмом?
for i = 0..2^k-1
output (i ^ (i >> 1))
Где ^ --- операция побитового xor-а, а >> --- сдвиг на один бит вправо:
Варианты ответа:
1) Битовое представление следующего числа отличается от предыдущего только в одном бите
2) Без первого элемента последовательность совпадает со следующей: seq(2^k)
seq(2^k) = seq(2^{k-1}) 2^k seq(2^{k-1})
seq(1) = 1
3) i-ый бит следующего числа хранит сумму по модулю два всех битов предыдущего числа, номера чьих позиций меньше либо равны i
b_i = (\sum_{j=0}^{i} a_i) % 2
4) Следующее число всегда больше предыдущего
Отметьте истинные утверждения.
Варианты ответа:
1) Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
2) Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
3) Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком
Отметьте истинные утверждения.
Варианты ответа:
1) Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
2) Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
3) Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком
Пусть для некоторой задачи есть полиномиальный алгоритм. Лежит ли эта задача в NP?
Пусть для некоторой задачи есть полиномиальный алгоритм. Лежит ли эта задача в NP?
Какова сложность алгоритма "Быстрая сортировка" в худшем случае:
Какова сложность алгоритма "Быстрая сортировка" в худшем случае:
Имеются монеты достоинством 1, 2, 5, 10, 25, 50 копеек. Нужно представить определенную сумму с помощью наименьшего количества монет. Какой алгоритм предпочтительнее всего использовать?
Имеются монеты достоинством 1, 2, 5, 10, 25, 50 копеек. Нужно представить определенную сумму с помощью наименьшего количества монет. Какой алгоритм предпочтительнее всего использовать?
Что верно о алгоритме быстрой сортировки?
Варианты ответа:
1) Для неотсортированного и отсортированного массива количество сравнений примерно равное
2) Алгоритм требует дополнительной памяти
3) Считается самым быстрым на практике алгоритмом
4) Среднее количество обменов O(n*log n)
Что верно о алгоритме быстрой сортировки?
Варианты ответа:
1) Для неотсортированного и отсортированного массива количество сравнений примерно равное
2) Алгоритм требует дополнительной памяти
3) Считается самым быстрым на практике алгоритмом
4) Среднее количество обменов O(n*log n)
Какой алгоритм сортировки (до 1000 элементов) на практике является самым быстрым (при этом используется генератор случайных чисел и производится не менее 100 тестов для более объективной оценки)?
Какой алгоритм сортировки (до 1000 элементов) на практике является самым быстрым (при этом используется генератор случайных чисел и производится не менее 100 тестов для более объективной оценки)?
Каким способом рациональнее всего вычислить площадь произвольного многоугольника?
Варианты ответа:
1) С помощью итерационного алгоритма сложности O(n)
2) С помощью рекурсивного алгоритма сложности O(n2)
3) С помощью алгоритма сложности O(1)
4) Не для всех многоугольников можно точно вычислить площадь алгоритмическим путём
Каким способом рациональнее всего вычислить площадь произвольного многоугольника?
Варианты ответа:
1) С помощью итерационного алгоритма сложности O(n)
2) С помощью рекурсивного алгоритма сложности O(n2)
3) С помощью алгоритма сложности O(1)
4) Не для всех многоугольников можно точно вычислить площадь алгоритмическим путём
Сколько условных операторов if-else нужно использовать для вычисления y = f(x), если область определения функции (-oo < x < +oo) состоит из четырёх вложенных областей и в каждой из них f(x) различна?
Сколько условных операторов if-else нужно использовать для вычисления y = f(x), если область определения функции (-oo < x < +oo) состоит из четырёх вложенных областей и в каждой из них f(x) различна?
Какую задачу позволяет решить алгоритм Дейкстры?
Варианты ответа:
1) Данный алгоритм формирует матрицу достижимости для каждой вершины
2) Данный алгоритм осуществляет обход графа, при этом проходит по каждой из вершин исключительно один раз
3) Данный алгоритм находит кратчайшее расстояние из заданной вершины во все остальные
Какую задачу позволяет решить алгоритм Дейкстры?
Варианты ответа:
1) Данный алгоритм формирует матрицу достижимости для каждой вершины
2) Данный алгоритм осуществляет обход графа, при этом проходит по каждой из вершин исключительно один раз
3) Данный алгоритм находит кратчайшее расстояние из заданной вершины во все остальные
Для любой сортировки, основанной на сравнениях, в наихудшем случае для n элементов нужно произвести не менее n*lg(n) сравнений.
Для любой сортировки, основанной на сравнениях, в наихудшем случае для n элементов нужно произвести не менее n*lg(n) сравнений.
Для чего применяется алгоритм Евклида?
Для чего применяется алгоритм Евклида?
Отметьте существующие типы графов?
Отметьте существующие типы графов?
Какова асимптотическая оценка для быстрого алгоритма возведения числа в целочисленную степень n, применяя только операцию умножения?
Какова асимптотическая оценка для быстрого алгоритма возведения числа в целочисленную степень n, применяя только операцию умножения?
Существует ли сейчас алгоритм факторизации (разложения на простые множители) числа, который работает за полиномиальное время на классическом компьютере?
Существует ли сейчас алгоритм факторизации (разложения на простые множители) числа, который работает за полиномиальное время на классическом компьютере?
Укажите минимальное число ребер, которые должны быть удалены из полного графа K6 таким образом, чтобы оставшийся граф был планарным.
Укажите минимальное число ребер, которые должны быть удалены из полного графа K6 таким образом, чтобы оставшийся граф был планарным.
Как называются числа, которые вычисляются по cледующей рекуррентной формуле?
Fn = Fn-1 + Fn-2, F1 = F2 = 1
Как называются числа, которые вычисляются по cледующей рекуррентной формуле?
Fn = Fn-1 + Fn-2, F1 = F2 = 1
Что делает топологическая сортировка?
Варианты ответа:
1) Сортирует веса ребер графа
2) Сортирует вершины по глубине их достижения из заданной вершины
3) Упорядочивает вершины ориентированного ацикличного графа так, что если граф содержит ребро (u,v) то u располагается раньше v
4) Ничего из вышеперечисленного
Что делает топологическая сортировка?
Варианты ответа:
1) Сортирует веса ребер графа
2) Сортирует вершины по глубине их достижения из заданной вершины
3) Упорядочивает вершины ориентированного ацикличного графа так, что если граф содержит ребро (u,v) то u располагается раньше v
4) Ничего из вышеперечисленного