Обсуждение:Примеры неразрешимых задач: однозначность грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «: {{tick}} как-то сразу прыгаем в решение задачи, надо бы хоть написать, что хотим выполнить m-...»)
 
Строка 1: Строка 1:
−
: {{tick}} как-то сразу прыгаем в решение задачи, надо бы хоть написать, что хотим выполнить m-сведение в начале док-ва, а не в конце. Написать в начале, что доказываем от противного и предполагаем, что такой алгоритм существует.
+
: {{tick|ticked=1}} как-то сразу прыгаем в решение задачи, надо бы хоть написать, что хотим выполнить m-сведение в начале док-ва, а не в конце. Написать в начале, что доказываем от противного и предполагаем, что такой алгоритм существует.
 
: {{tick}} англоязычные термины, ссылки на англоязычные источники
 
: {{tick}} англоязычные термины, ссылки на англоязычные источники
−
: {{tick}} что за символы z_1 .. z_n, произвольные или что? Надо пояснить.
+
:: Ambiguous {{---}} это "'''не'''однозначный". "post correspondence problem" убрать (этот термин должен появиться в конспекте по ПСП). --[[Участник:Sementry|Мейнстер Д.]] 03:06, 15 января 2013 (GST)
−
: {{tick}} по-моему, грамматику можно сделать проще, написать, что S -> A | B
+
: {{tick|ticked=1}} что за символы z_1 .. z_n, произвольные или что? Надо пояснить.
−
: {{tick}} не "пусть есть правила", а, наверное, зададим грамматику такими-то правилами.
+
: {{tick|ticked=1}} по-моему, грамматику можно сделать проще, написать, что S -> A | B
−
: {{tick}}  Поскольку <tex>\forall i, j : i \ne j</tex> <tex>z_{i} \ne z_{j}</tex> — вот это вообще что-то непонятное. В какой последовательности здесь рассматриваются индексы? Если в алфавите, достаточно это написать словами.
+
: {{tick|ticked=1}} не "пусть есть правила", а, наверное, зададим грамматику такими-то правилами.
−
: {{tick}} "Таким образом, мы получили m-сведение множества решений ПСП к множеству решений нашей задачи, так как если существует решение ПСП, то существует такой поднабор индексов, что слово  выводится двумя способами, то есть грамматика неоднозначна" — создается ощущение, что мы получили m-сведение только из за части предложения после "то", и предыдущее отбрасывается. Оформить это как доказательство в прямую и обратную стороны, а потом уже написать, что свели.
+
: {{tick|ticked=1}}  Поскольку <tex>\forall i, j : i \ne j</tex> <tex>z_{i} \ne z_{j}</tex> — вот это вообще что-то непонятное. В какой последовательности здесь рассматриваются индексы? Если в алфавите, достаточно это написать словами.
 +
: {{tick|ticked=1}} "Таким образом, мы получили m-сведение множества решений ПСП к множеству решений нашей задачи, так как если существует решение ПСП, то существует такой поднабор индексов, что слово  выводится двумя способами, то есть грамматика неоднозначна" — создается ощущение, что мы получили m-сведение только из за части предложения после "то", и предыдущее отбрасывается. Оформить это как доказательство в прямую и обратную стороны, а потом уже написать, что свели.
 
--[[Участник:Dgerasimov|Дмитрий Герасимов]] 12:49, 9 декабря 2012 (GST)
 
--[[Участник:Dgerasimov|Дмитрий Герасимов]] 12:49, 9 декабря 2012 (GST)
 +
 +
=== Это еще не все ===
 +
: Не забываем об орфографии, пунктуации и прочих немаловажных вещах:
 +
:: {{tick}} при записи грамматики корректнее использовать <tex> \rightarrow </tex>, а не <tex> \Rightarrow </tex>
 +
:: {{tick}} номера правил{{err|s=1|t=a}}
 +
:: {{tick}} причем{{err|t=,}} если
 +
:: {{tick}} сказать{{err|t=,}} однозначна
 +
:: {{tick}} то {{err|s=1|t=значит}}, {{err|s=1|t=то}} значит или то{{err|t=,}} значит{{err|t=,}}
 +
:: {{tick}} однозначна{{err|t=,}} и не существует {{err|s=1|t=два вывода}}двух выводов
 +
:: {{tick}} "постовской системы соответствия" {{---}} тогда уж "экземпляра ПСП"
 +
: {{tick}} Хорошо бы также разбить громоздкий абзац текста после определения грамматики на более мелкие.
 +
По содержанию претензий нет. --[[Участник:Sementry|Мейнстер Д.]] 03:06, 15 января 2013 (GST)

Версия 02:06, 15 января 2013

☑ как-то сразу прыгаем в решение задачи, надо бы хоть написать, что хотим выполнить m-сведение в начале док-ва, а не в конце. Написать в начале, что доказываем от противного и предполагаем, что такой алгоритм существует.
☐ англоязычные термины, ссылки на англоязычные источники
Ambiguous — это "неоднозначный". "post correspondence problem" убрать (этот термин должен появиться в конспекте по ПСП). --Мейнстер Д. 03:06, 15 января 2013 (GST)
☑ что за символы z_1 .. z_n, произвольные или что? Надо пояснить.
☑ по-моему, грамматику можно сделать проще, написать, что S -> A | B
☑ не "пусть есть правила", а, наверное, зададим грамматику такими-то правилами.
☑ Поскольку [math]\forall i, j : i \ne j[/math] [math]z_{i} \ne z_{j}[/math] — вот это вообще что-то непонятное. В какой последовательности здесь рассматриваются индексы? Если в алфавите, достаточно это написать словами.
☑ "Таким образом, мы получили m-сведение множества решений ПСП к множеству решений нашей задачи, так как если существует решение ПСП, то существует такой поднабор индексов, что слово выводится двумя способами, то есть грамматика неоднозначна" — создается ощущение, что мы получили m-сведение только из за части предложения после "то", и предыдущее отбрасывается. Оформить это как доказательство в прямую и обратную стороны, а потом уже написать, что свели.

--Дмитрий Герасимов 12:49, 9 декабря 2012 (GST)

Это еще не все

Не забываем об орфографии, пунктуации и прочих немаловажных вещах:
☐ при записи грамматики корректнее использовать [math] \rightarrow [/math], а не [math] \Rightarrow [/math]
☐ номера правилa
☐ причем, если
☐ сказать, однозначна
☐ то значит, то значит или то, значит,
☐ однозначна, и не существует два выводадвух выводов
☐ "постовской системы соответствия" — тогда уж "экземпляра ПСП"
☐ Хорошо бы также разбить громоздкий абзац текста после определения грамматики на более мелкие.

По содержанию претензий нет. --Мейнстер Д. 03:06, 15 января 2013 (GST)

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение:Примеры_неразрешимых_задач:_однозначность_грамматики&oldid=29935»