А именно, хотя бы один метод для добавления нового элемента в структуру и один метод либо для извлечения указанного элемента, либо для выполнения запроса к структуре данных.
7 В современных архитектурах/языках элемент массива может соответствовать слову, а не байту, но для простоты предположим, что массив символов хранится как массив байтов.
8 В принципе, это не обязательно должно иметь отношение к информатике. Например, вы можете описать в качестве системы стопку папок, которые необходимо изучить, или — распространенный пример на уроках информатики — стопку посуды, которую нужно вымыть.
9 Application programming interface (программный интерфейс приложения)
10 Больше информации по этой теме вы найдете в приложении В.
11 Жадный алгоритм — это стратегия решения задач, которая находит оптимальное решение, делая локально оптимальный выбор на каждом шаге. Пользуясь им, можно найти лучшее решение только для небольшого подкласса задач, но его также можно использовать в качестве эвристики для поиска приближенных (неоптимальных) решений.
12 NP-полные задачи — это множество задач, для которых любое данное решение может быть быстро проверено (за полиномиальное время), но не существует известного эффективного способа найти правильное решение в первую очередь. NP-полные задачи по определению в настоящее время не могут быть решены за полиномиальное время на классической детерминированной машине (например, модель RAM, которую мы рассмотрим в следующей главе).
13 Для псевдополиномиального алгоритма время работы в наихудшем случае зависит (полиномиально) от значения некоторых входных данных, а не только от их количества. Например, для задачи о рюкзаке 0-1 входными данными являются n элементов (с весом и стоимостью) и вместимость ранца C: полиномиальный алгоритм зависит только от числа n, в то время как псевдополиномиальный зависит также (или только) от значения C.
14 Динамическое программирование — это стратегия решения сложных задач, обладающих определенными характеристиками, а именно рекурсивной структурой подзадач, при которой результат каждой подзадачи требуется использовать несколько раз при вычислении окончательного решения. Окончательное решение вычисляется путем разбиения задачи на набор более простых подзадач, решения каждой из этих подзадач только один раз и сохранения этих решений.
15 Линейное время, если список товаров уже отсортирован. В противном случае линейно-логарифмическое.
7 В современных архитектурах/языках элемент массива может соответствовать слову, а не байту, но для простоты предположим, что массив символов хранится как массив байтов.
8 В принципе, это не обязательно должно иметь отношение к информатике. Например, вы можете описать в качестве системы стопку папок, которые необходимо изучить, или — распространенный пример на уроках информатики — стопку посуды, которую нужно вымыть.
9 Application programming interface (программный интерфейс приложения)
10 Больше информации по этой теме вы найдете в приложении В.
11 Жадный алгоритм — это стратегия решения задач, которая находит оптимальное решение, делая локально оптимальный выбор на каждом шаге. Пользуясь им, можно найти лучшее решение только для небольшого подкласса задач, но его также можно использовать в качестве эвристики для поиска приближенных (неоптимальных) решений.
12 NP-полные задачи — это множество задач, для которых любое данное решение может быть быстро проверено (за полиномиальное время), но не существует известного эффективного способа найти правильное решение в первую очередь. NP-полные задачи по определению в настоящее время не могут быть решены за полиномиальное время на классической детерминированной машине (например, модель RAM, которую мы рассмотрим в следующей главе).
13 Для псевдополиномиального алгоритма время работы в наихудшем случае зависит (полиномиально) от значения некоторых входных данных, а не только от их количества. Например, для задачи о рюкзаке 0-1 входными данными являются n элементов (с весом и стоимостью) и вместимость ранца C: полиномиальный алгоритм зависит только от числа n, в то время как псевдополиномиальный зависит также (или только) от значения C.
14 Динамическое программирование — это стратегия решения сложных задач, обладающих определенными характеристиками, а именно рекурсивной структурой подзадач, при которой результат каждой подзадачи требуется использовать несколько раз при вычислении окончательного решения. Окончательное решение вычисляется путем разбиения задачи на набор более простых подзадач, решения каждой из этих подзадач только один раз и сохранения этих решений.
15 Линейное время, если список товаров уже отсортирован. В противном случае линейно-логарифмическое.
Базовые определения
