Обчислювальні задачі існують об’єктивно, незалежно од того, чи зустрічалися вони конкретно Вам чи ні.

Я особисто був задіяний у проекті, в якому лабораторія мала станції прийому біологічних матеріалів розкидані по місту. І декілька разів на день вони запускали машини, що роз’їзджалися по місту, збирали біоматеріали і поверталися назад до головної лабораторії, де вони власне і проводили аналізи. І їм треба було так розписати маршрут машин, щоб довезти біоматеріали якомога швидше до центральної лабораторії. Там були ще додаткові умови, через що маршрути досить часто треба було перераховувати щодня, і кількість точок станцій прийому була декілька десятків, тож, повний перебір — це не варіант. Більш того, вони планували відкрити ще якусь кількість точок забору біоматеріалів. Це от прямо і є задача комівояжера, яка зустрілася в реалі.

Ми вирішили цю задачу своїм самописним варіантом гілок-і-границь, який: (а) працював швидко, шо дозволяло трохи не в режимі реального часу прораховувати маршрути; (б) видавала оптимальні маршрути.

Дейкстра знаходить найкоротший шлях між фіксованою вершиною та усіма іншими. Але в задачі комівояжера Вам необхідно, щоб сумарний шлях, шо проходить через усі вершини, був би мінімальним. Вибираючи щоразу вершину з найкоротшою дистанцією до поточної, може так статись, що сумарно пройдений шлях буде довшим за шлях, якби Ви обирали не найменш віддалені вершини.

Окрім того алгоритм Дейкстри і є приклад жадібного алгоритму. Більш того, автор його якраз і використав (хоча і непрямо) в своїй жадібній реалізації, коли викликав функцію розрахунку найкоротшого шляху між двома аптеками.

Я не знаю, какой советский индус-программист Вас покусал, но, судя по этому крику души без единого знака препинания, покусал он Вас, однако, знатно. Сочувствую что-ли :\

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

Что, как мне кажется, я смог уловить, так это то, что Вы из тех людей, которые берутся решать задачу, даже не разобравшись, а что же Вы решаете, лишь бы что-то решить. И неважно решение той ли задаче или нет. Решение есть? Есть! Ну и что, что это может быть решением какой-то другой задачи?!

Смотрите, задача звучала так (спасибо Andrii Tymoshenko за точный текст):

Дано файл(number.dat) з цілочисельним скінченним рядом (n=10). Елементи ряду є випадкові цілі числа в межах від —10 до 10, включаючи 0. Визначити за ознакою д’Ламбера, що ряд являється збіжним та запищіть результат у файл(answer.dat). Відповідь буде зараховано у форматі «sum>1 збіжний», «sum<1 розбіжний», «sum=1 невідомо». Можна використовувати будь яку зручну мову програмуваня

Вас, возможно, это удивит, но вменяемые люди редко вставляют в текст каких-либо заданий случайные слова. Тем более настолько специфические как «ознака д’Аламбера». То есть, человек, который составлял это задание, имел в виду что-то очень конкретное, раз он выбрал именно эти слова. И заметьте — про сумму в условии задачи ничего не говорится, говорится только о проверке по д’Аламберу. Какая-то сумма (sum) вспоминается вскользь только в самом-самом конце задачи, когда идет обсуждение формата вывода. Опустим момент с тем, что ряд у нас конечный (то есть он автоматически сходящийся), и посмотрим, а что же там за сумма у д’Аламбера? А у критерия д’Аламбера нет никакой суммы! Тогда сумма чего же это?!

Скорее всего, что это сумма всех чисел. Но! еще раз — человек, который составлял текст задачи, что-то имел в виду, говоря о проверке по конкретному критерию. И очень даже возможно, что то, что имел в виду тот человек — это совсем не то же самое, что Вы думаете, что он имел в виду. Это может быть сумма первых 5 элементов, первых 7, а, может, последних двух, так как в д’Аламбере нас интересует отношение двух соседних членов последовательности в бесконечности. Так какая сумма должна быть? И почему она должна быть не меньше 1 для сходимости? У д’Аламбера, который правильный, то все наоборот.

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

Вы уверены, что проблема была в неспособности учителей рассказать, как записывать и считывать данные в/из файла, а не в постановке задачи? Просто Ваши уточнения (спасибо за них, к слову!) сделали ее еще менее понятной, если честно. Я бы тоже завис на некоторое время, если б мне попалась такая задача, думая, что я явно не понимаю условие.

Вот Вы говорите, что необходимо было проверить по д’Аламберу сходимость ряда, когда дана конечная последовательность его членов. Но то, что Вы проверите на каких-то членах выполнимость условия д’Аламбера — ничего не скажет о сходимости ряда. И это будет верно для любого критерия сходимости. Вы в любом ряду можете заменить произвольное, но конечное количество членов на какие только захотите, сходимость/расходимость ряда останутся прежними. То есть проверка конечного количества членов ничего не даст.

Но дальше Вы еще и добавили, что

До задачі ж дається пояснення, що ряд скінченний і навіть сказано за яким принципом це визначити.

и тут я совсем запутался. Если ряд конечен, то он сходящийся. Все конечные ряды — сходящиеся. И зачем нужна проверка конечности ряда?

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

n — это конечное число. 1/n — все еще конечное число (даже не очень понимаю, зачем Вы его ввели тут). Это не бесконечно малая.

Лимит мы определяем через классический (ε, δ)-формализм Вейерштрасса. Где тут нестандартный анализ?

Где тут нестандартный анализ? Я вроде нигде не использовал бесконечно малые либо бесконечно большие величины. Все по классическому анализу Вейерштрасса.

Так само ці ж вчителі готують до олімпіад з програмування, а коли отримують завдання, які були в попередні роки кажуть «та таке неможливо зробити».

P.S. Олімпіадна задача це взяти числи з файлу порахувати чи це збіжний ряд і записати у файл

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

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

Набросал решение этого «парадокса»:

Будем считать ошибку En приближения длины диагональной линии через длину ступенчатой кривой, у которой количество ступенек — это какое-то произвольное, но конечное число n. Очевидно, что длина диагональной линии — sqrt(2), в то время как длина ступенчатой кривой 2 для любого n. Таким образом, какое б это n не было, ошибка приближения всегда будет 2 — sqrt(2). Даже если устремить это n в бесконечность. Иначе говоря, длину диагонали не приблизить ступенчатой функцией, так как ошибка приближения всегда константна.

А вот площадь треугольника — очень даже приближается, и это будет прямо таки «учебниковое» определению интеграла Римана через суммы Дарбу (или Римана? всегда их путаю).

Ага, значит речь о криволинейном интеграле. Тогда Ваша фраза

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

совершенно чудная. Криволинейный интеграл ПО ОПРЕДЕЛЕНИЮ такой, у которого поддифференциальная функция гладкая (на самом деле кусочно-гладкая). Если же под дифференциалом будет негладкая функция, то интеграл не «теряет смысл», а просто это НЕ криволинейный интеграл.

Криволинейный интеграл можно рассматривать как особый случай интеграла Римана-Стилтьеса, когда функция, по которой мы проводим интегрирование — кусочно-гладкая. Но для Римана-Стилтьеса существует теорема, которая говорит, что если поддифференциальная функция на интервале [a,b] конечной вариации, то интеграл существует для любой непрерывной на [a,b] функции. Обратите внимание — поддифференциальная функция должна быть конечной вариации, о гладкости ничего не говорится. И то — теорема постулирует достаточное условие, но не необходимое, а значит интеграл Римана-Стилтьеса существует даже для более широкого класса поддифференциальных функций.

В качестве примера можно взять дьявольскую функцию Кантора, которая хоть и дифференцируемая практически всюду, но все же далеко не гладкая и даже не кусочно-гладкая. Но она непрерывна и монотонна на [0,1], а значит имеет конечную вариацию. Ergo — она может выступать в качестве поддифференциальной функции в интеграле Римана-Стилтьеса, и этот интеграл имеет вполне определенный смысл. Так что гладкость не нужна для «осмысленности» интегрирования, что б это не значило.

Почему криволинейные интегралы выделяют отдельно? Просто потому, что если у Вас поддифференциальная функция g(x) гладкая, то в этом случае интеграл Римана-Стилтьеса преобразуется в самый обычный интеграл Римана путем замены dg(x)=g’(x)dx. Вот и все. Это просто приятный и хороший случай интегрирования по Риману-Стилтьесу.

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

Тут Вы тоже неправы. Ограниченная функция интегрируема по Риману (а я так понимаю, мы тут говорим об интеграле Римана) на интервале [a,b] тогда и только тогда, когда она практически всюду непрерывна на [a,b]. Гладкой она быть не обязана.

Так, например, интеграл от f(x) = |x| на интервале [-5,+5] существует и равен 25, хотя f(x) не дифференцируема в точке x = 0.

Честно говоря, я не очень понимаю смысл Ваших слов. Во-первых, о каком конкретно интеграле Вы ведете речь? Во-вторых,

Вот это dx. Именно она должна быть гладкой что б интегрирование имело смысл.

dx — это прирост аргумента? Или что это значит? На сколько я знаю, dx сам по себе не имеет никакого смысла. Смысл имеют обозначения d/dx (операторная форма) либо dy/dx (как синоним взятия производной). Это цельные обозначения, отдельно dx бессмысленно. В диффурах и интегральных уравнениях оно всегда идет вместе с dy, где y — это функция от х.

Если же dx в смысле бесконечно малого прироста, то прирост чего? Аргумента относительно себя самого же? Так это всегда 0. Если же это в смысле df = f’dx, где f(x) = x, то получается абсолютно ничего не значащая тривиальность dx = df = f’dx = [x]’dx = dx. Но в этом случае совершенно непонятна Ваша фраза

Именно она должна быть гладкой что б интегрирование имело смысл.

так как категория «гладкости», насколько мне известно, применима только к функциям, а dx — это какой-то неведомый зверь.

Переход к пределу только для гладких функций где производные сходятся.

Ну, это конечно же неправда. Контрпримером служит, например, функция f(x) = |x|. В точке x=0 она с любой стороны сходится к 0, но тем не менее у нее нет ни одной производной в нуле.

Другим примером служит Виннеровский процесс — он всюду непрерывен, а значит его предел существует в каждой точке, но при этом он нигде не дифференцируем, что значит, что у него нет ни одной производной ни в одной точке.

Так что, как видите, не только гладкие функции имеют пределы.

То есть не существует неразрешимых задач? Да и чем же тогда Ваш А-ритм отличается от алгоритма? Только конкретно. Без этих Ваших «да всем!». Вот очень конкретно.

Допустим, я смотрю на какой-то текст решения задачи. Как мне определить, что это не алгоритм, а именно А-ритм?

То есть полнота по Тьюринга, оке. А что же тогда такое теорема о полноте по Тьюринга? И с чего это вдруг

У читателя правомерно возникает вопрос, а нахрена это все? Есть МТ. Найти невыполнимые задачи для нее согласно теореме о полноте затруднительно. И вообще нет проблем.

Невычислимых проблем — вагон и малая телега. То, что Вы с ними не сталкивались — это не значит, что они редки. Я Вам даже больше скажу — их бесконечно раз больше, чем вычислимых проблем. Любая невычислимая функция, любое невычислимое число (это частный случай невычислимый функций) — примеры невычислимых задач. Их комбинации также будут скорее всего невычислимыми задачами. Еще примеры: задача Остановки, Колмогоровская сложность, константа Хайтина и другие.

Что такое теорема о полноте? О какой полноте идет речь? Вы дважды уже упомянули эту теорему, но нигде не даете ее утверждения.

У понятия «алгоритм» нет определения. И быть не может. Алгоритм — это одно из неопределяемых понятий, которое мы понимаем интуитивно через его свойства. Так, например, вот это «определение»

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

Допустим, у нас есть некоторая задача. Скажите, будет ли алгоритмом ее решения последовательность действий:

1. Реши задачу
2. PROFIT!!!

Невозможно сказать, что НЕ является алгоритмом, так как нет критерия, чтоб определить, что же такое алгоритм. У машин Тьюринга, к слову, тоже нет никакой конкретной последовательности шагов, но тезис Тьюринга-Черча говорит о том, что все алгоритмы реализуемы на машине Тьюринга. И обратите внимание на слово «тезис» — это не теорема, так как это утверждение недоказуемо как раз из-за отсутствия определения алгоритма.

Ну, математические тексты — это и есть комментарии к формулам, и они составляют бóльшую часть текста. Более того идеалом математического текста (хотя, возможно, уже и недостижимым на сегодняшний день) является такой труд, который, если изъять оттуда все формулы и всю математическую нотацию, останется понятным, и любой специалист в этой области сможет без труда восстановить ход размышлений и формулы.

Так что Ваше замечание некорректно: математики пишут комментарии к своим работам, и как раз эти самые комментарии и являются продуктом их работы. Иначе другие не смогут их понять.

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

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

Тогда Вы можете прямо ответить, что Вы создаете — формальную вычислительную модель или вычислительное устройство?

Вы говорите о совсем другом. Недетерминизмов много разных. Тот, что Вы имеете в виду, и тот о котором я говорю — это разные недетерминизмы.

В вашем случае — это проблематичность предсказания результата работы многопоточных систем.

Я же говорю про недетерминизм в контексте машин Тьюринга, когда существует возможность «разделения» выполняющих потоков (хотя машины Тьюринга не имеют потоков в нашем обычном понимании). Например, самый тривиальный алгоритм для решения задачи Выполнимости для НМТ всегда завершается и всегда имеет однозначный ответ, который зависит от входных данных. То есть несмотря на то, что машина недерминированна и сам алгоритм как бы недетерминированный — ответ машины всегда будет в данном случае детерминирован. Но это ведь не то же самое, что и недетерминированность в многопоточных системах?