Теоретическая информатика, определение понятия "Алгоритм". Школоте мимо, только для людей разбирающихся в вопросе.

Question

В алгоритме (по определению) все шаги должны быть точно (однозначно) определены.

Допустим, если в алгоритме на каком-то шаге ветвление зависяще от случайного события. Например, вызывает функцию "случайное_число () " и в зависимости от возвращённого значения произходят дальнейшие действия.

Так вот, строго теоретически по определению это является АЛГОРИТМОМ или нет? Ведь получается, что не все его шаги точно определены (точно описаны) . Или другими словами: на момент определения (написания) этого "алгоритма" и даже на момент начала выполнения ещё точно не известно, что в точности произойдёт на том шаге с ветвлением.

Что говорит теория на этот счёт?

Answer 1

Нет никакой "теоретической информатики", есть математика, есть практическая дисциплина - программирование. Есть попытки это связать (например, у Тьюринга) . Но, как и везде в математике, пока определение не стало стандартным - его просто приводят в начале лекции. Например, даже считать ли 0 натуральным числом - нет единого мнения, в итоге математики оговаривают в начале лекции или монографии, каким определением будут пользоваться. То. что вы описали - типичная ситуация, есть даже обще название "метод Монте-Карло". Мне как-то попался билет ЕГЭ, в котором в двух вопросах было противоречие именно по этому пункту: в первом спрашивалось, какое определение алгоритма правильное, и правильным ответом считался тот. где было требование "завершения за конкретное конечное число шагов". А через пару вопросов вдруг спрашивалось, завершится ли алгоритм (приведена программа) за конечное число шагов (то есть допускалось, что алгоритм и не завершается за конечное число шагов! ) . А еще могу вам подкинуть вариантик: вместо случайного числа можно взять задачу, про которую неизвестно, имет ли она решение за конечное число шагов. Ну, например, станет ли число 196 палиндромом если шаг за шагом складывать число с полученным перестановкой цифр задом наперед. (. Понятно, что тут тупо перебор - мы не знаем, конечный или нет!

Answer 2

переучился, сердешный. . Давай вернемся к истокам. Алгоритм - это расписанная по шагам инструкция, программа. Так что, если предписано взять случайное, хоть истинное, хоть псевдо. Значит это кому то надо именно так.