Корректность - алгоритм
Cтраница 4
 |
Вычисление функции отказов. 370. [46] |
Докажем, что алгоритм 9 2 правильно вычисляет / за время 0 ( у), Сначала докажем корректность алгоритма. [47]
Книга будет полезна студентам, изучающим курс дискретной математики, а также всем желающим проникнуть в технику написания и проверки корректности алгоритмов, включая программистов-практиков. [48]
Чтобы определить, в каком случае целесообразно в качестве корня кандидата в интервал на противолежащем ребре принять вершину с, на шаге ( 2) применяется лемма 3.4. ( Это не влияет на корректность алгоритма или его сложность, но позволяет несколько ускорить его работу. [49]
Некоторый мусор, созданный мутатором при работе сборщика, может быть собран в этом же цикле, но в худшем случае он с гарантией будет собран в следующем цикле. Корректность алгоритма и его реализации также гарантируют, что никакой не являющийся мусором объект никогда не будет ошибочно рассмотрен как мусор. Частота, с которой вызывается сборщик мусора, определяет, насколько часто мутатор не будет иметь объектов для поглощения и будет временно вынужден ждать сборки мусора. [50]
 |
Последний шаг деления пополам с использованием v при быстрой сортировке. [51] |
Для обеспечения корректности алгоритма можно ввести понятие сторож, определяемое как наибольшее возможное значение ключа файла и связываемое с г 1 - м элементом. [52]
Как бы ни был получен алгоритм, он должен быть обоснован; это означает, что если алгоритм создан для решения определенной задачи, то необходима уверенность в том, что для всех исходных данных, для которых эта задача может быть решена, алгоритм позволяет получить решение и ни для каких исходных данных не дает неправильного результата. Это называется корректностью алгоритма. [53]
Доказательство корректности алгоритма 8.7 тривиально, если доказать, что он заканчивает свою работу. Таким образом, корректность алгоритма вытекает из анализа времени его работы, что составляет содержание следующей теоремы. [54]
Алгоритм имеет полиномиальную временную сложность. Вывод и доказательство корректности алгоритма AVOID опускаются ( см. упр. Алгоритм AVOID ( R, В, F) применяется для каждого атрибута В из R. Если выход не пуст, множество выделенных ключей R заменяется на альтернативное множество, полученное алгоритмом AVOID. Известно, что если такое множество ключей существует, то при его использовании атрибут В удалим. Из R - В - В можно вывести новое множество F-зависимостей, представленных в R, так как для R должен существовать новый выделенный ключ К, для которого К - В ( К есть один из замененных ключей, найденных AVOID; см. упр. [55]
Алгоритм имеет полиномиальную временную сложность. Вывод и доказательство корректности алгоритма AVOID опускаются ( см. упр. Алгоритм AVOID ( R, В, F) применяется для каждого атрибута В из R. Если выход не пуст, множество выделенных ключей R заменяется на альтернативное множество, полученное алгоритмом AVOID. Известно, что если такое множество ключей существует, то при его использовании атрибут В удалим. Из R - В - В можно вывести новое множество F-зависимостей, представленных в R, так как для R должен существовать новый выделенный ключ К, для которого К - - В ( К есть один из замененных ключей, найденных AVOID; см. упр. [56]
Страницы: 1 2 3 4