Обсуждение:Сложностные классы. Вычисления с оракулом — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Я не понял, ЭТО зачтено или нет?)
 
(не показаны 4 промежуточные версии 2 участников)
Строка 16: Строка 16:
  
 
: Действительно, стало заметно лучше ;). Но в первом определении всё ещё написан бред. «ограничение» — какое ещё ограничение? T — это просто ''время работы'' программы. С памятью аналогично. TS — вообще из другой оперы, поскольку это не число (время работы или объем памяти), а, как я понимаю из последующего использования, класс задач. И аргументы у него не программа и слово, а две функции. Ну и так дальше в том же духе… [[Участник:Kirelagin|Кирилл Елагин]] 22:51, 2 июня 2012 (GST)
 
: Действительно, стало заметно лучше ;). Но в первом определении всё ещё написан бред. «ограничение» — какое ещё ограничение? T — это просто ''время работы'' программы. С памятью аналогично. TS — вообще из другой оперы, поскольку это не число (время работы или объем памяти), а, как я понимаю из последующего использования, класс задач. И аргументы у него не программа и слово, а две функции. Ну и так дальше в том же духе… [[Участник:Kirelagin|Кирилл Елагин]] 22:51, 2 июня 2012 (GST)
 +
: И вообще в TS надо еще написать пояснение про space-time tradeoff. [[Участник:Kirelagin|Кирилл Елагин]] 22:53, 2 июня 2012 (GST)
 +
:: Нина зачем-то проигнорировала примерно половину комментария. Я, наверное, слишком длинно написал… [[Участник:Kirelagin|Кирилл Елагин]] 13:46, 3 июня 2012 (GST)
 +
:::Кирилл, где ты взял space-time tradeoff? Я у Станка этого совсем не помню...
 +
:::: Я зато помню. Это было пояснение, почему TS(f,g) != DTIME(f) ∩ DSPACE(g). Собственно, надо нормально написать определение TS (желательно, наверное, с большой фигурной скобочкой), причем ''после'' DTIME и DSPACE. А потом нужно пояснить, почему, собственно, не равно пересечению. Если не помнишь, почему, спроси у Никиты — он точно помнит, поскольку больше всех возмущался по этому поводу. [[Участник:Kirelagin|Кирилл Елагин]] 23:12, 3 июня 2012 (GST)
 +
 +
Раз уж мы работаем со строками на лентах, вместо «мощность x» лучше писать «длина x».
 +
 +
В определении оракула два объекта обозначены одной буквой A.
 +
 +
[[Участник:Shevchen|Дмитрий Шевченко]] 16:47, 4 июня 2012 (GST)

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

ЭТО КАПЕЦ Кирилл Елагин 01:54, 24 апреля 2012 (GST)

Мда. Не могу не согласиться с предыдущим оратором. Претензии по содержанию

  • Мы, помнится, вводили определения не через МТ, а через программы. Напиши их именно так, пожалуйста. А если уж пишешь МТ, уточняй детерминизм оной в определении, а не в конце статьи.
  • А что такое оракул?

Претензии по оформлению.

  • Используй, пожалуйста, нормальные шаблоны.
  • Исправь минусы на тире.
  • Если объединение по чему-то, то это что-то пишется строго под знаком объединения.
  • Пропущенные запятые - это так, мелочи.

Я не понял, ЭТО зачтено или нет?

Если что, я остался при своём мнении, изложенном в первой строчке данного обсуждения. Кирилл Елагин 22:14, 31 мая 2012 (GST)

Действительно, стало заметно лучше ;). Но в первом определении всё ещё написан бред. «ограничение» — какое ещё ограничение? T — это просто время работы программы. С памятью аналогично. TS — вообще из другой оперы, поскольку это не число (время работы или объем памяти), а, как я понимаю из последующего использования, класс задач. И аргументы у него не программа и слово, а две функции. Ну и так дальше в том же духе… Кирилл Елагин 22:51, 2 июня 2012 (GST)
И вообще в TS надо еще написать пояснение про space-time tradeoff. Кирилл Елагин 22:53, 2 июня 2012 (GST)
Нина зачем-то проигнорировала примерно половину комментария. Я, наверное, слишком длинно написал… Кирилл Елагин 13:46, 3 июня 2012 (GST)
Кирилл, где ты взял space-time tradeoff? Я у Станка этого совсем не помню...
Я зато помню. Это было пояснение, почему TS(f,g) != DTIME(f) ∩ DSPACE(g). Собственно, надо нормально написать определение TS (желательно, наверное, с большой фигурной скобочкой), причем после DTIME и DSPACE. А потом нужно пояснить, почему, собственно, не равно пересечению. Если не помнишь, почему, спроси у Никиты — он точно помнит, поскольку больше всех возмущался по этому поводу. Кирилл Елагин 23:12, 3 июня 2012 (GST)

Раз уж мы работаем со строками на лентах, вместо «мощность x» лучше писать «длина x».

В определении оракула два объекта обозначены одной буквой A.

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение:Сложностные_классы._Вычисления_с_оракулом&oldid=23685»