NH4Cl + Ca(OH)2 CaCl2 + 2NH3­ + 2Н2O (NH4)2SO4 + 2KOH K2SO4 + 2NH3­ + 2Н2O

Задача о сумме

Задача о выполнимости схемы

Рассмотрим схему из функциональных элементов «и», «или», «не» с n битовыми входами и одним выходом, состоящую не более, чем из O() элементов – рис 6.4

Будем понимать под выполняющим набором значений из множества {0,1} на входе схемы, такой набор входов – значения x1,…,xn, при котором на выходе схемы будет значение «1».

Формулировка задачи – существует ли для данной схемы выполняющий набор значений входа. Очевидно, что задача принадлежит классу NP – проверка предъявленного выполняющего набора не сложнее количества функциональных элементов, и следовательно не больше чем O().

Это была одна из первых задач, для которой была доказана ее NP полнота, т.е. любая задача из класса NP полиномиально сводима к задаче о выполнимости схемы.

Решение этой задачи может быть получено перебором всех возможных значений входа с последующей проверкой на соответствие условию выполняющего набора. В худшем случае придется проверить все возможные значения входа, что приводит к оценке Для этой, как и для всех других NP–полных задач не известен полиномиальный алгоритм решения.

Уже рассмотренная задача о сумме также является NP–полной, отметим, что если количество слагаемых фиксировано, то сложность задачи является полиномиальной, так как:

для 2-х слагаемых

для 3-х слагаемых

Однако в общем случае придется перебирать 2^n различных вариантов, так как по биномиальной теореме , а при a=b=1, имеем:

Примеры задач:

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

Если Вы хотите рассадить в своем зоопарке по клеткам бегемотов, то Вам необходимо решить задачу о независимом множестве. Ведь известно, что бегемот из первой клетки не даст спокойно жить бегемотам из нулевой и третьей клеток (т.к. в графе есть ребра 1-0 и 1-3) и.т.д. Так, Вам нужно выбрать максимальное количество клеток, попарно не соединенных ребрами. Это и есть задача о независимом множестве.

Пример для клики. Если Вы хотите организовать самую большую вечеринку для «своих» (то есть, чтобы на вечеринке каждый знал каждого), то Вам необходимо решить задачу о максимальной клике. Обозначьте друзей вершинами, проведите ребро между двумя вершинами, если два этих друга знакомы и решите задачу о максимальной клике.

Химические свойства

Образование ковалентной связи по донорно–акцепторному механизму.

3. Аммиак – основание Льюиса. Его раствор в воде (аммиачная вода, нашатырный спирт) имеет щелочную реакцию (лакмус – синий; фенолфталеин – малиновый) из–за образования гидроксида аммония. NH₃ + Н₂O ↔NH₃∙H₂O ↔ NH₄⁺ + OH^–

3. Аммиак реагирует с кислотами с образованием солей аммония.

NH₃ + HCl →NH₄Cl 2NH₃ + H₂SO₄ →(NH₄)₂SO₄ NH₃ + H₂O + CO₂ →NH₄HCO₃

Аммиак – восстановитель (окисляется до N₂ или N⁺²O)

1. Разложение при нагревании 2N^–3H₃ →N₂⁰ + 3H₂ (нагревание)

2. Взаимодействие с кислородом:

a) без катализатора 4N^–3H₃ + 3O₂ →2N₂⁰ + 6Н₂O (горение)

б) каталитическое окисление (kat = Pt) 4N^–3H₃ + 5O₂ 4N⁺²O + 6Н₂O

3. Восстановление оксидов некоторых металлов

Дата добавления: 2014-01-07