На хабре.
Alles_gut пишет:
"а кое-кто учился пять лет решать подобные задачи. И задач оптимизации тоже ой как много. И многие из них в общем виде не решаются. А реальные задачи еще сложнее решаются. Заведем отдельный блог «оптимизационные задачи»? "
В разделе "Алгоритмы". Честно говоря, я немного хохо, но вроде как все задачи, которые можно сформулировать в мат выражениях решаемы - вопрос во времени (простой перебор всех ответов с проверкой на правильность например). Плюс задачи оптимизации редуцируются друг на друга. Толи я дурак, то ли лыжи? [Ответ]

exsulem,

Сообщение от :
вроде как все задачи, которые можно сформулировать в мат выражениях решаемы

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

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

Сообщение от exsulem:
На хабре.
Alles_gut пишет:
"а кое-кто учился пять лет решать подобные задачи. И задач оптимизации тоже ой как много. И многие из них в общем виде не решаются. А реальные задачи еще сложнее решаются. Заведем отдельный блог «оптимизационные задачи»? "
В разделе "Алгоритмы". Честно говоря, я немного хохо, но вроде как все задачи, которые можно сформулировать в мат выражениях решаемы - вопрос во времени (простой перебор всех ответов с проверкой на правильность например). Плюс задачи оптимизации редуцируются друг на друга. Толи я дурак, то ли лыжи?

Ключевое - В ОБЩЕМ ВИДЕ. Т.е. не только численными методами, но и аналитически.
К примеру - есть интегралы, которые "взять" невозможно, но можно посчитать приближено в случае определенного интеграла (т.е. на заданном промежутке) с достаточной точностью.
Еще хуже - с дифурами. Там уже без численных методов на практике - никуда. [Ответ]

exsulem,

Сообщение от :
Тут решаемость компьютерная, т.б. если ты можешь верифицировать (проверить подходит ли ответ) решение, следовательно ты можешь перебором через все возможные последовательности различной длинны алфавита искать правильные решения, если у тебя есть какие то аналитические методы решения - то это уже эвристический алгоритм, который может значительно ускорить нахождение ответов.

Ниче не понял. Численные методы не ищут решение перебором. Они ищут приближенное, обычно итерационно: вначале делается грубая оценка, потом она постепенно уточняется посредством так называемых итераций. Уточнять можно сколько душе угодно, только вот точное решение таким макаром обычно никогда получено не будет. [Ответ]

Church–Turing thesis: "Every effectively calculable function is a computable function", с оговорками. И когда нам проф объяснял что мы вообще можем решать, он показывал к какому типу грамматики относятся матиматические нотации стартуя с аксиом Пеано. Плюс в целом не известно взаимоотношение P и NP, поэтому можно считать неразрешимость всех задач оптимизации вопросом не решенным (в смысле нужно). [Ответ]

Сообщение от Yandex:
Уточнять можно сколько душе угодно, только вот точное решение таким макаром обычно никогда получено не будет.

Проверить любое решение (число/числа), не важно как найденное, является ли оно решением можешь? [Ответ]

Тогда уж надо было назвать "Задачи дискретной оптимизации" или что-то навроде [Ответ]

exsulem, вы гумманитарий что ли?
Перебрать за сколь угодное время все варианты - невозможно. Задачи оптимизации и численные методы направлены на сокращение этого времени до разумного предела. Плата за это, то что решение не точное.

Пример: уравнение x * x = e * e. При поиске х численными методам вы сколь угодно близко сможете подобраться к e, но никогда его не получите. [Ответ]

Сообщение от Yandex:
exsulem, вы гумманитарий что ли?
Перебрать за сколь угодное время все варианты - невозможно. Задачи оптимизации и численные методы направлены на сокращение этого времени до разумного предела. Плата за это, то что решение не точное.

Пример: уравнение x * x = e * e. При поиске х численными методам вы сколь угодно близко сможете подобраться к e, но никогда его не получите.

Как раз конкретно "е" подобрать можно, и 2*e и 3*e. Оценить разницу, и если она меньше эпсилон, ПРОВЕРИТЬ - а не "e" ли это. Аналитически взять производную то можно запросто от чего угодно, такой алгоритм пишется за пару вечеров, с простой рекурсией.
Беда в том что ln (x ^ (3+x) + pi*2) уже просто так не подберешь, а если там возможны большие простые числа, которые не выносятся вперед ответа - то тут уже перебор приближается к космическим цифрам по времени. [Ответ]

Сообщение от Yandex:
exsulem, вы гумманитарий что ли?
Перебрать за сколь угодное время все варианты - невозможно. Задачи оптимизации и численные методы направлены на сокращение этого времени до разумного предела. Плата за это, то что решение не точное.

Пример: уравнение x * x = e * e. При поиске х численными методам вы сколь угодно близко сможете подобраться к e, но никогда его не получите.

Гуманитарий - это типа ругательства в этом разделе?
Опять же насколько я понял, нет доказательства для задач оптимизации (не важно каких, они почти все друг на друга редуцируются) отсутствия полиномных алгоритмов. Просто нам сейчас известны только NP алгоритмы, которые сводятся к перебору в том или ином виде. Поэтому утверждать, что эти задачи неразрешимы, можно только с оговорками и принимая во внимание выше сказанное, аки неразрешимы нами и сейчас. Так же выражение - "Все, что можно записать в виде мат. формулы подлежит вычислению" не нужно понимать буквально, как некую доказанную теорему. Это часть рассуждений о принадлежности математики к определенному типу грамматик и вычислительной мощности машины Тьюринга. [Ответ]