Обсуждение:Заглавная страница - История изменений

Infovarius: /* Форум */ новая тема

2018-11-14T09:54:21Z

‎Форум: новая тема

Shersh: Снята защита с «Обсуждение:Заглавная страница»: вандализм прекратился

2015-12-27T12:08:45Z

Снята защита с «Обсуждение:Заглавная страница»: вандализм прекратился

Shersh: Защищена страница «Обсуждение:Заглавная страница»: заядлый вандализм ([edit=sysop] (бессрочно) [move=sysop] (бессрочно))

2015-11-19T20:49:33Z

Защищена страница «Обсуждение:Заглавная страница»: заядлый вандализм ([edit=sysop] (бессрочно) [move=sysop] (бессрочно))

Shersh: переименовал 2-SAT Выполнимость в Обсуждение:Заглавная страница поверх перенаправления: ЗАПРЕЩАЕТСЯ ЗАНИМАТЬСЯ ВАНДАЛИЗМОМ!!!

2015-11-19T20:48:51Z

переименовал 2-SAT Выполнимость в Обсуждение:Заглавная страница поверх перенаправления: ЗАПРЕЩАЕТСЯ ЗАНИМАТЬСЯ ВАНДАЛИЗМОМ!!!

Shersh: ЗАПРЕЩАЕТСЯ МЕНЯТЬ ОБСУЖДЕНИЯ ГЛАВНОЙ СТРАНИЦЫ!!!

2015-11-19T20:47:02Z

ЗАПРЕЩАЕТСЯ МЕНЯТЬ ОБСУЖДЕНИЯ ГЛАВНОЙ СТРАНИЦЫ!!!

GARiK Carrot: переименовал Обсуждение:Заглавная страница в 2-SAT Выполнимость

2015-11-19T14:57:11Z

переименовал Обсуждение:Заглавная страница в 2-SAT Выполнимость

GARiK Carrot в 14:53, 19 ноября 2015

2015-11-19T14:53:58Z

Shersh: Данные изменения здесь неуместны

2015-11-18T21:05:19Z

Данные изменения здесь неуместны

Shersh: Данные изменения здесь неуместны

2015-11-18T21:05:02Z

Данные изменения здесь неуместны

Shersh: Данные изменения здесь неуместны

2015-11-18T21:04:35Z

Данные изменения здесь неуместны

← Предыдущая		Версия 09:54, 14 ноября 2018
Строка 30:		Строка 30:

	Что-то тут не так. Мне кстати последний вариант больше нравится.		Что-то тут не так. Мне кстати последний вариант больше нравится.
		+
		+	== Форум ==
		+
		+	А есть ли на этой вики какое-то центральное место для обсуждений? Есть пара вопросов. В частности, не установить ли расширение FlaggedRevisions и гаджет HotCat? --[[Участник:Infovarius\|Infovarius]] ([[Обсуждение участника:Infovarius\|обсуждение]]) 12:54, 14 ноября 2018 (MSK)

@@ Строка 1: / Строка 1: @@
-== 2-SAT Выполнимость ==
+* Будьте любезны, я не учился в вашем учреждении, подскажите: что значит "Непроверяемые конспекты" на заглавной странице? Дело в том, что на первый взгляд, очень интересен опубликованные конспекты по математическому анализу, но они "непроверяемы"? Это что значит? В них могут содержаться ошибки?
-Рассмотрим функцию, записанную в виде 2-КНФ (КНФ Крома). <br>
+самая крутая заглавная страница в мире, ИМХО
-== Алгоритм Решения ==
+* [http://inkscape.org/ http://inkscape.org/] — программа для рисования в векторе. Подходит для изображения графов, марковских цепей, схем из функциональных элементов и т.п. [[Участник:Rybak|Андрей Рыбак]] 23:01, 17 января 2011 (UTC)
-Рассмотрим любой дизъюнкт функции: (a || b) <br>
+* Кто сломал тег wikitex???111 --[[Участник:Dgerasimov|Дмитрий Герасимов]] 14:44, 10 октября 2011 (UTC)
-Построим ориентированный граф, где вершинами будут аргументы и их отрицание, а ребрами будут ребра вида: !a => b и !b => a для каждого дизъюнкта функции (a || b) <br>
+* Кому вообще понадобились эти java-технологии? --[[Участник:Komarov|Андрей Комаров]] 00:43, 18 февраля 2012 (GST)
-Для того, чтобы данная задача 2-SAT имела решение, необходимо и достаточно, чтобы для любой переменной x из вершины x нельзя достичь !x и из вершины !x нельзя достичь x одновременно. (!x => x && x => !x)
+== Ссылки на источники ==
-== Доказательство ==
+== Имена преподавателей ==
-Пусть 2-SAT имеет решение. <br>
+Андрей Сергеевич Станкевич
-Пусть для любой переменной x из вершины x нельзя достичь !x и из вершины !x нельзя достичь x одновременно. <br>
+Федор Николаевич Царев
-== Ссылки ==
+Корнеев Георгий Александрович
-*[http://e-maxx.ru/algo/2_sat MAXimal :: algo :: Задача 2-SAT (2-CNF) ]
+Что-то тут не так. Мне кстати последний вариант больше нравится.

@@ Строка 1: / Строка 1: @@
-* Будьте любезны, я не учился в вашем учреждении, подскажите: что значит "Непроверяемые конспекты" на заглавной странице? Дело в том, что на первый взгляд, очень интересен опубликованные конспекты по математическому анализу, но они "непроверяемы"? Это что значит? В них могут содержаться ошибки?
+== 2-SAT Выполнимость ==
-самая крутая заглавная страница в мире, ИМХО
+Рассмотрим функцию, записанную в виде 2-КНФ (КНФ Крома). <br>
-* [http://inkscape.org/ http://inkscape.org/] — программа для рисования в векторе. Подходит для изображения графов, марковских цепей, схем из функциональных элементов и т.п. [[Участник:Rybak|Андрей Рыбак]] 23:01, 17 января 2011 (UTC)
+== Алгоритм Решения ==
-* Кто сломал тег wikitex???111 --[[Участник:Dgerasimov|Дмитрий Герасимов]] 14:44, 10 октября 2011 (UTC)
+Рассмотрим любой дизъюнкт функции: (a || b) <br>
-* Кому вообще понадобились эти java-технологии? --[[Участник:Komarov|Андрей Комаров]] 00:43, 18 февраля 2012 (GST)
+Построим ориентированный граф, где вершинами будут аргументы и их отрицание, а ребрами будут ребра вида: !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 одновременно. <br>
-Корнеев Георгий Александрович
+== Ссылки ==
-Что-то тут не так. Мне кстати последний вариант больше нравится.
+*[http://e-maxx.ru/algo/2_sat MAXimal :: algo :: Задача 2-SAT (2-CNF) ]

← Предыдущая		Версия 21:05, 18 ноября 2015
Строка 30:		Строка 30:

	Что-то тут не так. Мне кстати последний вариант больше нравится.		Что-то тут не так. Мне кстати последний вариант больше нравится.
−
−	~~== 2-SAT Выполнимость ==~~
−
−	~~Рассмотрим функцию, записанную в виде 2-КНФ (КНФ Крома). <br>~~
−	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. Противоречие.~~

@@ Строка 37: / Строка 37: @@
-== Алгоритм решения ==
+== Алгоритм Решения ==
@@ Строка 45: / Строка 45: @@
 Построим ориентированный граф, где вершинами будут аргументы и их отрицание, а ребрами будут ребра вида: !a => b и !b => a для каждого дизъюнкта функции (a || b) <br>
 Для того, чтобы данная задача 2-SAT имела решение, необходимо и достаточно, чтобы для любой переменной x из вершины x нельзя достичь !x и из вершины !x нельзя достичь x одновременно. (!x => x && x => !x)
 == Доказательство ==

← Предыдущая	Версия 12:08, 27 декабря 2015
(нет различий)

← Предыдущая	Версия 20:49, 19 ноября 2015
(нет различий)

← Предыдущая	Версия 20:48, 19 ноября 2015
(нет различий)

← Предыдущая	Версия 14:57, 19 ноября 2015
(нет различий)

← Предыдущая		Версия 21:04, 18 ноября 2015
Строка 57:		Строка 57:
	Пусть из !x можно достичь x, но из вершины x нельзя достичь !x. Докажем, что из x не достижимо такой y, что из y достижимо !y. (т.е. x => y => !y. (x = 1, y = 0)). <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. Противоречие.		Если из x => y, то (!x \|\| y), отсюда следует (!y => !x). Тогда x => y => !y => !x. Следовательно x => !x. Противоречие.
−
−
−	~~== Источники ==~~
−
−	~~MAXimal :: algo :: Задача 2-SAT (2-CNF) <ref> http://e-maxx.ru/algo/2_sat </ref>~~