Обсуждение:Заглавная страница — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм Решения)
(Форум: новая тема)
 
(не показано 10 промежуточных версий 2 участников)
Строка 31: Строка 31:
 
Что-то тут не так. Мне кстати последний вариант больше нравится.
 
Что-то тут не так. Мне кстати последний вариант больше нравится.
  
== 2-SAT Выполнимость ==
+
== Форум ==
  
Рассмотрим функцию, записанную в виде 2-КНФ (КНФ Крома). <br>
+
А есть ли на этой вики какое-то центральное место для обсуждений? Есть пара вопросов. В частности, не установить ли расширение FlaggedRevisions и гаджет HotCat? --[[Участник:Infovarius|Infovarius]] ([[Обсуждение участника:Infovarius|обсуждение]]) 12:54, 14 ноября 2018 (MSK)
2-SAT выполнимость данной функции - эта задача распределения аргументов таким образом, чтобы результат данной функции был равен 1.
 
 
 
 
 
== Алгоритм решения ==
 
 
 
 
 
Рассмотрим любой дизъюнкт функции: (a || b) <br>
 
Несложно заметить, что это равнозначно записи !a => b и !b => a <br>
 
 
 
Построим ориентированный граф, где вершинами будут аргументы и их отрицание, а ребрами будут ребра вида: !a => b и !b => a для каждого дизъюнкта функции (a || b) <br>
 
 
 
Для того, чтобы данная задача 2-SAT имела решение, необходимо и достаточно, чтобы для любой переменной x из вершины x нельзя достичь !x и из вершины !x нельзя достичь x одновременно. (!x => x && x => !x)
 
 
 
== Доказательство ==
 
 
 
Пусть 2-SAT имеет решение. <br>
 
Докажем, что не может быть такого, чтобы для любой переменной x из вершины x можно достичь !x и из вершины !x можно достичь x одновременно. (!x => x && x => !x) <br>
 
Тогда чтобы из !x достичь x (!x => x) x было верным, x должен быть равен 1. С другой стороны для того, чтобы из x достичь !x (!x => x) было верным, x должен быть равен 0. Отсюда следует противоречие. <br> <br>
 
 
 
Пусть для любой переменной x из вершины x нельзя достичь !x и из вершины !x нельзя достичь x одновременно. <br>
 
Докажем, что этого достаточно, чтобы 2-SAT имело решение. <br>
 
Пусть из !x можно достичь x, но из вершины x нельзя достичь !x. Докажем, что из x не достижимо такой y, что из y достижимо !y. (т.е. x => y => !y. (x = 1, y = 0)). <br>
 
Если из x => y, то (!x || y), отсюда следует (!y => !x). Тогда x => y => !y => !x. Следовательно x => !x. Противоречие.
 

Текущая версия на 12:54, 14 ноября 2018

  • Будьте любезны, я не учился в вашем учреждении, подскажите: что значит "Непроверяемые конспекты" на заглавной странице? Дело в том, что на первый взгляд, очень интересен опубликованные конспекты по математическому анализу, но они "непроверяемы"? Это что значит? В них могут содержаться ошибки?
    Именно это и значит. Данные конспекты пишут студенты, чтобы было проще готовиться к экзаменам. Они основаны на проводимых лекциях, сами студенты их перечитывают, но иногда в них могут содержаться случайные факты, ошибки, да и вообще они могут быть неполными. Хотя конспекты именно по математическому анализу достаточно хорошие. Дмитрий Коваников 10:43, 4 мая 2015 (GST)

самая крутая заглавная страница в мире, ИМХО

Коллеги, пожалуйста, давайте без вандализма. Я понимаю, что первое апреля и хочется пошутить. Но шутки должны быть смешными и к месту.

  • http://inkscape.org/ — программа для рисования в векторе. Подходит для изображения графов, марковских цепей, схем из функциональных элементов и т.п. Андрей Рыбак 23:01, 17 января 2011 (UTC)
  • черт, на вики-конспектах какая-то проблема со временем. В комментариях показывает одно, в последних изменениях - другое.(сообщение написано в 4:42) --Дмитрий Герасимов 08:42, 12 июня 2011 (UTC)
  • Кому вообще понадобились эти java-технологии? --Андрей Комаров 00:43, 18 февраля 2012 (GST)
    • Зря Андрей ты так про Джаву, зря-зря-зря... --Андрей Рыбак 23:30, 29 февраля 2012 (GST)
    • Это для первого курса 153N и второго 252N --Borisov 02:04, 4 марта 2012 (GST)
    • За год там ничего не появилось. Удалил. -- Dmitriy D. 08:14, 9 января 2013 (GST)

Ссылки на источники

  • Почему бы не организовать ссылки на источники, как в Википедии? С тегом <ref></ref> --Андрей Рыбак 20:13, 29 апреля 2012 (GST)

Имена преподавателей

Андрей Сергеевич Станкевич

Федор Николаевич Царев

Корнеев Георгий Александрович

Что-то тут не так. Мне кстати последний вариант больше нравится.

Форум

А есть ли на этой вики какое-то центральное место для обсуждений? Есть пара вопросов. В частности, не установить ли расширение FlaggedRevisions и гаджет HotCat? --Infovarius (обсуждение) 12:54, 14 ноября 2018 (MSK)