Столкнулся с тем, что качество определений википедии оставляет желать лучшего. Да, текста там много, но при этом формализация не является полной и точной. Остальная часть рунета пуста, в буквальном смысле. Все что есть, сотни сайтов копи-пасты с той же википедии. Поиск по книгам, посвященным программированию и алгоритмам (в частности) тоже не дал результатов. Определений либо вообще нет, либо приводятся отрывочно, либо качество перевода и работа редактора настолько запредельная, что сложно уловить смысл.
Решил формализовать различия между ними самостоятельно. Понял, что не смогу один с этим справиться. Возможно ли дать определения, не прибегая при этом, к таким понятиям как конечный автомат и машина Тьюринга? Кое-что у меня уже получилось, возможно с вашей помощью получится заполнить пробелы в определениях, обозначенные тильдами:
К разветвляющимся алгоритмам можно отнести:
- Алгоритм, поведение которого полностью зависит от входных данных, называют детерминированным |deterministic|. Каждый его шаг заранее предопределен. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Таким образом, обработка одних и тех же входных данных всегда приводит к одинаковому результату.
- Алгоритм, поведение которого невозможно предсказать (от чего оно зависит?), называют недетерминированным |nondeterministic|.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Таким образом, обработка одних и тех же входных данных может приводить как к одинаковым, так и к разным результатам.
Иногда, решение задачи сводиться к использованию случайных величин.
- Алгоритм, поведение которого, помимо входных данных, определяется значениями генератора случайных (псевдослучайных) чисел, называют стохастическим |randomized|
Итак, что мы имеем. поведение (ДА) определяется входными данными, поведение (СА) определяется входными данными и случайностью. Чем определяется поведение (НА) не понятно. Отдельная просьба, – не смотрите на дату, когда вопрос был задан. Даже если ответ был дан год назад, но вы знаете, что может его улучшить “just do it”. Для русскоязычной науки только польза.
