Пятнашки глазами алгоритмиста. Часть 4: ПОЧТИ лирическое отступление
Часть 1: асимптотическая оценка сложности
Часть 2: думаем и улучшаем оценки!
Часть 3: константная оценка точности
Есть общие правила. И есть исключения – их тоже надо знать.
Почему алгоритм не обязательно "плох", если известные точные оценки для него не так уж хороши?
На самом деле, один из трудно формализуемых, но важных вопросов, на который должны уметь отвечать (или хотя бы уметь его задавать) IT-специалисты и прикладники-оптимизаторы.
Мы рассмотрели метод уменьшения размера задачи и выяснили, что есть случаи, когда он сильно сбивается, совершая относительно много лишних ходов.
Но ведь подобные примеры, вероятно, будут встречаться редко? Даже чтоб их построить, пришлось немного подумать.
Можно ли сказать, что алгоритм будет достаточно хорошо строить решение почти всегда?
Тут, кстати, приходит на ум симплекс-метод решения задачи линейного программирования (к которой, по некоторым оценкам, сводится до 20-30% реально возникающих практических задач планирования). Меня не слишком устраивает положение вещей, когда студенты затрудняются ответить, чем этот метод хорош, какова его вычислительная сложность, и почему именно он широко изучается и применяется, в то время как были изобретены значительно лучшие (в асимптотическом смысле!) алгоритмы.
Да и вообще с задачами матпрограммирования... Видимо, у меня профессиональная деформация :) Но, если подбирать аналогии... имхо, например, это как учить вождению транспортных средств: натаскивать владению средствами управления, иногда даже более-менее объяснять сам принцип работы двигателя. И при этом ни слова или почти ни слова не говорить о развиваемой скорости, расходе топлива и факторах, на них влияющих.
Ну, то есть, может быть, если человек не станет непосредственно математиком или программистом, то ему это и не будет необходимо, но всё-таки...
К сожалению, не знаю, существует ли единая наглядная сводная справка по сложности алгоритмов решения распространённых типов задач, встречающихся в стандартных курсах "Методов оптимизации" (по крайней мере, сходу подобных методических материалов я не нашёл, и даже опытные преподаватели курса затруднились подсказать). Как-нибудь, может быть, надо этим заняться, правда, потребует серьёзного копания в литературе...
Прежде чем продолжить рассуждения о способах оценок, надо сделать отступление.
(с) xkcd.ru
Итак,
что означает для математика термин "почти"?
На самом деле, всё просто. "Почти" имеет ту же асимптотическую природу, что и основные обозначения (O-нотация) в теории вычислительной сложности. Нас интересует предельное поведение объекта, когда количество его элементов стремится к бесконечности.
И лучше всего это укладывается в голове на примерах из теории графов.
Вообще, наглядное графическое представление очень помогает при работе с абстрактными формальными объектами.
Недаром, как правило, при знакомстве с высшей математикой одно из первых рассматриваемых средств – диаграмма Эйлера-Венна (https://ru.wikipedia.org/wiki/Диаграмма_Венна), или попросту "круги Эйлера".
К слову, при работе над своей кандидатской тоже довелось чертить диаграммы и рисунки.
И, собственно, глава, посвященная основному результату, полностью излагается на языке гиперграфов, с которыми устанавливается тождественность.
Хотя это абсолютно не обязательно и, чисто формально, излишне. Просто иначе доказательства теорем было бы намного труднее воспринимать и невообразимо сложнее получить!
Вот, кстати, мне почему-то не попадались попытки визуализации непосредственно анализа вычислительной сложности (не считая обычных графиков роста функций). Хотя каждый хороший специалист, анализируя, к примеру, код с вложенными циклами, наверняка у себя в воображении как-то всё равно это представляет через картинки.
Наверное, для способных обучающихся такое разжёвывание не слишком важно, но ведь на потоке-то разные люди! И хорошо бы, чтобы у всех осталось что-то в головах.
У меня есть 2-3 показательных примера, о которых как-нибудь напишу позже, и стоит дальше подумать в этом направлении...
Впрочем, это мы опять отвлеклись.
Рассмотрим несколько очень простых, но красивых и удивительных фактов. Любому специалисту по теории графов они, конечно, известны, а вот входят ли в стандартные вузовские курсы соответствующей дисциплины, не совсем уверен (вероятно, тоже зависит от специальности).
Асимптотические свойства графов
Говорят, что почти все графы обладают некоторым свойством, если
отношение числа графов с n вершинами, имеющих это свойство,
к числу всех графов с n вершинами
стремится к 1
при n, стремящемся к бесконечности.
Соответственно, говорят, что почти нет графов, обладающим некоторым свойством,
если данное отношение стремится к 0.
Граф называется связным, если из любой вершины можно добраться по рёбрам в любую другую. Любой граф разбивается на один или несколько максимальных связных подграфов - компонент связности.
Вопрос: как будет вести себя количество этих компонент при увеличении размера графа (количества его вершин)?
Интуитивно кажется, что оно будет расти. И несвязных графов, соответственно, будет становится всё больше.
Так оно и есть — но только в абсолютном отношении!
А что, если мы возьмём произвольный случайный граф с n вершинами?
Окажется, что типичный случай будет выглядеть не так:
а примерно так:
Теорема. Почти все графы связны.
Доказывается это путём комбинаторных подсчётов. Отношение количества несвязных графов к общему количеству оценивается сверху как (n^2) / (2^(n-2))
Хотя квадратичная функция (частный случай полинома) с увеличением n растёт быстро, экспонента растёт несравненно быстрее!
Заодно заметим, что порядок роста полинома и экспоненты как раз и отличает "легкорешаемые" задачи от "труднорешаемых". Если оптимизатор говорит, что задача "легко" или "эффективно" решается, — скорее всего имеется в виду, что для неё существует полиномиальный алгоритм.
На самом деле, можно доказать и более сильное утверждение.
Двусвязный граф — это связный и неделимый граф (удаление любого ребра не приведёт к потере связности).
Теорема. Почти все графы двусвязны.
От связности перейдём к метрическим характеристикам.
Опять, казалось бы, с ростом количества вершин диаметр графа тоже будет увеличиваться... но сюрприз!
Теорема. Диаметры почти всех графов равны 2.
Теорема. Почти нет графов радиуса 1.
Следствие. Радиусы почти всех графов равны 2.
З.Ы. Вообще, есть много простых в постановке, но содержательных математических задач, и в теории графов их немало.
Например, очень интересно почитать о проблемах теории Рамсея (см. http://www.ega-math.narod.ru/Nquant/Ramsey.htm), начавшейся с задачки о раскраске графа
Неформально в двух словах:
полная неупорядоченность невозможна
но для гарантированного получения "упорядоченных" свойств часто требуются астрономические числа
И, напоследок, пара попавшихся мне недавно на глаза задач с доступной формулировкой и красивым наглядным представлением, к решению которых приложили руки люди, не являвшиеся профессиональными математиками:
1) апрель 2018 г. – доказано, что хроматическое число плоскости не меньше 5 (см. https://habr.com/post/358900/)
2) замощение плоскости пятиугольниками (см. https://ru.wikipedia.org/wiki/Пятиугольный_паркет)
Действительно забавная история: американская домохозяйка МарджСимпсон Райс в течение пары лет четырежды ставила в неудобное положение специалистов, пытавшихся доказать, что теперь-то все возможные замощения получены!
Какое-то время был долгий перерыв в получении новых результатов.
И вот в 2015 году, аж впервые с 1985, был найден новый, 15-й тип плиток!
Правда, учёные на этот раз уже как-то не спешат утверждать, что замощений больше не существует :)
Продолжение
.
Часть 2: думаем и улучшаем оценки!
Часть 3: константная оценка точности
Есть общие правила. И есть исключения – их тоже надо знать.
Почему алгоритм не обязательно "плох", если известные точные оценки для него не так уж хороши?
На самом деле, один из трудно формализуемых, но важных вопросов, на который должны уметь отвечать (или хотя бы уметь его задавать) IT-специалисты и прикладники-оптимизаторы.
Мы рассмотрели метод уменьшения размера задачи и выяснили, что есть случаи, когда он сильно сбивается, совершая относительно много лишних ходов.
Но ведь подобные примеры, вероятно, будут встречаться редко? Даже чтоб их построить, пришлось немного подумать.
Можно ли сказать, что алгоритм будет достаточно хорошо строить решение почти всегда?
Тут, кстати, приходит на ум симплекс-метод решения задачи линейного программирования (к которой, по некоторым оценкам, сводится до 20-30% реально возникающих практических задач планирования). Меня не слишком устраивает положение вещей, когда студенты затрудняются ответить, чем этот метод хорош, какова его вычислительная сложность, и почему именно он широко изучается и применяется, в то время как были изобретены значительно лучшие (в асимптотическом смысле!) алгоритмы.
Да и вообще с задачами матпрограммирования... Видимо, у меня профессиональная деформация :) Но, если подбирать аналогии... имхо, например, это как учить вождению транспортных средств: натаскивать владению средствами управления, иногда даже более-менее объяснять сам принцип работы двигателя. И при этом ни слова или почти ни слова не говорить о развиваемой скорости, расходе топлива и факторах, на них влияющих.
Ну, то есть, может быть, если человек не станет непосредственно математиком или программистом, то ему это и не будет необходимо, но всё-таки...
К сожалению, не знаю, существует ли единая наглядная сводная справка по сложности алгоритмов решения распространённых типов задач, встречающихся в стандартных курсах "Методов оптимизации" (по крайней мере, сходу подобных методических материалов я не нашёл, и даже опытные преподаватели курса затруднились подсказать). Как-нибудь, может быть, надо этим заняться, правда, потребует серьёзного копания в литературе...
Прежде чем продолжить рассуждения о способах оценок, надо сделать отступление.
(с) xkcd.ru
Итак,
что означает для математика термин "почти"?
На самом деле, всё просто. "Почти" имеет ту же асимптотическую природу, что и основные обозначения (O-нотация) в теории вычислительной сложности. Нас интересует предельное поведение объекта, когда количество его элементов стремится к бесконечности.
И лучше всего это укладывается в голове на примерах из теории графов.
Вообще, наглядное графическое представление очень помогает при работе с абстрактными формальными объектами.
Недаром, как правило, при знакомстве с высшей математикой одно из первых рассматриваемых средств – диаграмма Эйлера-Венна (https://ru.wikipedia.org/wiki/Диаграмма_Венна), или попросту "круги Эйлера".
К слову, при работе над своей кандидатской тоже довелось чертить диаграммы и рисунки.
И, собственно, глава, посвященная основному результату, полностью излагается на языке гиперграфов, с которыми устанавливается тождественность.
Хотя это абсолютно не обязательно и, чисто формально, излишне. Просто иначе доказательства теорем было бы намного труднее воспринимать и невообразимо сложнее получить!
Вот, кстати, мне почему-то не попадались попытки визуализации непосредственно анализа вычислительной сложности (не считая обычных графиков роста функций). Хотя каждый хороший специалист, анализируя, к примеру, код с вложенными циклами, наверняка у себя в воображении как-то всё равно это представляет через картинки.
Наверное, для способных обучающихся такое разжёвывание не слишком важно, но ведь на потоке-то разные люди! И хорошо бы, чтобы у всех осталось что-то в головах.
У меня есть 2-3 показательных примера, о которых как-нибудь напишу позже, и стоит дальше подумать в этом направлении...
Впрочем, это мы опять отвлеклись.
Рассмотрим несколько очень простых, но красивых и удивительных фактов. Любому специалисту по теории графов они, конечно, известны, а вот входят ли в стандартные вузовские курсы соответствующей дисциплины, не совсем уверен (вероятно, тоже зависит от специальности).
Асимптотические свойства графов
Говорят, что почти все графы обладают некоторым свойством, если
отношение числа графов с n вершинами, имеющих это свойство,
к числу всех графов с n вершинами
стремится к 1
при n, стремящемся к бесконечности.
Соответственно, говорят, что почти нет графов, обладающим некоторым свойством,
если данное отношение стремится к 0.
Граф называется связным, если из любой вершины можно добраться по рёбрам в любую другую. Любой граф разбивается на один или несколько максимальных связных подграфов - компонент связности.
Вопрос: как будет вести себя количество этих компонент при увеличении размера графа (количества его вершин)?
Интуитивно кажется, что оно будет расти. И несвязных графов, соответственно, будет становится всё больше.
Так оно и есть — но только в абсолютном отношении!
А что, если мы возьмём произвольный случайный граф с n вершинами?
Окажется, что типичный случай будет выглядеть не так:
а примерно так:
Теорема. Почти все графы связны.
Доказывается это путём комбинаторных подсчётов. Отношение количества несвязных графов к общему количеству оценивается сверху как (n^2) / (2^(n-2))
Хотя квадратичная функция (частный случай полинома) с увеличением n растёт быстро, экспонента растёт несравненно быстрее!
Заодно заметим, что порядок роста полинома и экспоненты как раз и отличает "легкорешаемые" задачи от "труднорешаемых". Если оптимизатор говорит, что задача "легко" или "эффективно" решается, — скорее всего имеется в виду, что для неё существует полиномиальный алгоритм.
На самом деле, можно доказать и более сильное утверждение.
Двусвязный граф — это связный и неделимый граф (удаление любого ребра не приведёт к потере связности).
Теорема. Почти все графы двусвязны.
От связности перейдём к метрическим характеристикам.
Опять, казалось бы, с ростом количества вершин диаметр графа тоже будет увеличиваться... но сюрприз!
Теорема. Диаметры почти всех графов равны 2.
Теорема. Почти нет графов радиуса 1.
Следствие. Радиусы почти всех графов равны 2.
З.Ы. Вообще, есть много простых в постановке, но содержательных математических задач, и в теории графов их немало.
Например, очень интересно почитать о проблемах теории Рамсея (см. http://www.ega-math.narod.ru/Nquant/Ramsey.htm), начавшейся с задачки о раскраске графа
Неформально в двух словах:
полная неупорядоченность невозможна
но для гарантированного получения "упорядоченных" свойств часто требуются астрономические числа
И, напоследок, пара попавшихся мне недавно на глаза задач с доступной формулировкой и красивым наглядным представлением, к решению которых приложили руки люди, не являвшиеся профессиональными математиками:
1) апрель 2018 г. – доказано, что хроматическое число плоскости не меньше 5 (см. https://habr.com/post/358900/)
2) замощение плоскости пятиугольниками (см. https://ru.wikipedia.org/wiki/Пятиугольный_паркет)
Действительно забавная история: американская домохозяйка Мардж
Какое-то время был долгий перерыв в получении новых результатов.
И вот в 2015 году, аж впервые с 1985, был найден новый, 15-й тип плиток!
Правда, учёные на этот раз уже как-то не спешат утверждать, что замощений больше не существует :)
Продолжение
.