Вот есть какая-то задача, необходимо для ее решения придумать алгоритм. Задача оперирует какими-то данными.
При одной организации данных и способе описания задачи на их основе алгоритмы получаются крайне громоздкими и нетривиальными.
Но, организовав входные данные иначе, просто организовав, даже без всяких решений задачи, как по щелчку пальцев задача и алгоритм становятся чудесным образом простыми, быстрыми и понятными.
Вот и вопрос — как узнать что твои данные организованы оптимальным образом для решения той или иной задачи? Есть ли какой-то формальный способ убедиться в том, что лучше всего данные организовывать и описывать именно так?
Здравствуйте, Homunculus, Вы писали:
H>Вот и вопрос — как узнать что твои данные организованы оптимальным образом для решения той или иной задачи? Есть ли какой-то формальный способ убедиться в том, что лучше всего данные организовывать и описывать именно так?
У меня такое чувство, что организация данных — это часть алгоритма. Например, для некоторых алгоритмов использование фиббоначиевой кучи сильно ускоряет дело и упрощает алгоритм. Ну и можно дойти до нормальных форм в БД, которые и нужны для ускорения в том числе типичных задач
Здравствуйте, Homunculus, Вы писали:
H>Вот есть какая-то задача, необходимо для ее решения придумать алгоритм. Задача оперирует какими-то данными. H>При одной организации данных и способе описания задачи на их основе алгоритмы получаются крайне громоздкими и нетривиальными. H>Но, организовав входные данные иначе, просто организовав, даже без всяких решений задачи, как по щелчку пальцев задача и алгоритм становятся чудесным образом простыми, быстрыми и понятными.
H>Вот и вопрос — как узнать что твои данные организованы оптимальным образом для решения той или иной задачи? Есть ли какой-то формальный способ убедиться в том, что лучше всего данные организовывать и описывать именно так?
Формальный — это алгоритмический. Предположим что такой способ есть, тогда его входные данные тоже должны быть как-то формализованы?
Здравствуйте, Homunculus, Вы писали:
H>Вот есть какая-то задача, необходимо для ее решения придумать алгоритм. Задача оперирует какими-то данными. H>При одной организации данных и способе описания задачи на их основе алгоритмы получаются крайне громоздкими и нетривиальными. H>Но, организовав входные данные иначе, просто организовав, даже без всяких решений задачи, как по щелчку пальцев задача и алгоритм становятся чудесным образом простыми, быстрыми и понятными.
H>Вот и вопрос — как узнать что твои данные организованы оптимальным образом для решения той или иной задачи? Есть ли какой-то формальный способ убедиться в том, что лучше всего данные организовывать и описывать именно так?
Звучит как "придумать критерий оптимальности, когда мы не знаем критерий оптимальности". К сожалению так не бывает.
Обычно считают количество операции, объем памяти нужные для алгоритма и выводят асимптотику. Если получается полиномиальная или меньше, то считается что алгоритм достаточно хорош.
Здравствуйте, Homunculus, Вы писали:
H>Вот и вопрос — как узнать что твои данные организованы оптимальным образом для решения той или иной задачи? Есть ли какой-то формальный способ убедиться в том, что лучше всего данные организовывать и описывать именно так?
Данные первичны. Что там на выходе? Отчеты? Графики? Чертеж для станка с ЧПУ? Как бы то ни было, зная форматы выходных данных, строим входные так, чтобы минимизировать затраты при преобразованиях.