Информационный портал Пируса Е.М. (математика, информатика)

Поиск в каталоге Refer.Ru:
Регистрация или вход Главная | Анкета | Рекомендовать | Обратная связь | В избранное | Сделать домашней
Статистика портала

Рейтинг@Mail.ru

Рейтинг сайтов YandeG
Яндекс цитирования
bigmir)net TOP 100
Модули портала
ГлавнаяГлавная
Галерея Галерея
Интернет РадиоИнтернет Радио
Лучшие статьи Лучшие статьи
НовостиНовости
Обратная связьОбратная связь
ОпросыОпросы
Поиск на порталеПоиск на портале
Порекомендовать Порекомендовать
ФайлыФайлы
ЧаВоЧаВо
Шутки, анекдотыШутки, анекдоты

Решена задача о раскраске дорог
Научные новости
Израильскому математику удалось обосновать гипотезу о раскраске дорог (Road Coloring), имеющую важное значение в теории автоматов.

Гипотеза о раскраске дорог (Road Coloring) была сформулирована в 1970 г. израильскими математиками Адлером и Вейссом в статье "Similarity of automorphisms of the torus". Гипотеза ставит вопрос о возможности синхронизации движения в конечном сильно связном графе с постоянной полустепенью исхода (постоянным числом ребер, исходящих из вершин).

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

Аврааму Трахтману (Avraham Trahtman), бывшему жителю России и выпускнику Уральского государственного университета, а ныне профессору Университета Бар-Илан, удалось найти решение этой задачи. Его работа под названием "The road coloring problem" опубликована на сайте электронной библиотеки Корнельского университета arxiv.org.

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


http://rnd.cnews.ru/math/news/top/index_science.shtml?2008/02/11/287590
Разместил: pirusyatko | Дата: 03.03.2008
[ Напечатать статью | Отправить другу ]
Рейтинг статьи

Средняя оценка: Средняя оценка: 0Всего голосов:0

Отлично
Хорошо Нормально Пойдёт Плохо


User Info


Добро пожаловать,
Guest

Регистрация или входРегистрация или вход
Потеряли пароль?Потеряли пароль?

Логин:
Пароль:

Сейчас онлайн
ПользователейПользователей: 0
ГостейГостей: 7
ВсегоВсего: 7
WebSite-Uptime
uptime
Главная | Статьи | Форум | Темы | Галерея | Вопросы и ответы | Учебники | Рекомендовать | Обратная связь
Спасибо администрации портала. Copyright © 2006-2009