Чтобы ответить «какие проблемы можно решить с помощью вычислений», мы разработали теорию вычислимости. Для задач, которые являются вычислимыми, есть ли теория, чтобы ответить на вопрос «программа, которую я получаю, самая простая»?
Я не думаю, что вычислительная сложность ответит на вопрос. Я думаю, что это учитывает, сколько времени нам нужно (хотя измеряется абстрактно).
Я не уверен, что алгоритмическая теория информации ответит на вопрос. Кажется, что теория говорит о размере, где эквивалентность минимального размера и простейшего не очевидна для меня (ну, по крайней мере, мне они кажутся разными).
Я думаю, что теория должна по крайней мере определить «простое» или «более простое» отношение.
Теперь я убежден, что мне стоит взглянуть на Колмогоровскую сложность. Тем не менее, я хотел бы объяснить, что у меня на уме, когда я задавал вопрос.
Когда я улучшаю программу, я пытаюсь уменьшить ненужные связи между различными частями программы (возможно, перераспределение частей, чтобы было меньше или слабее соединений). Поскольку количество соединений уменьшается, программа чувствует себя «проще». Отсюда и выбор слова «простой», когда я формулирую вопрос. Весьма вероятно, что размер программы также уменьшится, но это хороший побочный эффект, а не основная цель. Очевидно, что процесс улучшения не может продолжаться вечно. Есть момент, на котором я должен остановиться. Если, только рассматривая «структуру» (извините за другое неопределенное понятие) или «отношение», я могу убедить себя, что больше ничего нельзя сделать?
Здесь содержится лучшее описание моего понятия о сложности.
Ответы:
Эта проблема изучается в алгоритмической теории информации. То, что вы определяете, называется сложностью Колмогорова-Чейтина.
http://en.wikipedia.org/wiki/Kolmogorov_complexity
И кажется, что понятие простоты, которое вам требуется, может быть формализовано через понятие меры сложности, которое формализовано аксиомами Блюма.
http://en.wikipedia.org/wiki/Blum_axioms
Представляется также, что можно обобщить сложность Колмогорова, чтобы принять во внимание другие меры сложности. Смотрите ссылку ниже. (Статья Википедии о сложности Колмогорова посвящена этой проблеме.)
Бургин1990 - Обобщенная колмогоровская сложность и другие меры двойной сложности Кибернетика и системный анализ Том 26, № 4, 481-490
источник
Ответ на первый вопрос: да, есть теория, это Алгоритмическая теория информации, и они называются «Элегантные программы» (Григорий Чайтен).
По второму вопросу о том, "самая ли простая программа у меня"?
Ответа нет , потому что это неисчислимый вопрос, невозможно доказать, что программа является программой Elegant.
Я добавил ответ, чтобы добавить упоминание об элегантных программах .
источник
Существуют разные подходы к решению, что является простым кодом, а что нет.
Но, к сожалению, не существует автоматического способа определить это, например, Сложность по Колмогорову с рекурсивными функциями, некоторые рекурсивные функции (логические глубины) просты, но понимание этого не так просто.
По моему опыту, наша команда работала в системе, и мы нашли «простую» процедуру в Oracle (не более 50 строк) ... и мы попытались понять это, потребовалось 2 месяца (и несколько встреч) для полного понимания дело не в сложности кода, а в логике каждой переменной.
Я думаю, что способ определить, насколько простым является код: «прочитайте код и подумайте, сколько времени уходит на его понимание».
Итак, "Самая простая программа для решения проблемы?" можно разделить на:
а) простота кода (понятный код), но он слишком субъективен.
б) чрезмерная сложность функции, если у меня есть проблема X, тогда я должен решить задачу DX (Delta X), чтобы решить ее, где DX должен стремиться к X.
Например, если моя проблема (один) «очистить яблоко», и я должен сделать это на PHP (и язык), то
если мне очень повезло и у PHP есть функция function_peel_apple (), то это самый простой код из когда-либо X = 1 DX = 1, просто вызовите функцию и все!
Напротив, если мне не так повезло, но существуют функции function_peel () и function_get_apple (), то X = 1 (одна задача) и DX = 2 (две задачи).
Если в худшем случае не существует какой-либо функции, то я должен создать одну (или более одной) самостоятельно и добавить несколько задач до решения проблемы, теперь это сложная программа.
источник