Нас всех в начальной школе мучали заданиями типа "продолжите последовательность". Мы выполняли их, используя однотипные приемы: посчитать разность, найти закономерность в последовательности разностей или разбить последовательность на две подпоследовательности(через одно число например) и искать закономерности в каждой из подпоследовательностей. Особо одаренные переводили числа в другую систему счисления и искали закономерности там. Вариантов бесконечно много.
Но вот я закончил институт, и уже думаю, как своих детей в школу поведу. И в минуты отдыха во время серфа по разным форумам натыкаюсь я на эти пресловутые задачи "продолжить последовательность". Образование у меня не совсем математическое (скорей, техническое), но подвох в этих задачах я начал чуять только недавно.
А все дело в том, что даны первые члены последовательности, но однозначное правило задания не указано, значит сама последовательность не задана. Значит любое число будет являться правильным продолжением последовательности.
Первой мыслью было писать произвольные числа в продолжении последовательности и говорить, что раз задача поставлена некорректно, то мы ее доопределим и дадим ответ согласно новым определениям. И задача будет решена правильно.
Но оставлять нерешенной задачу, пусть даже и поставленную безграмотно, это не очень хорошо. Так что раз я физик, то было бы логично применить какие-нибудь знания в области обработки экспериментальных данных (не устану повторять, что это самая полезная дисциплина, которая мне преподавалась). Для этого нужно экстраполировать функцию в целых числах. Но вот незадача! В реальной жизни мы экстраполируем функции, заранее зная, какого вида она должна быть. Это значит, что мы выбираем функцию, схожую по поведению с начальными данными, параметризуем ее, получаем, скажем, функцию вида:
Потом мы из исходных данных подбираем параметры a и b так, чтобы минимизировать среднеквадратичное отклонение (или что вы там любите минимизировать). Ну а дальше подставляем следующие значения n для продолжения последовательности. Здесь есть много НО. Во-первых, последовательность целочисленная (хотя этого не указывают в задаче, но подразумевают). Так что для целочисленной последовательности нужно применять какие-то особые экстраполяции (ну или просто к функции дописывать оператор взятия целой части числа). Задача экстраполяции превращается в несуразную и исполинскую. Но имеющую право на жизнь и даже имеющую решение, но опять же с допущением (вид функции).
Что же говорит чистая математика в этом случае? Ответ мне подсказал один (возможно) математик (возможно). Ответ в принципе очевиден, только нужно было ориентироваться в терминах.
Для вводной приведу несколько примеров.
Рассмотрим бесконечную последовательность, состоящую только из единиц:
.png)
Мы можем вывести любой член последовательности для любого N. При этом есть бесконечно много способов задать эту последовательность. Например:
.png)
.png)
Но вот я закончил институт, и уже думаю, как своих детей в школу поведу. И в минуты отдыха во время серфа по разным форумам натыкаюсь я на эти пресловутые задачи "продолжить последовательность". Образование у меня не совсем математическое (скорей, техническое), но подвох в этих задачах я начал чуять только недавно.
А все дело в том, что даны первые члены последовательности, но однозначное правило задания не указано, значит сама последовательность не задана. Значит любое число будет являться правильным продолжением последовательности.
Первой мыслью было писать произвольные числа в продолжении последовательности и говорить, что раз задача поставлена некорректно, то мы ее доопределим и дадим ответ согласно новым определениям. И задача будет решена правильно.
Но оставлять нерешенной задачу, пусть даже и поставленную безграмотно, это не очень хорошо. Так что раз я физик, то было бы логично применить какие-нибудь знания в области обработки экспериментальных данных (не устану повторять, что это самая полезная дисциплина, которая мне преподавалась). Для этого нужно экстраполировать функцию в целых числах. Но вот незадача! В реальной жизни мы экстраполируем функции, заранее зная, какого вида она должна быть. Это значит, что мы выбираем функцию, схожую по поведению с начальными данными, параметризуем ее, получаем, скажем, функцию вида:
Что же говорит чистая математика в этом случае? Ответ мне подсказал один (возможно) математик (возможно). Ответ в принципе очевиден, только нужно было ориентироваться в терминах.
Для вводной приведу несколько примеров.
Рассмотрим бесконечную последовательность, состоящую только из единиц:
- Сказать, что для любого N
.png)
- Бесконечно перечислять все члены последовательности (это займет бесконечное время, но это же математика)
- Сказать что последовательность состоит из 2 подпоследовательностей, каждая из которых состоит только из единиц
- и так далее...
Рассмотрим поледовательность натуральных чисел:
Ее так же можно задать бесконечным числом способов. Не буду уже перечислять варианты задания последовательности, ибо это и так понятно, глядя на первый пример.
Какой же способ задания бесконечной последовательности выбрать? Ну нормальный человек бы выбрал тот, который короче. Иногда человек не может уловить смысла самого короткого определения, поэтому ему нужно определение подлиннее. Совсем имбецил вообще определений не понимает, поэтому ему нужно бесконечное время перечислять все члены последовательности.
У программистов часто стоит вопрос, каким образом лучше реализовать алгоритм: кратко и чтобы работал быстро, но при этом код будет нечитаем и чтобы его понять понадобится много человеко-часов, или написать, чтобы он работал медленно, но читался понятно.
Математика - это такая наука, которая формализует все, даже очевидные вещи. Так произошло и с определением простоты. Для заданной последовательности ее сложность можно определить через Колмогоровскую меру сложности. Однако можно применить и другие менее формализованные методы: длина машины Тьюринга для задания последовательности, количество букв в описании последовательности соседом по подъезду с первого этажа и т.д.
Таким образом мы должны выбрать такое определение, Колмогоровская сложность которого была бы минимальна.
Теперь приблизимся к исходной задаче: заданы первые несколько членов бесконечной целочисленной последовательности. Здесь нужно вспомнить (это не в моем случае) или найти (а вот это в самый раз) теорему о том, что для любой бесконечной последовательности, не являющейся случайной, рано или поздно можно найти конечную подпоследовательность, такую что колмогоровская сложность задания ее прямым перечислением превысит сложность исходного правила генерации. По-простому и не совсем математично: фразу "последовательность, состоящая только из единиц" с какого-то момента можно произнести быстрее, чем просто перечислять "один, один, один...".
И тут мы подходим к так называемой индукции Соломонова. Этот метод призван выявлять алгоритмы (в нашем случае задания бесконечных последовательностей), которые достигают своей цели с наибольшей вероятностью наиболее просто.
Помните бритву Оккама? Это суждение, которое утверждает, что нужно выбирать самый простой вариант решения. Так вот это она и есть, только математически формализованная.
В случае индукции Соломонова сложность наиболее часто принимается за длину машины Тьюринга, описывающей данный алгоритм. Это делается так, потому что сама индукция Соломонова невычислима и для расчета сложности необходимо потратить бесконечное время.
Для того, чтобы дальнейшие рассуждения были более понятны, возьмем конкретный пример:
Итак, у нас есть бесконечное число алгоритмов, генерирующих все существующие последовательности.
Берем первое число (7) и отсеиваем из всех алгоритмов те, которые не производят 7 в качестве первого члена. Алгоритмов осталось по-прежнему бесконечное число. Дальше мы упорядочиваем эти алгоритмы по возрастанию колмогоровской сложности. На первом месте оказывается самый простой из всех (но, скорей всего, не подходящий нам).
Потом из всех оставшихся алгоритмов отсеиваем те, которые не производят на втором месте (15). И упорядочиваем. И повторяем все снова. Когда мы доберемся до числа (63) и упорядочим все вновь, то мы получим алгоритм, задающий нужную нам последовательность наиболее простым способом. Он будет стоять на первом месте.
Осталась одна проблема: время поиска все еще бесконечно. То есть к реальной жизни это все еще не применимо. Над этой задачей бьются математики из разных областей: искусственный интеллект, теория информации и многих других. Написано множество статей, но, как понимаете, реальный искусственный интеллект пока не создали.
Вот так тупая школьная задача не имеет строгого решения, но ее как-то все решают и есть даже те, кто решил правильно или неправильно. По-хорошему решением этой задачи будет указание нескольких чисел и описание последовательности. В этом случае решение не будет внутренне противоречиво.
И напоследок вот вам анекдот в тему.
При дворе персидского шаха один мудрец придумал игру под названием шахматы. И так эта игра понравилась шаху, что играл он в нее целыми днями и все наиграться не мог. Однажды шах позвал мудреца и говорит ему: - Проси, мудрец, у меня что хочешь – всё тебе дам! Уж больно игра твоя хороша! - О Великий шах, - отвечает мудрец, - Если я попрошу, то попрошу немало, не сможете вы мне этого дать. - Как смеешь ты так думать?! – рассердился шах, - Проси сейчас же и увидишь! - Ваше величество, видите эту шахматную доску? На ней шестьдесят четыре поля. Дайте мне за первое поле 1 зернышко риса, за второе поле – 2 зерна, за третье – 4 зерна, за четвертое - 8 зерен, за пятое – 16 зерен, за шестое – 32 зерен и так далее, до последнего поля. - Ха! - воскликнул шах, - Да мудрец ли ты? Я думал, ты попросишь горы золота и мешки алмазов, а ты ведешь речь о нескольких тысячах зёрен. Ты сумасшедший, но как хочешь! Вошли слуги и стали выкладывать зерна… Одно, два, четыре, восемь, шестнадцать, тридцать два, хотели уже и шестьдесят четыре ставить, но шах их остановил: — Мудрец думает, что он слишком хитроумный, геометрической прогрессией развести меня хотел? Раз он сказал буквально "за шестое – 32 зерен и так далее", то и на седьмую и на все остальные клетки положите по 32 зерна, я уже посчитал, как раз чуть больше 2 тысяч зерен получится. Этим шахом был Ходжа Насреддин.
И напоследок вот вам анекдот в тему.
При дворе персидского шаха один мудрец придумал игру под названием шахматы. И так эта игра понравилась шаху, что играл он в нее целыми днями и все наиграться не мог. Однажды шах позвал мудреца и говорит ему: - Проси, мудрец, у меня что хочешь – всё тебе дам! Уж больно игра твоя хороша! - О Великий шах, - отвечает мудрец, - Если я попрошу, то попрошу немало, не сможете вы мне этого дать. - Как смеешь ты так думать?! – рассердился шах, - Проси сейчас же и увидишь! - Ваше величество, видите эту шахматную доску? На ней шестьдесят четыре поля. Дайте мне за первое поле 1 зернышко риса, за второе поле – 2 зерна, за третье – 4 зерна, за четвертое - 8 зерен, за пятое – 16 зерен, за шестое – 32 зерен и так далее, до последнего поля. - Ха! - воскликнул шах, - Да мудрец ли ты? Я думал, ты попросишь горы золота и мешки алмазов, а ты ведешь речь о нескольких тысячах зёрен. Ты сумасшедший, но как хочешь! Вошли слуги и стали выкладывать зерна… Одно, два, четыре, восемь, шестнадцать, тридцать два, хотели уже и шестьдесят четыре ставить, но шах их остановил: — Мудрец думает, что он слишком хитроумный, геометрической прогрессией развести меня хотел? Раз он сказал буквально "за шестое – 32 зерен и так далее", то и на седьмую и на все остальные клетки положите по 32 зерна, я уже посчитал, как раз чуть больше 2 тысяч зерен получится. Этим шахом был Ходжа Насреддин.
Комментариев нет:
Отправить комментарий