Корректность (информатика) - Correctness (computer science)

В теоретическая информатика, правильность из алгоритм утверждается, когда говорят, что алгоритм верен относительно Технические характеристики. Функциональный Корректность относится к поведению алгоритма ввода-вывода (т.е. для каждого ввода он дает ожидаемый результат).[1]

Различают частичная правильность, который требует, чтобы если ответ был возвращен, он был правильным, и полная правильность, что дополнительно требует остановки алгоритма. Поскольку нет общего решения проблема остановки, полная правильность не разрешимый. А доказательство прекращения это тип математическое доказательство что играет решающую роль в формальная проверка потому что полная правильность алгоритма зависит от завершения.[2]

Например, при последовательном поиске целые числа 1, 2, 3,… чтобы посмотреть, сможем ли мы найти пример какого-нибудь явления - скажем, странного идеальное число - написать частично корректную программу (используя факторизация для вычисления каждого целого числа аликвотная сумма ). Но сказать, что эта программа полностью верна, значило бы что-то утверждать. в настоящее время не известно в теория чисел.

Доказательство должно быть математическим, если и алгоритм, и спецификация даны формально. В частности, не ожидается, что это будет утверждение о правильности данной программы, реализующей алгоритм на данной машине. Это потребует таких соображений, как ограничения на память компьютера.

А глубокий результат в теория доказательств, то Переписка Карри – Ховарда, заявляет, что доказательство функциональной корректности в конструктивная логика соответствует определенной программе в лямбда-исчисление. Преобразование доказательства таким образом называется извлечение программы.

Логика Хоара это конкретный формальная система за строгое рассуждение о правильности компьютерных программ.[3] Он использует аксиоматические методы для определения семантики языка программирования и спора о правильности программ с помощью утверждений, известных как тройки Хоара.

Тестирование программного обеспечения Любая деятельность, направленная на оценку атрибута или возможности программы или системы и определение того, что она соответствует требуемым результатам. Несмотря на решающее значение для качества программного обеспечения и широко применяемое программистами и тестировщиками, тестирование программного обеспечения по-прежнему остается искусством из-за ограниченного понимания принципов работы программного обеспечения. Сложность тестирования программного обеспечения связана с его сложностью: мы не можем полностью протестировать программу средней сложности. Тестирование - это больше, чем просто отладка. Целью тестирования может быть обеспечение качества, верификация и валидация или оценка надежности. Тестирование также можно использовать в качестве общей метрики. Проверка правильности и проверка надежности - две основные области тестирования. Тестирование программного обеспечения - это компромисс между бюджетом, временем и качеством.[4]

Смотрите также

Примечания

  1. ^ Данлоп, Дуглас Д .; Базили, Виктор Р. (Июнь 1982 г.). «Сравнительный анализ функциональной корректности». Коммуникации ACM. 14 (2): 229–244. Дои:10.1145/356876.356881.
  2. ^ Манна, Зоар; Пнуэли, Амир (сентябрь 1974 г.). «Аксиоматический подход к абсолютной корректности программ». Acta Informatica. 3 (3): 243–263. Дои:10.1007 / BF00288637.
  3. ^ Хоар, К.А.Р. (Октябрь 1969 г.). «Аксиоматическая основа компьютерного программирования» (PDF). Коммуникации ACM. 12 (10): 576–580. CiteSeerX  10.1.1.116.2392. Дои:10.1145/363235.363259. Архивировано из оригинал (PDF) 4 марта 2016 г.
  4. ^ Пан, Цзяньтао (весна 1999 г.). «Тестирование программного обеспечения» (курсовая). Университет Карнеги Меллон. Получено 21 ноября 2017.

Рекомендации