Теория алгоритмов

[Mihaylo]

Пытаюсь понять и установить взаимосвязи на уровне философии. Существует понятие задачи и понятие алгоритма.
У одной задачи может быть несколько алгоритмов [решения]. А один алгоритм может решать несколько задач. То есть существуют теоретико-множественные отношения между задачами...

Если прервать некий алгоритм где-то в процессе выполнения, то часть алгоритма, которая успела выполниться, она ведь тоже является полноценным алгоритмом, но выполняющим другую задачу, а именно: подзадачу той задачи, которую не успел выполнить полноценный алгоритм. Так ведь? Или не всегда?

А существует ли такой алгоритм, который выполняет строго только обозначенную задачу и никакой больше? Этот алгоритм всегда один или, наоборот, много? Например, алгоритм сортировки числового массива помимо сортировки решает задачу поиска максимального числа и минимального числа в массиве. Тут возникает вопрос, как определять границы задач и алгоритмов?

Есть ли по этой тематике, что почитать?

[Sender]

Mihaylo в сообщении #1444609 писал(а):

А существует ли такой алгоритм, который выполняет строго только обозначенную задачу и никакой больше?

Нет, так как любой алгоритм в числе прочего решает задачу решения задач алгоритмами.

[mihaild]

(Оффтоп)

Mihaylo в сообщении #1444609 писал(а):

Пытаюсь понять и установить взаимосвязи на уровне философии

Неудачная идея.

Mihaylo в сообщении #1444609 писал(а):

А один алгоритм может решать несколько задач

В классических определениях - не может. Любой алгоритм задает ровно одну конкретную функцию.

Mihaylo в сообщении #1444609 писал(а):

Например, алгоритм сортировки числового массива помимо сортировки решает задачу поиска максимального числа и минимального числа в массиве.

Нет, не решает. Ответом на задачу поиска максимального числа является число, а на задачу сортировки - массив чисел.
Даже если у нас уже есть алгоритм сортировки, то для получения максимума нужно приложить дополнительные усилия - а именно взять последнее число из массива.

Mihaylo в сообщении #1444609 писал(а):

Есть ли по этой тематике, что почитать?

По теории алгоритмов - Верещагин, Шень "Языки и исчисления" "Вычислимые функции". Или прикладное - Кормен, "Алгоритмы. Построение и анализ".

По "философии алгоритмов" вы можете почитать хоть Порфирьевича (нейросетевой генератор текстов) - я сильно сомневаюсь, что есть более осмысленные тексты.

Порфирьевич писал(а):

Истина состоит в том, что «все просто, потому что больше одного вопроса не может быть» и «один алгоритм не может решить задачу».

[arseniiv]

Mihaylo
А вы случайно не про классы сложности? Тогда про теорию сложности [алгоритмов] читать.

mihaild в сообщении #1444612 писал(а):

По теории алгоритмов - Верещагин, Шень "Языки и исчисления".

Это же второй том, нужен третий, «Вычислимые функции».

[Mihaylo]

mihaild в сообщении #1444612 писал(а):

По "философии алгоритмов" вы можете почитать хоть Порфирьевича

Философия у меня в голове. А я хочу почитать нечто конкретное.

arseniiv в сообщении #1444621 писал(а):

Mihaylo
А вы случайно не про классы сложности? Тогда про теорию сложности [алгоритмов] читать.

Нее, не про сложность.

[mihaild]

(Оффтоп)

arseniiv в сообщении #1444621 писал(а):

Это же второй том, нужен третий

И я же даже специально посмотрел как называется третий том (нужен сильно реже, поэтому не был уверен в точном названии), и всё равно написал не то.

Mihaylo в сообщении #1444653 писал(а):

А я хочу почитать нечто конкретное

Ну вот я дал вам конкретные книги. Устраивают? Если нет, то чем?

[arseniiv]

Mihaylo в сообщении #1444653 писал(а):

Нее, не про сложность.

Я не уверен, что есть литература, где говорят про произвольные задачи / классы задач, дают им точное общее определение, потому что в такой общности как-то не видно, какая была бы польза. Кажется, что сказать на эту тему можно лишь разве чуть больше, чем уже сказал mihaild о примере про сортировку и поиск максимума.

[alesha_popovich]

Mihaylo в сообщении #1444609 писал(а):

А существует ли такой алгоритм, который выполняет строго только обозначенную задачу и никакой больше?

Конечно, например алгоритм, который ничего не делает. Или тождественный алгоритм который просто возвращает то, что ему передали на вход (т.е. тоже по сути ничего не делает)

[Dmitriy40]

alesha_popovich в сообщении #1444721 писал(а):

Или тождественный алгоритм который просто возвращает то, что ему передали на вход (т.е. тоже по сути ничего не делает)

Тут под вопросом, ведь он как минимум принимает данные и возвращает данные, это уже две разные (под)задачи.
Всё же это лишь вопрос терминологии, определений, что считать задачей, что нет.

[realeugene]

Mihaylo в сообщении #1444609 писал(а):

Существует понятие задачи

Определите его, пожалуйста.
Понятие алгоритма определяется строго математически в некоторой модели вычислений. Существуют различные модели вычислений.

[Mihaylo]

mihaild в сообщении #1444674 писал(а):

Ну вот я дал вам конкретные книги. Устраивают? Если нет, то чем?

Не успел даже полистать. Спасибо, посмотрю.

[Mihaylo]

Полистал я Верещагина с Шенем, но не нашел я там желаемого и интересного. Может надо вникать поглубже, но, мне кажется, проблематика зависания программ не относится к тому, что я ищу.

realeugene в сообщении #1444729 писал(а):

Mihaylo в сообщении #1444609 писал(а):

Существует понятие задачи

Определите его, пожалуйста.

Задача - это вопрос, алгоритм - это решение, выход алгоритма - ответ. Условие задачи - это вход программы (алгоритма).

В процессе выполнения алгоритма могут быть вычислены какие-то промежуточные результаты, следовательно, решена некоторая подзадача. Но другой алгоритм может получать другие промежуточные результаты и соответственно решать другие подзадачи.

Фактически интерес мой следующий: я хочу разобраться как задача бьется на подзадачи, на столько подзадач, что в итоге алгоритм будет проанализирован вплоть до отдельного своего шага. С алгоритмом все понятно: каждый его последующий шаг принимает от предыдущего шага состояние [регистров] и некоторую память. А что происходит с задачей и подзадачами? Здесь ведь тоже наблюдаются отношения между множествами, однако они для меня никак не формализованы.

[mihaild]

Ну каждый алгоритм решает подзадачи вида "что получится на $i$-м шаге этого алгоритма", и не решает никаких других (не эквивалентных этим). Сойдет?

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

[arseniiv]

Плюсмного-много-много.

Mihaylo в сообщении #1444878 писал(а):

Условие задачи - это вход программы (алгоритма).

Ну нет. «Найдите прямую, проходящую через две точки. Точки не совпадают» — тут алгоритму будут подаваться на вход какие-то представления точек, но ему например не будет подаваться на вход ни в каком виде информация, что они не совпадают. И даже если будет, то что он с ней сделает?

-- Вс мар 15, 2020 02:42:43 --

Задача — это что-то, что можно решить, может быть в зависимости от каких-то параметров. Подзадача — это что-то, что нужно обязательно решить для решения задачи [хотя бы для одного (слишком слабо, но абстракции на пустом месте лучше не раздувать, так что даже это пояснение я убираю в скобки за сомнительностью) значения параметров задачи, и если уже зафиксирован какой-то способ её решения, потому что мы можем нуждаться в разном, идя разными путями]. Я не припомню чтобы у этих слов были какое-то совместное словоупотребление, требующее большей детальности определений.

[Mihaylo]

Ну ещё вот такой мыслительный эксперимент: есть задача, но не известен алгоритм решения. Эвристическим методом найден один шаг алгоритма, который что-то выполняет с условием задачи, то есть формально этот шаг корректен. Этот шаг решает некую подзадачу.
Мы имеем две задачи, одна из которых претендует быть подзадачей другой. Как проверить, не предъявляя окончательный алгоритм большой задачи?