Обсуждение:Вероятностные вычисления. Вероятностная машина Тьюринга — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показаны 4 промежуточные версии 3 участников)
Строка 1: Строка 1:
 
Претензии по сути:
 
Претензии по сути:
 +
 
1) вступление; я его не очень поняла; что значит, что "программы получают доступ к генератору случайных чисел" и зачем это надо?
 
1) вступление; я его не очень поняла; что значит, что "программы получают доступ к генератору случайных чисел" и зачем это надо?
  
Строка 5: Строка 6:
  
 
3) Доказательство этой теоремы. Почему <tex>R_i</tex> дизъюнктны?
 
3) Доказательство этой теоремы. Почему <tex>R_i</tex> дизъюнктны?
 +
  
 
По оформлению: вот опять же лично мне не нравится такой псевдокод, как-то непривычно после if видеть двоеточие.
 
По оформлению: вот опять же лично мне не нравится такой псевдокод, как-то непривычно после if видеть двоеточие.
 +
 +
 +
Сейчас в первой теореме имеются более существенные проблемы, связанные с некорректным введением <tex>\Sigma</tex>.--[[Участник:Igor buzhinsky|Игорь Бужинский]] 21:41, 1 июня 2012 (GST)
 +
 +
1) Фразу следует понимать буквально. Это нужно, чтобы сформулировать введение, не прибегая к пока не введенным терминам. Можно перефразировать.
 +
 +
2, 3) Формулировку и доказательство поправил. Я добавил еще одно предложение про <tex>\Sigma</tex> перед теоремой, правда, у меня нет источника, подтверждающего правильность сделанного. Без этого предложения было бы необоснованным говорить, что что-то нетривиальное вообще принадлежит <tex>\Sigma</tex>.--[[Участник:Igor buzhinsky|Игорь Бужинский]] 18:39, 2 июня 2012 (GST)
 +
 +
Программы, удовлетворяющие ограничениям <tex>\mathrm{ZPP}</tex>, могут ошибаться. То же относится к <tex>\mathrm{RP}</tex> в случае <tex>x \not \in L</tex>.
 +
 +
Что за сложностный класс <tex>\Sigma^*</tex>? Для класса, содержащего все языки, лучше подойдёт какой-нибудь <tex>U</tex>. Или можно словами расписать, что содержит все языки. Или <tex>2^{\Sigma^*}</tex>, в конце концов.
 +
 +
[[Участник:Shevchen|Дмитрий Шевченко]] 23:00, 4 июня 2012 (GST)

Текущая версия на 22:05, 4 июня 2012

Претензии по сути:

1) вступление; я его не очень поняла; что значит, что "программы получают доступ к генератору случайных чисел" и зачем это надо?

2) Первая теорема. Ее формулировка лично не мне очень понятна. Должно быть что-то вроде "Для любых х и А R будет измеримо", так? А двоеточие читается как "таких, что".

3) Доказательство этой теоремы. Почему [math]R_i[/math] дизъюнктны?


По оформлению: вот опять же лично мне не нравится такой псевдокод, как-то непривычно после if видеть двоеточие.


Сейчас в первой теореме имеются более существенные проблемы, связанные с некорректным введением [math]\Sigma[/math].--Игорь Бужинский 21:41, 1 июня 2012 (GST)

1) Фразу следует понимать буквально. Это нужно, чтобы сформулировать введение, не прибегая к пока не введенным терминам. Можно перефразировать.

2, 3) Формулировку и доказательство поправил. Я добавил еще одно предложение про [math]\Sigma[/math] перед теоремой, правда, у меня нет источника, подтверждающего правильность сделанного. Без этого предложения было бы необоснованным говорить, что что-то нетривиальное вообще принадлежит [math]\Sigma[/math].--Игорь Бужинский 18:39, 2 июня 2012 (GST)

Программы, удовлетворяющие ограничениям [math]\mathrm{ZPP}[/math], могут ошибаться. То же относится к [math]\mathrm{RP}[/math] в случае [math]x \not \in L[/math].

Что за сложностный класс [math]\Sigma^*[/math]? Для класса, содержащего все языки, лучше подойдёт какой-нибудь [math]U[/math]. Или можно словами расписать, что содержит все языки. Или [math]2^{\Sigma^*}[/math], в конце концов.

Дмитрий Шевченко 23:00, 4 июня 2012 (GST)