Насколько я знаю, в общем случае теоретически невозможно написать самую короткую программу, выполняющую определенную задачу. Существует ли подобное ограничение на идеальную оптимизацию?
12.05.09 12:02: Перенесено модератором из 'Алгоритмы' — Кодт
Программировать сложно. Но не программировать еще сложнее.
Здравствуйте, DSblizzard, Вы писали:
DS>Насколько я знаю, в общем случае теоретически невозможно написать самую короткую программу, выполняющую определенную задачу.
Число программ меньше любого определённого размера конечно. Следовательно, для любой выполняемой задачи существует самая короткая программа выполняющая её.
Здравствуйте, DSblizzard, Вы писали:
DS>Насколько я знаю, в общем случае теоретически невозможно написать самую короткую программу, выполняющую определенную задачу.
Я бы сказал, невозможно написать саму длинную программу, выполняющую определенную задачу, хотя многие, включая MS, похоже усиленно стараются...
Здравствуйте, DSblizzard, Вы писали:
DS>Насколько я знаю, в общем случае теоретически невозможно написать самую короткую программу, выполняющую определенную задачу. Существует ли подобное ограничение на идеальную оптимизацию?
С оптимизацией вообще не очень понятно, потому что то, что будет оптимальным в одном случае, не будет оптимальным в другом. Например, заранее трудно предугадать, что окажется большим дефицитом: память, процессор или пропускная способность ввода-вывода. Я хочу сказать, само понятие идеально оптимизированной задачи невозможно определить в общем случае.
Re[2]: Возможна ли идеальная оптимизация?
От:
Аноним
Дата:
11.05.09 01:47
Оценка:
Здравствуйте, Pzz, Вы писали:
Pzz>С оптимизацией вообще не очень понятно, потому что то, что будет оптимальным в одном случае, не будет оптимальным в другом. Например, заранее трудно предугадать, что окажется большим дефицитом: память, процессор или пропускная способность ввода-вывода. Я хочу сказать, само понятие идеально оптимизированной задачи невозможно определить в общем случае.
Забыл добавить, оптимизация по скорости. Ввод-вывод и ограничения памяти не учитываем.
Здравствуйте, Don Reba, Вы писали:
DR>Число программ меньше любого определённого размера конечно. Следовательно, для любой выполняемой задачи существует самая короткая программа выполняющая её.
Некоторые программы просто зависают и определить, закончат ли они работу теоретически невозможно.
Программировать сложно. Но не программировать еще сложнее.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, Pzz, Вы писали:
Pzz>>С оптимизацией вообще не очень понятно, потому что то, что будет оптимальным в одном случае, не будет оптимальным в другом. Например, заранее трудно предугадать, что окажется большим дефицитом: память, процессор или пропускная способность ввода-вывода. Я хочу сказать, само понятие идеально оптимизированной задачи невозможно определить в общем случае.
А>Забыл добавить, оптимизация по скорости. Ввод-вывод и ограничения памяти не учитываем.
Как тебе уже сказали, теоретически при фиксированной машине, возможно, а практически -- не имеет смысла, ибо на соседней машине будет работать иначе. Кроме того, "ограничения памяти ты можешь, конечно, не учитывать", вот только скорость их будет "учитывать" и без тебя.
Здравствуйте, DSblizzard, Вы писали:
DS>Здравствуйте, Don Reba, Вы писали:
DR>>Число программ меньше любого определённого размера конечно. Следовательно, для любой выполняемой задачи существует самая короткая программа выполняющая её.
DS>Некоторые программы просто зависают и определить, закончат ли они работу теоретически невозможно.
В данном случае это значения не имеет. Для оптимизации по скорости достаточно выбрать одну, любую, решающую задачу, а для любой другой достаточно дождаться, чтобы она проработала такое же время, и отбросить, как точно, не оптимизирующую.
Здравствуйте, DSblizzard, Вы писали:
DS>Некоторые программы просто зависают и определить, закончат ли они работу теоретически невозможно.
Это справедливо только для машины Тьюринга с бесконечной памятью. Реальные программы имеют указатели фиксированного размера. На них, опять же теоретически, проблемы остановки нет.
Здравствуйте, DSblizzard, Вы писали:
DS>Насколько я знаю, в общем случае теоретически невозможно написать самую короткую программу, выполняющую определенную задачу. Существует ли подобное ограничение на идеальную оптимизацию?
"идеальная оптимизация" практически невозможна. Одна и таже программа может работать быстрее или медленее в разных конфигурациях компа.
Зато вполне существует ассимптотическая сложность и оценка количества операций при конкретных входных данных.
Здравствуйте, vadimcher, Вы писали:
V>Как тебе уже сказали, теоретически при фиксированной машине, возможно, а практически -- не имеет смысла, ибо на соседней машине будет работать иначе. Кроме того, "ограничения памяти ты можешь, конечно, не учитывать", вот только скорость их будет "учитывать" и без тебя.
И еще, при фиксированных входных данных. Потому что оптимальная с точки зрения скорости последовательность действий от данных, как правило, зависит.
Здравствуйте, gandjustas, Вы писали:
DS>>Насколько я знаю, в общем случае теоретически невозможно написать самую короткую программу, выполняющую определенную задачу. Существует ли подобное ограничение на идеальную оптимизацию?
G>"идеальная оптимизация" практически невозможна. Одна и таже программа может работать быстрее или медленее в разных конфигурациях компа. G>Зато вполне существует ассимптотическая сложность и оценка количества операций при конкретных входных данных.
Прикол в том, что асимптотическая сложность тоже в общем случае зависит от "конфигурации" компьютера.
Пример — с помощью Алгоритма Шора можно на квантовом компьютере раскладывать большие числа на множители за полиномиальное время. Дело за малым — построить квантовый комьютер для размерностей, представляющих практический интерес.
В свете этого, действительно, ответ на вопрос топикстартера однозначный: "Нет"
Здравствуйте, Don Reba, Вы писали:
DR>Это справедливо только для машины Тьюринга с бесконечной памятью. Реальные программы имеют указатели фиксированного размера. На них, опять же теоретически, проблемы остановки нет.
Зато есть неизвестные входные параметры.
DS>>Насколько я знаю, в общем случае теоретически невозможно написать самую короткую программу, выполняющую определенную задачу. DR>Число программ меньше любого определённого размера конечно. Следовательно, для любой выполняемой задачи существует самая короткая программа выполняющая её.
Здравствуйте, Don Reba, Вы писали:
DR>Здравствуйте, DSblizzard, Вы писали:
DS>>Насколько я знаю, в общем случае теоретически невозможно написать самую короткую программу, выполняющую определенную задачу.
DR>Число программ меньше любого определённого размера конечно. Следовательно, для любой выполняемой задачи существует самая короткая программа выполняющая её.
существовать то она существует. но найти ее нельзя. даже если ты будеш перебирать все программы ты уткнешся в то что нельзя выяснить являются ли они эквивалентными.
рассмотрение этой проблемы я бы делел с точки зрения конструктивного или интуиционистского (?) анализа.
Вот что удалось раскопать самому:
Wikipedia, Compiler optimization:
"However, optimizing compilers are by no means perfect. There is no way that a compiler can guarantee that, for all program source code, the fastest (or smallest) possible equivalent compiled program is output; such a compiler is fundamentally impossible because it would solve the halting problem.
This may be proven by considering a call to a function, foo(). This function returns nothing and does not have side effects (no I/O, does not modify global variables and "live" data structures, etc.). The fastest possible equivalent program would be simply to eliminate the function call. However, if the function foo() in fact does not return, then the program with the call to foo() would be different from the program without the call; the optimizing compiler will then have to determine this by solving the halting problem."
Вроде, comp.compilers:
"Do not confuse the halting problem with the question whether a specific program terminates/loops on a specific computer. The halting problem is not about computers, but about programs."
Программировать сложно. Но не программировать еще сложнее.
Рассмотрим более-менее практический пример, но в то же время допускающий анализ.
Пишем приложение, которое будет выполняться на одной архитектуре, но в будущем — на более мощных компьютерах, которые еще не доступны. Показатели компьютеров меняются только количественно — например, не появляется новых ускоренных инструкций по обработке операций с плавающей запятой. Никаких кэшей, вся память с одним временем доступа. Программа достаточно простая, так что мы знаем, что проблемы остановки для нее не существует. Различных входных данных — потенциально неограниченное количество.
Ввод и вывод происходят в начале и конце программы и время, которое на них тратится, не учитывается. Как обстоят дела в этом случае?
Программировать сложно. Но не программировать еще сложнее.
Здравствуйте, DSblizzard, Вы писали:
DS>Насколько я знаю, в общем случае теоретически невозможно написать самую короткую программу, выполняющую определенную задачу. Существует ли подобное ограничение на идеальную оптимизацию?
По теореме об ускорении невозможно написать и, например, самую быструю программу.
