powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
8 сообщений из 8, страница 1 из 1
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
    #39708552
Мудроглюков
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
..., и другие задачи.

Так алгоритм Магу "сделал" теоретическую сложность этих задач ниже экспоненциальной?

? Или-таки стали вникать в суть и пошло-поехало:
кроме P и NP
P — полиномиальное время (наиболее часто используется в вычислениях, поскольку задачи этого класса могут быть решены за реальное время)
NP — для задач этого класса неизвестны эффективные алгоритмы решения, поэтому рассматриваются алгоритмы проверки правильности решений (полный перебор вариантов)

обязательно надо уточнять (, чтобы всё не выглядело ерундой)

PSPACE — полиномиальные затраты памяти
EXP — экспоненциальная временная сложность
ESPACE — экспоненциальные затраты памяти
...

Ведь оптимальное раскрытие-сокращение длиннющих многопеременных булевых выражений требует огромной памяти. И т.д. и т.п.

__________________________
__________________________
PS Что есть "алгоритм Магу" -
http://sci.sernam.ru/book_comb.php?id=31
...
...
Рейтинг: 0 / 0
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
    #39710296
Мудроглюков
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ведь наверно любой средний программист (и алгоритмист) легко
переведет экспоненциальный рост времени в экспоненциальный рост памяти, "сделав" при этом рост времени вообще линейным

а есть еще массивные параллельные вычисления, где дополнительные параллельные блоки могут подключаться
по мере надобности,
а есть еще аналоговые вычислительные подмодули,
а есть еще ...

и еще что-то обязательно появится
...
Рейтинг: 0 / 0
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
    #39763224
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мудроглюковведь наверно любой средний программист (и алгоритмист) легко
переведет экспоненциальный рост времени в экспоненциальный рост памяти, "сделав" при этом рост времени вообще линейным

а есть еще массивные параллельные вычисления, где дополнительные параллельные блоки могут подключаться
по мере надобности,
а есть еще аналоговые вычислительные подмодули,
а есть еще ...

и еще что-то обязательно появитсязаполнение экспоненциальной памяти само по себе провоцирует экспоненциальный рост времени на это дело, если конечно она не заполнена до этого
...
Рейтинг: 0 / 0
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
    #39763328
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хм. Забавно. Новость от 2018 года. https://nplus1.ru/news/2018/04/10/chromatic-number

Уже 4 красок мало?
...
Рейтинг: 0 / 0
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
    #39763370
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonХм. Забавно. Новость от 2018 года. https://nplus1.ru/news/2018/04/10/chromatic-number

Уже 4 красок мало?В данной работе работает шестиугольник, к которому пристыкован шестиугольник.
Во всех вершинах (кроме крайних ?) сходятся 3 грани.
6+6=12.

Есть ещё один вариант.
8+4=12.

Восьмиугольник и четырехугольник.
Во всех вершинах сходятся 3 грани.

Здесь появляется интересная задачка:
найти ещё картинки (или графы), повторяющиеся из одних и тех же сторон (или группы сторон) между гранями, где в вершине картинки только 3 грани.
...
Рейтинг: 0 / 0
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
    #39763381
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Например, ещё:

в сотах или в шестиугольниках, как в статье, вместо вершины будет треугольник.

Получаем 12-угольник и треугольник.

А далее, 24 и 3, 48 и 3 и т.д.
...
Рейтинг: 0 / 0
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
    #39763384
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Ошибся:

12, 6 и 3
24, 12, 6 и 3
48, 24, 12, 6 и 3
и т.д.
...
Рейтинг: 0 / 0
Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
    #39763420
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Был в форумах такой Рэт-Крысопыт. Многим он запомнился хроническим депрессивным настроением
и жалобами на неудачи. Читатели ПТ вкурсе.

Но кроме этого он решал задачу изоморфизма графов на сях. И на тот момент лучше чем аналоги
и интернетах. Исходник он мне передавал но я к сожалению его прое.. не сохранил вобщем.
...
Рейтинг: 0 / 0
8 сообщений из 8, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]