Алгоритмы и структуры данных поиска - тест 2

Какие существуют метрики, отображающие эффективность алгоритма?

В функциональной парадигме при проектировании алгоритма, какой оценкой на время работы интересуются?

При размере входных данных N, как рассчитывается время работы алгоритма?

Считается ли компьютерная память важным ресурсом, учитывающимся при разработке эффективного алгоритма?

Считается ли процессорное время важным ресурсом, учитывающимся при разработке эффективного алгоритма?

Возможна ли такая ситуация при проектировании алгоритма, когда можно сэкономить на одном ресурсе в ущерб другому (процессорное время / память)?

Зависит ли время работы алгоритма от размера входных данных N?

Если T - время работы алгоритма, N - размер входных данных, что отображает функция max T(I) для N(I) = N?

При рассмотрении времени работы T(M) и памяти M(N) что нас интересует?

При оценивании функций какая оценка соответствует символике f = O(g)?

При оценивании функций символике f = Θ(g) соответствует:

Если при оценивании фиксированного алгоритма оценки сверху и снизу совпали, то какие действия предпринимаются?

O-символика датет приближенную оценку. Что нужно сделать, чтобы найти оценку точнее?

Что означает найти оценку для фиксированного алгоритма?

Что означает найти оценку снизу на задачу?

Чем такая схема <CPU - Память> отличается от реальной жизни?

Какие из перечисленных ниже утверждений относятся к параметру машинное слово w в стандартной модели оперативной памяти (RAM - model)?

Какие характеристики относятся к стандартной модели оперативной памяти (RAM - model)?

В чем состоит отличие в работе алгоритма для модели "разрешающие деревья" от RAM - модели и модели машины Тьюринга?

Что представляе собой программа для модели "разрешающие деревья"?

Какая нижняя оценка справедлива для задачи сортировки?

В алгоритмической модели "разрешающее дерево" в каком случае работа алгоритма завершается?

С какого элемента начинается работа в разрешающем дереве в стандартном случае?

Что называется бинарным деревом?

Что нзывается правильным разрешающим деревом?

Что назыавется сложностью для алгоритма, заданного разрешающим деревом?

Как оценивается сложность правильного дерева сортировки (в худшем случае)?

Можно ли сортировать быстрее чем за T = Ω(N*log N), если разрешить дополнительные операции с ключами?

Сколько листьев должно быть в правильном дереве для множества из N элементов?

Какое из перечисленных ниже высказываний не характеризует разрешающие деревья?

Почему модель алгоритма "разрешающее дерево" не очень типична для практики?

Пусть имеется двоичный счетчик, то есть вектор, состоящий из битов, представляющий двоичное число. Изначально все биты равны 0. Пусть есть операция Increment, какова ее сложность в худшем случае?

Пусть имеется двоичный счетчик, то есть вектор, состоящий из битов, представляющий двоичное число. Изначально все биты равны 0. Для M операций Increment, какова их сложность в худшем случае?

Пусть имеется двоичный счетчик, то есть вектор, состоящий из битов, представляющий двоичное число. Изначально все биты равны 0. Для M операций Increment в каком случае справедлива оценка O(M*N)?

По какому принципу выбирается размер reallocation для аддитивного метода? Если C - старый размер массива.

По какому принципу выбирается размер reallocation для мультипликативного метода? Если C - старый размер массива.

Какое время будет затрачено на выполнение последовательности из M операций для аддитивного метода увеличения рамера массива?

Какое время будет затрачено на выполнение последовательности из M операций для мультипликативного метода увеличения рамера массива?

Для оценки сложности цепочки инкрементов, пусть 1 у.е. компьютер требует за 1 элементарную операцию. Пусть записано некоторое двоичное число 010111, над каждой 1 лежит по 1 у.е., сколько потребуется элементарных действий для операции Increment?

Пусть 1 у.е. компьютер требует за 1 элементарную операцию. Пусть записано некоторое двоичное число, начиная справа имеем k единиц до 0. При текущем балансе -(k+1) (credit: k, debit: 1), если k единиц снять со структуры, 1 положить, сколько нужно попросить у клиента, чтобы выйти в 0?

Пусть 1 у.е. компьютер требует за 1 элементарную операцию. Пусть записано некоторое двоичное число, начиная справа имеем k единиц до 0. При текущем балансе -(k+1) (credit: k, debit: 1), если k единиц снять со структуры, 1 положить, сколько нужно попросить у клиента, чтобы выйти в 0 для 5 запросов?

Пусть 1 у.е. компьютер требует за 1 элементарную операцию. Пусть записано некоторое двоичное число, начиная справа имеем k единиц до 0. При текущем балансе -(k+1) (credit: k, debit: 1), чему равна учетная стоимость?

Для библиотеки std::vector, реализующей массив на C++, что происходит, когда нужно добавить еще один элемент в конец массива, если массив полностью заполнен?

При анализе учетных стоимостей операций C(ai) с каждым из состояний Si связано некоторое вещественное значение ϕi, называемое потенциалом. Тогда чему равняется приведенная стоимоть C'(ai)?

Для задачи о бинарном поиске, какую нужно использовать функцию потенциала, чтобы получить приведенную стоимость C'(ai) = 2

Если подобрать такую функцию потенциала ϕ, что приведенная стоимость будет ограничена каким-то числом M: C'(ai) <= M. Тогда какая будет линейная оценка для суммы стоимостей?

Какие две операции должен выполнять хороший стэк?

Какова учетная стоимость операций в стэке, реализованном с помощью вектора?

Что называется гистерезисом с точки зрения структур данных?

Как будет называться свойство структуры данных, для которой выполняется следующее: если коэффициент заполнения становится больше 1, тогда размер структуры увеличивается (например в 2 раза), если коэффициент заполнения падает до 1/4 раза, тогда размер структуры уменьшается в два раза.

Какие минусы есть у структуры данных Linked lists при использовании ее для реализации стэка?

Какие плюсы есть у структуры данных Chunked vector по сравнению с Linked lists, при использовании в качестве стэка?

Какие высказывания относятся к структуре данных chunked vector?

Какие высказывания относятся к структуре данных linked lists?

Как эффективно реализовать стэк с поддержкой минимума?

Как (с помощью каких структур данных) можно эффективно реализовать очередь с поддержкой минимума?

Какая будет стоимость операций enqueue и dequeue в учетном смысле, если очередь реализована с помощью двух стэков?

С помощью каких структур данных, перечисленных ниже, нельзя реализовать очередь?

Что такое циклическая очередь?

Что означает свойство persistent (версионирование) для структуры данных?

Какая существует главная проблема, мешающая реализации immutable очереди с помощью двух стэков?

Какое время выполнения операции Push у persistent стэка? Если N - длина стэка

Существует подход для освобождения памяти для persistent stack, называемый подсчет ссылок (ref-counting). Как его можно описать?

Выберите, чем характеризуется подход для освобождения памяти для persistent stack, называемый подсчет ссылок (ref-counting)?

Чем характеризуется подход с использованием сборщика мусора для эффективной работы с памятью в peristent-стэке?

Каких двух строк не хватает в приведенном псевдокоде операции Push persistent-стэка? S - ссылка на стэк, v - данные для новой вершины.
	    Push(S, v)
	w = new Node()
	...
	...
	return w		
	

Какие строки лишние в приведенном псевдокоде операции Pop для persistent-стэка? S - ссылка на стэк.
	    Pop(S)
	w = new Node()
	w.next = S	
	return S.next