НГУ

Форумы НГУ
Текущее время: Пн дек 11, 2017 10:49 am

Часовой пояс: UTC + 7 часов




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 46 ]  На страницу 1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Пт фев 17, 2012 10:28 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
У меня есть несколько вопросов по этим машинам. Просьба специалистам по возможности высказаться.

Первый вопрос: есть известная теорема Агравала-Каяла-Саксены, которая говорит, что множество простых чисел полиномиально вычислимо. Спрашивается, что это означает? Если мы излагаем теорию алгоритмов на основе машин Тьюринга, это означает следующее. На ленту машины выкладывается число , записанное в максимально короткой форме. Такая запись занимает символов. Затем запускается алгоритм, который за шагов, где - длина входа, определяет, является ли простым.

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

Вопрос 1: если мы излагаем теорию алгоритмов на основе машин Шёнфилда, как мы можем сформулировать эту теорему? Ведь у нас нет ленты, значит, нет понятия "длина входа". Регистры машины Шёнфилда безразмерны и могут содержать в себе любое число.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Сб фев 18, 2012 3:42 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Pavel E. Alaev писал(а):
На ленту машины выкладывается число , записанное в максимально короткой форме.


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

Pavel E. Alaev писал(а):
В итоге мы получаем алгоритм, который за шагов определяет простоту числа .

Если мне не изменяет память, .

Pavel E. Alaev писал(а):
Вопрос 1: если мы излагаем теорию алгоритмов на основе машин Шёнфилда, как мы можем сформулировать эту теорему?

А никак не можем!!!

Машина Тьюринга - достаточно адекватная модель реальных вычислительных устройств в плане сложности вычислений. Машина Шёнфилда, увы, всего лишь вычисляет за конечное время то, что вычислимо за конечное время на МТ. Для изложения теории сложности она не годится.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Пн фев 20, 2012 1:21 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Коба писал(а):
А никак не можем!!!

По-видимому, действительно так. Мы могли бы ввести длину входа аксиоматически: например, если при запуске МШ в некоторых ячейках находятся ненулевые числа , то длиной входа можно было бы считать . Но в этом случае, например, задача распознавания равенства двух чисел x и y станет экспоненциально сложной: если в двух регистрах МШ лежат x и y, то легко показать, что меньше чем за \min(x,y) шагов вопрос об их равенстве точно не решить.

На одноленточной МТ эта задача решается за квадратичное время, а на двухленточной - за линейное.

Тогда у меня вопрос к В.П.: Вы, кажется, по работе располагаетесь поближе к сложности вычислений: понятию "число шагов работы алгоритма" у вас какое точное определение даётся?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн фев 20, 2012 6:56 pm 
Не в сети
Плодовитый автор

Зарегистрирован: Сб мар 18, 2006 10:52 pm
Сообщения: 742
Откуда: Алексей Салмин
эх, а даже я не знал, что есть такая теорема. чему учился столько лет :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Пн фев 20, 2012 8:32 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт окт 01, 2004 6:27 pm
Сообщения: 1869
Pavel E. Alaev писал(а):
Тогда у меня вопрос к В.П.: Вы, кажется, по работе располагаетесь поближе к сложности вычислений: понятию "число шагов работы алгоритма" у вас какое точное определение даётся?

Бывают разные модели вычислений. Как правило в модели формально определяется сложность вычислений, а понятие по смыслу подобное "числу шагов работы алгоритма" есть не всегда. Приведу два примера, когда подобное понятие есть.
1. Ветвящиеся программы (BDD http://en.wikipedia.org/wiki/Binary_decision_diagram ). Это такой ориентированный граф без циклов со степенью исхода 2, каждая внутренняя вершина дерева помечена некоторой переменной. Граф имеет начальную вершину и две конечные 0 и 1. Если переменная равна 0 идём в левого сына, 1 - в правого. Если значение булевой функции 0, то должны попасть в конечную вершину 0. Здесь "числу шагов работы алгоритма" соответствует глубина схемы - число вершин в самом длинном ориентированном пути. Аналогично определятся глубина в разных схемах из функциональных элементах, контактно-вентильных схемах и т.д.
2.Клеточные автоматы http://en.wikipedia.org/wiki/Cellular_automaton
Это такой ориентированный граф, в каждой вершине которого помещена функция, переменными которой служат значения в соседних вершинах. За один такт одновременно пересчитываются значения во всех вершинах. "Число шагов работы алгоритма" - это, конечно, число тактов. Аналогично определяется число шагов алгоритма для разных специализированных конечных автоматов ( игра "жизнь", дискретная генная сеть).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Пн фев 20, 2012 9:17 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
В.П. писал(а):
Бывают разные модели вычислений. ...

Я, может быть, имел в виду не столько Вашу узкую специальность, сколько дискретную математику в целом. Попробую переформулировать: пусть мы произносим фразу "число компонент связности конечного неориентированного графа может быть определено за полиномиальное число шагов".

Верно ли, что любые два сотрудника ИМ, вообще как-то связанные с конечными графами и алгоритмами, понимают её смысл одинаково? Или у нас есть разные модели вычислений, и один сотрудник может считать, что фраза верна, а другой - что неверна?

P.S. Что-то старая гвардия на форум подтянулась! То IVM выплыл из глубины веков, то вот salmin...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Пн фев 20, 2012 10:15 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт окт 01, 2004 6:27 pm
Сообщения: 1869
Pavel E. Alaev писал(а):
В.П. писал(а):
Бывают разные модели вычислений. ...

Я, может быть, имел в виду не столько Вашу узкую специальность, сколько дискретную математику в целом.

Сложность вычислений точно не моя узкая специальность.
Pavel E. Alaev писал(а):
Верно ли, что любые два сотрудника ИМ, вообще как-то связанные с конечными графами и алгоритмами, понимают её смысл одинаково? Или у нас есть разные модели вычислений, и один сотрудник может считать, что фраза верна, а другой - что неверна?

Если определено в каком виде задан граф (длина входа), то "сложность вычисления" в крупном масштабе (линейная, полиномиальная, NP и т.д.) понимается однозначно. Так как все "разумные" вычислительные преобразования в данном масштабе имеют вполне определённую сложность.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Вт фев 21, 2012 11:33 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Pavel E. Alaev писал(а):
...задача распознавания равенства двух чисел x и y станет экспоненциально сложной: если в двух регистрах МШ лежат x и y, то легко показать, что меньше чем за \min(x,y) шагов вопрос об их равенстве точно не решить.

На одноленточной МТ эта задача решается за квадратичное время, а на двухленточной - за линейное.

С другой стороны прибавление единицы на МШ происходит мгновенно, а на МТ на это требуется хотя бы и линейное, но всё же время...

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Вт фев 21, 2012 2:11 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
В.П. писал(а):
Если определено в каком виде задан граф (длина входа), то "сложность вычисления" в крупном масштабе (линейная, полиномиальная, NP и т.д.) понимается однозначно.

С графом в смысле входа картина довольно ясная: если число вершин равно N, он задаётся матрицей NxN из 0 и 1, и длину входа можно по умолчанию считать равной N^2 с точностью до константы.

Но чтобы достичь такого тотального единомыслия, нужны ведь какие-то определения? У меня вопрос, в чём они состоят. Как на практике определяется число шагов алгоритма, хотя бы примерно?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Вт фев 21, 2012 4:33 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт окт 01, 2004 6:27 pm
Сообщения: 1869
Pavel E. Alaev писал(а):
Но чтобы достичь такого тотального единомыслия, нужны ведь какие-то определения? У меня вопрос, в чём они состоят. Как на практике определяется число шагов алгоритма, хотя бы примерно?

Обычно алгоритм состоит из известных операций: арифметические, полный перебор, сортировка, какие-то задачи класса NP (поиск клики, гамильтонова цикла и т.д.). Для каждой операции верхняя оценка числа операций известна, остаётся правильно оценить параметры операций.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Вт фев 21, 2012 8:33 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
В.П. писал(а):
Обычно алгоритм состоит из известных операций: арифметические, полный перебор, сортировка ... Для каждой операции верхняя оценка числа операций известна ...

На практике этого, наверное, достаточно. Но странно, что нет общепринятого стандартного определения. Не Моисей же сообщил человечеству эти оценки.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Вт фев 21, 2012 8:46 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт окт 01, 2004 6:27 pm
Сообщения: 1869
Pavel E. Alaev писал(а):
В.П. писал(а):
Обычно алгоритм состоит из известных операций: арифметические, полный перебор, сортировка ... Для каждой операции верхняя оценка числа операций известна ...

На практике этого, наверное, достаточно. Но странно, что нет общепринятого стандартного определения. Не Моисей же сообщил человечеству эти оценки.

Нет ну я полагал, что в конечном счёте оценки сводятся к вычислениям на Машине Тьюринга. Формальное определение класса NP обращается именно к ней.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Ср фев 22, 2012 8:57 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
В.П. писал(а):
Нет ну я полагал, что в конечном счёте оценки сводятся к вычислениям на Машине Тьюринга. Формальное определение класса NP обращается именно к ней.

Ага, я тоже всегда так полагал. И вроде в книге Пападимитроу написано то же самое. Моисей = Алан Тьюринг :)

Причём если берём время вычислений с точностью до полинома, то неважно, сколько у МТ лент и т. п. Все достаточно распространённые в литературе конфигурации МТ полиномиально сводятся друг к другу.

P. S. Кстати, есть такая теорема: язык является регулярным (распознаётся конечным автоматом) тогда и только тогда, когда он распознаётся на недетерминированной МТ за линейное время. Вот про это я слышал лишь краем уха, хотелось бы где-нибудь прочитать подробнее.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Ср фев 22, 2012 1:39 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Сб мар 15, 2003 1:40 am
Сообщения: 163
Коба писал(а):
А никак не можем!!!


Как то даже обидно за машины...

Pavel E. Alaev писал(а):
По-видимому, действительно так. Мы могли бы ввести длину входа аксиоматически: например, если при запуске МШ в некоторых ячейках находятся ненулевые числа , то длиной входа можно было бы считать .


Эти логарифмы называются логарифмическим весовым критерием для определения сложности вычисления операций на машинах Шенфилда, с произвольным доступом к памяти (RAM), и т.п. Противовес - равномерный весовой критерий, где от размера числа сложность выполнения операции не зависит.

Вот типичные утверждения из "метрической" теории алгоритмов, которой Коба отказалв существовании :):


Цитата:
Для любой k-ленточной машины Тьюринга M существует такая моделирующая ее машина с произ.дост. к памяти R, что при равномерном весовом критерии и при логарифмическом весовом критерии.


Цитата:
При логарифмическом весовом критерии для любой РАМ R существует моделирующая ее пятиленточная машина Тьюринга M такая, что . При равномерном полиномиально невозможно.


Последний раз редактировалось guest Ср фев 22, 2012 2:01 pm, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Машины Тьюринга и Шёнфилда
СообщениеДобавлено: Ср фев 22, 2012 1:50 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Сб мар 15, 2003 1:40 am
Сообщения: 163
В.П. писал(а):
Нет ну я полагал, что в конечном счёте оценки сводятся к вычислениям на Машине Тьюринга. Формальное определение класса NP обращается именно к ней.


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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 46 ]  На страницу 1, 2, 3, 4  След.

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: Google [Bot], RoberttInaks, Samueliks и гости: 10


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB