Обсуждение:Класс P — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(todo)
 
 
(не показано 7 промежуточных версий 2 участников)
Строка 2: Строка 2:
 
* Смысловая фигня:
 
* Смысловая фигня:
 
** То, что вверху написано — это, насколько я понимаю, определение. Его надо перенести вниз, чтобы оно было после оглавления. Ещё там написана какая-то чушь. Что такое <tex>i</tex> в двойном определении, что такое вообще <tex>in</tex>?
 
** То, что вверху написано — это, насколько я понимаю, определение. Его надо перенести вниз, чтобы оно было после оглавления. Ещё там написана какая-то чушь. Что такое <tex>i</tex> в двойном определении, что такое вообще <tex>in</tex>?
 +
*** Перенёс и поправил само определение. Лида написала там <tex>in</tex> когда-то, идейно это тоже верно, как мне кажется. Но теперь я уже занёс то определение, которое нам давал А.С.
 
** Определения надо НОРМАЛЬНО оформить. Как и для теорем, для них есть собственный шаблон.
 
** Определения надо НОРМАЛЬНО оформить. Как и для теорем, для них есть собственный шаблон.
 +
*** Оформил.
 
** Ссылка на определение DTIME.
 
** Ссылка на определение DTIME.
 +
*** Очень долго думал, как её туда запилить... Так и не смог ничего разумного придумать. Нужен совет.
 +
**** Я добавил ссылку. Не самый хороший костыль, конечно. Я ещё подумаю над этим.
 
** Что за <tex>L1</tex>. Проиндексируй нормально. А ещё там во второй строчке текст абсолютно сливается. Исправь.
 
** Что за <tex>L1</tex>. Проиндексируй нормально. А ещё там во второй строчке текст абсолютно сливается. Исправь.
 +
*** Проиндексировал. А во второй строчке у меня всё в порядке... Либо я не понял, о чём ты.
 +
**** Да, там всё теперь норм.
 
** Было бы неплохо написать хоть какие-нибудь идеи по поводу доказатеств свойств.
 
** Было бы неплохо написать хоть какие-нибудь идеи по поводу доказатеств свойств.
 +
*** Свойство 1 кажется мне очевидным (если мы знаем тот факт, что сумма и произведение полиномов есть полином). Свойства 2 и 3 доказаны по ссылкам на соответствующие сведения (там есть конкретно рассмотрение этих сведений для задач из класса <tex>P</tex>).
 +
**** Мне свойство 1 очевидным не кажется. Особенно какое-нибудь замыкание Клини. Но это несложные факты, поэтому я не прошу полное доказательство.
 +
***** Написал довольно строгое доказательство замкнутости замыкания Клини. Остальные очень простые, смысла их расписывать не вижу.
 
** Ссылка на определение констекстно-свободных языков в формулировке соответствующей теоремы.
 
** Ссылка на определение констекстно-свободных языков в формулировке соответствующей теоремы.
 +
*** Сделал. Заодно и на регулярные языки тоже сделал ссылку.
 
** «Легко показать, что, по определению…» → «Легко показать, что, по определению <tex>P</tex>…»
 
** «Легко показать, что, по определению…» → «Легко показать, что, по определению <tex>P</tex>…»
* Смысловая фигня:
+
*** Ок. Сделал.
 +
* Остальная фигня:
 
** В первом определении после «то есть» двоеточие.
 
** В первом определении после «то есть» двоеточие.
 +
*** Хорошо, сделал.
 
** «Но, по теореме…» Запятая здесь не нужна. Мне кажется, лучше просто выпилить это «но».
 
** «Но, по теореме…» Запятая здесь не нужна. Мне кажется, лучше просто выпилить это «но».
 +
*** Согласен, сделал.
 +
 +
== TODO 2 ==
 +
* В перечислениях в конце каждого пункта ставится либо точка (если пункт — отдельное предложение), либо точка с запятой (если все пункты — это одно баааальшое предложение). Это я про интерпретацию определния <tex>P</tex>.
 +
** Fixed.
 +
* У доказательства замкнутости относительно замыкания Клини проблемы с форматированием: начало имеет отступ в «2 таба», а конец — вообще не имеет отступа. Думаю, что лучше это доказательство выделить в отделиную лемму и оформить соответствующе.
 +
** Done.
 +
* Будем считать, что мы научились ставить ссылки для текста в техе («примечаниями»). Поэтому в предпоследнем абзаце <tex>NP</tex> можно тоже написать нормально в техе.
 +
** Fixed.
 +
* Вставь ссылки на МТ и НМТ. МТ у нас в вики нет, так что эта ссылка — на википедию. Определние НМТ у нас есть.
 +
** Done.
 +
 +
Небольшой комментарий по поводу программ: в первой можно оставить «return p(f(w))»; во второй хочется замены «poses» на «positions».
 +
<s>Grammar nazi</s> [[Участник:Shevchen|Дмитрий Шевченко]] 17:30, 4 июня 2012 (GST)

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

TODO

  • Смысловая фигня:
    • То, что вверху написано — это, насколько я понимаю, определение. Его надо перенести вниз, чтобы оно было после оглавления. Ещё там написана какая-то чушь. Что такое [math]i[/math] в двойном определении, что такое вообще [math]in[/math]?
      • Перенёс и поправил само определение. Лида написала там [math]in[/math] когда-то, идейно это тоже верно, как мне кажется. Но теперь я уже занёс то определение, которое нам давал А.С.
    • Определения надо НОРМАЛЬНО оформить. Как и для теорем, для них есть собственный шаблон.
      • Оформил.
    • Ссылка на определение DTIME.
      • Очень долго думал, как её туда запилить... Так и не смог ничего разумного придумать. Нужен совет.
        • Я добавил ссылку. Не самый хороший костыль, конечно. Я ещё подумаю над этим.
    • Что за [math]L1[/math]. Проиндексируй нормально. А ещё там во второй строчке текст абсолютно сливается. Исправь.
      • Проиндексировал. А во второй строчке у меня всё в порядке... Либо я не понял, о чём ты.
        • Да, там всё теперь норм.
    • Было бы неплохо написать хоть какие-нибудь идеи по поводу доказатеств свойств.
      • Свойство 1 кажется мне очевидным (если мы знаем тот факт, что сумма и произведение полиномов есть полином). Свойства 2 и 3 доказаны по ссылкам на соответствующие сведения (там есть конкретно рассмотрение этих сведений для задач из класса [math]P[/math]).
        • Мне свойство 1 очевидным не кажется. Особенно какое-нибудь замыкание Клини. Но это несложные факты, поэтому я не прошу полное доказательство.
          • Написал довольно строгое доказательство замкнутости замыкания Клини. Остальные очень простые, смысла их расписывать не вижу.
    • Ссылка на определение констекстно-свободных языков в формулировке соответствующей теоремы.
      • Сделал. Заодно и на регулярные языки тоже сделал ссылку.
    • «Легко показать, что, по определению…» → «Легко показать, что, по определению [math]P[/math]…»
      • Ок. Сделал.
  • Остальная фигня:
    • В первом определении после «то есть» двоеточие.
      • Хорошо, сделал.
    • «Но, по теореме…» Запятая здесь не нужна. Мне кажется, лучше просто выпилить это «но».
      • Согласен, сделал.

TODO 2

  • В перечислениях в конце каждого пункта ставится либо точка (если пункт — отдельное предложение), либо точка с запятой (если все пункты — это одно баааальшое предложение). Это я про интерпретацию определния [math]P[/math].
    • Fixed.
  • У доказательства замкнутости относительно замыкания Клини проблемы с форматированием: начало имеет отступ в «2 таба», а конец — вообще не имеет отступа. Думаю, что лучше это доказательство выделить в отделиную лемму и оформить соответствующе.
    • Done.
  • Будем считать, что мы научились ставить ссылки для текста в техе («примечаниями»). Поэтому в предпоследнем абзаце [math]NP[/math] можно тоже написать нормально в техе.
    • Fixed.
  • Вставь ссылки на МТ и НМТ. МТ у нас в вики нет, так что эта ссылка — на википедию. Определние НМТ у нас есть.
    • Done.

Небольшой комментарий по поводу программ: в первой можно оставить «return p(f(w))»; во второй хочется замены «poses» на «positions». Grammar nazi Дмитрий Шевченко 17:30, 4 июня 2012 (GST)